Collective Tree Exploration with Predictions

Romain Cosson, Yichen Huang, Michael Mitzenmacher, Ali VakilianarXiv 2026 · arXiv

TL;DR

This paper provides the first theoretical framework for Collective Tree Exploration (CTE) using subtree-size predictions. The authors develop algorithms that achieve near-optimal exploration times when predictions are accurate and degrade gracefully as errors increase, establishing fundamental performance bounds for both additive and multiplicative prediction error models.

What Problem Does This Paper Address?

In robotics and AI, coordinating a team of $k$ agents to explore an unknown environment—modeled here as a rooted tree—is a classic challenge. The goal is to visit every node as quickly as possible. While the offline version (knowing the map in advance) is well-understood, the online version is difficult because agents must decide how to partition unexplored regions in real-time without knowing what lies ahead.

In practice, robots often have "side information" like coarse floor plans or occupancy map estimates from machine learning models. However, classical "competitive analysis" usually ignores this information, focusing only on the worst-case scenario. This paper bridges that gap by applying the learning-augmented algorithms framework to CTE. It asks: If we are given (potentially inaccurate) estimates of how many nodes are in each subtree, how much faster can we explore?

Methods

The authors analyze two primary error measures for predictions ($\hat{n}_u$) of actual subtree sizes ($n_u$):

  1. Maximum Additive Error ($E$): The largest absolute difference $|\hat{n}_u - n_u|$ across all nodes.
  2. Multiplicative Distortion ($\mu$): The maximum factor by which a prediction overestimates or underestimates the true size.

The Seed-and-Sweep Algorithm (Additive Error)

For additive errors, the authors propose SEED-AND-SWEEP.

  • Phase 1 (Seed): Robots use a "Biased Rounding Seeding" procedure to move to specific nodes (seeds) deep in the tree. The key innovation is a rounding rule that prevents prediction errors from compounding as robots move further from the root.
  • Phase 2 (Sweep): Each robot performs a depth-first search (DFS) starting from its seed, eventually backtracking to the root to pick up any branches missed by others.
Figure 1: Seed and sweep. In the sweep panel, each edge is styled according to the first robot that traverses it: solid orange for s1, dashed blue for s2, and dash-dotted purple for s3.

The Skeleton Framework (Multiplicative Error)

For multiplicative distortion, the authors introduce the concept of $\tau$-skeletons—the connected part of the tree where all nodes have a predicted size of at least $\tau$.

Figure 2: A $\tau$-skeleton (blue) and the threshold components (orange) revealed by lowering the threshold to $\tau' < \tau$.

The algorithm explores the tree in successive "waves" by iteratively lowering the threshold $\tau$. It uses "Adaptive Teams" to explore the components between skeletons, effectively treating them as unknown sub-problems while using the skeleton as a roadmap to allocate robots efficiently.

Datasets

Not discussed in the paper. This is a theoretical work focused on algorithmic proofs and complexity analysis rather than empirical testing on specific datasets.

Key Insights and Ideas

  • Rounding is Critical: In the additive model, a naive proportional allocation of robots based on predictions fails because small errors at every branching point can lead to massive misallocations deep in the tree. The authors' Biased Rounding ensures that the error in the number of robots assigned to any subtree remains a constant, regardless of the tree's depth.
  • Predictions Replace Communication: Interestingly, the authors show that under bounded additive error, predictions can effectively replace the need for robots to communicate. Robots can "guess" where others are going based on the shared predictions, achieving a performance that previously required active coordination.
  • Skeleton-Based Acceleration: For multiplicative errors, the skeleton framework allows the team to focus on "heavy" subtrees first. By aggressively jumping between threshold levels, they can achieve a competitive ratio that scales with the square root of the distortion ($\sqrt{\mu}$), significantly better than a linear dependence on $\mu$.

Key Results

  • Additive Error: The algorithm completes exploration in $O(OPT + E)$ rounds, where $OPT$ is the optimal offline time. The authors also prove a lower bound showing that no deterministic algorithm can achieve $O(OPT) + o(E)$, making their result essentially tight.
  • Multiplicative Distortion: The authors provide an algorithm with a competitive ratio of $\tilde{O}(\min\{ \sqrt{\mu} \log k, \mu \log \log k + \mu^{1.5} \})$. This represents a significant improvement over the best-known prediction-free algorithms ($O(\log^2 k)$) when predictions are reasonably accurate.
  • Consistency: When predictions are perfect ($\mu=1$ or $E=0$), the algorithms recover the optimal offline performance of $\Theta(n/k + D)$.

Limitations and Future Work

  • Multiplicative Gap: The authors suspect the dependence on $\mu$ can be further improved, potentially reaching a ratio that depends only on $\mu$ and not on the number of agents $k$.
  • Finer-Grained Additive Bounds: The current additive result hides a constant factor on $OPT$. Future work could aim for a more precise bound like $2n/k + O(D + E)$.
  • Stochastic Models: This paper assumes worst-case (adversarial) errors. Exploring how algorithms perform when errors follow a specific distribution (e.g., Gaussian) remains an open question.
  • Asynchronous Environments: The current model assumes synchronous rounds; extending this to asynchronous settings where robots might move at different speeds or fail is a natural next step.

Summary updated

Abstract

We study collective tree exploration with subtree-size predictions. In this problem, a team of $k$ mobile agents needs to explore an unknown rooted tree as fast as possible, and whenever a new vertex $u$ is discovered, the team receives a prediction $\hat n_u$ of the number of nodes $n_u$ in the subtree rooted at $u$. We provide algorithmic guarantees under two error measures: the maximum error $E=\max_u|\widehat n_u-n_u|$ and the multiplicative distortion $μ= (\max_u\widehat n_u/n_u)(\max_u n_u/\widehat n_u)$. For the maximum error, we present a deterministic algorithm that explores any tree with $n$ nodes and depth $D$ in $O(\text{OPT}+E)$ rounds, where $\text{OPT} = Θ(n/k+D)$ is the offline benchmark, and we show that there is no deterministic algorithm that admits an $O(\text{OPT})+o(E)$ guarantee. For the multiplicative distortion, we present several algorithms that induce a competitive ratio in $\widetilde O(\min\{ \sqrtμ\log k, μ\log\log k+μ^{1.5} \})$, where the $\widetilde O(\cdot)$ may hide logarithmic factors in $μ$.
BibTeX
@misc{cosson2026collective,
  author = {Romain Cosson and Yichen Huang and Michael Mitzenmacher and Ali Vakilian},
  title = {{Collective Tree Exploration with Predictions}},
  year = {2026},
  eprint = {2611.17482},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17482},
}
Figure