网络路径生成和成群的无人机导航

文摘

日益流行的无人机(uav)对于消费者应用程序,事故无人机的数量也在迅速增加。因此,无人机的运动安全已成为一个主要关心无人机操作员。一群无人机,无法保证安全运行没有阻止无人机碰撞与另一个和静态和动态出现,移动障碍在飞行区域。在本文中,我们提出一个在网上,无碰撞路径生成和成群的无人机导航系统。该系统使用地理位置的无人机和成功地检测到,静态的,和移动障碍预测和避免如下:(1)UAV-to-UAV碰撞,(2)UAV-to-static-obstacle碰撞,和(3)UAV-to-moving-obstacle碰撞。我们碰撞预测方法利用高效运行时监控和复杂事件处理(CEP)及时预测。提出系统的一个独特的特性是能够预见潜在的碰撞和主动找到最好的方法来避免碰撞预测以确保整群的安全。我们还提供一个基于仿真提出了系统的实现以及实验评价涉及一系列的实验和比较我们的结果和四个现有方法的结果。结果表明,该系统成功地预测和避免所有三种碰撞以在线的方式。此外,它生成安全、高效无人机路线,有效地扩展到大型问题实例,适合凌乱区和场景涉及高风险的无人机飞行碰撞。

1。介绍

无人机(UAV)或无人驾驶飞机是一种半自治性的飞机,可以远程控制和操作通过使用计算机和无线电通信线路(1]。无人机根据他们的设计可以分为不同类型,大小和飞行机制。在现有类型、表演或轴飞行器特别受欢迎,因为它们简单的设计,体积小,成本低,更大的机动性,和悬停的能力。quadrotor使用两双相同,垂直导向的这一对螺旋桨旋转顺时针和逆时针旋转。商用表演越来越多被用于各种各样的应用,如监测和监督、搜索和救援行动,地理测绘、摄影和拍摄,野生动物的研究和管理,公共事件,媒体报道农业遥感应用,航空包裹递送(2- - - - - -5]。这些应用程序需要一个高效且可伸缩的解决方案在线路径生成和多个无人机导航系统。

无人机正变得越来越受欢迎。在美国,美国联邦航空管理局(FAA)预计,小型无人机爱好者的数量将从2017年的大约110万增加到240万年的2022 (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 -英国苏塞克斯- 46623754),发生在英国,在伦敦盖特威克机场跑道关闭了一天多,因为两个无人机被发现多次在机场飞行。破坏影响了约110000 760个航班上的乘客没有航班起飞或降落。这类事件一方面说明教育和培训项目的重要性为无人驾驶飞机运营商和罪犯严格立法,但另一方面,他们也激励需要无碰撞路径生成和无人机的导航系统。确保无危险、安全为室内应用无人机飞行也是同样重要的。因此,无人机的运动安全已成为一个主要关心无人机操作员。它指的是无人机的能力与静态检测和避免碰撞和移动环境中的障碍。静态障碍包括建筑物,树木,和其他类似的固定物品,而可移动的物品(例如,鸟)被认为是移动的障碍。

一些商用的表演能够检测和避免一些障碍。例如,收的幻影4职业(https://www.dji.com/phantom-4-pro)使用five-directional传感器提供障碍检测和传感在五个方向前后传感范围高达30米和7米左右。然而,其避障机制并不在各种各样的工作场景。在这项工作中,我们假设每个无人机配备足够的障碍检测能力和能够成功检测所有静态和动态出现,移动环境的障碍。因此,这项工作的重点不是障碍检测。相反,我们专注于预测和避免碰撞。

多个无人机工作以合作的方式可以用来提供强大的功能,一个无人机不能提供(3]。因此,对于大的和高度复杂的应用程序和任务超出了单个无人机的能力或不能有效地执行如果使用只有一个无人机,可以同时使用多个无人机群或形式的舰队。在这样的场景中,无法保证安全运行没有阻止无人机碰撞与另一个和静态和动态出现,移动障碍在飞行区域。因此,在无人机群的背景下,确保运动安全需要设计并实现一个在线运动路径规划,协调,和多个无人机导航系统集成支持预测和避免碰撞。

无人机的运动安全问题是目前重要的研究引起了人们的关注。一些全面的文学评论运动规划算法的无人机可以在[6,7]。这些方法的主要焦点是在离线运动计划阶段计划和生产任务的无人机路径或轨迹开始之前。Augugliaro et al。8)提出了一种规划方法,提前生成可行的路径。拉[9]和Karaman Frazzoli [10]介绍了sampling-based路径规划算法。席尔瓦Arantes et al。11)提出了一种路径规划方法对于关键情况需要紧急降落的无人机。董et al。3)提出了一个软件平台合作控制多个无人机。伯克尔et al。12)提出了一个可替换主体系统架构在一群无人机团队协作。伊万诺娃et al。4)提出了无人机障碍检测方法。de Souza [13de Souza),和无尽的14]提出的方法对运动协调成群的无人机使用智能手机和移动通信网络。他们的工作关注的内部交流群,不提供解决方案无碰撞路径生成。

