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 measuresexpand
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.
Anonymous finite graphs
standard settingverifiedIf 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.
Assumed (added on the last edge are outlined)
Not assumed
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.
- Graph size: finite graph
- \(G\) has finitely many nodes.
- 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.
- External help: no help
- No information beyond the agent's own observations.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
Results, in order of publication
Theorem 3.2: an infinite strongly universal exploration sequence with cover time \(O(n^{2\theta})\), \(\theta\) the exponent of Reingold's universal exploration sequences; explicit when those are.
For any fixed integer \(a \gg 1\); with backtracking (the agent sees the entry port).
Open questions
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.
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.
Notes
For a treasure present when the agent starts, Ta-Shma and Zwick note that following \(U_1U_2U_4\dots\), universal traversal sequences of doubling length, solves the problem in polynomial time Ta-Shma & Zwick 2014. The bounds above are for the harder case. Checked against the full texts.
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.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
Branches from here
Treasure hunt with advice
Treasure hunt guided by pebbles
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.