Mobility Matters
Home›Mobile agents on graphs›Exploration›Graph exploration by a single agent›Treasure hunt

Treasure hunt

One agent must find a static treasure at an unknown node; the cost should depend on how far the treasure is, not on the size of the graph.

Problem statement and measurescollapse
010120101201010101sv*sv*sv*sv*sv*sv*sv*sv*sv*sv*sv*sv*sv*sv*Start: agent at s, treasure at an unknown node v*N = 1: follow the sequence (2)N = 2: follow the sequence (1, 2)N = 4: follow the sequence (1, 1, 2, 0)N = 8: follow the sequence (1, 2, 1, 1, 1, 1, 2, 2)Final: treasure found during the phase N = 8, after 13 moves
Treasure hunt by exploration sequences of doubling size Ta-Shma & Zwick 2014: in the phases \(N = 1, 2, 4, 8, \dots\) the agent follows the sequence for size \(N\) from where it stands (entering by port \(p\) with term \(x\), it leaves by port \((p + x) \bmod \deg\); ports are numbered from 0) and stops on the treasure \(v^*\). The short sequences drawn here are illustrative, not actual universal sequences, which are much longer. One frame per move.

A single deterministic agent starts at a node \(s\) of an unknown connected graph whose edges carry ports (at each node, local numbers of the edges at that node); a treasure sits at an unknown node \(v^*\) at distance \(d\) from \(s\). The agent must reach \(v^*\) (it recognises the treasure when it arrives). Cost is the number of moves (edge traversals) until the treasure is found, measured against \(d\), against \(e(d)\) (the number of edges with an endpoint at distance less than \(d\) from \(s\)) or against a path weight defined per paper. Help counts any external help the agent receives: bits of advice from an oracle that knows the instance, or pebbles (objects left on nodes) placed by it. Unless a variant says otherwise the agent knows nothing about the graph, \(d\) or \(v^*\).

Measures: Cost, edge traversals until the treasure is reached; Help, bits of advice, or pebbles placed in advance by an oracle.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

A hiker is lost in a park whose trails form a network, and a rescuer walks from the trailhead looking for her, without a map and without knowing which direction to take. The network is a graph: trail junctions are nodes and the trails between them are edges; the rescuer is a single agent that starts at a node \(s\) and walks along edges, and one crossing of one edge is a move. The graph is unknown and connected, and at each node the edges at that node carry local numbers, its ports. The hiker is the treasure, at an unknown node \(v^*\) at distance \(d\) from \(s\) (the distance is the fewest edges on a path between two nodes). The agent recognises the treasure only when it stands on it. In the basic version the graph is finite, with \(n\) nodes, and the agent knows nothing about it; it must reach \(v^*\), and the cost is the number of moves it makes.

1AlgorithmUniversal exploration sequences of doubling size Anonymous finite graphs → Ta-Shma & Zwick 2014

An exploration sequence is a list of numbers \(x_1, x_2, \dots\); following it means: at the \(i\)-th move, if you entered the current node (of degree \(\deg\), the number of edges at it) by port \(p\), leave by port \((p + x_i) \bmod \deg\). A sequence is universal for size \(N\) if following it visits every node of every connected graph with at most \(N\) nodes, from any start. Such sequences exist and can be computed Reingold 2008.

  1. For \(N = 1, 2, 4, 8, \dots\) (one phase per value of \(N\)):
  2. follow the universal sequence for size \(N\) from wherever you are;
  3. stop as soon as you stand on the treasure.
Why it works and what it costs. Once \(N \ge n\), the sequence for size \(N\) visits every node, including \(v^*\), so the search ends during that phase Ta-Shma & Zwick 2014. Each sequence has length polynomial in \(N\), the lengths grow geometrically, and the loop never goes past \(N < 2n\), so the total cost is polynomial in \(n\). It ignores \(d\): a treasure next door may cost as much as one far away. With node labels, a treasure at distance \(d\) is found at cost \(O(e(d)\log d)\) Bouchard et al. 2023a, where \(e(d)\) is the number of edges with an endpoint at distance less than \(d\) from \(s\).

Why it matters. Doubling a guess you do not know (here \(n\)) is the standard way to remove knowledge from an algorithm; it reappears in rendezvous and gathering.

2Lower boundThe treasure is behind the last port Labelled nodes, locally finite graphs → Bouchard et al. 2023a

Let \(s\) have many neighbours, say 20, and put the treasure on one of them, so \(d = 1\). The agent cannot see what is at the other end of an edge without crossing it. An adversary watches the agent and puts the treasure behind whichever of the 20 ports the agent tries last; since every node looks the same from \(s\), the agent cannot avoid this.

