《电子技术应用》

基于改进人工势场法的无人机在线航路规划算法

2018年电子技术应用第4期
杨丽春1,2,顾颖彦1,白 宇2
(1.江苏自动化研究所,江苏 连云港222061;2.北京航空航天大学 电子信息工程学院,北京100191)
摘要: 在线航路规划能够使无人机针对动态变化的环境快速有效地生成相适应的飞行航路,是无人机任务规划系统必需的能力之一。基于人工势场法提出一种三维在线航路规划方法,使无人机在应对动态变化的飞行环境时能实时规划出保障飞行安全并满足其任务执行效率指标的飞行航路。此航路规划方法在环境构建过程中引入了参考航路引力场和自适应的时间扰动因子,解决了原人工势场法在航路规划中容易陷入势场局部最小值而导致无法用适感环境动态变化区域的问题。在此基础上,提出一种虚拟目标法以更有效地解决人工势场法遇到的局部极值陷阱问题。通过仿真验证表明:所提出的无人机在线航路规划方法比传统的人工势场法更容易跳出势场的局部最小值,且有较好的避障能力。
中图分类号: V297
文献标识码: A
DOI:10.16157/j.issn.0258-7998.174798
中文引用格式: 杨丽春,顾颖彦,白宇. 基于改进人工势场法的无人机在线航路规划算法[J].电子技术应用,2018,44(4):5-9,13.
英文引用格式: Yang Lichun,Gu Yinyan,Bai Yu. UAV′s online route planning algorithm based on improved artificial potential-field[J].Application of Electronic Technique,2018,44(4):5-9,13.

UAV′s online route planning algorithm based on improved artificial potential field

Yang Lichun1,2,Gu Yinyan1,Bai Yu2
(1.Jiangsu Automation Research Institute,Lianyungang 222061,China; 2.School of Electronic and Information Engineering,Beihang University,Beijing 100191,China)
Abstract: Online route planning could make the UAV in the dynamic environment quickly and efficiently generate suitable flight routes so that it is the necessary ability of UAV mission planning. This paper presents a three-dimensional online route planning method based on the adaptive artificial potential field method,which could cope with the UAV dynamic flight environment and quickly generate the real-time safety flight route that satisfies the task requirement. The route planning method uses the reference route gravitational field and the adaptive time disturbance factor in the process of constructing environment to help the UAV escape the trap when fall into the local minimum of potential field. And a virtual target method is proposed to help effectively solve the trapping problem. Computer simulation results show that the UAV online route planning method is easier to jump out of the local minimum of the potential field than the traditional method, and has better obstacle avoidance capability.

0 引言

    无人机在线航路规划是综合考虑无人机机动性能、任务需求等约束条件因素应对动态变化的规划环境,进而规划出一条满足任务需求的最优或可行航路[1]。传统的航路规划算法是以固定的任务目标、稳定不变的飞行环境为假设前提而提出的,是静态的规划,而无人机在实际的军事、勘探、商业等应用中,其任务目标与飞行环境都可能是变化和不确定的,因此传统的航路规划算法无法满足无人机在动态变化的任务执行环境中快速运行期间对航路变化的要求。由于传统航路规划算法存在在线规划能力不足的问题,一种可以快速有效地生成针对动态变化环境相适应的飞行航路的在线航路规划方法亟待提出。

    近年来,国内外许多学者针对动态环境中的飞行器航路规划问题做了大量研究,并提出了多种可行的算法——动态规划法[2-3]、神经网络法[4]、启发式A*搜索法[5]、模拟退火法[6]、遗传算法[7-8]、粒子群算法[9]等。这些算法比传统的航路规划算法有更好的在线规划能力,使飞行器可以在动态变化的飞行环境中做出与环境变化相应的反应,然而当飞行环境地形精度要求较高时,地形栅格数量急剧增加,从而搜索空间变大,这些算法的规划用时会大幅增加,大大降低了无人机的反应速度,使其动态规划能力下降。其次这些方法规划出来的航路没有充分考虑无人机实际的飞行航迹与飞行性能,大多航路是以关键坐标点间直线连接组成不平滑的航路,这种连接方式必须考虑无人机安全指标,例如最大转弯半径、最小直飞距离等。因此,这些常用于全局航路规划的算法在针对动态环境的在线航路实时规划方面仍存在一定不足。

    本文在考虑无人机的机动性能和威胁回避要求的基础上,提出了一种基于改进的自适应人工势场法(Artificial Potential Field,APF)的在线航路规划方法。该方法以全局规划生成的航路规划结果为参考航线,根据飞行环境的动态变化快速生成可行航路以确保飞行的安全和任务的执行效率。同时针对人工势场法在特殊区域容易陷入局部最小值,从而导致规划失败的问题,以变化的参考航路势场替代任务目标引力场,尽可能减少势场局部最小值的情况。同时引入时间因子,即使无人机陷入特殊区域的局部最小值,也可以通过时间因子的扰动快速脱离,确保航路规划的成功。另外提出一种虚拟目标方法,选取适当虚拟目标暂时替代实际目标,帮助解决局部极值陷阱问题。仿真结果表明,基于自适应人工势场法的航路规划方法满足在线航路规划的实时性和安全性要求,势场局部最小值的处理切实可行。

