Online Multi-Robot Coverage: Algorithm Comparisons

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.