Interval Reachability Analysis : Bounding Trajectories of Uncertain Systems With Boxes for Control and Verification

This brief presents a suite of computationally efficient methods for bounding trajectories of dynamical systems with multi-dimensional intervals, or ‘boxes’. It explains the importance of bounding trajectories for evaluating the robustness of systems in the face of parametric uncertainty, and for verification or control synthesis problems with respect to safety and reachability properties. The methods presented make use of:

• interval analysis;
• monotonicity theory;
• contraction theory; and
• data-driven techniques that sample trajectories.

The methods are implemented in an accompanying open-source Toolbox for Interval Reachability Analysis.

This brief provides a tutorial description of each method, focusing on the requirements and trade-offs relevant to the user, requiring only basic background on dynamical systems. The second part of the brief describes applications of interval reachability analysis. This makesthe brief of interest to a wide range of academic researchers, graduate students, and practising engineers in the field of control and verification. 

Pierre-Jean Meyer received his Master’s degree in Electrical Engineering and Automatic Control from Institut National Polytechnique de Toulouse, France, in 2011. He then received his Ph.D. in Automatic Control from Université Grenoble Alpes, France, in 2015. Between 2015 and 2017, he was a postdoctoral researcher at the Automatic Control Department of KTH Royal Institute of Technology, Sweden. Since December 2017, he has been a postdoctoral researcher at the Electrical Engineering and Computer Sciences Department of U.C. Berkeley. His research interests include reachability analysis and abstraction-based control synthesis.

Alex Devonport received his B.S. in Electrical Engineering from Arizona State University in 2016, where he then worked as a researcher. Since 2017, he has been a graduate student in the Electrical Engineering and Computer Science department of U.C. Berkeley. His main research interests are reachability analysisand data-driven methods in control theory.

Murat Arcak is Professor at U.C. Berkeley in the Electrical Engineering and Computer Sciences Department.  He received his B.S. degree in Electrical Engineering from the Bogazici University, Turkey, in 1996, and his M.S. and Ph.D. degrees from the University of California, Santa Barbara, in 1997 and 2000, respectively. His research is focused on dynamical systems and control theory with applications to synthetic biology, multi-agent systems, and transportation. Prior to joining Berkeley in 2008, he was a faculty member at the Rensselaer Polytechnic Institute. He received a CAREER Award from the National Science Foundation in 2003, the Donald P. Eckman Award from the American Automatic Control Council in 2006, the Control and Systems Theory Prize from the Society for Industrial and Applied Mathematics (SIAM) in 2007, and the Antonio Ruberti Young Researcher Prize from the IEEE Control Systems Society in 2014. He is a member of SIAM and a fellow of IEEE.