Online Drone Coverage of Targets on a Line
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}]$.
cs.DS