Scalable Safety Verification via Zonotopic Reachability Analysis

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2103 papers133 conceptsfrozen 2026-10-04

To guarantee that an autonomous car will never collide or a robot arm will never strike a human, engineers cannot rely on simulations alone. Simulation only tests a finite number of scenarios, leaving the "long tail" of edge cases untouched. Instead, researchers use reachability analysis: a formal method that calculates the set of all possible states a system can reach over time, accounting for every possible disturbance and sensor error.

The central challenge of reachability analysis is the "state-space explosion." Representing these sets of possible states accurately in high-dimensional space is often computationally impossible. A breakthrough in this field, pioneered largely by Matthias Althoff and colleagues, involves using a specific geometric primitive called the zonotope.

The Geometry of Efficiency

A zonotope is a centrally symmetric polytope. Intuitively, you can think of it as the Minkowski sum of several line segments (called generators) in $n$-dimensional space.

In formal verification, we must perform two primary operations repeatedly:

  1. Linear Transformations: Moving the set according to the system's physics (e.g., $x_{t+1} = Ax_t$).
  2. Minkowski Sums: Adding sets together to account for uncertain inputs or noise (e.g., $x + \text{noise}$).

As Matthias Althoff demonstrated in Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars, zonotopes are uniquely suited for this. While general polytopes suffer from exponential complexity growth during these operations, zonotopes handle them with simple matrix multiplications and generator concatenations. This efficiency allows tools like CORA to verify systems with hundreds or even thousands of dimensions, such as the International Space Station model discussed in the ARCH-COMP18 Category Report.

Taming Nonlinearity with Conservative Linearization

Most real-world systems, like a car's tires or a drone's aerodynamics, are nonlinear. Directly calculating reachable sets for nonlinear equations is usually intractable. The standard workaround is conservative linearization.

In this approach, the nonlinear system is approximated by a linear model at each time step. Crucially, the difference between the true nonlinear behavior and the linear approximation is captured as a "linearization error." This error is treated as an additional bounded uncertain input. By adding this error term (represented as a small zonotope) back into the reachable set, researchers like Luca Geretti and Julien Alexandre Dit Sandretto ensure that the resulting set is a guaranteed over-approximation of the true system behavior, as detailed in the ARCH-COMP24 Category Report.

Beyond Simple Shapes: Polynomial and Constrained Zonotopes

While standard zonotopes are efficient, they have limitations: they are always centrally symmetric and convex. To handle more complex, non-convex behaviors, the field has evolved toward more sophisticated structures:

  • Polynomial Zonotopes: Introduced by Niklas Kochdumper and Matthias Althoff in Representation of Polytopes as Polynomial Zonotopes, these use polynomial combinations of generators. This allows them to represent non-convex sets and capture the "curving" effect of nonlinear dynamics more tightly than linear boxes.
  • Constrained Zonotopes: Standard zonotopes struggle with set intersections (e.g., "where does the car's reachable set intersect with the obstacle?"). Mark Wetzlinger and others have utilized constrained zonotopes, which add linear constraints to the generator coefficients, enabling precise intersections and "inner-approximations" (sets guaranteed to be entirely reachable).

Real-Time Safety and Control

The ultimate goal of this research is to move verification from the design phase to the "run-time" phase.

In RAIL: Reachability-Aided Imitation Learning for Safe Policy Execution, researchers use polynomial zonotopes to create a real-time safety filter for neural networks. If a robot's learned policy suggests an action that would lead the reachable set into an obstacle, the system "projects" that action back into a safe zonotope. Similarly, Simon Schaefer and Helen Oleynikova demonstrate in HumanMPC how representing reachable sets as zonotopes allows complex collision-avoidance constraints to be solved as simple Quadratic Programs in milliseconds.

By treating safety as a geometric problem of set propagation, zonotopic reachability analysis provides the mathematical bridge between high-level autonomous logic and the messy, uncertain reality of physical dynamics.

Papers in this version

Showing 60 of 103 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 82 papers
  2. Version 1 · 2026-10-04 · 103 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_conservative_linearization_8d4fca18,
  title = {conservative linearization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conservative-linearization/rdr_8d4fca18b5e94e839c75cb04e6c2352f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scalable_safety_verification_via_zonotop_8d4fca18_v1,
  title = {Scalable Safety Verification via Zonotopic Reachability Analysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-safety-verification-via-zonotopic-reachability-analysis/rdr_8d4fca18b5e94e839c75cb04e6c2352f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}