Linear Search with Probabilistic Detection and Variable Speeds

Abstract

We present results on new variants of the famous 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.