Combining zonotopes and support functions for efficient reachability analysis of linear systems
Matthias Althoff, Goran Frehse · 2016
Reachability analysis is an important technique for formally verifying continuous systems, as well as for guaranteed state estimation, stability analysis, and controller synthesis. We present a detailed assessment of the computational efficiency for the reachability analysis of linear systems with respect to the two most scalable set representations: zonotopes and support functions. As a result, we propose representing reachable sets as a combination of support functions and zonotopes. This mix of representations can be converted to polyhedra of desired (directional) precision, at a higher precision compared to exclusively using support functions or zonotopes. The benefits are shown by an in-depth analysis of computational complexity and by numerical experiments.