Multi-robot tree and graph exploration

Abstract

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(r <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k-1</sup> ), 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 read 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.