Utilizing Dependencies to Obtain Subsets of Reachable Sets

Niklas Kochdumper, Bastian Schürmann, Matthias Althoff

Published 2019-10-18Version 1

Reachability analysis has become a fundamental method supporting formally-correct synthesis, robust model predictive control, set-based observers, fault detection, invariant computation, and conformance checking, to name only a few. In many of these applications, one requires to compute a reachable set starting within a previously computed reachable set. While it was previously required to re-compute the entire reachable set, we demonstrate that one can leverage the dependencies of states within the previously computed set. As a result, we almost instantly obtain an over-approximative subset of a previously computed reachable set by evaluating analytical maps. The advantages of our novel method are demonstrated for falsification of systems, optimization over reachable sets, and synthesizing safe maneuver automata. In all of these applications, the computation time is reduced significantly.