TY - JOUR
T1 - A flooding algorithm for multirobot exploration
AU - Cabrera-Mora, Flavio
AU - Xiao, Jizhong
N1 - Funding Information:
Manuscript received May 20, 2011; revised October 25, 2011; accepted November 23, 2011. Date of publication January 23, 2012; date of current version May 16, 2012. This work was supported in part by the U.S. Army Research Office under Grants W911NF-08-1-0531 and W911NF-09-1-0565 and in part by the U.S. National Science Foundation under Grants CNS-0619577 and IIS-0644127. This paper was recommended by Associate Editor H. Wang.
PY - 2012
Y1 - 2012
N2 - In this paper, we present a multirobot exploration algorithm that aims at reducing the exploration time and to minimize the overall traverse distance of the robots by coordinating the movement of the robots performing the exploration. Modeling the environment as a tree, we consider a coordination model that restricts the number of robots allowed to traverse an edge and to enter a vertex during each step. This coordination is achieved in a decentralized manner by the robots using a set of active landmarks that are dropped by them at explored vertices. We mathematically analyze the algorithm on trees, obtaining its main properties and specifying its bounds on the exploration time. We also define three metrics of performance for multirobot algorithms. We simulate and compare the performance of this new algorithm with those of our multirobot depth first search (MR-DFS) approach presented in our recent paper and classic single-robot DFS.
AB - In this paper, we present a multirobot exploration algorithm that aims at reducing the exploration time and to minimize the overall traverse distance of the robots by coordinating the movement of the robots performing the exploration. Modeling the environment as a tree, we consider a coordination model that restricts the number of robots allowed to traverse an edge and to enter a vertex during each step. This coordination is achieved in a decentralized manner by the robots using a set of active landmarks that are dropped by them at explored vertices. We mathematically analyze the algorithm on trees, obtaining its main properties and specifying its bounds on the exploration time. We also define three metrics of performance for multirobot algorithms. We simulate and compare the performance of this new algorithm with those of our multirobot depth first search (MR-DFS) approach presented in our recent paper and classic single-robot DFS.
UR - http://www.scopus.com/inward/record.url?scp=84861196470&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84861196470&partnerID=8YFLogxK
U2 - 10.1109/TSMCB.2011.2179799
DO - 10.1109/TSMCB.2011.2179799
M3 - Article
C2 - 22275717
AN - SCOPUS:84861196470
SN - 1083-4419
VL - 42
SP - 850
EP - 863
JO - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
JF - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
IS - 3
M1 - 6135816
ER -