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.

Progress map

tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Memory

No assumptions

—

Node identifiers + static graph, + undirected

—

Communication + labelled nodes

—

Timing + global communication

—

Arbitrary graphs, complete communication + synchronous

1 open · 1 results

unknown \(\tfrac{2n}{k}+D^2(\min\{\log\Delta,\log k\}+2)\) vs —

unknown — vs —

Trees, complete communication any \(k\), + tree

2 open · 5 results

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 + \(k = n\), + tree

1 open · 1 results

polynomial gap \(D^2\) vs \(D^2/3\) online tree revelation

unknown — vs —

Large teams, complete communication + \(k \ge Dn^{1+\varepsilon}\)

1 open · 1 results

tight \(D(1+\tfrac{1}{\gamma-1}+o(1))\) vs \(D(1+\tfrac1{\gamma}-o(1))\) distance

unknown — vs —

Trees, asynchronous, complete communication asynchronous, + tree

0 open · 3 results

tight \(2n+O(kD\log^2 k)\) vs \(\Omega(\log^2 k)\cdot(n+kD)\) adversarial activation

unknown — vs —

Timing no communication, + whiteboards

—

Trees, communication by whiteboards only + synchronous, + tree

1 open · 1 results

polynomial gap \(O(D + n/\log k)\) vs —

unknown — vs —

Trees, asynchronous, whiteboards only asynchronous, + tree

1 open · 1 results

polynomial gap \(2n+O(k^2 2^k D)\) vs —

unknown — vs —

Trees, no communication no communication, no whiteboards, + synchronous, + tree

0 open · 1 results

tight \(O(k)\cdot\text{optimal}\) vs \(\Omega(k)\cdot\text{optimal}\) no information sharing

unknown — vs —

Large teams, local communication + local communication, + synchronous, + \(k \ge Dn^{1+\varepsilon}\)

0 open · 1 results

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

0 open · 1 results

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 + \(k = n\)

1 open · 2 results

tight \(O(n)\) vs \(\Omega(n)\) distance

unknown \(O(\log n)\) vs —

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