Distributed Computing by Mobile Robots: Gathering
Distributed Computing by Mobile Robots: Gathering
复制标题
移动机器人的分布式计算：采集
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
N. Santoro
中科院分区：
文献类型：
--
作者：
Mark Cieliebak;P. Flocchini;G. Prencipe;N. Santoro
考虑平面上一组 $n>2$ 相同的移动计算实体，称为机器人，以“查看-计算-移动”周期运行，没有任何直接通信方式。聚集问题是所有实体在有限时间内在未提前固定的点聚集的原始任务，没有任何外部控制。在各种强有力的假设（例如，周期的同步性、瞬时运动、过去的完整记忆、共同坐标系等）下，文献中对该问题进行了广泛的研究。在本文中，我们考虑没有这些假设的设置，即当实体健忘（即，它们不记得先前周期的结果和观察）、迷失方向（即，没有共同的坐标系）和完全异步（即，对周期的时间安排和周期内的活动不存在假设）时。此类机器人的现有算法贡献仅限于 $n \leq 4$ 的解决方案或有限的初始配置集...
Consider a set of $n>2$ identical mobile computational entities in the plane, called robots, operating in Look-Compute-Move cycles, without any means of direct communication. The Gathering Problem is the primitive task of all entities gathering in finite time at a point not fixed in advance, without any external control. The problem has been extensively studied in the literature under a variety of strong assumptions (e.g., synchronicity of the cycles, instantaneous movements, complete memory of the past, common coordinate system, etc.). In this paper we consider the setting without those assumptions, that is, when the entities are oblivious (i.e., they do not remember results and observations from previous cycles), disoriented (i.e., have no common coordinate system), and fully asynchronous (i.e., no assumptions exist on timing of cycles and activities within a cycle). The existing algorithmic contributions for such robots are limited to solutions for $n \leq 4$ or for restricted sets of initial configura...