Multi-Region Coverage Path Plann

Multi-Region Coverage Path Planning for Heterogeneous Unmanned Aerial Vehicles Systems（2019西北工业大学）

多区域覆盖路径规划异构无人机系统

摘要：最近无人驾驶飞行器（UAVs），由于他们强大的自主权和适应能力，在军事和民用被广泛采用。虽然在开发具有搜索或监视任务的系统的时候，无人机可以有效降低成本和提高灵活性，但是它们导致复杂的路径规划问题。特别是在区域覆盖系统，覆盖路径规划问题，其中寻求覆盖所有感兴趣区域的路径，具有NP-Hard，计算复杂性很难解决。在本文中，

我们研究了多无人机在多区域系统中异构的覆盖路径规划问题。首先，使用无人机模型和区域，基于混合整数线性的精确公式提出编程以产生最佳覆盖路径。然后考虑区域和扫描时间

区域之间的飞行时间，提出了一种有效的启发式方法分配区域并获得无人机的覆盖命令。最后，进行实验以显示几个方面提出的启发式方法的可靠性和效率。

关键词 - 无人机，覆盖路径规划， 区域覆盖，覆盖顺序

1 介绍

随着电气和计算机的快速发展工程，无人机（UAV）已广泛应用被军事和民用领域采用，如监视，搜索，救援和农业[1]。相比有人驾驶的车辆，无人机不会放置人的生命处于风险中[2]，并且在执行中具有显着的优势沉闷和危险的任务[3]。 由于无人机的能量有限，通信带宽和感应范围，很多实用应用程序已经超出了单个无人机的能力[4]。具有高并行性和鲁棒性的多个无人机系统具有逐渐成为一个独立的研究领域，以利用无人机的合作和获得更高的运作

效率[5]。

虽然无人机可以实现有效的成本降低和在实际应用的开发中灵活性增强，它们使得系统执行路径更加复杂规划，系统决策和协作控制[6]。 特别是在区域覆盖系统中的位置侦察目标的不确定性或兴趣点关注某些地区的所有信息[7]，覆盖路径规划问题具有NP-Hard计算复杂性[8]并且很难解决。无人机的覆盖路径规划是一个复杂的全球性最佳问题，主要是寻求一个能够完全覆盖给定感兴趣区域的最佳飞行路径在特定的约束条件下。 覆盖路径规划

是无人机系统的关键研究点之一[9]许多因素，如地形，数据，威胁信息，燃料消费[10]和系统可调度性[11]，应该是考虑到了。 无人机的最佳覆盖路径应该获得这样的时间成本可以降低尽可能多。

面对无人机数量的显着增加和地区，系统设计师逐渐倾向于依赖决策工具为每个无人机产生有效的覆盖路径。 已经提出了一系列算法来解决这个问题从几何角度来看问题。 但是，大多数研究主要集中在单个区域研究无人机的覆盖路径规划，多个无人机覆盖多个分离地区

由于其非凡的复杂性通常不会被考虑在内。

通常采用多种异构无人机在实际应用中覆盖多个分离区域。例如，在军事领域，需要多个无人机完全参与搜索任务的同时在有限的时间内找出敌人的目标。在农业领域，多个无人机用于检测植被和状态从山上分离的梯田上的杂草生长[12]。 在所有上述应用中，多个无人机都有合作搜索各个区域以检测对象利益。区域应分配给最好的无人机和覆盖路径应该优化。覆盖路径规划无人机对于保证正确有效地完成搜索或检测任务是必要且重要的。

在本文中，我们研究了对于多个无人机的覆盖路径规划问题关于多个分离区域。 我们找到一种有效的方法来分配区域并且生产每个无人机的覆盖命令（顺序），以便覆盖任务尽早完成。论文的主要贡献可归纳如下：

1.建立了异构无人机和分离区域的模型，基于混合整数的精确公式提出线性编程以获得最佳覆盖无人机的路径。

2.考虑到区域的扫描时间以及区域之间的飞行时间，提出了一种启发式方法将区域分配给无人机并优化覆盖范围命令。这种启发式方法并不能完全搜索解空间，可以有效的解决混合无人机覆盖路径规划问题。

