Safe Reach Set Computation via Neural Barrier Certificates

Alessandro Abate, Sergiy Bogomolov, Alec Edwards, Kostiantyn Potomkin, Sadegh Soudjani, Paolo Zuliani

Abstract

Ensuring the safety of autonomous systems requires rigorous reachability analysis, which is often computationally prohibitive for real-time applications. This paper presents a novel framework that leverages neural networks to predict barrier certificates—formal proofs of safety—in milliseconds. By shifting the heavy computational burden to an offline training phase, the proposed "MetaNN" approach generates candidate certificates that are subsequently verified by an SMT solver. Experimental results on nonlinear vehicle dynamics demonstrate a 99% success rate in finding valid safety proofs, significantly outperforming traditional synthesis tools in both speed and reliability.

Introduction

Autonomous systems, such as self-driving cars and drones, must operate within strict safety bounds. Reachability analysis—the process of determining all possible future states of a system—is the gold standard for safety verification. However, for nonlinear systems, this analysis is often undecidable or computationally expensive. Barrier Certificates (BCs) offer an elegant alternative by defining a "fence" in the state space that the system is proven never to cross. While powerful, synthesizing these certificates typically involves slow, iterative optimization, making them unsuitable for real-time decision-making.

The MetaNN Framework

The authors propose a two-phase architecture designed to bring formal safety guarantees to real-time deployment.

Offline Training and Online Deployment

The process begins with an offline phase where a formal synthesis tool, FOSSIL, generates a large dataset of valid barrier certificates for various initial conditions. A Meta-Neural Network (MetaNN) is then trained to learn the mapping between the system's initial state and the coefficients of a valid barrier certificate.

During online operation, the MetaNN functions as a high-speed generator. Given the current state, it instantly predicts a candidate barrier certificate. To ensure absolute safety, this candidate is passed to a Satisfiability Modulo Theories (SMT) solver for formal verification. This "safety sandwich" combines the speed of deep learning with the rigor of symbolic logic.

The MetaNN framework: Offline training uses FOSSIL to generate data for the MetaNN, which then provides real-time candidate certificates for formal verification during deployment.

Reach Set Computation via Working Regions

To handle unbounded state spaces, the framework employs a simulation-based approach to define a "working region." The process involves simulating trajectories, computing an octagonal bound, and then bloating that bound to define the area where the barrier certificate must hold. This allows the system to compute sound over-approximations of the reachable set efficiently, providing a safe operating envelope for the controller.

The reach set computation process: trajectories are bounded and bloated to define a working region for the barrier certificate.

Experimental Evaluation

The framework was tested on several dynamical systems, including complex nonlinear vehicle dynamics. For the car model, the MetaNN was trained on over 5,000 valid barrier certificates.

Key Results

  • Reliability: In autonomous driving scenarios, the MetaNN increased the success rate of finding a valid safety certificate within a 2-second window from 78% (using FOSSIL directly) to 99%.
  • Performance: While traditional solvers often exhibit high variance and timeouts, the MetaNN-based approach provided verified candidates in a constant time of less than 0.7 seconds.
  • Real-time Obstacle Avoidance: The system successfully navigated a car model through obstacles by iteratively generating safe reach sets every 2 seconds of simulated time.

Conclusion

By predicting the parameters of a formal proof rather than the system state itself, the MetaNN framework provides a robust path toward real-time formal verification. This approach achieves the best of both worlds: the sub-second response times required for robotics and the absolute safety guarantees required for critical infrastructure.

Summary updated

Abstract

We present a novel technique for online safety verification of autonomous systems, which performs reachability analysis efficiently for both bounded and unbounded horizons by employing neural barrier certificates. Our approach uses barrier certificates given by parameterized neural networks that depend on a given initial set, unsafe sets, and time horizon. Such networks are trained efficiently offline using system simulations sampled from regions of the state space. We then employ a meta-neural network to generalize the barrier certificates to state space regions that are outside the training set. These certificates are generated and validated online as sound over-approximations of the reachable states, thus either ensuring system safety or activating appropriate alternative actions in unsafe scenarios. We demonstrate our technique on case studies from linear models to nonlinear control-dependent models for online autonomous driving scenarios.
BibTeX
@inproceedings{abate2024safe,
  author = {Alessandro Abate and Sergiy Bogomolov and Alec Edwards and Kostiantyn Potomkin and Sadegh Soudjani and Paolo Zuliani},
  title = {{Safe Reach Set Computation via Neural Barrier Certificates}},
  booktitle = {ADHS},
  year = {2024},
  doi = {10.1016/j.ifacol.2024.07.433},
}
Figure