Résumé
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,. . .).