跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2604.02491 · v2

Online Drone Coverage of Targets on a Line

首次提交 2026-04-03 03:48
版本更新 2026-11-15 05:59
雷达观测 2026-11-17 12:06
arXiv ↗PDF ↗

摘要

We study the online target coverage problem for a mobile drone equipped with a camera with fixed scanning half-angle α∈(0,π/2)α\in (0, π/2). Targets appear online at arbitrary positions along the xx-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 α∈(0,π/2)α\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 α∈(π/6,π/3)α\in (π/6, π/3) and peaks at 5/45/4 when α=π/4α= π/4. Going further, we introduce a family of memoryless, state-based linear interpolation algorithms Aλ\mathcal{A}_λ (generalizing the \textsc{Midpoint} rule at α=π/4α= π/4) and prove that the optimized algorithm Aλ∗\mathcal{A}_{λ^*} strictly outperforms β∗β^*-\textsc{Hedge} throughout α∈(0,π/3)α\in (0, π/3), achieving a tight competitive ratio of 3/2≈1.2247\sqrt{3/2} \approx 1.2247 at α=π/4α= π/4 while matching the optimal bound csc⁡α\cscα for β∗β^*-\textsc{Hedge} on [π/3,π/2)[π/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 α∈(0,π/2)α\in (0, π/2). This lower bound attains its maximum at α=π/4α= π/4 with value (1+2)/2≈1.2071(1 + \sqrt{2})/2 \approx 1.2071, narrowing the optimal competitive ratio at α=π/4α= π/4 to the interval [(1+2)/2, 3/2][(1+\sqrt{2})/2,\, \sqrt{3/2}].

作者备注:This is the full version of the paper that appeared in the Proceedings of the 37th International Workshop on Combinatorial Algorithms (IWOCA 2026), Clermont-Ferrand, France, on June 8-12, 2026. It corrects and extends several results from the initial ArXiv version of the full conference paper

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-15 05:59 · 最新观测版本

Online Drone Coverage of Targets on a Line

We study the online target coverage problem for a mobile drone equipped with a camera with fixed scanning half-angle α∈(0,π/2)α\in (0, π/2). Targets appear online at arbitrary positions along the xx-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 α∈(0,π/2)α\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 α∈(π/6,π/3)α\in (π/6, π/3) and peaks at 5/45/4 when α=π/4α= π/4. Going further, we introduce a family of memoryless, state-based linear interpolation algorithms Aλ\mathcal{A}_λ (generalizing the \textsc{Midpoint} rule at α=π/4α= π/4) and prove that the optimized algorithm Aλ∗\mathcal{A}_{λ^*} strictly outperforms β∗β^*-\textsc{Hedge} throughout α∈(0,π/3)α\in (0, π/3), achieving a tight competitive ratio of 3/2≈1.2247\sqrt{3/2} \approx 1.2247 at α=π/4α= π/4 while matching the optimal bound csc⁡α\cscα for β∗β^*-\textsc{Hedge} on [π/3,π/2)[π/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 α∈(0,π/2)α\in (0, π/2). This lower bound attains its maximum at α=π/4α= π/4 with value (1+2)/2≈1.2071(1 + \sqrt{2})/2 \approx 1.2071, narrowing the optimal competitive ratio at α=π/4α= π/4 to the interval [(1+2)/2, 3/2][(1+\sqrt{2})/2,\, \sqrt{3/2}].

查看此版本解读 →查看此版本原文 ↗