Multi-robot tree and graph exploration

Peter Brass, Andrea Gasparri, Flavio Cabrera, Jizhong Xiao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


In this paper we present an algorithm for the exploration of an unknown graph with k robots, which is guaranteed to succeed on any graph, and which on trees we prove to be near-optimal for two robots, having optimal dependence on the size of the tree but not on its radius. We believe that the algorithm performs well on any graph, and this is substantiated by simulations. For trees with n edges and radius r, the exploration time is 2n/k +O(rk-1), improving a recent method with O( n/log k + r) [1], and almost reaching the lower bound max( 2n/k , 2r). The algorithm is meant to be used in indoor navigation or cave search scenarios where the environment can be modeled as a graph. In this scenario, communication is realized by the devices being dropped by the robots at explored vertices, and the states of which are ead and changed by further visiting robots. Simulations on Player/Stage platform have been performed in both tree and graph exploration which corroborate the mathematical results.

Original languageEnglish (US)
Title of host publication2009 IEEE International Conference on Robotics and Automation, ICRA '09
Number of pages6
StatePublished - Nov 2 2009
Event2009 IEEE International Conference on Robotics and Automation, ICRA '09 - Kobe, Japan
Duration: May 12 2009May 17 2009

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729


Other2009 IEEE International Conference on Robotics and Automation, ICRA '09

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering


Dive into the research topics of 'Multi-robot tree and graph exploration'. Together they form a unique fingerprint.

Cite this