We consider search by mobile agents for a hidden, idle target, placed on the infinite line. Feasible solutions are agent trajectories in which all agents reach the target sooner or later. A special feature of our problem is that the agents are $p$-faulty, meaning that every attempt to change direction is an independent Bernoulli trial with known probability $p$, where $p$ is the probability that a turn fails. We are looking for agent trajectories that minimize the worst-case expected termination time, relative to competitive analysis. First, we study linear search with one deterministic $p$-faulty agent, i.e., with no access to random oracles, $p\in (0,1/2)$. For this problem, we provide trajectories that leverage the probabilistic faults into an algorithmic advantage. Our strongest result pertains to a search algorithm (deterministic, aside from the adversarial probabilistic faults) which, as $p\to 0$, has optimal performance $4.59112+\epsilon$, up to the additive term $\epsilon$ that can be arbitrarily small. Additionally, it has performance less than $9$ for $p\leq 0.390388$. When $p\to 1/2$, our algorithm has performance $\Theta(1/(1-2p))$, which we also show is optimal up to a constant factor. Second, we consider linear search with two $p$-faulty agents, $p\in (0,1/2)$, for which we provide three algorithms of different advantages, all with a bounded competitive ratio even as $p\rightarrow 1/2$. Indeed, for this problem, we show how the agents can simulate the trajectory of any $0$-faulty agent (deterministic or randomized), independently of the underlying communication model. As a result, searching with two agents allows for a solution with a competitive ratio of $9+\epsilon$, or a competitive ratio of $4.59112+\epsilon$. Our final contribution is a novel algorithm for searching with two $p$-faulty agents that achieves a competitive ratio $3+4\sqrt{p(1-p)}$.
翻译:我们考虑移动代理在无限线上搜寻隐藏的、空闲的目标。可行的解决方案是代理的轨迹,在这些轨迹中,所有代理都会迟早到达目标。我们问题的一个特殊特点是代理是 $p$-错误的,这意味着每次改变方向的尝试都是独立伯努利试验,其已知概率为 $p$,其中 $p$ 是转向失败的概率。我们寻找代理轨迹,使得最坏情况下相对于竞争性分析的期望终止时间最小化。首先,我们研究带有一个确定的 $p$-错误代理的线性搜索,即没有访问随机奥拉克尔,$p \in (0,1/2)$。对于此问题,我们提供了利用概率错误为算法优势的轨迹。我们最强的结果涉及搜索算法(除了对抗性概率性错误之外是确定性的),它的性能在 $p \rightarrow 0$ 时是最佳的,达到 $4.59112+\epsilon$,其中 $\epsilon$ 的附加项可以任意小。此外,它在 $p \leq 0.390388$ 时的性能低于 $9$。当 $p \rightarrow 1/2$ 时,我们的算法的性能为 $\Theta(1/(1-2p))$,我们还表明该算法在常数因子上是最优的。其次,我们考虑具有两个 $p$-错误代理的线性搜索,$p \in (0,1/2)$,我们提供了三种不同优点的算法,即使在 $p \rightarrow 1/2$ 的情况下,它们的竞争比也是有界的。事实上,对于这个问题,我们展示了如何使代理能够模拟任何 $0$-错误代理(确定性或随机化),而不依赖于底层通信模型。因此,使用两个代理进行搜索可以得到一个竞争比为 $9+\epsilon$ 或一个竞争比为 $4.59112+\epsilon$ 的解决方案。我们最后的贡献是一种用两个 $p$-错误代理进行搜索的新算法,它实现了一个竞争比为 $3+4\sqrt{p(1-p)}$。