1 人工势场法的基本理论与应用

    人工势场法在机器人的路径规划算法中已经有大量的应用,并常被用于解决三维路径规划问题[10-13]。人工势场法与其他三维航路规划算法相比具有显著的优点:首先,人工势场法在规划航路时只需根据势力场计算当前位置受到的合力,结合当前无人机运动状态进行避障规划,所以其最显著的特点即为计算量小,运算速度快[14]。其次,利用人工势场法可以得到平滑而安全的航路,而其他航路规划算法不仅需要对航路进行平滑操作,可能还需要重新进行最小直飞距离、最大爬升角度等飞行安全性能检测。

1.1 人工势场法的基本理论

    人工势场法的基本原理是:将环境中运动的物体看作处于虚拟力场中的一个质点,虚拟力场由目标的吸引力场和障碍物的排斥力场组成,通过搜索沿着势函数下降的路线规划出避撞的航路。单障碍物受力图和多障碍物受力图分别如图1和图2所示。其中虚拟引力如式(1)所示,斥力如式(2)所示,详细步骤如下:

wrj1-t1.gif

wrj1-t2.gif

    (1)在规划空间内设计势场。任务目标对应吸引力场,方向指向目标位置。威胁障碍物对应排斥力场,方向为远离障碍方向。

    (2)根据规划空间引力和斥力场模型计算合力,结合运动物体当前运动状态规划运动轨迹。

     wrj1-gs1-2.gif

式中,k为引力正权重因子,X为无人机的位置矢量,Xg为目标的位置矢量;η是斥力正权重因子,ρ是无人机与威胁障碍之间的距离,ρ0是单个威胁障碍的最大作用距离,当无人机与威胁障碍的距离大于ρ0时无排斥力作用。

    然而,没有全局采样的人工势场法可能因为失去对全局的感知而容易陷入局部最小值,由于人工势场法有依赖局部势场的特性,可能存在人工势场的构建不合理的情况,如果目标点的势能并不是最小或存在局部极小值,那么当无人机随着势场的引导到达势场的局部极小值时有很大几率无法逃离该区域,从而导致航路规划失败。

1.2 局部最小值陷阱

    当目标点处于障碍物近力场范围内,此时无人机向目标前进时障碍物产生的斥力会急剧增大并超过目标点的吸引力,无人机将受到远离目标的合力而远离目标运动,表现为无人机在目标位置附近盘旋而不能完成规划,如图3所示。

wrj1-t3.gif

    当无人机、威胁源中心和目标处于同一直线,威胁源在无人机和目标中间时,由于合力可能等于零,无人机将在威胁源前停止运动,或当吸引力过大时无人机将与威胁障碍相撞,这两种情况都会导致规划失败,如图4所示。

