Finite-Step Invariant Sets for Hybrid Systems with Probabilistic Guarantees

arXiv:2604.05102 · eess.SY, cs.RO, cs.SY · Submitted 2026-04-06 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: I'm Rosa.

Dev: And I'm Dev, here with Taro.

Rosa: We're looking at the paper: "Finite-Step Invariant Sets for Hybrid Systems with Probabilistic Guarantees".

Paper summary: Rosa: To wrap up, we're talking about this paper "Finite-Step Invariant Sets for Hybrid Systems with Probabilistic Guarantees" by Varun Madabushi and Elizabeth Dietrich <ref:2604.05102#pg1>.

Dev: The authors developed an iterative algorithm that uses sampling-based optimization on the discrete dynamics of a Poincare map to compute finite-step invariant sets <ref:2604.05102#pg2>.

Taro: What this means for us is that we can get a statistically sound idea of the system's stability bounds even when we don't have perfect knowledge of the system dynamics <ref:2604.05102#pg1>.

Rosa: It shows the effectiveness of this algorithm on three different dynamical systems, including one where the true invariant set isn't explicitly known <ref:2604.05102#pg1>.

Dev: Ultimately, it establishes a foundation for future work on probabilistic verification in robust bipedal robot control because we now have a method to quantify the violation of finite-step set invariance <ref:2604.05102#pg3>.

Conclusion: Rosa: So we're wrapping up on this paper "Finite-Step Invariant Sets for Hybrid Systems with Probabilistic Guarantees." Basically, they've figured out a way to find the stable regions of these complex hybrid systems using sampling and optimization.

Dev: That’s right. They use the discrete movement of the system—what we call Poincare dynamics—to build an ellipsoid that stays around the main periodic orbit.

Rosa: And it’s not just about finding a rough shape; they give you a probabilistic guarantee on how well that ellipsoid captures the true stable set after just one step. That means you know your prediction has a certain level of accuracy.

Taro: So, if I'm running a control system and I need to know it won't go completely haywire in the next few steps, this method gives me a statistical confidence measure on that safety.

Dev: Exactly. They’ve shown this works on three different types of systems, including one where they didn't even know what the true stable set looked like beforehand. That's pretty significant for real-time control loops.

Rosa: It moves us away from just theoretical stability and into something practical for things like bipedal robots or power electronics where the dynamics are messy and you can't model everything perfectly.

Dev: But they’ve also flagged a limitation, which is important—the method gets really computationally expensive if the system is very high-dimensional, meaning a lot of samples are needed to do it right.

Rosa: So it’s powerful because it gives you the guarantee you need, but you have to be mindful of how much data you're willing to throw at the problem. That opens up some interesting questions about how we balance accuracy and speed in robotics.

Varun Madabushi, Elizabeth Dietrich, Hanna Krasowski, Maegan Tucker

Georgia Institute of Technology · University of California, Berkeley

eess.SY, cs.RO, cs.SY

Submitted: 2026-04-06

Updated: 2026-11-16

Code: https://github.com/dynamicmobility/finite-step-invariance

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 84/100

The gist: Poincare return maps are fundamental tools for analyzing periodic orbits in hybrid dynamical systems, including legged locomotion and power electronics with switching behavior The resulting solution…

Key concepts

Poincare Return Map
This is a discrete-time map derived from analyzing the continuous evolution of a hybrid system by observing its state when it crosses a specific surface (the guard surface). It simplifies the complex hybrid dynamics into a manageable discrete system, allowing researchers to study periodic orbits as fixed points of this map.
Invariant Set
An invariant set is a region in the state space such that if the system starts within that region, it will always remain within it for all future time steps. The goal of the paper is to computationally find an ellipsoid that acts as such a set for hybrid systems.
Ellipsoidal Optimization
Instead of searching through every possible point, the method uses optimization to fit a minimum-volume ellipsoid around candidate points that satisfy one-step invariance. This iterative process refines the shape of the invariant set by minimizing its volume while ensuring it captures the system's behavior effectively.
PAC Bounds
Probably Approximately Correct (PAC) bounds are used to provide probabilistic guarantees on the algorithm's results. These bounds allow researchers to state with high confidence that their computed invariant set is close enough to the true set, based on a mathematical analysis of binomial tails.

Terminology

Summary

