UC Santa Cruz

We study the problem of computing the forward “reachable tube”, defined as a tem- poral union of the “reach sets” of a dynamical system, or the sets of states the system can attain in future instances of time when subject to set-valued uncertainties in its initial conditions, controls, and exogenous disturbances. Fast computation of the reachable tubes for uncertain dynamical systems is essential for safety-critical applica- tions such as autonomous driving and unmanned aerial systems traffic management where much of the high-level decision making (e.g., lane changing in autonomous driving or switching between motion primitives during flight of an unmanned aerial system) critically depends on the reachable tubes. At the same time, computation of the reachable tubes is difficult in general, due to the high-dimensional, non-convex nature of the problem. Yet applications mentioned before demand their accurate computation at a time scale much smaller than that of the physical dynamics.

In this thesis, we propose a framework for computing tight outer approximations of forward reachable tubes in real-time that leverages parallel computation. Our algorithm builds on ellipsoidal calculus and convex optimization. We report numerical results to demonstrate the efficacy of the proposed algorithm.