Divide and Conquer: Variable Set Separation in Hybrid Systems Reachability Analysis

Stefan Schupp
(RWTH Aachen University)
Johanna Nellen
(RWTH Aachen University)
Erika Ábrahám
(RWTH Aachen University)

In this paper we propose an improvement for flowpipe-construction-based reachability analysis techniques for hybrid systems. Such methods apply iterative successor computations to pave the reachable region of the state space by state sets in an over-approximative manner. As the computational costs steeply increase with the dimension, in this work we analyse the possibilities for improving scalability by dividing the search space in sub-spaces and execute reachability computations in the sub-spaces instead of the global space. We formalise such an algorithm and provide experimental evaluations to compare the efficiency as well as the precision of our sub-space search to the original search in the global space.

In Herbert Wiklicky and Erik de Vink: Proceedings 15th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2017), Uppsala, Sweden, 23rd April 2017, Electronic Proceedings in Theoretical Computer Science 250, pp. 1–14.
This work was partially supported by the German Research Council (DFG) in the context of the HyPro project.
Published: 12th July 2017.

ArXived at: http://dx.doi.org/10.4204/EPTCS.250.1 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org