Efficient Norm-Based Reachable Sets via Iterative Dynamic Programming

Abstract

In this work, we present a numerical optimal control framework for reachable set computation using \emph{normotopes}, a new set representation as a norm ball with a shaping matrix. In reachable set computations, we expect to continuously vary the shape matrix as a function of time. Incorporating the shape dynamics as an input, we build a \emph{controlled embedding system} using a linear differential inclusion overapproximating the dynamics of the system, where a single forward simulation of this embedding system always provides an overapproximating reachable set of the system, no matter the choice of \emph{hypercontrol}. By iteratively solving a linear quadratic approximation of the nonlinear optimal hypercontrol problem, we synthesize less conservative final reachable sets, providing a natural tradeoff between runtime and accuracy. Terminating our algorithm at any point always returns a valid reachable set overapproximation.