Search and Rescue on the Plane

Abstract

We study a planar variant of the search and rescue problem whereby an agent starting at an arbitrary position $P_{\theta ,r}=(r\cos \theta ,r\sin \theta )$ in the plane must locate an object at an unknown position on the positive $x$-axis and deliver it to the origin. Our main contribution is to characterize the optimal form of any competitive algorithm, derive closed-form expressions for the competitive ratio, and identify a critical angle ${\theta }^{\ast }\approx 15.6^{\circ }$ which yields a phase transition to optimal competitive search and delivery in the following sense. For each angle $-\pi \le \theta \le \pi$ we compute a checkpoint (landing position on the $x$-axis) where the agent must go first prior to initiating a search on the $x$-axis in order to optimize the competitive ratio of search and delivery. We show that if $|\theta |\ge {\theta }^{\ast }$ then the checkpoint is at the origin, while if $|\theta |<{\theta }^{\ast }$ then the agent should land at the checkpoint $(r\cdot k_{|\theta |},0)$ on the $x$-axis, where $k_{|\theta |}$ is a real number given by an explicit formula we present.