UC Santa Cruz

Reachability analysis is a method to guarantee the performance of safety-critical applications such as automated driving and robotics against dynamic uncertainties. The main object of study is the reach set, defined as the set of states that a controlled dynamical system may reach at a future time, depending on a set-valued evolution of uncertainties. We develop the theory and algorithms for learning the reach sets of full state feedback linearizable systems---an important class of nonlinear control systems, common in vehicular applications such as automobiles and drones. These reach sets, in very general settings, are compact but nonconvex. The new idea we propose is to compute these reach sets in the associated Brunovsky normal coordinates, and then transform the sets back to the original coordinates via known diffeomorphisms. Our algorithms exploit learning-theoretic ideas to provide probabilistic guarantees on the computed sets.

As a by-product of our analysis, we uncover the exact geometry of the integrator reach set with compact set-valued inputs. These exact results include the closed-form parametric and implicit formulae for the boundaries, volumes, and widths of the integrator reach sets. The exact parametric formula for the boundary admits an integral representation involving the boundary of the compact input sets. The exact implicit formula is given by the vanishing of certain Hankel determinants. These results on integrators should be of independent interest, serving as benchmarks for quantifying the conservatism in reach set computation algorithms.

Our geometric analysis also helps clarify a taxonomy, i.e., what kind of compact convex sets can the integrator reach sets be. We show that the integrator reach sets resulting from arbitrary, time-invariant, compact input sets are zonoids and semialgebraic, but not spectrahedra. The integrator reach sets resulting from arbitrary, time-varying, compact input sets are shown to be zonoids but not semialgebraic in general.

We detail how these geometric results enable the semi-analytical computation of the reach set of any controllable linear time invariant system, as well as the reach sets of full state feedback linearizable systems.

Leveraging an Isomorphism between compact sets and their support functions, we also propose a data-driven method for learning any general compact set.

This is useful for learning compact sets such as reach sets, maximal control invariant sets, region-of-attraction that are related to an underlying nonlinear dynamical system but an analytic model for the dynamical nonlinearities are unavailable. Our results show that the proposed geometric learning ideas can be efficient when we only have access to simulated or experimentally observed data. We demonstrate computational learning of these compact sets by carrying out regression analyses on their support functions using finite data sets.Finally, we outline the directions for future research.