Introduction
In the fields of control theory and robotics, ensuring the stability and safety of autonomous non-linear systems is a critical challenge. Proving these properties typically requires finding specific mathematical certificates: Lyapunov functions for asymptotic stability (ensuring a system settles at a desired state) and Barrier certificates for safety (guaranteeing a system never enters a dangerous state).
Historically, engineers have faced a trade-off between automation, flexibility, and formal soundness. Analytical methods require significant manual intuition, numerical methods lack formal guarantees for continuous domains, and symbolic methods often rely on rigid, user-provided templates. FOSSIL (Formal Synthesis of Lyapunov and Barrier Certificates) is a software tool designed to bridge this gap by providing a fully automated, flexible, and formally sound framework for certificate synthesis.
The FOSSIL Framework
The core of FOSSIL is an enhanced Counter-Example Guided Inductive Synthesis (CEGIS) loop. This architecture combines the expressive power of neural networks with the rigorous verification capabilities of Satisfiability Modulo Theories (SMT) solvers.
As shown in the architecture above, the process involves two primary agents:
- The Learner (Neural Network): Acts as a flexible template that trains on sampled data points from the system's state space to approximate a valid certificate.
- The Verifier (SMT Solver): Performs a symbolic check of the Learner's candidate function. Unlike point-wise numerical checks, the SMT solver mathematically proves whether the function holds across the entire continuous domain. If the candidate is invalid, the Verifier generates a counterexample.
Novel Intermediary Modules
Standard CEGIS loops often struggle with the interface between numerical neural networks and symbolic solvers. FOSSIL introduces two novel modules to optimize this communication:
The Translator
The Translator converts the numerical neural network into a symbolic mathematical expression. To ensure the SMT solver remains efficient, the Translator rounds the network's weight matrices and biases. This simplification prevents the solver from becoming bogged down by complex floating-point arithmetic while maintaining the functional integrity of the certificate.
The Consolidator
A single counterexample from an SMT solver is often insufficient for effectively retraining a neural network. The Consolidator addresses this by taking the Verifier's counterexample and using gradient-based exploration to find a "cloud" of related counterexamples. This augmentation provides the Learner with a richer dataset, significantly accelerating the retraining phase and improving the robustness of the synthesis process.
Conclusion
FOSSIL represents a significant step forward in neuro-symbolic control theory. By integrating neural network flexibility with SMT-based formal guarantees through the use of specialized Translator and Consolidator modules, the tool automates the discovery of complex stability and safety proofs for non-linear dynamical systems. This architecture leverages the strengths of both machine learning and formal methods to provide a robust solution for autonomous system verification.
Summary updated