EDP Sciences logo
Submit your paper
Search
Menu
All issues Volume 37 / No 1 (February 2019) JNWPU, 37 1 (2019) 100-106 Full HTML
Open Access
Issue
JNWPU
Volume 37, Number 1, February 2019
Page(s) 100 - 106
DOI https://doi.org/10.1051/jnwpu/20193710100
Published online 03 April 2019

© 2019 Journal of Northwestern Polytechnical University

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

无人机航路规划是根据无人机的特定任务，考虑地形、气象等环境因素以及无人机自身的飞行性能，在满足多约束条件的前提下，为每架无人机规划出从起始点到目标点的可飞航路，实现指定性能指标最优或较优的过程。针对无人机航路规划问题，国内外学者提出了许多算法，如人工势场法[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), 引力势场函数是无人机到目标点距离的函数, 定义为:

式中，k为大于0的引力场函数的系数常量; ρ(X, Xg)=‖X-Xg‖。引力为引力势场函数的负梯度:

若障碍物的坐标为X0=(x0, y0), 无人机到障碍物的距离为ρ(X, X0)=‖X-X0‖, 则定义斥力势场函数:

式中，m为大于零的斥力场系数常量, ρ0为障碍物的最大影响范围。斥力定义为

人工势场实时处理能力强、规划速度快、运算量小, 具有良好的路径规划性能, 但当其引力与斥力大小相等方向相反时, 所有力相互抵消使合力为零, 会使无人机陷入局部极小值, 导致规划失败。

1.2 改进的人工势场法

传统的人工势场法存在易陷入局部极小值和在目标点附近易震荡的缺点, 本文针对以上缺点, 对人工势场法的斥力函数进行改进。当无人机遇到障碍物时将斥力分为两部分:

1) 当障碍物速度与无人机速度方向成锐角时, F1为斥力方向, 新增斥力F2为f向量和斥力F1向量的合向量方向, 其中f向量方向与-V方向相同, 大小与F1相等, 如图 1a)所示。

2) 当障碍物速度与无人机速度方向成钝角时, F1为斥力方向, 新增斥力F2方向为垂直斥力F1方向, 大小与F1相等。当无人机在规避动态障碍物时, 当预测出移动目标移动速度、方向及航迹后, 无人机从移动目标后方穿过能保证无人机与障碍物成功避开且规避路径最短, 如图 1b)所示。

上述改进的人工势场法通过新增与移动目标运动方向相反的斥力, 可以使无人机恰好在移动目标后方进行障碍规避, 达到减小规避路径的目的。且由于新增斥力的影响, 减小了无人机陷入局部极小值点的可能性。

thumbnail 图1

改进人工势场法斥力构成图

2 模糊逻辑算法

模糊控制是建立在人工经验基础上、不需知晓被控对象的数学模型就可以对系统实施控制的一种算法。模糊控制算法易对不确定系统或非线性系统进行控制, 对被控对象的参数变化有较强的鲁棒性。在基于模糊逻辑(fuzzy logic)的无人机路径规划算法中, 算法分为目标搜寻(goal searching behavior)、障碍规避(obstacle avoidance behavior)、数据融合(fusion weight behavior)三部分来进行。算法框架如图 2所示。

假设无人机仅在水平面内活动, 不考虑垂直方向上的运动。以无人机起始点建立坐标轴xoy, 无人机速度大小恒定, 设为V。设无人机与目标点间连线与x轴间的夹角为θ, 则其对时间的导数为其角速度ω。设无人机速度方向与x轴的夹角为α, 则定义ϕ=α-θ, 为无人机向着目标点的角度。建立无人机的数学模型为

1) 目标搜寻(goal searching behavior):

此环节保证无人机能最终向着目的地而去, 以此时刻无人机距离目的地的距离D和无人机向着目标点的角度ϕ作为输入, 通过模糊推理系统, 确定无人机向着目的地的速度VGS和角速度ωGS。

2) 障碍规避(obstacle avoidance behavior):

此环节以障碍物最左端、中心、最右端距离无人机的距离dL, dF, dR为输入, 通过模糊推理系统, 确定无人机在规避障碍物时的速度VOA和角速度ωOA;

3) 数据融合(fusion weight behavior):