在本文中,我们提出一个在网上,无碰撞路径生成和成群的无人机导航系统。该系统使用地理位置的无人机和成功地检测到,静态和动态出现,移动障碍预测和避免如下:(1)UAV-to-UAV碰撞,(2)UAV-to-static-obstacle碰撞,和(3)UAV-to-moving-obstacle碰撞。它包括三个主要组件:(1)一个复杂事件处理(CEP)和碰撞预测模块,(2)一个互斥锁定机制,(3)碰撞避免机制。CEP和碰撞预测模块利用高效运行时监控和CEP及时预测。互斥锁机制可以防止多个无人机试图飞到在同一时间同一地点。碰撞避免机制试图找到最好的方法来防止无人机碰撞在一起成功地检测到静态和运动障碍的飞行区域。提出系统的一个独特的特性是能够预见潜在的碰撞和主动找到最好的方法来避免碰撞预测以确保整群的安全。与现有的作品(3,4,6- - - - - -16),我们提出了系统不依赖于一个计划阶段和生产效率,以在线的方式无碰撞路径。我们专注于预测和避免碰撞和在线路径生成和成群的无人机导航。

我们还提供一个基于仿真提出了系统的实现以及实验评价涉及一系列的实验和比较我们的结果与四现有方法的结果9- - - - - -11,17]。结果表明,该系统成功地预测和避免所有三种碰撞以在线的方式。此外,它生成安全、高效无人机路线,有效地扩展到大型问题实例,适合凌乱区和场景涉及高风险的无人机飞行碰撞。我们提出的导航系统,它的实现,实验,结果不是基于无人机群或限于一个特定的应用程序。相反,他们是通用的,足以适用于广泛的应用程序。本文中给出的工作扩展了我们的初步方法和结果报告(2]。

我们进行如下:部分2建立了术语和背景。提出了在线,无碰撞路径生成和导航系统对无人机群提出了部分3。节4,我们说明我们建议的方法的主要步骤在一个小例子。部分5提出了一些重要的实现细节以及实验评估。部分6回顾重要的相关工作。最后,我们提出我们的结论部分7。

2。预赛

该系统不仅支持在线预测和避免碰撞,它还为所有无人机群生成完整的路线。与传统的运动路径规划方法要求所有障碍及其精确的位置必须是已知在任务开始之前,该方法不承担任何先验知识的障碍。换句话说,我们假设的地形飞行区域事先是未知的。因此,该系统不做任何假设的数量和位置的静态和动态出现,移动障碍。它不需要一个初步的,线下运动计划阶段产生高效的无人机航线。在我们的方法中,无人机起飞从开始位置和不间断地飞向目的地,直到提出系统预测碰撞和触发器碰撞避免机制防止碰撞预测。自提出系统使用无人机的地理位置生成路径和预测和避免碰撞,它需要正确和精确位置信息的无人机舰队。不精确和不正确的信息会导致更长的路径,并在最坏的情况下,一些无人机可以碰撞与其他无人机或一些静态或运动障碍。

让任务飞行区域由一组有限的位置 ,在每个位置被表示为一个点在三维空间 。在一个户外的使命,维度可能对应于纬度、经度和海拔高程,分别。确保合适的群体的形成,假定任何两个连续的位置之间的距离在传感范围小于或等于的无人机,大于或等于安全距离无人机。例如,前后感应范围幻影4 Pro无人机是30米。因此,如果群包括幽灵四箴无人机,任何两个连续的位置之间的最大距离 应该小于或等于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)UAV-to-UAV碰撞,(2)UAV-to-static-obstacle碰撞,和(3)UAV-to-moving-obstacle碰撞。我们碰撞避免机制试图找到最好的方法来避免或绕过碰撞和计算无人机以在线方式的无碰撞路径。在人口密集的和杂乱的飞行区域,它可能不可能立即计算绕过所有无人机的路线。在这样的场景中,该系统可能把一些无人机hover-in-place模式直到情况好转,路线明确。此外,它也可能会让一些无人机暂时撤退或放弃寻找更合适,无碰撞路径。

该系统实现了一个安全的方法。因此,无危险,安全运行群整体优先的其他目标包括无人机航线的长度,无人机的及时到达目的地,实现任何其他特定于任务的目标。因此,我们不制定问题作为一个优化问题。相反,我们实现一个随机、贪婪的方法,试图找到安全、高效的路线。无人机起飞从开始位置和不间断地飞向目的地直到CEP和碰撞预测模块预测碰撞,在这种情况下,调用我们的碰撞避免机制,以避免碰撞。此外,我们的互斥锁机制可以防止多个无人机试图飞到在同一时间同一地点。在每个步骤中,提出的方法使得一个随机,贪婪的决定为每个无人机。它试图找到下一个位置为每个无人机不仅安全,而且减少了距离目的地。提出系统的主要组件是下面描述。

3.1。复杂事件处理和碰撞预测

复杂事件处理(CEP)是一种技术,实时、快速处理大量的事件从一个或多个事件流获取和识别重要的复杂事件在事件流和模式。CEP已成功地应用于多种业务领域包括零售管理、卫生保健和云计算(18,19]。例如,在零售管理,CEP可以用来检测入店行窃和缺货事件。CEP的基本或原始事件是加工成复杂或复合事件的事件处理查询,这都写在一个结构化查询语言(SQL)喜欢的语言。因此,CEP为实时事件流提供了一个类似的功能,一个关系数据库管理系统提供了持久数据。

