State set representations and their usage in the reachability analysis of hybrid systems

• Zustandsmengenrepräsentierungen und ihre Verwendung in der Erreichbarkeitsanalyse Hybrider Systeme

Schupp, Stefan; Ábrahám, Erika (Thesis advisor); Frehse, Goran (Thesis advisor)

Aachen (2019)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2019

Abstract

Hybrid systems in computer science are systems with combined discrete-continuous behavior. This work presents results obtained in the field of safety verification for linear hybrid systems whose continuous behavior can be described by linear differential equations. We focus on a special technique named flowpipe-construction-based reachability analysis, which over-approximates the reachable states of a given hybrid system as a finite union of state sets. In these computations we can use different geometric and symbolic representations for state sets as datatypes. The choice of the state set representation has a strong impact on the precision of the approximation and on the running time of the analysis method. Additionally, numerous further parameters and heuristics influence the analysis outcome. In this work we investigate on the influence and optimal usage of these parameters. Our results are collected in a publicly available open-source C++ programming library named HyPro. The major contributions of this work are threefold: 1) We present our HyPro library offering implementations for several state set representations that are commonly used in flowpipe-construction-based reachability analysis. A unified interface in combination with reduction and conversion methods supports the fast implementation of versatile analysis methods for linear hybrid systems. 2) We put our library to practice and show its applicability by embedding a flowpipe-construction-based reachability analysis method in a CEGAR-based abstraction refinement framework. The parallelization of this approach further increases its performance. 3) We introduce methods to decompose the search space and replace high-dimensional computations by computations in lower-dimensional subspaces. This method is applicable under certain conditions. An automated check of these conditions, an automated decomposition, and the integration of dedicated analysis methods for subspace computations extend our approach.

Institutions

• Department of Computer Science [120000]
• Chair of Computer Science 2 (Software Modeling and Verification) [121310]
• UnRAVeL Research Training Group [080060]