论文标题
线搜索一个遗忘的移动目标
Line Search for an Oblivious Moving Target
论文作者
论文摘要
考虑在无限的线路上搜索，该线路涉及从线路的起点开始的自主机器人，以及在初始距离处的忽略移动目标$ d \ geq 1 $。机器人可以以恒定的最大速度$ 1 $的速度改变方向并在线上移动，而目标也以恒定速度$ v> 0 $在线移动，但无法更改其速度或方向。目标是让机器人在尽可能少的时间内赶上目标。 $ v = 0 $和目标的初始距离$ d $的经典案例是机器人未知的是``牛路问题''。 Alpert和Gal给出了一种最佳算法，即具有未知初始距离$ d $的目标，以已知的速度$ v <1 $移出机器人。在本文中，我们为剩余的知识情况设计和分析搜索算法，即，当$ d $和$ v $知道$ v $时，$ v $是众所周知的，但是$ d $是未知的，但是当$ d $已知，但是当$ v $尚不清楚，而当$ v $和$ v $和$ d $ nes nes n n nes时。此外，对于每个知识模型，我们分别考虑目标远离原点以及朝向原点移动的情况。我们设计算法并分析上述所有八个病例的竞争比率。当目标朝着原点以及$ V $何时且目标远离原点时，所产生的竞争比率是最佳的。
Consider search on an infinite line involving an autonomous robot starting at the origin of the line and an oblivious moving target at initial distance $d \geq 1$ from it. The robot can change direction and move anywhere on the line with constant maximum speed $1$ while the target is also moving on the line with constant speed $v>0$ but is unable to change its speed or direction. The goal is for the robot to catch up to the target in as little time as possible. The classic case where $v=0$ and the target's initial distance $d$ is unknown to the robot is the well-studied ``cow-path problem''. Alpert and Gal gave an optimal algorithm for the case where a target with unknown initial distance $d$ is moving away from the robot with a known speed $v<1$. In this paper we design and analyze search algorithms for the remaining possible knowledge situations, namely, when $d$ and $v$ are known, when $v$ is known but $d$ is unknown, when $d$ is known but $v$ is unknown, and when both $v$ and $d$ are unknown. Furthermore, for each of these knowledge models we consider separately the case where the target is moving away from the origin and the case where it is moving toward the origin. We design algorithms and analyze competitive ratios for all eight cases above. The resulting competitive ratios are shown to be optimal when the target is moving towards the origin as well as when $v$ is known and the target is moving away from the origin.
