Optimal deterministic ring exploration with oblivious asynchronous robots

Abstract : We consider the problem of exploring an anonymous unoriented ring of size $n$ by $k$ identical, oblivious, asynchronous mobile robots, that are unable to communicate, yet have the ability to sense their environment and take decisions based on their local view. Previous works in this weak scenario prove that $k$ must not divide $n$ for a deterministic solution to exist. Also, it is known that the minimum number of robots (either deterministic or probabilistic) to explore a ring of size $n$ is $4$. An upper bound of $17$ robots holds in the deterministic case while $4$ probabilistic robots are sufficient. In this paper, we close the complexity gap in the deterministic setting, by proving that no deterministic exploration is feasible with less than five robots whenever the size of the ring is even, and that five robots are sufficient for any $n$ that is coprime with five. Our protocol completes exploration in $O(n)$ robot moves, which is also optimal.
Type de document :
Rapport
[Research Report] 2009, pp.23
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00422100
Contributeur : Maria Potop-Butucaru <>
Soumis le : lundi 5 octobre 2009 - 17:10:05
Dernière modification le : vendredi 31 août 2018 - 09:25:53
Document(s) archivé(s) le : mardi 15 juin 2010 - 22:27:44

Fichiers

ReportExploration.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00422100, version 1
  • ARXIV : 0910.0832

Collections

Citation

Anissa Lamani, Maria Potop-Butucaru, Sébastien Tixeuil. Optimal deterministic ring exploration with oblivious asynchronous robots. [Research Report] 2009, pp.23. 〈inria-00422100〉

Partager

Métriques

Consultations de la notice

328

Téléchargements de fichiers

178