此环节将目标搜寻环节和障碍规避环节所得无人机速度与角速度进行融合:

通过模糊推理系统确定融合的参数τ, 从而得出最终无人机速度与角速度。

模糊逻辑算法在多障碍物环境下寻找路径能力强, 但其对规则库的依赖性大, 若所构造规则库不够全面, 若输入量和规则不匹配, 算法性能将大大降低甚至完全不适用。

thumbnail 图2

基于模糊逻辑算法的无人机路径规划框架图

3 蚁群算法

蚁群算法(ant colony optimization, ACO)是由Macro Dorigo于1991年受蚂蚁觅食过程中的路径行为启发而提出的随机搜索全局优化方法。蚂蚁在寻找食物过程中, 会向周围环境释放信息素, 为了找到最优路径, 蚂蚁的搜索空间要尽可能大, 但是这会导致收敛速度变慢, 因此, 需要在全局最优以及收敛速度之间达到一个折中。蚂蚁们沿着释放信息素浓度最大的路线行进搜索, 最终找到食物。若有蚂蚁开辟出一条更短的路径, 由于信息素的多少与路径长度成反比, 越来越多的蚂蚁会逐渐移动到这条更优路径上, 经过一段时间后, 就可以规划出一条最短的路径。

蚁群算法在路径规划过程中, 将地图按栅格划分, 分别标记可行路径节点和障碍节点。设置蚂蚁总数为m, 每只蚂蚁按照一定的距离移动, 选择下一个可行路径节点, 并释放强度一致的信息素。从i节点到j节点, 第k只蚂蚁的转移概率为:

式中，π(t)表示蚂蚁k一步允许选择的节点, 用公式表示为:

式中，σk为蚂蚁设置的禁忌表, 用来记录蚂蚁k走过的路径。α为信息素浓度启发因子, α越大, 代表该路径是多数蚂蚁选择的路径; β为期望启发因子, 用来为蚂蚁提供选择下一个位置的依据, 蚂蚁趋向于选择距离短的路径, 此时β值较大。ηij为期望启发函数, 是位置i和位置j之间距离dij的倒数

蚂蚁在经过的路径上留下的信息素实时更新, 其更新规则为

式中，ρ为信息素挥发系数, ρ∈(0, 1)。

Δτijk为蚂蚁在t到t+n时刻留在i和j位置间的信息素。依据ant-cycle模型:

式中，Q为信息素强度; Lk为蚂蚁k所走过的路径长度; Pk(begin, end)为蚂蚁k从起点到终点所走的路径。

在ant-quantity模型中

在此定义

当迭代次数达到预先设定的值或者最佳路径不再变化时, 上述迭代过程中止。算法收敛的快慢与蚂蚁数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种算法航程比。

thumbnail 图3

基于人工势场法单机动态障碍物仿真图
thumbnail 图4

基于模糊逻辑算法的单机对动态障碍物仿真图
表1

动态障碍物2种算法最小分离距离表

表2

航程比表

4.2 静态障碍物环境下

实验设计了相同的仿真环境, 针对最小分离距离和航程比2个指标比较了上述3种算法。图 4~6分别为基于改进人工势场算法、模糊逻辑算法和基于蚁群算法的单机对多静态障碍物仿真图。表 3给出了3种算法对5个静态障碍物环的最小分离距离, 表 4比较了静态障碍物环境下3种算法航程比。3种算法均是通过改变障碍物包络大小来实现无人机尽可能远离障碍物进行规避机动, 障碍物包络的大小直接影响了无人机与障碍物的最小分离距离和航程比。蚁群算法是一种基于栅格地图的全局优化算法, 栅格划分的大小对规划路径的性能指标影响巨大, 同时, 栅格划分越多, 对算法运算量和运行时间也影响巨大。本仿真实验考虑到实验计算机运算能力有限, 在蚁群算法的仿真中通过一定比例尺缩放后, 将100×100地图划分为100个10×10的栅格, 在栅格中设置可行节点和障碍节点对路径进行寻优规划。由于栅格的粗糙性, 使得所规划路径航程比增加不少, 但从中可以看出蚁群算法所规划路径的全局最优性, 即最短。模糊逻辑算法由于其目标搜寻环节的存在, 使得无人机倾向于从多障碍物中间穿插而过, 而人工势场法需要考虑全部障碍物的影响, 在规划路径时倾向于从多障碍物边缘绕开。蚁群算法由于具有全局搜索能力, 所规划航迹一定会从障碍物中间穿过, 使其规避路径最短。

