Patrolling Grids with a Bit of Memory
摘要
This work addresses the challenge of patrolling regular grid graphs of any dimension using a single mobile agent with minimal memory and limited sensing range. We show it is impossible to patrol some grid graphs with 0 bits of memory, regardless of sensing range, and give an exact characterization of those grid graphs that can be patrolled with 0 bits of memory and sensing range V. On the other hand, we show that an algorithm exists using 1 bit of memory and \(V=1\) that patrols any d-dimensional grid graph. This result is surprising given that the agent must be able to move in 2d distinct directions to patrol, while 1 bit of memory allows specifying only two directions per sensory input. Our 1-bit patrolling algorithm handles this by carefully exploiting a small state-space to access all the needed directions while avoiding getting stuck. Overall, our results give concrete evidence that extremely little memory is needed for patrolling high-dimensional regular environments.