Underapproximating backward reachable sets by semialgebraic sets
Date of Issue2017
School of Computer Science and Engineering
Underapproximations (UAs) of backward reachable sets play an important role in controller synthesis and trajectory analysis for constrained nonlinear dynamical systems, but there are few methods available to compute them. Given a nonlinear system, a target region of simply connected compact type and a time duration, we present a method using boundary analysis to compute an UA of the backward reachable set. The UA is represented as a semialgebraic set, formed by what we term polynomial level - set functions. The polynomial level - set function is a semidefinite positive function with one real root, such that the interior and closure of a semialgebraic set formed by it are both simply connected and have the same boundary. The function can be computed by solving a convex program, which is constructed based on sum-of-squares decomposition and linear interval inequalities. We test our method on several examples and compare them with existing methods. The results show that our method can obtain better estimations more efficiently in terms of time for these special examples.
IEEE Transactions on Automatic Control
© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: [http://dx.doi.org/10.1109/TAC.2017.2694351].