Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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, Antti

dblp

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

URL of the conference:


URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section