Playing Stochastically in Weighted Timed Games to Emulate Memory - MOVE Modélisation et Vérification - LIS Laboratoire d'Informatique et Systèmes de Marseille (UMR 7020) Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Playing Stochastically in Weighted Timed Games to Emulate Memory

Résumé

Weighted timed games are two-player zero-sum games played in a timed automaton equipped with integer weights. We consider optimal reachability objectives, in which one of the players, that we call Min, wants to reach a target location while minimising the cumulated weight. While knowing if Min has a strategy to guarantee a value lower than a given threshold is known to be undecidable (with two or more clocks), several conditions, one of them being the divergence, have been given to recover decidability. In such weighted timed games (like in untimed weighted games in the presence of negative weights), Min may need finite memory to play (close to) optimally. This is thus tempting to try to emulate this finite memory with other strategic capabilities. In this work, we allow the players to use stochastic decisions, both in the choice of transitions and of timing delays. We give for the first time a definition of the expected value in weighted timed games, overcoming several theoretical challenges. We then show that, in divergent weighted timed games, the stochastic value is indeed equal to the classical (deterministic) value, thus proving that Min can guarantee the same value while only using stochastic choices, and no memory.
Fichier principal
Vignette du fichier
LIPIcs-ICALP-2021-137.pdf (840.23 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-03282049 , version 1 (08-07-2021)

Identifiants

Citer

Benjamin Monmege, Julie Parreaux, Pierre-Alain Reynier. Playing Stochastically in Weighted Timed Games to Emulate Memory. 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Jul 2021, Glasgow (virtual), United Kingdom. ⟨10.4230/LIPIcs.ICALP.2021.137⟩. ⟨hal-03282049⟩
60 Consultations
15 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More