Reach-Avoid Verification Based on Convex Optimization

• 成果类型: Article
• 署名作者: Xue, Bai; Zhan, Naijun; Fraenzle, Martin; Wang, Ji; Liu, Wanwei
• 署名单位: Chinese Academy of Sciences; Institute of Software, CAS; Carl von Ossietzky Universitat Oldenburg; National University of Defense Technology - China
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3274821
• 发表日期: 2024
• 页码: 598-605
• 关键词: trajectory; programming; Wrapping; safety; reachability analysis; optimization; computational modeling; Ordinary differential equations (ODEs); quantified constraints; reach-avoid verification

摘要

In this article, we propose novel sufficient conditions for verifying reach-avoid properties of continuous-time systems modeled by ordinary differential equations. Given a system, an initial set, a safe set, and a target set of states, we say that the reach-avoid property holds if, for all initial conditions in the initial set, any trajectory of the system starting at them will eventually, i.e., in unbounded yet finite time, enter the target set while remaining inside the safe set until that first target hit (that is, if the system starting from the initial set can reach the target set safely). Based on a discount value function, two sets of quantified constraints are derived for verifying the reach-avoid property via the computation of exponential/asymptotic guidance-barrier functions (they form a barrier escorting the system to the target set safely at an exponential or asymptotic rate). It is interesting to find that one set of constraints whose solution is termed exponential guidance-barrier functions is just a simplified version of the existing one derived from the moment based method, while the other one whose solution is termed asymptotic guidance-barrier functions is completely new. Furthermore, built upon this new set of constraints, we derive a set of more expressive constraints, which includes the aforementioned two sets of constraints as special instances, providing more chances for verifying the reach-avoid property successfully. Finally, several examples demonstrate the theoretical developments and performance of proposed sufficient conditions using semidefinite programming methods.