wrj1-t4.gif

    当多个排斥力和吸引力在某一区域近乎相等时,由于合力几乎为零,无人机的运动速度会变慢,甚至停止,导致规划失败,如图5所示。

wrj1-t5.gif

    针对人工势场法的局部最小值问题,一些研究人员采用在局部最小值点对势能增加微扰的方法,增加无人机逃出局部最小值捕获的概率,还可以在势能引导的基础上考虑无人机自身的惯性,也能有效解决这一问题。通过对问题的分析,本文对传统人工势场法引入参考航路引力场和时间扰动因子的方式进行改进,来解决容易陷入局部最小值的问题,并提出一种虚拟目标法,为逃离局部极值陷阱提供新的解决方案。

2 改进的人工势场法

    要利用人工势场法进行无人机在线航路规划,确切的飞行环境及飞行安全约束都必须转化为相应的引力场或斥力场,形成整个规划空间或局部空间的势场。

2.1 人工势场法的基本理论

2.1.1 刚性约束场

    为保障无人机的飞行安全,无人机需要躲避危险地形及突发高度威胁,满足最低飞行高度的限制。无人机携带的燃料有限考虑避障航程,满足对无人机最大航程的限制。当无人机执行任务时不得跨越禁飞区时,应满足航空管制要求等情况都是刚性约束的范畴。则按照人工势场法对威胁障碍的建模标准,其中刚性约束势场的地形约束虚拟斥力FTerrain为:

     wrj1-gs3.gif

式中,X为无人机当前位置向量,h为X处的离地高度,ηTerrain为地形高程虚拟力的正权重因子。禁飞区、最大航程及恶劣天气等刚性约束的虚拟力公式和上述表示相似。

2.1.2 威胁约束场

    无人机在敌方空域执行任务时可能会出现进入敌方雷达侦测范围、高炮威胁范围或电磁通讯干扰范围等危险情况,长时间停留在敌对识别区内将直接威胁着无人机的安全。按照人工势场法对威胁障碍的建模标准,其中威胁约束势场的雷达约束虚拟斥力如式(4)所示:

     wrj1-gs4.gif

式中,ηradar为雷达威胁排斥力的正权重因子,X为无人机当前位置矢量,雷达的最大作用距离为Rmax,Xradar为敌对雷达的位置矢量。当敌对雷达与无人机距离超过雷达最大识别距离后虚拟排斥力变为0,为消去极点影响,对分母增加Rmax/10项。敌方高炮威胁区约束和电磁干扰约束的虚拟力公式和式(4)相似。

    传统规划算法除了要将上述飞行环境进行数学建模外,还需要对无人机自身飞行性能参数约束进行建模,来保证规划结果为可飞航线。例如最小直飞距离约束、最小转弯半径约束及最大爬升率约束等。由于基于人工势场法的在线航路规划方法根据势函数的连续特性规划形成平滑而安全的航路,完全不需要对航路规划结果再进行平滑处理,而且规划结果也完全满足无人机飞行性能约束的要求,不再需要对上述飞行性能约束进行建模。

2.2 目标引力场优化

    本文提出将目标引力场使用参考航路引力场进行替代的方法,使无人机受到向参考航线靠拢的力。离线规划算法的可靠性保证了参考航路的可靠性。因此,可以构建人工势场尽可能少出现局部最小值的情况。仅仅是静态地对参考航迹构建人工势场虽然可以消除原人工势场构建过程中存在的局部最小值,却不能保证新的人工势场不会引入新的局部最小值,因此这种方式不能根本地解决局部最小值问题。

    为了能够保证消除人工势场中的局部最小值,参考航路引力场的中心位置随着时间和无人机当前位置改变进行变换,才可以满足局部最小值都能随着时间的推移而失去最小值特性,能最大限度地规避整个规划区域的局部最小值问题。本文无人机在模拟仿真时每隔时间Δt对飞行环境进行检测,如图6所示,如果有新增威胁时对其进行斥力场建模,无人机当前位置和出发点的实际飞行距离为s,当前飞行速度为v,则设置参考航线距离起点s+v×Δt的点为无人机的下一个飞行目标,实现目标引力场随时间及运动状态依据参考航线动态变化。

