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