Ricochet Robots game: complexity analysis Technical Report

Abstract : This paper investigates the Ricochet Robots game problem from a complexity standpoint. The problem consists in moving robots in a grid game board in horizontal or vertical direction only, to reach specific target tiles. Once a robot starts moving in a direction, it cannot be stopped until being blocked by a wall or another robot. We show that the optimization problem corresponding to this game is Poly-APX-hard. We also show that the decision problem is PSPACE-complete when we consider an arbitrary number of robots. In such a context, several lower bounds are introduced, exploring some classic complexity hypothesis (P = N P, ET H,. . .).
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02191102
Contributor : Samuel Masseport <>
Submitted on : Tuesday, July 23, 2019 - 11:59:26 AM
Last modification on : Wednesday, July 24, 2019 - 1:23:20 AM

File

Ricochet_Robots_complexity_ana...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02191102, version 1

Collections

Citation

Samuel Masseport, Benoit Darties, Rodolphe Giroudeau, Jorick Lartigau. Ricochet Robots game: complexity analysis Technical Report. 2019. ⟨hal-02191102⟩

Share

Metrics

Record views

30

Files downloads

42