The Complete Visibility Problem for Fat Robots with Lights

Abstract

We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move 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. We consider obstructed visibility under which a robot cannot see another robot if a third robot is positioned between then on the straight line connecting them. The literature solves this problem on the robots with lights model for point robots. In this paper, we study this problem, for the very first time, on the robots with lights model for fat robots, i.e., the robots which have physical extents. In particular, we present and analyze an algorithm for the fat robots of unit disc size extents that solves Complete Visibility in O(N) time using 9 colors in the fully synchronous setting avoiding robot collisions.