Abstract
Ensuring the safety of autonomous systems in stochastic environments typically requires expensive formal verification. However, these guarantees are often invalidated by localized environmental changes, necessitating costly re-certification. We present VeRecycle, a framework that "recycles" existing probabilistic safety proofs by mathematically adjusting them in response to changes. VeRecycle achieves a three-order-of-magnitude speedup over traditional methods while maintaining competitive safety thresholds.
Introduction
Autonomous systems operating in real-world environments, such as warehouse robots or self-driving vehicles, must navigate stochastic dynamics while maintaining rigorous safety guarantees. Researchers often employ "probabilistic neural Lyapunov certificates" to prove that a system will reach a goal state while avoiding unsafe regions with a specific probability. Unfortunately, these formal proofs are brittle; a minor environmental change, such as a new obstacle or a change in surface friction, renders the original certificate invalid. Traditional re-certification is computationally intensive, often requiring hours of retraining and formal solving. VeRecycle addresses this gap by providing a lightweight method to update safety guarantees on the fly.
Methodology
VeRecycle leverages the mathematical properties of Lyapunov functions to adjust safety thresholds without re-running full verification.
Localized Analysis and the Infimum Link
The framework assumes that while the specific nature of a change might be unknown, its location within the state space ($\mathcal{X}_?$) is identified. The core theoretical insight is that the maximum reclaimable safety threshold is linked to the infimum (minimum value) of the existing Lyapunov certificate within the affected area. If the Lyapunov function maintains high values in the "corrupted" region, the system is statistically unlikely to enter that area, allowing much of the original safety guarantee to be preserved.
Sound Approximation and Compositional Re-routing
To ensure safety, VeRecycle uses Interval Bound Propagation (IBP) to find a sound lower bound on the certificate's value. For complex, multi-stage tasks, the framework employs a graph-based compositional approach. By updating safety scores for individual path segments (modules), VeRecycle can use shortest-path algorithms to identify the safest global route in the modified environment.
Experimental Evaluation
The framework was evaluated using the "Stochastic Nine Rooms" benchmark, where a robot navigates a 3x3 grid of rooms with slippery floors. The researchers introduced seven types of localized changes across 63 unique reach-avoid specifications to test the robustness and efficiency of the recycling process.
Results
VeRecycle demonstrates significant improvements in computational efficiency. As shown in the results table, the framework computes new safety thresholds in approximately 0.33 seconds, compared to over 918 seconds for baseline re-certification—a speedup exceeding 2,700x.
Crucially, this speed does not come at the cost of safety. The reclaimed probability thresholds remain highly competitive with, and often identical to, those produced by exhaustive verification methods. In practical scenarios, VeRecycle successfully re-routes systems away from degraded paths to maintain high overall success probabilities.
Conclusion
VeRecycle represents a significant step toward resilient autonomous systems. By shifting the paradigm from "re-verify" to "re-calculate," it enables real-time adaptation to environmental changes. Future work will focus on extending the framework to continuous-time systems and integrating targeted re-learning loops to further refine conservative bounds.
Summary updated