Patrolling Grids with a Bit of Memory
share
We study the following problem in elementary robotics: can a mobile agent with b bits of memory, which is able to sense only locations at Manhattan distance V or less from itself, patrol a d-dimensional grid graph? We show that it is impossible to patrol some grid graphs with 0 bits of memory, regardless of V, and give an exact characterization of those grid graphs that can be patrolled with 0 bits of memory and visibility range V. On the other hand, we show that, surprisingly, an algorithm exists using 1 bit of memory and V=1 that patrols any d-dimensional grid graph.
READ FULL TEXT