A fast method for solving guard set intersection in nonlinear hybrid reachability

摘要

Reachability computation formulates the problem of simulating the behavior of a continuous or hybrid dynamical system in a set-theoretical framework. Compared to the stochastic approach, it provides guaranteed results and has been shown highly valuable for verification or synthesis tasks. This issue is still quite challenging for uncertain nonlinear hybrid dynamical systems.Recently, [1] proposed a method for solving the flow/guard intersection problem that is at the core of hybrid reachability. It first derives an analytical expression for the boundaries of continuous flows using interval Taylor methods and techniques for controlling the wrapping effect. It then expresses the event detection and localization problem underlying flow/guard intersection as a constraint-satisfaction problem (CSP). One of the main issues in interval integration is to control, at each step, the overestimation of the reachable state set due to the wrapping effect. For this purpose, [1] only relies on the geometrical transformation induced by Lohner's QR-factorization method [4], which acts at the integration step. But when dealing with hybrid systems, another source of overestimation exists at the transition step. This paper describes an efficient method for solving flow/guard intersection: using the standard contractor HC4Revise at the transitions step, we will show how to minimize both the overestimation of the flow/guard intersection and the computational complexity, hence computation time. Interestingly, the geometrical transformation introduced by Lohner's QR-factorization method combined with our method, eventually minimizes the overestimation for the whole hybrid flow trajectory. The performance of the new method is illustrated on examples involving typical hybrid systems.