Semidefinite Outer Approximation of the Backward Reachable Set of Discrete-time Autonomous Polynomial Systems
This provides a computational method for control and verification of polynomial dynamical systems, though it appears incremental as it builds on the occupation measure approach.
The paper tackles the problem of approximating backward reachable sets for discrete-time autonomous polynomial systems by formulating it as an infinite-dimensional linear programming problem and approximating it with a hierarchy of semidefinite programs, demonstrating the approach on three dynamical systems.
We approximate the backward reachable set of discrete-time autonomous polynomial systems using the recently developed occupation measure approach. We formulate the problem as an infinite-dimensional linear programming (LP) problem on measures and its dual on continuous functions. Then we approximate the LP by a hierarchy of finite-dimensional semidefinite programming (SDP) programs on moments of measures and their duals on sums-of-squares polynomials. Finally we solve the SDP's and obtain a sequence of outer approximations of the backward reachable set. We demonstrate our approach on three dynamical systems. As a special case, we also show how to approximate the preimage of a compact semi-algebraic set under a polynomial map.