A Faster Algorithm for Solving One-Clock Priced Timed Games

Thomas Dueholm Hansen; Rasmus Ibsen-Jensen; Peter Bro Miltersen

doi:10.1007/978-3-642-40184-8_37

A Faster Algorithm for Solving One-Clock Priced Timed Games

Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Abstract

One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that one-clock priced timed games can be solved in time m 12 n n O(1), where n is the number of states and m is the number of actions. The best previously known time bound for solving one-clock priced timed games was 2O(n2+m) , due to Rutkowski. For our improvement, we introduce and study a new algorithm for solving one-clock priced timed games, based on the sweep-line technique from computational geometry and the strategy iteration paradigm from the algorithmic theory of Markov decision processes. As a corollary, we also improve the analysis of previous algorithms due to Bouyer, Cassez, Fleury, and Larsen; and Alur, Bernadsky, and Madhusudan.

Original language	English
Title of host publication	CONCUR 2013 – Concurrency Theory : 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings
Editors	Pedro R. D*Argenio, Hernán Melgratti
Number of pages	15
Publisher	Springer VS
Publication date	2013
Pages	531-545
ISBN (Print)	978-3-642-40183-1
ISBN (Electronic)	978-3-642-40184-8
DOIs	https://doi.org/10.1007/978-3-642-40184-8_37
Publication status	Published - 2013
Event	International Conference on Currency Theory - Buenos Aires, Argentina Duration: 27 Aug 2013 → 30 Aug 2013 Conference number: 24

Conference

Conference	International Conference on Currency Theory
Number	24
Country/Territory	Argentina
City	Buenos Aires
Period	27/08/2013 → 30/08/2013

Series	Lecture Notes in Computer Science
Volume	8052
ISSN	0302-9743

Access to Document

10.1007/978-3-642-40184-8_37

http://link.springer.com/chapter/10.1007%2F978-3-642-40184-8_37

Cite this

Hansen, T. D., Ibsen-Jensen, R., & Miltersen, P. B. (2013). A Faster Algorithm for Solving One-Clock Priced Timed Games. In P. R. D*Argenio, & H. Melgratti (Eds.), CONCUR 2013 – Concurrency Theory: 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings (pp. 531-545). Springer VS. https://doi.org/10.1007/978-3-642-40184-8_37

Hansen, Thomas Dueholm ; Ibsen-Jensen, Rasmus ; Miltersen, Peter Bro. / A Faster Algorithm for Solving One-Clock Priced Timed Games. CONCUR 2013 – Concurrency Theory: 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings. editor / Pedro R. D*Argenio ; Hernán Melgratti. Springer VS, 2013. pp. 531-545 (Lecture Notes in Computer Science, Vol. 8052).

@inproceedings{ab83b7f5599d4d9da15fb3f69da27f0e,

title = "A Faster Algorithm for Solving One-Clock Priced Timed Games",

abstract = "One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that one-clock priced timed games can be solved in time m 12 n n O(1), where n is the number of states and m is the number of actions. The best previously known time bound for solving one-clock priced timed games was 2O(n2+m) , due to Rutkowski. For our improvement, we introduce and study a new algorithm for solving one-clock priced timed games, based on the sweep-line technique from computational geometry and the strategy iteration paradigm from the algorithmic theory of Markov decision processes. As a corollary, we also improve the analysis of previous algorithms due to Bouyer, Cassez, Fleury, and Larsen; and Alur, Bernadsky, and Madhusudan.",

author = "Hansen, {Thomas Dueholm} and Rasmus Ibsen-Jensen and Miltersen, {Peter Bro}",

year = "2013",

doi = "10.1007/978-3-642-40184-8_37",

language = "English",

isbn = "978-3-642-40183-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer VS",

pages = "531--545",

editor = "D*Argenio, {Pedro R.} and Hern{\'a}n Melgratti",

booktitle = "CONCUR 2013 – Concurrency Theory",

note = "International Conference on Currency Theory ; Conference date: 27-08-2013 Through 30-08-2013",

}

Hansen, TD, Ibsen-Jensen, R & Miltersen, PB 2013, A Faster Algorithm for Solving One-Clock Priced Timed Games. in PR D*Argenio & H Melgratti (eds), CONCUR 2013 – Concurrency Theory: 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings. Springer VS, Lecture Notes in Computer Science, vol. 8052, pp. 531-545, International Conference on Currency Theory, Buenos Aires, Argentina, 27/08/2013. https://doi.org/10.1007/978-3-642-40184-8_37

A Faster Algorithm for Solving One-Clock Priced Timed Games. / Hansen, Thomas Dueholm; Ibsen-Jensen, Rasmus; Miltersen, Peter Bro.
CONCUR 2013 – Concurrency Theory: 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings. ed. / Pedro R. D*Argenio; Hernán Melgratti. Springer VS, 2013. p. 531-545 (Lecture Notes in Computer Science, Vol. 8052).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - A Faster Algorithm for Solving One-Clock Priced Timed Games

AU - Hansen, Thomas Dueholm

AU - Ibsen-Jensen, Rasmus

AU - Miltersen, Peter Bro

N1 - Conference code: 24

PY - 2013

Y1 - 2013

N2 - One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that one-clock priced timed games can be solved in time m 12 n n O(1), where n is the number of states and m is the number of actions. The best previously known time bound for solving one-clock priced timed games was 2O(n2+m) , due to Rutkowski. For our improvement, we introduce and study a new algorithm for solving one-clock priced timed games, based on the sweep-line technique from computational geometry and the strategy iteration paradigm from the algorithmic theory of Markov decision processes. As a corollary, we also improve the analysis of previous algorithms due to Bouyer, Cassez, Fleury, and Larsen; and Alur, Bernadsky, and Madhusudan.

AB - One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that one-clock priced timed games can be solved in time m 12 n n O(1), where n is the number of states and m is the number of actions. The best previously known time bound for solving one-clock priced timed games was 2O(n2+m) , due to Rutkowski. For our improvement, we introduce and study a new algorithm for solving one-clock priced timed games, based on the sweep-line technique from computational geometry and the strategy iteration paradigm from the algorithmic theory of Markov decision processes. As a corollary, we also improve the analysis of previous algorithms due to Bouyer, Cassez, Fleury, and Larsen; and Alur, Bernadsky, and Madhusudan.

U2 - 10.1007/978-3-642-40184-8_37

DO - 10.1007/978-3-642-40184-8_37

M3 - Article in proceedings

SN - 978-3-642-40183-1

T3 - Lecture Notes in Computer Science

SP - 531

EP - 545

BT - CONCUR 2013 – Concurrency Theory

A2 - DArgenio, Pedro R.

A2 - Melgratti, Hernán

PB - Springer VS

T2 - International Conference on Currency Theory

Y2 - 27 August 2013 through 30 August 2013

ER -

Hansen TD, Ibsen-Jensen R, Miltersen PB. A Faster Algorithm for Solving One-Clock Priced Timed Games. In D*Argenio PR, Melgratti H, editors, CONCUR 2013 – Concurrency Theory: 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings. Springer VS. 2013. p. 531-545. (Lecture Notes in Computer Science, Vol. 8052). doi: 10.1007/978-3-642-40184-8_37