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

Abstract

Reachability analysis is the problem of evaluating the set of all states that can be reached by a system starting from a given set of initial states. Since the reachable set can rarely be computed exactly, a standard approach is to over-approximate this set as tightly as possible. Various set representations and methods have been proposed for finding over-approximations; however, they are computationally expensive and do not scale well to high dimensional systems. This is a particularly important shortcoming for “symbolic control,” where the designer must first generate a finite state transition system from a continuous state model with repeated reachability computations. In this talk we present a suite of methods that offer computational efficiency using a simpler set representation in the form of multi-dimensional intervals. These methods leverage nonlinear systems concepts, such as monotonicity and its variants, sensitivity of trajectories to initial conditions and parameters, and contraction properties. We further introduce data-driven approaches for problems where probabilistic guarantees are appropriate. As we demonstrate with examples interval representation and the associated methods are particularly well suited to symbolic control, but of independent interest as well.