Comparison of Online Exploration and Coverage Algorithms in Continuous Space

We propose a framework to compare algorithms for multi agent exploration in an unknown continuous 2d environment. To analyze trade offs we compare algorithms with varying robot hardware requirements. We showcase our approach on Random Ballistic Walk (RBW), frontier-based exploration (The Next Frontier, TNF), Spiraling and Selective Backtracking (SSB), and Local Voronoi Decomposition (LVD). Algorithms that operate in a discrete grid-based space, such as LVD and SSB, are mapped to a continuous space for comparison with other algorithms. To our knowledge, no other extensive comparison of these exploration algorithms operating under the same testing environment has been conducted. The algorithms are tested in a custom 2D physics-driven simulation (Multi Agent Exploration Simulator, MAES), with two types of maps, namely the Cave map (C-Map) and the Building map (B-Map). The performance of each algorithm is evaluated in terms of coverage and exploration of the map. Results show that SSB performed the best in terms of coverage in all tested scenarios. TNF performed the best in terms of exploration, especially on bigger maps.
RBW achieved good results in terms of both coverage and exploration in C-Maps, but not in B-Maps. LVD performed similarly to RBW in C-Maps, but better in the B-Maps.