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 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›+ finite graph›+ oracle pebbles

Treasure hunt guided by pebbles

verified
Cost: near-optimalHelp: unknown

An oracle places pebbles (at most one per node); \(O(d\log\Delta)\) pebbles let the agent reach the treasure in near-optimal time.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Graph sizefinite+External helppebbles placed by an oracle that knows the instance

Not assumed

Node identifiersanonymous nodesTopologyarbitrary 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: 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: oracle 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.
Topology: any topology
\(G\) is any connected graph in the class allowed by the other axes.

What is known

Cost · edge traversals until the treasure is reached
near-optimal
An additive \(\log^3\Delta\).
lower bound
\(\Omega(d\log\Delta)\) Gorain et al. 2022
bottleneckport addressing
holds when
  • any number of pebbles
  • \(d\) = distance to the treasure
introductory—
current best
\(O(d\log\Delta+\log^3\Delta)\)
Help · bits of advice, or pebbles placed in advance by an oracle
unknown
No lower bound on the number of pebbles recorded.
lower boundnone known
introductory—
current best
\(O(d\log\Delta)\ \text{pebbles}\)

Results, in order of publication

Gorain et al. 2022 current best
Cost \(O(d\log\Delta+\log^3\Delta)\)Help \(O(d\log\Delta)\ \text{pebbles}\)

Introductory and current best (SIROCCO 2021 bounds; whether the journal version improves them was not checked).

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.

Algorithms from weaker settings work here

Anonymous finite graphs
Cost \(O(n^{\theta(1+1/a)})\)

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.