Convex computation of the reachable set for controlled polynomial hybrid systems

This paper presents an approach to computing the time-limited backwards reachable set (BRS) of a semialgebraic target set for controlled polynomial hybrid systems with semialgebraic state and input constraints. By relying on the notion of occupation measures, the computation of the BRS of a target set that may be distributed across distinct subsystems of the hybrid system, is posed as an infinite dimensional linear program (LP). Computationally tractable approximations to this LP are constructed via a sequence of semidefinite programs each of which is proven to construct an outer approximation of the true BRS with asymptotically vanishing conservatism. In contrast to traditional Lyapunov based approaches, the presented approach is convex and does not require any form of initialization. The performance of the presented algorithm is illustrated on 2 nonlinear controlled hybrid systems.