Conservative Linearization for Reachability Analysis

110 concepts88 papers2 proposals

When deploying autonomous vehicles or robotic systems in safety-critical environments, traditional testing via point-based simulation is insufficient. A simulation can show that a vehicle avoids an obstacle under one specific trajectory, but it cannot prove safety for the infinite variety of disturbances, sensor noises, and initial conditions the system might encounter in the real world.

To provide mathematical guarantees, researchers use reachability analysis. Instead of tracking a single state over time, reachability analysis propagates an entire set of possible initial states through the system's dynamics. The goal is to compute a "flow-pipe"—an over-approximation of every state the system could possibly reach. If this flow-pipe never intersects with an unsafe region (such as an obstacle or a crash state), the system is formally proven to be safe.

However, computing these sets exactly is notoriously difficult. For nonlinear systems, it is generally mathematically intractable. The core insight of this research direction is to combine highly efficient geometric set representations—specifically zonotopes—with a technique called conservative linearization to achieve scalable, formally trustworthy verification.

The Geometry of Uncertainty: Why Zonotopes?

The choice of how to represent a set of states determines whether reachability analysis takes milliseconds or hours. Traditional representations like general polyhedra suffer from the "curse of dimensionality": as the number of state variables grows, the number of vertices or facets explodes exponentially.

To bypass this complexity, much of the literature relies on zonotopes, a specific class of centrally symmetric polytopes. Intuitively, a zonotope can be thought of as the projection (or shadow) of a higher-dimensional hypercube onto a lower-dimensional space. Mathematically, a zonotope is defined by a center vector $c$ and a set of generator vectors $g_i$:

$$Z = \left\{ c + \sum_{i=1}^m \beta_i g_i \;\middle|\; \beta_i \in [-1, 1] \right\}$$

This representation is incredibly powerful because the two fundamental operations required to propagate states through linear dynamics are computationally trivial:

  1. Linear Transformations: Multiplying a zonotope by a matrix $A$ simply requires multiplying the center and each generator by $A$.
  2. Minkowski Sums: Adding two sets together (for instance, adding a set of states to a set of bounded disturbances) is achieved by simply concatenating their generators.

As shown by Matthias Althoff in Reachability Analysis of Large Linear Systems With Uncertain Inputs in the Krylov Subspace, these properties allow zonotopes to track uncertainty in high-dimensional linear systems with far lower computational complexity than general polyhedral methods. Tools evaluated in the ARCH friendly competitions, such as those reviewed by Matthias Althoff et al. in reports like ARCH-COMP18 Category Report: Continuous and Hybrid Systems with Linear Continuous Dynamics and ARCH-COMP24 Category Report: Continuous and Hybrid Systems with Linear Continuous Dynamics, heavily leverage zonotopes and related structures like Taylor models to maintain high numerical precision while scaling to complex systems.

Bridging the Nonlinear Gap: Conservative Linearization

While zonotopes make linear reachability analysis highly efficient, real-world systems—such as autonomous cars or chemical processes—are inherently nonlinear. If we attempt to propagate a zonotope directly through a nonlinear function, it loses its symmetric structure, making exact computation impossible.

This is where conservative linearization comes in. In Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars, Matthias Althoff formalized a method to abstract nonlinear dynamics into a linear system without losing formal guarantees.

Instead of trying to compute the reachability of a complex nonlinear function $f(x)$, the function is linearized around a given state or set using a Taylor series expansion:

$$f(x) \approx f(x_0) + J(x_0)(x - x_0) + \mathcal{R}$$

where $J(x_0)$ is the Jacobian matrix and $\mathcal{R}$ represents the higher-order Taylor remainder terms. In standard engineering applications, this remainder is simply discarded. In conservative linearization, however, the remainder $\mathcal{R}$ is rigorously bounded over the entire set of states being considered. This bound is treated as an additional, uncertain but bounded input to the linearized system.

By encapsulating the linearization error as a symbolic error term, the original nonlinear system is abstracted into a linear differential inclusion. Because the error bound is guaranteed to contain all possible deviations between the linear approximation and the true nonlinear dynamics, the reachable set computed for this abstract linear system is a guaranteed over-approximation of the true nonlinear system's behavior.

As highlighted in category reports like ARCH-COMP17 Category Report: Continuous Systems with Nonlinear Dynamics by Matthias Althoff et al. and ARCH-COMP20 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics by Luca Geretti et al., this mechanism allows verification tools to leverage fast linear solvers while maintaining absolute safety guarantees for nonlinear systems.

Taming the Wrapping Effect with Advanced Enclosures

While conservative linearization provides a path forward, it introduces a secondary challenge known as the wrapping effect. When an over-approximating geometric shape (like a standard zonotope) is used to enclose a set that is rotating or shearing over time, the shape must be artificially enlarged to fit the true state space. Over multiple time steps, these accumulated over-approximations can compound exponentially, causing the computed flow-pipe to blow up to an unusable size.

To preserve the functional dependencies between initial states and future outcomes, researchers have introduced higher-order extensions. Luca Geretti et al. discuss the use of high-order Taylor models in ARCH-COMP21 Category Report: Continuous and Hybrid Systems with Nonlinear Dynamics, which approximate the flow of nonlinear systems as polynomial functions with interval error remainders.

Similarly, Niklas Kochdumper et al. demonstrate the utility of polynomial zonotopes in Utilizing dependencies to obtain subsets of reachable sets. Unlike standard zonotopes, which assume linear combinations of independent factors, polynomial zonotopes allow the generators to depend nonlinearly on shared underlying parameters. This preserves the mathematical relationships between state variables as they evolve, drastically reducing the wrapping effect.

For scenarios involving non-convex sets or complex data-driven system matrices, Z. Zhang et al. introduced constrained polynomial zonotopes in Data-Driven Nonconvex Reachability Analysis Using Exact Multiplication. By adding explicit linear equality constraints to the polynomial factors, this representation maintains closure under multiplication and intersection without introducing conservative approximations, allowing researchers to track non-convex reachable sets exactly.

Broad Applications in Modern Autonomy

By transforming intractable nonlinear problems into scalable geometric operations, conservative linearization and advanced zonotopic representations have unlocked real-time verification across diverse domains:

Ultimately, the power of this research direction lies in its pragmatic compromise: it acknowledges that exact nonlinear reachability is impossible, but proves that through clever geometry and rigorous error bounding, we can still achieve absolute mathematical certainty of safety.

Key Foundational Work

A GEOMETRIC APPROACH TO REACHABILITY COMPUTATIONS FOR CONSTRAINED DISCRETE-TIME SYSTEMS (2002) — contributed 3 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_conservative_linearization_8d4fca18_v2,
  title = {conservative linearization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conservative-linearization/rdr_8d4fca18b5e94e839c75cb04e6c2352f/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake