Complete Visitability for Autonomous Robots on Graphs

Abstract

We consider the distributed setting of N autonomous mobile robots operating on graphs following Look-Compute-Move cycles and communicating with other robots using colored lights under the robots with lights model. We assume obstructed visibility under which a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. We introduce and study the fundamental problem of repositioning N robots on the nodes of a graph so that each robot has a path to all others without visiting an intermediate node that is occupied by any other robot (which we call the Complete Visitability problem). This problem is of interest due to its relationship to the problems of information collection, scattering, flocking, and dispersion on graphs. This problem generalizes the Complete Visitability problem studied in the literature, where the goal was to reposition the robots on a plane so that each robot sees all others. We have the following four results: We first show that it is impossible to solve Complete Visitability on arbitrary graphs, irrespective of the number of colors, time, and the robot activation setting (fully synchronous, semi-synchronous, or asynchronous). We then give an algorithm that solves Complete Visitability on grid graphs using 7 colors in the semi-synchronous setting. The algorithm uses 6 colors in the fully synchronous setting. The algorithm is collision-free. We then show that the total number of moves by any robot is O(h) and the runtime is O(h <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) in our algorithm, where h denotes the number of layers of robots in the initial configuration. We also show that the number of moves bound is asymptotically tight and any Complete Visitability algorithm has runtime Ω(h) in grid graphs. We finally show that the algorithm and bounds for grid graphs extend to hexagonal tessellation graphs under chirality - robots agree on left and right directions.