A decentralized algorithm for collision free navigation of multiple robots in search tasks

Abstract

This paper presents a novel collision free decentralized random algorithm for multiple robots to search targets in unknown environments with a collision avoidance method. A common triangular grid pattern is used by all robots as the initial condition which guarantees complete coverage. Then robots move between vertices of the grid. The next vertex for the robot is chosen in certain order and is based on its past explored map and information from neighbors in communication range. The searched area and obstacles are arbitrary and unknown. The volume and physical constraints of the robot are considered to ensure that it moves without any collisions. A mathematical proof of convergence with probability 1 is given and the effectiveness of the algorithm is validated by the Matlab simulation.