Mobility Matters
Home›Mobile agents on graphs›Exploration›Collaborative exploration

Collaborative exploration

\(k\) agents start together at the root of an unknown graph and must visit all its nodes; how much faster than one agent can a team be?

Problem statement and measurescollapse
sssssssssss123Start: k = 3 agents at the root s of an unknown treeEach agent takes a different unexplored edgeNo unexplored edge here: step back towards sBack at s, agent 2 is sent to the shallowest unfinished nodeDepth next: explore below the anchor, then go back upFinal: every node visited, all agents back at s after 10 rounds
Collective tree exploration Fraigniaud et al. 2006, here by Breadth-First Depth-Next Cosson et al. 2023: \(k = 3\) agents start at the root \(s\) of an unknown tree and share one map. An agent at the root is sent to the shallowest node with an unexplored edge (its anchor); from there it walks down unexplored edges that no other agent takes in that round, and steps back towards the root when there is none. One frame per round; the time is compared with the offline optimum \(\Theta(n/k + D)\).

A team of \(k\) distinguishable agents starts at a node \(s\) (the root) of an unknown connected graph with \(n\) nodes; \(D\) is the largest distance from \(s\). In synchronous rounds every agent traverses at most one edge. When an agent reaches a node it sees the incident edges. The team must visit every node (some papers also require all agents to return to \(s\); the bounds coincide asymptotically).

Time is the number of rounds (in the asynchronous model: the total number of moves). The offline optimum is \(\Theta(n/k + D)\), so an algorithm that explores every tree in \(\mathrm{CR}(k)\cdot(n/k+D)\) rounds is called \(\mathrm{CR}(k)\)-competitive; a single depth-first search is \(O(k)\)-competitive. Memory is bits per agent; most of this literature lets it be unbounded.

Unless a variant says otherwise, nodes are labelled (an agent recognises a node it has seen), which is the standard assumption of collective tree exploration; on trees it does not matter for lower bounds Disser et al. 2020. With anonymous nodes and \(k = n\), the problem is solved by rooted dispersion.

Measures: Time, rounds until every node is visited (asynchronous: total moves); Memory, bits per agent.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine \(k\) rescuers entering a cave system through one entrance; they want every chamber checked as soon as possible. We model the cave as a graph: chambers are nodes, tunnels between two chambers are edges, and each rescuer is an agent. The cave is a tree (a graph without cycles, so there is exactly one route between any two nodes) with \(n\) nodes; the entrance is its root \(s\), and the depth \(D\) is the largest distance from \(s\). All \(k\) agents start at \(s\); time passes in rounds, and in each round every agent may walk along one edge. Nodes are labelled (an agent recognises a node it has seen before), and an agent at a node sees the edges leaving it. In the basic version all agents share everything they learn (global communication), so they act on one map: the part of the tree seen so far. The team must visit every node; the time is the number of rounds, and an algorithm is judged by how close it gets to the best possible time of about \(n/k + D\) rounds.

1AlgorithmBreadth-First Depth-Next Trees, complete communication → Cosson et al. 2023

The algorithm BFDN of Cosson et al. 2023. Call an edge unexplored if it has been seen but no agent has walked it yet (the paper calls it dangling).

  1. When an agent is at the root, give it an anchor: a node of the map with an unexplored edge, preferring nodes closest to the root and, among those, the ones with the fewest agents already anchored there.
  2. The agent walks along the map to its anchor.
  3. From there it does a depth-first search: if an unexplored edge leaves its node and no other agent has chosen it this round, it takes it; otherwise it steps one edge back towards the root.
  4. Back at the root it gets a new anchor. The team stops when all agents are at the root and no unexplored edge is left.
