论文标题
外围监视问题的进展
Progress on a perimeter surveillance problem
论文作者
论文摘要
我们考虑了Kingston，Beard和Holt于2008年提出的外围监视问题，并于2019年由Davis，Humphrey和Kingston进行了研究。在此问题中，$ N $无人机监视有限的间隔，以统一的速度和交换信息，只有在遇到另一个无人机时才交换信息。金斯敦等。描述了一种特定的在线算法来协调其行为，并要求在无人机完全同步之前需要多长时间。他们将算法的行为分为两个阶段，并基于猜想的最坏情况结构在每个阶段的长度上呈现上限。戴维斯等。对第1阶段的猜想提出了反例。 我们在第2阶段提出了尖锐的上限，这表明在这种情况下，猜想最坏情况是正确的。我们还介绍了第1阶段的新下限和同步的总时间，并报告了获得上限的部分进展。
We consider a perimeter surveillance problem introduced by Kingston, Beard, and Holt in 2008 and studied by Davis, Humphrey, and Kingston in 2019. In this problem, $n$ drones surveil a finite interval, moving at uniform speed and exchanging information only when they meet another drone. Kingston et al. described a particular online algorithm for coordinating their behavior and asked for an upper bound on how long it can take before the drones are fully synchronized. They divided the algorithm's behavior into two phases, and presented upper bounds on the length of each phase based on conjectured worst-case configurations. Davis et al. presented counterexamples to the conjecture for phase 1. We present sharp upper bounds on phase 2 which show that in this case the conjectured worst case is correct. We also present new lower bounds on phase 1 and the total time to synchronization, and report partial progress towards obtaining an upper bound.
