A Decentralized Control Algorithm for Target Search by a Multi-Robot Team

Abstract

This paper introduces a novel decentralized random algorithm to search of an unknown area by a multi-robot system. The proposed algorithm applies a triangular grid pattern for the search procedure that guarantees complete search of the whole area. The algorithm is based only on information about the nearest neighbours of each robot. The monitoring region is of an arbitrary shape and not known to the robots a priori. A mathematically rigorous proof of convergence with probability 1 of the proposed algorithm is given and eectiveness of the algorithm is also illustrated via computer simulation.