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.
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.
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