本文的其余部分安排如下。 第二节介绍相关工作。第III节给出了使用的模型在本文中，并提出了一个确切的表述。第四节提出了一种有效的启发式方法来获得覆盖顺序每个无人机。第五节进行实验和分析我们的方法的表现。 最后，第VI节给出了一个本文的摘要和未来工作的方向。

2 相关工作

作为任务规划的一部分，覆盖路径规划（CPP）在提高生存能力和任务能力方面发挥着重要作用[7]通过寻找覆盖感兴趣区域的路径。 CPP已在文献中广泛涉及，主要是研究

影响因素，如地区的形状，内部障碍和无人机表现。基于无人机的速度和能量相关，[1]的作者为单个无人机建立了一个速度能量模型，通过将分辨率约束纳入路径并提出了覆盖范围生成算法。在[13]中，CPP问题被制定为旅行商问题（TSP）和多人口并行遗传算法用于模拟覆盖路径在有障碍的地区生成。随着能量和无人机的可操作性的约束[14]中的作者提出了满足要求的覆盖路径规划策略高度自治和实时能力。然而，在所有的那些作品中，无人机的数量只有一个，这样的结果不能适应复杂的系统以及使用多个无人机的系统。

目前，研究覆盖路径规划问题

通常主要关注多无人机覆盖单个区域。覆盖路径规划为多个异构，单个区域的无人机需要三个重要步骤：异构无人机的性能评估，区域分割和分配，以及覆盖路径生成。路径规划，

也就是任务调度[15]，是一个重要的要求用于无人机的无碰撞操作。在[16]中，作者首先通过考虑无人机的相对能力和初始位置提出了将整个区域划分为不同的算法部分。然后他们使用往复路径生成方法为每个无人机提供覆盖路径。在[17]中，提出了一种合作搜索方法将多个智能体整合到有利的形式中，并且不会没有受到一些无人机中途故障的影响。虽然上述研究分析了CPP的问题多个无人机，它们只能在只有一个无人机的情况下工作区域被认为。这种限制严重限制了使用提出的算法。这些结果不可能是直接的扩展到多个无人机合作的应用

涵盖多个地区。

多个地区的多个无人机的CPP问题是通常建模为组合优化模型和用各种优化算法解决。在[18]中，CPP问题被建模为商业供需网络物流优化模型，路径规划通过最小化总成本实现多个无人机网络流量。在[19]中，作者提出了一个整数用于多个UAV任务分配的编程模型，以及模拟典型的敌人灭火。在[20]中，作者模仿无人机作为Dubins飞行的车辆具有有界转弯半径的恒定高度，并提供车队保护一组地面车辆。CPP多个地区的多个无人机问题通常都有一个问题具有大量优化目标的高复杂性和约束。为了找到确切的覆盖路径无人机，现有的优化算法应该考虑所有可能的区域分配并需要大量资金时间特别是在硬实时的应用中要求，解决CPP问题是不可接受的通过使用现有的优化算法。

3 系统模型和精确公式

3.1 符号和系统模型（多无人机以及多区域搜索）

无人机U不同的速度和传感器性能，具有多个扫描区域R ，一个无人机其中一个元组<V,W> V为速度，W为速度V下面的扫描宽度。

3.2 确切的公式

在这一小节中，基于混合整数线性规划（MILP）[21]，我们提出了一个精确的公式

多个无人机的路径规划问题区域。 MILP是一种用于覆盖路径规划的强大方法问题是因为它可以处理具有离散的动态系统决策变量和许多有效的求解器可用。路径规划问题被定义为最小化a线性目标函数（所有无人机的最大时间成本）受线性约束（区域的覆盖约束）。

该公式保证所有区域都被完全覆盖，并为飞行中的元素寻求最佳值路径数组，以最大限度地减少所有无人机的最大时间成本。约束（3）表明无人机起飞的数量从基地起不超过无人机的总数。约束（4）保证无人机起飞的数量从基地起飞等于飞回的无人机数量基地。 约束（5）和（6）表示不重叠区域限制：每个区域都应该被覆盖一只也是唯一一架无人机。

