Searching in Euclidean Spaces with Predictions

We study the problem of searching for a target at some unknown location in ${\mathbb{R}}^d$ when additional information regarding the position of the target is available in the form of predictions. In our setting, predictions come as approximate distances to the target: for each point $p\in {\mathbb{R}}^d$ that the searcher visits, we obtain a value $\lambda (p)$ such that $\mathrm{\mid }p\mathit{t}\mathrm{\mid }\le \lambda (p)\le c\cdot \mathrm{\mid }p\mathit{t}\mathrm{\mid }$, where $c\ge 1$ is a fixed constant, $\mathit{t}$ is the position of the target, and $\mathrm{\mid }p\mathit{t}\mathrm{\mid }$ is the Euclidean distance of $p$ to $\mathit{t}$. The cost of the search is the length of the path followed by the searcher. Our main positive result is a strategy that achieves $(10c{)}^{d+1}$-competitive ratio, even when the constant $c$ is unknown. We also give a lower bound of roughly $(c\mathrm{/}4{)}^{d-1}$ on the competitive ratio of any search strategy in ${\text{RR}}^d$, assuming that $c\ge 4$.