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›anonymous nodes, + local communication, + synchronous

Anonymous graphs, a team of constant-memory agents

verified

Time: unknownMemory: tight

\(\Theta(\log\log n)\) agents with constant memory are necessary and sufficient to explore any anonymous graph.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Communicationlocal (co-located agents communicate)+Timingsynchronous rounds

Not assumed

Node identifiersanonymous nodesRandomnessdeterministicNode 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: 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: 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

Polynomial; exponent not tracked.

lower boundnone known

introductory—

current best

\(n^{O(1)}\)

Disser et al. 2019

\(n\) unknown

Memory · bits per agent

tight

\(\Theta(\log\log n)\) agents with \(O(1)\) bits.

lower bound

\(\Omega(\log\log n)\ \text{agents}\) Disser et al. 2019

bottlenecktrap graphs

holds when

each agent has \(O((\log n)^{1-\varepsilon})\) bits
deterministic

introductory—

current best

\(O(1)\ \text{bits each},\ O(\log\log n)\ \text{agents}\)

Disser et al. 2019

\(n\) unknown

Results, in order of publication

Disser et al. 2019 current best

Time \(n^{O(1)}\)Memory \(O(1)\ \text{bits each},\ O(\log\log n)\ \text{agents}\)

\(n\) unknown

Introductory and current best. One agent walks, the others act as pebbles.

Open questions

None recorded for this variant.

Notes

Here the question is not speed but the size of a team of finite automata; it mirrors the single-agent pebble variant.

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.