无人机群在线路径生成与导航

摘要

随着无人机在消费者应用领域的日益普及，涉及无人机的事故数量也在迅速增加。因此，无人机的运动安全性已成为无人机操作人员最关心的问题。对于一群无人机来说，如果不防止无人机相互碰撞，在飞行区域内静态和动态出现移动障碍物，则无法保证无人机的安全运行。本文提出了一种适用于无人机群的在线无碰撞路径生成与导航系统。该系统利用无人机和成功检测到的静态和移动障碍物的地理位置来预测和避免以下情况:(1)无人机与无人机的碰撞，(2)无人机与静态障碍物的碰撞，(3)无人机与移动障碍物的碰撞。我们的碰撞预测方法利用高效的运行时监控和复杂事件处理(CEP)来进行及时的预测。该系统的一个显著特点是能够预测潜在的碰撞，并主动寻找最佳方法来避免预测碰撞，以确保整个群的安全。我们还提出了基于仿真的系统实现，以及涉及一系列实验的实验评估，并将我们的结果与四种现有方法的结果进行比较。结果表明，该系统能够在线预测并避免这三种碰撞。生成安全高效的无人机航路，有效地扩展到大规模问题实例，适用于飞行区域混乱和无人机碰撞风险高的场景。

1.介绍

无人驾驶飞行器(UAV)或无人机是一种半自主飞行器，可以通过使用计算机和无线电链路远程控制和操作[1］．无人机可以根据其设计，尺寸和飞行机制分为不同类型。在现有类型中，等数或二峰值特别受欢迎，因为它们的设计简单，体积小，成本低，机动性，以及悬停在适当位置的能力。四足电阻使用两对相同，垂直定向的螺旋桨，其中一对顺时针旋转，另一对旋转逆时针。商业上可获得的四轮压力机越来越多地用于各种应用，例如监测和监测，搜索和救援行动，地理映射，摄影和拍摄，野生动物研究和管理，媒体覆盖公共活动，遥感农业应用和空中包装交货 [2- - - - - -5］．针对这些应用，高效和可扩展的解决方案需要多架无人机的在线路径生成和导航系统。

无人机越来越受欢迎。在美国，联邦航空管理局(FAA)预计，业余爱好者的小型无人机数量将从2017年的估计110万架增加到2022年的240万架(https://www.faa.gov/news/updates/?newsId=89870)．随着无人机在消费者应用中的日益普及和使用，涉及无人机的事故数量也在急剧增加。联邦航空局每月收到100多份未经授权和潜在危险的无人机活动报告，由飞行员、公民和执法部门报告(https://www.faa.gov/uas/resources/public_records/uas_sightings_report/)．在最近的一次事件中(https://www.bbc.com/news/uk-england-sussex-46623754当时，伦敦盖特威克机场(London Gatwick Airport)的跑道关闭了一天多，因为发现两架无人机在机场上空反复飞行。此次航班中断影响了760个航班上的约11万名乘客，所有航班都无法起飞或降落。这类事件一方面显示了无人机操作员教育和培训计划的重要性，并对违法者实施更严格的立法，但另一方面，它们也激发了对无人机无碰撞路径生成和导航系统的需求。确保无危险、安全的无人机飞行对室内应用也同样重要。因此，无人机的运动安全性已成为无人机操作人员最关心的问题。它是指无人机在环境中检测和避免与静态和移动障碍物碰撞的能力。静态障碍包括建筑、树木和其他类似的固定物品，而移动物品(例如，鸟)则被认为是移动障碍。

一些商用的四旋翼飞行器能够探测和避开一些障碍物。例如，大疆的Phantom 4 Pro (https://www.dji.com/phantom-4-pro)采用五向传感器提供五个方向的障碍物检测或传感，前后感应范围可达30米，左右感应范围可达7米。然而，它的避障机制并非适用于所有场景。在这项工作中，我们假设每一架无人机都配备了足够的障碍检测能力，并能够成功地检测其周围所有静态和动态出现的移动障碍。因此，本工作的重点不在障碍物检测上。相反，我们专注于碰撞预测和避免。

以合作方式工作的多架无人机可用于提供单架无人机无法提供的强大能力[3.］．因此，对于规模更大、高度复杂的应用和任务，如果一架无人机的能力超过了一架无人机的能力，或者如果只使用一架无人机，就无法有效地执行，那么多架无人机可以以集群或机队的形式一起使用。在这种情况下，如果不防止无人机相互碰撞，在飞行区域内静态和动态出现移动障碍，则无法保证安全操作。因此，在无人机群体环境下，为确保运动安全，需要设计并实现多架无人机的在线运动路径规划、协调和导航系统，并集成支持碰撞预测和避免。

无人机运动安全问题目前吸引了显着的研究。关于无人机运动规划算法的一些全面的文献综述，可以在[6，7］．这些方法的主要焦点是在执行任务开始前计划和生产UAV路径或轨迹的离线运动规划阶段。奥格里亚罗等[8提出了一种提前生成可行路径的计划方法。Lavalle [9Karaman和Frazzoli [10]提出了基于采样的路径规划算法。Silva Arantes等人[11]提出了一种针对需要无人机紧急着陆的关键情况下的路径规划方法。Dong等人[3.]介绍了一个用于多个无人机的合作控制的软件平台。Bürkle等人。［12]提出了一种多智能体系统体系结构，用于无人机群中的团队协作。Ivanovas等人[4]提出了一种无人机障碍物检测方法。de souza [13和de Souza和Endler [14]提出了一种利用智能手机和移动通信网络进行无人机集群运动协调的方法。他们的工作专注于群的内部通信，并没有提供无碰撞路径生成的解决方案。

本文提出了一种适用于无人机群的在线无碰撞路径生成与导航系统。该系统利用无人机和成功检测到的静态和动态出现的移动障碍物的地理位置来预测和避免以下情况:(1)无人机与无人机的碰撞，(2)无人机与静态障碍物的碰撞，(3)无人机与移动障碍物的碰撞。它包括三个主要部分:(1)复杂事件处理(CEP)和碰撞预测模块，(2)互斥锁定机制，(3)避免碰撞机制。CEP和碰撞预测模块利用有效的运行时监控和CEP进行及时预测。互斥锁定机制可以防止多架无人机同时飞向同一位置。该避碰机制是在成功检测到飞行区域内的静态和移动障碍物的情况下，寻找防止无人机相互碰撞的最佳方法。该系统的一个显著特点是能够预测潜在的碰撞，并主动寻找最佳方法来避免预测的碰撞，以确保整个群的安全。与现有工程相比[3.，4，6- - - - - -16.]，我们提出的系统不依赖于规划阶段，而是以在线方式生成高效、无碰撞的路径。重点研究了无人机群的碰撞预测与避碰和在线路径生成与导航。

我们还提出了基于模拟的实施系统的实施以及涉及一系列实验的实验评估，并将结果与​​四种现有方法的结果进行比较[9- - - - - -11，17.］．结果表明，该系统能够在线预测并避免这三种碰撞。生成安全高效的无人机航路，有效地扩展到大规模问题实例，适用于飞行区域混乱和无人机碰撞风险高的场景。我们提出的导航系统，它的实现，实验和结果不基于或限于无人机群的特定应用。相反，它们足够通用，可以适用于广泛的应用程序。本文中提出的工作扩展了我们的初步方法和在[2］．

我们按照以下步骤进行2设置术语和上下文。为UAV群的建议在线，无碰撞路径生成和导航系统介绍3.．节4，我们将通过一个小示例说明我们所建议的方法的主要步骤。部分5介绍了一些重要的实现细节和实验评价。部分6回顾重要的相关工作。最后，我们在本节给出了我们的结论7．

2.预备

该系统不仅为在线碰撞预测和规避提供了支持，还为群内所有无人机生成了完整的碰撞路径。传统的运动路径规划方法要求在任务开始前必须知道所有障碍物及其精确位置，与此不同的是，本文提出的方法不假设任何关于障碍物的先验知识。换句话说，我们假设飞行区域的地形事先不知道。因此，该系统对静态和动态出现的移动障碍物的数量和位置不作任何假设。它不需要一个初步的离线运动规划阶段来为无人机产生有效的路线。在我们的方法中，无人机从它们的起始位置起飞，不间断地飞向它们的目的地，直到提出的系统预测碰撞并触发我们的避碰机制来防止预测的碰撞。由于该系统利用无人机的地理位置来生成它们的路径，并预测和避免冲突，因此需要机群中所有无人机的准确位置信息。不精确和不正确的信息可能导致更长的路径，在最坏的情况下，一些无人机可能与其他无人机相撞，或与一些静态或移动障碍。

让任务飞行区用有限的地点集来表示 ，每个位置的地方是三维空间中的一个点吗 ．在户外任务中，尺寸可以分别对应纬度、经度和海拔或高度。为了保证蜂群的形成，我们假定蜂群中任意两个连续位置的距离是否小于或等于传感范围，且大于或等于安全距离对于无人机。例如，前后传感范围幻影4 Pro无人机的高度可达30米。因此，如果群中包含Phantom 4 Pro无人机，则为任意两个连续位置之间的最大距离 应小于或等于30米。的安全距离对于无人机来说，这取决于它们的最大速度 ，障碍物检测和处理时间 ，无线通信延迟［13］．例如，如果在最大速度下找到两个无人机朝向彼此开始每秒钟5米，并且有一个障碍物检测和处理时间0.5秒和一个无线通信延迟0.2秒，安全距离可以估计为 结果是9米。因此，在本例中为任意两个连续位置之间的最小距离 应该大于或等于9米。作为问题的简化，我们假设所有连续的位置是均匀的，固定的距离相隔彼此表示为这样 ．因此，飞行区可以看作是一个三维网格。这种简化允许更快地生成、比较和评估解决方案或无人机路径。为清晰起见，本文中使用的重要术语和符号汇总于表中1．

此外,让 在群体中是一套无人机或无人机。静态障碍物表示为 ．类似地，动态出现的移动障碍用集合表示 ．每个无人机都占据某个位置 ．无人机从出发地起飞，飞向目的地。无人机路线或路径是从无人机的起始位置到无人机的目的地位置的位置序列。对于一个无人驾驶飞机 ， 这样在哪里是初始位置还是起始位置最终或目的地点是 ．同样，每个静态和移动障碍物都占据某个位置 ．此外，移动的障碍物继续任意移动，直到它们离开飞行区。

我们为一群无人机制定三项基本安全要求（SRS）：SR1: ， 不与SR2： ， 和不互相碰撞SR3: ， 不与

由于所提出的系统不对静态和移动障碍的数量和位置假设任何先验知识，并且不依赖于初步，离线运动计划阶段，因此无法在任务开始之前验证SRS。为了SR1涉及静态障碍，无人机不得飞到静态障碍所在的位置。我们所提出的系统通过提供有效的碰撞预测和碰撞避免机制，帮助无人机避免以在线方式以在线方式成功检测到的静态障碍物。同样，对于SR2这涉及到与其他无人机的碰撞，在任何给定的时间都是必须的吗T.，每个位置都是最多的一个无人机占据。建议的系统阻止无人机飞入附近的其他无人机。提出的互斥锁定和碰撞避免机制防止无人机飞行到时代其他无人机占用的任何位置T.．为了SR3关于碰撞与动态出现，移动的障碍，提出的系统提供了一个类似的方法SR1这有助于无人机避免以在线方式成功地检测到移动障碍。

3.无碰撞路径生成和导航

数字1提出了一种用于无人机群的在线无碰撞路径生成和导航系统的高级体系结构和概述。该系统的主要组成部分包括:(1)CEP和碰撞预测模块，(2)互斥锁定机制，(3)避碰机制。系统的输入是无人机位置更新、静态障碍物检测和移动障碍物检测。基于这三种输入，CEP和碰撞预测模块预测:(1)无人机与无人机的碰撞，(2)无人机与静态障碍物的碰撞，(3)无人机与移动障碍物的碰撞。我们的避碰机制试图找到避免或绕过冲突的最佳方法，并在线计算无人机的无碰撞路径。在一个人口密集、飞行混乱的地区，可能不可能立即计算出所有无人机的旁路路线。在这种情况下，该系统可能会让一些无人机进入原地悬停模式，直到情况有所改善，路线明确。此外，它还可以让一些无人机暂时撤退或后退，以找到更合适的、无碰撞的路线。

该系统采用安全第一的方法。因此，无人机群的无危险、安全操作优先于其他目标，包括无人机路线的长度、无人机及时到达目的地，以及任何其他特定任务目标的实现。因此，我们没有将这个问题表述为一个优化问题。相反，我们采用一种随机的、贪婪的方法来寻找安全有效的路线。无人机从它们的起始位置起飞，不间断地飞向目的地，直到CEP和碰撞预测模块预测发生碰撞，在这种情况下调用避碰机制来避免碰撞。此外，我们的互斥锁定机制阻止多架无人机试图在同一时间飞到同一位置。在每一步，该方法都对每架无人机进行随机贪婪决策。它试图为每架无人机找到下一个位置，这不仅是安全的，而且还减少了距离目的地的距离。拟议系统的主要组成部分将在以下小节中描述。

３.１.复杂事件处理和碰撞预测

复杂事件处理(CEP)是一种对一个或多个事件流中的大量事件进行实时、快速处理的技术，以派生和识别事件流中的重要复杂事件和模式。CEP已成功应用于多个业务领域，包括零售管理、医疗保健和云计算[18.，19.］．例如，在零售管理中，CEP可用于检测入店盗窃和缺货事件。CEP中的基本或基本事件通过事件处理查询被处理成复杂或复合事件，这些查询是用类似结构化查询语言(SQL)的语言编写的。因此，CEP为实时事件流提供了与关系数据库管理系统为持久数据提供的类似功能。

最广泛使用的CEP工具之一是ESPER CEP引擎（http://www.espertech.com/esper/)，其中事件处理查询是用事件处理语言(EPL)编写的。使用Esper CEP引擎有三个主要步骤:（1）在第一步中，向CEP引擎注册事件类型和事件源。Esper中的事件类被编写为普通的旧Java对象。（2）第二步要求用EPL编写事件处理查询。（3）最后，在第三步中，实现了可用于执行适当控制和修复操作的事件sink。

我们所提出的系统中的CEP和碰撞预测模块使用CEP引擎监控并跟踪无人机的当前位置以及成功检测到的静态和移动障碍物。桌子2呈现来自所提出的系统的三种类型的事件以及其性质。例如，UAVS以每50毫秒为单位生成和发送位置更新事件。无人机位置活动（DroneLocEvent）包含有关无人机的无人机名称 ，无人驾驶飞机的位置在三维飞行区域 ，事件时间T.．CEP发动机接收并处理这些事件，以预测集群中可能发生的无人机对无人机冲突。类似地，对于每个成功检测到的静态障碍，将生成一个静态障碍事件(SObsEvent)并发送给CEP引擎。静态障碍物检测事件中包含静态障碍物的名称和位置静态障碍。CEP引擎处理所有无人机位置更新事件和静态障碍物检测事件，预测无人机到静态障碍物的碰撞。最后，对于成功检测到的移动障碍，生成移动障碍事件(MObsEvents)并发送给CEP引擎。移动障碍物检测事件包含移动障碍物的障碍物名称 ，的位置和事件时间T.．CEP发动机处理无人机位置更新事件和移动障碍物检测事件，预测无人机到移动障碍物的碰撞。

提出的系统实现了三个EPL查询来处理这三种类型的事件，并确定一架无人机是否在接近另一架无人机或静态或移动障碍飞行。清单1显示第一个查询。它使用DroneLocEvents来检查两架无人机是否距离很近。如果匹配成功，CEP引擎触发相关事件汇，该事件汇可以预测无人机与无人机之间的碰撞，然后调用碰撞避免机制来防止无人机之间的碰撞。

清单中的第二个查询2使用Dronelocevents和Sobsevents来确定无人机是否紧邻静态障碍物。同样，列表中的第三查询3.使用Dronelocevents和MobSevents来确定无人机是否靠近移动障碍物。在每种情况下，触发相关的事件宿地，其可以预测碰撞并调用碰撞避免机制。

为了预测这三种不同类型的碰撞，事件接收器使用了不同的参数和规则。参数包括无人机的(当前)位置、静态和移动障碍物的位置以及无人机的期望下一个位置。算法中给出了碰撞预测规则1．规则1规定，当无人机的下一个期望位置时，预测无人机对无人机的碰撞与另一个无人机的当前或期望的下一个位置相同 ．类似地，规则2用于预测无人机与静态障碍物的碰撞，如果无人机试图飞到一个被静态障碍物占据的位置 ．最后，规则3指出，当无人机期望的下一个位置时，预测无人机到移动障碍物的碰撞与移动障碍物的当前位置相同吗 ．

3.2。相互排斥的锁定机制

上一节中描述的CEP和碰撞预测模块涵盖了可能导致UAV碰撞的大部分场景。然而，由于无人机可以快速且任意移动，因此仍然可能发生一些故障和碰撞。例如，在任务期间，一个位置是免费的，两架无人机 同时决定搬到 ．如果CEP和碰撞预测模块对无人机碰撞的预测时间略长，则避撞机制可能没有足够的时间来预防碰撞。然而，如果CEP和碰撞预测模块能够快速、正确地预测碰撞，则避碰模块可以对无人机进行保存只允许其中一个继续飞往 ．其他无人机要么被重定向到另一个位置，要么在当前迭代中无法移动。为了防止这样的场景和失败，我们使用互斥锁定机制来扩展我们的碰撞预测方法。

所提出的系统在当前使用相互排斥的锁和无人机的直接下一个位置，以防止多个无人机尝试同时移动到同一位置。每个位置的锁定状态可以是锁定或解锁．每个UAV的当前位置总是被认为锁定所有其他无人机。此外，一旦UAV决定下一步移动，系统就会在UV的立即下一个位置上互相锁定，以便其他无人机不会尝试移动到同一位置。同样，在决定下次移动的同时，无人机首先检查可能的下一个位置的锁定状态，并仅尝试移动到一些解锁位置。而且，如果多个无人机同时尝试锁定相同的位置，其中一个只获取锁定。对于涉及非常短的时间间隔的场景，可以在一个时间间隔中获取相互排斥的锁，并且可以在下次间隔中执行移动。无人机在飞到下一个地点时立即释放他们之前的位置的锁。

数字2图示了所提出的锁定机构。它表明，UAV始终为其当前位置保留互斥锁。此外，在确定下一个移动时，它首先检查所有可能的下一个位置的锁定状态。然后尝试锁定其中一个解锁的位置。成功锁定下一个位置后，它会移动到下一个位置。最后，它释放了前一个位置的锁定。以这种方式，两个或多个无人机永远不会尝试同时移动到同一位置。

3.3。碰撞避免机制

每当CEP和碰撞预测模块预测碰撞时，它调用我们的碰撞避免机制，这试图找到最佳方法以避免预测的冲突，并以在线方式计算无人机的无机路由。基于预测碰撞的严重程度，周围环境和整体情况以及成功探测到的静态和移动障碍物(和 ）在 ，我们的碰撞避免机制使用的三个防撞技术按照以下顺序:(1)将无人机重定向到另一个方向,(2)把无人机hover-in-place模式直到路线了,和(3)暂时撤退或者回溯无人机去探索一些替代无碰撞路径。算法中给出了所提出的避碰机制的伪代码2．我们的回溯方法将在下一节中描述。

第一种避碰技术，即将无人机重定向到另一个方向，即改变无人机的飞行方向。例如，如果一架无人机在X维度的 ，但是CEP和碰撞预测模块预测由于路径上的障碍物或其他无人机的存在而发生碰撞，那么无人机不能在无危险的情况下继续飞行X维度。因此，该避碰机构对无人机的飞行方向进行了重定向y或Z.尺寸使无人机能够避免碰撞。然而，在一个人口密集和混乱的飞行区域，避碰机制可能无法立即计算出所有无人机的旁路路径。因此，在这种情况下，所提出的避碰机制会激活部分无人机的原地悬停模式，直到情况改善和路径明确。此外，作为最后的手段，它暂时回溯一些无人机，以探索一些替代的无碰撞路线。需要注意的是，这三种避碰技术都会带来一些开销，这可能会延长一些无人机的航线和飞行时间。然而，如前所述，对于安全第一的方法来说，这是不可避免的。

3．4．回溯的方法

所提出的回溯方法可以暂时后退或回溯无人机，因此它可以探索一些替代的无碰撞路线。如算法所示2，所提出的回溯算法在两个情况下触发：（1）如果UAV悬停太长或（2），如果UAV继续移动，但它没有找到适当的碰撞路由即可到达其目的地。在密集的，杂乱的飞行区中，这种情况并非前所未有。有时，UAV会继续悬停或在目的地附近移动，但它没有找到到目标的碰撞路由，因为其他一些无人机或障碍驻留在UAV和其目的地之间，因此阻碍了UAV的路由。在这种情况下，重要的是允许无人机暂时退回或回溯，因此它可能能够探索一些替代路线来达到目的地。

算法中给出了所提出的回溯算法的伪代码3.．算法迭代，直到成功完成所需数量的回溯步骤或达到最大次数的回溯尝试(第9行)。在每次迭代中，它尝试将无人机移动到与目标相反的方向。它随机选择三个维度中的一个 并试图移动无人机，以增加与目的地的距离。回溯算法不会禁用CEP和碰撞预测模块以及互斥锁定机制。因此，在每次迭代中，无人机要么回溯一步，要么发现碰撞危险或无人机未能锁定所需位置，然后悬停在当前位置。当无人机返回正常飞行模式(第10行)时，它探索一些替代的无碰撞路线，以到达它的目的地。

4.一个说明性的例子

在本节中，我们给出一个小例子来说明所提出的在线无碰撞路径生成和导航系统的主要组成部分和步骤。虽然提出的系统适用于现实的三维飞行区域，但在纸上演示三维飞行区域是困难的。因此，我们使用一个二维的飞行区域来做一个简单的说明。

数字3.给出了一个二维飞行区域内4架无人机、2个静态障碍物和4个运动障碍物的实例。在我们的例子中，飞行区域显示为一个7 × 7的网格，其中所有连续的位置彼此之间是统一的、固定的距离。每个无人机的起始和目的地位置也被突出显示。目标是将无人机从起始位置路由到目标位置，同时避免与静态和移动障碍物以及集群中的其他无人机发生碰撞。

应该注意的是，该示例中障碍物的精确位置的知识仅用于说明目的。如前所述，所提出的系统不会对飞行区中静态和移动障碍物的数量和位置进行任何假设。同样，虽然是数字3（a）表明，在使命开始之前，所有移动障碍物存在于特派团开始前，在实际情况下，在执行任务期间，可以在飞行区动态出现一些移动障碍物（例如鸟类）。

数字3 (b)这是自特派团开始后五次间隔后飞行区的快照。结果表明，每架无人机从起始位置开始飞行，向目标位置飞行，在每个时间间隔内随机选择水平维度或垂直维度飞行。数字3 (b)还表明，来自图的左侧最左转障碍物3 (b)在执行任务期间离开飞行区，其余移动障碍移到飞行区内一些新的任意地点。尽管移动的障碍物以任意的方式水平或垂直移动，但在5个时间间隔内，每个移动的障碍物只能移动一步，也就是说，只能移动到飞行区内的下一个连续的位置。因此，移动的障碍物移动得比无人机慢。这是一个合理的假设，因为如果移动的障碍物比无人机移动得更快，即使是最先进和最快的碰撞检测、预测和回避机制也无法避免无人机到移动障碍物的碰撞。

图中标记的方向边3 (b)在线显示系统生成的无碰撞无人机航路。例如，在Figure的左上角3 (b)，标记为1的第一向下边缘意味着UAV 1在向下方向上飞行。类似地，标记为1,2的相同方向上的下一个边缘示出了UAV 1和2使用相同的边缘。但是，使用相同边缘的两个无人机并不意味着无人机到UAV碰撞。当两个无人机同时在同一边缘飞行时，可以发生在边缘上的无人机到UAV碰撞。在此示例中，UAV 1和UAV 2在同一边缘上飞行，但以不同的时间间隔飞行。UAV 1在UAV 2到达那里之前离开了边缘，因此，两个无人机之间没有碰撞危险。数字3 (b)也显示了5个时间间隔后无人机的当前位置。可以看出，除无人机3外，所有无人机都飞行了5步。由于系统无法为无人机3找到一个无碰撞的移动方式，导致无人机3飞行了4步，然后在第5个时间间隔内悬停。

图中的无人机3.在每个步骤中使用所提出的相互排斥的锁定机构。如部分所述3．2，每个UAV首先尝试锁定其中一个解锁的下一个位置。在成功锁定其下一个位置后，无人机将移至其下一个位置并发布了以前的位置的锁。因此，在任何时候，两个或多个无人机都没有尝试移动到飞行区域的相同位置。

图中无人机13 (b)在向下方向开始垂直飞行，并继续朝向其目的地，直到它检测到静止障碍物。在此阶段，我们的CEP和碰撞预测模块预测了一个无人驾驶到静态障碍的碰撞，并调用了我们的碰撞避免机制，该机制将无人机重定向到水平，向右方向，因此无人机可以继续飞行到目的地。但是，在同一时间间隔中，UAV 3试图飞到与UAV 1为首的相同位置。互相检测到的两个UAV，并且UAV和碰撞预测模块预测了UAV到UAV碰撞。结果，调用了我们的碰撞避免机制，该机制试图在垂直，向上方向上重定向UAV 3，但是UAV在该位置检测到移动障碍物，并且CEP和碰撞预测模块预测了无人驾驶的移动 -障碍碰撞。因此，碰撞避免机制激活了UAV 3的停止模式，但让UAV 1锁定然后移动到下一个位置。因此，UAV 3仅在五个时间间隔飞行四个步骤。在这个例子中，无人机2和4并没有遇到碰撞危险，并正常飞向他们的目的地。而且，没有一个无人机徘徊在太长或太长时间才能找到合适的碰撞路线。因此，我们的回溯算法未被调用。

数字3 (c)显示完成任务后的飞行区域快照。它展示了每一架无人机如何找到自己的目的地，同时避开路上的障碍和其他无人机。剩下的三个移动障碍物又移到飞行区内一些新的任意地点。在第6个时间间隔内，无人机1被重定向向下，避免与无人机3发生碰撞。同样，在向下飞行两个时间间隔后，无人机1到达飞行区域的末端，再次转向水平，向右。最后，在向右飞行了几段时间后，无人机1号到达了目的地。如图所示3 (c)在美国，所有其他无人机都以类似的方式找到了自己的方式。

5.实施与实验评价

为了演示和评估我们提出的系统，我们开发了一个软件模拟器。本节简要描述一些重要的实现细节，以及涉及一系列实验的实验评估。我们还将我们的结果与以下四种方法的结果进行了比较:（1）粒子群优化 - 基于PSO的方法．苏吉特和比尔德的[17.基于粒子群算法的路径规划方法为无人机群生成路径。（2）贪婪启发式和遗传算法(GAs)方法．Silva Arantes等人[11]方法采用贪婪启发式算法和GAs算法来生成和优化无人机在关键情况下的路径。（3）快速探索随机树(rrt)．LaValle提出的一种基于采样的路径规划算法[9］．（4）RRT^∗．Karaman和Frazzoli开发的RRT的扩展[10来规划最优路径。

5.1。实现细节

所谓的系统的第一个主要组成部分的实施是基于ESPER CEP引擎和算法1．第二个组件称为互斥锁定机制，实现图中所示的锁定机制2．类似地，碰撞避免组件实现算法2和3.．

我们已经实施了一个简单，受控的模拟平台，不考虑复杂的物理现象和不受控制的环境变量，如引力和风。目的是在理想的情况下测试和评估所提出的系统，同时忽略和最小化外部不受控制因素的影响。因此，更容易分析和解释结果。实施假设所有无人机以相同的速度飞行，并且在执行任务期间没有内部无人机失败。我们还假设每个UAV至少存在至少一个可行的路径。

5.2。实验设计与设置

桌子3.介绍了实验设计。实验评价包括四个实验。在每个实验中，我们都采用了Sujit和Beard提出的方法[17.基于pso的方法，Silva Arantes等[11贪婪启发式和基于ga的方法，LaValle的[9RRT算法，Karaman和Frazzoli的[10] RRT^∗算法执行10次，每次使用随机种子。本节中报告的所有结果均超过10次运行。实验是在内存为16g的英特尔酷睿i7-4790处理器上进行的。在软件模拟器中使用的时间间隔长度为50毫秒。我们测量了以下因变量:(我)平均路由长度(ARL)．随着UAV的数量在离散的飞行区域中移动的平均无人机路径长度。UAV路由是从UAV的起始位置到UAV的目标位置的移动或步骤。要最小化以生成更短的路线。(2)最长路由长度(LLR)．生成的最长路由的总步数。要最小化以生成更短的路线。(3)碰撞数(NC)．无人机碰撞的次数。最小化以生成更安全的路线。(iv)计算时间(T)．算法的计算时间(毫秒)。它是算法运行和产生结果所花费的时间。最小化以减少计算开销。

实验1旨在模拟一个小问题实例。主要目的是在更简单的情况下评估所提出的系统的碰撞预测和避免能力。实验使用了10×10×10飞行区，20个无人机，20个静态障碍物和20个移动障碍物。实验2使用了一个涉及更大的飞行区和更多种无人机和障碍物的大问题实例，并且旨在评估所提出的系统以获得更大的问题实例。实验使用了20×20×20飞行区，50个无人机，50个静态障碍物和50个移动障碍物。

第三个实验评估了该系统在一个人口密集、包含大量静态和移动障碍的杂波环境下的性能。实验3采用与实验1相似的实验设计，但静态和移动障碍的数量是实验1的两倍。最后，实验4的目标是在一个涉及无人机碰撞高风险的场景中评估所提出的系统。该实验采用了与实验2相似的实验设计，但无人机数量是实验2的两倍。

所有的无人机和障碍物都是随机放置的。然而，为了确保无人机在起飞过程中不发生碰撞，我们使用了独特的起始位置，并且在无人机起始位置没有设置任何障碍。同样，无人机的目的地位置也是随机选择的，但确保所有目的地位置都是唯一的，目的地位置没有障碍。

5．3.结果和分析

结果如表所示4．表中最好的结果在大胆的字体。在ARL和LLR列的结果表明，RRT^∗算法(10]在所有实验中产生了最短的无人机路线，而RRT [9生成第二最短的路由。NC列表明，所提出的方法在所有实验中都产生了最安全的路径，而贪婪启发式和基于ga的方法[11产生了第二安全的路线。而言,T其中，RRT方法在实验2和3中表现最好，而本文方法在实验2和3中表现次等，而greedy和GA-based方法在实验1和4中表现次等。以职业薪酬为基础的方法[17.就任何因变量而言，都不是最佳或第二最佳。

在第一个实验中，ARL用于提出的，基于PSO，贪婪和GA的，RRT和RRT^∗算法分别为17、25、26、16、15。类似地，对于所提出的，基于pso的，贪婪的和基于ga的，RRT，和RRT, LLR^∗算法分别为36,49,47,36和29。五种方法也在实验2至4中产生类似的结果。因此，RRT^∗该算法在所有实验中都得到了最短路径。

尽管提出的方法没有产生最短的路线，但它在所有四个实验中都产生了最安全的路线。表中的NC列4显示所提出的，基于PSO，贪婪和GA的，RRT和RRT的碰撞或崩溃的次数^∗算法。所有实验的崩溃总数分别为0、14、9、18和29。如本节所述3.，该系统提供了一种安全第一的方法，在这种方法中，无人机群的无危险、安全操作优先于任何其他目标，包括路径长度。这种安全第一的方法在所有的实验中都很明显。该方法通过交易航路长度生成较长的航路，以提高无人机的安全性。从而避免了所有无人机对无人机、无人机对静态障碍物、无人机对移动障碍物的碰撞，所有无人机都成功完成了机动。

表中的最后一列4显示了T五种算法以毫秒为单位的结果。结果表明，RRT算法在所有实验中运行的时间最少，而在实验2和3中的提出方法执行第二最快，并且贪婪和基于GA的算法在实验中执行第二个最快的算法1因此，结果表明，所提出的算法具有低计算开销，并且在合理的时间内产生安全且有效的路由。

实验1结果表明，所提出的系统适用于较小的问题实例。在实验2的结果中进一步证明了所提出的系统的性能和可扩展性，其产生了更大的问题实例的无人机路线。在实验3中，无人机在其方面遇到了更多的障碍，因为飞行区被静态和移动障碍物杂乱无章。它迫使他们为目的地留下更长时间的路线，但建议的方法成功地避免了所有障碍和碰撞，并将所有无人机传给其目的地。它表明，所提出的系统也适用于密集地填充的杂乱的飞行区域。最后，实验4结果表明，该方法也适用于涉及无人机碰撞风险的复杂问题实例。

6.相关工作

半自主机器人系统的运动安全性问题是目前研究的热点。与自主移动机器人有关的问题的全面概述载于[20.］．在[21.表明最突出的路由方案并不能保证运动安全。我们的方法解决了这个问题，不仅保证了安全，而且提供了高效的在线路由。

Macek等人[22.]提出了一种分层结构的机器人导航解决方案。他们关注的是城市环境中车辆的安全航行问题。它们还区分了全局路线规划和避碰控制。然而，在他们的工作中，他们专注于与单一车辆导航相关的安全问题，而没有考虑在车队或机器人群的背景下无碰撞路径生成和导航的问题。Aniculaesei等[23.]提出了一种采用形式验证来确保运动安全的形式方法。他们使用UPPAAL模型检查器(http://www.uppaal.org/)，以验证移动中的机器人在侦测到障碍物时，是否会启动制动器并安全停止。由于我们提出的系统不假设任何关于静态和移动障碍物的数量和位置的先验知识，也不依赖于初步的离线运动规划阶段，因此在任务开始前无法验证安全要求。因此，我们没有采用正式的验证。本文提出的解决方案快速灵活，能够在线动态生成和重新计算无人机路径，避免了无人机不必要的停止。

Petti和Fraichard [24.]提出了一种依靠局部运动规划来确保安全的方法。他们指出，计算整个航线是一个非常复杂和计算密集型的问题，唯一可行的解决方案是计算下一个安全状态和其中的航行。他们的解决方案支持单一车辆的导航。在我们的工作中，我们离散了飞行区域，并开发了一个高效的系统，计算整个群的下一个安全状态，并提供了在线路径生成和碰撞避免机制。

关于无人机运动规划算法的综合文献综述可在[6］．[6适用于初步的离线运动规划阶段，在任务开始前规划并生成无人机的有效路径或轨迹。我们提出的系统不依赖于规划阶段，并以在线的方式为整个群生成高效、无碰撞的路径。有关无人机运动规划的最新研究载于[7］．

奥格里亚罗等[8]提出了一种用于为四轮车队列生成无碰撞轨迹的算法。他们专注于计划的方法，这些方法提前产生可行的路径。Lavalle [9Karaman和Frazzoli [10]提出了基于采样的路径规划算法RRT和RRT^∗,分别。RRT被设计成通过增量构建树来有效地探索高维空间。RRT^∗是RRT的扩展。它的设计目的是规划最优路径。

马吉德等[15，16.]提出了一条路径规划和导航方法，用于苗条的无人机。它们将离线路径规划组合在线导航方法，并使用机器学习和进化算法来产生有效的路径，同时最大化群体中无人机的安全性。它们还使用碰撞预测和无人机反射，以防止与不可预见的障碍物碰撞。相比之下，本文介绍了一个在线，无碰撞的路径生成和导航方法，不需要离线路径规划。

Dong等人[3.]介绍了一个软件平台，用于多个无人机的在线合作控制。他们的工作侧重于从地面控制站监控和控制多个无人机。该方法不会为无人机生成路径。相反，完整的航班信息（包括无人机路径）被提供给地控制站，该控制站向UAV队列发送控制命令。de souza [13和de Souza和Endler [14]提出了一种利用智能手机和移动通信网络进行无人机集群运动协调的方法。他们使用CEP，但仅用于分析和评估群体的形成精度。此外，他们的工作侧重于群体的内部通信，并且不提供对无碰撞路径生成的解决方案。Bürkle等人。［12]提出了一种多智能体系统体系结构，用于无人机群中的团队协作。他们还开发了一个模拟平台，用于巡逻或监视无人机监控保护区，以防止潜在的入侵。然而，他们没有解决群集的路径规划和避碰问题。

Ivanovas等人[4]提出了一种无人机障碍物检测与避障方法。他们的方法使用计算机视觉技术检测立体相机图像中的静态障碍物。他们方法的主要焦点是如何将一些块匹配算法用于障碍物检测。他们没有提出多无人机的路径规划和避碰方法。Barry和Tedrake [25.]提出了一种障碍物检测算法，用于允许以在线方式检测和避免碰撞的障碍物。同样，林[26.[，]提出了一种在线的无人机路径规划器，用于检测和避免移动障碍物。这些方法仅适用于单个无人机，不为集群无人机提供支持。在我们的工作中，我们假设每架无人机都配备了足够的障碍感知和检测能力，并且不需要任何额外的障碍检测支持。因此，本文重点研究了无人机群的碰撞预测与规避以及在线路径生成与导航。

苏吉特和比尔德[17.]提出了一种基于粒子群算法的无人机群路径规划算法。在他们的方法中，每当无人机检测到移动障碍物时，基于粒子群算法的算法根据碰撞发生前计算新路径所允许的时间为无人机生成新路径。Silva Arantes等人[11]提出了一种针对需要无人机紧急着陆的关键情况下的无人机路径规划方法。他们的方法利用贪婪启发式和无人机在不同类型的设备故障引起的关键情况下生成和优化可行路径。

节5，我们将我们提出的方法与Sujit和Beard的结果进行了比较[17.基于pso的方法，Silva Arantes等[11贪婪启发式和基于ga的方法，LaValle的[9RRT算法，Karaman和Frazzoli的[10] RRT^∗算法。结果表明，我们提出的方法在所有四个实验中都产生了最安全的路径。因此，该方法优于基于pso的、贪婪启发式和基于遗传算法的、RRT和RRT^∗无人机安全问题。

7.结论

本文提出了一种针对无人机群的在线无碰撞路径生成与导航系统。该系统利用无人机和成功检测到的静态和动态出现的移动障碍物的地理位置来预测和避免以下情况:(1)无人机与无人机的碰撞，(2)无人机与静态障碍物的碰撞，(3)无人机与移动障碍物的碰撞。它包括三个主要组件:(1)CEP和碰撞预测模块，(2)互斥锁定机制，(3)避免碰撞机制。CEP和碰撞预测模块利用有效的运行时监控和CEP进行及时预测。互斥锁定机制可以防止多架无人机同时飞向同一位置。该避碰机制是在成功检测到飞行区域内的静态和移动障碍物的情况下，寻找防止无人机相互碰撞的最佳方法。因此，该系统的一个显著特点是能够在线预测碰撞风险，并主动寻找最佳方法来避免预测的碰撞，以确保整个群的安全。

我们还提出了基于仿真的系统实现，以及一系列实验评估，并将我们的结果与四种现有方法的结果进行了比较。结果表明，该系统能够在线预测并避免所有三种碰撞。生成安全高效的无人机航路，有效地扩展到涉及数十架无人机和障碍物的大型问题实例，适用于人口密集、飞行区域混乱、无人机碰撞风险高的场景。

作为我们未来工作的一部分，我们计划在一个更真实的模拟环境中实现该系统，允许考虑复杂的物理现象和不受控制的环境变量。此外，我们希望测试和评估我们的系统，以不同的能力和飞行速度不同的无人机。最后，作为未来的工作，还计划提供足够的支持和在线机制，以处理和控制无人机位置信息不准确和任务执行期间无人机内部故障所产生的情况。

数据可用性

稿件中包含所有重要数据（表4)．

的利益冲突

作者声明他们没有利益冲突。

致谢

这项工作得到了芬兰科学院项目的支持。OpenCPS:加速弹性CPS和CoRA开发的开放集成框架:复杂软件密集型系统的持续弹性保证。

参考文献

1. R. Austin，“无人驾驶飞机系统：无人机设计，开发和部署，”航空航天系列，Wiley，Hoboken，NJ，美国，2010年。查看在：谷歌学者
2. a . Ashraf, a . Majd，和E. Troubitsyna，“为无人机编队的实时、无碰撞运动协调和导航系统”第五届欧洲计算机系统工程会议论文集，ECBS ' 17，第1-9页，ACM，拉纳卡，塞浦路斯，2017年8月。查看在：出版商网站|谷歌学者
3. 董旭东，陈伯明，蔡国强，林海，李廷辉，“多无人机协同控制综合软件系统的开发”，《中国航空航天大学学报》IEEE控制与自动化国际会议的诉讼程序， 1629-1634页，克赖斯特彻奇，新西兰，2009年12月。查看在：出版商网站|谷歌学者
4. A. Ivanovas，A. Ostreeika，R.Maskelićnas，R.Damaševičius，D.Połap，以及M.Woïniak，“基于无人空中车辆的基于障碍物的障碍物避免”人工智能和软计算， L. Rutkowski, R. Scherer, M. Korytkowski, W. Pedrycz等人，Eds。，pp. 58–69, Springer International Publishing, Salmon Tower Building, NY, USA, 2018.查看在：出版商网站|谷歌学者
5. G. Pajares，“基于无人机(uav)的遥感应用概述和现状”，摄影测量工程与遥感第81卷第1期4，页281-330,2015。查看在：出版商网站|谷歌学者
6. C. Goerzen, Z. Kong, B. Mettler，“基于自主无人机制导的运动规划算法综述”，智能与机器人系统学报(第57卷)1-4页，65 - 100,2010。查看在：出版商网站|谷歌学者
7. F.肯德尔，“指导，导航和无人旋翼机制的进步调查”，野外机器人学报，卷。29，不。2，pp。315-378,2012。查看在：出版商网站|谷歌学者
8. F. Augugliaro，A.P.Schoellig和R. D'Andrea，“为十六型舰队的无碰撞轨迹产生：一种顺序凸面编程方法，”2012 IEEE/RSJ智能机器人与系统国际会议论文集，页1917-1922，葡萄牙阿尔加维，2012年10月。查看在：出版商网站|谷歌学者
9. S. M. LaValle，“快速探索随机树:路径规划的新工具”，计算机科学Deptartment，爱荷华州立大学，艾姆斯，IO，美国，1998，技术报告TR 98-11。查看在：谷歌学者
10. S. Karaman和E. Frazzoli，《基于采样的最佳运动规划算法》，国际机器人研究杂志，卷。30，不。7，pp。846-894，2011。查看在：出版商网站|谷歌学者
11. J. D. Silva Arantes, M. D. Silva Arantes, C. F. Motta Toledo, o.t. Júnior，和B. C. Williams，“在关键情况下无人机路径规划的启发式和遗传算法方法”，国际人工智能工具杂志第26卷第2期1、文章编号1760008,2017。查看在：出版商网站|谷歌学者
12. A. Bürkle, F. Segor, M. Kollmann，“自主微型无人机群”，智能与机器人系统学报，卷。61，没有。1-4，pp。339-353，2011。查看在：出版商网站|谷歌学者
13. B. J. O. de Souza，基于移动网络的无人机群体运动协调方法，罗马天主教大学里约热内卢de Janeiro，里约热内卢de Janeiro，巴西，2015，硕士论文。
14. B. J. O. de Souza和M. Endler，“通过移动网络协调无人机群内的行动”2015年IEEE国际普遍计算和通信研讨会（Percom Workshops）的诉讼程序，pp.154-159，西雅图，WA，美国，2015年3月。查看在：出版商网站|谷歌学者
15. A. Majd, A. Ashraf, E. Troubitsyna，和M. Daneshtalab，“集成学习、优化和预测的无人机群的有效导航”，在2018年第26届Euromicro并行、分布式和基于网络的处理(PDP)国际会议论文集2018年3月，英国剑桥，第101-108页。查看在：出版商网站|谷歌学者
16. A. Majd, A. Ashraf, E. Troubitsyna，和M. Daneshtalab，“利用优化、学习和无人机反应来最大限度地提高无人机群的安全性”2018年IEEE进化计算大会论文集，里约热内卢，巴西，2018年1月。查看在：出版商网站|谷歌学者
17. P. B. Sujit和R. Beard，“使用随时算法的多个无人机路径规划”2009年美国控制会议的诉讼程序，PP。2009年6月，美国圣路易斯圣路易斯2978-2983。查看在：出版商网站|谷歌学者
18. A. Mdhaffar, R. B. Halima, M. Jmaiel，和B. Freisleben，“云计算环境的反应性性能监视”，集群计算，第20卷，第2期。3，第2465-2477页，2017年9月。查看在：出版商网站|谷歌学者
19. E. Wu, Y. Diao, S. Rizvi，“基于流的高性能复杂事件处理”2006年美国计算机学会SIGMOD数据管理国际会议论文集，SIGMOD ' 06，第407-418页，ACM，纽约，纽约，美国，2006年6月。查看在：出版商网站|谷歌学者
20. R. Siegwart，I. R. Nourbakhsh和D. Scaramuzza，自主移动机器人导论:智能机器人和自主代理，麻省理工学院出版社，剑桥，马萨诸塞州，美国，2011。
21. T.Fraichard，“关于运动安全的简短论文”2007年IEEE机器人和自动化国际会议的诉讼程序，第1140-1145页，罗马，意大利，2007年4月。查看在：出版商网站|谷歌学者
22. K. Macek，D.Vasquez，T.Fraichard，以及R. Siegwart，“动态城市情景中的安全车辆导航”2008年第11届智能交通系统国际IEEE会议的诉讼程序，第482-489号，中国北京，2008年10月。查看在：出版商网站|谷歌学者
23. A. Aniculaesei，D. Arnsberger，F. Howar和A. Rausch，“在动态环境中验证安全关键自治系统”第一次信息物理系统验证与验证研讨会论文集，pp.79-90，雷克雅未克，冰岛，2016年6月。查看在：谷歌学者
24. S. Petti和T. Fraichard，“动态环境中反应性规划的部分运动规划框架”IFAC / AAAI国际信息学国际信息会议的诉讼程序，自动化和机器人2005年，英国埃克塞特。查看在：出版商网站|谷歌学者
25. A. J. Barry和R. Tedrake，“杂乱环境中的高速导航推送器立体声”，“2015年IEEE机器人与自动化国际会议论文集，pp.3046-3052，西雅图，WA，美国，2015年5月。查看在：出版商网站|谷歌学者
26. 林，无人机的移动避障美国亚利桑那州立大学(Arizona State University, Tempe, AZ, USA)， 2015年博士论文。

版权

版权所有©2020 Adnan Ashraf等。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。