Why it works and what it costs. Each agent mostly does what a single agent exploring alone does (walk down unexplored edges, back up when stuck), and the anchors spread the team over the shallowest unfinished parts of the tree. Cosson et al. 2023 prove a time of \(\tfrac{2n}{k} + D^2(\min\{\log\Delta,\log k\}+2)\) rounds, where \(\Delta\) is the maximum degree; the \(2n/k\) term is what \(k\) agents need just to walk every edge twice. The best known algorithm today takes \(\tfrac{2n}{k} + O(D\log^2 k)\) rounds Cosson & Massoulié 2026.

Why it matters. Its analysis through a simple game against an adversary opened the series of papers that brought the overhead from roughly a factor \(k/\log k\) down to polylogarithmic in \(k\).

2Lower boundEven knowing the tree: n/k + D Trees, complete communication → Cosson et al. 2023

Suppose the agents knew the whole tree in advance. Two things still take time.

  1. Some agent must reach the deepest node, which is \(D\) edges from the root: at least \(D\) rounds.
  2. Each of the \(n-1\) nodes other than the root must be entered for the first time by some agent, and in one round \(k\) agents enter at most \(k\) nodes: at least \((n-1)/k\) rounds.
Why it holds. So no algorithm beats about \(\max\{n/k, D\}\), which is at least half of \(n/k + D\). Knowing the tree, this is also achievable up to a factor 2: cut a depth-first tour of the tree (length \(2(n-1)\)) into \(k\) pieces of length \(2(n-1)/k\) and send one agent to each piece, for \(2(n/k + D)\) rounds in total, as recalled in Cosson et al. 2023. An online algorithm (one that discovers the tree as it goes) that is always within a factor \(\mathrm{CR}(k)\) of \(n/k + D\) is called \(\mathrm{CR}(k)\)-competitive; a single depth-first search by one agent is \(O(k)\)-competitive.

Why it matters. This simple yardstick is what every result on collaborative exploration is measured against.

3Lower boundAn adversary that grows the tree Trees, complete communication → Disser et al. 2020

When the tree is not known in advance, it is revealed only where agents stand, so one can imagine an adversary (an opponent who builds the worst input) drawing the tree during the run. When the agents reach a node, the adversary decides how many children it has. Whatever way the agents split up, the adversary can make the long branches continue where few agents went and end the branches that received many agents. The full proof that this costs a factor \(\Omega(\log k/\log\log k)\) is longer Disser et al. 2020.

Why it holds. Every deterministic algorithm takes \(\Omega\big(\tfrac{\log k}{\log\log k}(\tfrac nk + D)\big)\) rounds on some tree, even with global communication and unlimited memory Disser et al. 2020; it was first shown by Dynia et al. 2007 for \(k < \sqrt n\). The best algorithm is \(O(\log^2 k)\)-competitive Cosson & Massoulié 2026, so the remaining gap is between \(\log k/\log\log k\) and \(\log^2 k\).

