Skip to Main content Skip to Navigation
Conference papers

Reachability Games with Relaxed Energy Constraints

Loïc Hélouët 1 Nicolas Markey 1 Ritam Raha 2, 1 
1 SUMO - SUpervision of large MOdular and distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : We study games with reachability objectives under energy constraints. We first prove that under strict energy constraints (either only lower-bound constraint or interval constraint), those games are LOGSPACE-equivalent to energy games with the same energy constraints but without reachability objective (i.e., for infinite runs). We then consider two kinds of relaxations of the upper-bound constraints (while keeping the lower-bound constraint strict): in the first one, called weak upper bound, the upper bound is absorbing, in the sense that it allows receiving more energy when the upper bound is already reached, but the extra energy will not be stored; in the second one, we allow for temporary violations of the upper bound, imposing limits on the number or on the amount of violations. We prove that when considering weak upper bound, reachability objectives require memory, but can still be solved in polynomial-time for one-player arenas; we prove that they are in co-NP in the two-player setting. Allowing for bounded violations makes the problem PSPACE-complete for one-player arenas and EXPTIME-complete for two players.
Document type :
Conference papers
Complete list of metadata
Contributor : Nicolas Markey Connect in order to contact the contributor
Submitted on : Wednesday, September 18, 2019 - 2:43:25 PM
Last modification on : Monday, April 4, 2022 - 9:28:23 AM

Links full text



Loïc Hélouët, Nicolas Markey, Ritam Raha. Reachability Games with Relaxed Energy Constraints. GandALF 2019 - Tenth International Symposium on Games, Automata, Logics, and Formal Verification, Sep 2019, Bordeaux, France. pp.17-33, ⟨10.4204/EPTCS.305.2⟩. ⟨hal-02291241⟩



Record views