To guarantee that an autonomous system—whether a self-driving car, a quadcopter, or a robotic arm—will operate safely, we must understand every state it could possibly reach. This is the core objective of reachability analysis: computing the boundaries of a system's behavior over time under worst-case disturbances and all possible control inputs.
If we can compute this "reachable set," we can construct an impenetrable safety filter. If the system attempts a maneuver that would push it outside of this safe boundary, the filter intervenes.
Historically, computing these boundaries has been bottlenecked by a fundamental mathematical barrier: the curse of dimensionality. However, a powerful paradigm shift has emerged, leveraging neural networks to bypass traditional computational limits and scale safety verification to high-dimensional systems.
The Curse of the Grid
To find a system's reachable set, researchers typically solve the Hamilton-Jacobi (HJ) partial differential equation (PDE). The solution to this equation yields a value function across the system's state space. The boundary where this value function flips from positive to negative defines the exact edge of the safe operating envelope.
Traditionally, solving this PDE requires discretizing the state space into a rigid grid. If you want to analyze a simple system with 3 dimensions (such as a robot's $x$ position, $y$ position, and heading $\theta$) using a modest grid of 100 points per dimension, you must evaluate $100^3 = 1,000,000$ points.
Grid-Based (Exponential Growth):
3D Space: 100 × 100 × 100 = 1,000,000 points (Manageable)
6D Space: 100^6 = 1,000,000,000,000 points (Intractable)
As systems grow more realistic, their dimensionality explodes. A quadcopter requires at least 6 to 13 dimensions to model its position, velocity, and orientation. An F-16 jet might require 16 dimensions. Slicing a 13-dimensional space into a grid requires $100^{13}$ points—an astronomical number that completely exhausts both computational time and computer memory. Consequently, traditional grid-based HJ reachability analysis has been strictly limited to systems with fewer than about 5 or 6 dimensions.
Bypassing Grids with Neural PDE Solvers
To break this curse, researchers changed how the value function is represented. Instead of storing the value function discretely at every intersection of a massive grid, what if we treat the value function as a continuous landscape parameterized by a neural network?
Neural networks are universal function approximators. Crucially, they scale remarkably well to high-dimensional inputs because they learn to exploit the underlying structure and regularities of the function, rather than treating every region of space as independent.
Traditional Grid: [Point] -> [Value] (Requires storing every point)
Neural Solver: [State Vector] -> Neural Network -> [Value] (Continuous landscape)
In this framework, known as a Neural PDE Solver, the neural network takes a high-dimensional state vector as an input and outputs the safety value. The network is trained by minimizing a loss function derived directly from the HJ PDE itself, forcing the network to satisfy the physics of the system's dynamics.
As demonstrated by Javier Borquez et al. in Parameter-Conditioned Reachable Sets for Updating Safety Assurances Online, using neural networks with sinusoidal activation functions allows these solvers to capture the sharp, complex boundaries of reachable sets in high dimensions without exponential memory scaling. By treating changing environmental parameters as "virtual states," their model computes safety assurances across 12 dimensions simultaneously.
Similarly, Hyun Joe Jeong et al. utilize the "DeepReach" neural PDE framework in Parameterized fast and safe tracking (FaSTrack) using DeepReach to scale safety-critical tracking analysis to a 13-dimensional quadcopter model, a task completely inaccessible to grid-based alternatives.
Learning Safety Certificates Directly
A closely related approach bypasses the HJ PDE entirely by training neural networks to act as Control Barrier Functions (CBFs). A CBF is a mathematical certificate: if a controller can prove that the system state remains within a region where the barrier function is positive, the system is guaranteed to never enter an unsafe state.
Finding these barrier functions analytically for highly nonlinear systems is notoriously difficult. However, by framing the search as a machine learning problem, optimization algorithms can search the space of neural network weights to find a valid safety envelope.
- Simin Liu et al. show in Safe Control Under Input Limits with Neural Control Barrier Functions that Neural CBFs can successfully manage a 10-dimensional quadcopter-pendulum system, even when the system's actuators hit physical saturation limits.
- To stabilize training for even larger systems, Oswin So et al. introduce Policy Neural Control Barrier Functions in How to Train Your Neural Control Barrier Function: Learning Safety Filters for Complex Input-Constrained Systems. By reframing the safety problem as a policy evaluation task, they successfully generate safety filters for a 16-dimensional F-16 aircraft model.
Bridging the Gap: Restoring Formal Guarantees
While neural networks successfully break the curse of dimensionality, they introduce a new problem: approximation error. A neural network might be $99\%$ accurate, but in safety verification, that remaining $1\%$ could mean a catastrophic collision. Because neural networks are black boxes, they lack the strict, ironclad guarantees of traditional grid-based mathematics.
To fix this, the research community has developed verification wrappers that calculate a statistical or optimization-based safety buffer.
[Learned Optimistic Boundary] + [Statistical Safety Buffer] = [Provably Safe Boundary]
Instead of blindly trusting the neural network's output, researchers treat the learned boundary as an initial guess. Albert Lin 0003 et al. demonstrate in Generating Formal Safety Assurances for High-Dimensional Reachability that by using scenario-based optimization, one can sample the system's trajectories to calculate a rigorous probabilistic error bound on the neural network's predictions. This error bound is then used to "shrink" the permitted safe set, pruning away any overly optimistic regions.
In subsequent work, Albert Lin 0003 et al. establish a mathematical bridge between scenario optimization and conformal prediction in Verification of neural reachable tubes via scenario optimization and conformal prediction. This framework provides an "outlier-adjusted" safety buffer that recovers significantly more usable operating space for the robot while maintaining strict, provable bounds on the probability of failure.
Geometric Alternatives: Set-Based Scaling
It is worth noting that neural networks are not the only way to scale reachability analysis. A parallel, non-learning approach achieves scalability by restricting the geometry of the reachable sets themselves.
Instead of tracking individual points on a grid or learning a continuous landscape, these methods propagate entire geometric shapes—most notably zonotopes (centrally symmetric polytopes)—through time.
As Matthias Althoff demonstrates in Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars, if the system's dynamics can be bounded linearly, computing how a zonotope stretches and deforms over time is incredibly efficient. This geometric abstraction allows for the formal verification of systems with over 100 continuous state variables in just a few seconds. For strictly linear continuous systems, the ARCH-COMP24 Category Report notes that these discrete-time set-based methods can scale to verify state spaces exceeding 100,000 dimensions.
However, for highly nonlinear, non-convex systems where geometric shapes become too conservative or complex to track, neural approximations remain the leading frontier for practical, high-dimensional safety verification.
Key Foundational Work
Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars (2010) — contributed 1 concept elements to this direction.
Verification of Uncertain Embedded Systems by Computing Reachable Sets based on Zonotopes (2008) — contributed 1 concept elements to this direction.