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

Stéphane Devismes 1 Franck Petit 2 Sébastien Tixeuil 3
2 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
Résumé : 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.
Type de document :
Communication dans un congrès
Chaintreau, Augustin and Magnien, Clemence. 11èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2009), Jun 2009, Carry-Le-Rouet, France. 2009
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00383351
Contributeur : Stéphane Devismes <>
Soumis le : mardi 12 mai 2009 - 22:17:46
Dernière modification le : vendredi 6 juillet 2018 - 10:08:02
Document(s) archivé(s) le : lundi 15 octobre 2012 - 10:16:19

Fichier

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

Identifiants

  • HAL Id : inria-00383351, version 1

Collections

Citation

Stéphane Devismes, Franck Petit, Sébastien Tixeuil. Exploration Optimale Probabiliste d'un Anneau par des Robots Semi-Synchrones et Amnésiques. Chaintreau, Augustin and Magnien, Clemence. 11èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2009), Jun 2009, Carry-Le-Rouet, France. 2009. 〈inria-00383351〉

Partager

Métriques

Consultations de la notice

484

Téléchargements de fichiers

106