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

Abstract

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 Proceedings QAPL 2017, arXiv:1707.03668. This work was partially supported by the German Research Council (DFG) in the context of the HyPro project

Cited by in corpus (5)

• Reach Set Approximation through Decomposition with Low-dimensional Sets and High-dimensional Matrices
• Reachability analysis of linear hybrid systems via block decomposition
• Efficient Convex Zone Merging in Parametric Timed Automata
• Robot Swarms as Hybrid Systems: Modelling and Verification
• Quantitative Aspects of Programming Languages and Systems over the past $2^4$ years and beyond