4 最有效的时间比率第一算法

即使提出的MILP配方可以找到一个确切的覆盖路径规划解决方案，它考虑所有可能

无人机的飞行路径和覆盖顺序，这是非常的费时费力。这是因为多个无人机的覆盖路径规划问题是NP难问题。问题的复杂性迅速增加变量的数量增加，因此经常不适合实时实际应用。相对而言本节提出了有效的启发式算法。

基于第三部分中建立的无人机和区域模型。我们提出最高有效时间比率（HETRF）算法来计划每个无人机的覆盖路径。这个算法需要考虑到每两个地区之间的飞行时间和扫描每个区域的时间。在这个算法中，区域大面积或靠近当前扫描区域最有可能在下一步被选择。同时，通过调整每个无人机的覆盖顺序，采用一个优化策略来降低时间成本。

HETRF是有界数的路径规划算法异构无人机，有两个主要阶段：一个地区分配阶段和序列调整阶段。该区域当无人机完成其覆盖任务时，分配阶段计算所有未分配区域的有效时间比率，选择具有最高有效时间比率的区域，并指定这个空闲的无人机到选定的区域。序列调整阶段调整分配给相同的无人机给区域的覆盖顺序，并最大限度地减少每个所需的时间成本

无人机。

4.1 区域分配阶段

中间漏掉 具体可以见论文

风景图片

4.2 序列调整阶段

在区域分配阶段，区域基于其有效时间比率被分配给无人机。每个无人机获得区域序列，其中所有区域都应该被这架无人机排列顺序覆盖。但是，在区域分配阶段，区域的选择完全基于它们的有效时间比率，在大多数情况下，覆盖顺序并不是最佳的。 一个序列调整阶段需要采用优化政策改变每个无人机的覆盖顺序，使时间成本将尽可能减少。

最短距离优先策略是最常见的策略之一在路径规划问题中使用了优化策略。 我们也采用这种策略来调整无人机的覆盖顺序。在这个策略中，一旦无人机完成了一个给定区域的覆盖任务，剩余区域和当前区域之间的距离应该计算。无人机将选择最接近的区域做覆盖任务。一轮又一轮调整，直到考虑所有地区。最后一个新的获得每个UAV的区域序列。无人机将

从基地起飞，覆盖新序列中的区域一个接一个地飞回基地。

4.3 运行时间分析

我们分析了HETRF的计算复杂性本小节中的算法。从算法1我们知道，算法的主要计算部分是从第3到第28行，它有两个部分：区域分配阶段和序列调整阶段。

中间有一段没有翻译

但是，数量该算法的计算步骤非常考虑悲观的情况，我们在实验中发现了我们的方法的平均表现通常表现更好解决覆盖路径规划问题。

5 试验和结果

此方法和三个存在的方法比较 the large area first scheduling (LAF) algorithm, the large area first scheduling (LAF) algorithm, the short distance first scheduling (SDF) algorithm and genetic algorithm (GA)

5.1 区域生成

5.2 绩效评估

[图片上传失败...(image-2e3d52-1566369937627)]

6 结论和未来工作

在本文中，我们旨在解决覆盖路径多区域异构无人机的规划问题。我们建立了无人机和地区的模型，并提出了一个基于混合整数线性规划的精确公式完全搜索解空间并获得精确的覆盖路径。同时，我们提出了一种启发式分配方法区域并获得每个无人机的覆盖顺序。该启发式考虑了区域上的扫描时间和地区之间的飞行时间，可以解决覆盖范围路径规划问题有效。

虽然我们的方法在相对较短的时间内可以实现合理的解决方案，我们想找到一个更有效的方法来改善其性能。同时，我们有兴趣研究在有障碍的地区，覆盖路径规划问题想看看是否有些本文的结果可以适应更复杂的情况。

问题的总结：

1 文中提到的不同速度指的是不同的无人机具有固定的不同速度。

2 多个区域并不是紧挨着中间有好多的区域，关于区域的中心自有相应的计算方法

3 最短距离优先策略是怎么一回事呢？

4 Fig2的时候初始的时候怎么分派无人机进行任务执行？

5 最后的Average execution time是什么含义呢？