Distributed, complete, multi-robot coverage of initially unknown environments using repartitioning
Kurt Hungerford, Prithviraj Dasgupta, K. R. Guruprasad · Adaptive Agents and Multi-Agents Systems · 2014
We consider the problem of coverage path planning by multiple robots in an environment where the location and geometry of obstacles are initially unknown to the robots. We propose a novel algorithm where the robots initially partition the environment using Voronoi partitioning. Each robot then uses an auction-based algorithm to reallocate inaccessible portions of its initial Voronoi cell to robots in neighboring Voronoi cells so that each robot is responsible for covering a set of contiguous connected regions. We have verified the performance of our algorithm on e-puck robots within the Webots simulator in different environments with different obstacle geometries and shown that it performs complete, non-overlapping coverage.