表3

静态障碍物环境下几种最小分离距离表

表4

静态障碍物环境下各算法航程比表

thumbnail 图5

基于人工势场法的单机对多静态障碍物仿真图
thumbnail 图6

基于模糊逻辑算法的单机对多静态障碍物仿真
thumbnail 图7

基于蚁群算法的单机对单静态障碍物仿真图

4.3 仿真结果分析

结合上述2种环境下的仿真实验可以得出以下结论：

1) 人工势场法运行速度快、实时性强，所规划航迹光滑，改进的人工势场法克服了易陷入局部极小值和在目标点附近震荡的缺点，使其可以很好地适用于无人机。

2) 模糊逻辑算法在系统模型未知的情况下也能适用，算法鲁棒性强。但其依赖于根据先验知识建立的规则表，规则表建立的好坏直接关系着算法的性能。在适宜的规则表下，模糊逻辑算法运算量小、运算速度快，实时性强。

3) 人工势场法和模糊逻辑算法属于局部规划算法，而蚁群算法作为全局优化算法，在栅格选取适宜的情况下，更容易为无人机规划出全局最优的路径。但蚁群算法搜索空间大时，选择随机性大，算法收敛能力差，且蚁群算法中信息素对算法的寻优能力影响重大。

5 结论

本文针对小型无人机路径规划问题进行了探讨与研究。分别设立了静态障碍物和动态障碍物环境，基于最小规避距离和航程比这2个指标，对传统人工势场算法进行了改进，减小了无人机陷入局部极小值点的可能性。将其与模糊逻辑算法和基于蚁群算法在无人机路径规划的性能上进行了比较。仿真实验结果表明，3种算法均可实现动态、静态障碍物环境下对无人机碰撞规避路径规划。3种算法各有优缺点，通过融合改进的方式，未来可以运用于现实的感知与规避系统，在全局信息未知的情况下实现最优路径规划。此外，针对实际的感知与规避系统，在设计路径规划算法时，应综合考虑无人机的处理速率约束、气动约束、环境感知约束等，针对特定应用背景下的无人机路径规划方法还有待研究。

References

  1. 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) [Article] [Google Scholar]
  2. 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) [Article] [Google Scholar]
  3. 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) [Article] [Google Scholar]
  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 [Article] [CrossRef] [Google Scholar]
  5. 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) [Article] [Google Scholar]
  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 [Article] [CrossRef] [Google Scholar]
  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 [Google Scholar]
  8. Gu Chen. Application of Improved A* Algorithm in Robot Path Planning[J]. Electronic Design Engineering, 2014(19): 96-98 (in Chinese) [Article] [Google Scholar]
  9. 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) [Article] [Google Scholar]
  10. 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) [Article][Article] [Google Scholar]
  11. 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) [Article] [Google Scholar]
  12. 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) [Article] [Google Scholar]
  13. 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) [Article] [Google Scholar]
  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 [Google Scholar]
  15. 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) [Article] [Google Scholar]
  16. 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) [Article] [Google Scholar]
  17. 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) [Article] [Google Scholar]
  18. 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) [Article] [Google Scholar]

All Tables

表1

动态障碍物2种算法最小分离距离表

In the text
表2

航程比表

In the text
表3

静态障碍物环境下几种最小分离距离表

In the text
表4

静态障碍物环境下各算法航程比表

In the text

All Figures

thumbnail 图1

改进人工势场法斥力构成图
In the text
thumbnail 图2

基于模糊逻辑算法的无人机路径规划框架图
In the text
thumbnail 图3

基于人工势场法单机动态障碍物仿真图
In the text
thumbnail 图4

基于模糊逻辑算法的单机对动态障碍物仿真图
In the text
thumbnail 图5

基于人工势场法的单机对多静态障碍物仿真图
In the text
thumbnail 图6

基于模糊逻辑算法的单机对多静态障碍物仿真
In the text
thumbnail 图7

基于蚁群算法的单机对单静态障碍物仿真图
In the text

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.