Differentiable Invariant Sets for Hybrid Limit Cycles with Application to Legged Robots

This paper presents a three-step numerical method using parametric embeddings to compute and formally verify forward-invariant sets around hybrid limit cycles for legged robots, which is then integrated into a bi-level optimization framework to design tracking controllers that maximize the size of these robustness regions.

The Gist

The Big Picture: The "Unbreakable Bubble" for a Walking Robot

Imagine you have a robot that walks on two legs. You want it to walk forever without falling over. In the world of robotics, this is tricky because the robot is constantly hitting the ground, jumping, and changing its motion. It's like a gymnast doing a routine where they land, bounce, and switch legs in a split second.

The engineers in this paper asked a simple question: "How big of a 'safety bubble' can we draw around this robot's perfect walking path so that even if the robot gets pushed or stumbles, it will always bounce back to the correct path and never fall?"

They call this safety bubble a "Forward Invariant Set." If the robot starts inside this bubble, it is mathematically guaranteed to stay inside it forever.

The Problem: Why is this so hard?

Usually, to find this safety bubble, engineers use heavy, slow math (like trying to solve a massive Sudoku puzzle that gets exponentially harder every time you add a new variable).

• The Old Way: It's like trying to map every single possible path a falling leaf could take through a storm. It takes hours or days of computer time, and it often fails for complex robots like bipedal walkers.
• The Challenge: The robot's movement isn't smooth; it's "hybrid." It flows smoothly (walking) but then suddenly "jumps" (hitting the ground). This sudden jump makes the math very messy.

The Solution: The "Stretchy Rubber Sheet" Method

The authors developed a new, faster way to find this safety bubble. Here is how they did it, broken down into three steps:

1. The "Rubber Sheet" (The Shape)

Instead of trying to track every single point the robot could be, they imagine the robot's possible positions as a stretchy, 3D rubber sheet (mathematically called a "normotope," which is just a fancy ellipsoid or egg shape).

• They start with a small rubber sheet around the robot's perfect walking path.
• They use a special math tool (called immrax) that acts like a super-fast, stretchy camera. This tool predicts how the rubber sheet will stretch, shrink, or twist as the robot walks forward.

2. The "Doorway" (The Impact)

When the robot's foot hits the ground, it's like passing through a magical doorway.

• The Jump: The moment the foot hits the ground, the robot's speed and position change instantly (like a ball bouncing off a wall).
• The Check: The authors' method checks: "If our rubber sheet hits this doorway, does it get squished into a smaller shape, or does it explode outward?"
• They catalog exactly where the rubber sheet touches the ground and how it bounces back.

3. The "Loop" (The Guarantee)

The magic happens when they look at the whole cycle.

• They let the rubber sheet travel through one full step of walking and hitting the ground.
• The Test: If the rubber sheet comes back out of the cycle smaller (or exactly the same size) than when it started, they have found their safety bubble!
• The Logic: If the robot starts inside the bubble, and the bubble shrinks or stays the same size after every step, the robot can never escape. It is trapped in a safe loop.

The Secret Weapon: "Differentiable" Math

The coolest part of this paper is that their math tool is "differentiable."

• Analogy: Imagine you are trying to find the best way to inflate a balloon so it fits through a door.
  • Old Way: You guess a size, try to fit it, fail, guess again, try again. (Slow and blind).
  • New Way: The balloon has a "smart sensor" that tells you exactly how much to squeeze or stretch it to fit perfectly. It gives you a "gradient" (a slope) that points the way to the best shape.
• Because their math is differentiable, they can use this "smart sensor" to automatically design a controller (a brain for the robot) that makes the safety bubble as big as possible. They didn't just find a bubble; they found the biggest possible bubble the robot can handle.

The Results: A Giant Leap for Robot Walking

They tested this on a simple 2D walking robot (like a stick figure with legs).

• Speed: Their method took 19 seconds to calculate the safety bubble.
• Comparison: Older methods took 17 minutes or even 36 hours for similar problems.
• Success: When they used their new method to design a controller, the robot's safety bubble grew 4.25 times larger. This means the robot could handle much bigger pushes and stumbles without falling over.

Summary

The authors built a fast, stretchy, smart math tool that draws a "safety bubble" around a walking robot. They proved that if the robot stays in the bubble, it will never fall. Even better, they used the tool's "smart sensors" to automatically make that bubble as big as possible, giving the robot a much wider margin for error. This is a huge step toward making robots that can walk in the real world without needing a perfect, controlled environment.

Technical Summary

1. Problem Statement

The paper addresses the challenge of analyzing the robustness of hybrid dynamical systems, specifically those exhibiting periodic behavior like legged robots.

• Core Challenge: For hybrid systems (continuous dynamics with discrete transitions/impacts), characterizing the forward-invariant set (a region of attraction) containing a limit cycle is crucial for safety and stability but computationally expensive.
• Limitations of Existing Methods:
  • Sum-of-Squares (SoS) Programming: Scales poorly with system dimension (combinatorial growth in variables), limiting it to low-dimensional systems (<10 states).
  • Hamilton-Jacobi (HJ) Reachability: Suffers from the "curse of dimensionality," where computational complexity grows exponentially with state space dimension.
