We consider a swarm of mobile robots evolving in a bidimensional Euclidean space. We study a variant of the crash-tolerant gathering problem: if no robot crashes, robots have to meet at the same arbitrary location, not known beforehand, in finite time; if one or several robots crash at the same location, the remaining correct robots gather at the crash location to rescue them. Motivated by impossibility results in the semi-synchronous setting, we present the first solution to the problem for the fully synchronous setting that operates in the vanilla Look-Compute-Move model with no additional hypotheses: robots are oblivious, disoriented, have no multiplicity detection capacity, and may start from arbitrary positions (including those with multiplicity points). We furthermore show that robots gather in a time that is proportional to the initial maximum distance between robots.
翻译:我们认为,在二维的欧几里德空间里,流动机器人成群而演。我们研究了一个不发生机器人撞车事件的问题:如果不发生机器人撞车事件,机器人必须在同一任意地点相遇,这是事先不知道的,时间有限;如果一个或数个机器人在同一地点坠车,其余的正确机器人会聚集在坠机地点,以救援他们。由于不可能的结果,在半同步的环境下,我们为在香草 Look-Compute-Move模型中运行的完全同步的设置提出了第一个解决方案,没有附加假设:机器人是模糊的,方向不明的,没有多重的检测能力,并且可能从任意位置(包括多点的机器人)开始。我们进一步表明,机器人聚集的时间与机器人之间的最初最大距离成正比。