Cluster, Allocate, Cover: An Efficient Approach for Multi-robot Coverage

Abstract

This article presents an algorithm for online multirobot coverage that proceeds with minimal knowledge of the already explored region and the frontier cells. It creates clusters of frontier cells which are designated to robots using an optimal assignment scheme. Coverage is then performed using a novel path planning technique. Many approaches that use clustering for multi-robot coverage do not specify strict time criteria for re-clustering. Moreover, the motion plans they use result in redundant coverage. To overcome these limitations, an appropriate motion plan for the robots is chosen based on the context of already covered frontiers. Dispersion of robots is vital for efficient coverage and is an emergent behavior in our approach. The efficacy of the proposed approach is tested in simulation and on a multi-robot test-bed. The algorithm performs better than some state of the art approaches.