Exploration d'arbres par des équipes de robots asynchrones et sans mémoire

Résumé : Une équipe d'entités mobiles (robots), identiques et sans mémoire, doit explorer un arbre anonyme en visitant tous ses noeuds. Les robots démarrent depuis des noeuds différents et arbitraires de l'arbre et opèrent suivant des cycles Regarder-Calculer-Aller (Look-Compute-Move). A la fin, chaque noeud doit avoir été visité par au moins un robot, et tous les robots doivent s'arrêter. Dans un cycle, un robot prend une photographie de la configuration courante (Regarder), prend la décision de rester immobile ou de se déplacer vers un des noeuds adjacents (Calculer), et dans ce dernier cas se déplace instantanément vers ce voisin (Aller). Les cycles sont exécutés de façon asynchrone par chaque robot. Nous présentons un algorithme d'exploration pour tous les arbres à n noeuds de degré maximum 3 utilisant O(log n/loglog n) robots, et nous prouvons que pour de tels arbres Omega(log n/loglog n) robots sont nécessaires pour les explorer. Nous montrons par ailleurs que l'exploration de certains arbres à n noeuds de degré maximum 4 nécessite Omega(n) robots.
Type de document :
Communication dans un congrès
9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.99-102, 2007
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00176961
Contributeur : David Coudert <>
Soumis le : vendredi 5 octobre 2007 - 01:56:21
Dernière modification le : lundi 11 décembre 2017 - 14:04:10
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 12:57:08

Fichier

61-Ilcinkas_AlgoTel2007.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00176961, version 1

Collections

Citation

Paola Flocchini, David Ilcinkas, Andrzej Pelc, Nicola Santoro. Exploration d'arbres par des équipes de robots asynchrones et sans mémoire. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.99-102, 2007. 〈inria-00176961〉

Partager

Métriques

Consultations de la notice

153

Téléchargements de fichiers

40