Multi-robot Coverage Using Voronoi Partitioning Based on Geodesic Distance

In this paper we propose Geodesic-VPC, a “partition” and “cover” strategy for a multi-robot system using Voronoi partitioning based on geodesic distance metric in the place of the usual Euclidean distance. Each robot is responsible for covering the corresponding geodesic-Voronoi cell using a single-robot coverage strategy. The proposed partitioning scheme ensures that Voronoi cells are contiguous even in the presence of obstacles. We demonstrate that if the single-robot coverage strategy is capable of providing a complete and non-repetitive coverage, then the proposed Geodesic-VPC strategy provides a complete and non-repetitive coverage. We use spanning tree-based coverage algorithm as the underlying single-robot coverage strategy for the purpose of demonstration, though any existing single-robot coverage algorithm can be used.