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)}$。

0
下载
关闭预览

相关内容

【2023新书】使用Python进行统计和数据可视化,554页pdf
专知会员服务
126+阅读 · 2023年1月29日
【ICML2022】在线决策Transformer
专知会员服务
33+阅读 · 2022年7月27日
【2022新书】高效深度学习,Efficient Deep Learning Book
专知会员服务
117+阅读 · 2022年4月21日
NP完备破解羊了个羊?
新智元
0+阅读 · 2022年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
R工程化—Rest API 之plumber包
R语言中文社区
11+阅读 · 2018年12月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【CNN】一文读懂卷积神经网络CNN
产业智能官
18+阅读 · 2018年1月2日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月17日
Arxiv
0+阅读 · 2023年5月17日
Arxiv
0+阅读 · 2023年5月16日
Arxiv
0+阅读 · 2023年5月16日
Arxiv
0+阅读 · 2023年5月16日
Arxiv
0+阅读 · 2023年5月15日
Arxiv
10+阅读 · 2021年11月3日
VIP会员
相关VIP内容
相关资讯
NP完备破解羊了个羊?
新智元
0+阅读 · 2022年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
R工程化—Rest API 之plumber包
R语言中文社区
11+阅读 · 2018年12月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【CNN】一文读懂卷积神经网络CNN
产业智能官
18+阅读 · 2018年1月2日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员