Collective Tree Exploration with Predictions
Organizations: Computer Science Department, Courant Institute, New York University. · John A. Paulson School of Engineering and Applied Science, Harvard University. · Rutgers University.
Abstract
We study collective tree exploration with subtree-size predictions. In this problem, a team of mobile agents needs to explore an unknown rooted tree as fast as possible, and whenever a new vertex is discovered, the team receives a prediction of the number of nodes in the subtree rooted at . We provide algorithmic guarantees under two error measures: the maximum error and the multiplicative distortion . For the maximum error, we present a deterministic algorithm that explores any tree with nodes and depth in rounds, where is the offline benchmark, and we show that there is no deterministic algorithm that admits an guarantee. For the multiplicative distortion, we present several algorithms that induce a competitive ratio in , where the may hide logarithmic factors in .
Figures & tables
| Method | Threshold evolution | Exploration within a layer | Competitive ratio |
|---|---|---|---|
| Baseline ( Section 4.1 ) | Halve each time | One robot per component | |
| Adaptive teams ( Section 4.2 ) | Halve each time | Adaptive team sizes . | |
| Aggressive exploration ( Section 4.3 ) | Quota-dependent large jumps | PowerScatter then adaptive tail. |
Tree Search
Tree Search explores branching sequences of actions or decisions to find high-quality solutions under limits on time, memory, or computation.
See all 64 papers