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.

### The mutual visibility problem for oblivious robots

#### Abstract

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.
##### Scheda breve Scheda completa Scheda completa (DC)
2014
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11568/853461`
• ND
• 28
• ND