使用最广泛的CEP的工具之一是灵异少女CEP引擎(http://www.espertech.com/esper/),事件处理的查询都写在事件处理语言(EPL)。有三个主要的步骤使用埃斯珀CEP引擎:(1)在第一步中,事件类型和事件注册CEP引擎的来源。一个事件类灵异少女被编写为一个普通Java对象。(2)第二步在EPL需要编写事件处理查询。(3)最后,在第三步中,实现事件水槽可以用来执行一些合适的控制和修复操作。

CEP和碰撞预测模块在计划的系统使用CEP引擎来监视和跟踪当前位置的无人机和成功地检测到静态和运动障碍。表2介绍了三种类型的事件从提出系统以及它们的属性。无人机生成并发送位置在定期更新事件,例如,每50毫秒。无人机位置事件(DroneLocEvent)包含有关无人机的无人驾驶飞机 ,无人驾驶飞机的位置在三维飞行区域 ,时间和事件t。CEP引擎接收和处理这些事件预测可能UAV-to-UAV群碰撞。同样,对于每个成功检测到静态障碍,一个静态障碍事件(SObsEvent)生成和发送到CEP引擎。一个静态障碍检测事件包含的障碍名称静态障碍和位置静态的障碍。CEP引擎处理所有无人机位置更新事件和静态障碍检测事件预测UAV-to-static-obstacle碰撞。最后,对于成功地检测到移动的障碍物,移动障碍事件(MObsEvents)生成和发送到CEP引擎。一个移动的障碍检测事件包含障碍运动障碍的名称 ,的位置移动的障碍,和事件的时间t。CEP引擎流程无人机位置更新事件和运动障碍检测事件预测UAV-to-moving-obstacle碰撞。

提出系统实现三个EPL查询处理三种类型的事件和确定无人机飞行在附近的另一个无人驾驶飞机或一个静态或运动障碍。清单1第一个查询。它使用DroneLocEvents检查两个无人机近距离。如果找到一个匹配,CEP引擎触发事件接收有关,这可能预测UAV-to-UAV碰撞,然后调用碰撞避免机制来防止无人机碰撞在一起。

第二个查询清单2使用DroneLocEvents和SObsEvents确定无人机在附近的一个静态障碍。同样,第三个查询清单3使用DroneLocEvents和MObsEvents确定无人机在附近的一个移动的障碍。在每种情况下,触发相关的事件接收,预测碰撞和调用冲突避免机制。

预测三种不同的冲突,事件水槽使用各种参数和规则。参数包括(当前)位置的无人机和静态和运动障碍和预期的未来无人机的位置。碰撞预测规则提出了算法1。规则1,UAV-to-UAV碰撞时预测所需的下一位置的无人驾驶飞机是一样的当前或预期的位置,另一个无人驾驶飞机吗 。同样,规则2用于预测UAV-to-static-obstacle碰撞,这可能发生,如果无人驾驶飞机试图飞到一个位置被一个静态障碍 。最后,规则3州UAV-to-moving-obstacle碰撞时预测所需的下一位置的无人驾驶飞机是一样的当前位置移动的障碍吗 。

3.2。互斥锁机制

CEP和碰撞预测模块在前一节中描述涵盖了大部分的场景会导致无人机碰撞。然而,由于无人机可能快速行动和随意,有些失败和碰撞仍然可以发生。例如,在一个任务,一个位置是免费的,两个无人机呢 同时决定搬到 。如果CEP和碰撞预测模块需要稍长的预测UAV-to-UAV碰撞,碰撞避免机制可能不会留下足够的时间去防止碰撞。然而,如果CEP和碰撞预测模块快速、正确地预言了碰撞,防撞模块可以保存无人机通过只允许其中一个继续飞行 。另一种无人机将被重定向到另一个位置或者移动当前迭代中失败。为了防止这样的场景和失败,我们增加我们的碰撞预测方法与互斥锁定机制。

该系统使用互斥锁立即对当前和未来无人机的位置,以防止多个无人机试图在同一时间同一地点。每个位置的锁状态可以是锁着的或解锁。当前位置的所有其他无人机无人机总是被认为是锁着的。此外,一旦一个无人机决定其下一步,系统将立即一个互斥锁的位置无人机无人机,其他不要试图移动到相同的位置。同样,决定自己下一步的行动时,无人机首次检查可能的下一个位置的锁状态,只有尝试去解锁位置。此外,如果多个无人机同时试图锁定相同的位置,只有一个人获得锁。场景涉及很短的时间间隔,互斥锁可能获得在一个时间间隔,此举可能在接下来的执行时间间隔。的无人机释放锁之前的位置就飞到下一个位置。

图2说明了提出的锁定机制。它显示了一个无人机通常保持一个互斥锁的当前位置。此外,当决定下一步行动,它首先检查所有可能的下一个位置的锁状态。然后试图锁的一个位置。成功锁定后的下一个位置,它移动到下一个位置。最后,它释放锁之前的位置。通过这种方式,两个或两个以上的无人机从未试图在同一时间同一地点。

3.3。碰撞避免机制

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

第一个防撞技术,即,将无人机重定向到另一个方向,意味着改变无人机的飞行方向。例如,如果一个无人机飞行的x维度的 ,但CEP碰撞和碰撞预测模块预测由于障碍物的存在或另一个无人机路径,然后邮件无人机不能继续飞行x维度。因此,碰撞避免机制重定向的无人机飞行y或z维度的无人机可以避免碰撞。然而,在人口密集的和杂乱的飞行区域,碰撞避免机制可能无法立即计算绕过所有无人机的路线。因此,在这样的情况下,提出碰撞避免机制激活hover-in-place模式的一些无人机直到情况好转和路线清晰。此外,作为最后的手段,它暂时放弃一些无人机探索替代无碰撞路径。应该注意的是,所有三个防撞技术产生一些开销,这可能会延长路线,增加一些无人机的飞行时间。然而,正如前面所解释的那样,这是不可避免的,最安全的方法。

3.4。回溯的方法

拟议中的回溯方法暂时撤退或者回溯无人机,所以它可能会探索一些替代无碰撞路径。所示的算法2触发,拟议的回溯算法在两种情况:(1)如果一个无人机徘徊太久或(2)如果一个无人机继续移动,但没有找到合适的无碰撞路径到达目的地。在人口稠密,凌乱的飞行区域,这种情况并非史无前例。有时,无人机继续徘徊在目的地附近或移动,但它确实没有找到无碰撞的路径到达目的地,因为其他一些无人机或障碍驻留无人机和目的地之间的位置,从而阻碍无人机的路线。在这种情况下,重要的是要让无人机暂时撤退或放弃,所以它可以探索一些替代路线到达目的地。

提出了回溯算法的伪代码的算法3。算法迭代,直到所需数量的回溯步骤成功完成或放弃尝试达到的最大数量(9行)。在每一次迭代,它试图将无人机无人机的目的地的相反的方向。随机选择的一个三维空间 并试图将无人机到目的地的距离增加。回溯算法没有禁用CEP和碰撞预测模块和互斥锁机制。因此,在每个迭代中,无人机后退一步或者如果找到碰撞危险或无人机无法锁所需的位置,然后它徘徊在它的当前位置。当无人机返回到正常飞行模式(第10行),它探索了一些替代无碰撞路径到达目的地。

4所示。一个说明性的例子

在本节中,我们提出一个小例子来说明我们提出的主要组件和步骤网上无碰撞路径生成和导航系统。虽然提出了实际系统的工作原理,三维飞行区域,很难说明和演示三维飞行区域。因此,我们使用一个二维区域飞行了一个更简单的例子。

图3有四个无人机提供了一个说明性的例子,两个静态障碍,和四个飞行在一个二维移动障碍区。飞区在我们的示例中显示为7×7网格,在连续的位置都是统一的,固定的距离分开。每个无人机的起点和目的地位置也会高亮显示。目标是路线无人机从开始位置到目的地的位置,同时避免碰撞与静态和运动障碍和其他无人机群。

应该注意的是,知识的精确位置的障碍在这个例子只是出于演示目的。如前所述,该系统不做任何假设的数量和位置的静态和运动障碍的飞行区域。同样,尽管图3(一个)显示了所有移动障碍存在于任务的飞行区域开始前,在现实的场景中,一些动态移动障碍(例如,鸟)可能出现在飞行区内的执行任务。

图3 (b)提出了飞行的快照区五时间间隔之后开始算起的使命。它表明每个无人机从开始位置开始飞行,飞向目的地位置随机选择飞在水平或垂直维度在每个时间间隔。图3 (b)还显示,最左侧移动障碍从图3 (b)离开了飞行区域的执行任务期间,其余的移动障碍搬到一些新的在飞行区内任意位置。虽然移动障碍以任意方式水平或垂直移动,在五个时间间隔每移动障碍只有一步,也就是说,只有在飞行区内连续下一个位置。因此,移动慢于无人机运动障碍。这是一个合理的假设,因为如果移动障碍比无人机移动得更快,即使最先进的和最快的碰撞检测,预测和规避机制将无法避免UAV-to-moving-obstacle碰撞。

贴上标签,定向边缘图3 (b)显示无碰撞无人机航线以在线的方式由系统生成。例如,在图的左上角3 (b),第一个向下的边缘标记1意味着无人机飞向下的方向。同样,下一个边缘在同一方向贴上1、2 1和2显示无人机使用相同的优势。然而,有两个无人机使用相同的边缘并不意味着UAV-to-UAV碰撞。边上UAV-to-UAV碰撞可以发生在两个无人机飞在同一时间在同一边缘。在这个例子中,无人机1和无人机2飞在相同的边缘,但在不同的时间间隔。无人机1左边缘无人机2到达那里之前,因此,没有两个无人机之间的碰撞风险。图3 (b)还显示当前位置的无人机后五个时间间隔。可以看出,所有无人机除了无人机3飞五个步骤。无人机三飞四个步骤,然后徘徊在第五次间隔因为系统找不到无碰撞对无人机3。

无人机的图3使用该互斥锁机制在每一步。节中描述3.2,每个无人机首次试图锁解锁下一个地点之一。成功锁定他们的下一个位置后,无人机搬到下一个地点和释放锁之前的位置。因此,在任何时候,两个或两个以上的无人机没有尝试去飞的同一位置区。

无人机在图13 (b)开始飞行垂直向下的方向,继续向目的地,直到检测到一个静态的障碍。在这个阶段,我们的CEP预测UAV-to-static-obstacle碰撞和碰撞预测模块和调用我们的碰撞避免机制,无人机重定向到水平,向右的方向,因此,无人机可以继续飞向目的地。然而,在相同的时间间隔,无人机无人机3试图飞到相同的位置1。两个无人机检测,无人机和碰撞预测模块预测UAV-to-UAV碰撞。调用结果,我们碰撞避免机制,它试图重定向无人机3在垂直向上的方向,但无人机探测到一个移动的障碍在这个位置,和CEP和碰撞预测模块预测UAV-to-moving-obstacle碰撞。因此,无人机的避碰机制激活hover-in-place模式3,但是让无人机1锁,然后转移到下一个位置。因此,无人机3飞五时间间隔只有四个步骤。在这个例子中,无人机2和4没有遇到碰撞风险和一般飞向目的地。此外,没有无人机徘徊太久或花了太长时间才找到合适的无碰撞路径。因此,我们回溯算法没有调用。

图3 (c)完成后显示的快照飞行区域的任务。它表明每个无人机发现如何去目的地同时避开障碍物和其他无人驾驶飞机。再一次,其余三个移动障碍搬到一些新的在飞行区内任意位置。在第六次间隔,无人机1重定向在下行方向,避免碰撞与无人机3。同样,飞行后向下两个时间间隔,无人机1达到飞行区域的结束,再次重定向到水平,向右的方向。最后,飞多间隔后向右方向,无人机1到达目的地。我们可以看到在图3 (c)以相似的方式,其他所有无人机发现他们的方式。

5。实施和实验评价

为了演示和评估我们的提出的系统,我们已经开发出一种软件模拟器。本节简要介绍一些重要的实现细节以及实验评估涉及一系列的实验。我们也比较我们的结果和结果的以下四个方法:(1)基于粒子群优化(PSO)的方法。Sujit和胡子的17]PSO-based路径规划方法为一群无人机生成路径。(2)贪婪的启发式和遗传算法(气)的方法。席尔瓦Arantes et al。(11)方法使用贪婪启发式和天然气的生成和优化路径下的无人机关键的情况。(3)迅速探索随机树(rrt)。拉[提出sampling-based路径规划算法9]。(4)RRT^∗。RRT的扩展由Karaman和Frazzoli [10)计划最优路径。

