Gathering six oblivious robots on anonymous symmetric rings
Gathering six oblivious robots on anonymous symmetric rings
复制标题
在匿名对称环上聚集六个不经意的机器人
DOI：
10.1016/j.jda.2013.09.006
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Navarra
中科院分区：
文献类型：
--
作者：
Gianlorenzo D'angelo;G. Stefano;A. Navarra
基于机器人的计算系统的最新模型使用放置在匿名图的节点上的相同的、无记忆的和移动的机器人。机器人在Look-Compute-Move循环中运行;在一个循环中，机器人对整个环上的当前机器人进行快照（Look），决定是否保持空闲或移动到其相邻节点之一（Compute），并在后一种情况下移动到该邻居（Move）。周期异步执行每个robots.We考虑的情况下，六个机器人放置在一个匿名环的节点上，以这样的方式，他们构成一个对称的位置相对于一个单一的对称轴，我们问是否存在一个策略，允许机器人聚集在一个节点。这是在一系列关于在匿名戒指上收集遗忘机器人的论文之后留下的第一个案例。只要收集是可行的，我们提供了一个新的分布式方法，保证一个积极的回答所提出的问题。
A recent model for robot-based computing systems makes use of identical, memoryless, and mobile robots placed on nodes of anonymous graphs. Robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current robots disposal on the entire ring (Look), takes a decision whether to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes a move to this neighbor (Move). Cycles are performed asynchronously for each robot.We consider the case of six robots placed on the nodes of an anonymous ring in such a way they constitute a symmetric placement with respect to one single axis of symmetry, and we ask whether there exists a strategy that allows the robots to gather at one node. This is the first case left open after a series of papers dealing with the gathering of oblivious robots on anonymous rings. As long as the gathering is feasible, we provide a new distributed approach that guarantees a positive answer to the posed question.