On the optimal reachability problem in weighted timed games

Patricia Bouyer-Decitre
LSV, CNRS & ENS de Cachan
Friday, 20 March, 2015 - 14:00
NO Solvay (5th floor)
A weighted timed game is a timed game with extra quantitative information representing e.g. energy consumption. Optimizing the weight for reaching a target is a natural question, which has been investigated for ten years. Existence of optimal strategies is known to be undecidable in general, and only very restricted classes of games have been described for which optimal weight and almost-optimal strategies can be computed. In this talk, I will give an overview of rather old results about the optimal reachability problem in weighted timed automata and games. I will then focus on more recent results, that are joint work with Samy Jaziri and Nicolas Markey. First I will show that the value problem is undecidable in weighted timed games. I will then describe an algorithm to compute arbitrary approximations of the value in a game, and corresponding almost-optimal strategies. The algorithm applies to a large subclass of weighted timed games, and is the first approximation scheme which is designed in the current context.