Why it matters. It refuted the hope of a constant competitive ratio and shows that not knowing where the work is costs something no amount of communication can repair.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Memory
Arbitrary graphs, complete communication
On graphs with cycles it is not even known whether any algorithm beats depth-first search by more than a constant.
unknown \(\tfrac{2n}{k}+D^2(\min\{\log\Delta,\log k\}+2)\) vs —
unknown — vs —
Trees, complete communication standard
Collective tree exploration as posed by Fraigniaud, Gąsieniec, Kowalski and Pelc: the competitive ratio is now between \(\Omega(\log k/\log\log k)\) and \(O(\log^2 k)\).
near-optimal \(\tfrac{2n}{k}+O(D\log^2 k)\) vs \(\Omega\big(\tfrac{\log k}{\log\log k}\,(\tfrac nk + D)\big)\) online tree revelation
unknown — vs —
Trees with \(k = n\) agents
With as many agents as nodes, \(D^2\) rounds suffice, and some trees need \(D^2/3\); this is the bound dispersion inherits.
polynomial gap \(D^2\) vs \(D^2/3\) online tree revelation
unknown — vs —
Large teams, complete communication
With \(k = Dn^{\gamma}\) agents (\(\gamma>1\)), exploration takes \(D(1+\tfrac1{\gamma-1}+o(1))\) rounds, almost the trivial \(D\).
tight \(D(1+\tfrac{1}{\gamma-1}+o(1))\) vs \(D(1+\tfrac1{\gamma}-o(1))\) distance
unknown — vs —
Trees, asynchronous, complete communication
An adversary chooses which agent moves; the cost is the total number of moves, and the optimal regret is \(\Theta(\log^2 k)\) per unit of depth.
tight \(2n+O(kD\log^2 k)\) vs \(\Omega(\log^2 k)\cdot(n+kD)\) adversarial activation
unknown — vs —
Trees, communication by whiteboards only
Agents talk only by writing at the node they occupy; the original algorithm still gives \(O(k/\log k)\).
polynomial gap \(O(D + n/\log k)\) vs —
unknown — vs —
Trees, asynchronous, whiteboards only
The fully distributed asynchronous setting: the first competitive algorithm appeared in 2025.
polynomial gap \(2n+O(k^2 2^k D)\) vs —
unknown — vs —
Trees, no communication
Without any communication, \(k\) agents are no faster than one.
tight \(O(k)\cdot\text{optimal}\) vs \(\Omega(k)\cdot\text{optimal}\) no information sharing
unknown — vs —
Large teams, local communication
If agents only talk when they meet, large teams still explore in \(O(D)\) rounds, and the price of locality is visible in the constant.
tight \(D(1+\tfrac{2}{\gamma-1}+o(1))\) vs \(D(1+\tfrac2c-o(1))\) locality of communication
unknown — vs —
Anonymous graphs, a team of constant-memory agents
\(\Theta(\log\log n)\) agents with constant memory are necessary and sufficient to explore any anonymous graph.
unknown \(n^{O(1)}\) vs —
tight \(O(1)\ \text{bits each},\ O(\log\log n)\ \text{agents}\) vs \(\Omega(\log\log n)\ \text{agents}\) trap graphs
Anonymous graphs with \(k = n\) agents
Nodes cannot be recognised and agents only talk when co-located: \(n\) agents explore by dispersing, in \(O(n)\) rounds with \(O(\log n)\) bits each.
tight \(O(n)\) vs \(\Omega(n)\) distance
unknown \(O(\log n)\) vs —

Open questions 8

Arbitrary graphs, complete communication

  1. Is there an \(o(k)\)-competitive collaborative exploration algorithm for arbitrary graphs? (Stated as open in Cosson & Massoulié 2026.)

Trees, complete communication

  1. Determine the competitive ratio of synchronous collective tree exploration: between \(\Omega(\log k/\log\log k)\) and \(O(\log^2 k)\).
  2. Do randomized algorithms help? A randomized lower bound of \(\Omega(\sqrt{\log k}/\log\log k)\) is attributed to Ortolf and Schindelhauer (SPAA 2012), not checked here. Cosson and Massoulié conjecture they do not Cosson & Massoulié 2025.

Trees with \(k = n\) agents

  1. For \(k=n\) and trees of depth \(D\) well above \(\sqrt{\log n}\) (e.g. \(D=\sqrt n\)), is \(\Omega(D^2)\) still necessary?

Large teams, complete communication

  1. Which team size is necessary and sufficient for \(O(D)\)-round exploration of graphs of larger diameter? (Stated in Dereniowski et al. 2015.)

Trees, communication by whiteboards only

  1. Is there a separation between write-read and complete communication? Cosson & Massoulié 2025 conjecture that centralised communication helps.

Trees, asynchronous, whiteboards only

  1. Is there a distributed asynchronous algorithm with polylogarithmic competitive ratio?

Anonymous graphs with \(k = n\) agents

  1. Can \(n\) agents explore an anonymous tree in \(o(n)\) rounds, e.g. \(O(D^2)\), with local communication? With labelled nodes and global communication \(D^2\) suffices Disser et al. 2020.

