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