Ring exploration with myopic luminous robots
Ring exploration with myopic luminous robots
复制标题
近视发光机器人环探索
DOI：
10.1016/j.ic.2021.104702
复制
发表时间：
2021
影响因子：
1
通讯作者：
Fukuhito Ooshita and Sebastien Tixeuil
中科院分区：
文献类型：
--
作者：
Eto Hiroshi;Ito Takehiro;Kobayashi Yasuaki;Otachi Yota;Wasa Kunihiro;早乙女献自，中澤巧爾;Ryota Nakayama and Naoki Nishida;Fukuhito Ooshita and Sebastien Tixeuil
我们研究探索算法的自主移动的机器人在均匀的环形网络中发展。与以往的工作不同，我们考虑了近视（每个机器人只能观察其相邻节点）和亮度（每个机器人只能使用两种颜色的光）的机器人属性。三）近视机器人是必要的和足够的，以实现永久（分别为。终止）探索，以及（ii）在SSYNC和ASYNC模型中，三个（分别为）四）近视机器人是必要的和足够的，以实现永久（分别为。我们还表明，在所有的执行模型中，我们的永久探索算法是通用的。也就是说，该算法从任何可解的初始配置解决了永久探索，其中两个（分别为）三）近视机器人和两种颜色的FSYNC模型（分别为。SSYNC和ASYNC模型）。另一方面，我们为普遍的终止探索提供了不可能的结果。
We investigate exploration algorithms for autonomous mobile robots evolving in uniform ring-shaped networks. Unlike previous works, we consider myopia (each robot can only observe its neighboring nodes) and luminosity (each robot can use only two colors for its light) properties for the robots.As a main contribution, we prove that(i)in the FSYNC model, two (resp. three) myopic robots are necessary and sufficient to achieve perpetual (resp. terminating) exploration, and(ii)in the SSYNC and ASYNC models, three (resp. four) myopic robots are necessary and sufficient to achieve perpetual (resp. terminating) exploration.We also show that, in all execution models, our perpetual exploration algorithm is universal. That is, the algorithm solves perpetual exploration from any solvable initial configuration with two (resp. three) myopic robots and two colors in the FSYNC model (resp. the SSYNC and ASYNC models). On the other hand, we provide impossibility results for universal terminating exploration.