wrj1-t6.gif

2.3 时间扰动因子优化

    由于新引入代替的航路引力场仍有可能生成新的局部最小值,所以进一步考虑无人机速度因素,增加时间扰动因子。本文对目标的吸引力进行如下的设计,记X为无人机位置矢量,Xobj为动态目标点的位置矢量,则目标点的吸引力Fobj如式(5)所示。

    wrj1-gs5.gif

式中,μp为正权重因子,表示当前目标的吸引力随着目标距离的增加而增加,这主要为了保证在无新增威胁的情况下无人机能沿着参考航线飞行;μt为目标吸引力的时间扰动分量权重因子,当无人机速度在正常范围时μt值为零,当无人机的速度降低到一定范围,并且此状态保持一定时间后,μt的值随着时间增加,吸引力增加将人工势场局部最小值重新调整,保证当无人机在局部最小值时总可以被目标吸引而逃离局部最小值点。

2.4 虚拟目标法

    当规划航路陷入局部最小值而无法逃离时,提出一种使用虚拟目标暂时替代实际目标的方法,使航路逃离局部极值陷阱。如何找到合适的虚拟目标是虚拟目标法的关键,虚拟目标的位置特点是:(1)可以使航路逃离当前的局部极值陷阱。(2)到达虚拟目标后,从虚拟目标到实际目标的路径规划将不再回到已经逃离的局部极值陷阱。

    因此,如图7所示,航路规划当前位置为C点,离目标点较近的障碍物中心位置为O点,实际目标位置为T点,需要根据路径当前位置、障碍物位置与实际目标位置的位置关系找出满足虚拟目标条件的虚拟目标点U。连接并延长直线CO、TO,分别交障碍物圆O的边缘于点E、F,则在射线OE、OF夹角范围内,障碍物圆O的边缘(即弧线EF的外侧)任取一点即为虚拟目标点U的位置,一般取|OU|=|OC|,∠FOU=∠EOU。设立虚拟目标后,目标引力发出位置由T点变为U点,按照前文所述方法,可绕过障碍物,到达U点。当到达U点后,目标引力发出位置由U点恢复为T点,则已经逃离局部极值陷阱继续进行航路规划。

wrj1-t7.gif

3 航路规划算法仿真

3.1 时间扰动因子优化

    基于APF算法的在线航路规划在按照参考航路运行中,压线能力出众,并有平滑航迹的功能。对改进后的无人机在线航路算法进行仿真,首先对无人机的航路进行离线规划,设置禁飞区后规划无人机参考航路和新的雷达威胁源,在线规划结果如图8所示。

wrj1-t8.gif

    由图8可以看出,自适应APF和传统APF方法在应对雷达威胁源的处理基本相似,均能尽可能远离雷达的最大识别距离,然而传统APF方法在应对已知刚性约束(禁飞区)时,在禁飞区边缘出现震荡飞行,这种航路并不满足最优的安全系数要求,而依据参考航线飞行则满足飞行安全系数。通过调整自适应APF算法中的权重因子?滋p可以实现不同侧重的规划效果,对不同的因子μp进行仿真结果如图9所示。

wrj1-t9.gif

    可以看出,当μp为0.5时,无人机的航线较光滑地从新威胁的左侧通过;当μp为到1.5时,虽然无人机从威胁右侧通过,但其在威胁处机动较明显,这是因为目标的吸引使无人机保持在参考航路附近,当靠近障碍物时排斥力急剧增加,所以航迹显示转弯曲率较大;μp进一步调整,可以看出无人机航路更接近最优航路。

    在构建环境中出现局部最小值情况下,传统APF算法和自适应APF算法仿真结果如图10所示。

