Anonymous Graph Exploration without Collision by Mobile Robots

Abstract : Considering autonomous mobile robots moving on a finite anonymous graph, this paper focuses on the Constrained Perpetual Graph Exploration problem (CPGE). That problem requires each robot to perpetually visit all the vertices of the graph, in such a way that no vertex hosts more than one robot at a time, and each edge is traversed by at most one robot at a time. The paper states an upper bound k on the number of robots that can be placed in the graph while keeping CPGE solvability. To make the impossibility result as strong as possible (no more than k robots can be initially placed in the graph), this upper bound is established under a strong assumption, namely, there is an omniscient daemon that is able to coordinate the robots movements at each round of the synchronous system. Interestingly, this upper bound is related to the topology of the graph. More precisely, the paper associates with each graph a labeled tree that captures the paths that have to be traversed by a single robot at a time (as if they were a simple edge). The length of the longest of these labeled paths reveals to be the key parameter to determine the upper bound k on the number of robots.
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
Contributeur : Anne Jaigu <>
Soumis le : lundi 11 février 2008 - 09:27:59
Dernière modification le : mardi 16 janvier 2018 - 15:54:12
Document(s) archivé(s) le : lundi 17 mai 2010 - 16:24:23


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00250153, version 1


Roberto Baldoni, François Bonnet, Alessia Milani, Michel Raynal. Anonymous Graph Exploration without Collision by Mobile Robots. [Research Report] PI 1886, 2008, pp.12. 〈inria-00250153〉



Consultations de la notice


Téléchargements de fichiers