  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 that 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 highly regular environments
like grid graphs compared to arbitrary graphs. The techniques we use, such as
partitioning the environment into sensing regions and exploiting distinct
coordinates resulting from higher-dimensionality, may be applicable to
analyzing the space complexity of patrolling in other types of regular
environments as well.
