HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LIFL - Laboratoire d'Informatique Fondamentale de Lille, LRI - Laboratoire de Recherche en Informatique
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.
Complete list of metadata

Contributor : Sébastien Tixeuil Connect in order to contact the contributor
Submitted on : Tuesday, February 10, 2009 - 9:45:13 PM
Last modification on : Friday, February 4, 2022 - 3:31:54 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 7:20:32 PM


Files produced by the author(s)


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


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⟩



Record views


Files downloads