''Logarithmic-Time Complete Visibility for Robots with Lights''

Ramachandran Vaidyanathan

Costas Busch

Jerry L. Trahan

Gokarna Sharma

Suresh Rai

Proc. 2015 International Parallel and Distributed Processing Symposium (IPDPS), pp. 375-384


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 there is a third robot positioned between them on the straight line joining them. Robots communicate using colored lights. The computation is synchronous and each robot performs a look-compute-move during a round. Specifically, during a round a robot is permitted to observe the light and position of every robot visible to it. It may also perform an internal computation based on the observed lights and positions (including deciding on a new color for its own light), and possibly moving to a new position at the end of the round. The challenge posed by this model of computation stems from the fact 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 rounds. In this paper we first show that the best previously known algorithm for the complete visibility problem on this model runs in linear time in the worst case. We then present a new, significantly faster algorithm with logarithmic worst-case time complexity.