← 研踪 PaperTrailarXiv: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
摘要
We study the online target coverage problem for a mobile drone equipped with a camera with fixed scanning half-angle . Targets appear online at arbitrary positions along the -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 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 and peaks at when . Going further, we introduce a family of memoryless, state-based linear interpolation algorithms (generalizing the \textsc{Midpoint} rule at ) and prove that the optimized algorithm strictly outperforms -\textsc{Hedge} throughout , achieving a tight competitive ratio of at while matching the optimal bound for -\textsc{Hedge} on . 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 . This lower bound attains its maximum at with value , narrowing the optimal competitive ratio at to the interval .
作者备注: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
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 . Targets appear online at arbitrary positions along the -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 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 and peaks at when . Going further, we introduce a family of memoryless, state-based linear interpolation algorithms (generalizing the \textsc{Midpoint} rule at ) and prove that the optimized algorithm strictly outperforms -\textsc{Hedge} throughout , achieving a tight competitive ratio of at while matching the optimal bound for -\textsc{Hedge} on . 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 . This lower bound attains its maximum at with value , narrowing the optimal competitive ratio at to the interval .
查看此版本解读 →查看此版本原文 ↗