Document Open Access Logo

Simple Priced Timed Games are not That Simple

Authors Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Engel Lefaucheux, Benjamin Monmege

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.278.pdf
  • Filesize: 0.63 MB
  • 15 pages

Document Identifiers

Author Details

Thomas Brihaye
Gilles Geeraerts
Axel Haddad
Engel Lefaucheux
Benjamin Monmege

Cite As Get BibTex

Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Engel Lefaucheux, and Benjamin Monmege. Simple Priced Timed Games are not That Simple. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 278-292, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.FSTTCS.2015.278

Abstract

Priced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modeling the costs of spending time in a state and executing an action, respectively). The goals of the players are to minimise and maximise the cost to reach a target location, respectively. We consider priced timed games with one clock and arbitrary (positive and negative) weights and show that, for an important subclass of theirs (the so-called simple priced timed games), one can compute, in exponential time, the optimal values that the players can achieve, with their associated optimal strategies. As side results, we also show that one-clock priced timed games are determined and that we can use our result on simple priced timed games to solve the more general class of so-called reset-acyclic priced timed games (with arbitrary weights and one-clock).

Subject Classification

Keywords
  • Priced timed games
  • real-time systems
  • game theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rajeev Alur, Mikhail Bernadsky, and P. Madhusudan. Optimal reachability for weighted timed games. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04), volume 3142 of Lecture Notes in Computer Science, pages 122-133. Springer, 2004. Google Scholar
  2. Rajeev Alur and David L. Dill. A theory of timed automata. Theoretical Computer Science, 126(2):183-235, 1994. Google Scholar
  3. Rajeev Alur, Salvatore La Torre, and George J. Pappas. Optimal paths in weighted timed automata. Theoretical Computer Science, 318(3):297-322, 2004. Google Scholar
  4. Gerd Behrmann, Ansgar Fehnker, Thomas Hune, Kim G. Larsen, Judi Romijn, and Frits W. Vaandrager. Minimum-cost reachability for priced timed automata. In Proceedings of the 4th International Workshop on Hybrid Systems: Computation and Control (HSCC'01), volume 2034 of Lecture Notes in Computer Science, pages 147-161. Springer, 2001. Google Scholar
  5. J. Berendsen, T. Chen, and D. Jansen. Undecidability of cost-bounded reachability in priced probabilistic timed automata. In Theory and Applications of Models of Computation, volume 5532 of LNCS, pages 128-137. Springer, 2009. Google Scholar
  6. Patricia Bouyer, Thomas Brihaye, Véronique Bruyère, and Jean-François Raskin. On the optimal reachability problem of weighted timed automata. Formal Methods in System Design, 31(2):135-175, 2007. Google Scholar
  7. Patricia Bouyer, Thomas Brihaye, and Nicolas Markey. Improved undecidability results on weighted timed automata. Information Processing Letters, 98(5):188-194, 2006. Google Scholar
  8. Patricia Bouyer, Franck Cassez, Emmanuel Fleury, and Kim G. Larsen. Optimal strategies in priced timed game automata. In Proceedings of the 24th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'04), volume 3328 of Lecture Notes in Computer Science, pages 148-160. Springer, 2004. Google Scholar
  9. Patricia Bouyer, Samy Jaziri, and Nicolas Markey. On the value problem in weighted timed games. Research Report LSV-14-12, Laboratoire Spécification et Vérification, ENS Cachan, France, October 2014. 24 pages. Google Scholar
  10. Patricia Bouyer, Kim G. Larsen, Nicolas Markey, and Jacob Illum Rasmussen. Almost optimal strategies in one-clock priced timed games. In Proceedings of the 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'06), volume 4337 of Lecture Notes in Computer Science, pages 345-356. Springer, 2006. Google Scholar
  11. Thomas Brihaye, Véronique Bruyère, and Jean-François Raskin. On optimal timed strategies. In Proceedings of the Third international conference on Formal Modeling and Analysis of Timed Systems (FORMATS'05), volume 3829 of Lecture Notes in Computer Science, pages 49-64. Springer, 2005. Google Scholar
  12. Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Engel Lefaucheux, and Benjamin Monmege. Simple priced timed games are not that simple. Research Report 1507.03786, arXiv, July 2015. Google Scholar
  13. Thomas Brihaye, Gilles Geeraerts, Axel Haddad, and Benjamin Monmege. To reach or not to reach? Efficient algorithms for total-payoff games. In Luca Aceto and David de Frutos Escrig, editors, Proceedings of the 26th International Conference on Concurrency Theory (CONCUR'15), volume 42 of LIPIcs, pages 297-310. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, September 2015. Google Scholar
  14. Thomas Brihaye, Gilles Geeraerts, Shankara Narayanan Krishna, Lakshmi Manasa, Benjamin Monmege, and Ashutosh Trivedi. Adding Negative Prices to Priced Timed Games. In Proceedings of the 25th International Conference on Concurrency Theory (CONCUR'13), volume 8704 of Lecture Notes in Computer Science, pages 560-575. Springer, 2014. Google Scholar
  15. D. Gale and F. M. Stewart. Infinite games with perfect information. In Contributions to the theory of games, vol. 2. Annals of Mathematical Studies, volume 28 of Lecture Notes in Computer Science, pages 245-266. Princeton University Press., 1953. Google Scholar
  16. Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, and Peter Bro Miltersen. A faster algorithm for solving one-clock priced timed games. In Proceedings of the 24th International Conference on Concurrency Theory (CONCUR'13), volume 8052 of Lecture Notes in Computer Science, pages 531-545. Springer, 2013. Google Scholar
  17. Peter J. Ramadge and W. Murray Wonham. The control of discrete event systems. In Proceedings of the IEEE, volume 77(1), pages 81-98, 1989. Google Scholar
  18. Michał Rutkowski. Two-player reachability-price games on single-clock timed automata. In Proceedings of the 9th Workshop on Quantitative Aspects of Programming Languages (QAPL'11), volume 57 of Electronic Proceedings in Theoretical Computer Science, pages 31-46, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact