Contact-rich robotic systems, such as legged robots and manipulators, are often represented as hybrid systems. However, the stability analysis and region-of-attraction computation for these systems is often challenging because of the discontinuous state changes upon contact (also referred to as state resets). In this work, we cast the computation of region-ofattraction as a Hamilton-Jacobi (HJ) reachability problem. This enables us to leverage HJ reachability tools that are compatible with general nonlinear system dynamics, and can formally deal with state and input constraints as well as bounded disturbances. Our main contribution is the generalization of HJ reachability framework to account for the discontinuous state changes originating from state resets, which has remained a challenge until now. We apply our approach for computing region-of-attractions for several underactuated walking robots and demonstrate that the proposed approach can (a) recover a bigger region-of-attraction than state-of-the-art approaches, (b) handle state resets, nonlinear dynamics, external disturbances, and input constraints, and (c) also provides a stabilizing controller for the system that can leverage the state resets for enhancing system stability.

Many robotic systems are complicated by their Hybrid System nature due to contacts. In this work, we are interested in attaining stable walking behaviors for legged robots from various configurations. In doing so, it is desirable that the robot leverages contacts with the ground for enhancing its stability.

Examples of hybrid robotics systems. Hybrid system, roughly speaking is any system that cannot be described by one mode of dynamics. Robots that people are really excited to use for practical applications these days are mostly hybrid systems, due to their nature of interacting with the environment through contacts, impacts or due to many other factors. Examples of such systems include Legged robots, humanoids, aerial vehicles, manipulators with grasping, and multi-robot tasks. (Image sources: Stanford, Kuka, Skydio, UofT, OpenAI, MIT, Boston Dynamics)

We aim to achieve this by solving an optimal control problem for the hybrid system models that describe the walking motion of legged robots. The main challenge is that constructive methods for solving this based on the Dynamic Programming are well established for continuous systems, however, are scarcely developed for contact-rich systems.

First, stabilizing the walking motion is translated into a reachability problem where the target set is the walking gait.

Examples of hybrid robotics systems. Hybrid system, roughly speaking is any system that cannot be described by one mode of dynamics. Robots that people are really excited to use for practical applications these days are mostly hybrid systems, due to their nature of interacting with the environment through contacts, impacts or due to many other factors. Examples of such systems include Legged robots, humanoids, aerial vehicles, manipulators with grasping, and multi-robot tasks. (Image sources: Stanford, Kuka, Skydio, UofT, OpenAI, MIT, Boston Dynamics)

Then, to solve this reachability problem, existing Dynamic Programming reachability frameworks are extended to hybrid systems with discontinuous reset maps by incorporating the Value Remapping principle in the algorithm. The main idea of the value remapping is that the value function at a pre-reset state (those on the switching surface) is same as the value function at the post-reset state. This value remapping is the bellman principle of optimality with respect to the discrete transition of the hybrid dynamics. Finally, the value remapping does not increase the computational complexity to the existing algorithm.

Cartoon description of the value remapping principle. The plane S indicates switching surface, the set of states where the discrete transition is applied defined by the reset map. For a walking robot, the reset map is defined by the ground impact, and the switching surface captures all the states where the swing foot hits the ground. The plane S+ indicates the image of the reset map. The main idea of the value remapping is that the value function at a pre-reset state (those on the switching surface) is same as the value function at the post-reset state.

(a) Rimless wheel system. (b) Teleporting Dubins car system. The car “teleports” to the other side of the x-axis whenever it hits the x-axis from a positive y-direction. (c) Two-link Compass-gait walker. The pink indicates the stance leg, and the blue indicates the swing leg.

The rimless wheel is a popular model of a passivedynamic walker. One of the reasons for its popularity is that RoA can be computed analytically for the rimless wheel. Using the SOS programming, we are able to recover only a subset of the RoA. Our approach is able to recover the entire RoA of the system.

