Xiaoming Zheng, Sven Koenig, David Kempe and Sonal Jain. Multi-Robot Coverage of Weighted and Unweighted Terrain. IEEE TRANSACTIONS ON ROBOTICS (submitted),2008

Abstract: One of the main applications of mobile robots is terrain coverage: visiting each location in known terrain. Coverage is crucial for lawn mowing, cleaning, harvesting, search-andrescue, intrusion detection and mine clearing. Naturally, coverage can be sped up with multiple robots. In this article, we describe Multi-Robot Forest Coverage (MFC), a new multi-robot coverage algorithm based on a tree-cover algorithm by Even et al. for finding a tree cover with trees of balanced weights. We then extend MFC and an alternative existing multi-robot coverage algorithm from unweighted terrain to weighted terrain. Our theoretical results show that the cover times of MFC in weighted and unweighted terrain are at most a factor of about sixteen and eight, respectively, larger than minimal. Our experimental results show that the cover times of MFC are close to minimal in all tested scenarios and smaller than those of the alternative multi-robot coverage algorithm.

Paper is available upon request.