Open AccessEnergy and mean-payoff timed games
Author(s) -
Romain Brenguier,
Franck Cassez,
Jean-François Raskin
Publication year - 2014
Publication title -
hal (le centre pour la communication scientifique directe)
Language(s) - English
Resource type - Conference proceedings
DOI - 10.1145/2562059.2562116
Subject(s) - undecidable problem , computer science , stochastic game , relation (database) , energy (signal processing) , class (philosophy) , turns, rounds and time keeping systems in games , mathematical optimization , theoretical computer science , mathematical economics , artificial intelligence , game mechanics , mathematics , video game design , decidability , data mining , statistics
In this paper, we study energy and mean-payoff timed games. The decision problems that consist in determining the existence of winning strategies in those games are undecidable, and we thus provide semi-algorithms for solving these strategy synthesis problems. We then identify a large class of timed games for which our semi-algorithms terminate and are thus complete. We also study in detail the relation between mean-payoff and energy timed games. Finally, we provide a symbolic algorithm to solve energy timed games and demonstrate its use on small examples using HyTech.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom