Paper Info
Title
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.
Year
DOI
Venue
2008
10.1016/j.ipl.2008.08.011
Inf. Process. Lett.
Keywords
Field
DocType
paper associate,robots movement,finite anonymous graph,simple edge,strong assumption,cpge solvability,anonymous graph exploration,upper bound k,autonomous mobile robot,single robot,k robot,upper bound,anonymity,robot,distributed computing,mobile robot
Strength of a graph,Combinatorics,Visibility graph,Loop (graph theory),Biconnected graph,Null graph,Regular graph,Mathematics,Voltage graph,Complement graph
Journal
Volume
Issue
ISSN
109
2
0020-0190
Citations 
PageRank 
References 
10
0.69
14
Authors
4
Name
Order
Citations
PageRank
Roberto Baldoni11606132.37
François Bonnet2806.65
Alessia Milani318715.54
Michel Raynal44078349.46