Competitive Connected Multi-robot Exploration of Unknown Graphs

Abstract

Multi-robot graph exploration is a central problem in robotics, planning, and multi-agent systems. In this work, we consider the problem of exploring an unknown n-node graph by k robots that must remain connected throughout the process. Such a connectivity is frequently required for safety reasons, and naturally arises in real-world applications such as search-and-rescue and maintenance operations. We study the overhead imposed by not knowing the graph in advance, measured in terms of the competitive ratio of the number of exploration rounds necessary when the graph is unknown (versus the case that it is known). We introduce a novel exploration procedure, DFS-BGS, to tackle the problem, and analyze its performance both theoretically and experimentally. On the theoretical end, DFS-BGS provably achieves a competitive ratio O(k^(1/3)), for the case n < k. Empirically, we compare our online DFS-BGS to COCTA, the SOTA algorithm for trees that are known in advance. Examining the performance of the algorithms on real-world hotel floor plans as well as random graphs over a wide range of parameters, DFS-BGS incurs only a small slowdown, even with hundreds of robots and thousands of nodes.