本文为以色列理工学院（作者：Nir Drucker）的硕士论文，共65页。

许多无人驾驶飞行器（UAV）针对的国防和民用相关任务涉及在各种时间限制下监测预先确定的一组地面目标。特别是我们关注的任务中，每个目标都与一个相对的截止时间相关联，这意味着该目标的两次连续扫描之间的时间有一个上限。这些限制可能与目标的性质和客户端对特定场景的反应速度有关。人们可以想象，无人机的长距离巡逻，其中某些敏感位置与相对截止时间有关，该截止时间由地面部队对无人机操作员检测到的事件作出反应的速度来定义；或者监视敌人聚集的情况，试图在敌人聚集时检测到各种变化。

民用方面可能包括设施监测和森林火灾监测。在每一种这样的应用中，相对期限是根据缩短反应时间与增加无人机成本的相对值来计算的。上面讨论的任务是例行程序，可以用循环计划来解决，很少有必要偏离这样的计划。这与当今的无人机地面手动引导形成了鲜明对比。装载预先计划的飞行路线是由现代无人机系统支持的，但据我们所知，没有人使用这种能力来规划无人机机群的最佳循环路线。鉴于无人机在过去十年的技术能力和成功经验方面取得了重大进展，国防和民用相关的市场正在迅速增长，因此各类无人机的自动化是一个迫切需要。

在这项工作中，我们正式定义了CR-UAV问题，并证明了所需无人机数量的下限。这个界限对于节省计算时间很有用，避免了代价高昂的、注定要失败的搜索。我们研究了解决这个（NP-hard）问题的几个方案。具体来说，提出了一个基于析取MILP的模型。我们将约束集合定义为一阶差分约束理论，即布尔变量与x-y≤c形式的约束的布尔组合，其中x、y∈R、c是常数，并说明了如何不仅可以用MILP工具，而且可以用SMT（Satisfiability Modulo Theory）解算器求解。我们提出了一种基于DFS的搜索算法，该算法可以探索有界循环路径；展示了一种基于DFS的搜索算法，该算法探索了（否则是连续的）状态空间的离散化版本。最后，我们对这些方法进行了广泛的实证评估。

Many defense and civilian-related tasks targeted by Unmanned Aerial Vehicles (UAVs) are concerned with monitoring of a predefined set of ground targets under various timing constraints. In particular we are concerned with tasks in which each target is associated with a relative deadline, which means that there is an upper bound on the time between two consecutive scans of that target. Such constraints may be related to the nature of the target and the speed in which the client needs to react to a particular scenario. One may imagine a long border patrolled by UAVs, where certain sensitive locations are associated with a relative deadline that is defined by the speed in which ground forces can react to an event detected by the UAV operator; or a situation in which a military monitors enemy gatherings, attempting to detect various changes when they occur. Civilian applications may include monitoring of facilities and monitoring of forests for fire. In each such application the relative deadline is calculated according to the relative value of shortening the time to react versus the cost of additional UAVs. The tasks discussed above are (seemingly endless) routines that can be solved with a cyclic plan. Only rarely it is necessary to deviate from such a plan. This stands in stark contrast to the common practice today of manually guiding the UAVs from the ground. Loading preplanned flight routes are supported by modern UAV systems, but no one as far as we know used this capability for planning optimal cyclic routes of fleets of UAVs. Automation of UAVs in various levels is an urgent need since the market, both the defense and civilian-related, is growing rapidly given the major progress in their capabilities and proven success in the last decade.

In this work we formally define the CR-UAV problem and prove a lower-bound on the number of required UAVs. This bound is useful for saving computation time, as it is easy to compute and avoids costly search that is bound to fail. We study several venues for solving this (NP-hard) problem. Specifically, we propose a model based on disjunctive MILP. We identify the set of constraints as belonging to the first-order theory of difference constraints, namely a Boolean combination of Boolean variables and constraints of the form x − y ≤ c where x, y ∈ R and c is a constant, and explain how they can be solved not only with MILP tools, but also with SMT (Satisfiability Modulo Theory) solvers. We present a DFS-based search algorithm that explores bounded cyclic paths; We show a DFS-based algorithm that explores a discretized version of the (otherwise continuous) state-space. Finally, we present the results of our extensive empirical evaluation of these methods.

1 引言

2 CR-UAV问题的正式定义

3 UAV数量的下限

4 积分解的充分性考虑

5 约束模型

6 CR-UAV建模为有限状态系统

7 其它模型

8 实验结果

9 结论

10 文献回顾

11 未来研究展望

附录A 时间自动机

附录B 一种显式搜索算法 

下载英文原文地址：

http://page3.dfpan.com/fs/6l2cejb222415239169/ 

更多精彩文章请关注微信号：