论文标题
带有角度提示的飞机上的确定性寻宝
Deterministic Treasure Hunt in the Plane with Angular Hints
论文作者
论文摘要
配备有指南针和长度的移动剂必须在欧几里得飞机上找到惰性宝藏。代理商和宝藏都被建模为点。一开始，代理商最多距宝藏$ d> 0 $，但既不知道距离也不知道。找到宝藏意味着最多距离它。代理做出了一系列动作。它们每个都在于在选定的距离处沿选定的方向直接移动。在开始和每次移动之后，代理都会得到一个提示，该提示由小于$2π$的正角组成，其顶点处于代理的当前位置以及所包含宝藏的位置。我们调查了这些提示如何使用确定性算法降低寻找宝藏的成本的问题，其中成本是代理轨迹的最差总长度。众所周知，没有任何提示，最佳（最坏情况）成本为$θ（d^2）$。我们表明，如果给出的所有角度最多都是$π$，那么成本可以降低到$ o（d）$，这是最佳的。如果所有角度最多都是$β$，其中$β<2π$是代理商不知道的常数，那么对于某些$ε> 0 $来说，成本最多为$ o（d^{2-ε}）$。对于这两种积极的结果，我们提出确定性算法，以实现上述成本。最后，如果给出提示的角度可能是任意的，小于$2π$，那么我们表明成本$θ（d^2）$无法击败。
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 $Θ(D^2)$. We show that if all angles given as hints are at most $π$, then the cost can be lowered to $O(D)$, which is optimal. If all angles are at most $β$, where $β<2π$ is a constant unknown to the agent, then the cost is at most $O(D^{2-ε})$, 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 $Θ(D^2)$ cannot be beaten.
