Home›Mobile agents on graphs›Exploration›Graph exploration by a single agent

Graph exploration by a single agent

One agent starts at a node of an unknown anonymous graph and must visit every node; how much memory does it need, which pebbles or knowledge make it possible, and how fast can it be?

Problem statement and measuresexpand

A single deterministic agent is placed at a node \(s\) of a connected graph \(G\) with \(n\) nodes, \(m\) edges and maximum degree \(\Delta\). Nodes are anonymous (they carry no names the agent can read), and the edges at each node are numbered locally; these numbers are the node's ports. The agent sees the degree of its node and the port by which it entered. It must visit every node of \(G\). Three termination requirements are standard:

perpetual exploration: every node is eventually visited; the agent never has to stop;
exploration with stop: every node is visited and the agent then stops, anywhere;
exploration with return: every node is visited and the agent stops at \(s\).

Return implies stop, and stop implies perpetual exploration. Memory is the number of bits of the agent's state; when the agent carries pebbles (objects it can drop on a node and pick up again) their number is reported with the memory. Time is the number of moves (edge traversals) until exploration is complete; for periodic exploration it is the period. Unless a variant says otherwise the agent knows nothing about \(G\), not even \(n\).

Exploration is the oldest problem of the mobile-agent literature: it started as maze search by finite automata, and the question of how little memory suffices runs from Budach's impossibility (1978) to Reingold's log-space algorithm (2005). Several agents exploring together form the sibling problem, collaborative exploration.

Measures: Time, edge traversals until every node is visited (for periodic exploration: the period); Memory, bits of agent memory; pebbles, if any, are counted separately.

no assumptions›+ static graph›+ undirected›nothing known, no markers, adversarial ports, + perpetual

Arbitrary graphs, perpetual exploration

standard settingverified

Time: unknownMemory: tight

The classical memory question: how many bits must a finite-state agent have to visit every node of every graph of diameter \(D\) and degree \(\Delta\)?

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Termination requirementvisit every node; never required to stop (perpetual)

Not assumed

Node identifiersanonymous nodesKnowledgenothing known about the graphRandomnessdeterministicMarkersno markersPreprocessingports and nodes as given by an adversaryTopologyarbitrary 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.
Knowledge: nothing known: The agent knows nothing about \(G\): not \(n\), \(m\), \(\Delta\) or \(D\).
Randomness: deterministic: The next state and move of an agent are a function of its current state and what it observes.
Markers: no markers: The agent cannot mark nodes.
Preprocessing: adversarial ports: Port numbers (and any node labels) are chosen by an adversary.
Termination requirement: perpetual: Every node is visited at least once (and, for periodic exploration, infinitely often); the agent never needs to halt.
Topology: any topology: \(G\) is any connected graph in the class allowed by the other axes.

What is known

Time · edge traversals until every node is visited (for periodic exploration: the period)

unknown

The paper does not study time ("time is not an issue in our approach").

lower boundnone known

introductory—

current best—

Memory · bits of agent memory; pebbles, if any, are counted separately

tight

\(\Theta(D\log\Delta)\) bits in the worst case over graphs of diameter \(D\) and degree \(\Delta\).

lower bound

\(\Omega(D\log\Delta)\) Fraigniaud et al. 2005

bottlenecktrap graphs

holds when

deterministic agent, no knowledge of the graph
degree \(\Delta \ge 3\); the traps are planar
Theorem 4 and Corollary 5: for every \(K\)-state agent there is a planar trap of degree \(\Delta\) and diameter \(O(\log K/\log\Delta)\)

Corollary 3 gives \(\lceil\log n\rceil\) bits directly: for every \(K\)-state agent there is a planar trap with at most \(K+1\) nodes (Theorem 2; with loops and multiple edges, or \(K+\Delta+2\) nodes for simple graphs). Earlier: no finite automaton explores all mazes Budach 1978; no finite team of automata explores all cubic planar graphs Rollik 1980.

introductory—

current best

\(O(D\log\Delta)\)

Fraigniaud et al. 2005

Results, in order of publication

Fraigniaud et al. 2005 current best

Memory \(O(D\log\Delta)\)

Introductory and current best (Increasing-DFS, Theorem 6 and Corollary 7): depth-first searches of depth \(1, 2, 3, \dots\); no knowledge of \(D\) or \(\Delta\) is needed. The bound is the memory used until exploration is complete; by Theorem 8 any agent that explores all graphs uses unboundedly many states over time.

Open questions

What is the time of memory-optimal perpetual exploration, and is there a trade-off between memory and time?

Notes

In Fraigniaud et al. 2005 exploring means traversing every edge, not only visiting every node. The model goes back to maze search: Shannon's maze-solving mouse, Budach's theorem that no finite automaton explores all mazes Budach 1978, Blum and Kozen Blum & Kozen 1978, and Rollik's result that no finite team of automata explores all cubic planar graphs Rollik 1980. Blum and Kozen proved that a finite automaton with two pebbles, or two automata together, search every maze, and that no three finite automata together can search all finite planar cubic graphs (Theorem 6.1; also one automaton, Theorem 4.1, and two, Theorem 4.6), so mazes, which come with a compass, are strictly easier than graphs; whether any finite team suffices for planar cubic graphs was left open Blum & Kozen 1978. Their automata need not halt. This confirms the account of Fraigniaud et al. 2005; the reading in Cohen et al. 2008 that one agent with three pebbles cannot explore all graphs is not a result of Blum & Kozen 1978. Fraigniaud, Ilcinkas and Pelc showed that a polynomial increase in the number of states strictly enlarges the class of explorable regular graphs (DAM 2008, not in the bibliography yet). Checked against the full text.

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.