Asynchronous Gathering Algorithms for Autonomous Mobile Robots with Lights
Asynchronous Gathering Algorithms for Autonomous Mobile Robots with Lights
复制标题
带灯自主移动机器人的异步采集算法
DOI：
10.1007/978-3-030-91081-5_27
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
K. Wada
中科院分区：
文献类型：
--
作者：
R. Nakai;Y. Sudo;K. Wada
我们考虑异步调度程序（ASYNC）中具有称为光的持久内存的自主移动机器人的收集问题。众所周知，如果系统是半同步 (SSYNC) 甚至集中式（每次只有一个机器人处于活动状态），则基本标准模型中的机器人没有灯光时，聚集是不可能的。据了解，机器人可以在ASYNC中用10种颜色的灯光来解决Gathering。该结果是通过组合以下结果而获得的。 （1）具有 5k 颜色的 ASYNC 机器人对具有 k 颜色的 SSYNC 机器人的模拟[7]，以及（2）具有 2 种颜色的 SSYNC 机器人解决了聚集问题[28]。在本文中，我们通过减少颜色数量来改进结果，并表明具有 3 种颜色灯光的 ASYNC 机器人可以解决聚集问题。我们还表明，我们可以通过具有 3k 种颜色的 ASYNC 机器人使用 k 种颜色构建任何不公平 SSYNC 算法的模拟算法，其中不公平并不能保证每个机器人都被无限频繁地激活。结合该模拟和 2 种颜色的 SSYNC 机器人的聚集算法[28]，我们获得了 6 种颜色的 ASYNC 机器人的聚集算法。我们的主要结果可以通过将颜色数量从 6 种减少到 3 种来获得。
We consider aGatheringproblem fornautonomous mobile robots with persistent memory calledlightin an asynchronous scheduler (ASYNC). Gathering is well known to be impossible when robots have no lights in basic standard models if the system is semi-synchronous (SSYNC) or even centralized (only one robot is active at each time). It is known that robots can solve Gathering with 10 colors of lights in ASYNC. This result is obtained by combining the following results. (1) The simulation of SSYNC robots withkcolors by ASYNC robots with 5kcolors [7], and (2) Gathering is solved by SSYNC robots with 2 colors [28].In this paper, we improve the result by reducing the number of colors and show that Gathering can be solved by ASYNC robots with 3 colors of lights. We also show that we can construct a simulation algorithm of anyunfairSSYNC algorithm usingkcolors by ASYNC robots with 3kcolors, where unfairness does not guarantee that every robot is activated infinitely often. Combining this simulation and the Gathering algorithm by SSYNC robots with 2 colors [28], we obtain a Gathering algorithm by ASYNC robots with 6 colors. Our main result can be obtained by reducing the number of colors from 6 to 3.