2. 西北工业大学 自动化学院, 陕西 西安 710072
无人机航路规划是根据无人机的特定任务,考虑地形、气象等环境因素以及无人机自身的飞行性能,在满足多约束条件的前提下,为每架无人机规划出从起始点到目标点的可飞航路,实现指定性能指标最优或较优的过程。针对无人机航路规划问题,国内外学者提出了许多算法,如人工势场法[1-4]、模糊逻辑算法[4-7]、A*算法[8-10]、遗传算法[11]、蚁群算法[12-15]、粒子群算法[1]等。
传统的人工势场法易陷入局部极小值,为了改善这个缺点,文献[1]提出了改进的人工势场法,通过修改斥力方向,设置本机与障碍物的距离小于临界值,并将其与自主建立虚拟目标牵引点相结合。在行走的过程中,若本机与障碍物的距离大于临界值,则采用修改斥力方向的方法进行路径规划,当本机与障碍物的距离小于临界值时,则转入自主建立虚拟目标牵引点算法进行路径规划。模糊逻辑算法在多障碍物环境下具有良好的寻找路径能力,文献[6]构建了一套多障碍物环境下基于模糊逻辑的机器人避撞路径规划方法,该方法较好地解决了多障碍物环境下机器人局部规划路径的问题。蚁群算法的优点是可以进行全局路径规划,但是其搜索能力与收敛速度间存在相互制约关系。为了解决上述问题,文献[12]提出了优化禁忌表及双向蚂蚁群体的不同搜索策略来提高蚂蚁的搜索能力和算法的收敛速度。文献[17]针对航迹规划最优性和实时性问题,构建了改进粒子群无人机航迹规划算法。文献[18]提出了快速扩展随机树的航迹规划方法,解决了无人机实时三维航迹规划问题。
本文分别设立了静态障碍物和动态障碍物环境,基于最小分离距离和航程比2个指标分析比较了人工势场法、模糊逻辑算法和蚁群算法对无人机碰撞规避路径规划的性能。对传统的人工势场法存在易陷入局部极小值和在目标点附近易震荡的缺点,本文对人工势场法的斥力函数进行改进,减小了无人机陷入局部极小值点的可能性。
1 人工势场法 1.1 人工势场法的基本原理人工势场法是根据电荷间相互作用规律的理论演变而来的。其实质就是对无人机的运行环境人为建立一个对目标点的引力场以及对障碍物的斥力场,无人机在其合力的作用下,将会避开障碍物向目标点移动并最终到达目标点。若无人机的当前位置坐标向量为X=(x, y), 目标点的坐标向量为Xg=(xg, yg), 引力势场函数是无人机到目标点距离的函数, 定义为:
(1) |
式中,k为大于0的引力场函数的系数常量; ρ(X, Xg)=‖X-Xg‖。引力为引力势场函数的负梯度:
(2) |
若障碍物的坐标为X0=(x0, y0), 无人机到障碍物的距离为ρ(X, X0)=‖X-X0‖, 则定义斥力势场函数:
(3) |
式中,m为大于零的斥力场系数常量, ρ0为障碍物的最大影响范围。斥力定义为
(4) |
人工势场实时处理能力强、规划速度快、运算量小, 具有良好的路径规划性能, 但当其引力与斥力大小相等方向相反时, 所有力相互抵消使合力为零, 会使无人机陷入局部极小值, 导致规划失败。
1.2 改进的人工势场法传统的人工势场法存在易陷入局部极小值和在目标点附近易震荡的缺点, 本文针对以上缺点, 对人工势场法的斥力函数进行改进。当无人机遇到障碍物时将斥力分为两部分:
1) 当障碍物速度与无人机速度方向成锐角时, F1为斥力方向, 新增斥力F2为f向量和斥力F1向量的合向量方向, 其中f向量方向与-V方向相同, 大小与F1相等, 如图 1a)所示。
(5) |
2) 当障碍物速度与无人机速度方向成钝角时, F1为斥力方向, 新增斥力F2方向为垂直斥力F1方向, 大小与F1相等。当无人机在规避动态障碍物时, 当预测出移动目标移动速度、方向及航迹后, 无人机从移动目标后方穿过能保证无人机与障碍物成功避开且规避路径最短, 如图 1b)所示。
上述改进的人工势场法通过新增与移动目标运动方向相反的斥力, 可以使无人机恰好在移动目标后方进行障碍规避, 达到减小规避路径的目的。且由于新增斥力的影响, 减小了无人机陷入局部极小值点的可能性。
2 模糊逻辑算法模糊控制是建立在人工经验基础上、不需知晓被控对象的数学模型就可以对系统实施控制的一种算法。模糊控制算法易对不确定系统或非线性系统进行控制, 对被控对象的参数变化有较强的鲁棒性。在基于模糊逻辑(fuzzy logic)的无人机路径规划算法中, 算法分为目标搜寻(goal searching behavior)、障碍规避(obstacle avoidance behavior)、数据融合(fusion weight behavior)三部分来进行。算法框架如图 2所示。
假设无人机仅在水平面内活动, 不考虑垂直方向上的运动。以无人机起始点建立坐标轴xoy, 无人机速度大小恒定, 设为V。设无人机与目标点间连线与x轴间的夹角为θ, 则其对时间的导数为其角速度ω。设无人机速度方向与x轴的夹角为α, 则定义ϕ=α-θ, 为无人机向着目标点的角度。建立无人机的数学模型为
(6) |
1) 目标搜寻(goal searching behavior):
此环节保证无人机能最终向着目的地而去, 以此时刻无人机距离目的地的距离D和无人机向着目标点的角度ϕ作为输入, 通过模糊推理系统, 确定无人机向着目的地的速度VGS和角速度ωGS。
(7) |
2) 障碍规避(obstacle avoidance behavior):
此环节以障碍物最左端、中心、最右端距离无人机的距离dL, dF, dR为输入, 通过模糊推理系统, 确定无人机在规避障碍物时的速度VOA和角速度ωOA;
3) 数据融合(fusion weight behavior):
此环节将目标搜寻环节和障碍规避环节所得无人机速度与角速度进行融合:
(8) |
通过模糊推理系统确定融合的参数τ, 从而得出最终无人机速度与角速度。
模糊逻辑算法在多障碍物环境下寻找路径能力强, 但其对规则库的依赖性大, 若所构造规则库不够全面, 若输入量和规则不匹配, 算法性能将大大降低甚至完全不适用。
3 蚁群算法蚁群算法(ant colony optimization, ACO)是由Macro Dorigo于1991年受蚂蚁觅食过程中的路径行为启发而提出的随机搜索全局优化方法。蚂蚁在寻找食物过程中, 会向周围环境释放信息素, 为了找到最优路径, 蚂蚁的搜索空间要尽可能大, 但是这会导致收敛速度变慢, 因此, 需要在全局最优以及收敛速度之间达到一个折中。蚂蚁们沿着释放信息素浓度最大的路线行进搜索, 最终找到食物。若有蚂蚁开辟出一条更短的路径, 由于信息素的多少与路径长度成反比, 越来越多的蚂蚁会逐渐移动到这条更优路径上, 经过一段时间后, 就可以规划出一条最短的路径。
蚁群算法在路径规划过程中, 将地图按栅格划分, 分别标记可行路径节点和障碍节点。设置蚂蚁总数为m, 每只蚂蚁按照一定的距离移动, 选择下一个可行路径节点, 并释放强度一致的信息素。从i节点到j节点, 第k只蚂蚁的转移概率为:
(9) |
式中,π(t)表示蚂蚁k一步允许选择的节点, 用公式表示为:
(10) |
式中,σk为蚂蚁设置的禁忌表, 用来记录蚂蚁k走过的路径。α为信息素浓度启发因子, α越大, 代表该路径是多数蚂蚁选择的路径; β为期望启发因子, 用来为蚂蚁提供选择下一个位置的依据, 蚂蚁趋向于选择距离短的路径, 此时β值较大。ηij为期望启发函数, 是位置i和位置j之间距离dij的倒数
(11) |
蚂蚁在经过的路径上留下的信息素实时更新, 其更新规则为
(12) |
式中,ρ为信息素挥发系数, ρ∈(0, 1)。
(13) |
Δτijk为蚂蚁在t到t+n时刻留在i和j位置间的信息素。依据ant-cycle模型:
(14) |
式中,Q为信息素强度; Lk为蚂蚁k所走过的路径长度; Pk(begin, end)为蚂蚁k从起点到终点所走的路径。
在ant-quantity模型中
(15) |
在此定义
(16) |
当迭代次数达到预先设定的值或者最佳路径不再变化时, 上述迭代过程中止。算法收敛的快慢与蚂蚁数m, 信息素浓度因子α、启发信息因子β、信息素浓度挥发因子ρ均有关。蚂蚁数量m越大, 路径搜索的随机性越高, 因此收敛就越慢, m太小则会出现搜索过早停滞现象。
4 仿真实验及结果分析该仿真实验基于MATLAB 2016a进行, 实验仿真分2个环节进行:单机对单动态障碍物、单机对多静态障碍物。仿真过程中, 根据实际项目要求, 参照以下几个指标进行评价:
1) 对地形建筑物等静止目标的规避最小分离距离(即无人机空间飞行轨迹与目标的最短距离)不小于100 m;
2) 对空中飞行器的规避最小分离距离(即无人机与飞行器空间飞行轨迹间的最短距离)不小于200 m;
3) 飞机因规避机动偏离原始任务飞行路径所增加的航程不超过规避起始点到规避终止点直线距离的50%(以下简称航程比)。
在动态障碍物环节分别对人工势场法和模糊逻辑算法进行仿真比较; 在静态障碍物环节分别对以上3种方法进行仿真比较。
4.1 动态障碍物环境仿真实验设计了相同的仿真环境, 仅考虑无人机水平方向的运动, 且假设无人机与障碍物均为质点。障碍物由鼠标在Matlab GUI界面手动随机绘制。图 3为基于人工势场法的无人机对动态障碍物仿真图, 图 4为基于模糊逻辑算法的无人机对动态障碍物仿真图。表 1给出了APF和Fuzzy算法对5个随机动态障碍物的最小分离距离, 表 2比较了动态障碍物环境下2种算法航程比。
实验设计了相同的仿真环境, 针对最小分离距离和航程比2个指标比较了上述3种算法。图 4~6分别为基于改进人工势场算法、模糊逻辑算法和基于蚁群算法的单机对多静态障碍物仿真图。表 3给出了3种算法对5个静态障碍物环的最小分离距离, 表 4比较了静态障碍物环境下3种算法航程比。3种算法均是通过改变障碍物包络大小来实现无人机尽可能远离障碍物进行规避机动, 障碍物包络的大小直接影响了无人机与障碍物的最小分离距离和航程比。蚁群算法是一种基于栅格地图的全局优化算法, 栅格划分的大小对规划路径的性能指标影响巨大, 同时, 栅格划分越多, 对算法运算量和运行时间也影响巨大。本仿真实验考虑到实验计算机运算能力有限, 在蚁群算法的仿真中通过一定比例尺缩放后, 将100×100地图划分为100个10×10的栅格, 在栅格中设置可行节点和障碍节点对路径进行寻优规划。由于栅格的粗糙性, 使得所规划路径航程比增加不少, 但从中可以看出蚁群算法所规划路径的全局最优性, 即最短。模糊逻辑算法由于其目标搜寻环节的存在, 使得无人机倾向于从多障碍物中间穿插而过, 而人工势场法需要考虑全部障碍物的影响, 在规划路径时倾向于从多障碍物边缘绕开。蚁群算法由于具有全局搜索能力, 所规划航迹一定会从障碍物中间穿过, 使其规避路径最短。
m | ||||||
方法 | 最小分离距离 | x | ||||
1 | 2 | 3 | 4 | 5 | ||
AFP | 176.6 | 168.2 | 173.6 | 181.3 | 169.3 | 174.0 |
Fuzzy | 125.9 | 128.3 | 129.9 | 127.0 | 122.6 | 126.7 |
ACO | 158.1 | 141.1 | 141.4 | 141.4 | 158.1 | 148.1 |
结合上述2种环境下的仿真实验可以得出以下结论:
1) 人工势场法运行速度快、实时性强,所规划航迹光滑,改进的人工势场法克服了易陷入局部极小值和在目标点附近震荡的缺点,使其可以很好地适用于无人机。
2) 模糊逻辑算法在系统模型未知的情况下也能适用,算法鲁棒性强。但其依赖于根据先验知识建立的规则表,规则表建立的好坏直接关系着算法的性能。在适宜的规则表下,模糊逻辑算法运算量小、运算速度快,实时性强。
3) 人工势场法和模糊逻辑算法属于局部规划算法,而蚁群算法作为全局优化算法,在栅格选取适宜的情况下,更容易为无人机规划出全局最优的路径。但蚁群算法搜索空间大时,选择随机性大,算法收敛能力差,且蚁群算法中信息素对算法的寻优能力影响重大。
5 结论本文针对小型无人机路径规划问题进行了探讨与研究。分别设立了静态障碍物和动态障碍物环境,基于最小规避距离和航程比这2个指标,对传统人工势场算法进行了改进,减小了无人机陷入局部极小值点的可能性。将其与模糊逻辑算法和基于蚁群算法在无人机路径规划的性能上进行了比较。仿真实验结果表明,3种算法均可实现动态、静态障碍物环境下对无人机碰撞规避路径规划。3种算法各有优缺点,通过融合改进的方式,未来可以运用于现实的感知与规避系统,在全局信息未知的情况下实现最优路径规划。此外,针对实际的感知与规避系统,在设计路径规划算法时,应综合考虑无人机的处理速率约束、气动约束、环境感知约束等,针对特定应用背景下的无人机路径规划方法还有待研究。
[1] |
刘砚菊, 代涛, 宋建辉. 改进人工势场法的路径规划算法研究[J]. 沈阳理工大学学报, 2017(1): 61-65.
LIU Yanju, DAI Tao, SONG Jianhui. Research of Path Planning Algorithm Based on Improved Artificial Potential Field[J]. Journal of Shenyang Ligong University, 2017(1): 61-65. (in Chinese) DOI:10.3969/j.issn.1003-1251.2017.01.015 |
[2] |
孟蕊, 苏维均, 连晓峰. 基于动态模糊人工势场法的移动机器人路径规划[J]. 计算机工程与设计, 2010, 31(7): 1558-1561.
MENG Rui, SU Weijun, LIAN Xiaofeng. Mobile Robot Path Planning Based on Dynamic Fuzzy Artificial Potential Field Method[J]. Computer Engineering and Design, 2010, 31(7): 1558-1561. (in Chinese) |
[3] |
丁家如, 杜昌平, 赵耀, 等. 基于改进人工势场法的无人机路径规划算法[J]. 计算机应用, 2016, 36(1): 287-290.
DING Jiaru, DU Changping, ZHAO Yao, et al. Path Planning Algorithm for Unmanned Aerial Vehicles Based on Improved Artificial Potential Field[J]. Journal of Computer Applications, 2016, 36(1): 287-290. (in Chinese) |
[4] | ZHANG T, ZHU Y, SONG J. Real-Time Motion Planning for Mobile Robots by Means of Artificial Potential Field Method in Unknown Environment[J]. Industrial Robot, 2013, 37(4): 384-400. |
[5] |
李擎, 张超, 韩彩卫, 等. 动态环境下基于模糊逻辑算法的移动机器人路径规划[J]. 中南大学学报, 2013(增刊2): 104-108.
LI Qing, ZHANG Chao, HAN Caiwei, et al. Path Planning Based on Fuzzy Logic Algorithm for Mobile Robots in Dynamic Environments[J]. Journal of Central South University, 2013(suppl 2): 104-108. (in Chinese) |
[6] | KARIM B, ZHU Q. A Fuzzy Logic Behavior Architecture Controller for a Mobile Robot Path Planning in Multi-Obstacles Environment[J]. Research Journal of Applied Sciences Engineering & Technology, 2013, 5(14): 3835-3842. |
[7] | LI Q, ZHANG C, HAN C, et al. Path Planning Based on Fuzzy Logic Algorithm for Mobile Robots in Static Environment[C]//Proceedings of IEEE Conference on Control and Decision Conference, 2013: 2866-2871 |
[8] |
顾辰. 改进的A*算法在机器人路径规划中的应用[J]. 电子设计工程, 2014(19): 96-98.
GU Chen. Application of Improved A* Algorithm in Robot Path Planning[J]. Electronic Design Engineering, 2014(19): 96-98. (in Chinese) DOI:10.3969/j.issn.1674-6236.2014.19.031 |
[9] |
占伟伟, 王伟, 陈能成, 等. 一种利用改进A*算法的无人机航迹规划[J]. 武汉大学学报(信息科学版), 2015, 40(3): 315-320.
ZHAN Weiwei, WANG Wei, CHEN Nengcheng, et al. Path Planning Strategies for UAV Based on Improved A* Algorithm[J]. Geomatics and Information Science of Wuhan University, 2015, 40(3): 315-320. (in Chinese) |
[10] |
屈耀红, 肖自兵, 袁冬莉. 基于风场信息的无人机在线航迹规划方法[J]. 西北工业大学学报, 2012, 30(4): 576-581.
QU Yaohong, XIAO Zibing, YUAN Dongli. An Effective Method of UAV Flight Path Planning On-Line in Wind Field Using Improved A* Searching Algorithm[J]. Journal of Northwestern Polytechnical University, 2012, 30(4): 576-581. (in Chinese) DOI:10.3969/j.issn.1000-2758.2012.04.018 |
[11] |
徐翔, 梁瑞仕, 杨会志. 基于改进遗传算法的智能体路径规划仿真[J]. 计算机仿真, 2014, 31(6): 357-361.
XU Xiang, LIANG Ruishi, YANG Huizhi. Path Planning for Agent Based on Improved Genetic Algorithm[J]. Computer Simulation, 2014, 31(6): 357-361. (in Chinese) DOI:10.3969/j.issn.1006-9348.2014.06.080 |
[12] |
康冰, 王曦辉, 刘富. 基于改进蚁群算法的搜索机器人路径规划[J]. 吉林大学学报, 2014, 44(4): 1062-1068.
KANG Bing, WANG Xihui, LIU Fu. Path Planning of Searching Robot Based on Improved Ant Colony Algorithm[J]. Journal of Jilin University, 2014, 44(4): 1062-1068. (in Chinese) |
[13] |
刘洋, 章卫国, 李广文, 史静平. 一种三维环境中的无人机多路径规划方法[J]. 西北工业大学学报, 2014, 32(3): 412-416.
LIU Yang, ZHANG Weiguo, LI Guangwen, Shi Jingping. A Multi-Path Planning Method for Unmanned Aerial Vehicle(UAV) in 3D Environment[J]. Journal of Northwestern Polytechnical University, 2014, 32(3): 412-416. (in Chinese) |
[14] | ZHAO Q, ZHEN Z, CHEN G, et al. Path Planning of UAVs Formation Based on Improved Ant Colony Optimization Algorithm[C]//Proceedings of IEEE Conference on Guidance, Navigation and Control, 2015: 1549-1552 |
[15] |
赖智铭, 郭躬德. 基于自适应阈值蚁群算法的路径规划算法[J]. 计算机系统应用, 2014, 23(2): 113-118.
LAI Zhiming, GUO Gongde. Ant Colony Optimization Based on Self-Adaption Threshold for Path Planning[J]. Computer System Applications, 2014, 23(2): 113-118. (in Chinese) DOI:10.3969/j.issn.1003-3254.2014.02.019 |
[16] |
李擎, 张超, 陈鹏, 等. 一种基于粒子群参数优化的改进蚁群算法及其应用[J]. 控制与决策, 2013, 28(6): 873-879.
LI Qing, ZHANG Chao, CHEN Peng, et al. Improved Ant Colony Optimization Algorithm Based on Particle Swarm Optimization[J]. Control and Decision, 2013, 28(6): 873-879. (in Chinese) |
[17] |
方群, 徐青. 基于改进粒子群算法的无人机三维航迹规划[J]. 西北工业大学学报, 2017, 35(1): 66-73.
FANG Qun, XU Qing. 3D Route Planning for UAV Based on Improved PSO Algorithem[J]. Journal of Northwestern Polytechnical University, 2017, 35(1): 66-73. (in Chinese) |
[18] |
尹高扬, 周绍磊, 吴青坡. 无人机快速三维航迹规划算法[J]. 西北工业大学学报, 2016, 34(4): 564-570.
YING Gaoyang, ZHOU Shaolei, WU Qingpo. Efficient Path Planning Algorithm in Three Dimensions for UAV[J]. Journal of Northwestern Polytechnical University, 2016, 34(4): 564-570. (in Chinese) |
2. School of Automation, Northwestern Polytechnical University, Xi'an 710072, China