''Complete Visibility for Robots with Lights in O(1) Time''
Gokarna Sharma
Ramachandran Vaidyanathan
Jerry L. Trahan
Costas Busch
Suresh Rai
Proc. 18th International Symposium on Stabilization, Safety, and
Security of Distributed Systems
(SSS 2016), pp. 327-345, 2016.
Abstract:
We consider the problem of repositioning N autonomous robots on a
plane so that each robot is visible to all others (the COMPLETE VISIBILITY problem);
a robot cannot see another robot if its visibility is obstructed by a third robot
positioned between them on a straight line. This problem is important since it provides
a basis to solve many other problems under obstructed visibility. Robots operate
following Look-Compute-Move (LCM) cycles and communicate with other
robots using colored lights as in the recently proposed robots with lights model.
The challenge posed by this model is that each robot has only a constant number
of colors for its lights (symbols for communication) and no memory (except
for the persistence of lights) between LCM cycles. Our goal is to minimize the
number of rounds needed to solve COMPLETE VISIBILITY, where a round is
measured as the time duration for all robots to execute at least one complete
LCM cycle since the end of the previous round. The best previously known algorithm
for COMPLETE VISIBILITY on this robot model has runtime of O(log N)
rounds. That algorithm has the assumptions of full synchronicity, chirality, and
robot paths may collide. In this paper we present the first algorithm for COMPLETE
VISIBILITY with O(1) runtime that runs on the semi-synchronous (and
also the fully synchronous) model. The proposed algorithm does not have the
chirality assumption and is collision free.