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.