Finite-Step Invariant Sets for Hybrid Systems with Probabilistic Guarantees

This paper proposes a sampling-based optimization framework that computes finite-step invariant ellipsoids for hybrid systems using Poincare return maps, providing probabilistic guarantees on invariance even when system dynamics are accessible only through forward simulation.

The Gist

Imagine you are trying to teach a robot to walk down a hill. You want to be sure that if you give the robot a little nudge—maybe a gust of wind or a pebble under its foot—it won't fall over. Instead, it should wobble a bit, find its balance, and keep walking.

In the world of robotics, this "wobble and recover" ability is called robustness. To prove a robot is robust, engineers need to find a "safe zone" around its perfect walking pattern. If the robot starts anywhere inside this safe zone, it will stay inside it forever, no matter how many steps it takes.

This paper introduces a clever new way to find that safe zone, even when the math describing the robot is too messy to solve with a standard calculator.

The Problem: The "Black Box" Robot

Usually, to find a safe zone, you need a perfect mathematical formula for how the robot moves. But for complex robots (like a walking robot with knees and ankles), the math is a "black box." You can't write down a simple equation; you can only run a computer simulation to see what happens.

Furthermore, the robot's movement is "hybrid." It flows smoothly like water (swinging a leg), but then suddenly "snaps" like a light switch when the foot hits the ground. This makes finding the safe zone incredibly hard. Traditional methods often guess a simple shape (like a perfect circle) and hope it fits, but real robots are rarely that simple.

The Solution: The "Try and Check" Game

The authors propose a method that is less like solving a math equation and more like playing a game of "Hot and Cold" with a massive amount of data.

Here is how their algorithm works, using a simple analogy:

1. The Poincaré Map: The "Step Counter"

Instead of watching the robot walk continuously, the researchers only look at the robot at one specific moment: the exact instant the foot hits the ground.

• Imagine taking a photo of the robot every time it steps.
• If you look at the sequence of photos, you can see how the robot's state changes from one step to the next.
• This turns a complex, continuous walking motion into a simple "step-to-step" game.

2. The "Safe Bubble" (The Ellipsoid)

The researchers start with a big, invisible bubble (mathematically called an ellipsoid, which is like a squashed or stretched sphere) around the robot's perfect walking step.

• The Goal: Shrink this bubble until it fits perfectly around the "safe zone," but not so small that it cuts off any safe paths.

3. The Sampling Game (The "Throw and Catch")

Since they can't solve the math directly, they use a sampling strategy:

1. Throw Darts: They randomly pick thousands of points inside their current big bubble. Think of these as "test robots" starting at slightly different positions.
2. Run the Simulation: They run the simulation for each test robot to see where it lands on the next step.
3. The "Escape" Test:
   • If a test robot lands inside the bubble, it's a "good" point. It stayed safe.
   • If a test robot lands outside the bubble, it "escaped." The bubble is too small or in the wrong shape.
4. Shrink and Refine: They take all the "good" points (the ones that stayed safe) and draw a new, tighter bubble that fits them perfectly. They throw away the points that escaped.
5. Repeat: They do this over and over. The bubble gets tighter and tighter, molding itself to the actual shape of the safe zone.

The "Magic Guarantee": The "Holdout" Trick

Here is the most brilliant part. How do they know their bubble is actually safe for every possible starting point, not just the ones they tested?

They use a statistical trick called the Holdout Method.

• Imagine you are a teacher grading a test. You give the student 100 practice questions (the training set) to learn from.
• Then, you give them 50 brand new questions (the holdout set) that they have never seen before.
• If the student gets 49 out of 50 right, you can be very confident they will pass the real exam.

In this paper, the "students" are the test robots. The algorithm checks the "new" robots to see how many escape. If only a tiny fraction escape (say, 1 out of 100), the math guarantees that the bubble is safe for 99% of all possible scenarios with a very high level of confidence.

Why This Matters

• It's Flexible: Unlike old methods that forced the safe zone to be a perfect circle, this method lets the safe zone be an oval or a stretched shape, fitting the robot's actual physics much better.
• It Works with "Black Boxes": You don't need the math formulas. You just need a simulator.
• Real-World Proof: They tested this on a "Compass Gait" walker (a simple 2D walking robot). The algorithm successfully found a safe zone that was much more accurate than previous methods, proving the robot could handle bumps and nudges without falling.

The Bottom Line

This paper gives engineers a new, powerful tool to say: "I don't know the exact math of this robot, but I have run thousands of simulations, and I can guarantee with 99.9% certainty that if you nudge it, it will stay on its feet."

It turns the scary problem of "Will my robot fall?" into a solvable game of "Throw darts, check the results, and shrink the target," backed by solid math that proves the safety.

Technical Summary

1. Problem Statement

Hybrid dynamical systems, which combine continuous evolution with discrete events (e.g., legged locomotion, power electronics), are often analyzed using Poincaré return maps. These maps reduce the stability analysis of periodic orbits to discrete-time fixed-point problems.

