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.
Anonymous graphs with \(k = n\) agents
verifiedNodes 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.
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: anonymous nodes
- Nodes have no identifiers; an agent at \(v\) sees only \(\deg(v)\) and the port numbers \(1,\dots,\deg(v)\), which are assigned locally and independently at each endpoint of an edge.
- Randomness: deterministic
- The next state and move of an agent are a function of its current state and what it observes.
- Communication: local communication
- Agents at the same node at the same time can read each other's entire memory (face-to-face communication). Agents crossing on an edge do not meet.
- 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: \(k = n\)
- Exactly \(k=n\) agents.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
- a path with all agents on one endpoint
Results, in order of publication
Rooted dispersion; Augustine and Moses Jr. observe that any dispersion algorithm with \(k=n\) solves \(n\)-agent exploration under the same conditions.
Rooted dispersion in \(O(k)\) rounds with \(O(\log(k+\Delta))\) bits; exploration follows by the observation above (our inference, not stated in the paper).
Open questions
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.
Notes
See the overview From exploration to dispersion.
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
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.