Paper detail

Towards a General Framework for Searching on a Line and Searching on $m$ Rays

Consider the following classical search problem: given a target point $p\in \Re$, starting at the origin, find $p$ with minimum cost, where cost is defined as the distance travelled. Let $D$ be the distance of $p$ from the origin. When no lower bound on $D$ is given, no competitive search strategy exists. Demaine, Fekete and Gal (Online searching with turn cost, Theor. Comput. Sci., 361(2-3):342-355, 2006) considered the situation where no lower bound on $D$ is given but a fixed \emph{turn cost} $t>0$ is charged every time the searcher changes direction. When the total cost is expressed as $c D+ϕ$, where $c$ and $ϕ$ are positive constants, they showed that if $c$ is set to $9$, then the optimal search strategy has a cost of $9D+2t$. Although their strategy is optimal for $c=9$, we prove that the minimum cost in their framework is $5D+t+2\sqrt{2D(2D+t)} < 9D+2t$. Note that the minimum cost requires knowledge of $D$. However, given $D$, the optimal strategy has a smaller cost of $3D+t$. Therefore, this problem cannot be solved optimally and exactly when no lower bound on $D$ is given. To resolve this issue, we introduce a general framework where the cost of moving distance $x$ away from the origin is $α_1 x+β_1$ and the cost of moving distance $y$ towards the origin is $α_2 y+β_2$ for constants $α_1,α_2,β_1,β_2$. Given a lower bound $λ$ on $D$, we provide a provably optimal competitive search strategy when $α_1,α_2,β_1,β_2 \geq 0$ and $α_1+α_2 > 0$. Finally, we address the problem of searching for a target lying on one of $m$ rays extending from the origin where the cost is measured as the total distance travelled plus $t \geq 0$ times the number of turns. We provide a search strategy and compute its cost. We prove our strategy is optimal for small values of $t$ and conjecture it is always optimal.