Asynchronous Collective Tree Exploration by Tree-Mining

We investigate the problem of collaborative tree exploration with complete communication introduced by [FGKP06], in which a group of $k$ agents is assigned to collectively go through all edges of an unknown tree in an efficient manner and then return to the origin. The agents have unrestricted communication and computation capabilities. The algorithm's runtime is typically compared to the cost of offline traversal, which is at least $\max\{2n/k,2D\}$ where $n$ is the number of nodes and $D$ is the tree depth. Since its introduction, two types of guarantee have emerged on the topic: the first is of the form $r(k)(n/k+D)$, where $r(k)$ is called the competitive ratio, and the other is of the form $2n/k+f(k,D)$, where $f(k,D)$ is called the competitive overhead. In this paper, we present the first algorithm with linear-in-$D$ competitive overhead, thereby reconciling both approaches. Specifically, our bound is in $2n/k + O(k^{\log_2 k} D)$ and thus leads to a competitive ratio in $O(k/\exp(0.8\sqrt{\ln k}))$. This is the first improvement over the $O(k/\ln k)$-competitive algorithm known since the introduction of the problem in 2004. Our algorithm is obtained for an asynchronous generalization of collective tree exploration (ACTE). It is an instance of a general class of locally-greedy exploration algorithms that we define. We show that the additive overhead analysis of locally-greedy algorithms can be seen through the lens of a 2-player game that we call the tree-mining game and that could be of independent interest.