MPI-INF Logo
Publications

Server    halma.mpi-inf.mpg.de

Proceedings Article, Paper


@InProceedings
Beitrag in Tagungsband, Workshop
Author, Editor
Author(s):
Kupferschmid, Sebastian
Hoffmann, Jörg
Dierks, Henning
Behrmann, Gerd		dblp
dblp
dblp
dblp
Not MPG Author(s):
Kupferschmid, Sebastian
Dierks, Henning
Behrmann, Gerd
Editor(s):
Valmari, Anttidblp
Not MPII Editor(s):
Valmari, Antti
BibTeX cite key*:
KupferschmidEtAl2006
Title, Booktitle
Title*:
Adapting an AI Planning Heuristic for Directed Model Checking
Booktitle*:
Model checking software : 13th International SPIN Workshop
Event, URLs
Conference URL::
Downloading URL:
http://www.springerlink.com/content/r5141t3t21476m73/fulltext.pdf
Event Address*:
Vienna, Austria
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
30 March 2006
Event End Date:
1 April 2006
Publisher
Name*:
Springer
URL:
http://www.springer.com/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3925
Number:
Month:
Pages:
35-52
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
978-3-540-33102-5; 3-540-33102-6
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:

There is a growing body of work on directed model checking, which improves the falsification of safety properties by providing heuristic functions that can guide the search quickly towards short error paths. Techniques of this kind have also been made very successful in the area of AI Planning. Our main technical contribution is the adaptation of the most successful heuristic function from AI Planning to the model checking context, yielding a new heuristic for directed model checking. The heuristic is based on solving an abstracted problem in every search state. We adapt the abstraction and its solution to networks of communicating automata annotated with (constraints and effects on) integer variables. Since our ultimate goal in this research is to also take into account clock variables, as used in timed automata, our techniques are implemented inside UPPAAL. We run experiments in some toy benchmarks for timed automata, and in two timed automata case studies originating from an industrial project. Compared to both blind search and some previously proposed heuristic functions, we consistently obtain significant, sometimes dramatic, search space reductions, resulting in likewise strong reductions of runtime and memory requirements.

This work was partly supported by the German Research Council (DFG) as part of the Transregional Collaborative Research Center “Automatic Verification and Analysis of Complex Systems” (SFB/TR 14 AVACS). See http://www.avacs.org/ for more information.

URL for the Abstract:
http://dx.doi.org/10.1007/11691617_3
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Programming Logics Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, CCL bibliography, VG Wort



BibTeX Entry:
@INPROCEEDINGS{KupferschmidEtAl2006,
AUTHOR = {Kupferschmid, Sebastian and Hoffmann, J{\"o}rg and Dierks, Henning and Behrmann, Gerd},
 EDITOR = {Valmari, Antti},
 TITLE = {Adapting an AI Planning Heuristic for Directed Model Checking},
 BOOKTITLE = {Model checking software : 13th International SPIN Workshop},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {3925},
 PAGES = {35--52},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Vienna, Austria},
 ISBN = {978-3-540-33102-5},
; ISBN = {3-540-33102-6},
}

Entry last modified by Uwe Brahm, 01/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Jörg Hoffmann		Created
02/13/2006 11:43:45 AM
Revisions
5.
4.
3.
2.
1.		Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm		Edit Dates
2007-04-26 13:10:48
2007-04-26 13:10:23
2007-04-26 13:04:33
04/11/2007 08:26:35 AM
16.02.2007 09:31:43