Grid based 2D navigation by a decentralized robot system with collison avoidance

Abstract

This paper presents a collision-free decentralized random algorithm for robots to search an unknown 2D area with obstacles. Assumptions in this paper are based on real robots instead of particles so collisions between robots are considered. Robots move along edges of a grid and randomly choose the next steps in sequence based on local sensing, communication, and the repulsive force method. A rigorous mathematical proof of convergence with probability 1 is given. For a complete search of the area, an equilateral triangular grid should be used and the algorithm is compared with others in the simulation.