Patrolling Grids with a Bit of Memory

Patrolling is a key problem in robotics wherein a mobile agent or team of mobile agents are tasked with repeatedly visiting every vertex of a graph environment by traversing edges. This task has well-known applications to navigation, web crawling, and swarm intelligence [19]. Patrolling has been studied under diverse sets of assumptions regarding e.g. the number of agents, the capabilities of each agent, and the underlying graph environment [22]. A central question related to patrolling is the space complexity of patrolling an environment: the amount of memory required by the agent(s) to patrol the environment [5, 8, 11, 13, 15, 18, 22]. The simplest kind of environment that is interesting to patrol is perhaps the grid graph. Hence, the goal of this work is to establish the space complexity of patrolling d-dimensional grid graphs with a single mobile agent that has limited visibility. More concretely, suppose a mobile agent with fixed orientation, R, is placed somewhere inside a grid graph. We assume R has b bits of internal state memory and the ability to see locations at Manhattan distance V or less from itself (see Figure 1), and must act based only on this information, i.e., it is a finite automaton. For what values of b and V does there exist an algorithm that enables R to patrol the grid?