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

no assumptions›+ static graph, + undirected

Anonymous graphs with possibly infinite degrees

verified

Cost: tightHelp: tight

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.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected

Not assumed

Graph sizefinite or countably infinite, degrees may be infiniteNode identifiersanonymous nodesExternal helpno helpTopologyarbitrary connected graph

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: infinite degrees allowed: \(G\) is finite or countably infinite; a node may have countably infinite degree (ports \(1,2,3,\dots\)).
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.

Statement for this variant

For a path with largest port \(q\) and length \(\rho\), its type is \((q,\rho)\) with value \(\rho\,2^{\rho}q^{\rho}\); \(w(s,v^*)\) is the value of the cheapest type of a path from \(s\) to \(v^*\).

What is known

Cost · edge traversals until the treasure is reached

tight

Optimal order of magnitude among universal algorithms.

lower bound

\(\Omega(w(s,v^*))\) Pattanayak & Pelc 2024

bottleneckport addressing

holds when

among universal algorithms (no knowledge of the graph)
graphs whose nodes may have countably infinite degree

introductory—

current best

\(O(w(s,v^*))\)

Pattanayak & Pelc 2024

Help · bits of advice, or pebbles placed in advance by an oracle

tight

No help is used.

lower boundnone known

introductory—

current best—

Results, in order of publication

Pattanayak & Pelc 2024 current best

Cost \(O(w(s,v^*))\)

Introductory and current best (Theorem 2.1).

Open questions

None recorded for this variant.

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.