Why it holds. The agent walks out and back along at least 19 edges before it tries the last one, so it pays about twice the degree of \(s\). Here \(e(1)\), the number of edges with an endpoint at distance less than 1 from \(s\), is exactly the degree of \(s\), and the same idea applied layer by layer gives the general bound \(\Omega(e(d))\) of Bouchard et al. 2023a, which holds even when nodes carry labels. Their algorithm costs \(O(e(d)\log d)\), so the gap is a factor \(\log d\). Trivially the agent also needs at least \(d\) moves.

Why it matters. It shows that the right measure of cost is the number of edges near the start, not the distance, which is why later work states bounds in terms of \(e(d)\) or path weights.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Cost
Help
Anonymous graphs with possibly infinite degrees
A universal algorithm whose cost is optimal among universal algorithms, measured by a weight \(w(s,v^*)\) of the cheapest path type to the treasure.
tight \(O(w(s,v^*))\) vs \(\Omega(w(s,v^*))\) port addressing
tight — vs —
Anonymous finite graphs standard
If the treasure is present from the start, concatenating universal traversal sequences finds it in polynomial time; if it may appear later, explicit solutions need backtracking and take the length of a universal exploration sequence, polynomial with a huge exponent, times a polylogarithmic factor.
unknown \(O(n^{\theta}\log n\,(\log\log n)^{1+\varepsilon})\) vs —
unknown — vs —
Treasure hunt with advice
How many bits of advice buy a given cost \(C\): about \(d\log(m/C)\).
tight \(C\) vs —
near-optimal \(O(d\log(d\cdot m/C)+\log\log m)\) vs \(\Omega(d\log(m/C))\) information
Treasure hunt guided by pebbles
An oracle places pebbles (at most one per node); \(O(d\log\Delta)\) pebbles let the agent reach the treasure in near-optimal time.
near-optimal \(O(d\log\Delta+\log^3\Delta)\) vs \(\Omega(d\log\Delta)\) port addressing
unknown \(O(d\log\Delta)\ \text{pebbles}\) vs —
Labelled nodes, locally finite graphs
With node labels, a treasure at distance \(d\) is found at cost \(O(e(d)\log d)\), against a lower bound of \(\Omega(e(d))\).
near-optimal \(O(e(d)\log d)\) vs \(\Omega(e(d))\) distance
tight — vs —
Dynamic graphs, connected at every step
If the edges may change at every step while every snapshot stays connected, no agent ever finds the treasure, even when every snapshot is a ring; if every two nodes become adjacent within every \(\xi\) steps and agents flag the nodes they visit, \(\Theta(\xi n)\) steps are necessary and sufficient on such rings.
impossible — vs \(\text{impossible}\) adversarial edge changes
unknown — vs —

Open questions 7

Anonymous finite graphs

  1. Treasure hunt when the treasure may appear after the agent starts and the agent does not see its entry port: "We do not know if an efficient solution is possible when backtracking is not allowed" Ta-Shma & Zwick 2014.
  2. Do strongly universal traversal sequences exist? They exist if and only if treasure hunt has a solution independent of the start time Ta-Shma & Zwick 2014.
  3. Is there a strongly universal exploration sequence with cover time \(O(n^{\theta})\), or \(O(n^{\theta}\log n)\), for fixed-degree graphs? Xin 2026 (preprint) reaches \(O(n^{\theta}\log n\,(\log\log n)^{1+\varepsilon})\) and shows that its recurrence cannot keep linear length with periods \(\Theta(2^j j)\) (Corollary 10.2), which is "not a lower bound for arbitrary SUESs".

Labelled nodes, locally finite graphs

  1. Remove the \(O(\log d)\) factor between \(O(e(d)\log d)\) and \(\Omega(e(d))\) Bouchard et al. 2023a.

Dynamic graphs, connected at every step

  1. With flags in VP(\(\xi\)), the lower bound of \(\xi(n-3)\) steps for one deterministic agent is proved for \(\xi\ge 2n\); does \(\Omega(\xi n)\) hold for every \(\xi\ge\lceil (n-1)/2\rceil\), the smallest window for which VP(\(\xi\)) is non-empty? Ayoubi et al. 2026
  2. What is the competitive ratio of randomized agents in VP(\(\xi\)) against an adaptive online adversary? Ayoubi et al. 2026
  3. Which of these results extend to vertex-permuted graphs other than rings? Ayoubi et al. 2026

What the community started looking at

