Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots

Stéphane Devismes 1 Franck Petit 2, 3 Sébastien Tixeuil 4, 5
3 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : We consider a team of $k$ identical, oblivious, asynchronous mobile robots that are able to sense (\emph{i.e.}, view) their environment, yet are unable to communicate, and evolve on a constrained path. Previous results in this weak scenario show that initial symmetry yields high lower bounds when problems are to be solved by \emph{deterministic} robots. In this paper, we initiate research on probabilistic bounds and solutions in this context, and focus on the \emph{exploration} problem of anonymous unoriented rings of any size. It is known that $\Theta(\log n)$ robots are necessary and sufficient to solve the problem with $k$ deterministic robots, provided that $k$ and $n$ are coprime. By contrast, we show that \emph{four} identical probabilistic robots are necessary and sufficient to solve the same problem, also removing the coprime constraint. Our positive results are constructive.
Liste complète des métadonnées

https://hal.inria.fr/inria-00360305
Contributeur : Sébastien Tixeuil <>
Soumis le : mardi 10 février 2009 - 21:45:13
Dernière modification le : vendredi 6 juillet 2018 - 10:08:02
Document(s) archivé(s) le : mardi 8 juin 2010 - 19:20:32

Fichiers

RR-6838.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00360305, version 1
  • ARXIV : 0902.1834

Citation

Stéphane Devismes, Franck Petit, Sébastien Tixeuil. Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots. [Research Report] RR-6838, INRIA. 2009, pp.29. 〈inria-00360305〉

Partager

Métriques

Consultations de la notice

571

Téléchargements de fichiers

306