The Mutual Visibility Problem for Oblivious Robots

摘要

Consider a finite set of identical entities, called robots, which can move freely in the Euclidean plane. Let p(t) denote the location of robot p at time t; a robot p can see robot q at time t if at that time no other robot lies in the line segment p(t)q(t). We consider the basic problem called Mutual Visibility: starting from arbitrary distinct locations, within finite time the robots must reach, without collisions, a configuration where they all see each other. This problem must be solved by each entity autonomously executing the same algorithm. We study this problem in the standard model of semi-synchronous oblivious robots. The extensive literature on computability in such a model has never considered this problem because it has always assumed that three collinear robots are mutually visible. In this paper we remove this assumption, and present an algorithm that solves Mutual Visibility. To prove its correctness, we solve a seemingly unrelated problem, Communicating Vessels, which is interesting in its own right. As a byproduct of our solution, we also solve a classical problem for oblivious robots, Near-Gathering, even if one robot is faulty and unable to move.