What the community started looking at

Collaborative exploration asked a different question from the single-agent line: not how little memory, but how much faster \(k\) agents can be than one. Fraigniaud, Gąsieniec, Kowalski and Pelc measured an algorithm by its competitive ratio against the offline optimum \(\Theta(n/k + D)\) and showed that communication matters: without it, \(k\) agents gain nothing Fraigniaud et al. 2006. The following twenty years were spent narrowing the ratio from \(O(k/\log k)\) towards the \(\Omega(\log k/\log\log k)\) lower bound Dynia et al. 2007 Disser et al. 2020 Cosson & Massoulié 2024, and on what very large teams can do Dereniowski et al. 2015.

Derived problems

Dispersion: With \(k = n\) agents, a dispersed configuration has an agent on every node, so any dispersion algorithm solves \(n\)-agent collaborative exploration under the same assumptions Augustine & Moses Jr. 2018. Consequently every lower bound for \(n\)-agent exploration is a lower bound for dispersion (this is how the \(\Omega(D^2)\) tree bound of Disser et al. 2020 enters), and every dispersion algorithm is an exploration algorithm for anonymous graphs with local communication. For \(k < n\) dispersion asks for less: only \(k\) nodes must be occupied.

Black hole search: Locating the black hole means exploring every other node safely, so black hole search is exploration of a dangerous graph by a team, where agents can be lost.

Exploration of dynamic graphs by teams: When an adversary removes edges, a single agent can be blocked forever; the question shifts from speed to how many agents are needed to visit every node.

Perspectives

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • Finding your way A single agent in an anonymous graph: how much memory it needs, what a pebble, an advice string or knowledge of n buys, why stopping is harder than exploring, and how treasure hunt asks for exploration only as far as the target. Each line of papers, in its own words, on why the question matters.
  • From exploration to dispersion, and beyond How collaborative exploration asks how much a team speeds up a search, how dispersion arose as the case k = n under weaker assumptions, what dispersion gives back to exploration, and why dispersing first has become the standard opening move for computing graph structures with agents.
  • What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.
  • The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.

All settings

The assumption tree (11 settings, 5 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Memory); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Node identifiers › Randomness › Communication › Node memory › Timing › Team size › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Team size

0any number \(k\) of agents1\(k = n\) agents1large teams, \(k \ge D\,n^{1+\varepsilon}\)

Fraigniaud, Gąsieniec, Kowalski and Pelc posed collective tree exploration for any number \(k\) of agents and measured algorithms by their competitive ratio against the offline optimum Fraigniaud et al. 2006. Two team sizes then turned out to have sharper answers than arbitrary \(k\). For large teams, Dereniowski, Disser, Kosowski, Pająk and Uznański explore in \(O(D)\) rounds with \(k=Dn^{1+\varepsilon}\) agents, a constant competitive ratio, and Disser, Mousset, Noever, Steger and Škorić showed that \(k=Dn^{1+o(1)}\) agents do not suffice for that, so the threshold is essentially tight Dereniowski et al. 2015 Disser et al. 2020. For \(k=n\), Disser et al. gave a simple algorithm taking \(D^2\) rounds on every tree and showed that trees of arbitrarily large height need \(\Omega(D^2)\) rounds Disser et al. 2020. This team size matters beyond exploration because, as Augustine and Moses Jr. observed when they introduced dispersion, "any solution to a problem of dispersion acts as a solution to \(n\) robot exploration under the same conditions" Augustine & Moses Jr. 2018.

Formal definitions
0any \(k\)
Any number \(k\ge 2\) of agents.
1\(k = n\)
Exactly \(k=n\) agents.
1\(k \ge Dn^{1+\varepsilon}\)
\(k\ge D\,n^{1+\varepsilon}\) agents for a constant \(\varepsilon>0\) (written \(k=Dn^\gamma\), \(\gamma>1\)).

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.