5.1。实现细节

第一个主要组件的实现所提出的系统称为CEP和碰撞预测模块是基于灵异少女CEP引擎和算法1。第二个组件,称为互斥锁定机制,提出实现锁定机制呈现在图2。同样,防撞组件实现算法2和3。

我们实现了一个简单、控制仿真平台,不考虑复杂的物理现象和不受控制的环境变量,如重力和风力。目标是测试和评估拟议的系统在一个理想的场景而忽视和减少外部不可控因素的影响。因此,它更容易分析和解释结果。假设所有实现无人机飞行以同样的速度,没有内部无人机在执行任务失败。我们还假设为每个无人机至少有一个可行的路径。

5.2。试验设计和设置

表3介绍了实验的设计。实验评价包括四个实验。在每个实验,我们跑我们建议的方法,Sujit和胡子的17]PSO-based方法,席尔瓦Arantes et al。(11贪婪启发式和遗传方法,拉的9Karaman RRT算法,和Frazzoli [10]RRT^∗算法10次,每次使用一个随机种子。所有的结果报道在本节平均超过10分。实验运行在一个英特尔酷睿i7 - 4790处理器16 gb的内存。时间间隔的长度中使用软件模拟器是50毫秒。我们测量了因变量:(我)平均路径长度(支持)。无人机平均路径长度测量随着无人机的数量的离散飞行区域。无人机的路线是动作或步骤的序列从无人机的开始位置到无人机的目的地的位置。要最小化生成短路线。(2)长度最长的路线(LLR)。最长的总数中的步骤生成的路线。要最小化生成短路线。(3)数量的碰撞(NC)。无人机的数量碰撞。要最小化生成安全的路线。(iv)计算时间(T)。算法的计算时间以毫秒为单位(女士)。它是算法运行的时间和生产结果。最小化减少计算开销。

实验1是为了模拟一个小问题实例。主要目的是评估碰撞预测和规避能力提出系统的一个简单的场景。实验用10×10×10区20无人机飞行,20静态障碍,和20运动障碍。实验2使用一个大问题实例涉及到一个更大的飞行区域和更多的无人驾驶飞机和障碍,旨在评估提出了一个更大的问题实例系统。实验用20×20×20和50个无人机飞行区域,50 50静态障碍和运动障碍。

第三个实验评估拟议的系统人口稠密,凌乱的环境涉及大量的静态和运动障碍。实验3使用一个类似的实验设计,实验1,但静态和运动障碍的两倍。最后,实验4的目的是评估拟议的系统在一个场景中涉及高无人驾驶飞机碰撞的风险。实验使用了一个类似的实验设计与实验2但无人机的两倍。

无人机和障碍都是随机放置。然而,确保无人机起飞期间不发生碰撞,使用独特的开始位置,没有放置在无人机障碍开始位置。同样,无人驾驶飞机的目的地位置也随机选择,但这是确保所有目的地的位置是独一无二的,没有障碍出现在目的地的位置。

5.3。结果和分析

这项研究的结果发表在表4。最好的结果表中突出显示大胆的字体。陆军研究实验室的结果,LLR RRT列显示^∗算法(10)产生最短的无人机航线在所有的实验中,当RRT [9)生成第二个最短的路线。数控列显示,该方法生产最安全的路线在所有的实验中,当贪婪启发式和遗传的方法(11)产生的第二个最安全的路线。而言,TRRT表现最佳,而该方法执行第二最佳实验2和3,贪婪和遗传方法执行第二个最好在实验1和4。PSO-based方法(17)不执行最佳或第二最佳对因变量。

在第一个实验中,陆军研究实验室的提议,PSO-based,贪婪和遗传,RRT, RRT^∗算法是17日,25日,26日,16日和15日。同样,提议的LLR PSO-based,贪婪和遗传,RRT, RRT^∗算法是36岁,49岁,47岁,36岁,分别和29。五个方法在实验2到4也产生了类似的结果。因此,RRT^∗在所有实验算法产生的最短路线。

尽管该方法并未产生最短的路线,它在所有四个实验产生了最安全的路线。数控列在表4显示了拟议的碰撞或碰撞,PSO-based,贪婪和遗传,RRT, RRT^∗算法。事故的总数在所有实验是0,14日,9日,18日和29日。如上所述节3,该系统提供了一个安全第一的邮件的方法,安全运行的无人机群优先于任何其他目标包括线路长度。安全这方面的建议的方法是明显的在所有的实验。该方法生成的贸易通道长度略长航线的无人机的安全。UAV-to-static-obstacle,因此,所有UAV-to-UAV UAV-to-moving-obstacle碰撞和避免,所有无人机成功地完成了自己的动作。

表的最后一列4显示了T五种算法的结果,以毫秒为单位。结果表明,RRT算法花费最少的时间和生产运行结果在所有的实验中,虽然该方法执行第二最快实验2和3,和贪婪遗传算法在实验1和4表现第二快。因此,结果表明,该算法具有较低的计算开销和它产生安全、高效的路线在合理的时间内。

实验1的结果表明,该系统适用于较小的问题实例。提出系统的性能和可伸缩性在实验2的结果进一步证明,生产无人机路线为一个更大的问题实例。在实验3中,无人机会遇到更多障碍方面,因为飞行区域凌乱了静态和运动障碍。迫使他们需要更长的路线,但该方法设法成功避免了所有障碍和冲突和所有无人机路由到目的地。这表明该系统也适用于人口密集、凌乱的飞行区域。最后,实验4的结果表明,该方法也适用于复杂的问题实例涉及高无人驾驶飞机碰撞的风险。

6。相关工作

运动的半自治机器人系统的安全问题是目前重要的研究引起了人们的关注。一个全面的概述与自主移动机器人相关的问题在[20.]。在进行分析21)表明,最突出的路由方案并不能保证运动的安全。我们的方法解决这一问题,并确保不仅安全,而且还提供了高效、网络路由。

