智能无人机地图生成和搜索和救援行动离散路径规划

摘要

搜索和救援行动(SAR)发生在任何紧急情况下，人们参与和他们的生命有危险。这些操作现在是在先进技术的帮助下进行的，例如无人机(uav)。本文提出了无人机离散路径规划的几种计算方法。在此之前，对搜索区域进行智能表征，以估计网格地图的潜在风险/占用程度。这种估计主要是基于模糊逻辑，考虑了不同的因素。然后，应用了四种方法来计算路径规划:吸引法、模糊逻辑法、ANFIS法和粒子群算法。它们都计算无人机要跟踪的航路点的位置，以最小化距离和人们所暴露的风险。在此基础上，针对多架无人机同时搜索的情况，提出了相应的搜索策略，并对无人机群的形成进行了讨论。最后，在一个真实的仿真场景中对这四种不同数量无人机的路径规划方案进行了测试，并对每种方法的性能进行了分析和比较。

1.介绍

不幸的是，每年都有自然灾害，像火灾或地震影响的城市，城镇和自然环境的一些消息。此外，我们也看到人类悲剧的海上事故或谁得到在危险的地方迷路的人。所有这些情况，和其他许多人，都有一个共同的重要方面。他们受到参与这样或那样的险情和直接风险这种情况下许多人的生命。

在这些情况下，甚至在开始降低风险(即灭火)之前，最关键的方面是对潜在幸存者的搜索和救援。搜救过程由专业小组执行，他们甚至冒着生命危险去拯救他人。

