Combinatorial methods for invariance and safety of hybrid systems

Inspired by Switching Systems and Automata theory, we investigate how combinatorial analysis techniques can be performed on a hybrid automaton in order to enhance its safety or invariance analysis. We focus on the particular case of Constrained Switching Systems, that is, hybrid automata with linear dynamics and no guards. We follow two opposite approaches, each with unique benefits: First, we construct invariant sets via the ‘Reduced’ system, induced by a smaller graph which consists of the essential nodes, called the unavoidable nodes. The computational amelioration of working with a smaller, and in certain cases the minimum necessary number of nodes, is significant. Second, we exploit graph liftings, in particular the Iterated Dynamics Lift (T -Lift) and the Path-Dependent Lift (P-Lift). For the former case, we show that invariant sets can be computed in a fraction of the iterations compared to the non-lifted case, while we show how the latter can be utilized to compute non-convex approximations of invariant sets of a controlled complexity. We also revisit well studied problems, highlighting the potential benefits of the approach. In particular, we apply our framework to (i) invariant sets computations for systems with dwell-time restrictions, (ii) fast computations of the maximal invariant set for uncertain linear systems and (iii) non-convex approximations of the minimal invariant set for arbitrary switching linear systems.