Poincare return maps are a fundamental tool for analyzing periodic orbits in hybrid dynamical systems, including legged locomotion, power electronics, and other cyber-physical systems with switching behavior. The Poincare return map captures the evolution of the hybrid system on a guard surface, reducing the stability analysis of a periodic orbit to that of a discrete-time system. While linearization provides local stability information, assessing robustness to disturbances requires identifying invariant sets of the state space under the return dynamics. However, computing such invariant sets is computationally difficult, especially when system dynamics are only available through forward simulation. In this work, we propose an algorithmic framework leveraging sampling-based optimization to compute a finite-step invariant ellipsoid around a nominal periodic orbit using sampled evaluations of the return map. The resulting solution is accompanied by probabilistic guarantees on finite-step invariance satisfying a user-defined accuracy threshold. We demonstrate the approach on two low-dimensional systems and a compass-gait walking model.
Figures & tables
Fig. 1 : One iteration of the proposed algorithm. (a) N points are sampled from Ei . (b) The Poincaré map P partitions return points into those that leave the set ( V⊂Ei ) and those that return ( W⊂Ei ). (c) The preimages are respectively partitioned into U and Z . (d) Ei+1 is fit to U . The algorithm repeats until the PAC bound satisfies a user-defined ϵ .
Fig. 2 : Sampling-based, finite-step invariant set algorithm and verification. (a,b) Sequence of ellipsoid iterates E0,E1,…,E∗ produced by the algorithm for the Convex Expander-Contractor and Compass-Gait Walker (three coordinate projections), respectively. (c,d) Verification of the final set E∗ : samples U (preimages whose Poincaré returns remain in E∗ ) and Z (preimages that escape), together with their return images W⊂E∗ and V⊂E∗ . Since the user-specified accuracy for both algorithms was ϵ=0.03 , it is not required that all points return to E∗ .
Fig. 3 : Mean and standard deviation of accuracy 1−ϵ and ellipsoid volume Vol(θ) over 10 algorithm runs. The dashed gray line indicates the user-defined target accuracy for each system. (Left): The Convex Expander-Contractor system (accuracy: dark orange, volume: light orange) with desired accuracy 97% , converges within 5 iterations on average. (Middle): The Nonconvex Expander-Contractor system (accuracy: dark purple, volume: light purple) with desired accuracy 93% , converges within 150 iterations on average. (Right): The Compass-Gait walker system (accuracy: dark pink, volume: light pink) with desired accuracy 97% , converges within 75 iterations on average.
Fig. 4 : Evaluation of extension of one-step probabilistic guarantees to k -step invariance. ϵ is evaluated over trajectories propagated for k steps: stable probabilities suggest the one-step guarantee of Alg. 1 is robust.
Fig. 5 : Invariant sets of Nonconvex Expander-Contractor (NEC) system. The true invariant set (light purple), consisting of two circles, is closely approximated by the RBF representation (orange). The ellipsoid (dark purple) from Alg. 1 results in an under-approximation with lower accuracy.
Fig. 6 : Coordinates and parameters of the Compass-Gait Walker.
For hybrid systems exhibiting periodic behavior, analyzing the invariant set containing the limit cycle is a natural way to study the robustness of the closed-loop system. However, computing these sets can be computationally expensive, especially when applied to contact-rich cyber-physical systems such as legged robots. In this work, we extend existing methods for overapproximating reachable sets of continuous systems using parametric embeddings to compute a forward-invariant set around the nominal trajectory of a simplified model of a bipedal robot. Our three-step approach (i) computes an overapproximating reachable set around the nominal continuous flow, (ii) catalogs intersections with the guard surface, and (iii) passes these intersections through the reset map. If the overapproximated reachable set after one step is a strict subset of the initial set, we formally verify a forward invariant set for this hybrid periodic orbit. We verify this condition on the bipedal walker model numerically using immrax, a JAX-based library for parametric reachable set computation, and use it within a bi-level optimization framework to design a tracking controller that maximizes the size of the invariant set.
Varun Madabushi, Akash Harapanahalli, Samuel Coogan +1
School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA, 30332, USA.
Reduced-order models are powerful for analyzing and controlling high-dimensional dynamical systems. Yet constructing these models for complex hybrid systems such as legged robots remains challenging. Classical approaches rely on hand-designed template models (e.g., LIP, SLIP), which, though insightful, only approximate the underlying dynamics. In contrast, data-driven methods can extract more accurate low-dimensional representations, but it remains unclear when stability and safety properties observed in the latent space meaningfully transfer back to the full-order system. To bridge this gap, we introduce HALO (Hybrid Auto-encoded Locomotion), a framework for learning latent reduced-order models of periodic hybrid dynamics directly from trajectory data. HALO employs an autoencoder to identify a low-dimensional latent state together with a learned latent Poincaré map that captures step-to-step locomotion dynamics. This enables Lyapunov analysis and the construction of an associated region of attraction in the latent space, both of which can be lifted back to the full-order state space through the decoder. Experiments on a simulated hopping robot and full-body humanoid locomotion demonstrate that HALO yields low-dimensional models that retain meaningful stability structure and predict full-order region-of-attraction boundaries.
Blake Werner, Sergio A. Esteban, Massimiliano De Sa +2
Caltech, Pasadena, CA, USA · NC State University, Raleigh, NC, USA
Safety-critical control of autonomous systems requires formal safety certificates, such as controlled invariant sets, that must be computed online as conditions change. Although standard synthesis algorithms scale poorly with state dimension, monotone dynamical systems with lower-closed safety specifications allow for accelerated computation of controlled invariant sets. In particular, lazy fixed-point algorithms exploit monotonicity and track only the antichain basis of the set. However, membership tests and redundancy checks against an evolving basis remain major bottlenecks. We introduce a threshold-function reformulation in which a lower-closed set on a d-dimensional grid is represented by its column heights along a designated axis. This reformulates the greatest-fixed-point iteration as independent one-dimensional binary searches, one per grid column, yielding an embarrassingly parallel iteration with asymptotically lower computational complexity than the lazy fixed-point algorithm. Experiments synthesize invariant sets on 3D grids with 10^9 cells in under 50 ms and 10^14 cells in under two minutes. We further demonstrate online re-synthesis in a safety-informed model predictive controller example.
Yasin Sonmez, Mahmoud Khaled, Majid Zamani +1
University of California, Berkeley, USA · Ludwig-Maximilian University, Germany · University of Colorado Boulder, USA