Guided search for hybrid systems based on coarse-grained space abstractions
Open Access
- 7 August 2015
- journal article
- spin 2013
- Published by Springer Nature in International Journal on Software Tools for Technology Transfer
- Vol. 18 (4) , 449-467
Abstract
Hybrid systems represent an important and powerful formalism for modeling real-world applications such as embedded systems. A verification tool like SpaceEx is based on the exploration of a symbolic search space (the region space). As a verification tool, it is typically optimized towards proving the absence of errors. In some settings, e.g., when the verification tool is employed in a feedback-directed design cycle, one would like to have the option to call a version that is optimized towards finding an error trajectory in the region space. A recent approach in this direction is based on guided search. Guided search relies on a cost function that indicates which states are promising to be explored, and preferably explores more promising states first. In this paper, we propose an abstraction-based cost function based on coarse-grained space abstractions for guiding the reachability analysis. For this purpose, a suitable abstraction technique that exploits the flexible granularity of modern reachability analysis algorithms is introduced. The new cost function is an effective extension of pattern database approaches that have been successfully applied in other areas. The approach has been implemented in the SpaceEx model checker. The evaluation shows its practical potential.Keywords
This publication has 40 references indexed in Scilit:
- Reachability analysis of linear systems using support functionsNonlinear Analysis: Hybrid Systems, 2010
- Coverage-guided test generation for continuous and hybrid systemsFormal Methods in System Design, 2009
- PHAVer: algorithmic verification of hybrid systems past HyTechInternational Journal on Software Tools for Technology Transfer, 2008
- Abstractions for hybrid systemsFormal Methods in System Design, 2007
- Computational techniques for hybrid system verificationIEEE Transactions on Automatic Control, 2003
- On the regularization of Zeno hybrid automataSystems & Control Letters, 1999
- Pattern DatabasesComputational Intelligence, 1998
- Design and evaluation tools for Automated Highway Systems1996
- The algorithmic analysis of hybrid systemsTheoretical Computer Science, 1995
- Smart cars on smart roads: problems of controlIEEE Transactions on Automatic Control, 1993