''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


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.