Multi-robot forest coverage

One of the main applications of mobile robots is terrain coverage: visiting each location in known terrain. 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. In this paper, we describe multi-robot forest coverage, a new multi-robot coverage algorithm based on an algorithm by Even et al. (2004) for finding a tree cover with trees of balanced weights. The cover time of multi-robot forest coverage is at most eight times larger than optimal, and our experiments show it to perform significantly better than existing multi-robot coverage algorithms.

Authors

• Xiaoming Zheng
• Sonal Jain
• Sven Koenig
• David Kempe 0001

Keywords

• Tree graphs
• Polynomials
• Mobile robots
• Cleaning
• Intrusion detection
• Costs
• Computer science
• Application software
• Electrical capacitance tomography
• Multi-robot Coverage
• Multiple Robots
• Lawnmower
• Small Cell
• Large Cell
• Travel Costs
• Thick Line
• Root Of The Tree
• Subtree
• Polynomial-time Algorithm
• Ideal Time
• Binary Search
• Spanning Tree
• Maximum Matching
• Coverage Problem
• Largest Cost
• Grid Graph
• Cell Decomposition
• Robot Teams
• Spanning Tree Coverage
• Terrain Coverage