Hybrid Systems: From Verification to Falsification

Publication Type:

Book Chapter

Authors:

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

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.springerlink.com/content/h08451055222lw8v/?p=d6bcf97446c84aa8b9415d6d13e90699&pi=1

Keywords:

hybrid systems, HyDICE, kavrakilab, kinodynamic/physics-based motion planning, multi-layered synergistic planning

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.


Preprint PDF     Publisher's web site