Macek et al。22机器人导航)提出了一种分层的架构解决方案。他们关注的问题,汽车在城市环境中安全航行。他们还区分了全局路径规划和避碰控制。然而,在他们的工作,他们关注的安全问题与单个车辆的导航和没有考虑的问题无碰撞路径生成和导航的舰队或成群的机器人。Aniculaesei et al。23)提出一个正式的方法,使用正式的验证,以确保运动的安全。他们利用UPPAAL模型检查器(http://www.uppaal.org/)来验证一个移动机器人进行刹车和安全地停止检测的一个障碍。自从我们提出系统不承担任何先验知识的数量和位置的静态和运动障碍和不依赖于初步离线运动计划阶段,不能验证安全要求之前开始的任务。因此,我们没有使用正式的验证。提出的解决方案在我们的工作是快速和灵活的动态生成和验算无人机航线以在线的方式,避免不必要的无人机的停止。

Petti和Fraichard24)提出了一个方法,依赖于局部运动计划,以确保安全。他们状态,计算整个路线是这样一个复杂和计算密集型问题,唯一可行的解决方案是计算下一个安全状态和导航。他们的解决方案支持单个车辆的导航。在我们的工作中,我们有离散飞行区域,已经开发出一种高效的系统,计算未来整个群的安全状态,并提供一种机制,在网络路径生成和避碰。

