Title :
Improved analysis of a multirobot graph exploration strategy
Author :
Brass, Peter ; Vigan, Ivo ; Ning Xu
Author_Institution :
Dept. of Comput. Sci., City Coll. of New York, New York, NY, USA
Abstract :
In this paper, we present an algorithm for exploring an unknown graph with opaque edges by multiple robots. We show that this algorithm is near optimal on graphs with n vertices and superlinear number of edges (i.e., ω(n) edges), and give an adversarial construction to show that the algorithm does not perform well on cyclic graphs with O(n) edges.
Keywords :
graph theory; mobile robots; multi-robot systems; adversarial construction; graph vertices; multirobot graph exploration strategy; near optimal algorithm; opaque edges; superlinear edges; unknown graph; Bipartite graph; Collision avoidance; Computer science; Electronic mail; Mobile robots; Upper bound; Graph Exploration; Mapping; On-line Algorithm; Path Planning for Multiple Mobile Robot Systems;
Conference_Titel :
Control Automation Robotics & Vision (ICARCV), 2014 13th International Conference on
DOI :
10.1109/ICARCV.2014.7064607