Ta-Shma and Zwick introduced deterministic treasure hunt as the variant of rendezvous in which one agent never moves Ta-Shma & Zwick 2014. The question from the start was cost as a function of how far the treasure is, not of the size of the graph, which led to strongly universal exploration sequences. Later work asked how much external help (advice bits, pebbles) reduces the cost Miller & Pelc 2015b Gorain et al. 2022, what is possible in graphs with infinite degrees Pattanayak & Pelc 2024b, and whether the treasure can be found at all in a ring whose nodes an adversary reorders at every step Ayoubi et al. 2026.

Subproblem of Graph exploration by a single agent

An agent that explores the graph finds any treasure, so every exploration algorithm solves treasure hunt; the question is how much cheaper it can be when the treasure is close, measured against its distance \(d\) (or a weight of the path to it) rather than the size of the graph.

Perspectives

  • Finding your way A single agent in an anonymous graph: how much memory it needs, what a pebble, an advice string or knowledge of n buys, why stopping is harder than exploring, and how treasure hunt asks for exploration only as far as the target. Each line of papers, in its own words, on why the question matters.
  • Meeting at one place Rendezvous and gathering on graphs, gathering and convergence in the plane, and evacuation through an unknown exit all ask entities to end at one point. The papers give the same reasons for meeting, but each model makes a different part of it hard: symmetry and exploration on graphs, capability in the plane, information in continuous search.
  • What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Gaur et al. 2025 Robust Treasure Hunt in Anonymous Graphs with Quantum Pebbles by Oblivious Agents. An oblivious agent (no memory between moves) guided by pebbles that an oracle places on a shortest path to the treasure at distance \(d\) (their \(D\)): pebbles of one colour never suffice, at least \(\Delta-1\) colours are needed for a deterministic agent (Theorems 1 and 2), and \(\Delta-1\) colours suffice. Quantum pebbles, one per node of the path, each emitting qubits that encode the port to take, let the agent reach the treasure in \(d\) moves with probability tending to 1, using \(O(\Delta^3(\log d+\log\Delta))\) measurements per node (Theorem 4). One wrong colour can trap an oblivious agent forever, and under such persistent errors every randomized strategy succeeds only with probability exponentially small in \(d\) (Theorem 5, Proposition 1); the quantum protocol tolerates independent errors on each emitted qubit below an explicit threshold (Theorem 6). Preprint; read (arXiv v2).
  • Bhattacharya et al. 2022 Treasure Hunt in Graph Using Pebbles. Fewer pebbles than the distance: with \(p < d\) pebbles placed by an oracle (their \(k\) and \(D\)), the cost becomes exponential in \(d/p\), e.g. \(O(p\Delta^{d/(p+1)})\) for \(d/2 \le p < d\), against \(\Omega((p/e)^{p/(p+1)}(\Delta-1)^{d/(p+1)})\) on trees for every \(p < d\) (Theorem 4); also bipartite graphs and \(p = cd\). Read (arXiv v1).
  • Bouchard et al. 2021 Impact of knowledge on the cost of treasure hunt in trees. Trees: the agent gets a map of the tree rooted at its start, with or without port numbers, and the distance to the treasure or not. The penalty of a less precise kind of knowledge is very large for a map without ports when the distance is known, small when it is not, and medium for not knowing the distance when a map is given. Read (arXiv v1, 2025).
  • Bouchard et al. 2020 Deterministic Treasure Hunt in the Plane with Angular Hints. In the plane: an agent with a compass and a measure of length gets, after each move, an angle smaller than \(2\pi\) that contains the treasure. Angles at most \(\pi\) give cost \(O(D)\), which is optimal; angles at most a constant \(\beta < 2\pi\) give \(O(D^{2-\varepsilon})\); arbitrary angles cannot beat \(\Theta(D^2)\) (their \(D\) bounds the initial distance). Read (arXiv v1).
  • Pelc & Yadav 2019a Cost vs. Information Tradeoffs for Treasure Hunt in the Plane. In the plane, with advice: the treasure is within distance \(D\) and is found from distance \(r\). For every size \(z\) of advice, cost \(O(\mathrm{OPT}(z,D,r))\) when \(r \le 1\) or \(r \ge 0.9D\), and \(O(\mathrm{OPT}(z,D,r)^{1+\alpha})\) for every constant \(\alpha > 0\) in between. Read (arXiv v1).
  • Pelc & Yadav 2021 Advice complexity of treasure hunt in geometric terrains. Polygonal terrains with obstacles: the advice needed to find the treasure at cost \(O(L)\), where \(L\) is the length of a shortest path to it, is determined exactly for convex terrains with convex fat obstacles, and is exponentially larger for arbitrary terrains. Read (arXiv v2).
  • Bhattacharya et al. 2023 Pebble Guided Treasure Hunt in Plane. In the plane, with pebbles: an agent with a compass whose speed the adversary controls can turn only at pebbles. One pebble does not allow a finite cost, two give \(O(D)\), and \(k > 8\) pebbles give \(O(k^2) + D(\sin\theta_0 + \cos\theta_0)\) for an angle \(\theta_0\) that shrinks as \(k\) grows, so the cost approaches \(D\) for large \(D\) (Theorem 3). Read (arXiv v1).
  • Dobrev et al. 2017 Treasure Hunt with Barely Communicating Agents. Treasure hunt in another sense, from Fraigniaud, Korman and Rodeh: \(k\) deterministic agents open boxes of an infinite ordered list, and an agent can only tell whether a box was opened before. With failing agents they are 1-competitive against an algorithm that knows which agents fail; with \(f\) boxes that are black holes, between \(2f+1\) and \(4f+1\) agents are needed. Read (LIPIcs version).
  • Korman & Rodeh 2016 Parallel Linear Search with no Coordination for a Randomly Placed Treasure. The same box search with a treasure placed uniformly at random among many boxes: \(k\) searchers that do not coordinate achieve speed-up \(k(k+1)/(3k-1)\), about three times worse than full coordination as \(k\) grows. Read (arXiv v2).

