Statistical analysis of stochastic multi-robot boundary coverage

Ganesh P. Kumar, Spring Berman

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

5 Scopus citations


We present a novel analytical approach to computing the population and geometric parameters of a multi-robot system that will provably produce specified boundary coverage statistics. We consider scenarios in which robots with no global position information, communication, or prior environmental data have arrived at uniformly random locations along a simple closed or open boundary. This type of scenario can arise in a variety of multi-robot tasks, including surveillance, collective transport, disaster response, and therapeutic and imaging applications in nanomedicine. We derive the probability that a given point robot configuration is saturated, meaning that all pairs of adjacent robots are no farther apart than a specified distance. This derivation relies on a geometric interpretation of the saturation probability and an application of the Inclusion-Exclusion Principle, and it is easily extended to finite-sized robots. In the process, we obtain formulas for (a) an integral that is in general computationally expensive to compute directly, and (b) the volume of the intersection of a regular simplex with a hypercube. In addition, we use results from order statistics to compute the probability distributions of the robot positions along the boundary and the distances between adjacent robots. We validate our derivations of these probability distributions and the saturation probability using Monte Carlo simulations of scenarios with both point robots and finite-sized robots.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE International Conference on Robotics and Automation
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)9781479936854, 9781479936854
StatePublished - Sep 22 2014
Event2014 IEEE International Conference on Robotics and Automation, ICRA 2014 - Hong Kong, China
Duration: May 31 2014Jun 7 2014

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729


Other2014 IEEE International Conference on Robotics and Automation, ICRA 2014
CityHong Kong

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering


Dive into the research topics of 'Statistical analysis of stochastic multi-robot boundary coverage'. Together they form a unique fingerprint.

Cite this