A faster algorithm for solving one-clock priced timed games

DOI10.1007/978-3-642-40184-8_37MaRDI QIDQ2842131zbMATH OpenOpenAlexFDO

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

Publication date 12 August 2013

Published in CONCUR 2013 – Concurrency Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.3498

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Games involving graphs (91A43) Applications of game theory (91A80)

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 2^(O(n^2+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.

Recommendations

• Simple priced timed games are not that simple
• Almost Optimal Strategies in One Clock Priced Timed Games
• Two-player reachability-price games on single-clock timed automata
• Adding negative prices to priced timed games
• Reachability-Time Games on Timed Automata

Cited in

(14)

• Timed network games
• Optimal reachability in divergent weighted timed games
• Model Checking Real-Time Systems
• Efficient On-the-Fly Algorithms for Partially Observable Timed Games
• Timed network games with clocks
• Symbolic Approximation of Weighted Timed Games
• One-clock priced timed games with negative weights
• Simple priced timed games are not that simple
• Almost Optimal Strategies in One Clock Priced Timed Games
• Timed Basic Parallel Processes
• CONCUR 2005 – Concurrency Theory
• Optimal controller synthesis for timed systems
• Inaproximability in weighted timed games
• Decidability of one-clock weighted timed games with arbitrary weights

This page was built for publication: A faster algorithm for solving one-clock priced timed games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842131)