TY - GEN

T1 - Network exploration by silent and oblivious robots

AU - Chalopin, Jérémie

AU - Flocchini, Paola

AU - Mans, Bernard

AU - Santoro, Nicola

PY - 2010

Y1 - 2010

N2 - In this paper we investigate the basic problem of Exploration of a graph by a group of identical mobile computational entities, called robots, operating autonomously and asynchronously. In particular we are concerned with what graphs can be explored, and how, if the robots do not remember the past and have no explicit means of communication. This model of robots is used when the spatial universe in which the robots operate is continuous (e.g., a curve, a polygonal region, a plane, etc.). The case when the spatial universe is discrete (i.e., a graph) has been also studied but only for the classes of acyclic graphs and of simple cycles. In this paper we consider networks of arbitrary topology modeled as connected graphs with local orientation (locally distinct edge labels). We concentrate on class Hk of asymmetric configurations with k robots. Our results indicate that the explorability of graphs in this class depends on the number k of robots participating in the exploration. In particular, exploration is impossible for k<3 robots. When there are only k=3 robots, only a subset of H3 can be explored; we provide a complete characterization of the networks that can be explored. When there are k=4 robots, we prove that all networks in H4 can be explored. Finally, we prove that for any odd k>4 all networks in Hk can be explored by presenting a general algorithm. The determination of which networks can be explored when k>4 is even, is still open but can be reduced to the existence of a gathering algorithm for Hk.

AB - In this paper we investigate the basic problem of Exploration of a graph by a group of identical mobile computational entities, called robots, operating autonomously and asynchronously. In particular we are concerned with what graphs can be explored, and how, if the robots do not remember the past and have no explicit means of communication. This model of robots is used when the spatial universe in which the robots operate is continuous (e.g., a curve, a polygonal region, a plane, etc.). The case when the spatial universe is discrete (i.e., a graph) has been also studied but only for the classes of acyclic graphs and of simple cycles. In this paper we consider networks of arbitrary topology modeled as connected graphs with local orientation (locally distinct edge labels). We concentrate on class Hk of asymmetric configurations with k robots. Our results indicate that the explorability of graphs in this class depends on the number k of robots participating in the exploration. In particular, exploration is impossible for k<3 robots. When there are only k=3 robots, only a subset of H3 can be explored; we provide a complete characterization of the networks that can be explored. When there are k=4 robots, we prove that all networks in H4 can be explored. Finally, we prove that for any odd k>4 all networks in Hk can be explored by presenting a general algorithm. The determination of which networks can be explored when k>4 is even, is still open but can be reduced to the existence of a gathering algorithm for Hk.

UR - http://www.scopus.com/inward/record.url?scp=78650197985&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-16926-7_20

DO - 10.1007/978-3-642-16926-7_20

M3 - Conference proceeding contribution

AN - SCOPUS:78650197985

SN - 3642169252

SN - 9783642169250

T3 - Lecture Notes in Computer Science

SP - 208

EP - 219

BT - Graph-Theoretic Concepts in Computer Science

A2 - Thilikos, Dimitrios M.

PB - Springer, Springer Nature

CY - Berlin; Heidelberg

T2 - 36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010

Y2 - 28 June 2010 through 30 June 2010

ER -