Finding your way

The papers give three reasons, and they explain why the field measures memory rather than time. The first is practical. Fraigniaud, Ilcinkas, Peer, Pelc and Peleg: visiting all nodes "is fundamental in searching for data stored at unknown nodes of a network", traversing all edges is needed "in network maintenance and when looking for defective components", and since "robots and mobile agents are meant to be simple, often small and inexpensive devices", they ask for the least memory that suffices, "regardless of the time of exploration" Fraigniaud et al. 2005. They also explain the anonymous model: node labels may be absent or invisible to the agent, but ports must be distinguishable at a node, otherwise not even a star with three leaves can be explored Fraigniaud et al. 2005.

The second reason comes from complexity theory. Fraigniaud, Ilcinkas, Rajsbaum and Tixeuil recall that a finite set of finite automata able to explore all graphs "would have put USTCON in L", which motivated "quite a long sequence of studies" until Reingold placed undirected connectivity in log-space Fraigniaud et al. 2006 Reingold 2008. The third is a modelling view stated by Disser, Hackfeld and Klimm: exploration is "a natural abstraction of a process of computing where nodes correspond to states", so a single agent is a single processor and a team of agents is a parallel machine Disser et al. 2019.

The history is told the same way in several introductions. Shannon's maze-solving machine of 1951 is the "first known finite automaton algorithm designed for graph exploration" Fraigniaud et al. 2005 Shannon 1951. Rabin claimed in 1967 that no finite automaton with finitely many pebbles explores all graphs; Budach gave the first formal proof for an automaton without pebbles, phrased for labyrinths Budach 1978; and Rollik proved that no finite set of cooperating finite automata explores all cubic planar graphs, which implies Rabin's claim because an automaton is at least as strong as a pebble Rollik 1980. In mazes the picture is kinder: Blum and Kozen showed that a finite automaton with two pebbles, or two cooperating automata, search every two-dimensional maze, because an automaton in a maze "has a compass: it can distinguish N,E,S,W"; on finite planar cubic graphs, by contrast, "no three finite automata together can search all" of them (Theorem 6.1) Blum & Kozen 1978. The statements about Rabin, Budach and Rollik are as recounted by Fraigniaud et al. 2005 and Disser et al. 2019 (Blum and Kozen also recount Budach's result); those originals were not read for this catalogue.

The modern question starts from those traps. Fraigniaud et al. build, for every \(K\)-state automaton, a planar trap with at most \(K+1\) nodes, and deduce that exploring all graphs of diameter \(D\) and maximum degree \(\Delta\) needs \(\Omega(D\log\Delta)\) bits; a depth-first search of depth \(D+1\) shows this is tight Fraigniaud et al. 2005. Two resources appear already in this early work and stay in all later work: memory inside the agent, and markers outside it.

On trees the answer depends on what the agent must do at the end. Perpetual exploration needs and can do with \(\Theta(\log\Delta)\) bits Diks et al. 2002; a memoryless agent that always leaves by the next port after the one it entered also works, as Cohen et al. recall Cohen et al. 2008. Exploration with return needs \(\Theta(\log n)\) bits Diks et al. 2002 Ambühl et al. 2011. Exploration with stop sits between \(\Omega(\log\log\log n)\) and \(O(\log n)\), and whether stopping is cheaper than returning is the open problem left by Diks, Fraigniaud, Kranakis and Pelc Diks et al. 2002.

Knowledge of \(n\) changes what is possible. With an upper bound on \(n\), a random walk with an \(O(\log n)\)-bit step counter explores any graph with high probability Aleliunas et al. 1979, and Reingold's log-space universal exploration sequences make this deterministic with \(O(\log n)\) bits Reingold 2008. Disser et al. summarise the single-agent picture as \(\Theta(\log n)\) bits, necessary and sufficient Disser et al. 2019; the lower bound the catalogue records for agents that know \(n\) is \(\omega((\log n)^{1-\varepsilon})\) bits, and whether the full \(\Omega(\log n)\) holds when \(n\) is known is listed as open on the exploration page.

Visiting every node is not the same as knowing that every node has been visited. Without a bound on \(n\) and without any way to mark a node, a deterministic agent cannot explore with stop, whatever its memory Dieudonné & Pelc 2012; already an even cycle cannot be explored with stop without a marker Fraigniaud et al. 2006. One pebble that marks the start restores it: depth-first phases of increasing depth find new nodes, and the agent stops after phase \(D+1\), using \(O(D\log\Delta)\) bits Fraigniaud et al. 2005. Fraigniaud, Ilcinkas, Rajsbaum and Tixeuil introduced the reduced-automata technique to prove lower bounds of this kind, and showed \(\Omega(\log n)\) bits for exploration with stop and one pebble Fraigniaud et al. 2006.

Termination returns in the multi-agent problems. In dispersion, Sudo et al. make all agents stop in the rooted case only with global upper bounds on \(k\) and on the number of edges Sudo et al. 2024, and the only asynchronous dispersion algorithm known in which every agent terminates takes time exponential in the diameter Kshemkalyani & Ali 2019; the dispersion variants list the open questions.

Cohen, Fraigniaud, Ilcinkas, Korman and Peleg view pebbles as the agent's ability "to dynamically label the nodes", and ask what happens if a designer labels the nodes beforehand Cohen et al. 2008. Their answer is that 2-bit labels (three values) let an automaton with fewer than 25 states explore every graph and stop, and 1-bit labels suffice for graphs of bounded degree, although no finite automaton explores all graphs of maximum degree 3 unaided Cohen et al. 2008. Ilcinkas asks the dual question for ports: since an adversarial port numbering defeats every finite automaton, how short can the period of a finite automaton be if the designer chooses the ports? Periodic exploration, he writes, is "particularly useful for network maintenance, where every node has to be regularly checked"; a three-state automaton achieves period \(4n-2\) Ilcinkas 2008, later improved to \(3.5n-2\) against a lower bound of \(2n-2\) Czyzowicz et al. 2012.

Disser, Hackfeld and Klimm settled the exchange rate between memory and markers: a constant-memory agent needs and can do with \(\Theta(\log\log n)\) pebbles, even without knowing \(n\), and the trade-off has two thresholds, no pebbles needed with \(\Omega(\log n)\) bits and \(\Omega(\log\log n)\) pebbles needed as soon as the memory drops to \(O((\log n)^{1-\varepsilon})\) Disser et al. 2019. At the far end, an automaton with a single state explores every connected graph with two pebbles, and two is the minimum Pattanayak & Pelc 2024.

Ta-Shma and Zwick introduced deterministic treasure hunt as "a version of the rendezvous problem in which one of the robots is completely passive" Ta-Shma & Zwick 2014. They point out that the problem is easy if the treasure is present when the agent starts; the hard case is a treasure placed later, which must still be found within time polynomial in \(n\), and it led them to strongly universal exploration sequences. Whether this is possible without backtracking (when the agent does not see its entry port) is still open in their words: "We do not know if an efficient solution is possible when backtracking is not allowed" Ta-Shma & Zwick 2014. Xin improved the cover time of these sequences Xin 2007.

Later papers motivate the problem with rescue. Bouchard, Dieudonné, Labourel and Pelc: "When a miner is lost in a contaminated mine, it may have to be found by a robot, and the length of the robot's trajectory should be as short as possible" Bouchard et al. 2023. Cost is then measured against the distance \(d\) to the treasure, or \(e(d)\), the number of edges near the start, not against the size of the graph; with labelled nodes they reach \(O(e(d)\log d)\) against \(\Omega(e(d))\) Bouchard et al. 2023. Gorain, Mondal, Nayak and Pandit note that depth-first search costs \(O(\Delta^d)\) for a treasure at distance \(d\) and that urgent searches call for help Gorain et al. 2022. Miller and Pelc measure that help as bits of advice from an oracle and give the trade-off between advice and cost Miller & Pelc 2015; Gorain et al. instead place pebbles once, so that many agents can reuse them Gorain et al. 2022. Pattanayak and Pelc drop the assumption that degrees are finite, which they report all earlier treasure hunt and rendezvous algorithms made, motivated by graphs of very large degree such as social networks Pattanayak & Pelc 2024.

Directed graphs, where the agent cannot walk back, are a separate branch: one pebble and \(O(n\Delta_{out}\log n)\) bits suffice against an \(\Omega(n\log\Delta_{out})\) lower bound, where \(\Delta_{out}\) is the maximum out-degree Fraigniaud & Ilcinkas 2004, and a known bound on \(n\) gives polynomial time Bender et al. 2002. See the directed variants of exploration.