Under segment visibility, two robots discover a target as soon as it belongs to the segment joining their positions, even if neither robot has physically reached it. We study two unit-speed robots starting at the center of a unit disk that must both reach an exit (target) placed at an unknown point of its boundary. In our model robots are permitted to leave the disk while searching. We give a three-phase tangent-and-arc algorithm whose exact worst-case evacuation time is 2\sqrt{3}+π/3 \approx 4.511299$. We also prove a matching lower bound for the class of descending horizontal full-slice sweeps, allowing asymmetric robot trajectories. The proof uses an exterior path-length inequality and a feasible minimum-half-width symmetrization. Determining the optimal time over all segment-visibility algorithms remains open.
Stefan Dobrev, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, Sunil Shende
原文摘要
We study the online target coverage problem for a mobile drone equipped with a camera with fixed scanning half-angle $α\in (0, π/2)$. Targets appear online at arbitrary positions along the $x$-axis, and upon each arrival the drone must move to a feasible position whose visibility interval covers both the newly revealed target and all previously arrived targets. The objective is to minimize the total Euclidean length of the drone's trajectory, evaluated against an optimal offline trajectory via the competitive ratio. We establish exact competitive ratios across the range $α\in (0, π/2)$ for three natural baseline algorithms,\textsc{Straight-Up}, \textsc{Cone-Apex}, and \textsc{Greedy}. We then analyze fixed-angle steering strategies and derive the optimal fixed-angle algorithm $β^*$-\textsc{Hedge}, which improves upon the baselines for $α\in (π/6, π/3)$ and peaks at $5/4$ when $α= π/4$. Going further, we introduce a family of memoryless, state-based linear interpolation algorithms $\mathcal{A}_λ$ (generalizing the \textsc{Midpoint} rule at $α= π/4$) and prove that the optimized algorithm $\mathcal{A}_{λ^*}$ strictly outperforms $β^*$-\textsc{Hedge} throughout $α\in (0, π/3)$, achieving a tight competitive ratio of $\sqrt{3/2} \approx 1.2247$ at $α= π/4$ while matching the optimal bound $\cscα$ for $β^*$-\textsc{Hedge} on $[π/3, π/2)$. Finally, we establish a universal lower bound on the competitive ratio of any deterministic or randomized online algorithm (against an oblivious adversary) across the entire domain $α\in (0, π/2)$. This lower bound attains its maximum at $α= π/4$ with value $(1 + \sqrt{2})/2 \approx 1.2071$, narrowing the optimal competitive ratio at $α= π/4$ to the interval $[(1+\sqrt{2})/2,\, \sqrt{3/2}]$.
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.