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 measuresexpand

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.

no assumptions›+ static graph, + undirected›+ labelled nodes›+ global communication›+ synchronous

Arbitrary graphs, complete communication

verified
Time: unknownMemory: unknown

On graphs with cycles it is not even known whether any algorithm beats depth-first search by more than a constant.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Node identifierslabelled nodes (an agent can recognise a node it has visited)+Communicationglobal (any agent can read any other agent's state)+Timingsynchronous rounds

Not assumed

RandomnessdeterministicNode memoryno whiteboardsTeam sizeany number \(k\) of agentsTopologyarbitrary connected graph
Formal definitions of this setting
Graph dynamics: static graph
\(G_t=G\) for all \(t\): the edge set never changes.
Edge direction: undirected
\(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
Node identifiers: labelled nodes
Each node \(v\) carries a distinct identifier that agents at \(v\) can read; hence an agent can recognise a node it has visited.
Randomness: deterministic
The next state and move of an agent are a function of its current state and what it observes.
Communication: global communication
At every round every agent can read the memory of every other agent, wherever it is.
Node memory: no whiteboards
Nodes have no storage: no information can be left at a node except by an agent staying there.
Timing: synchronous
Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
Team size: any \(k\)
Any number \(k\ge 2\) of agents.
Topology: any topology
\(G\) is any connected graph in the class allowed by the other axes.

What is known

Time · rounds until every node is visited (asynchronous: total moves)
unknown
No \(o(k)\)-competitive algorithm is known without extra knowledge; lower bounds are inherited from trees.
lower boundnone known
introductory—
current best
\(\tfrac{2n}{k}+D^2(\min\{\log\Delta,\log k\}+2)\)
agents know their distance to the root
Memory · bits per agent
unknown
Memory is not bounded in these papers.
lower boundnone known
introductory—
current best—

Results, in order of publication

Cosson et al. 2023 current best
Time \(\tfrac{2n}{k}+D^2(\min\{\log\Delta,\log k\}+2)\)
agents know their distance to the root

Proposition 7; \(n\) counts edges here.

Open questions

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

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.

Algorithms from weaker settings work here

Anonymous graphs, a team of constant-memory agents
Time \(n^{O(1)}\)Memory \(O(1)\ \text{bits each},\ O(\log\log n)\ \text{agents}\)

Lower bounds from stronger settings hold here

Trees, complete communication
Time \(\Omega\big(\tfrac{\log k}{\log\log k}\,(\tfrac nk + D)\big)\)
Large teams, complete communication
Time \(D(1+\tfrac1{\gamma}-o(1))\)

Branches from here

Trees, complete communication

any \(k\)+tree
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)\).

Trees with \(k = n\) agents

+\(k = n\)+tree
With as many agents as nodes, \(D^2\) rounds suffice, and some trees need \(D^2/3\); this is the bound dispersion inherits.

Large teams, complete communication

+\(k \ge Dn^{1+\varepsilon}\)
With \(k = Dn^{\gamma}\) agents (\(\gamma>1\)), exploration takes \(D(1+\tfrac1{\gamma-1}+o(1))\) rounds, almost the trivial \(D\).

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