Poincare return maps are fundamental tools for analyzing periodic orbits in hybrid dynamical systems, including legged locomotion and power electronics with switching behavior The resulting solution is accompanied by probabilistic guarantees on finite-step invariance satisfying a user-defined accuracy threshold. p. 0

Methodology Overview

The proposed framework leverages sampling-based optimization to compute a finite-step invariant ellipsoid around a nominal periodic orbit using sampled evaluations of the return map. By sampling points from a candidate invariant set and enforcing invariance of the return map on these samples, the authors generate a dataset for which they can solve a tractable optimization problem. p. 0 The holdout method is then used to provide a risk estimate for the resulting prediction, based on an independent validation set. p. 0

System Modeling and Invariance Analysis

Hybrid dynamical systems are defined by continuous evolution and discrete events, often analyzed using Poincare sections where the guard surface S is chosen as a natural choice. The hybrid system induces a discrete-time dynamical system on the guard xk+1 = P(xk), xk ∈ S. p. 1 A periodic orbit corresponds to a fixed point of the Poincare map, x∗ = P(x∗). p. 1 Forward invariant sets are defined as a set I ⊂ S with respect to (9) such that x0 ∈ I ⇒ xk ∈ I, ∀k ∈ N. p. 1

Optimization and Guarantee Formulation

The goal is to find an ellipsoid E satisfying the invariance condition P(x) ∈ E for all x ∈ E. This is relaxed to fitting a minimum-volume ellipsoid to the set of points that satisfy one-step invariance at a given time step. p. 2 The algorithm iteratively refines the candidate invariant ellipsoid by filtering input-output samples and improving the set estimate through repeated solution of the ellipsoidal optimization problem. p. 2 Probabilistic guarantees are provided using Probably Approximately Correct (PAC) bounds derived from a binomial tail inversion. p. 2

Empirical Validation and Extensions

The approach is demonstrated on two low-dimensional systems and a compass-gait walking model. The results show that the algorithm consistently recovers an invariant set with one-step accuracy ϵ < 0. p. 403 for the Convex Expander-Contractor system. p. 4 Furthermore, extensions to more expressive set representations, such as radial basis functions (RBFs), can achieve tighter approximations for nonconvex invariant sets like the Nonconvex Expander-Contractor system. p. 6

Limitations and Future Scope

A limitation is the curse of dimensionality inherent to sampling-based approaches, requiring more samples in high-dimensional spaces. Furthermore, without structural assumptions on the system or the true invariant set, convergence of the identification algorithm is not guaranteed for any particular accuracy ϵ. p. 6 The choice of set representation involves a trade-off between accuracy and computational efficiency. p. 6

Conclusion

In this work, they present an algorithm that leverages sampling-based optimization to compute invariant sets of hybrid systems via their discrete Poincare dynamics. Their approach requires minimal structural assumptions on the dynamical system and provides probabilistic guarantees on violation of finite-step set invariance. p. 7 They demonstrate the effectiveness of this algorithm on three dynamical systems, including one where the true invariant set is not explicitly known. p. 7 These results establish a foundation for future work on probabilistic verification in robust, bipedal robot control. p. 7

Acknowledgments

This work is supported by the National Science Foundation (NSF) CPS Award and Elizabeth Dietrich was also supported by an NSF Graduate Research Fellowship.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Sampling-based optimization for computing finite-step invariant ellipsoids allows AI systems to robustly identify regions of state space where periodic behaviors are guaranteed to remain stable for a finite number of steps with probabilistic guarantees on violation probability.

  2. The system can utilize this framework to compute forward invariant sets under a Poincare return map, enabling robustness analysis for hybrid systems like legged locomotion or power electronics, which is often difficult when dynamics are only available through forward simulation.

  3. AI systems can achieve more accurate robustness estimates than those based on uniform balls around a nominal gait by fitting forward-invariant ellipsoids using sampled evaluations of the return map, yielding less conservative robustness estimates.

  4. The algorithm can be extended to handle nonconvex invariant sets by replacing the ellipsoid constraint with a set of radial basis functions, allowing for tighter approximations of complex geometries like those found in certain walking models.

  5. By employing the holdout method and binomial tail inversion, the framework provides Probably Approximately Correct PAC guarantees on finite-step invariance, ensuring that a learned invariant set has a high confidence level regarding its actual robustness against disturbances.

Sources

Related papers