We present results on new variants of the linear search (or cow-path) problem that involves an agent searching for a target with unknown position on the infinite line. We consider the variant where the agent can move either at speed 1 or at a slower speed \(v \in [0, 1)\) . When traveling at the slower speed v, the agent is guaranteed to detect the target upon passing through its location. When traveling at speed 1, however, the agent, upon passing through the target’s location, detects it with probability \(p \in [0, 1]\) . We present algorithms and provide upper bounds for the competitive ratios for three cases separately: when \(p=0\) , \(v=0\) , and when \(p,v \in (0,1)\) . We also prove that the provided algorithm for the \(p=0\) case is optimal.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Linear Search with Probabilistic Detection and Variable Speeds

  • Jared Coleman,
  • Oscar Morales-Ponce

摘要

We present results on new variants of the linear search (or cow-path) problem that involves an agent searching for a target with unknown position on the infinite line. We consider the variant where the agent can move either at speed 1 or at a slower speed \(v \in [0, 1)\) . When traveling at the slower speed v, the agent is guaranteed to detect the target upon passing through its location. When traveling at speed 1, however, the agent, upon passing through the target’s location, detects it with probability \(p \in [0, 1]\) . We present algorithms and provide upper bounds for the competitive ratios for three cases separately: when \(p=0\) , \(v=0\) , and when \(p,v \in (0,1)\) . We also prove that the provided algorithm for the \(p=0\) case is optimal.