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.
Labelled nodes, locally finite graphs
verifiedWith node labels, a treasure at distance \(d\) is found at cost \(O(e(d)\log d)\), against a lower bound of \(\Omega(e(d))\).
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: locally finite
- \(G\) is finite or countably infinite, and every node has finite degree.
- Node identifiers: labelled nodes
- Each node \(v\) carries a distinct identifier that agents at \(v\) can read; hence an agent can recognise a node it has visited.
- 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
- \(e(d)\): edges with an endpoint at distance below \(d\)
- holds for every algorithm on some graphs
Results, in order of publication
Introductory and current best; holds also in the fuel- and rope-restricted models, and refutes a 1999 conjecture of Awerbuch, Betke, Rivest and Singh.
Open questions
Remove the \(O(\log d)\) factor between \(O(e(d)\log d)\) and \(\Omega(e(d))\) Bouchard et al. 2023.
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
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.