Efficient guiding towards cost-optimality in UPPAAL

Gerd Behrmann, Ansgar Fehnker, Thomas Hune, Kim Larsen, Paul Pettersson, Judi Romijn

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

95 Citations (Scopus)

Abstract

In this paper we present an algorithm for efficiently computing the minimum cost of reaching a goal state in the model of Uniformly Priced Timed Automata (UPTA). This model can be seen as a submodel of the recently suggested model of linearly priced timed automata, which extends timed automata with prices on both locations and transitions. The presented algorithm is based on a symbolic semantics of UTPA, and an efficient representation and operations based on difference bound matrices. In analogy with Dijkstra’s shortest path algorithm, we show that the search order of the algorithm can be chosen such that the number of symbolic states explored by the algorithm is optimal, in the sense that the number of explored states can not be reduced by any other search order. We also present a number of techniques inspired by branch-and-bound algorithms which can be used for limiting the search space and for quickly finding near-optimal solutions.
Original languageEnglish
Title of host publicationTools and Algorithms for the Construction and Analysis of Systems
Subtitle of host publication7th International Conference, TACAS 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001 Genova, Italy, April 2-6, 2001, Proceedings
EditorsTiziana Margaria, Wang Yi
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages174-188
Number of pages15
ISBN (Print)3540418652
DOIs
Publication statusPublished - 2001
Externally publishedYes
Event7th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2001 held as part of the Europ ean Joint Conference on Theory and Practice of Software, ETAPS 2015 - Genova, Italy
Duration: 2 Apr 20016 Apr 2001

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Springer Nature
Volume2031
ISSN (Print)0302-9743

Conference

Conference7th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2001 held as part of the Europ ean Joint Conference on Theory and Practice of Software, ETAPS 2015
Country/TerritoryItaly
CityGenova
Period2/04/016/04/01

Fingerprint

Dive into the research topics of 'Efficient guiding towards cost-optimality in UPPAAL'. Together they form a unique fingerprint.

Cite this