Uniform scattering of autonomous mobile robots in a grid
Uniform scattering of autonomous mobile robots in a grid
复制标题
网格中自主移动机器人的均匀分散
DOI：
10.1142/s0129054111008295
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
N. Santoro
中科院分区：
文献类型：
--
作者：
Lali Barrière;P. Flocchini;Eduardo Mesa Barrameda;N. Santoro
我们考虑一组部署在网格网络中的自主移动的机器人的均匀散射问题：从网格中的任意位置开始，使用纯粹的本地化计算，机器人必须移动，以便在有限时间内达到静态平衡的状态，它们均匀地覆盖网格。理论上的探索是确定机器人解决问题所需的最小能力。我们证明了均匀散射确实是可能的，即使是非常弱的机器人。证据是建设性的。我们提出了一个可证明是正确的协议，统一的自我部署在网格中。该协议是完全本地化的，无冲突的，并且它做了最少的假设;特别是：（1）它不需要机器人之间的任何直接或显式通信;（2）它不假设机器人同步或定时，因此机器人可以在它们的所有动作中完全异步;（3）它只需要有限的可见范围;（4）它在每个机器人处仅使用恒定大小的存储器，因此在计算上机器人可以是简单的随机状态机;（5）它不需要全局定位系统，而仅需要网格中的定向（例如，指南针）;（6）它不需要标识符，因此机器人可以是匿名的并且完全相同。
We consider the uniform scattering problem for a set of autonomous mobile robots deployed in a grid network: starting from an arbitrary placement in the grid, using purely localized computations, the robots must move so to reach in finite time a state of static equilibrium in which they cover uniformly the grid. The theoretical quest is on determining the minimal capabilities needed by the robots to solve the problem. We prove that uniform scattering is indeed possible even for very weak robots. The proof is constructive. We present a provably correct protocol for uniform self-deployment in a grid. The protocol is fully localized, collision-free, and it makes minimal assumptions; in particular: (1) it does not require any direct or explicit communication between robots; (2) it makes no assumption on robots synchronization or timing, hence the robots can be fully asynchronous in all their actions; (3) it requires only a limited visibility range; (4) it uses at each robot only a constant size memory, hence computationally the robots can be simple Finite-State Machines; (5) it does not need a global localization system but only orientation in the grid (e.g., a compass); (6) it does not require identifiers, hence the robots can be anonymous and totally identical.