Efficient Boustrophedon Multi-Robot Coverage: an algorithmic approach

This paper presents algorithmic solutions for the complete coverage path planning problem using a team of mobile robots. Multiple robots decrease the time to complete the coverage, but maximal efficiency is only achieved if the number of regions covered multiple times is minimized. A set of multi-ro...

Full description

Saved in:
Bibliographic Details
Published in:Annals of mathematics and artificial intelligence 2008-04, Vol.52 (2-4), p.109-142
Main Authors: Rekleitis, Ioannis, New, Ai Peng, Rankin, Edward Samuel, Choset, Howie
Format: Article
Language:English
Subjects:
Algorithms
Allocations
Artificial Intelligence
Communication
Complex Systems
Computational efficiency
Computer Science
Constrictions
Expert systems
Line of sight communication
Mathematical analysis
Mathematics
Multiple robots
Robots
Tasks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents algorithmic solutions for the complete coverage path planning problem using a team of mobile robots. Multiple robots decrease the time to complete the coverage, but maximal efficiency is only achieved if the number of regions covered multiple times is minimized. A set of multi-robot coverage algorithms is presented that minimize repeat coverage. The algorithms use the same planar cell-based decomposition as the Boustrophedon single robot coverage algorithm, but provide extensions to handle how robots cover a single cell, and how robots are allocated among cells. Specifically, for the coverage task our choice of multi-robot policy strongly depends on the type of communication that exists between the robots. When the robots operate under the line-of-sight communication restriction, keeping them as a team helps to minimize repeat coverage. When communication between the robots is available without any restrictions, the robots are initially distributed through space, and each one is allocated a virtually-bounded area to cover. A greedy auction mechanism is used for task/cell allocation among the robots. Experimental results from different simulated and real environments that illustrate our approach for different communication conditions are presented.
ISSN:1012-2443
1573-7470
DOI:10.1007/s10472-009-9120-2