Inner Approximating Robust Reach-Avoid Sets for Discrete-Time Polynomial Dynamical Systems

Reach-avoid analysis, which involves the computation of reach-avoid sets, is an established tool that provides hard guarantees of safety (via avoiding unsafe states) and target reachability (via reaching target sets) and, therefore, is widely used in safe-critical systems design, such as air traffic management systems and biomedical systems. This article investigates the problem of inner approximating robust reach-avoid sets for discrete-time polynomial dynamical systems subject to disturbances over open (i.e., not bounded a priori) time horizons. The robust reach-avoid set of interest is a set of all initial states such that the system starting from each of them should reach a target set within a bounded time horizon while staying inside a safe set before the first target hitting time, despite the actual disturbance. Based on a discounted value function and the dynamic programming principle, we show that the robust reach-avoid set can be characterized exactly via the unique bounded solution to a Bellman-type equation. Due to the insurmountable challenge in solving this equation analytically, we reformulate the Bellman-type equation such that its straightforward relaxation can result in a set of novel constraints for inner approximating the robust reach-avoid set. When the data involved are polynomials, i.e., the safe set, target set, and disturbance set are semialgebraic, the problem of solving this set of constraints can be encoded into a semidefinite program, which can be solved efficiently in polynomial time via interior point methods. Finally, several examples demonstrate the performance of the proposed method.