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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Patrolling Grids with a Bit of Memory

  • Michael Amir,
  • Dmitry Rabinovich,
  • Alfred M. Bruckstein

摘要

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.