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. 2023, 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. 2023

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. 2023, 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 are polynomial with a huge exponent.
unknown \(O(n^{\theta(1+1/a)})\) 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 —

Open questions 3

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.

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. 2023.

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 2015 Gorain et al. 2022, and what is possible in graphs with infinite degrees Pattanayak & Pelc 2024.

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.

All settings

The assumption tree (5 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. 2023. 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 2024. 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 2024.

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 2015; 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 2015. 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.