Uniform Circle Formation for Swarms of Opaque Robots with Lights
Uniform Circle Formation for Swarms of Opaque Robots with Lights
复制标题
带灯的不透明机器人群的均匀圆圈形成
DOI：
10.1007/978-3-030-03232-6_21
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Beatrice Palano
中科院分区：
文献类型：
--
作者：
Caterina Feletti;C. Mereghetti;Beatrice Palano
均匀圆形成问题需要一群任意定位在平面上的移动代理，在正多边形的顶点上移动。每个代理（通常称为机器人）通过一系列查看-计算-移动周期进行操作。机器人不存储过去的操作/系统快照。它们是匿名的，无法通过外观来区分，并且不具有共同的坐标系（原点和轴）和手性。该系统是完全同步的，因为所有机器人都有一个共同的时钟/时间调节周期的概念。根据文献，最近已知均匀圆形成问题可以在机器人为点状或胖形的系统中解决，但在这两种情况下都是透明的：没有机器人阻碍任何其他机器人的可见性。在这里，我们在更现实的不透明机器人系统中解决均匀圆形成问题，即机器人可能由于共线性而阻碍可见性。然而，我们的机器人被认为是点状和发光的，即配备了呈现不同颜色的持久光。后一种特性代表了机器人必须进行通信的唯一方式。我们提出的算法使用恒定数量的外观-计算-移动周期以及恒定数量的颜色。
The Uniform Circle Formation problem requires a swarm of mobile agents, arbitrarily positioned onto the plane, to move on the vertices of a regular polygon. Each agent, customarily called robot, acts through a sequence of look-compute-move cycles. The robots do not store past actions/system snapshots. They are anonymous and cannot be distinguished by their appearance and do not have a common coordinate system (origin and axis) and chirality. The system is fully synchronous in that all robots have a common clock/notion of time regulating cycles. From the literature, the Uniform Circle Formation problem is recently known to be solvable in a system where robots are punctiform or fat, but in both cases transparent: no robot obstructs the visibility of any other robot. Here, we solve the Uniform Circle Formation problem within a more realistic opaque robot system, i.e., robots may have obstructed visibility due to collinearities. Yet, our robots are assumed to be punctiform and luminous, i.e., equipped with a persistent light assuming different colors. This latter peculiarity represents the only way robots have to communicate. Our proposed algorithm uses a constant number of look-compute-move cycles as well as a constant number of colors.