Mutual visibility by luminous robots without collisions
Mutual visibility by luminous robots without collisions
复制标题
发光机器人相互可见而不会发生碰撞
DOI：
10.1016/j.ic.2016.09.005
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
G. Viglietta
中科院分区：
文献类型：
--
作者：
Giuseppe Antonio Di Luna;P. Flocchini;S. Chaudhuri;Federico Poloni;N. Santoro;G. Viglietta
我们考虑匿名dimensionelessrobotswith受阻的能见度在平面上移动的相互可见性问题：从不同的位置开始，机器人必须达到，没有碰撞，其中没有三个是共线的配置。我们在发光机器人模型中研究了这个问题，其中每个机器人都有一个可见光，可以采用固定集合中的颜色。除其他结果外，我们证明了相互可见性可以在SSynch中使用2种颜色和在ASynch中使用3种颜色来解决。如果对手可以中断和停止机器人移动到其计算的目的地，相互可见性仍然是可解决的SSynch与3种颜色，如果机器人同意一个轴的方向，也在ASynch。作为副产品，我们提供了第一个障碍可见性解决方案的两个经典问题的遗忘机器人：无碰撞收敛到一个点（也称为近聚集）和圆的形成。
We consider the Mutual Visibility problem for anonymous dimensionlessrobotswith obstructed visibility moving in a plane: starting from distinct locations, the robots must reach, without colliding, a configuration where no three of them are collinear. We study this problem in theluminous robotsmodel, in which each robot has a visible light that can assume colors from a fixed set.Among other results, we prove that Mutual Visibility can be solved in SSynch with 2 colors and in ASynch with 3 colors. If an adversary can interrupt and stop a robot moving to its computed destination, Mutual Visibility is still solvable in SSynch with 3 colors and, if the robots agree on the direction of one axis, also in ASynch.As a byproduct, we provide the first obstructed-visibility solutions to two classical problems for oblivious robots:collision-less convergence to a point(also known asnear-gathering) andcircle formation.