宋 宇, 王志明

(长春工业大学 计算机科学与工程学院， 吉林 长春 130012)

0 引 言

随着科学技术的不断发展，无人机的应用领域不断扩大，从地质勘探到无人机快递，无人机路径规划都是一项重要的技术指标。

无人机路径规划指的是寻找一条或几条从给定起点到给定终点的最优路径，路径的优劣程度一般由路径长度，所经过的威胁区域如雷达威胁区的路径长度等决定的。对路径规划的研究开始于20世纪60年代，期间国内外学者提出了大量的路径规划方法，包括蚁群算法[1]、粒子群算法[2]、A*算法、Laguerre图法[3]、PRM算法、人工势场法等。文献[1]采用蚁群算法对路径规划中的参数设置进行了研究，文献[2]提出了基于线性惯性权重与自然选择算法的优化粒子群算法的无人机航迹规划，文献[3]提出了一种基于Delaunay图的Laguerre图构造算法,证明了当两个威胁源不相交时，Laguerre图生成的备选航路必然从它们之间的空隙内穿过，文献[4]提出一种障碍物边界点设置与平滑算法，文献[5]利用距离传感器采用模糊控制的方法进行了路径规划研究。对于三维路径规划问题，目前提出的各算法在不同的应用场景中各有优劣，例如蚁群算法与粒子群算法均易陷入局部最优解，A*算法与PRM算法不能保证找到的路径为全局最优路径，人工势场法存在目标点不可达及障碍物边界附近振荡的问题。WDO算法[6]是一种新的自然启发式基于大气运动的全局优化算法，模拟无限小的空气块遵循牛顿第二定律运动规律优化目标函数，文中采用WDO算法对无人机进行路径规划方法研究[7]。

1 粒子群算法

粒子群优化算法由Kennedy和Eberhart在1995年提出，启发来自对鸟类捕食问题的研究，每个粒子都代表一个可能解，通过个体最优与全体最优不断迭代找到待优化函数的最优解。其速度更新方式如下：

(1)

式中:ω，c1，c2----权重系数;

r1，r2----随机数;

位置更新方程如下：

(2)

1)初始化粒子种群数量，最大迭代次数，系数ω，c1，c2，速度最大值umax，位置边界值，适应度函数。

2)任意给定每个粒子的位置与速度值。

3)依次计算每个粒子的适应度值(每个可能解的适应度值)，得到第一代粒子的局部最优粒子与全局最优粒子并记录之。

4)更新所有粒子的速度并检查速度值是否越界，若越界，规定为±umax。

5)更新所有粒子的位置并检查位置是否越界。

6)依次计算每个粒子的适应度值(每个可能解的适应度值)，得到当前代粒子的局部最优粒子与全局最优粒子并记录之。比较当前最优粒子的适应度值是否优于之前记录的最优适应度值，若是，更新局部最优粒子与全局最优粒子;若否，全局最优解与局部最优解不变。

7)检查是否达到最大迭代次数，若未达到,则跳到4);若达到，算法结束，最后一次迭代中粒子的全局最优位置记为问题的最优解。

2 WDO算法

WDO优化算法是一种基于种群的迭代全局优化算法，启发来自大气中风的运动，空气块的每一个位置代表一个可能解，空气块的每一个速度代表可能解的变化量。每个空气块的速度更新公式为:

(3)

其中，α为对前一个解的保留系数;等式右端第一项类似于大气中空气块受到摩擦力的影响;右端第二项表示空气块速度变化中始终有一个速度分量指向坐标原点的方向，类似于空气块受到的重力影响，此项的加入有效地避免了空气块的位置陷于边界值;右端第三项中的i为按压力值(适应度函数)排列当前所有空气块所得的排列序号，当i=1时压力值最小(当前最优解)，该项表示，空气块位置越靠近当前最优解(i与1的差的绝对值越小),速度的变化越小;右端第四项表示随机选择的其他维速度对当前维速度的影响，i值越小，影响越大，类似于由于地球自转，空气块受到的Coriolis力，此随机项的加入，增强了算法全局搜索能力。空气块位置更新公式为：

xnew=xcur+(unewΔt)

(4)

式中:xnew----更新后的位置;

xcur----更新前的位置;

Δt----通常取为1。

为了防止空气块速度过大，导致空气块跳过最优位置，通常事先规定一个速度最大值umax，并规定:

(5)

当unew=±umax时，空气块位置会受到速度更新公式右端第二项的影响而被拉回可能解的寻优空间。WDO算法计算步骤如下：

1)初始化空气块种群数量，最大迭代次数，系数α，g，RT，c，速度最大值umax，位置边界值，空气压力函数(适应度函数)。

2)任意给定每个空气块的位置与速度值。

3)依次计算每个空气块的压力值(每个可能解的适应度值)，按压力值大小排列各空气块。

4)更新所有空气块的速度,并检查速度值是否越界，若越界，规定为±umax。

