基于改进粒子群算法的无人机路径规划*

王翼虎，王思明

(兰州交通大学自动化与电气工程学院,甘肃 兰州 730070)

1 引言

近年来，无人机技术发展迅猛，路径规划问题是无人机自动控制的关键问题之一。目前路径规划的常用方法有粒子群PSO(Particle Swarm Optimization)算法、A*算法[1]、蚁群算法[2,3]、人工势场法[4]等。粒子群算法应用于无人机路径规划时，易于实现且收敛速度快，但是由于其进行路径规划这类高维复杂问题的优化时极易出现早熟现象，这严重限制了算法的实际应用。

针对粒子群算法的问题，国内外学者进行了诸多尝试。文献[5,6]采用自适应原理调整参数，在算法的不同时期采用不同的惯性权重和学习因子，能够在一定程度上改善粒子群算法的早熟收敛，但是对参数的选择需要更多的数据实验，同时参数对于环境规模的适应性不足，算法灵活性不高。文献[7]提出一种自适应混沌粒子群优化算法并应用于三维路径规划，采用自适应logistic混沌映射优化全局最优粒子的方法引导种群跳出局部最优，该算法可以有效地使种群快速跳出局部极值点，但是对于算法总体寻优效率并没有提升。文献[8]提出一种基于粒子群优化和极坐标机器人路径规划方法，用概率论方法分析了该方法的收敛性，并分析了参数选择对收敛性的影响，对于粒子群路径规划参数选择具有一定指导意义，但是该方法本身规划质量和效率并不高。文献[9]在粒子群算法中引入模拟退火算法，使得种群能够跳出局部极值点，提高了粒子群算法的全局寻优能力，但在局部搜索能力上仍存在局限性。

本文根据无人机路径规划任务建立三维高程环境模型，构造基于路径长度、障碍危险以及高程代价的适应度函数。针对传统PSO算法的缺陷，本文在传统粒子群算法中引入BFO(Bacteria Foraging Optimization)算法的趋化算子和迁徙算子进行改进，提出了PSO-BFO混合算法，最后通过Matlab对2种算法进行三维全局路径规划仿真，验证了改进算法的有效性。

2 无人机路径规划环境建模

本文研究在已知环境下的无人机的全局路径规划，建立模拟城市环境的三维高程数字地图模型。考虑无人机飞行安全裕度后用圆柱体模拟建筑物，用半球体模拟其他树木等障碍及禁飞区，其三维高程数学模型表示为[10]：

z1(x,y)=hi,r

z(x,y)=max(z1(x,y),z2(x,y))

(1)

3 适应度函数

在采用粒子群算法进行路径规划时，适应度函数用以评价生成路径的优劣程度，也是算法种群迭代进化的依据，适应度函数的优劣决定着算法执行的效率与质量。为了更好地进行路径质量判断，本文综合考虑路径的长度代价、障碍危险代价以及路径平滑度几个方面来构造适应度函数。假设有C条路径，每条路径由n个点组成，环境中共存在g个球形和柱形障碍。

3.1 路径长度代价

路径长度是评价路径优劣最重要的指标之一，路径越短，其耗时和耗能都越少。引入路径长度代价如下：

(2)

其中，Tm代表第m,m∈{1,2,…,M}条路径中所有相邻节点之间的距离总和，(xj,yj,zj)为路径中第j个节点的坐标。

3.2 障碍危险代价

则第m条路径的障碍威胁代价为：

(3)

其中，rk为球形障碍或柱形障碍的半径。

3.3 航迹高程代价

无人机的稳定飞行高度也是无人机航迹规划过程中的重要环节。对于大多数飞行器来说，飞行高度不应该发生太大的变化。稳定飞行高度有助于减轻控制系统的负担，节省更多的燃料。故引入航迹高程代价：

(4)

高程代价为航迹每个相邻航迹点高度差之和，其中hj表示路径节点j的高度。

综合Tm、danm和Cm得到路径适应度函数为：

f=w1·Tm+w2·danm+w3Cm

(5)

其中，w1、w2和w3为[0,1]内的权重系数，用来灵活配置Tm、danm和Cm之间的关系。

4 改进粒子群算法

粒子群算法用搜索空间中的点模拟自然鸟群中个体，将其觅食行为的过程类比为可行解变换优化的迭代过程。其搜索过程基本不利用外部信息，仅以适应度函数作为进化依据，每个个体根据个体极值和全局极值接近最优解。本文以粒子群算法为基础进行迭代寻优，并且引入细菌觅食算法对粒子群算法进行改进。

4.1 粒子群算法