幸运的是，这些特区团队在大多数情况下，设备齐全都有先进的技术，现在包括无人驾驶飞行器（无人机），以改善人们寻找人们，并防止救援团队经过风险的地方，没有真正证据发现幸存者的真正证据[1］．

这些自动驾驶汽车在过去十年里经历了巨大的发展。无人机目前被用于许多不同的应用，如国防、监视或包裹交付等[2］．但无人机路径规划问题是无人机任务规划的一个重要问题[3.］．

其中许多应用都使用自动控制的飞行器，这些飞行器能够通过预先规划的轨迹飞行，甚至能够对轨迹做出实时决策。然而，大多数商用无人机仍然使用离机飞行员和固定的预先计划轨迹[4.］．

这项工作的最终动机是在SAR操作中尽可能快地找到风险的人，使用配备有车载摄像头的全自动无人机。因此，我们提出了一些优化此搜索的策略。路径规划考虑到特定情景的危害，其中将有一些风险较高的地方。为此，我们首先先制定了一种基于模糊逻辑的方法，以表征要探索的表面，并估计潜在风险的程度和人们在那个地方的可能性。

然后，我们开发了一个离散路径规划器，利用前面的分析生成的地图，尽可能快地找到人。在实际场景中实现了四种智能离散路径规划策略并进行了测试。最后，我们将展示集群中无人机的数量如何影响人员搜索的速度和有效性。

以下主题不包含在此工作的范围内：UAV车载控制和避障和无人机路径跟随和图像处理。事实上，我们不使用UAV的动态模型。路径规划作为沿着某些离散点的轨迹计算，对应于搜索区域的地图被划分的不同小区。UAV以恒定速度从一个电池移动到另一个电池（相邻的一个）。访问的小区数量给出了轨迹的长度，因此花了时间。

论文组织如下2总结了相关工作。部分3.介绍了模糊入住/风险图的生成。在部分4.，提出了智能离散路径规划的四种方法，并对实际仿真场景的结果进行了分析。本节讨论了在搜索和救援任务中使用几架无人机的结果5.．部分6.展示了一个案例研究和部分7.总结和讨论了整体结果。最后，对本文的研究成果进行了总结和展望。

2.背景

搜索和救援（SAR）业务必须由主管当局进行，以便在紧急情况下涉及人们的危险。这些紧急情况的性质可能是非常不同的;因此，危险将根据紧急情况而有所不同，因此SAR使命也适应了场景。例如，一些紧急情况是人们在无人居住的地方，火灾，飞机或船舶事故中丢失，自然灾害像山体滑坡，洪水和地震一样[5.］．

自主机器人和车辆已被用于在危险环境中执行任务，如核电站的操作、火星探索和战场上的敌军监视[6.］．实际上，无人机通常用于SAR操作。这些无人机的共同操作是由SAR团队成员远程命令[7.］．UAV由其飞行员移动到所需的区域，以便收集SAR任务的相关信息[8.］．UAV的有效载荷可能是不同的性质，通常是录制视频或拍摄照片的相机，但也可以找到其他传感器，例如气体分析仪以检测烟雾组合物。

但仍然在获得路径或轨迹方面规划SAR使命是一个具有挑战性的问题，需要仔细考虑。自主无人机航班可以基于预先预分的路径，也可以在线计算[9.］．通过无人机实现的自主程度取决于用于控制车辆的方法，并生成其路由[10］．因此，自主无人机必须具有自动路径规划计算功能，才能实现真正的自主。

离散搜索是当今一个有趣的话题，有很多应用。例如，在已建成的基础设施监控中，一种有效的路径规划算法对于利用计算机视觉对大型表面进行机器人检测至关重要[11那12或在交互式虚拟世界中控制自主代理，考虑到这些虚拟场景的规模和复杂性日益增长的需求，甚至是虚拟角色的人群动画和全身运动规划领域[13］．

离散路径规划有不同的做法。该书由卡尔曼和卡帕迪亚[13综述了在离散空间中实现智能导航的几种相关技术的发展，从经典的规划和计算几何技术开始，然后逐渐转向更高级的主题，尽管被应用于交互式虚拟世界，以解决最短路径和有限的时间预算。一些更常用于无人机的路径跟踪算法在[14，包括它们之间的比较，以帮助选择其中一个或另一个。几何方法，如样条插值是为了得到平滑的曲线通过一些路径点[15那16］．在[7.]，路径规划定义使用蒙特卡罗搜索最优路径使用在线检测参数。

几个作者还解决了航路点之间的路径的优化。其中许多使用遗传算法（GA）[17-20.］．其他建议采用估计分配算法[21] 或者搜索(22］．一般情况下，无人机需要在已知的环境中移动，获得最优路径以避开障碍物、雷达区域、建筑物、电池耗尽等。

3.生成风险/占用地图

在搜索和救援的过程中，最好利用来自不同来源的关于灾难的日益增加的可用性数据。特别是，这些信息可以作为驱动无人机在空间上空飞行路径规划的宝贵资源，以发现处于危险中的人[8.］．因此，第一步将是估计和定义搜索区域，包括所有可用数据，并定义所需的区域覆盖级别，以生成用于离散无人机路径规划的地图。

该区域表征涉及对搜索将发生的表面和一些特征的量化分析。输入是要覆盖区域的地图。该地图分为电池网格。这些单元中的每一个都将具有潜在风险和占用的分配值，该占用风险和占用将用于计算UAV将遵循的航路点。

为了进行网格划分，假设无人机位于单元的几何中心时能够跟踪整个单元。也就是说，单元的大小不会大于无人机机载摄像头覆盖的面积。但这很难估计，因为它取决于两个主要因素:无人机的高度和相机镜头的开启角度。同时，在视觉跟踪的情况下，由于相机的特点，无人机的高度将受到限制。事实上，如果海拔太高，相机就不能正确对焦，因此跟踪就无法工作。考虑到这一点，并考虑到我们正在以一种理论的方式处理一个离散的场景，我们已经建立了100 × 100 m细胞大小的限制。这个值可以根据所使用的传感器的技术规格进行缩放。

一旦确定了网格的大小，对于我们正在探索的特定区域，将对单元的数量进行简单计算。

该工作的应用场景是一个真实的案例。2016年8月，加那利群岛(西班牙)的拉帕尔马岛宣布发生森林火灾。大火持续了数天，影响面积超过4000公顷，占全岛面积的6.8%(图)1（a））.幸运的是，没有平民受害者，但不幸的是，有一人在灭火阶段死亡。火灾期间，2500多人需要从家中撤离。

在图1（a），我们可以看到火是如何在一天中生长的。模拟场景对应于火灾发生的第三天(虚线红线)。三天是搜寻一个人的合理时间。选择一个比火灾区域大的矩形区域进行跟踪和分区。网格分区有24 × 24个单元格(图1（b））.

一旦定义了要覆盖的区域并获得了网格分区，将对每个单元的潜在风险/占用值进行估计。

3.1。潜在风险/占用估计

潜在的风险/占用地图旨在为人们占据每个细胞的可能性，并且在这种情况下，对该人的生命的潜在危害。

要计算此值，需要一些来自不同来源的信息。为了获得我们需要知道的潜在入住，例如，人们访问该地区的频率。潜在风险可以通过紧急情况的类型给出。该信息可以通过专家和/或历史数据从该地区的分析中获得。我们将考虑两个主要组成部分来定义地图，称为地形和应急因素。它们由模糊推理系统（FIS）定义。

地形FIS有作为输入变量命名留住那危害， 和过境（桌子1）.输出是保姆，这是该因素对地图的贡献。

其中两个输入变量被定义为模糊(留住和危害），第三个(交通)将被认为是一个脆的重量，以应用到输出。这两个留住和危害语言变量在0和1之间归一化。模糊集由三角形和梯形隶属函数给出。标签为低、中、高留住（数字2(一个)）和低和高危害（数字2（b））.

输出由三个三角模糊集(Low, Mid, High)定义。运用专家知识得到的模糊规则如下:

规则	留住		危害	输出
1		高的	高的	高的
2		高的	低	低
3.		中等的	高的	高的
4.		中等的	低	中等的
5.		低	高的	中等的
6.		低	低	低

该模糊系统的输出最终由过境变量。即地形FIS结果乘以地形FIS结果得到最终结果保姆价值。的过境一般来说，在交通便利的地方，人们很难迷路并呆在那里(占用率低);如果发生了什么事，他们应该已经被找到并撤离了。此外，风险也会很低，因为会有帮助来解决这种情况。因此，过境值会降低保姆在这种情况下。反之亦然。

这个保姆因子是将分配给每个小区的最终值的贡献的一部分，以便访问它们（见等式（1)）.

表格3.显示这些变量可能具有的值的示例。给出的值留住根据地形可达性和地形特征估计因子。交通不便的地区或难以进入的地区比道路或平原等地区的滞留因素更小。的危害也根据地形性质进行了估算。过境价值取决于该地区是否有道路或建筑物。

举个例子来说明，如果停留的投入很高，那么地形因素对单元的风险/占用值的贡献也应该很高(会有人员在那里)，但同时这个值将与其他两个因素(运输和危险)相平衡。无论如何，如果停留时间很长，很有可能那个地方的危险很低(没有危险)，此外交通因素也很低(道路，可到达的地方)，从而降低了最终的风险。

已应用相同的推理来确定紧急情况。模糊输入变量是影响和受伤,在那里影响是由三个具有三角隶属函数的模糊集和受伤有两个梯形。第三个输入SAR团队位置，是一个值为1的二元变量，但救援队已经在现场的情况为0。这些变量的定义见表2．调用这个FIS的输出Pemergency（见等式（1)）.

例如，如果特定区域受到强烈影响，并且事故类型对人们生活危险，这一FIS的价值将很高。它将思考SAR团队是否在那里，降低风险和占用。

最后，关于重要的重要性保姆和Pemergency对路径规划最终决策的影响因素，其意义如下。第一个更重要，因为它代表了必须参观的区域，因为很可能有人在那里。此外，它们也可能是危险区域。然而,Pemergency代表应该被访问的区域，因为由于某种紧急情况，他们可能对人们潜在危险，以防人们在那里。

３．２．潜在的风险/入住率地图

我们估计这些模糊推理系统的结果，地形和紧急情况，获取拉帕尔马搜索区域地图上的每个单元格。为它们生成一个映射(图)3.）.

颜色表示该单元格对应的因子的值，从深蓝色(值0)到黄色(值1)3（a）显示地形的贡献。高滞留因子可以在地图中间观察到的，和次级道路明确地标记为蓝色。紧急贡献如图3（b）．有三个区别区域：不受影响之一，一个在中间已经严重影响由消防和淡绿色的。

然后根据(给出的关系将两个贡献组合起来1）获得捕获La Palma火灾的区域的潜在风险/占用价值（图4.），这将是离散路径规划的输入：

第三个任期（1)，即历史贡献，量化了某一事件在同一地点再次发生的可能性。正数为1，否则为0。

可以看到该地区的不同元素;例如，可以清楚地识别出一些道路，并且黄色区域对应于森林，具有较高的风险价值和火灾开始的地方。

4.离散路径规划

使用来自人工智能领域的技术，已经开发和应用了四种离散路径规划方法。最终目标是定义无人汶城市必须遵循的航点，以便尽快找到参与SAR操作的人，并尽量减少其生命的风险。

要以最快的方式找到人们，有必要探索最小化行驶距离的整个区域。此外，不仅有时间而且风险必须最小化，因此无人机首先应该转到那些风险较大或更具危险的区域。由于同时难以解决这两次问题，首先将访问具有较高潜在风险/占用/占用的地区，然后距离将被最小化，寻找两个目标之间的良好权衡。

如前所述，机载摄像机应该能够跟踪网格分区的整个单元，路径点将位于这些单元的中心。路径规划包括设置单元格应该通过的顺序。

要检查解决方案的质量，结果由两个数字量化：(我)距离是无人机​​行驶的总距离。（ii）重量是计算为的因素 单元格的相关位置顺序在哪里 它被跟踪是该单元的潜在风险/占用价值。这个权重值的意义是量化那些最重要的细胞，那些高值，比其他值更早地跟踪，因此最小化它是有趣的。

这四种方法的场景是如图所示的24 × 24单元格图4.与拉帕尔马大火受灾地区相对应。

4.1。第一个建议：景点途径

这种所谓的吸引力的方法是基于势场理论。一般情况下，当最后一点是使用已知的潜在领域。计算矢量和其方向和幅度取决于这最后一点的距离，考虑到可能会影响轨迹的障碍或禁区。

在我们的情况下，最后一点是未知的。为了定义它，为每个小区估计吸引值，使得具有最高吸引值的小区将是下一个航点。吸引值直接取决于电池的潜在风险/占用以及与当前位置的距离（3.）.在这个表达式（3.）， 代表了吸引矩阵的第一个单元和 与该单元相关的潜在风险/占用率。覆盖矩阵包含关于单元格是否已经被跟踪的历史信息。也就是说，被覆盖的是一个与和 那值为1表示未跟踪单元格，值为0表示跟踪单元格。分母是到这个的欧氏距离个小区到当前位置

该算法试图去高点值，但在当前位置附近，因此进一步的单元格与高价值没有近处的吸引力大。因此，轨迹是一致的，无人机跟踪低和高细胞减少的距离，但总是通过更高被更吸引细胞。如果没有考虑距离，只有数值将决定路径点，所以轨迹可能从一个路径点跳转到另一个路径点，它可能是颠簸的。

然而，根据这一提议，距离的吸引力大于潜在的风险/占用价值。因此，实际上，轨迹尝试首先最小化距离，然后最小化潜在的风险/占用。尽量最小化距离是有趣的，以最小化重量更为重要，因为它至关重要，首先到达发现某人更高的概率。因此， （3.）改为（4.)，以使这些因素之间的关系更为平衡:

在 （4.)，选择距离的指数函数是因为它的渐近特性。非常近的细胞将利用这个距离，但在短期内所有的细胞都将受到类似的影响，这与之前的线性关系相反，更远的细胞比更近的细胞被探索的机会更少。

为了得到更好的解决方案，我们又做了两个改进。第一个是关于轨迹的连续性。为了避免连续单元格之间的跳转，实现了一系列条件规则。据此，如果两个连续的路点位于同一垂直或水平线上，这两个点之间的所有单元格将自动成为路点。这样，这些细胞就被认为已经被跟踪了，无人机将不必再回去探索它们。

算法的第二个改进是关于路径点的选择。选择吸引力最大的单元作为路径点，但有时多个单元具有相同的最大值。最初选择的是找到的第一个最大值，因此路径取决于起始点。为了避免这种偏差，应用了一种控制策略。第一个路径点将是具有最大吸引力值的细胞，其周围的细胞具有更高的吸引力值比其他候选人的价值观;也就是说，它位于更多的地区密度。具有这种密度的矩阵， 那，按下式生成:

然后，求出矩阵吸引力的最大值（4.)，查找最大值值(5.） 完成了。与最大景点小区中密度最高的小区被选择为下一个航点。

经过所有这些修改后，在La Palma地图上运行一个模拟来显示这种方法(图5.）.

轨迹从左上角开始，覆盖整个表面。它似乎是一致的，具有良好的连续性。距离的值为680个单位，重量为37392.如预期的那样，轨迹开始穿过浅蓝色细胞到绿色的细胞，以快速覆盖地图的黄色部分（更高价值观）。当UAV靠近黄色细胞时，它直接进入它，然后覆盖所有更接近的低细胞，没有浪费时间探索低被自动考虑的细胞访问。然后它进入了其他黄色区域等。

总而言之，这一原始提案很好，这很简单，但仍然可以提高行为，因为有一些环和路径彼此交叉。其他策略将进行测试。

4.2。模糊逻辑方法

采用模糊逻辑的不同方法也已实现。甲Mamdani型模糊推理系统（FIS）设计有两个输入，（潜在的风险/占用）和（距离）和一个输出，吸引矩阵 ．这样的潜在风险/占用值的贡献，并在当前位置的距离分开，并产生它们之间的非线性关系。对于每个输入，三个三角形和梯形的模糊集合被分配（高，中和低）和两个用于输出（高和低）。九条模糊规则见表4.．

模拟进行了不同的场景来测试这个初始的模糊做法。结果是比以前的解决方案更糟糕。当分析轨迹的演化，我们发现，无人机更喜欢去到相邻小区以较低值，而不是进一步的细胞与高值。实际上，黄色细胞首先被无人机包围，但直到稍后未跟踪。

虽然FIS通常由了解系统行为的专家设计和调整，但在这种情况下，知识相当差。因此，由于目标是最小化距离和风险，可以使用优化方法来调整隶属函数。也就是说，实施了一种进化的FIS，其由上面提出的相同的FIS组成，但用遗传算法调整。

遗传算法的配置必须包含FIS梯形隶属函数的32个参数。每个梯形隶属度函数由4个点定义: 那 那 那和 ．这些参数的值必须是相关的;也就是说,必须小于 那 比 那等等。这些限制由线性约束定义 ， 存在 在我们的例子中。

适应性标准是重量和距离的函数，均为范围标准化并被最小化如下：

其余的GA参数如表所示5.．

最初，这个过程在计算上非常缓慢，这使得这个问题无法解决。为了减少计算时间，我们考虑一个更小的映射，一旦成员函数被调整，它将被缩放为更大的一个，以查看它是否适合。因此，遗传算法执行相同的配置，但为5 × 5矩阵。

作为一个例子，图6.示出了GA调整后的输入可变距离（a）和输出表面（B）的隶属函数。在表面上它可以看到短距离和高的高输出值也长距离的值。

现在使用25×25进行测试拉帕尔玛的地图（图7.），使用5×5映射图计算的隶属函数。

结果是 和 ．虽然距离比引力解中长得多，重量却更低。因此，我们可以说，这个解决方案也达到了目标，但更倾向于最小化风险/占用率与距离的关系。然而，表示两个连续路径点之间的过渡的小角度是不现实的，使无人机无法承受的轨迹。

这种方法的强度是高度的快速收敛价值细胞，稍后访问较低的细胞。这意味着，即使在较长的时间内覆盖所有的细胞，由于重量更低，也量化了占用率，在短时间内找到人的可能性更高。

4．3．简称ANFIS方法

另一种解决方案是使用基于自适应网络的模糊推理系统(ANFIS)实现的[23］．FIS与前一个相同，但现在通过ANFIS算法修改成员函数。

此外，包括一个新的输入变量，密度矩阵（5.）.现在系统能够给高密度区域更高的吸引力值，而不是只使用这个因素来选择最大值。

因此，输入为 那 那和 ．前两个是标准化的是 ．为每个变量计算三个高斯隶属函数。输出也是吸引矩阵 ．但是ANFIS需要样本进行训练。因此，我们手工生成了80个合成数据集。训练在50个时期进行(图)8(一个)）.为新变量生成的成员关系函数的示例如图所示8 (b)．

新生成的控制面如图所示9.．可以观察到与图中所示的差异6 (b)．在这种情况下，它们虽然显然是非线性的。

一旦生成了ANFI，仿真就在LA Palma的实际情况上运行。轨迹如图所示10．得到的结果如下: 和 ．

在这种情况下，与模糊逻辑解决方案相比（ 和 )，重量更高，但距离更短，所以很难说哪个更好。然而，这种方法真正有趣的是无人机如何超越最高细胞首先，完成低位搜索细胞。

4.4。粒子群优化算法的应用

虽然以前的解决方案似乎满足了主要目标，但它们还可以改进。在这种情况下，提出了一种基于粒子群优化(PSO)的进化方法。

遗传算法用于获取应该访问的细胞的顺序。GA在小地图上运行得很好，但当缩放到25 × 25地图时，就会出现一些问题。此外，在之前的所有解决方案中，路径点的计算都是非常静态的，所有的单元都是从其中心点开始跟踪的。尽管在开始时对这种跟踪每个细胞的方法做了假设，但在这个粒子群算法解决方案中，我们试图找到一个连续的策略。

方法是完全不同的。我们从一样开始Map (24 × 24 cells)，但每个cell都除以10以获得更好的离散化。每一个新的更小的细胞都有相同的值比包含它的更大的单元格。一旦地图被划分，搜索了PSO算法的航点。

粒子群优化适应度函数的变量为路径点的坐标。计算是由10个路径点组成的组，所以将有20个变量:“坐标和10”“坐标。然后，计算距离、权重和跟踪的单元格数。很明显，距离必须被最小化，而被跟踪的单元需要被最大化，这意味着无人机正在通过新单元的最大数量，因为被跟踪的单元不会被多次考虑。

为了获得被跟踪的单元，我们将在两个连续的路径点之间绘制一条直线，并将沿着该轨迹的10 × 10的正方形内的所有单元视为被跟踪。这意味着无人机将继续使用与之前解决方案相同的区域拍摄图像。这是第一个相关的修改。

另一个重要的修改是在这种情况下，重量将最大化。在以前的方法中，重量最小化是有趣的，因为它意味着无人机首先前往高位细胞。然而，使用这种方法，它反而更有趣，因为，如前所述，计算是以10个路径点为串进行的。所以，如果把前十个点的权重最大化，那么后十个点的权重就会降低。也就是说，无人机正在飞越高空细胞第一。

这些因素之间的关系如下所示:

PSO算法的其余配置如表所示6.．

一旦设置完成，就应用粒子群算法。轨迹如图所示11．

的值和现在不计算，因为它们不相关，因为方法的性质完全不同于以前的解决方案。但它值得一看(图11)轨迹如何有许多直线覆盖所有可能的空间，特别是在高之间地区。还有更多的迭代可能以覆盖地图的100％执行了。然而，我们也可以通知称，无人机前进和倒退到同一个点，这意味着这是不是这样的最佳解决方案。

5.多个无人机方法

在搜救行动中，通常使用多架无人机。群体系统利用简单的局部行为集体解决复杂问题，其中群体的能力大于其各部分的总和[24那25］．在这项工作中，研究了两种不同的无人机群体形成离散路径规划：自由和分布。无人机是相同的，但从地图的不同位置开始，其中它们跟踪所有所需的区域。

利用吸引法、模糊逻辑法和ANFIS方法得到了多架无人机的离散路径规划。该策略与之前针对一架无人机提出的策略相同，但现在对于每一次迭代，计算的路径点数量与可用车辆数量相同。为简单起见，只考虑1、2或3架无人机，但该解决方案可以扩展到所需的任意数量。

在La Palma的网格图中，2-UAV配置的起点是（13,1）和（18,1），适用于3个无人机。

5.1。自由编队

自由群算法由两架或多架无人机同时并行运行的路径规划算法组成;也就是说，每架无人机沿着覆盖区域走一条独立的路径。当计算新的航路点时，其他无人机跟踪的单元的信息应该是可用的，所以其他无人机不需要访问任何已经跟踪的单元。

作为一个例子，图12给出了2架和3架无人机(分别为a和b)在采用吸引法获得离散路径规划时的轨迹。

用吸引路径规划方法得到的结果如下 那 1无人机;= 713，2架无人机= 19638;和= 720,3架无人机自由编队= 12812。在所有情况下，距离是相当相似的，但重量是非常低的多无人机。

这种权重的影响是由于并行搜索。正如对单个无人机所解释的那样，权重是计算每个单元被跟踪的顺序的值，并为所有单元格获得总和。在这种情况下，有两个单元，其中有1，两个具有订单2等，直到无人机达到一半的单元格。

搜索时间应该会减少，因为尽管距离是相似的，但它是由几架无人机共享的，所以现在的最大飞行距离大约是只有一架无人机飞行距离的一半甚至三分之一。

关于路径，看看两个无人机（图12(一个))会聚到地图开始处中间的绿色区域。然后他们分开，在不同的高处寻找价值领域。最后，它们再次收敛价值领域。有3架无人机时，收敛性不像这种情况那么明显，这意味着对每个区域的跟踪更加分布式。

在所有情况下，不同无人机的轨迹相互交叉。这并不意味着碰撞，因为无人机不在同一时间同一地点。然而，路径规划必须使用避碰算法来完成，这超出了本工作的范围。

如前所述，由于解的性质，粒子群算法无法实现自由生成。对于ANFIS方法，结果是相似的，最坏的情况是模糊的。

5.2。分布式群体的形成

分布式无人机群的形成意味着地图被分成若干部分，每个部分与车辆一样多，每架无人机被分配一个它必须跟踪的区域。

2、3架无人机在具有吸引力路径规划的分布式集群编队中的路径规划如图所示13．可以看出每个UAV如何跟踪独立区域，并且他们的路径不会交叉。距离现在2个无人机和673个= 678为3架无人机，以及权重= 20411分别为= 13712。距离类似，但略长于仅使用一架无人机(680)，略好于使用自由编队无人机(713和720)获得的飞行距离。在重量上，它比一架无人机(37392)的情况要小得多，3架无人机比2架无人机的情况要好得多。

对于不同方法（模糊逻辑和ANFIS），已经采用了不同数量的无人机进行了相同的实验。

5.3。不同无人机数量下的方法比较

最后，表格7.总结了两种配置的不同方法的结果。正如预期的那样，当UAV的数量增加时，结果会改善。这主要是由于计算重量的方式，并证明了拟议策略的有效性。

总的来说，可以看出不同的方法有其优缺点。吸引法是有最短路径的方法，其次是ANFIS方法。但是它的权重比其他方法略高。实际上，模糊逻辑的权值最小，虽然差别不大，但与其他两种方法的距离要远得多。从这个意义上说，ANFIS方法具有最平衡的结果，具有中等权重和低距离值。

总而言之，很难说哪个更好。这取决于目标的优先级。最快的方法是吸引策略，但模糊方法是寻找人的最好方法，至少访问最有可能找到人的区域。在下一节中，我们将根据实际情况检查这些结果。

6.案例就读

为了分析和证明本文提出的离散路径规划建议的有效性和实用性，他们将要在特区实际情况进行比较。

在拉帕尔马的潜在风险/占用地图上已经随机找到了30个失踪的人。均匀分布的随机生成器给出一个与地图的每个单元相关联的值。然后，这个值乘以该单元的潜在风险/占用值的一半。由此产生的25个值最高的位置被选中。这样我们就得到了一个随机分布，但向高的区域加权值。其余5例病例人工分布在低密度地区值（图14）.这些最后一个是要找到的前五个案例，以便它们可以很容易地位于显示搜索时间结果的图表中。

用于测试策略的主要标准是无人机需要分别找到30个人的时间。它应该与距离成正比。所有无人机都被认为具有相同的技术特性，并且以相同的速度飞行(设为3)。为了使仿真更加真实，我们还考虑了另一个假设。无人机在跟踪小区时，其速度比在不同区域之间移动时(跟踪速度= 1)要低。

评估每种情况（查找某人）估计UAV从具有特定配置（策略和形成）从初始位置到达那里的时间。

在评估案例时，计算每种方法及其培训所需的时间。对于每一种情况，都有一种特定阵型的方法是最快的，它是赢家;还有另一个是最慢的，也就是一个松散的。如果加上所有可能的配置和策略结果，总共应该有30场胜利和30场失败，但还有更多，因为空间和速度是离散的，在某些情况下，会出现平局。

这样，我们可以比较不同的方法，看看哪一个是最好的探索低区或高细胞等。

6．1.用吸引策略找对象

吸引力路径规划的时间结果如表所示8.．获胜的次数代表一个特定配置在其他配置中是最佳的次数。损失的数量代表了什么时候是最严重的一次。

数据15和16给出了不同数量的无人机对该策略的比较。纵轴表示时间单位，横轴表示情况。

正如预期的那样，当UAV的数量增加时，时间会减少。此外，前五个点需要更多的时间，因为它们有很低价值观，所以UAV进入较高后那些。

图中显示了相同无人机数量的两种群配置的比较17(免费的, ;分布式的,）.我们可以观察到两个无人机的差异并不重要。尽管如此，甚至具有三个无人机，甚至具有类似的趋势，某些情况都存在巨大差异，这表明搜索是以非常不同的哲学完成的。

6.2。模糊逻辑路径规划

采用模糊逻辑路径规划得到的结果如表所示9.．

在这种情况下，有更多的成功配置。最糟糕的情况几乎只与一架无人机的使用有关。这意味着该方法对于一架无人机是无效的，但随着无人机数量的增加，尤其是分布式编队时，其效率得到了极大的提高。

6.3。ANFIS路径规划结果

为ANFIS路径规划获得的结果如表所示10．

尽管这种方法似乎是在找人方面最好的一个，它具有相同的问题，因为模糊逻辑方法。即，较好的结果与自由群形成比与分布式之一获得;最坏的情况下再次与仅无人机。无论如何，这种策略给出了这种情况下最好的平均值。

6.4。粒子群算法在SAR任务中的路径规划结果

PSO路径规划获得全部最严重的结果。这种方法不起作用，因为UAV在航点之间长距离行驶，以便以距离/速度关系覆盖表面。由于连续跟踪，与其他方法相比，UAV非常慢。获得的所有结果比其他解决方案更糟糕，具有许多损失，这意味着无人机没有找到那个人（图18）.

鉴于这些结果，PSO不会考虑不同方法之间的全局比较。

7.全球成果讨论

对不同的方法和结构进行了比较，并对整体结果进行了讨论。为了有一个好的概述，每一种策略都被应用到相同的30个案例中，当使用多架无人机进行搜索时，有两种可能的编队。

首先,图19展示了一架无人机的三种不同的搜索策略。时间结果非常相似，但一般来说，ANFIS路径规划略好。这三种方法都适用于低细胞，但吸引力比其他人发现那些更糟糕的情况更短。

在图中20.和21分别给出了2架和3架无人机自由群编队时的路径规划结果。结果也非常相似。模糊逻辑路径规划似乎比其他方法更糟糕。

分布式群集配置，图22和23显示2和3个无人机的结果。对于所有方法，2个无人机的结果再次相似，具有ANFIS方法略微更好的性能。

但是，在图中23，可以看出模糊逻辑方法与其他方法有很大的不同。该方法在分布式群体中效果较好，这可能是因为它是为较小的地图设计的，所以当搜索区域较小时，该方法的性能就会提高。

最后,图24显示每个方法的每个配置的平均时间。根据这些结果，搜索最快的配置是在分布式群体形成中具有3个无人机 那正如预期的那样，模糊逻辑方法为这种特定配置提供了最佳结果，具有ANFIS和吸引力类似搜索时间。

尽管如此，关于损失和胜利的数量（图25)，这是一个关键因素，ANFIS方法一般是最好的方法。模糊逻辑也有一个非常好的性能，特别是分布式配置，正如它说。但是，即使赢的次数少，吸引法也是最一致的，因为它的损失次数少，说明它的结果是相当均衡的。

作为摘要，我们可以说吸引方法获得了效率的中位置。它表现了定期和广泛的搜索，这意味着它不会花费大量的时间发现低位但它没有像其他方法走得快到高值区。这种方法对齐次方程很有效地图。

模糊逻辑呈现出相当快的收敛，但它是非常不规则的。但是，它在大高的地图中运行良好因为它的搜索类型，它在所有危险区域中执行随机搜索。

ANFIS方法已被证明是一般术语中最好的方法。它有快速收敛到高处值，并对其余单元格执行相当常规的搜索。它在低电平时工作得更糟远离高地的地区其他方法获得了更好的结果。

8.结论和未来工作

在这项工作中，提出了两个主要贡献。第一个是根据风险/占用因素生成搜索区域的模糊地图，以搜索和救援(SAR)任务为目标。二是应用不同的智能策略进行离散路径规划，覆盖网格搜索区域。

对于地图的刻画，得出的结论是，它有助于将路径规划的重点放在有希望的区域上。路径规划者找到最小化人们所面临风险的轨迹。事实上，在模拟结果中，可以观察到对高风险/被占领区域的快速跟踪，从而更快地发现卷入危险情况的人。

四项智能策略已应用于离散路径规划，即吸引力，原始的策略和模糊，ANFIS和PSO。除此之外，剩下的时间就搜索时间和距离而获得了良好的结果。另一个结论是，该方法的性能强烈取决于相关的概率图。这阐述了这一地图的重要性，同时考虑到可能影响搜索的可能变量和因素。

在Swarm形成中使用多个UVS进行搜索，已经观察到对路径规划方法类型的依赖。一般来说，分布式形成更好，但应与之相关联地图及路径规划方法。

未来与本工作几个方面相关的工作如下:(我)研究地图描述的其他因素及其对潜在风险/占用价值的影响，这已被证明对SAR任务很重要（ii）使用更现实的无人机模型，包括动态[26[还避免和视觉跟踪算法[27](3)在真实系统上测试最成功的建议。

的利益冲突

作者声明本文的发表不存在利益冲突。

致谢

这项工作是欧洲联盟EP-Interreg V-A Spain-葡萄牙（POCTEP）的支持，项目0115_Tecnolivo_6_E，为涵盖在开放访问中发布纸张的成本提供资金。

参考文献

1. L. Novaro Mascarello和F. Quagliotti，“民用小型无人机系统(sUASs):操作和安全挑战”，飞机工程与航空航天技术，卷。89，没有。5，pp。703-708,2017。查看在：出版商的网站|谷歌学术搜索
2. G. Pajares, J. J. Ruz, P. Lanillos, M. Guijarro, J. M. De La Cruz，和M. Santos，“无人机的轨迹生成和决策”，Riai - Revista Iberoamericana de Automatica E Informatica Industrial，第5卷，第5期。1，页83-92,2008。查看在：谷歌学术搜索
3. P. García-Auñón, M. Santos-Peñas, J. M. de la Cruz García，“基于模糊逻辑的参数选择改进无人机路径跟踪算法”，应用逻辑杂志，第24卷，第2期B部分，第62-75页，2017。查看在：出版商的网站|谷歌学术搜索|MathSciNet
4. M. Silvagni，A. Tonoli，E. Zenerino和M. Chiaberge，“山地雪崩事件中的搜索和救援行动的多用途无人机”，“地质学，自然灾害和风险，第8卷，第2期1，pp。18-33,2017。查看在：出版商的网站|谷歌学术搜索
5. R. Dubé， A. Gawel, C. Cadena, R. Siegwart, L. Freda, M. Gianni，“用于搜索和救援行动的3D定位、绘图和路径规划”，收录于第14届安全，安全和救援机器人专题讨论会的诉讼程序，2016年SSRR，第72-273号，瑞士，2016年10月。查看在：出版商的网站|谷歌学术搜索
6. M. Jun和R. D 'Andrea，“不确定和对抗环境下的无人机路径规划”，出版协同控制:模型、应用和算法，卷。1合作系统， pp. 95-110，施普林格美国，波士顿，马萨诸塞州，2003。查看在：出版商的网站|谷歌学术搜索
7. F. Kamrani和R. Ayani，搜索操作中的无人机路径规划，高空作业车，英达，2009年。
8. C. Baker，G.Ramchurn，L. Teacy和N. Jennings，“计划搜索和救援UAV团队的任务”2016年的诉讼程序：ECAI，2016年智能系统的着名申请会议，p。6，2016。查看在：谷歌学术搜索
9. K. P. Valavanis和G. J. Vachtsevanos，《无人机任务和路径规划:简介》，无人机手册， pp. 1443-1446, 2015。查看在：出版商的网站|谷歌学术搜索
10. E. Besada-Portas, L. de La Torre, J. M. de La Cruz，和B. de Andrés-Toro，“现实场景中多无人机的进化轨迹规划器”，IEEE机器人学报第26卷第2期4，页619-634,2010。查看在：出版商的网站|谷歌学术搜索
11. “基于视觉的无人机表面检测的增强离散粒子群优化路径规划”，中国航空航天大学学报(自然科学版)，自动化建设，卷。81，pp。25-33,2017。查看在：出版商的网站|谷歌学术搜索
12. G. E. Anaya Fuentes, E. S. Hernández Gress, J. C. Seck Tuoh Mora, J. Medina Marín，“基于旅行商问题的作业车间调度问题求解”，Riai - Revista Iberoamericana de Automatica E Informatica Industrial，第13卷，第2期4, pp. 430-437, 2016。查看在：出版商的网站|谷歌学术搜索
13. M. Kallmann和M. Kapadia，“交互式虚拟世界的几何和离散路径规划”，视觉计算综合讲座，第8卷，第2期1, pp. 1 - 201, 2016。查看在：出版商的网站|谷歌学术搜索
14. P. B. Sujit，S. Saripalli和J. B. Sousa，“算法之后的无人机路径评估”2013年第12届欧洲控制会议，ECC 2013论文集，第3332-3337页，che, 2013年7月。查看在：谷歌学术搜索
15. A. Barrientos, P. Gutiérrez和J. Colorado，先进无人机轨迹生成:规划和制导，高空作业车，英达，2009年。
16. E. G.埃尔南德斯-Martinez的，E. D.费雷拉-Vazquez的，G.费尔南德斯-安纳亚，和J. J.弗洛雷斯-Godoy的“采用距离和面积约束异构移动剂的形成跟踪，”复杂性，卷。2017年，第9404193，2017年。查看在：出版商的网站|谷歌学术搜索
17. E.BEADA-PORTAS，L. de la Torre，A. Moreno和J.L.L. Risco-Martín，“关于多目标进化无人机路径规划者的性能比较”信息科学， vol. 238, pp. 111-125, 2013。查看在：出版商的网站|谷歌学术搜索
18. P.加西亚奥尼翁和M.桑托斯，“对于英寸决策和软计算无人机系统的路径规划遗传算法的使用，”世界科学，卷。9，PP。430-435,2014。查看在：谷歌学术搜索
19. M. Davoodi, F. Panahi, A. Mohades, S. N. Hashemi，“离散空间中的多目标路径规划”，应用软计算，第13卷，第2期1, pp. 709 - 720,2013。查看在：出版商的网站|谷歌学术搜索
20. F. Alonso Zotes和M. SantosPeñas，航空航天任务中的行星轨迹启发式优化，“Riai - Revista Iberoamericana de Automatica E Informatica Industrial，卷。14，不。1，第1-15，2017。查看在：出版商的网站|谷歌学术搜索
21. 杨平，唐凯，和J. a . Lozano，“基于新坐标系统的无人机路径规划的分布算法估计”，出版2014年IEEE进化计算大会论文集，CEC 2014，页1469-1476，中国，2014年7月。查看在：出版商的网站|谷歌学术搜索
22. -J。鲁斯，O.阿雷瓦洛，G.帕哈雷斯，和M. J.德克鲁兹静态和动态环境下无人机轨迹规划，高空作业车，英达，2009年。
23. J. S. R. Jang，“ANFIS：基于自适应网络的模糊推理系统”，IEEE系统、人与控制论汇刊，第23卷，第2期。3，第665-685页，1993。查看在：出版商的网站|谷歌学术搜索
24. T. Tomic，K. Schmid，P. Lutz等，“朝着一个完全自主的无人机：室内和户外城市寻找和救援的研究平台，”IEEE机器人与自动化杂志第19卷第2期3，第46-56页，2012。查看在：出版商的网站|谷歌学术搜索
25. J. B. Seco, J. Dormido Canto, M. Montalvo Martinez, J. López-Orozco, E. Besada Portas, J. De la Cruz Garcia， " Centro De Control De Tierra para Colaboración De Vehículos Autónomos Marinos， "杂志伊比利亚德。自动化ËINFORMATICA工业，第15卷，第5期。1，页1,2017。查看在：出版商的网站|谷歌学术搜索
26. J. E. Sierra和M.桑托斯，“使用分析和神经技术建模系统：杂交，”Neurocomputing, 2017年。查看在：出版商的网站|谷歌学术搜索
27. “基于水平消减控制策略的无人机末制导律研究”，国家自然科学基金项目，项目负责人。复杂性，卷。2017年，第1-19,2017。查看在：出版商的网站|谷歌学术搜索

版权

版权所有©2018VíctorSanJuan等。这是分布下的开放式访问文章知识共享署名许可协议如果正确引用了原始工作，则允许在任何媒体中的不受限制使用，分发和再现。