State-Augmented Linear Games with Antagonistic Error for High-Dimensional, Nonlinear Hamilton-Jacobi Reachability

Will Sharpless, Yat Tin Chow, Sylvia L. Herbert

Introduction

Hamilton-Jacobi Reachability (HJR) analysis is the gold standard for formal safety verification in robotics and autonomous systems. It provides a rigorous mathematical framework to identify "safe" states—those from which a system can avoid failure despite worst-case disturbances—and "reachable" states—those from which a system can successfully reach a goal.

Despite its theoretical strengths, HJR traditionally relies on Dynamic Programming (DP) to solve the underlying partial differential equations. This approach suffers from the "curse of dimensionality," where the computational cost grows exponentially with the number of state variables. Consequently, DP-based HJR is typically limited to systems with fewer than six dimensions. While the generalized Hopf formula offers a way to solve linear systems in thousands of dimensions, it cannot be directly applied to the nonlinear dynamics characteristic of the real world. This paper proposes a framework to bridge this gap by "lifting" nonlinear systems into a higher-dimensional linear space while maintaining formal safety guarantees.

Methodology

The authors introduce a three-step framework designed to transform a nonlinear reachability problem into a computationally efficient linear game:

1. State Augmentation (Lifting)

Drawing inspiration from Koopman operator theory, the method maps the nonlinear system into a higher-dimensional "State-Augmented" (SA) space. By applying lifting functions—such as polynomials or Radial Basis Functions (RBFs)—the nonlinear dynamics are approximated as a linear system. This allows the system to be analyzed through a linear lens without losing the essential characteristics of its behavior.

2. Antagonistic Error Modeling

Because no linearization is perfect, the authors explicitly calculate the maximum error between the true nonlinear dynamics and the linear SA model. This error is treated as an "antagonistic player" in a differential game. By modeling the linearization error as a smart, malicious disturbance that actively tries to push the system toward failure, the authors ensure that any resulting safety policy is robust against the inaccuracies of the model.

3. Hopf Formula Solver

With the system now represented as a linear game (including the adversarial error player), the authors utilize the generalized Hopf formula. Unlike DP, which requires gridding the entire state space, the Hopf formula solves for specific points independently and in parallel. This enables the framework to scale to high-dimensional systems that were previously impossible to verify.

Theoretical Insights: Conservative Envelopes

A core contribution of this research is the proof that solving the linear game with antagonistic error produces a conservative envelope of the true reachable set. Theorem 2 in the paper demonstrates that if a controller succeeds in this "harder" linear game, it is mathematically guaranteed to succeed in the original nonlinear system.

Furthermore, this lifting technique allows the method to represent complex, non-convex safety sets. While linear HJR is usually restricted to convex sets, solving a convex problem in the higher-dimensional lifted space and then projecting it back down to the original state space allows for the capture of intricate, non-convex boundaries.

Experimental Validation

The framework was tested on several benchmark dynamical systems to validate its accuracy and scalability:

  • Slow Manifold System: A classic nonlinear system used to show how state-augmented dynamics can capture autonomous behavior and provide tight safety envelopes.
  • Controlled Van der Pol Oscillator: This testbed evaluated the impact of different lifting functions, including 3rd and 4th-degree polynomials and RBFs with 7–11 centers.
  • Baselines: The proposed SA-HJR method was compared against traditional DP-based HJR (the ground truth) and standard linearizations like Taylor Series and Dynamic Mode Decomposition (DMD).

The results indicated that SA-HJR successfully contained the true reachable sets calculated by DP. Moreover, it provided significantly tighter (less overly cautious) safety sets compared to standard Taylor Series or DMD linearizations, which often produced sets that were either unsafe or too large to be useful.

Conclusion and Future Work

This research demonstrates a viable path for performing formal safety analysis on high-dimensional nonlinear systems. By combining state augmentation with antagonistic error modeling, the authors leverage the scalability of the Hopf formula—known to handle up to 4,096 dimensions—without sacrificing safety guarantees.

However, the method's performance is currently tied to the quality of the linearization; if the error is high in a specific region, the safety set becomes overly conservative. Future work will focus on automating the selection of lifting functions, potentially using neural networks, and exploring probabilistic error bounds to further refine the accuracy of the safety envelopes.

Summary updated

BibTeX
@inproceedings{sharpless2024state,
  author = {Will Sharpless and Yat Tin Chow and Sylvia L. Herbert},
  title = {{State-Augmented Linear Games with Antagonistic Error for High-Dimensional, Nonlinear Hamilton-Jacobi Reachability}},
  booktitle = {CDC},
  year = {2024},
  url = {https://openreview.net/forum?id=H7ELX060Rf},
}
Figure