Randolph's Robot Game is NP-complete!

摘要

We introduce a new type of movement constraints for a swarm of robots in a grid environment. This type is inspired by Alex Randolphs board game Ricochet Robot and may be used to model robots with very limited abilities for self localization: We assume that once a robot starts to drive in a certain direction, it does not stop its movement until it hits an obstacle wall or another robot. We show that the question, whether a given cell can be reached is NP-complete for arbitrary environments. A Java