5)更新所有空气块的位置,并检查位置是否越界。

6)检查是否达到最大迭代次数，若未达到,则跳到3);若达到，算法结束，最后一次迭代中空气块的位置记为最优解。

3 基于WDO的无人机三维路径规划

(6)

其中g可定义为一个与迭代次数成正比例关系的函数值。随着迭代次数的增加,趋向最优粒子的速度会相对减小，进一步增强了发现最优解的潜力。

另外，为了进一步增加待选空气块在最优解附近的寻优能力，可将式(3)改为:

(7)

其中q为从1到粒子总数的一个随机值，增加最后一项后，趋近最优解的速度增加了一个趋向别的粒子的速度分量，增强了发现最优解的潜力。

文中采用WDO进行三维路径规划,步骤如下：

1)初始化最大迭代次数500，令α=0.4，g=0.2,RT=3,c=0.4,中间点的个数为10，位置边界值±10，速度边界值±3，适应度函数定义为从起点到中间点再到终点的距离之和，若某中间点落在障碍物(文中采用球体来代表威胁空间或障碍物)之内，则此适应度函数值加5。

2)任意给定中间点的位置与速度值。

3)给所有中间点的x坐标赋值，令x=((x1-x0)/n)*i,令与之相应的速度值为0。

4)依次计算每个可能解的适应度值，按适应度值大小排列各空气块(可能解)，记录当前最优解。

5)令g=gmin+(gmax-gmin)*ij/100,其中ij为当前迭代次数。按照式(6)依次更新所有空气块的速度并检查速度值是否越界，若越界，规定为±3max。

6)令更新后的速度值中对应于x坐标的速度值等于0。

7)更新所有空气块的位置并检查位置是否越界，若越界，规定为±10。

8)检查是否达到最大迭代次数，若未达到,则跳到4);若达到，算法结束，最后一次迭代中空气块的位置记为最优解。

4 仿真与结果分析

在Matlab2014a环境下对起点为(-5，-8，-9),终点为(7，7，7)的路径规划过程进行了仿真，威胁区域表示圆心坐标为(3，3，3),(2，-2，-3)，半径为2的2个球体，最大迭代次数为500，空气块种群规模为30，中间点个数为10，gmin=6.1,gmax=7.4。采用粒子群算法与WDO算法的仿真结果500代后得出的路径如图1所示。

图1 粒子群算法500代后得出的路径

粒子群算法最短路径下降曲线如图2所示。

图2 粒子群算法最短路径下降曲线

从仿真结果可以看出，经500次迭代后，适应度下降曲线中较长的横线表明基本粒子群算法易陷入局部最优。

WDO算法500次迭代后生成的最终路径如图3所示。

图3 WDO算法500代后得出的路径

适应度函数值与迭代次数的关系曲线如图4所示。

图4 WDO算法最短路径下降曲线

从图中可以看出，WDO算法收敛速度较快，路径较合理。

采用式(4)的速度更新策略得出的路径规划图如图5所示。

采用式(6)的速度更新策略得出的最短路径随着迭代次数的下降曲线如图6所示。

由图6可知，采用式(6)的速度更新策略得出的解更优。

采用式(7)的速度更新策略得出的路径规划图如图7所示。

采用式(7)的速度更新策略得出的最短路径随着迭代次数的下降曲线如图8所示。

图5 式(6)速度更新策略500代后得出的路径

图6 式(6)更新策略最短路径下降曲线

图7 式(7)速度更新策略500代后得出的路径

图8 式(7)更新策略最短路径下降曲线

由图8可知，采用式(7)速度更新策略得出的解更优。

5 结 语

将WDO算法用于无人机三维路径规划，成功地在Matlab环境下进行了仿真，并与粒子群算法进行了比较，可以看出前者生成的路径明显更合理，得出了WDO算法在路径规划问题中相对有效性的结论。

[1] 史恩秀,陈敏敏,李俊,等.基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报,2014,45(6):53-57.

[2] 张建南,刘以安,王刚.基于优化粒子群算法的无人机航路规划[J].传感器与微系统,2017,36(3):58-61.

[3] 王树磊,魏瑞轩,沈东,等.面向航路规划的Laguerre图构造算法[J].系统工程与电子技术,2013,35(3):552-556.

[4] Han J, Seo Y. Mobile robot path planning with surrounding point set and path improvement[J]. Applied Soft Computing,2017,57:35-47.

[5] Zhao R, Lee H K. Fuzzy-based path planning for multiple mobile robots in unknown dynamic environment[J]. Journal of Electrical Engineering & Technology,2017,12(2):918-925.

[6] Bayraktar Z, Komurcu M, Bossard J A, et al. The wind driven optimization technique and its application in electromagnetics[J]. IEEE Transactions on Antennas & Propagation,2013,61(5):2745-2757.

[7] 代君,任淑红,王晓璐.小型无人机姿态航向参考系统信息融合算法[J].长春工业大学学报,2016,37(1):52-55.