Summary
This paper studies how multiple robots moving at the same speed can find a hidden target on a flat surface. They discover the target not by seeing it directly but when the target lies exactly on the line segment connecting two robots. The authors find the best possible ways for two and more robots to do this efficiently, depending on whether they know how far the target is or not. For two robots, they provide exact limits on how well any method can perform compared to an ideal case. For three or more robots, they find a precise ratio that applies no matter what. These results help understand how groups of robots can collaborate to locate unknown points.
What this means in practice
- •For robotics engineers: Design cooperative robot teams efficiently locating targets when direct line-of-sight sensing is limited to connections between pairs of robots in planar environments.
- •For sensor network designers: Develop algorithms for sensor nodes that detect events based on conditions along segments joining pairs of nodes rather than direct detection.
A theory result. No direct application yet.
Abstract
We study deterministic search by $n \geq 2$ unit-speed robots starting at the origin of the Euclidean plane. We introduce the concept of \emph{segment visibility} whereby a stationary target $x$ at distance $d=\|x\|>0$ is discovered at the first instant $t$ when $x$ belongs to the segment joining a pair of robots at time $t$. Discovery time is compared with the omniscient optimum $d$. We distinguish two knowledge models according to whether the robots know $d$ in advance. For $n=2$ robots, in the \emph{known-$d$} model, we give a symmetric four-phase algorithm and prove that its competitive ratio is optimal: $1+\sqrt3+π/6$; the matching lower bound follows from the known-distance two-robot shoreline-search theorem through an explicit reduction to segment detection. For $n=2$ robots, in the \emph{unknown-$d$} model, a three-circle construction and a quantitative initial-path estimate yield the stronger lower bound $\sqrt3+π/6+\sqrt{17}/4 \approx3.286425990$, giving an explicit positive cost for not knowing the radius; we also analyze a feasible antipodal-diameter logarithmic-spiral algorithm with optimized ratio $8.928516954\ldots$, thus proving that the competitive ratio when $d$ is unknown is at least $ \sqrt3+π/6+\sqrt{17}/4 $ and at most $8.928516954\ldots.$ For $n \geq 3$ robots, the competitive ratio of finding the target is exactly $\sec (π/n)$ regardless of whether or not $d$ is known to the robots.