Safety Verification via Symbolic Reachability Analysis

35 concepts34 papers1 proposal

In complex systems—ranging from multi-agent robot swarms to concurrent software protocols—the central challenge is ensuring that the system never enters a "bad" state. Traditional testing and simulation can demonstrate that a system works in specific scenarios, but they cannot prove it will always be safe. To achieve absolute guarantees, researchers use reachability analysis: a formal method that mathematically maps every possible state a system can reach to ensure none of them intersect with danger.

The Geometry of Safety

For systems with continuous movement, like a legged robot or a self-driving car, the number of possible states is infinite. We cannot simulate every possible trajectory. Instead, as described by Althoff et al. in the ARCH-COMP20 report, reachability analysis computes a flowpipe.

Think of a flowpipe as a geometric "envelope" or tube that wraps around all possible paths the system might take over time. If this tube never touches a forbidden region (an "unsafe set"), the system is provably safe. To make this computationally feasible, Kochdumper et al. utilize polynomial zonotopes—efficient mathematical shapes—to track how initial uncertainties propagate through the system, allowing for massive speedups in safety checks.

Reasoning Backward from Failure

While forward reachability projects where a system will go, backward reachability works like a forensic investigation. It starts at the "crime scene"—the set of all unsafe states—and works backward to find every state that could eventually lead there.

As Felli et al. and Calvanese et al. demonstrate, this is often done symbolically. Instead of checking individual points, the authors use logic formulas (often powered by SMT solvers) to represent sets of states. By iteratively computing "preimages"—the set of states that can transition into the current set—the algorithm discovers the entire region of the state space that is "doomed" to reach a violation. If the system's starting configuration is not in this doomed region, the system is verified as safe.

Safety Shields and Filters

In modern AI, we often want to use Reinforcement Learning (RL) to find optimal behaviors, but RL agents learn through trial and error, which is inherently dangerous. To solve this, researchers like Fisac et al. and Könighofer et al. propose a "shielded" or "filtered" approach.

The intuition is to separate the performance of the agent from the safety of the system:

  1. Offline: Reachability analysis identifies the "safe" operating zone where a recovery action is always guaranteed to exist.
  2. Online: A "shield" monitors the agent's proposed actions. If the agent tries to take a step that would move the system into a state from which a crash is inevitable, the shield intervenes and substitutes a safe, pre-verified action.

Zhu et al. take this further by using symbolic regression to learn the environment's physics as mathematical formulas, allowing the shield to perform formal reachability analysis on the fly, even in unknown environments.

Scaling to Infinite Agents

A recurring problem in distributed systems is parameterized verification: proving a protocol is safe whether there are two agents or two million. Abdulla et al. addressed this by using symbolic backward reachability with constraints that represent an unbounded number of processes.

To avoid the "state explosion" that happens as more agents are added, Kaiser et al. developed dynamic cutoff detection. They show that for many systems, if you can prove safety for a small, specific number of agents (the "cutoff"), that proof automatically generalizes to any number of agents. This allows us to verify massive multi-agent systems by only analyzing a tiny, representative version of them.

Key Foundational Work

Model Checking via Reachability Testing for Timed Automata (1997) — contributed 1 concept elements to this direction.
Communication and Interaction in Multi-Agent Planning (1983) — 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_symbolic_backward_reachability_7bf34cd0,
  title = {symbolic backward reachability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/symbolic-backward-reachability/rdr_7bf34cd0b83a4d6096c80cce4a59f9a8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_symbolic_backward_reachability_7bf34cd0_v1,
  title = {symbolic backward reachability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/symbolic-backward-reachability/rdr_7bf34cd0b83a4d6096c80cce4a59f9a8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake