When deploying autonomous systems like self-driving cars, drones, or robotic arms into the real world, we require mathematical guarantees that they will operate safely. Traditionally, this assurance is provided via formal verification methods like reachability analysis—calculating every possible future state a system might reach under worst-case environmental disturbances.
However, as highlighted by Vaskov et al. in Towards Provably Not-at-Fault Control of Autonomous Robots in Arbitrary Dynamic Environments and Holmes et al. in Reachable Sets for Safe, Real-Time Manipulator Trajectory Design, these exact mathematical calculations are notoriously slow. They suffer from high computational complexity and scale poorly with system dimensions, introducing processing latencies that fail to meet the millisecond-level requirements of real-time control loops.
To bridge this gap, a major research direction focuses on real-time safety verification: techniques designed to maintain rigorous safety guarantees while drastically reducing runtime latency. Rather than attempting to solve exhaustive, computationally intensive verification problems from scratch at every time step, these approaches rely on three core insights: decoupling safety from performance via shielding, simplifying the underlying mathematical representations, and amortizing the computational burden using offline learning.
Decoupling Safety via Shielding and Simplex Architectures
Why try to verify a highly complex, unverified controller—such as a deep neural network or reinforcement learning policy—directly at runtime? Instead, we can let the complex controller run freely, but wrap it in a lightweight, formally verified "safety filter" or "shield".
[Unverified Controller] ---> (Proposed Action)
|
v
[Safety Shield] <--- (Monitors Environment)
|
+-----------------------+-----------------------+
| Safe | Unsafe
v v
(Execute Action) (Override with Verified
Backup Policy)
As surveyed by Könighofer et al. in Correct-by-Construction Runtime Enforcement in AI - A Survey, a runtime shield continuously monitors the system state. It projects a short horizon into the future using a simplified system model. If the unverified policy proposes an action that would push the system into an irrecoverable state, the shield intercepts and overrides it with a pre-verified, fail-safe backup policy.
This mechanism forms the core of the Simplex architecture reviewed by Chen et al. in Runtime safety assurance methods for cyber physical systems based on simplex architecture. By separating the high-performance goal from the safety constraint, the system only incurs the cost of active intervention when failure is imminent. For example, Yang et al. demonstrate this in Case Study: Runtime Safety Verification of Neural Network Controlled System by integrating a high-performance reachability tool with a safety-switch logic, allowing a physical robot to pivot to a backup controller immediately before a collision occurs.
Mathematical Relaxations and Geometric Simplifications
Exact reachability analysis often involves solving complex non-linear differential equations or high-degree polynomial optimization problems online. We can trade a small amount of precision for massive speedups by relaxing these mathematical constraints into more tractable geometric or algebraic forms.
Instead of computing exact, complex kinematic boundaries for a moving human arm, Pereira et al. demonstrate in A cartesian-space method for calculating human reachable occupancy that using simple geometric bounds derived from physical limits (like maximum velocity and acceleration) yields a 2x speedup. This structural simplification enables fluid, real-time human-robot collaboration without the overhead of tracking skeletal kinematics.
On the optimization side, traditional Sum-of-Squares (SOS) polynomials provide exact safety certificates but are too slow for mid-flight replanning. To solve this, Ahmadi et al. in Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making introduce Scaled Diagonally Dominant Sum of Squares (SDSOS). This framework relaxes complex polynomial constraints into highly tractable Second Order Cone Programs (SOCPs), allowing unmanned aerial vehicles (UAVs) to generate formal safety certificates within millisecond timeframes.
Amortizing Computation through Learning-Based Approximations
A powerful way to achieve real-time execution is to shift the heavy computational lifting offline. By pre-computing safety boundaries or training a machine learning model to recognize safe states, runtime verification reduces to a fast neural network forward pass.
In the Neural Predictive Monitoring framework explored by Cairoli et al. in Learning-Based Approaches to Predictive Monitoring with Conformal Statistical Guarantees, deep learning models are trained to predict future safety violations while maintaining rigorous statistical or conformal guarantees. Similarly, Cleaveland et al. demonstrate in Learning Enabled Fast Planning and Control in Dynamic Environments with Intermittent Information that a neural network can be trained to approximate computationally expensive reachability analysis and potential fields, dropping control loop latency to just 27 milliseconds.
OFFLINE PHASE:
[Expensive Formal Solvers] ---> [Generate Safe Reach Sets] ---> [Train Neural Network]
ONLINE PHASE:
[Current State] ---> [Trained Neural Network] ---> [Instant Safety Prediction (ms)]
Furthermore, the authors of Safe Reach Set Computation via Neural Barrier Certificates introduce a meta-neural network framework to predict barrier certificates—formal proofs of safety—in real time. By shifting the iterative optimization process entirely offline, the system generates sound reach-set approximations in milliseconds, bypassing the timeouts that plague traditional online solvers.
Statistical and Probabilistic Risk Assessment
When worst-case deterministic verification is too conservative or slow, researchers leverage statistical properties to evaluate risk rapidly. Traditional sampling methods, such as Monte Carlo simulations, require thousands of iterations to verify state safety, creating a severe latency bottleneck in high-speed driving environments.
To circumvent this, Wang et al. show in Fast Risk Assessment for Autonomous Vehicles Using Learned Models of Agent Futures that by utilizing statistical moments and polynomial algebra, an autonomous vehicle can analytically calculate collision risk against deep learning predictions, bypassing sampling entirely.
For reinforcement learning agents, Bastani et al. introduce Statistical Model Predictive Shielding (SMPS) in Safe Reinforcement Learning via Statistical Model Predictive Shielding. SMPS uses highly efficient statistical sampling instead of exhaustive formal verification to ensure a robot never enters an irrecoverable state, accelerating the safety evaluation process up to 100x and allowing robust safety filters to operate within high-frequency control loops.
Key Foundational Work
Dynamic Verification of Trust in Distributed Open Systems (2007) — contributed 1 concept elements to this direction.
Planning with Loops (2005) — contributed 1 concept elements to this direction.