''Complete Visibility for Asynchronous Robots with Lights''
Gokarna Sharma
Ramachandran Vaidyanathan
Jerry L. Trahan
Costas Busch
Suresh Rai
Proc. International Parallel and Distributed Processing Symposium
(IPDPS'17), pp. 513-522, 2017
Abstract:
We consider the distributed setting of N autonomous
mobile robots that operate in Look-Compute-Move
(LCM) cycles and communicate with other robots using colored
lights (the robots with lights model). We study the fundamental
problem of repositioning N autonomous robots on a plane
so that each robot is visible to all others (the COMPLETE
VISIBILITY problem) on this model; a robot cannot see another
robot if a third robot is positioned between them on the straight
line connecting them. There exists an O(1) time, O(1) color
algorithm for this problem in the semi-synchronous setting.
In this paper, we provide the first O(log N) time, O(1) color
algorithm for this problem in the asynchronous setting. This
is a significant improvement over an O(N)-time translation of
the semi-synchronous algorithm to the asynchronous setting.
The proposed algorithm is collision-free -- robots do not share
positions and their paths do not cross.