Online Multi-Robot Coverage: Algorithm Comparisons

Abstract

We consider the common assumptions made when multi-robot systems are used for exploration and coverage and the metrics used to compare performance. We then take three algorithms -- the Rolling Dispersion Algorithm (RDA), the Multi-Robot Depth-First-Search (MR-DFS) algorithm, and the BoB algorithm -- chosen for their different strengths and assumptions, and compare, using a set of common metrics, their performance in different simulation environments. We present two simple extensions to RDA -- RDA-MS (multi-start) and RDA-EC (extended communication), which preserve RDA's original assumptions, but are able to perform as well as the algorithms that make more demanding assumptions.