Scalable Reachability Analysis

March 17, 2023, ESB 2001

Murat Arcak

UC Berkeley, EECS


The computation of reachable sets is critical for characterizing the behavior of safety-critical systems. Since the reachable set can rarely be computed exactly, several methods have been developed to approximate this set with various set representations. However, these methods are computationally expensive and do not scale well to high dimensional systems. This talk will present a suite of methods with superior scalability properties. After a quick review of some of our earlier techniques using monotonicity and sensitivity concepts, we will discuss more recent results with a data-driven approach. This approach is particularly suitable for high-dimensional and analytically intractable system models. We use a finite ensemble of sample trajectories to compute reachable set estimates, and we provide guarantees of high accuracy in a probabilistic sense with associated sample complexity bounds. We will present two computational methods with this flavor. The first one uses scenario optimization to construct reachable set estimates as approximate solutions to chance-constrained optimization problems. The second method uses a class of polynomials derived from empirical moment matrices, whose sublevel sets act as non-convex estimates of the reachable set.

Speaker's Bio

Murat Arcak is a professor at UC Berkeley in Electrical Engineering and Computer Sciences, and Mechanical Engineering. He received his PhD from UCSB in 2000. His research is in control theory, autonomous systems, and multi-agent systems, with applications in transportation, energy, and biology. 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 in 2007, and the Antonio Ruberti Young Researcher Prize from the IEEE Control Systems Society in 2014. He is a fellow of IEEE and the International Federation of Automatic Control

Video URL: