FLOCCHINI, Paola; ILCINKAS, David; PELC, Andrzej; SANTORO, Nicola

doi:10.1007/s00453-011-9611-5

Métadonnées

Licence d’utilisation du document

FLOCCHINI, Paola
School of Electrical Engineering and Computer Science [EECS]

ILCINKAS, David
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

PELC, Andrzej
Département d'Informatique et d'Ingénierie [DII]

Langue

Article de revue

Ce document a été publié dans

Algorithmica. 2013-03, vol. 65, n° 3, p. 562-583

Springer Verlag

Résumé en anglais

We consider the problem of exploring an anonymous unoriented ring by a team of k identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak scenario is standard when the spatial universe in which the robots operate is the two-dimensional plane, but (with one exception) has not been investigated before for networks. Our results imply that, although these weak capabilities of robots render the problem considerably more difficult, ring exploration by a small team of robots is still possible. We first show that, when k and n are not co-prime, the problem is not solvable in general, e.g., if k divides n there are initial placements of the robots for which gathering is impossible. We then prove that the problem is always solvable provided that n and k are co-prime, for k >= 17, by giving an exploration algorithm that always terminates, starting from arbitrary initial configurations. Finally, we consider the minimum number rho(n) of robots that can explore a ring of size n. As a consequence of our positive result we show that rho(n) is O(log n). We additionally prove that Omega(log n) robots are necessary for infinitely many n.< Réduire

Mots clés en anglais

mobile robots

asynchronous

oblivious

exploration

ring

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

DOI

Origine

Unités de recherche