假设存在一个规模为M的粒子种群，具有N维空间搜索区域，记为X=[x1,…,xi,…,xM]T，其中第i个粒子的位置表示为xi=[xi1,xi2,…,xiN]T，其速度即粒子在每次迭代中移动的距离表示为vi=[vi1,vi2,…,viN]T,粒子i当前经过的适应度最佳的位置即个体极值表示为Pi=[pi1,pi2,…,piN]T，用Pg=[pg1,pg2,…,pgN]T表示整个种群搜索到的适应度最佳的位置即全局极值。优化问题的可行解即为优化粒子的位置。粒子每次迭代按式(6)更新其位置与速度[11]。

(6)

4.2 细菌觅食算法

细菌觅食算法BFO是群体智能算法的一种，模拟细菌种群觅食行为进行建模，通过迭代来产生最优解。在BFO算法中，算法寻优由趋化、繁殖和迁移3个操作的三层嵌套循环构成，最内层是趋化，中间层是繁殖，最外层是迁移，下面对以上操作分别做简要介绍[12]。

(1)趋化操作。

细菌趋化算子的操作描述为:细菌首先向随机方向游走一个步长单位的距离，如式(7)所示；然后计算该位置适应度，如果新位置的适应度优于上一个位置的，则沿翻转方向再前进单位步长，若适应度劣于该细菌所在上一个位置的，或者达到最大游动次数则退出该次趋化操作。

P(i,j+1,k,l)=P(i,j,k,l)+C(i)φ(i)

(7)

其中，P(i,j+1,k,l)为细菌位置，i为细菌的序号，j，k，l分别为趋化、复制、迁徙操作次数，C(i)为细菌执行一次趋化操作向前游动的单位步长，φ(i)表示细菌随机翻转中生成的随机单位方向向量。

(2)繁殖操作。

在细菌完成一定次数的趋化过程后，进行繁殖操作，定义细菌的繁殖能量为细菌在整个趋化过程内的适应度之和，高繁殖能量的细菌获得繁殖机会，低繁殖能量的则被淘汰。

设淘汰掉的细菌数量为Sr=S/2,将细菌按照繁殖能量高低排序，然后淘汰低能量的Sr个细菌，剩余细菌进行自我复制分裂出与自己完全相同的新个体，取代被淘汰的个体，保持细菌种群大小不变。

(3)迁徙操作。

完成种群的繁殖操作后，细菌个体以一个固定概率Ped进行迁移，对任何细菌个体随机生成一个[0,1]的随机数Rand。若Rand

4.3 PSO-BFO混合算法

粒子群算法早期搜索速度较快，但同时也带来一个问题，粒子搜索过程中PSO算法会因为粒子速度过大而错过最优解[13]，而且由于所有粒子在“跟随”思想的引导下，都向着一个方向飞行，导致粒子趋向同一化，丧失种群多样性，导致算法陷入局部最优，且算法在后期缺乏跳出局部最优的能力。

针对以上问题，本文在粒子群算法中引入BFO的趋化和迁徙算子。BFO算法的趋化过程实质就是细菌在解空间中搜索其所在位置的邻域，由适应度函数决定其搜索方向。趋化过程的引入将增强PSO的局部搜索能力，改善PSO中粒子在搜索过程中由于速度过大而错过最优解区域的问题。而引入迁徙算子会在粒子群陷入局部最优时使得算法有跳出局部最优的能力，将有利于算法跳出局部最优，但是固定概率的迁移算子会使部分优秀解流失，降低寻优速度，故将粒子按照适应度排序，只赋予低适应度的粒子迁移概率Ped。

PSO-BFO算法的具体步骤如下所示：

(1)初始化环境信息，确定规划空间边界为R=(xmax-xmin,ymax-ymin,zmax-zmin)，提取起始点S(xstart,ystart,zstart)，目标点G(xend,yend,zend)。

(2)设置种群大小pop_size及粒子大小part_size，最大迭代次数max_gen，粒子最大速度vmax=0.1R，初始化粒子的位置和速度如式(8)和式(9)所示。

(8)

(9)

(3)计算粒子初始适应度值f0，将粒子当前位置设为个体极值pbest0，将所有粒子中适应度最好的粒子位置设为全局极值gbest0，设置惯性权重wmax，wmin和学习因子c1，c2，迭代次数计数k=1。

(4)根据w=wmax-(wmax-wmin)(k/max_gen)线性递减策略更新惯性权重，根据式(6)更新粒子的速度和位置，计算个体适应度值fk，如果获得更优的个体极值和全局极值，则更新个体极值pbestk和全局极值gbestk。在全局极值获得更新时，加入趋化算子进行局部寻优，局部寻优流程如图1所示。

