A repartitioning algorithm to guarantee complete, non-overlapping planar coverage with multiple robots

Kurt Hungerford, Prithviraj Dasgupta, K. R. Guruprasad

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

We consider the problem of coverage path planning in an initially unknown or partially known planar environment using multiple robots. Previously, Voronoi partitioning has been proposed as a suitable technique for coverage path planning where the free space in the environment is partitioned into non-overlapping regions called Voronoi cells based on the initial positions of the robots, and one robot is allocated to perform coverage in each region. However, a crucial problem arises if such a partitioning scheme is used in an environment where the location of obstacles is not known a priori—while performing coverage, a robot might perceive an obstacle that occludes its access to portions of its Voronoi cell and this obstacle might prevent the robot from completely covering its allocated region. This would either result in portions of the environment remaining uncovered or requires additional path planning by robots to cover the disconnected regions. To address this problem, we propose a novel algorithm that allows robots to coordinate the coverage of inaccessible portions of their Voronoi cell with robots in neighboring Voronoi cells so that they can repartition the initial Voronoi cells and cover a set of contiguous, connected regions. We have proved analytically that our proposed algorithm guarantees complete, non-overlapping coverage. We have also quantified the performance of our algorithm on e-puck robots within the Webots simulator in different environments with different obstacle geometries and shown that it successfully performs complete, non-overlapping coverage.

Original languageEnglish (US)
Title of host publicationDistributed Autonomous Robotic Systems - The 12th International Symposium
EditorsYoung-Jo Cho, Nak-Young Chong
PublisherSpringer Verlag
Pages33-48
Number of pages16
ISBN (Print)9784431558774
DOIs
StatePublished - 2016
Event12th International Symposium on Distributed Autonomous Robotic Systems, DARS 2014 - Daejeon, Korea, Republic of
Duration: Nov 2 2014Nov 5 2014

Publication series

NameSpringer Tracts in Advanced Robotics
Volume112
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

Other

Other12th International Symposium on Distributed Autonomous Robotic Systems, DARS 2014
Country/TerritoryKorea, Republic of
CityDaejeon
Period11/2/1411/5/14

Keywords

  • Coverage path planning
  • Multi-robot systems
  • Voronoi partitioning

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'A repartitioning algorithm to guarantee complete, non-overlapping planar coverage with multiple robots'. Together they form a unique fingerprint.

Cite this