Hybrid Systems: From Verification to Falsification

Publication Type:

Book Chapter

Authors:

Plaku, E.; Kavraki, L.E.; Vardi, M.Y.

Source:

International Conference on Computer Aided Verification (CAV), Lecture Notes in Computer Science, Springer-Verlag Heidelberg, Volume 4590, Berlin, Germany, p.468--481 (2007)

URL:

http://www.kavrakilab.org/sites/default/files/PaperCAV_HyDICE-h.pdf

Keywords:

hybrid systems; kinodynamic/physics-based motion planning; project_Hybrid

Abstract:

We propose HyDICE, Hybrid DIscrete Continuous Exploration,
a multi-layered approach for hybrid-system testing that integrates
continuous sampling-based robot motion planning with discrete searching.
The discrete search uses the discrete transitions of the hybrid system and
coarse-grained decompositions of the continuous state spaces or related
projections to guide the motion planner during the search for witness
trajectories. Experiments presented in this paper, using a hybrid system
inspired by robot motion planning and with nonlinear dynamics associated
with each of several thousand modes, provide an initial validation of
HyDICE and demonstrate its promise as a hybrid-system testing method.
Comparisons to related work show computational speedups of up to two
orders of magnitude.