Offline Reachability Precomputation for Real Time Safety Verification

25 concepts20 papers1 proposal

When deploying autonomous systems—whether they are self-driving cars navigating busy intersections or robotic arms operating alongside humans—safety cannot be left to trial-and-error simulation. We require formal mathematical guarantees that a system will never enter an unsafe state, even when subjected to external disturbances, sensor failures, or unpredictable human behavior.

The gold standard for providing these guarantees is reachability analysis, a framework that computes the set of all possible future states a system can reach under a range of control inputs and disturbances. If we can mathematically prove that this "reachable set" never intersects with an obstacle or an unsafe condition, the system is guaranteed to be safe.

However, reachability analysis faces a severe computational bottleneck. Calculating these sets in high-dimensional spaces requires solving complex partial differential equations (PDEs) or running intensive numerical optimizations. While a safety-critical system needs to react to unexpected obstacles in milliseconds, these mathematical calculations can take minutes or even hours to solve on the fly.

To bridge this gap, a powerful paradigm has emerged: offline-online safety synthesis. The core intuition is simple: shift the heavy mathematical burden to an offline design phase, leaving only lightweight geometric lookups or basic arithmetic for real-time execution.


The Core Mechanism: Offline-Online Decoupling

To understand why this approach works, consider how a standard safety filter operates. In an online-only framework, the controller evaluates a proposed action by simulating the system's future trajectory and checking for collisions in real time. If the environment changes or a disturbance occurs, the entire optimization problem must be re-solved.

Offline-online decoupling fundamentally changes this workflow. During the offline phase, researchers compute the system's boundaries under worst-case assumptions. The result of this computation is stored as a parameterized safety set, a value function, or a lookup table. When the system is actively operating online, it no longer needs to solve differential equations; it simply queries the precomputed structure to verify if a proposed action is safe.

[ Offline Design Phase ] 
Complex System Dynamics + Worst-Case Disturbances 
  │
  ▼ (Solve Heavy PDEs / Sums-of-Squares / Optimization)
[ Precomputed Safety Set / Lookup Table / Value Function ]
  │
  ▼ (Deploy to Hardware)
[ Online Execution Phase ]
Current State + High-Speed Lookup ──► Millisecond-Level Safety Intervention

This separation allows for dramatic performance gains. For example, Matthias Althoff demonstrated in early foundational work that abstracting complex vehicle dynamics during an offline phase reduces online execution to sparse matrix multiplications, enabling real-time verification during active operation [Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars].

By moving from online optimization to offline pre-computation, systems achieve orders-of-magnitude speedups. Antoine Leeman et al. showed that solving a linear program offline to define a simplified safe set (such as an infinity-norm ball) allows a predictive safety filter to execute extremely fast online checks, making it suitable for hardware with limited processing power [Predictive safety filter using system level synthesis].


Representing and Querying Safety Sets

A key challenge in this field is determining how to store high-dimensional continuous safety sets without exhausting onboard memory or introducing slow search latencies. Researchers utilize several distinct representations to achieve millisecond-level lookups:

1. Geometric Primitives and Tubes

Instead of storing raw state trajectories, systems can precompute geometric bounds that wrap around a trajectory like a protective sleeve. Jerome Sieber et al. utilized this by pre-computing "safety tubes" derived from system-level responses to disturbances, reducing online solve times to a few milliseconds [System Level Disturbance Reachable Sets and their Application to Tube-based MPC]. For robotic arms with complex joint configurations, Patrick D. Holmes et al. precomputed joint-level reachable sets using efficient geometric shapes called zonotopes, shifting the heavy volume estimation away from the online planner [Reachable Sets for Safe, Real-Time Manipulator Trajectory Design].

2. Value Functions and Lookup Tables

When dealing with stochastic or adversarial environments, safety is often framed as a game where the system tries to avoid an tracking failure. Forrest Laine et al. solved Hamilton-Jacobi partial differential equations offline to generate an "Eyes-Closed Safety Kernel." Online, when a sensor fails, the robot performs a high-speed table lookup and applies gradient-based control laws directly from the precomputed solution [Eyes-Closed Safety Kernels: Safety of Autonomous Systems Under Loss of Observability]. Similarly, Bingzhuo Zhong et al. pre-calculated risk-associated value functions for stochastic cyber-physical systems, reducing complex probabilistic safety checks to simple matrix lookups and basic arithmetic [Sandboxing Controllers for Stochastic Cyber-Physical Systems].

3. Trajectory Parameterization