• The Challenge: While linearization provides local stability, practical applications require robustness to disturbances. This requires identifying forward-invariant sets (regions where trajectories remain forever).
• The Difficulty: Computing these sets is computationally intractable for general hybrid systems because:
  1. The return map is often available only via black-box simulation (no analytical gradients).
  2. The dynamics are highly nonlinear, leading to non-convex optimization problems.
  3. Existing methods often rely on heuristics or restrictive parameterizations (e.g., simple balls) that lack formal guarantees.
• The Goal: Develop a framework to compute finite-step invariant ellipsoids around a nominal periodic orbit using only sampled evaluations of the return map, accompanied by probabilistic guarantees on their validity.

2. Methodology

The authors propose an iterative, sampling-based optimization framework that combines Minimum Volume Ellipsoid (MVEE) fitting with the Holdout Method to derive Probably Approximately Correct (PAC) bounds.

A. Core Algorithm (Iterative Refinement)

The algorithm (Alg. 1) operates on a candidate ellipsoid $E$ defined by parameters $(A, b)$:

1. Sampling: Draw $N$ i.i.d. samples uniformly from the current ellipsoid $E$.
2. Propagation: Apply the Poincaré map $P$ to these samples to generate return points.
3. Partitioning:
   • Inliers ($U$): Input samples whose return points remain inside $E$.
   • Outliers ($V$): Input samples whose return points escape $E$.
4. Optimization (Refinement): If the number of outliers is too high, the algorithm fits a new, smaller ellipsoid to the set of inliers $U$ by solving a convex optimization problem (Minimizing volume subject to $U \subset E_{new}$).
5. Termination: The process repeats until the estimated violation probability satisfies a user-defined accuracy threshold $\epsilon$.

B. Probabilistic Guarantees (Holdout Method)

Instead of assuming the training samples perfectly represent the system, the authors use the Holdout Method to provide rigorous confidence bounds:

• They calculate the number of violations ($v$) in the sample set.
• Using Binomial Tail Inversion, they compute the maximum true error $\epsilon$ such that the probability of observing $v$ or more violations is at least $\beta$ (confidence level).
• This yields a PAC guarantee: $P(\text{violation} > \epsilon) \leq \beta$.
• Note: While the algorithm guarantees one-step invariance, the paper investigates the robustness of these bounds over $k$-steps.

3. Key Contributions

1. Algorithmic Framework: An iterative algorithm that frames invariant set computation as a sampling-based optimization problem, specifically targeting ellipsoidal sets for hybrid systems.
2. Probabilistic Certification: Integration of the holdout method to provide finite-sample PAC guarantees, ensuring the computed set is invariant with high confidence despite using a limited number of simulations.
3. Expressive Representation: Moving beyond simple uniform balls (used in prior work) to ellipsoids, which better capture the geometry of the return map and yield less conservative robustness estimates.
4. Empirical Validation: Demonstration on three systems, including a complex, high-dimensional bipedal walking model where the true invariant set is unknown.

4. Numerical Results

The approach was tested on three systems:

• Convex Expander-Contractor (CEC): A 2D system with a known analytical invariant set.
  • Result: The algorithm converged in ~5 iterations, recovering an ellipsoid with a volume only 1.1% smaller than the true invariant set.
• Nonconvex Expander-Contractor (NEC): A 2D system with a non-convex invariant set (two disconnected circles).
  • Result: The ellipsoidal representation resulted in an under-approximation (22% volume loss) and higher error ($\epsilon \approx 0.07$).
  • Insight: The paper discusses extending the method to Radial Basis Functions (RBFs) to handle non-convexity, showing RBFs could recover the true set almost perfectly in this case.
• Compass-Gait Walker: A 2-DOF planar bipedal robot (4D state space, 3D Poincaré map).
  • Result: The algorithm converged in 74 iterations to a conservative ellipsoid. Multi-step verification showed that while some points temporarily left the set, they returned, suggesting the one-step guarantee is robust for practical stability analysis.

5. Significance and Limitations

Significance:

• Robustness Analysis: Provides a practical tool for quantifying the disturbance bounds under which complex robotic gaits (like walking) remain stable.
• Black-Box Compatibility: Does not require analytical models or gradients, making it applicable to systems simulated in complex physics engines.
• Formal Guarantees: Bridges the gap between heuristic simulation and formal verification by providing statistical confidence bounds.

Limitations:

• Convexity Assumption: The current method uses ellipsoids, which may be overly conservative for systems with non-convex invariant sets (though RBF extensions are proposed).
• Curse of Dimensionality: Sampling-based approaches require exponentially more samples as dimensionality increases. The authors suggest mitigating this via GPU parallelization (e.g., using Brax or Isaac Gym).
• Convergence: Without structural assumptions, convergence to a specific accuracy $\epsilon$ is not theoretically guaranteed, though empirical results show consistent convergence.

Conclusion

This work establishes a foundation for probabilistic verification in robust control of hybrid systems. By leveraging sampling-based optimization and holdout methods, it enables the computation of finite-step invariant sets with rigorous statistical guarantees, offering a viable path for analyzing stability in complex, simulation-heavy robotic systems like bipedal walkers.