A Hamilton-Jacobi-Bellman Approach to Ellipsoidal Approximations of Reachable Sets for Linear Time-Varying Systems

Reachable sets for a dynamical system describe collections of system states that can be reached in finite time, subject to system dynamics. They can be used to guarantee goal satisfaction in controller design or to verify that unsafe regions will be avoided. However, general-purpose methods for computing these sets suffer from the curse of dimensionality, which typically prohibits their use for systems with more than a small number of states, even if they are linear. In this paper, we demonstrate that viscosity supersolutions and subsolutions of a Hamilton-Jacobi-Bellman equation can be used to generate, respectively, under-approximating and over-approximating reachable sets for time-varying nonlinear systems. Based on this observation, we derive dynamics for a union and intersection of ellipsoidal sets that, respectively, under-approximate and over-approximate the reachable set for linear time-varying systems subject to an ellipsoidal input constraint and an ellipsoidal terminal (or initial) set. We demonstrate that the dynamics for these ellipsoids can be selected to ensure that their boundaries coincide with the boundary of the exact reachable set along a solution of the system. The ellipsoidal sets can be generated with polynomial computational complexity in the number of states, making our approximation scheme computationally tractable for continuous-time linear time-varying systems of relatively high dimension.