Abstract

Abstract: One of the main applications of mobile robots is coverage: visiting each location in known terrain. Coverage is crucial for lawn mowing, cleaning, harvesting, search-and-rescue, intrusion detection and mine clearing. Naturally, coverage can be sped up with multiple robots. However, we show that solving several versions of multi-robot coverage problems with minimal cover times is NP-hard, which provides motivation for designing polynomial-time constant-factor approximation algorithms. We then describe Multi-Robot Forest Coverage (MFC), a new polynomial-time multi-robot coverage algorithm based on an algorithm by Even et al. for finding a tree cover with trees of balanced weights. Our theoretical results show that the cover times of MFC in weighted and unweighted terrain are at most about a factor of 16 larger than minimal. Our simulation results show that the cover times of MFC are close to minimal in all tested scenarios and smaller than the cover times of an alternative multi-robot coverage algorithm.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.