A distributed exploration algorithm for unknown environments with multiple obstacles by multiple robots

Abstract

In this paper, we present a complete algorithm for exploration of unknown environments containing disjoint obstacles with multiple robots. We propose a distributed approach considering two main cases. In the first one, the obstacles are distinguishable, i.e., each obstacle is uniquely identifiable, which can be imagined as each obstacle having a different color, and in the second case, the obstacles are not distinguishable. Two possible applications of our algorithms are: 1) Search of a static object in an unknown environment. 2) Damage verification in unknown environments composed by multiple elements (e.g. buildings). The main contributions of this work are the following: 1) The algorithms guarantee exploring the whole environment in finite time even though each robot does not have full information about the part of the environment explored by other robots. 2) The method only requires limited communication between the robots. In both cases distinguishable and indistinguishable obstacles, the robots communicate only at rendezvous. 3) The algorithm scales well to hundreds of robots and obstacles. We tested in several simulations the performance of our algorithms for both cases, in terms of the distance traveled by the robots.