Deterministic Treasure Hunt in the Plane with Angular Hints
- PDF / 4,719,863 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 72 Downloads / 226 Views
Deterministic Treasure Hunt in the Plane with Angular Hints Sébastien Bouchard1 · Yoann Dieudonné2 · Andrzej Pelc3 · Franck Petit1 Received: 22 December 2018 / Accepted: 2 May 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract A mobile agent equipped with a compass and a measure of length has to find an inert treasure in the Euclidean plane. Both the agent and the treasure are modeled as points. In the beginning, the agent is at a distance at most D > 0 from the treasure, but knows neither the distance nor any bound on it. Finding the treasure means getting at distance at most 1 from it. The agent makes a series of moves. Each of them consists in moving straight in a chosen direction at a chosen distance. In the beginning and after each move the agent gets a hint consisting of a positive angle smaller than 2𝜋 whose vertex is at the current position of the agent and within which the treasure is contained. We investigate the problem of how these hints permit the agent to lower the cost of finding the treasure, using a deterministic algorithm, where the cost is the worst-case total length of the agent’s trajectory. It is well known that without any hint the optimal (worst case) cost is 𝛩(D2 ) . We show that if all angles given as hints are at most 𝜋 , then the cost can be lowered to O(D), which is the optimal complexity. If all angles are at most 𝛽 , where 𝛽 < 2𝜋 is a constant unknown to the agent, then the cost is at most O(D2−𝜖 ) , for some 𝜖 > 0 . For both these positive results we present deterministic algorithms achieving the above costs. Finally, if angles given as hints can be arbitrary, smaller than 2𝜋 , then we show that cost complexity 𝛩(D2 ) cannot be beaten. Keywords Exploration · Treasure hunt · Algorithm · Mobile agent · Hint · Cost · Plane
A preliminary version of this paper appeared in the Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018) [4]. Supported in part by NSERC discovery Grant 8136 – 2013 and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais. Performed within Project ESTATE (Ref. ANR-16-CE25-0009-03), supported by French state funds managed by the ANR (Agence Nationale de la Recherche). * Sébastien Bouchard [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
1 Introduction Motivation A tourist visiting an unknown town wants to find her way to the train station or a skier lost on a slope wants to get back to the hotel. Luckily, there are many people that can help. However, often they are not sure of the exact direction: when asked about it, they make a vague gesture with the arm swinging around the direction to the target, accompanying the hint with the words “somewhere there”. In fact, they show an angle containing the target. Can such vague hints help the lost traveller to find the way to the target? The aim of the present paper is to answer this question. The model and problem formulation A mobi
Data Loading...