Rather than checking every individual state, the online planner can select from a parameterized family of trajectories. Sean Vaskov et al. developed Reachability-based Trajectory Design (RTD), which precomputes Forward Reachable Sets that account for vehicle tracking errors. The online planner only needs to verify that the parameters of a candidate trajectory remain within the precomputed safe bounds [Guaranteed Safe Reachability-based Trajectory Design for a High-Fidelity Model of an Autonomous Passenger Vehicle]. The authors later expanded this approach using Sums-of-Squares programming to generate forward reachable sets that include guaranteed fail-safe maneuvers, bypassing the need to re-solve differential equations during operation [Towards Provably Not-at-Fault Control of Autonomous Robots in Arbitrary Dynamic Environments].


Overcoming Conservatism and Adapting to Change

The primary drawback of offline pre-computation is conservatism. If a safety set is computed offline to cover every possible scenario, it must assume the absolute worst-case conditions. This can result in an overly cautious robot that refuses to move because its precomputed safety buffer is too large.

To make these safety sets more practical, recent methodologies focus on making the precomputed data dynamic and context-aware:

  • Maneuver-Based Decomposition: Instead of computing one massive safety zone, researchers break the problem down by intent. Sever Topan et al. demonstrated that by incorporating the vehicle's intended maneuver (e.g., a lane change versus driving straight), the volume of the required obstacle perception safety zone could be shrunk by up to 76% without compromising safety [Refining Obstacle Perception Safety Zones via Maneuver-Based Decomposition].
  • Behavioral Clustering: Humans drive and walk in distinct patterns. Anjian Li et al. precomputed reachability tensors for specific human behavioral clusters (e.g., braking, turning). Online, the system classifies the surrounding drivers' behaviors and dynamically switches between these specialized, less-conservative safety tensors [Prediction-Based Reachability for Collision Avoidance in Autonomous Driving].
  • Symbolic Parameter Adaptation: What happens if the physical properties of the robot change online, such as a drone picking up a heavy package? Rui Chen et al. addressed this by pre-computing the gradients of safety-critical determinants symbolically offline. At runtime, the system simply evaluates these expressions with the current state and new physical parameters, adapting its safety logic in milliseconds without needing numerical optimization [Real-time Safety Index Adaptation for Parameter-varying Systems via Determinant Gradient Ascend].

Scaling to Multi-Agent Systems via Symmetries

When multiple autonomous agents operate in the same space, the computational complexity scales exponentially with the number of agents—a phenomenon known as the curse of dimensionality. Precomputing a joint safety set for a dozen interacting robots is computationally intractable.

To solve this, researchers exploit mathematical symmetries. If multiple robots share identical or similar underlying dynamics, they do not need unique safety sets. Instead, their states can be mapped to a standardized "virtual system."

Hussein Sibai et al. demonstrated that pre-computed reachable sets can be stored in a database and reused for multi-agent verification. When a new interaction occurs online, the system applies geometric transformations (like rotations and translations) to check if a transformed version of a cached set covers the current initial conditions, completely bypassing online numerical integration [Multi-agent Safety Verification Using Symmetry Transformations].

Building on this principle, Jiaoyang Li et al. leveraged symmetry transformations to pre-compute tracking errors offline. Because this data can be reused across different path orientations, the safety bounds for complex nonlinear multi-agent systems can be calculated in under a second, enabling scalable, real-time motion planning [Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances].


The Fundamental Trade-off

The success of offline safety set pre-computation rests on a fundamental engineering trade-off: shifting the bottleneck from time to space. By investing heavy computational effort during the design phase, we drastically reduce the online latency required to keep a system safe.

As noted by Antoine Leeman et al., this trade-off means that online execution speed increases by orders of magnitude, though it can result in a more conservative safe operating region [Predictive safety filter using system level synthesis]. However, by combining these precomputed sets with hierarchical architectures—such as the framework proposed by Hung Duy Nguyen et al. that pairs high-level path planning with an offline robust Model Predictive Control loop—modern autonomous systems can achieve a thousand-fold increase in processing speed while maintaining rigorous, provable safety boundaries [Hierarchical Motion Planning and Offline Robust Model Predictive Control for Autonomous Vehicles].

Key Foundational Work

Bridging the Gap Between Safety and Real-Time Performance in Receding-Horizon Trajectory Design for Mobile Robots (2018) — contributed 2 concept elements to this direction.
Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_offline_safety_set_pre_computation_46cbab34,
  title = {offline safety set pre-computation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/offline-safety-set-pre-computation/rdr_46cbab3418554bb5b192dcc276a4c59e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_offline_safety_set_pre_computation_46cbab34_v1,
  title = {offline safety set pre-computation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/offline-safety-set-pre-computation/rdr_46cbab3418554bb5b192dcc276a4c59e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake