Exploration Optimale Probabiliste d'un Anneau par des Robots Semi-Synchrones et Amnésiques - Archive ouverte HAL Access content directly
Conference Papers Year : 2009

Exploration Optimale Probabiliste d'un Anneau par des Robots Semi-Synchrones et Amnésiques

(1) , (2) , (3)
1
2
3

Abstract

Nous considérons une cohorte de $k$ robots mobiles identiques, amnésiques et semi-synchrones, capables de percevoir leur environnement mais pas de communiquer, qui évoluent sur des chemins contraints. Les résultats précédents dans ce contexte montre que les situations initiales symétriques induisent des bornes inférieures élevées quand les problèmes doivent être résolus par des robots \emph{déterministes}. Nous initions l'étude des bornes et solutions \emph{probabilistes} dans le même contexte, et considérons le problème de l'exploration d'anneaux anonymes et non orientés de taille $n$ quelconque. Il est connu que $\Theta(\log n)$ robots sont nécessaires et suffisants pour résoudre le problème avec $k$ robots déterministes, quand $k$ et $n$ sont premiers entre eux. Nous montrons que \emph{quatre} robots probabilistes identiques sont nécessaires et suffisants pour résoudre le même problème, tout en supprimant la contrainte de coprimalité. Nos résultats positifs sont constructifs.
Fichier principal
Vignette du fichier
algotel_fr.pdf (73.9 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00383351 , version 1 (12-05-2009)

Identifiers

  • HAL Id : inria-00383351 , version 1

Cite

Stéphane Devismes, Franck Petit, Sébastien Tixeuil. Exploration Optimale Probabiliste d'un Anneau par des Robots Semi-Synchrones et Amnésiques. 11èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2009), Jun 2009, Carry-Le-Rouet, France. ⟨inria-00383351⟩
261 View
46 Download

Share

Gmail Facebook Twitter LinkedIn More