Treasure Hunt in Euclidean Plane: Cost vs. Pebble Trade-Off

Treasure hunt is a fundamental problem, where a mobile agent has to find an inert target (or treasure) in an unknown environment. We study this problem in the Euclidean plane where a mobile agent finds the treasure with the guidance of pebbles. The initial position of the agent and the position of the treasure are modeled as special points in the Euclidean plane. The treasure is situated at a distance of at most [Formula: see text] from the initial position of the agent. The agent has a perfect compass, but an adversary controls the speed of the agent. So, the agent does not have the ability to measure how much distance it has travelled for a given time. The agent can find the treasure only when it reaches the exact position of the treasure. The cost of the treasure hunt is defined as the total distance travelled by the agent before it finds the treasure. The agent has no prior knowledge of the position of the treasure or the value of [Formula: see text]. An Oracle, which knows the treasure’s position and the agent’s initial location, places some pebbles to guide the agent towards the treasure. Once decided to move along some specified angular direction, the agent can only change its direction when it encounters a pebble or a special point. We raise the following central question in this paper: “For given [Formula: see text], what is the most efficient treasure hunt algorithm if, at most, [Formula: see text] pebbles are placed by the Oracle?” We show that for [Formula: see text], there does not exist any treasure hunt algorithm that finds the treasure with finite cost. We have demonstrated the existence of an algorithm with cost [Formula: see text] for [Formula: see text]. For [Formula: see text], we have designed an algorithm that uses [Formula: see text] pebbles to find the treasure with cost at most [Formula: see text], where [Formula: see text]. The second result shows the existence of an algorithm with a cost arbitrarily close to [Formula: see text] for sufficiently large values of [Formula: see text].