License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2015.261
URN: urn:nbn:de:0030-drops-56440
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5644/
Go to the corresponding LIPIcs Volume Portal

Guha, Shibashis ; Krishna, Shankara Narayanan ; Manasa, Lakshmi ; Trivedi, Ashutosh

Revisiting Robustness in Priced Timed Games

pdf-format:
29.pdf (0.7 MB)

Abstract

Priced timed games are optimal-cost reachability games played between
two players---the controller and the environment---by moving a token along the edges of infinite graphs of configurations of priced timed automata. The goal of the controller is to reach a given set of target locations as cheaply as possible, while the goal of the environment is the opposite. Priced timed games are known to be undecidable for timed automata with 3 or more clocks, while they are known to be decidable for automata with 1 clock. In an attempt to recover decidability for priced timed games Bouyer, Markey, and Sankur studied robust priced timed games where the environment has the power to slightly perturb delays proposed by the controller.
Unfortunately, however, they showed that the natural problem of deciding the existence of optimal limit-strategy---optimal strategy of the controller where the perturbations tend to vanish in the limit---is undecidable with 10 or more clocks. In this paper we revisit this problem and improve our understanding of the decidability of these games. We show that the limit-strategy problem is already undecidable for a subclass of robust priced timed games with 5 or more clocks. On a positive side, we show the decidability of the existence of almost optimal strategies for the same subclass of one-clock robust priced timed games by adapting a classical construction by Bouyer at al. for one-clock priced timed games.

BibTeX - Entry

@InProceedings{guha_et_al:LIPIcs:2015:5644,
  author =	{Shibashis Guha and Shankara Narayanan Krishna and Lakshmi Manasa and Ashutosh Trivedi},
  title =	{{Revisiting Robustness in Priced Timed Games }},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{261--277},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Prahladh Harsha and G. Ramalingam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5644},
  URN =		{urn:nbn:de:0030-drops-56440},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.261},
  annote =	{Keywords: Priced Timed Games, Decidability, Optimal strategies, Robustness}
}

Keywords: Priced Timed Games, Decidability, Optimal strategies, Robustness
Collection: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Issue Date: 2015
Date of publication: 14.12.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI