Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Reachability games with relaxed energy constraints

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 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, i.e., when the upper bound is reached, the extra energy is not 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 coNP in the two-player setting. Allowing for bounded violations makes the problem PSPACE-complete for one-player arenas and EXPTIME-complete for two players. We then address the problem of existence of bounds for a given arena. We show that with reachability objectives, existence can be a simpler problem than the game itself, and conversely that with infinite games, existence can be harder.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/hal-02964729
Contributor : Loic Helouet <>
Submitted on : Monday, October 12, 2020 - 4:26:06 PM
Last modification on : Thursday, October 15, 2020 - 3:35:29 AM

File

meangames.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02964729, version 1

Citation

Loïc Hélouët, Nicolas Markey, Ritam Raha. Reachability games with relaxed energy constraints. 2020. ⟨hal-02964729⟩

Share

Metrics

Record views

6

Files downloads

24