Set Propagation Techniques for Reachability Analysis

By Matthias Althoff, Goran Frehse, Antoine Girard. Annu. Rev. Control. Robotics Auton. Syst., 2021

297 citations recorded by the source corpus.

Reachability analysis consists in computing the set of states that are reachable by a dynamical system from all initial states and for all admissible inputs and parameters. It is a fundamental problem motivated by many applications in formal verification, controller synthesis, and estimation, to name only a few. This article focuses on a class of methods for computing a guaranteed overapproximation of the reachable set of continuous and hybrid systems, relying predominantly on set propagation; starting from the set of initial states, these techniques iteratively propagate a sequence of sets according to the system dynamics. After a review of set representation and computation, the article presents the state of the art of set propagation techniques for reachability analysis of linear, nonlinear, and hybrid systems. It ends with a discussion of successful applications of reachability analysis to real-world problems.

Subfields: Computational Theory and Mathematics, Control and Systems Engineering

View Paper: https://www.semanticscholar.org/paper/c8575c73b02dbbba3a6f56830310cb289e64b52e