A Distributed Algorithm for Exploration of Unknown Environments with Multiple Robots

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 several variants. The robots are modeled as points or discs, the obstacles are distinguishable or they are not distinguishable, the point robots only communicate at rendezvous, the disc-shaped robots can communicate if they are visible to each other, finally the free subset of the configuration space has one or several connected components. 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 the robots are no capable of building an exact map of the environment, they cannot estimate their positions and 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. 3) We combine and extend the velocity obstacle method with our proposed approach to explore the environment using disc-shaped robots that are able to avoid collisions with both moving and static obstacles. 4) We propose an exploration strategy such that even if the configuration space has several connected components this strategy guarantees covering the largest possible portion of the environment with an omnidirectional sensor detecting the visibility regions. 5) The algorithm scales well to hundreds of robots and obstacles. We tested in several simulations the performance of our algorithms using different performance metrics.