Combinatorial Methods for Invariance and Safety of Hybrid Systems

Nikolaos Athanasopoulos, Raphaël M. Jungers

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)
274 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)130-140
Number of pages11
Early online date22 Sept 2018
Publication statusPublished - Dec 2018


Dive into the research topics of 'Combinatorial Methods for Invariance and Safety of Hybrid Systems'. Together they form a unique fingerprint.

Cite this