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.
Connected team, labelled graphs, shared knowledge
verifiedA team that must stay connected explores an unknown graph with \(k \ge n\) agents within a factor \(O(\min(\sqrt{D}, k^{1/3})\log k)\) of the best connected traversal of the known graph.
Assumed (added on the last edge are outlined)
Not assumed
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.
- Connectivity of the team: connected team
- In every round the nodes occupied by the agents induce a connected subgraph. An algorithm is then compared with the best traversal of the known graph by a team that obeys the same rule Mutzari et al. 2026.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
Statement for this variant
In every round the occupied nodes induce a connected subgraph; several agents may share a node. When an agent first visits a node, the whole team learns its degree and its unexplored edges. Time is compared with the fewest rounds in which a connected team can visit every node of the known graph.
What is known
Results, in order of publication
Introductory and current best. Corollary 3 gives \(O(\max(\sqrt{D}, \log k)\log k)\) by breadth-first exploration in growing layers that returns to the root after each layer; Theorem 4 gives \(O(k^{1/3}\log k)\) by running that algorithm up to depth \(k^{2/3}\) and, if the graph is deeper, letting the whole team perform one depth-first search as a unit, which takes \(O(n) = O(k)\) rounds while the optimum needs at least the depth.
Open questions
Is there an algorithm with sublinear overhead for \(n > k\) agents? The paper gives experiments only and calls a bound an important milestone Mutzari et al. 2026.
Notes
Mutzari, Aumann and Kraus compare their online algorithm experimentally with an offline coverage algorithm on random graphs and hotel floor plans. The offline problem is NP-hard; Jana, Italiano and Mandal approximate it for agents on distinct nodes Jana et al. 2025a. Checked against the full text of Mutzari et al. 2026 (IJCAI 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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Branches from here
Arbitrary graphs, complete communication
Trees with \(k = n\) agents
Large teams, complete communication
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.