Reachable Set Estimation and Safety Verification of Nonlinear Systems via Iterative Sums of Squares Programming

In this paper, the problems of forward reachable set estimation and safety verification of uncertain nonlinear systems with polynomial dynamics are addressed. First, an iterative sums of squares (SOS) programming approach is developed for reachable set estimation. It characterizes the over-approximations of the forward reachable sets by sub-level sets of time-varying Lyapunov-like functions that satisfy an invariance condition, and formulates the problem of searching for the Lyapunov-like functions as a bilinear SOS program, which can be solved via an iterative algorithm. To make the over-approximation tight, the proposed approach seeks to minimize the volume of the over-approximation set with a desired shape. Then, the reachable set estimation approach is extended for safety verification, via explicitly encoding the safety constraint such that the Lyapunov-like functions guarantee both reaching and avoidance. The efficiency of the presented method is illustrated by some numerical examples.