All settings

The assumption tree (6 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Cost, Help); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Graph size › Node identifiers › External help › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Graph size

0finite or countably infinite, degrees may be infinite1finite or countably infinite, every degree finite2finite

Ta-Shma and Zwick posed deterministic treasure hunt in a finite connected graph, as the variant of rendezvous in which one agent never moves Ta-Shma & Zwick 2014; Pelc notes that rendezvous with arbitrary delay contains this case, since the adversary may wake one agent late enough Pelc 2019. Infinite graphs make sense once cost is measured locally: Bouchard, Dieudonné, Labourel and Pelc consider connected graphs, finite or countably infinite, with finite degrees, and find a treasure at distance \(d\) at cost \(O(e(d)\log d)\), refuting a conjecture of Awerbuch, Betke, Rivest and Singh Bouchard et al. 2023a. Pattanayak and Pelc observed that "all known treasure hunt and rendezvous algorithms rely on the assumption that degrees of all nodes are finite, even when the graph itself may be infinite", removed the assumption, and noted that countable degrees are the limit: with uncountable degrees neither task can be done in finite worst-case time Pattanayak & Pelc 2024b. The three levels differ in the natural cost measure: a function of \(n\) in finite graphs, \(e(d)\) in locally finite ones, and a weight \(w(s,v^*)\) of the cheapest path type when \(e(d)\) may be infinite Pattanayak & Pelc 2024b.

Formal definitions
0infinite degrees allowed
\(G\) is finite or countably infinite; a node may have countably infinite degree (ports \(1,2,3,\dots\)).
1locally finite
\(G\) is finite or countably infinite, and every node has finite degree.
2finite graph
\(G\) has finitely many nodes.

External help

0no help1advice: bits from an oracle that knows the instance1pebbles placed by an oracle that knows the instance

External help measures how much information about the instance buys a fast treasure hunt. Miller and Pelc framed it in the paradigm of algorithms with advice: an oracle that knows the network, the start and the treasure gives the agent a binary string, and the question is the smallest advice that achieves a given cost, against cost \(\Theta(m)\) in the worst case without information Miller & Pelc 2015b; among the earlier advice papers they cite tree exploration with advice by Fraigniaud, Ilcinkas and Pelc Fraigniaud et al. 2008. Their nodes carry labels that the agent reads on arrival Miller & Pelc 2015b. Gorain, Mondal, Nayak and Pandit replaced the string by pebbles that the oracle places on nodes of an anonymous graph, at most one per node, seen only on arrival, arguing that when many agents search independently it is cheaper to put information on the nodes once than to give advice to each agent Gorain et al. 2022. They show \(O(d\log\Delta)\) pebbles give time \(O(d\log\Delta+\log^3\Delta)\) and that no number of pebbles beats \(\Omega(d\log\Delta)\) Gorain et al. 2022. The two forms of help sit on the same level because neither simulates the other: advice is global and read at once, pebbles are local and read along the walk.

Formal definitions
0no help
No information beyond the agent's own observations.
1advice
An oracle that knows the whole instance gives the agent a binary string before it starts; its length (in bits) is the measure.
1oracle pebbles
An oracle that knows the instance places pebbles on nodes (at most one per node) before the agent starts; their number is the measure.

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