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 \emph{overhead} imposed by not knowing the graph in advance, measured in terms of the \emph{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, \textsf{DFS-BGS}, to tackle the problem, and analyze its performance both theoretically and experimentally. On the theoretical end, \textsf{DFS-BGS} provably achieves a competitive ratio $\tilde{\mathcal{O}}(k^{1/3})$, for the case $n\leq k$. Empirically, we compare our online $\textsf{DFS-BGS}$ to $\textsf{COCTA}$~\cite{sinay2017maintaining}, 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, $\textsf{DFS-BGS}$ incurs only a small slowdown, even with hundreds of robots and thousands of nodes.