Improved tree exploration method for multiple moving agents
Polylogarithmic Collective Tree Exploration
Data Structures and Algorithms
Summary
This work looks at how a group of agents can explore an unknown tree structure where they only discover parts of it as they move. It studies a situation where agents do not move simultaneously but one at a time, controlled by an adversary. The authors provide a new method that guarantees exploration using a number of moves close to the best possible, even in the worst cases. Their approach also leads to better performance when all agents move together at the same time. They introduce a mathematical tool that helps achieve these results.
What this means in practice
- •For network schedulers: Design protocols to explore unknown network topologies efficiently despite delays and adversarial message scheduling.
- •For robotics teams: Plan coordinated exploration strategies for multiple robots in unknown environments where robot movement may be asynchronous and controlled.
A theory result. No direct application yet.
Authors
Romain Cosson, Laurent Massoulié
Abstract
We study asynchronous collective tree exploration, where $k$ agents with unrestricted communication start at the root of an unknown tree and discover edges online. At each step, an adversary chooses which agent moves. We give a deterministic algorithm that explores any tree with $n$ nodes and depth $D$ in at most \[ 2n+O\left(k\log^2(k)D\right) \] moves, matching known lower bounds up to a constant factor. As a direct consequence, we obtain a near-optimal competitive ratio of $O(\log^2 k)$ for synchronous collective tree exploration, where all agents move at each round. The proof relies on a multiscale power regularizer that may be of independent interest.