Distributed Voronoi partitioning for multi-robot systems with limited range sensors

K. R. Guruprasad, Prithviraj Dasgupta

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

22 Scopus citations


We consider the problem of distributed partitioning of an environment by a set of robots so that each robot performs its operations in the region within the corresponding cell. Voronoi partitioning is one of the most attractive techniques that has been used to solve this problem. It has been used in several distributed multi-robotic system and sensor network applications, such as sensor coverage, search and rescue, and coverage path planning. For a truly distributed implementation of such problems, each robot should be able to compute the corresponding Voronoi cell in a distributed manner. Further, in a practical application, the robots' sensors may have limited range, thus each robot may operate within a portion of its Voronoi cell constrained by the sensor range. We describe a distributed algorithm for computation of this range constrained Voronoi cell where each robot independently constructs chords corresponding to other robots that are within a distance of twice its sensor circle radius. A robot then uses a simple and fast technique to remove inessential chords to calculate the vertices of its Voronoi cell. We prove completeness and correctness of the proposed algorithm, and also provide the upper and lower bounds on the computational complexity of our algorithm. The theoretical results are validated with the help of experiments to show that for different values of sensor ranges, our proposed algorithm incurs a time complexity that is significantly lower than that of the existing full Voronoi partition computation algorithm. The maximum number of steps required by our algorithm is also shown to be within a constant times the lower bound given by the number of neighbors of each node.

Original languageEnglish (US)
Title of host publication2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2012
Number of pages7
StatePublished - 2012
Event25th IEEE/RSJ International Conference on Robotics and Intelligent Systems, IROS 2012 - Vilamoura, Algarve, Portugal
Duration: Oct 7 2012Oct 12 2012

Publication series

NameIEEE International Conference on Intelligent Robots and Systems
ISSN (Print)2153-0858
ISSN (Electronic)2153-0866


Conference25th IEEE/RSJ International Conference on Robotics and Intelligent Systems, IROS 2012
CityVilamoura, Algarve

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Computer Vision and Pattern Recognition
  • Computer Science Applications


Dive into the research topics of 'Distributed Voronoi partitioning for multi-robot systems with limited range sensors'. Together they form a unique fingerprint.

Cite this