wrj1-t10.gif

    从图10可以看出,传统APF算法在威胁源附近震荡而不能完成规划;自适应APF算法进入局部最小值区域时,开始行为与传统APF法行为类似,当震荡超过一定时间后,参考航迹中的目标点吸引力会随着时间的增加逐渐变强,最后势能局部最小值点被破坏,无人机从中逃离,顺利完成规划。

    通过算法仿真对自适应APF算法中参数的调整可以实现航迹的调整,对避障规划有更好的适应性,同时在不低于传统APF算法速度的情况下对极端情况下的无人机在线航路规划有较好的规划效果。

3.2 虚拟目标法仿真

    在路径规划环境中设立多个障碍物,形成使采用人工势场法易陷入局部极值陷阱的环境。采用虚拟目标法后的规划情况如图11所示,可见航路顺利逃出了局部极值陷阱。在航路规划完成后,需要对航路的关键航点进行选取,陷阱部分只对进入陷阱前与逃离陷阱后的两个关键航点选择,使规划出的实际航线避开逃离陷阱过程浪费的路径,其他部分则按照航点所需步长规则进行选择。

wrj1-t11.gif

4 结论

    在线航路规划算法是无人机任务规划系统的重要组成部分,具有重要的现实意义和工程实用价值。本文以人工势场法为基础,围绕当前应用该方法遇到的问题开展研究。通过对人工势场法在线航路规划算法的改进,解决了在线规划容易陷入死循环无法快速准确规划等问题,为实际无人机研究项目的关键技术进行攻关,部分成果经过适应性改进可以直接应用到实际无人机实验项目中。本文提出的改进的动态适应人工势场法在线规划算法与虚拟目标法对无人机航路规划领域相关问题有较好的参考价值。

参考文献

[1] 胡木,李春涛.无人机在线航路规划技术研究及其工程实现[J].四川兵工学报,2010,31(3):14-17.

[2] 赵锋,杨伟,杨朝旭,等.无人机三维航路动态规划及导引控制研究[J].计算机工程与应用,2014,50(2):58-64.

[3] 任博,吕雪燕,董彦斌.基于网格模型的无人机航路规划仿真[J].计算机仿真,2011,28(12):38-41.

[4] 刘洲洲,潘鲁宁.静态威胁下的无人机航迹规划[J].微处理机,2014(6):55-57.

[5] 席庆彪,苏鹏,刘慧霞.基于A*算法的无人机航路规划算法[J].火力与指挥控制,2013(11):5-9.

[6] 华珊珊.基于遗传退火算法的无人机航路规划[J].计算机测量与控制,2013,21(3):712-715.

[7] 李子杰,刘湘伟.基于进化算法的多无人机协同航路规划[J].火力与指挥控制,2015(2):85-89.

[8] 马云红,周德云.基于遗传算法的无人机航路规划[J].电光与控制,2005,12(5):24-27.

[9] 倪天权,王建东,刘以安.交叉粒群算法在无人机航路规划中的应用[J].系统工程与电子技术,2011,33(4):806-810.

[10] 焦红艳.基于人工势场的多Agent路径规划方法研究[J].河南科技学院学报(自然科学版),2016,44(4):56-61.

[11] 王芳,万磊,徐玉如,等.基于改进人工势场的水下机器人路径规划[J].华中科技大学学报(自然科学版),2011,39(s2):184-187.

[12] 王超,朱大奇.基于人工势场与速度合成的AUV路径规划[J].控制工程,2015,22(3):418-424.

[13] 单宝明,周培培.基于改进人工势场法的机器人路径规划研究[J].信息技术,2014(1):170-173.

[14] 丁家如,杜昌平,赵耀,等.基于改进人工势场法的无人机路径规划算法[J].计算机应用,2016,36(1):287-290.



作者信息:

杨丽春1,2,顾颖彦1,白  宇2

(1.江苏自动化研究所,江苏 连云港222061;2.北京航空航天大学 电子信息工程学院,北京100191)

继续阅读>>