GM-VPC: An Algorithm for Multi-robot Coverage of Known Spaces Using Generalized Voronoi Partition

Vishnu G. Nair, K. R. Guruprasad

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


In this paper we address the problem of coverage path planning (CPP) for multiple cooperating mobile robots. We use a 'partition and cover' approach using Voronoi partition to achieve natural passive cooperation between robots to avoid task duplicity. We combine two generalizations of Voronoi partition, namely geodesic-distance-based Voronoi partition and Manhattan-distance-based Voronoi partition, to address contiguity of partition in the presence of obstacles and to avoid partition-boundary-induced coverage gap. The region is divided into 2D×2D grids, where D is the size of the robot footprint. Individual robots can use any of the single-robot CPP algorithms. We show that with the proposed Geodesic-Manhattan Voronoi-partition-based coverage (GM-VPC), a complete and non-overlapping coverage can be achieved at grid level provided that the underlying single-robot CPP algorithm has similar property.We demonstrated using two representative single-robot coverage strategies, namely Boustrophedon-decomposition-based coverage and Spanning Tree coverage, first based on so-called exact cellular decomposition and second based on approximate cellular decomposition, that the proposed partitioning scheme completely eliminates coverage gaps and coverage overlaps. Simulation experiments using Matlab and V-rep robot simulator and experiments with Fire Bird V mobile robot are carried out to validate the proposed coverage strategy.

Original languageEnglish
Publication statusPublished - 01-05-2020

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Mathematics(all)
  • Computer Science Applications


Dive into the research topics of 'GM-VPC: An Algorithm for Multi-robot Coverage of Known Spaces Using Generalized Voronoi Partition'. Together they form a unique fingerprint.

Cite this