A decentralized algorithm for collision-free search tasks by multiple robots in 3D areas

Abstract

This paper presents a decentralized search algorithm for a multi-robot system in an unknown three-dimensional (3D) space with no collisions. Robots only have limited sensing and communication ranges and they move along edges of a grid pattern between vertices to search the whole area without collisions. When unvisited accessible vertices are available, a random algorithm with repulsive force is used to choose the next step. Otherwise, the breadth-first search algorithm is applied to find the path to a nearest unvisited vertex. This paper also proves the convergence of the algorithm with probability 1. Simulations are run to compare this algorithm with related algorithms to show its advantage.