A flooding algorithm for multirobot exploration

Flavio Cabrera-Mora, Jizhong Xiao

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


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.

Original languageEnglish (US)
Article number6135816
Pages (from-to)850-863
Number of pages14
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Issue number3
StatePublished - 2012

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'A flooding algorithm for multirobot exploration'. Together they form a unique fingerprint.

Cite this