Distrib uted, Complete, Multi-robot Coverage of Initially Unknown Environments using Repartitioning (Extended Abstract)
Kurt Hungerford, Prithviraj Dasgupta, K. R. Guruprasad · 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.