文摘
这项工作提出了一种基于路径规划算法和DWA来实现全局优化路径,同时满足安全性和速度要求无人机(UAV)。该算法首先进行预处理地图不规则无人机在飞行中遇到的障碍,包括网格预处理为凹弧形凸预处理障碍和障碍。此外,标准的一个算法改进的基于无人机的飞行环境信息和运动约束。此外,DWA算法对局部优化的局限性和长时间的规划减轻自适应调整评价函数根据无人机的安全阈值,障碍,和环境信息。因此,构造评价子函数全局最优路径。最后,全球路径选择的关键点的subtarget点局部路径规划。的前提下的最优路径,无人机实时路径的效率和安全是有效地改善。实验结果表明,基于改进的路径规划和DWA算法缩短了路径长度,降低了规划时间,提高了无人机路径平滑和增强了无人机的安全避障路径。
1。介绍
无人驾驶飞行器(无人机)是广泛应用于工业、生命科学、物流、等领域。近年来,无人机路径规划已成为一个关键问题。无人机路径规划设置开始和结束点的无人机环境地图和计划无碰撞,优化,和安全的路径使用相关的路径规划算法。
在无人机的核心,路径规划是路径规划算法。基于就业规划场景,路径规划可以分为全局路径规划和局部路径规划。全局路径规划利用环境地图与已知的障碍,而本地路径规划依赖于环境映射未知的障碍。主要用于全局路径规划算法,例如,一个(1,2),迪杰斯特拉3],RPT [4]。局部路径规划算法包括动态窗口算法(DWA) [5,6),人工势场法(APF) [7,8),而蚁群算法(ACO) [9]。许多学者研究无人机路径规划假设无人机环境常规形状的障碍(例如,圆形或矩形)。然而,无视障碍的违规行为防止准确表示和无人机飞行路径的规划。
律等人提出了一种基于图搜索的路径规划算法。改进算法使用弗洛伊德算法重量不同的路径,这大大减少了路径点的数量,有效地提高了平滑的路径10]。土耳其等人研究无人机雷达逃税的问题,关于一个雷达作为一个圆形禁飞区和实现路径规划在一个二维平面上通过模拟退火算法(11]。姚和王提出一种自适应蚁狮优化路径规划算法(12]。作者验证了算法的有效性,但只考虑圆形和矩形禁飞区。因此,它更适合与理想的障碍地图边界(12]。同样,徐等人模型障碍圆形禁飞区和优化规划路径的基础上,拉盖尔图(13]。Boulares Barnawe等人提出了一种回归算法,曾经丢失的目标计划的预测轨迹无人机的路径搜索任务(14]。Belkadi等人提出了一个分布式无人机轨迹生成策略,解决了一些问题在一群无人机控制和可应用于大规模搜索,监控、检查、和救援15]。黄等人提出了一种基于多无人机协同路径规划方法 - - - - - -平滑和构造多个威胁源组成的一个复杂的环境。使用改进后的蚁群算法 - - - - - -顺序滤波算法获得更灵活的路径(16]。
DWA是一种常用的局部路径规划算法,具有良好的避障能力。然而,很容易陷入局部最优,没有达到指定的目标点。此外,无人机的应用场景的复杂性的增加和环境可能呈现标准DWA无法解决复杂的路径规划问题。因此,通过结合DWA通常需要改进全局路径规划算法。
根据云南省et al .,在解决无人机路径规划问题,引入解耦策略,信使无人机路径规划问题是与社区(称为动态旅行商问题17]。霍等人提出了一个混合微分共生有机体搜索算法(HDSOS)相结合的微分进化变异策略与改进的共生有机体搜索(SOS)策略18]。该算法保持系统的局部搜索能力,同时实现良好的全局搜索性能(18]。解决无人机路径规划的问题在不同的威胁在复杂的环境中,Phung和Ha提出一种粒子群优化算法,不仅是优于经典粒子群优化,群优化阶段,和量子群优化也优于遗传算法(19]。Jeauneau等人提出了无人机路径规划两种方法在一个真实的3 d环境。单一路径提供了基于A *方法,和提供多条路径的遗传算法使用帕累托前沿(PF)。生成的路径必须满足车辆的动态特性(20.]。
当建立环境,研究文学作为规划空间太完美,使其不切实际的。这样的路径规划算法适用于简单的环境地图。考虑到大多数障碍在现实环境中不规则形状和无人机往往被视为粒子,上市的直接应用方法需要扩大范围的障碍和影响规划的结果。因此,改进是必需的。
支持路径规划在复杂的环境中,本文首先研究了不规则的无人机飞行中可能遇到的障碍。这样一个过程包括网格处理的障碍和凸加工凹弧障碍。接下来,提高成本函数通过使用障碍环境中权重系数映射。标准的一个算法是将先进的无人机运动约束和安全阈值。同时考虑速度和安全DWA的不相容,通过自适应算法提高速度评价函数,考虑障碍和安全的密度阈值。最后,全局路径规划中的关键节点作为当地subobjective指出,虽然依靠改进的改进算法和DWA算法。结果,最优,最短路径更平滑从开始到结束计划。
2。预处理环境建模和障碍
大多数的障碍在无人机的飞行环境是不规则的形状,和无人机通常被认为是一个粒子。无人机的飞行环境是直接视为普通地图,它很容易扩展的障碍和影响范围规划结果,首先环境地图处理。
2.1。网格空间建模方法
假设无人机在飞行的高度是常数,无人机运动在三维空间中简化的二维运动。假设以下无人机路径规划条件是:(1)起始点和目标点(2)无人机的物理性能的限制(3)信息的障碍
此外,请注意,巡航无人机可以被视为一个粒子。
2.2。网格的弧的障碍
本文利用粗糙集的概念来获得一个多边形近似弧形障碍(21]。的主要方法首先确定网格弧障碍的外缘,连同其定位网格。然后,多边形处理执行,每个弧网格定位的点连接,如图1 (b)。具体步骤如下:(步骤1)确定外缘线( )电弧障碍( )。此外,确定每个弧的网格位置线 ,并表示标记网格元素 。作为网格元素标记的中心定位点,并表示他们 ,在哪里段的数量的外缘线(步骤2)连接定位分 ,获得多边形通过对每个 顺时针从起始标记网格元素。因此,获得障碍的结果多边形处理,
(一)
(b)
2.3。凸填充凹多边形的障碍
凸灌装的过程就开始了通过确定网格中的每个多边形顶点的坐标图。从第一个网格元素开始,多边形顶点表示 ,在哪里是多边形的顶点数。如果内部角形成的两个相邻边缘大于180度,相应的顶点是一个凹点。否则,顶点是一个凸点。的搜索算法,如果路径点落入凹区域,下一个路径点必须放置在凹区域完成飞行任务。凹区域影响无人机路径质量和增加无效的路径点的数量,影响速度的解决方案。
图2显示了一个示例的凸灌装过程。的步骤如下。(步骤1)确定凹多边形的顶点 ,和法官的凹面和凸面每个顶点根据凹性和凸性规则(图2(一个))(步骤2)根据步骤1,从开始的凸点 ,和其他连接凸点顺时针,产生多边形凸的结果(例如, )。然后,根据弧障碍,障碍网格如图2 (b)
(一)
(b)
3所示。改进了算法
有许多转折点和大角度的路径通过标准的计划 ,这不利于无人机飞行。因此,这项工作提高了标准根据无人机飞行的运动特征和环境信息。
3.1。改进的启发式函数
的评价函数由一个成本函数和一个启发式函数 ,和最优搜索算法的性能依赖于启发式函数的选择。改进的一个算法引入了启发式的障碍权重系数函数,如方程所示(2)。障碍权重系数表达了网格地图的复杂性,和环境信息进行了分析。
障碍权重系数被定义为障碍的人数的比例在当前地图和网格细胞的数量在整个网格地图。让代表障碍网格细胞的数量和无人机起点和终点的坐标表示 和 ,分别。权重系数被定义为的障碍 在哪里成本从开始节点到当前节点,是启发式函数值从当前节点到目标节点, 当前节点的坐标,然后呢成本函数的重量吗 。的系数计算的比例从当前节点到目标点的距离和距离的起始节点到目标点。
根据方程(2),改进后的算法集自适应启发式函数的重量。当障碍权重系数很小,启发式函数的重量增加。的一个算法减少了搜索空间,提高了路径规划的速度,并有效地降低了拐点,拐点的路径。当障碍权重系数大,减少启发式函数的重量和增加搜索空间,以避免算法陷入局部优化。
3.2。确定无人机的安全距离
改进的一个设置路径节点之间的安全距离和障碍防止无人机碰撞与障碍。如图3的垂直距离(点的垂直距离行 )障碍的路径与预设安全距离判断路径是安全、可行的计划。
假设节点的坐标是 ,和目标节点的坐标是 。表示节点的坐标障碍作为 和节点的坐标作为 。线段的长度 ,表示为 ,障碍和线段之间的距离吗沿着纵轴。线之间的夹角和 - - - - - -轴是 ,而表示路径的距离障碍。具体原则如下:
的距离从方程(后的路径计算障碍6)。让表示安全阈值。然后,距离是相对于安全距离来确定路径是否可以作为一个替代路径。如果 ,被遗弃的道路。然后,根据改进的算法,继续寻找新的节点,直到找到最优路径。否则(即。,当 ),路径选择。
3.3。路径平滑优化
正如前面强调的,因为该算法搜索原理和节点搜索方向的标准算法8-node扩张方向,路径规划的算法是不利于无人机飞行。此外,路径规划需要很长时间,搜索路线接近障碍物的边缘。改进的一个算法结合了弗洛伊德算法的一个算法,有效地减少转折点在无人机路径的数量(22),提高无人机运动效率,满足无人机的应用程序需求。考虑运动模型来判断派生路径比原来更适合关于距离,时间,和角度,该算法优化路径的比较如图4。
如图4,标准的一个算法产生的路径( )。这条路有许多拐点,导致可怜的平滑。
弗洛伊德平滑算法可以用来消除冗余路径节点,有效地减少匝数和优化路径长度。Floyd算法结合了无人机运动特点改善路径平滑。通过判断是否存在两个节点之间的一个障碍,以及考虑到安全阈值和距离两个节点之间的连接到障碍,一个人可以决定的道路是可行的。最后,路径( )是获得。
在描述原则的基础上,标准的一个算法和改进的算法模拟和验证,所得路径如图5。
(一)
(b)
计划的标准算法(图5(一个))有很多冗余节点和道路部分,及其转动角度大。结果,路径长度是75.1543公里,这是次优(即。,而不是最短的)和不符合无人机的操作规则。相比之下,路径规划的改进算法(图5 (b))是相对顺利,其长度等于72.0735公里。因此,改进算法达到4.1%的改进路径长度。此外,可以观察到一定安全距离之间的全局路径和障碍,更有利于无人机运动。
4所示。改善DWA
局部路径规划,标准DWA算法只指定了目标点的位置,未能考虑未知的障碍。此外,当有很多障碍,路径规划算法容易陷入局部最优,导致全球路径长度的增加。改进的一个算法作为全球路径的关键节点subtarget点当地的道路。然后,使用环境信息调整速度评价子函数的权重系数。因此,无人机可以成功避免未知的障碍和安全、高效地达到目标点。
4.1。运动模型
DWA的基本思想(6,23,24)来预测无人机的速度矢量空间和状态矢量空间在一个特定的时间,模拟无人机的轨迹预测的时候,最后选择最优轨迹的基础上,评价函数。假设无人机正以统一的方式在每一个时间间隔 ,无人机运动学模型如下: 在哪里 是无人机的位置坐标和姿态角坐标在世界坐标的时间吗和是动态窗口(在下一节中进一步介绍)。
4.2。无人机的速度采样
DWA模型无人机的避障问题作为一个具有速度约束的优化问题,包括非完整约束,环境障碍约束和无人机动态约束。
DWA的速度向量空间图如图6。横坐标和纵坐标代表无人机角速度( )和无人机线速度( )。按照,和表示最大和最小线速度,而和最大和最小的角速度。整个区域 ,白色的区域( )代表了安全的地方无人机的速度范围考虑电动机转矩控制周期的限制。最后,是无人机动态窗口由上市三组的交集。
根据无人机的速度限制,是无人机的线速度和角速度拟合的最大动态窗口范围内:
无人机的运动轨迹可以细分为几个线性或圆周运动。为了保证无人机的安全,最大减速的情况下,当前无人机的速度应当能够在空中悬停在一定精度范围内前遇到障碍,和速度趋于0。线速度和角速度被定义为附近的障碍 在哪里是无人机的最大线性减速,无人机的最大角减速, 之间的最短距离路径和障碍。
无人机电动机转矩的局限性影响最大和最小实现速度和在一个特定的时间 。因此,动态窗口需要进一步降低。鉴于目前的线速度和角速度 ,动态窗口在下一个时期符合下列要求: 在哪里无人机的最大线性加速度和吗无人机的最大角加速度。
最后一个速度范围是一组在讨论的三集的交集,和动态窗口定义如下:
连续速度矢量空间( )离散基于线速度和角速度样本的数量获得离散采样点( )。每个采样点的无人机运动轨迹下一刻预计使用无人机运动学模型(见图7)。
4.3。自适应DWA算法
DWA控制速度使用权重系数( )速度评估子功能。如果太大,无人机是非常快的,但安全是减少。相反,如果太小,无人机的速度是不够的,但是安全是非常高的。考虑无人机的安全与速度之间的关系,改进的DWA算法自适应地计算速度评价函数的权重系数,而依赖于环境信息。无人机的传感器是用来收集环境信息。障碍密度和无人机之间的距离和障碍环境中用于计算速度评价函数的权重系数。权重系数调整,以达到更高的速度在安全领域,而速度是降低危险的地区提高无人机飞行安全。
4.3.1。障碍检测的安全阈值
的距离计算不同障碍使用障碍和无人机之间的距离和角度。具体计算公式如下:4 在哪里和之间的距离 - - - - - -th和 - - - - - -障碍和无人机无人机之间的角度和障碍。
之间的距离不同的障碍是判断无人机可以通过障碍。当等于两倍以上的两个障碍物之间的距离,无人机可以通过扩张的障碍。
4.3.2。自适应函数计算
无人机安全依赖于无人机之间最短的距离和障碍(表示 ),这是自适应动态的输入函数。阈值被定义为 在哪里是无人机的最高速度,是无人机的线性加速度,是参数。最大速度成正比和线性加速度成反比 。因此,无人机的刹车力越强,阈值越小。速度越快,阈值越大,保证无人机的安全。
速度评价函数的权重系数之间的关系和输入如下:
如果在无人机飞行安全阈值(即最短的距离无人机和障碍小于无人机安全阈值,无人机的飞行速度降低(根据指数函数的性质)。如果无人机飞行安全阈值(即外。,最短的距离无人机和障碍大于无人机之间的安全阈值),无人机的飞行速度是根据重量最大速度,如方程所示(14)。
最大速度的重量,安全阈值,然后呢是调整参数。当大于 ,重量随输入的增大而单调上升速度 ,也就是说, 。当小于 ,体重是一个指数函数的速度和 。的比率和减少,增加。否则,如果 的增加,减少。
4.3.3。改进的评价函数
标准DWA算法并不指无人机的全局路径只有计划的目标点。此外,在众多障碍的情况下,这个过程很容易落入局部最优,产生更大的路径距离。的 在评价函数无人机轨迹移动远离障碍,导致局部最优轨迹和增加全球移动的距离。如果相应的加权系数( )直接减少,无人机面对未知的障碍不能及时避免,导致碰撞。
解决上述问题,方位评价函数 设计于一体的全球路径的节点。让 表示当前的仿真速度的评价功能。两个不同的障碍评估函数, 和 ,设计。 被定义为评价函数预测轨迹的终点之间最短的距离和全球已知的障碍。同样的, 是评价函数预测轨迹的终点之间最短的距离和未知的障碍。轨迹评价函数如下: 在哪里 , , ,和的系数四个评估。
5。融合算法
这项工作结合了全局和局部路径规划。关键节点在全球道路被视为subtarget点当地的动态路径,确保动态路径规划的全局最优性。全局路径规划是已知的地图上进行。无人机的轨迹信息在未来期间计算基于无人机的当前的线速度和角速度。每个无人机轨迹预测使用评估标准,和不合理的轨迹或那些遇到一个障碍被丢弃。路径评价子功能评估某一路径,评估值积累。成本最低的轨迹被视为最优轨迹。如果当前最优轨迹是通的,无人机行动的速度对应于最优轨迹。无人机避免了基于避障规则遇到障碍。改进算法的流程图如图8。
6。仿真实验与分析
6.1。实验环境
主要模拟环境由英特尔核心i5 - 8265 u (R)的CPU @1.60GHz, Windows10,并在MATLAB环境下进行了模拟。一个 路径规划,建立了相应的网格地图来验证该算法的有效性。无人机的最大转向角被认为是相等的 。在仿真中,网格粒度是这样 公里,安全阈值等于0.8公里,无人机的起点和终点的坐标是(0.5,0.5)和(49.5,49.5)。无人机的飞行环境是通过网格处理障碍和凸加工凹弧障碍。无人机最初的领空如图9。
6.2。路径规划与仿真研究已知和未知的障碍
6.2.1。在最初的空域环境路径规划
仿真实验比较了改进算法、标准DWA算法和融合和DWA算法获得的规划时间和由此产生的路径的长度。结果如表所示1。
仿真结果(表2和图10)表明,改进了全局最优路径算法的计划。而改进的一个使用标准DWA算法,路径规划算法平滑而不是全局最优。此外,计划的路径不是基于全球计划路径,意思有几个冗余路径。在图10 (c),DWA算法结合了全局路径规划和考虑环境信息在无人机的飞行。因此,速度评价子函数的权重系数自适应地调整,有效地减少无人机路径规划时间。同时,障碍是杰出的减少影响评价函数已知的障碍,和计划路径短,接近全球规划路径。
(一)
(b)
(c)
根据表1路径的长度计划使用改进的融合和DWA算法相比降低了2.8%,通过标准DWA算法获得。此外,规划时间减少了26.3%,无人机的飞行速度平均增加了31.6%。
6.2.2。路径规划时的障碍是未知的
来验证该算法的路径规划性能在一个未知的环境中,障碍是暂时的无人机路径规划。灰色框(参见图代表未知的障碍11)。从图可以看出11,改善算法不能产生路径避免未知的障碍。标准的DWA算法成功地避免了障碍,但附近的无人机时才开始绕过障碍,提高碰撞的概率。图中所示11 (b),无人机不能沿着最初计划全球飞行路径,有很多冗余路径,提高了无人机的飞行距离。结合改进的算法和DWA算法,可以实现局部路径规划,可以有效地避免未知的障碍。当地的路径类似于全局路径,证明可以得到平稳安全的路径。
(一)
(b)
(c)
类似的实验报告部分6.2.1仿真实验比较了改进了算法、标准DWA算法和融合和DWA算法。获得的路径规划时间和路径长度如表所示2。
见表2,改善计划和DWA算法减少了路径长度的2.4%标准的DWA算法。此外,规划时间减少了35.7%,而平均无人机的飞行速度增加34.2%。
接下来,创建不同大小的环境地图获取环境不同的复杂性。将地图范围 , , , ,和 。最短路径长度和不同环境下路径规划的时间提取(数字地图12和13)。
如图12,地图大小的增加导致增加无人机的飞行路径。与标准DWA算法相比,平均路径计划融合的改进和DWA算法降低了4.22%。改进的优点和DWA算法与地图大小的增加更明显。图13显示的路径规划时间融合改进和DWA算法显著短于标准的DWA。此外,地图大小的增加突出的优点提出改进和DWA算法,表明该算法更有利于广泛的无人机路径规划。
7所示。结论
这项工作缓解方面的缺点路径的平滑度和安全使用标准的一个计划算法和解决的问题标准DWA算法对陷入局部最优的倾向。本文提出了一种路径规划算法相结合的改进算法和DWA算法,利用这两种算法的优势,减少它们的局限性。主要结论如下:(1)通过网格建模的不规则地图,这项工作建立网格处理障碍和凸加工凹弧障碍(2)环境信息和运动约束是用来改善算法。相比标准路径算法,通过改进的计划算法平滑,无人机的运动安全保证(3)设计一个自适应DWA动态调整路径评价函数使用的安全阈值,无人机信息和环境信息的障碍(4)关键节点的全局路径规划的改进的subtargets算法作为局部路径规划。这样的设计可以确保全球最优路径,提高了无人机的实时路径规划的效率和安全(5)实验结果表明,基于改进的融合的路径规划和DWA算法有效地减少了路径长度,缩短了无人机路径规划时间,并提高了路径平滑和当地的安全避障
数据可用性
使用的数据来支持本研究的发现可以从相应的作者。
的利益冲突
作者宣称没有利益冲突有关的出版。
确认
作者要感谢中国国家自然科学基金(批准号51909245和51909245),重点实验室开放基金的高性能船舶技术(武汉科技大学),教育部(批准号gxnc19051802),山西省自然科学基金(批准号201901 d211244),北中国大学高层次人才科研(批准号304/11012305),2018年的科技创新项目,在山西高等教育机构(批准号2020 l0272和2019 l0537),中国和北大学的自然科学基金(批准号XJJ201908)。