Nicolas Markey

Résumé

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 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. 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.

@article{icomp2022-HMR,
  author =              {H{\'e}lou{\"e}t, Lo{\"\i}c and Markey, Nicolas and
                         Raha, Ritam},
  title =               {Reachability games with relaxed energy constraints},
  publisher =           {Elsevier},
  journal =             {Information and Computation},
  volume =              {285~(Part~B)},
  year =                {2022},
  month =               may,
  doi =                 {10.1016/j.ic.2021.104806},
  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.
                         \par 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 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. 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.},
}