σ2计算方法如下所示：

(10)

Figure 1 Flow chart of chemotaxis operator图1 趋化算子流程图

(6)判断是否满足停止计算条件或达到最大迭代次数，是则输出规划结果；否则返回步骤(4)且k=k+1。

5 实验分析

实验在三维高程地图模型下，分别用PSO算法与PSO-BFO混合算法进行无人机路径规划仿真。实验所用电脑配置为Windows 7 64位系统，8 GB运行内存，2.5 GHz频率CPU，程序在Matlab平台运行。路径起终点以及规划环境参数设置如表1所示，粒子群算法参数设置如表2所示，混合算法中粒子群算法参数不变，加入细菌觅食算子，游动步长C=0.05|R|，最大趋化次数Nc=30，迁移概率Ped=0.25。

Table 1 Parameter settings for planning tasks 表1 规划任务参数设置

Table 2 Parameter setting of particle swarm algorithm表2 粒子群算法参数设置

为验证混合算法在三维路径规划中的有效性，将PSO-BFO混合算法与基本粒子群算法在相同的环境模型中进行对比实验。

图2～图4给出基本粒子群算法和本文混合算法的规划结果及其俯视图和正视图，图5给出了2种算法的最优适应度曲线。从图2可以看出，传统PSO算法和混合算法均能在三维环境中生成一条可行的全局路径，但是由图3和图4可以看出，本文混合算法规划结果的路径长度和平滑度都要优于传统PSO算法的，且由图5最优适应度曲线可以看出，混合算法由于引入趋化算子增强了其局部寻优能力，避免其跳过全局最优解，加快了收敛速度，适应度呈直线下降，适应度优于传统粒子群算法，且由于迁徙算子的引入使得算法陷入局部最优而停滞时也能够跳出局部最优，恢复寻优能力。

Figure 2 Path planning results of PSO algorithm and hybrid algorithm图2 粒子群算法和混合算法路径规划结果

Figure 3 Top view of planning results of PSO algorithm and hybrid algorithm图3 粒子群算法和混合算法规划结果俯视图

Figure 4 Front view of planning results of PSO algorithm and hybrid algorithm图4 粒子群算法和混合算法规划结果正视图

图6给出2种算法重复40次运行的适应度值，表3总结了重复实验中2种算法获得的最优适应度，以及多次运行的适应度平均值及其标准差。从图6及表3可以看出，传统PSO算法在进行路径规划时，规划路径适应度最优值及平均值均较差，且在重复运行中，规划结果的标准差远大于改进算法的，规划的稳定性差，这也使得其很难实际应用。而混合算法的多次运行结果最优值、平均值和标准差均大幅优于传统PSO算法的，说明混合算法不但增强了算法寻优能力，而且算法的稳定性也得到很大的提升。

Figure 5 Optimal fitness curves of PSO algorithm and hybrid algorithm图5 粒子群算法和混合算法最优适应度曲线

Figure 6 Simulation results of algorithms running for many times图6 算法多次运行仿真结果

表4给出了算法多次运行时的平均迭代总耗时Alltime(迭代次数达到设定的最大次数的时间)、算法收敛时的迭代次数Iter(最优适应度连续100代未更新)以及耗时Time，表中数值均为平均值。由表4可以看出，从算法总耗时上看，混合算法由于引入了趋化和迁徙算子，增加了一定的计算量，所以总耗时要高于传统PSO算法的，但是从算

Table 3 Simulation data comparison of PSO algorithm and hybrid algorithm 表3 PSO算法与混合算法仿真数据对比

法收敛时间上看，混合算法从开始到收敛的迭代次数平均值要比传统PSO算法低112.3，耗时也相应更短，这说明混合算法虽然增加了一定计算量，但是加快了算法收敛速度，整体效率优于传统PSO算法。

Table 4 Efficiency comparison of PSO algorithm and hybrid algorithm表4 PSO算法和混合算法效率对比

6 结束语

在无人机的三维路径规划问题中，传统PSO算法的寻优能力无法满足需求，本文将BFO算法的趋化算子和迁徙算子引入PSO算法提高了其寻优能力。最后分别对PSO算法和改进后的混合算法进行无人机路径规划仿真并对结果进行对比分析。仿真结果表明：与传统PSO算法相比，混合算法在路径规划问题中,寻优结果最优值与平均值均大幅优于传统PSO算法的，且多次运行时结果稳定性良好，在无人机的全局路径规划中具有一定的参考性与实用性。