一个全面的文献回顾无人机的运动规划算法可以在找到6]。的方法综述6)适用于初步离线运动计划阶段计划和生产一个有效路径或轨迹的无人机开始之前的使命。我们提出了系统不依赖于一个计划阶段和生产高效、无碰撞路径为整个群体以在线的方式。最近的一项调查运动规划的无人机可以在[7]。

Augugliaro et al。8)提出了一种算法用于生成无碰撞轨迹quadrotor舰队。他们专注于计划的方法,提前生成可行的路径。拉[9]和Karaman Frazzoli [10]介绍sampling-based叫做RRT RRT路径规划算法^∗,分别。RRT旨在有效地探索高维空间的逐步构建一个树。RRT^∗是RRT的延伸。计划是设计的最优路径。

Majd et al。15,16)提出了成群的无人机路径规划与导航方法。他们结合使用离线与在线导航路径规划方法和机器学习和进化算法生成有效路径,同时最大化的无人机群的安全。他们还使用了碰撞预测和无人驾驶飞机反射,防止碰撞和不可预见的障碍。相比之下,本文提出了一种在线无碰撞路径生成和导航的方法,不需要离线路径规划。

董et al。3)提出了一个软件平台在线合作多个无人机的控制。他们的工作集中在监测和控制多个无人机地面控制站。不生成无人机的路径的方法。相反,完整的航班信息(包括无人机路径)提供的地面控制站将控制命令发送给无人机舰队。de Souza [13de Souza),和无尽的14]提出的方法对运动协调成群的无人机使用智能手机和移动通信网络。他们使用CEP但只有来分析和评价形成群的准确性。此外,他们的工作重点的内部交流群,不提供无碰撞路径生成解决方案。伯克尔et al。12)提出了一个可替换主体系统架构在一群无人机团队协作。他们还开发了一个仿真平台巡逻或侦察机监视保护区对潜在的入侵。然而,他们没有解决路径规划和避碰的群。

