Asynchronous Ring Gathering by Oblivious Robots with Limited Vision

摘要

We investigate in this paper the gathering problem on ring shaped networks where the aim is to ensure that a collection of identical, oblivious and asynchronous mobile robots meet (gather) in one location not known in advance. Robots operate in cycles that consist of three phases: Look, Compute and Move. During the first phase, robots take a snapshot to see the positions of the other robots. In the second phase, they make a decision to move or to stay idle. In the last phase, they move towards a computed destination if any. While most of the previous works in the discrete universe, under this setting consider that robots have an unlimited visibility i.e., each robot is able to see the position of all the other robots in the system, only few studies have been devoted recently to the case where robots have a restricted visibility. In our work, we continue the investigation aiming to characterize the cases in which the problem can be solved.