Set Propagation Techniques for Reachability Analysis
Top Cited Papers
- 3 May 2021
- journal article
- research article
- Published by Annual Reviews in Annual Review of Control, Robotics, and Autonomous Systems
- Vol. 4 (1), 369-395
- https://doi.org/10.1146/annurev-control-071420-081941
Abstract
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. Expected final online publication date for the Annual Review of Control, Robotics, and Autonomous Systems, Volume 4 is May 3, 2021. Please see http://www.annualreviews.org/page/journal/pubdates for revised estimates.Keywords
This publication has 110 references indexed in Scilit:
- Bounds on the reachable sets of nonlinear control systemsAutomatica, 2013
- PHAVer: algorithmic verification of hybrid systems past HyTechInternational Journal on Software Tools for Technology Transfer, 2008
- Convexity of reachable sets of nonlinear ordinary differential equationsAutomation and Remote Control, 2007
- Verification of a cruise control system using counterexample-guided searchControl Engineering Practice, 2004
- Computational techniques for hybrid system verificationIEEE Transactions on Automatic Control, 2003
- Extended convex hullComputational Geometry, 2001
- What's Decidable about Hybrid Automata?Journal of Computer and System Sciences, 1998
- Algorithmic analysis of nonlinear hybrid systemsIEEE Transactions on Automatic Control, 1998
- How good are convex hull algorithms?Computational Geometry, 1997
- The algorithmic analysis of hybrid systemsTheoretical Computer Science, 1995