• Goal: Develop a scalable, differentiable method to compute forward-invariant sets for high-dimensional hybrid systems to facilitate robust control design.

2. Methodology

The authors propose a three-step approach using parametric reachability and interval analysis to overapproximate reachable sets. The framework relies on the immrax library (built on JAX) for efficient, differentiable set propagation.

A. Theoretical Framework

1. Parametric Embedding System:
   • Instead of tracking individual trajectories, the method propagates a normotope (an ellipsoid defined by a center $\bar{x}$, a shaping matrix $\alpha$, and an offset $y$).
   • It uses Linear Differential Inclusions (LDI) to bound the error dynamics of the continuous flow. The evolution of the ellipsoid parameters is governed by a differential equation system involving the logarithmic norm.
2. Hybrid Extension (The "Step-to-Step" Map):
   • The method extends continuous reachability to hybrid systems by handling the Guard Surface ($S$) and the Reset Map ($\Delta$).
   • Theorem 1 (Forward Invariance Condition): The authors derive conditions under which a computed "tube" of reachable states is forward invariant.
     • The tube must flow from an initial state, intersect the guard surface transversally, and after applying the reset map, the resulting set must be a strict subset of the initial set.
   • Theorem 2 (Intersection Cataloging): To handle the reset map efficiently, the method slices the $n$-dimensional ellipsoid with the $(n-1)$-dimensional guard surface (an affine subspace). This intersection is mathematically proven to be a lower-dimensional ellipsoid, allowing for exact computation of the post-impact set bounds.

B. Algorithmic Implementation

1. Initialization: An initial ellipsoid is defined around the nominal periodic orbit. The shaping matrix is derived using contraction theory (solving a semi-definite program to find a decaying norm).
2. Continuous Propagation: The embedding system is simulated forward until the nominal trajectory crosses the guard surface and the entire ellipsoid has passed through it.
3. Discrete Reset:
   • The intersection of the ellipsoid with the guard is computed (slicing).
   • The reset map is applied to this intersection using linear inclusions to bound the post-impact set.
   • A gain factor ($\gamma$) is computed. If $\gamma \leq 1$, the set is forward invariant.
4. Optimization (Bisection): A bisection algorithm scales the initial ellipsoid to find the largest possible invariant set.

C. Differentiability and Control Design

• A key innovation is that the entire pipeline (reachability computation, intersection, reset bounding) is differentiable via JAX's automatic differentiation.
• This allows the invariant set size (or the gain $\gamma$) to be used as a cost function in a bi-level optimization framework.
• Application: The authors optimize a tracking controller gain ($K$) to maximize the size of the invariant set, effectively designing a controller that is robust to the largest possible disturbances.

3. Key Contributions

1. Theoretical Extension: Extended parametric reachability theory to hybrid systems, providing formal conditions for the forward invariance of a parametric reachable set around a limit cycle.
2. Efficient Verification Procedure: Introduced a procedure using interval analysis and QR decomposition to efficiently verify invariance by slicing ellipsoids with guard surfaces and bounding reset map effects.
3. Differentiable Control Design: Demonstrated how the differentiability of the reachability framework can be leveraged to design controllers (via gradient descent) that maximize the region of attraction, moving beyond simple stability verification to active robustness optimization.

4. Results

The methodology was applied to a simplified planar bipedal walker (4-state system with a telescoping leg).

• System Setup: The robot was modeled with continuous dynamics and an inelastic collision reset. A nominal periodic gait was generated via trajectory optimization.
• Invariant Tube Computation:
  • Without continuous tracking control, the method verified a forward-invariant tube around the limit cycle.
  • Monte Carlo Verification: 100 trajectories initialized on the boundary of the computed tube were simulated for 15 steps; all remained within the tube, empirically validating the theoretical guarantee.
• Control Design:
  • Using the bi-level optimization (Algorithm 1), a tracking controller was designed to maximize the invariant set.
  • Performance: The optimized controller increased the size of the invariant tube by a factor of 4.25 compared to the step-to-step controller alone.
• Computational Efficiency:
  • The method computed the reachable set for the 4D system in 19.56 seconds (including JIT compilation).
  • Comparison: This is significantly faster than SoS programming (17.7 minutes for a similar system) and HJ reachability (36 hours).

5. Significance and Future Work

• Scalability: By avoiding the curse of dimensionality associated with HJ and the combinatorial explosion of SoS, this approach offers a path to analyzing higher-dimensional legged robots (e.g., 3D walkers, quadrupeds).
• Integration with Control: The differentiability of the invariant set metric allows it to be directly embedded into control synthesis loops, enabling "robustness-by-design."
• Limitations:
  • Currently assumes the guard surface can be represented as a linear hyperplane in some coordinate system (though a transformation map $\phi$ was found for the walker).
  • The method provides a conservative overapproximation due to interval analysis.
• Future Directions: Investigating coordinate maps for more complex hybrid systems and integrating tube refinement steps to reduce conservatism.

In summary, this paper presents a computationally efficient, differentiable framework for certifying the robustness of legged robots, bridging the gap between formal verification and practical control design.