伊万诺娃et al。4)提出了一个无人机障碍检测和避免方法。他们的方法使用计算机视觉技术检测静态障碍立体相机图像。的主要方法是对一些块匹配算法可以用于障碍检测。他们没有提出一个对多个无人机路径规划和避碰方法。巴里和Tedrake [25)提出了无人机障碍检测算法,以在线的方式允许检测和避免碰撞。类似地,林(26]提供了一个在线的无人机路径规划检测和避免运动障碍。这些方法只适用于单个无人机,不为一群无人机提供支持。在我们的工作中,我们假定每个传感无人机配备足够的障碍和检测能力,不需要任何额外的支持障碍检测。因此,我们专注于预测和避免碰撞和在线路径生成和成群的无人机导航。

Sujit和胡子17)提出了一个PSO-based成群的无人机路径规划算法。在他们的方法中,每当一个无人机检测移动的障碍,PSO-based算法生成一个新路径的无人机根据前的时间可以计算一个新的路径会发生碰撞。席尔瓦Arantes et al。11)提出了一种无人机路径规划方法对于关键情况需要紧急降落的无人机。他们的方法使用贪婪启发式和无人机来生成和优化可行的路径在不同类型的临界情况下引起的设备故障。

节5,我们已经提出了一个比较的结果,我们建议的方法与Sujit和胡子的17]PSO-based方法,席尔瓦Arantes et al。(11贪婪启发式和遗传方法,拉的9Karaman RRT算法,和Frazzoli [10]RRT^∗算法。结果表明,我们建议的方法产生在所有四个实验中最安全的路线。因此,该方法优于PSO-based、贪婪启发式遗传,RRT, RRT^∗方法对无人机的安全。

7所示。结论

在本文中,我们提出了一个在线,无碰撞路径生成和成群的无人机导航系统。该系统使用地理位置的无人机和成功地检测到,静态和动态出现,移动障碍预测和避免如下:(1)UAV-to-UAV碰撞,(2)UAV-to-static-obstacle碰撞,和(3)UAV-to-moving-obstacle碰撞。它包括三个主要组件:(1)CEP和碰撞预测模块,(2)一个互斥锁定机制,(3)碰撞避免机制。CEP和碰撞预测模块利用高效运行时监控和CEP及时预测。互斥锁机制可以防止多个无人机试图飞到在同一时间同一地点。碰撞避免机制试图找到最好的方法来防止无人机碰撞在一起成功地检测到静态和运动障碍的飞行区域。因此,提出了系统的一个独特的特性是它能够预见的风险以在线方式碰撞和主动找到最好的方法来避免碰撞预测以确保整群的安全。

我们还提出了一种基于仿真的实现提出了系统以及一个实验评价涉及一系列的实验和比较我们的结果与现有结果的四个方法。结果表明,该系统成功地预测和避免所有三种碰撞以在线的方式。此外,它生成安全、高效无人机路线,有效地扩展到大型实例涉及几十个无人机的问题和障碍,并适用于人口密集、凌乱飞区和场景涉及高无人机碰撞的风险。

作为我们未来工作的一部分,我们计划实施该系统在一个更现实的模拟环境,允许考虑复杂的物理现象和不受控制的环境变量。此外,我们想要测试和评估系统异构无人机可能有不同的功能和飞行速度不同。最后,一个适当的支持和在线机制来处理和控制情况引起的不精确信息的无人机位置和内部无人机故障任务执行期间还计划为未来的工作。

数据可用性

所有重要的数据都包括在手稿(表中4)。

的利益冲突

作者宣称没有利益冲突。

确认

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

引用

1. r·奥斯汀”无人机无人机系统:设计、开发和部署,”航空航天系列美国新泽西州霍博肯市威利,2010年。视图:谷歌学术搜索
2. a·阿什拉夫a Majd,大肠Troubitsyna”向实时、无碰撞运动协调和导航系统的无人机舰队”学报》第五欧洲计算机系统的工程会议上,欧洲央行的17岁拉纳卡,页1 - 9,ACM,塞浦路斯,2017年8月。视图:出版商的网站|谷歌学术搜索
3. g . x, b . m . Chen Cai, h·林和t·h·李,“开发一个全面的软件系统实现合作多个无人机的控制权,”《IEEE控制与自动化国际会议上,页1629 - 1634,克赖斯特彻奇,新西兰,2009年12月。视图:出版商的网站|谷歌学术搜索
4. a·伊万诺娃a . Ostreika r . Maskeliūnas r . Damaševičius d . Połap和m . Woźniak”无人驾驶飞行器基于块匹配的避障,”人工智能和软计算l .资助,r·谢勒m . Korytkowski w . Pedrycz et al .,。,pp. 58–69, Springer International Publishing, Salmon Tower Building, NY, USA, 2018.视图:出版商的网站|谷歌学术搜索
5. g . Pajares”,概述和现状遥感应用的基于无人机(uav),“摄影测量工程&遥感,卷81,不。4、281 - 330年,2015页。视图:出版商的网站|谷歌学术搜索
6. c .何z香港,b·梅特勒”运动规划算法的调查从自主无人机的角度指导,”智能和机器人系统杂志》上卷,57号1 - 4、65 - 100年,2010页。视图:出版商的网站|谷歌学术搜索
7. f . Kendoul”调查的指导的发展,导航,和无人旋翼机的控制系统,”《机器人技术领域卷,29号2、315 - 378年,2012页。视图:出版商的网站|谷歌学术搜索
8. f . Augugliaro a . p . Schoellig, r·D 'Andrea”一代的无碰撞轨迹quadrocopter舰队:一个连续凸规划方法,”学报2012年IEEE / RSJ智能机器人和系统国际会议阿尔加维,页1917 - 1922年,葡萄牙,2012年10月。视图:出版商的网站|谷歌学术搜索
9. s·m·拉瓦”,快速扩展随机树:路径规划的新工具,”计算机科学Deptartment美国爱荷华州立大学艾姆斯,IO, 1998,技术报告TR 98 - 11所示。视图:谷歌学术搜索
10. Karaman s和大肠Frazzoli Sampling-based算法最优运动规划,“国际机器人研究杂志》上,30卷,不。7,846 - 894年,2011页。视图:出版商的网站|谷歌学术搜索
11. j·d·席尔瓦Arantes m·d·席尔瓦Arantes c·f·莫塔托莱多ot小和公元前威廉姆斯,“启发式和遗传算法对无人机路径规划方法在紧急情况下,“国际期刊《人工智能工具,26卷,不。1,文章ID 1760008, 2017。视图:出版商的网站|谷歌学术搜索
12. a·伯克尔、f . Segor和m . Kollmann“自治微型无人机群,”《智能与机器人系统,卷61,不。1 - 4、339 - 353年,2011页。视图:出版商的网站|谷歌学术搜索
13. b . j . o . de Souza运动协调的方法使用移动网络成群的无人机教皇里约热内卢天主教大学,里约热内卢,巴西,2015年,硕士论文。
14. b . j . o . de Souza和m .无尽的协调运动在成群的无人机通过移动网络”学报2015年IEEE国际会议上普适计算和沟通工作坊(PerCom研讨会),第159 - 154页,西雅图,佤邦,美国,2015年3月。视图:出版商的网站|谷歌学术搜索
15. a . Majd a·阿什拉夫·e·Troubitsyna, m . Daneshtalab”集学习、优化和预测效率成群的无人机导航,”学报2018年26日Euromicro国际会议上平行,分布式和基于网络的处理(PDP)剑桥大学,页101 - 108年,英国,2018年3月。视图:出版商的网站|谷歌学术搜索
16. a . Majd a·阿什拉夫·e·Troubitsyna, m . Daneshtalab”使用优化,学习,和无人驾驶飞机反射最大化成群的无人机,安全”学报2018年IEEE国会进化计算(CEC)里约热内卢,巴西,2018年1月。视图:出版商的网站|谷歌学术搜索
17. p . b . Sujit和r .胡子,“随时多个无人机路径规划算法,”《2009年美国控制会议,页2978 - 2983年,圣路易斯,密苏里州,美国,2009年6月。视图:出版商的网站|谷歌学术搜索
18. a . Mdhaffar r . b . Halima m . Jmaiel和b . Freisleben反应性能监视的云计算环境中,“集群计算,20卷,不。3,第2477 - 2465页,2017年9月。视图:出版商的网站|谷歌学术搜索
19. e . Wu y刁,s . Rizvi“高性能复杂事件处理流,”学报2006年ACM SIGMOD国际会议管理的数据,SIGMOD 06年ACM,页407 - 418年,纽约,纽约,美国,2006年6月。视图:出版商的网站|谷歌学术搜索
20. r . Siegwart i r . Nourbakhsh, d . Scaramuzza介绍自主移动机器人:智能机器人和自治代理美国马剑桥,麻省理工学院出版社,2011年。
21. t . Fraichard“一小篇关于运动安全,”学报2007年IEEE机器人与自动化国际会议上,页1140 - 1145,罗马,意大利,2007年4月。视图:出版商的网站|谷歌学术搜索
22. k . Macek Vasquez d, t . Fraichard和r . Siegwart“安全车辆导航动态城市场景,”学报2008年11日国际IEEE会议在智能交通系统中,第489 - 482页,北京,中国,2008年10月。视图:出版商的网站|谷歌学术搜索
23. a . Aniculaesei d件、f . Howar和a . Rausch”向紧急安全自治系统在动态环境中,验证”第一届研讨会论文集Cyber-Physical系统的验证和确认,页79 - 90,雷克雅未克,冰岛,2016年6月。视图:谷歌学术搜索
24. 美国Petti和t . Fraichard部分运动规划框架,用于无功规划在动态环境中,”IFAC / AAAI学报》国际会议信息控制,自动化和机器人技术2005年,英国埃克塞特。视图:出版商的网站|谷歌学术搜索
25. a·j·巴里和r . Tedrake Pushbroom立体声高速导航在混乱的环境中,”学报2015年IEEE机器人与自动化国际会议上)举行(“国际机器人与自动化会议”,第3052 - 3046页,西雅图,佤邦,美国,2015年5月。视图:出版商的网站|谷歌学术搜索
26. y林,移动为无人机避障美国亚利桑那州立大学,坦佩阿兹,2015年博士论文。

版权

版权©2020 Adnan阿什拉夫等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。