Minimum-Cost Reachability for Priced Timed Automata

Gerd Behrmann; Ansgar Fehnker; Thomas Hune; Kim Larsen; Paul Pettersson; Judi Romijn; Frits W. Vaandrager

doi:10.1007/3-540-45351-2_15

Minimum-Cost Reachability for Priced Timed Automata

Gerd Behrmann
, Ansgar Fehnker
, Thomas Hune
, Kim Larsen
, Paul Pettersson
, Judi Romijn
, Frits W. Vaandrager

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

256 Citations (Scopus)

Abstract

This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques and a new notion of priced regions. The latter allows symbolic representation and manipulation of reachable states together with the cost of reaching them.

Original language	English
Title of host publication	Hybrid Systems: Computation and Control
Subtitle of host publication	4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings
Editors	Maria Domenica Di Benedetto, Alberto L. Sangiovanni-Vincentelli
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	147-161
Number of pages	15
ISBN (Electronic)	978-3-540-45351-2
ISBN (Print)	978-3-540-41866-5
DOIs	https://doi.org/10.1007/3-540-45351-2_15
Publication status	Published - 2001
Externally published	Yes
Event	4th International Workshop on Hybrid Systems: Computation and Control 2001 - Rome, Italy Duration: 28 Mar 2001 → 30 Mar 2001 Conference number: 4

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2034
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th International Workshop on Hybrid Systems: Computation and Control 2001
Abbreviated title	HSCC 2001
Country/Territory	Italy
City	Rome
Period	28/03/01 → 30/03/01

Keywords

n/a OA procedure

Access to Document

10.1007/3-540-45351-2_15

Cite this

Behrmann, G., Fehnker, A., Hune, T., Larsen, K., Pettersson, P., Romijn, J., & Vaandrager, F. W. (2001). Minimum-Cost Reachability for Priced Timed Automata. In M. D. D. Benedetto, & A. L. Sangiovanni-Vincentelli (Eds.), Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings (pp. 147-161). (Lecture Notes in Computer Science; Vol. 2034). Springer. https://doi.org/10.1007/3-540-45351-2_15

Behrmann, Gerd ; Fehnker, Ansgar ; Hune, Thomas et al. / Minimum-Cost Reachability for Priced Timed Automata. Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings. editor / Maria Domenica Di Benedetto ; Alberto L. Sangiovanni-Vincentelli. Berlin, Heidelberg : Springer, 2001. pp. 147-161 (Lecture Notes in Computer Science).

@inproceedings{a7c80d63a6ff43a18cd90225c122ddee,

title = "Minimum-Cost Reachability for Priced Timed Automata",

abstract = "This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques and a new notion of priced regions. The latter allows symbolic representation and manipulation of reachable states together with the cost of reaching them.",

keywords = "n/a OA procedure",

author = "Gerd Behrmann and Ansgar Fehnker and Thomas Hune and Kim Larsen and Paul Pettersson and Judi Romijn and Vaandrager, \{Frits W.\}",

year = "2001",

doi = "10.1007/3-540-45351-2\_15",

language = "English",

isbn = "978-3-540-41866-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "147--161",

editor = "Benedetto, \{Maria Domenica Di\} and Sangiovanni-Vincentelli, \{Alberto L.\}",

booktitle = "Hybrid Systems: Computation and Control",

address = "Germany",

note = "4th International Workshop on Hybrid Systems: Computation and Control 2001, HSCC 2001 ; Conference date: 28-03-2001 Through 30-03-2001",

}

Behrmann, G, Fehnker, A, Hune, T, Larsen, K, Pettersson, P, Romijn, J & Vaandrager, FW 2001, Minimum-Cost Reachability for Priced Timed Automata. in MDD Benedetto & AL Sangiovanni-Vincentelli (eds), Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2034, Springer, Berlin, Heidelberg, pp. 147-161, 4th International Workshop on Hybrid Systems: Computation and Control 2001, Rome, Italy, 28/03/01. https://doi.org/10.1007/3-540-45351-2_15

Minimum-Cost Reachability for Priced Timed Automata. / Behrmann, Gerd; Fehnker, Ansgar; Hune, Thomas et al.
Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings. ed. / Maria Domenica Di Benedetto; Alberto L. Sangiovanni-Vincentelli. Berlin, Heidelberg: Springer, 2001. p. 147-161 (Lecture Notes in Computer Science; Vol. 2034).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Minimum-Cost Reachability for Priced Timed Automata

AU - Behrmann, Gerd

AU - Fehnker, Ansgar

AU - Hune, Thomas

AU - Larsen, Kim

AU - Pettersson, Paul

AU - Romijn, Judi

AU - Vaandrager, Frits W.

N1 - Conference code: 4

PY - 2001

Y1 - 2001

N2 - This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques and a new notion of priced regions. The latter allows symbolic representation and manipulation of reachable states together with the cost of reaching them.

AB - This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques and a new notion of priced regions. The latter allows symbolic representation and manipulation of reachable states together with the cost of reaching them.

KW - n/a OA procedure

U2 - 10.1007/3-540-45351-2_15

DO - 10.1007/3-540-45351-2_15

M3 - Conference contribution

SN - 978-3-540-41866-5

T3 - Lecture Notes in Computer Science

SP - 147

EP - 161

BT - Hybrid Systems: Computation and Control

A2 - Benedetto, Maria Domenica Di

A2 - Sangiovanni-Vincentelli, Alberto L.

PB - Springer

CY - Berlin, Heidelberg

T2 - 4th International Workshop on Hybrid Systems: Computation and Control 2001

Y2 - 28 March 2001 through 30 March 2001

ER -

Behrmann G, Fehnker A, Hune T, Larsen K, Pettersson P, Romijn J et al. Minimum-Cost Reachability for Priced Timed Automata. In Benedetto MDD, Sangiovanni-Vincentelli AL, editors, Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings. Berlin, Heidelberg: Springer. 2001. p. 147-161. (Lecture Notes in Computer Science). doi: 10.1007/3-540-45351-2_15

Minimum-Cost Reachability for Priced Timed Automata

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this