Regions of Attraction (RoA) for the rimless wheel limit cycle (black): (Left) The true RoA is shown in light pink. RoA obtained using SOS programming is shown in purple. (Right) RoA computed using our approach. The proposed approach is able to recover the entire RoA. (Left is reproduced from Manchester et al., Regions of attraction for hybrid limit cycles of walking robots.)

We introduce state resets to a well-known Dubins car system which makes the car “teleport”. The key principles of our method are well exposed in its design and results. Whenever the car hits the x-axis, it will reset to the other side of the state space. The reference periodic orbit is a semicircular trajectory centered at the origin rotating in the counter-clockwise direction. The reset map has the contraction property, so it will be desirable to exploit this reset or "teleport" to reach the target faster.

We can first compute the Regions of Attraction (RoA) of the orbit, by computing the reachability value function backward in time based on our numerical algorithm.

Regions of Attraction (RoA) for the Teleporting Dubins Car: Our algorithm verifies the RoA of the orbit (in blue) by solving the dynamic programming backward in time. Thus, the verified RoA gradually expands from the orbit as we run our algorithm. Note that a big portion of the region near the switching surface (x-axis) is captured in the RoA, since the "teleport" is more accessible to the states in this region.

Then, for an initial state that is included in the computed RoA, when we evaluate the optimal controller resulting from the computed value function, the trajectory is able to reach the orbit in the most time-optimal way.

The optimal trajectory computed from our method reaches the target set after 4.3s by exploiting the teleport twice.

In contrast, a baseline controller designed based on feedback linearization takes significantly longer time to reach the orbit, since it does not have the knowledge of how to utilize the teleport.

The feedback-linearization-based controller reaches the target set after 11.9s. It does not know how to exploit the reset map.

We next consider a compass-gait walker, which consists of two links with an actuated joint between them. We consider a hybrid model of walking, with alternating phases of a continuous-time singlesupport phase followed by an instantaneous inelastic impact of the swing leg with the ground. The switching surface is defined as the set of states where the swing foot strikes the ground with a negative velocity.

The target hybrid limit cycle we wish to stabilize to is designed as a reference walking gait, which is tracked by a baseline controller designed based on feedback linearization and Control Lyapunov Function-based Quardartic Program (CLF-QP).

The robot in the nominal walking motion under the CLF-QP baseline controller. Left is the corresponding phase portrait in the configuration space.

Now let’s say someone pushed the robot hard so it shifted to this new initial state that is quite far from the usual walking motion. On the perturbed initial state, The robot has a big momentum to the backward direction. If we apply the same baseline controller from this state, it fails to stabilize to the walking gait.

The baseline controller failing to stabilize back to the walking motion from a largely perturbed initial state.

If we apply the optimal controller computed from our method to the same initial state, the robot is able to successfully stabilize back to the walking gait. Notice that it steps on the ground first, and exploit the ground impact to absorb the adverse momentum to stabilize the robot more easily.

The optimal controller recovering to the gait from the same perturbation.

Finally, we can also visualize the Region of Attractions verified from our method. First, we apply our method to the closed loop dynamics of the baseline controller. Although it is designed to be locally stabilizing, the verified RoA comprises only a small neighborhood of the reference gait. By contrast, exploiting the full control capacity limited by the torque saturation and the reset map, we are able to verify that the actual stabilizable region is much bigger than what can be achieved by the CLF-QP controller. Finally, we can also introduce disturbance to the robot’s dynamics: an unmodeled repulsive or stiction torque applied to the joint between the leg. The RoA computed under the robust optimal control setting is visualized next. Since now we only verify states that are robustly stabilizable to the gait, the resulting RoA is smaller than the non-robust RoA. However, it still shows that by applying the robust optimal controller, it is able to robustly stabilize a larger set of states than the CLF-QP.

RoAs for the compass-gait walker visualized by their projection on the configuraion space. (a) RoA for the closed-loop dynamics under the CLF-QP controller. (b) RoA that is verified by allowing the full control capacity. (c) Robust RoA by introducing the disturbance to the dynamics.