基于改进粒子群算法的UAV航迹规划方法

1212

(1.卫星导航系统与装备技术国家重点实验室，石家庄 050081；2.中国电子科技集团公司 第五十四研究所，石家庄 050081)

0 引言

无人机具有低成本、操作简单、无人员伤亡等特点，正在成为未来信息化的重要基础平台。随着近年来无人机越来越广泛的应用，无人机集群协同编队飞行已经成为了当前研究的热点。无人机集群航迹规划是实现集群编队飞行执行任务的关键技术之一，其是指考虑飞行地形、气候、威胁等因素，以及飞机自身平台性能约束，为无人机集群制定从初始位置到目标位置的最优飞行路径。

解决无人机集群航迹规划问题的关键在于优化算法设计，当前国内外对无人机航迹规划算法设计进行了一些尝试与突破，但仍存在较大的局限性，主要问题在于算法计算复杂度、求解精度、搜索时间难以平衡同时满足任务要求，因此设计具有计算快、精度高、容错率大等特点的航迹规划算法是未来发展趋势。

解决航迹规划问题的算法一般包括传统优化算法和各类进化算法，其中进化算法又以群智能算法为重点研究对象。粒子群优化算法就是一类典型的群智能算法，也是本文重点研究对象。粒子群算法(particle swarm optimization，PSO)是在1995年由美国社会心理学博士Kennedy和电子工程学博士 Eberhart共同提出的一种优化算法，是一个基于迭代方法的随机搜索与最优化处理过程[1]。和遗传算法相似，粒子群算法也是通过迭代寻找最优解，但它没有遗传算法中“交叉”和“变异”的操作，因此规则更加简单。在粒子群优化算法中，目标被看作是所优化问题的可能解，个体被看作没有质量和体积的粒子，每个粒子的运动方向和速度都受到自己和群体的历史状态信息的双重影响，利用群体中个体间的信息共享和协作，引导群体朝着更好的解的方向运动，从而完成整个粒子群在解空间中搜索最优解[2]。

1 经典粒子群算法

在D维的解空间上，粒子群的速度更新和位置更新如下两式所示，其中d表示位置或速度的第d维。

通常用Ns表示粒子群种群规模，记f(xi)为所优化问题的评价函数，粒子位置的优劣是依靠f(xi)的值来决定的。得到粒子新的位置后，可以求出对应的f(xi)，并更新粒子的历史最优位置信息pBesti和种群的历史最优位置信息gBesti，继续迭代进行下一步操作。

图1是粒子群优化算法求解优化问题的示意图，搜索空间是二维，全局最优解在黑点处，粒子从初始位置更新到了更新位置。其中v1是全局历史最优解引起的粒子的速度，v2是粒子历史最优解引起的速度，v3是粒子原来具有的速度。粒子最终的速度v由v1、v2和v3共同决定，使得粒子从初始位置到达更新位置，接下来以同样的方式继续更新速度和位置，粒子会逐渐接近全局最优解位置[4]。

图1 粒子群优化算法求解优化问题的示意图

粒子群算法的优点包括：通用性较强、搜索能力全面、算法原理简单等等。但是标准粒子群算法的缺点也很明显，比如在以全局最优值为搜索目标时局部搜索能力较差、容易早熟陷入局部最优，无法保证一定能够搜索到全局最优值等等[5]。

2 改进粒子群算法在航迹规划中的应用

由于传统粒子群优化算法应用在集群航迹规划中有早熟收敛过快，后期容易陷入局部最优，搜索到的航迹点轨迹不一定是最优解的问题，而单纯增加种群数量和节点个数则会导致计算量大幅度增加[6]，故本文采用整体粒子群航迹规划和节点间粒子群航迹再规划相结合的策略，可以更好地满足航迹规划从快速全局搜索过渡到精确局部搜索的要求。

整体粒子群航迹规划。建立无人机航迹规划模型，考虑无人机各项约束条件、优化指标等信息，设定粒子群种群数量、节点数目、迭代次数、学习因子、惯性权重等参数，快速规划得出无人机由当前位置到目标位置的最优飞行航迹。

节点间粒子群航迹再规划。在整体粒子群航迹规划之后，对于每两个相邻的节点间的航迹，先利用改进评价函数判断其可靠性，若满足指标则保留，若不满足指标，则选取该相邻两个节点作为初始点和目标点，考虑无人机各种约束信息，改进位置速度更新公式使其满足局部搜索要求，进行粒子群航迹的再规划。

利用改进粒子群算法进行航迹规划流程大致如图2所示。

图2 航迹规划流程图

对于整体粒子群航迹规划，首先进行航迹规划模型建立，包括环境建模以及确定约束条件和评价函数[7-8]。

航迹规划的环境模型包括基准地形模型、障碍区域以及威胁区域3个部分。基准地形建模设置飞行区域为200 m×200 m×100 m的直角坐标区域；障碍区域建模采用山峰模型，其数学描述为：

式中，hi表示第i座山的高度，(xi,yi)为山峰的地理中心坐标，xsi,ysi分别表示山峰在x轴和y轴方向的坡度向量，(x,y)代表地形中每个点投影到平面的点坐标，z(x,y)表示地形中每个点的高度；威胁区域一般指电磁干扰区域、禁飞区域以及敌方探测区域[9]等，可采用半球形模型对威胁区域建模，其数学描述为：

式中，Wi(x,y,z)表示第i个威胁区域；(xi,yi,0)表示威胁区域的中心；ri表示威胁区域半径。

约束条件一般包括以下几项[10-11]：

1)航迹长度Lp：无人机一次任务的总飞行路程。设第i个节点与下一个节点间的距离为li，两个节点的坐标分别为(xi,yi,zi)，(xi+1,yi+1,zi+1)，则有:

2)剩余飞行时间tp：无人机在执行一次任务过程中，最大飞行时间与已飞行时间的差值；

3)最低飞行高度h：无人机在飞行中与地形之间允许的最短距离，h太小会增加无人机与地面碰撞的概率；

还有很多无人机集群约束和环境约束条件，例如无人机数量约束、节点间距约束、大气威胁等[12]。本文选择航迹长度、剩余飞行时间和最低飞行高度来组成整体航迹评价函数，如下式所示:

式中,N为节点总数，Li为第i个节点与前一个节点间的距离；ti为到第i个节点的剩余时间；Ti为第i个节点处的高度威胁值。φ1、φ2和φ3为0～1的权重系数，通过调整它们的大小来改变各项约束条件对整体航迹评价函数的影响。

对于节点间粒子群航迹再规划，其要求航迹搜索的解更加精确，所得到的航迹结果更加圆滑，故可以采用改进航迹评价函数和速度位置更新公式的方法增强算法局部搜索能力。

与整体粒子群航迹规划评价函数不同，节点间航迹的评价函数应当更加关注无人机自身飞行条件约束情况[13]。本文选择最小转弯角、最大上升角和最大下降角来组成节点间航迹评价函数，如下式所示:

fi=∂1θi+∂2φi+∂3αi，i=1,…,N-1

式中,N为节点总数；θi为第i个节点间距中的最小转弯角度；φi为第i个节点间距中的最大上升角度，αi为第i个节点间距中的最大下降角度。∂1、∂2和∂3为0～1的权值。通过该评价函数判断各个节点间的航迹是否符合要求，满足要求的则保留，不满足要求的则利用改进的粒子群更新公式进行节点间航迹再规划。

对于节点间粒子群航迹规划的更新公式的改进主要在于合理调节算法参数上。由于惯性权重ω的取值对算法的搜索性能有很大的影响，较大的惯性权重可加快算法搜索速度，较小的惯性权重可增强算法搜索能力。但是单纯设计成线性递减的惯性权重在迭代后期不能很好地满足精确搜索的要求，而节点间粒子群航迹规划重点就在于迭代后期的精确搜索，故本文设计了一种针对局部精确搜索的惯性权重调整方法。具体的调整公式为：

式中，ωmax和ωmin为惯性权重的最大值和最小值，t为已迭代次数，T为最大迭代次数。λ1和λ2表示算法前期所占的比例，范围为0≤λ1<λ2<1。λ1和λ2的取值是由规划问题的复杂程度、要求的搜索精度等因素共同决定的[14]。由于节点间粒子群搜索前已经由整体粒子群搜索规划好大致航迹，所以在实验中λ1应当尽可能地取小，必要时可取为0。这种分段式调整策略使得在节点间航迹规划的初期有一个短暂的快速搜索阶段，防止在算法初期就陷入局部搜索停滞不前的情况；在算法前中期搜索速度快速下降，搜索精度快速大幅度上升，并在算法后期维持最高的搜索精度，有助于节点间航迹规划问题的解决[15-16]。

3 仿真与分析

针对本文提出的基于改进粒子群算法的航迹规划方法，利用Matlab R2017a进行仿真，并与传统和其他粒子群航迹规划方法进行对比分析。

建立环境模型：设定2000 m×2000 m×1000 m的直角坐标区域，给定半球形威胁模型、山峰模型的中心及半径。环境建模如图3所示。

图3 环境建模仿真

设置整体航迹规划粒子群算法参数：设定无人机数量为12，种群数量N=50，群体最大迭代次数T=100，航迹节点数目取为30，最大迭代时间tmax取1000。学习因子取C1=C2=2，惯性权重ω取0.7。整体粒子群航迹规划评价函数中φ1、φ2和φ3分别取0.5,0.3,0.2。整体粒子群航迹规划仿真结果如图4所示。

图4 整体粒子群航迹规划图

继续进行节点间航迹规划。利用节点间航迹规划评价函数判断各节点航迹合理性，∂1、∂2和∂3分别取0.4,0.3,0.3。设置节点间航迹规划粒子群算法参数：种群数量改为100，航迹节点数目改为10。惯性权重ω按照调整公式设置，其中λ1和λ2分别取为0.1和0.3，ωmax和ωmin取为0.9和0.4。其余参数不变。

12架无人机航迹规划结果如图5所示。可见无人机编队形成圆滑航迹，绕过障碍和山峰飞行并在目的地形成大致圆形构型。

图5 最终航迹规划结果图

表1 算法性能对比

可以看出，本文提出的改进算法对比传统粒子群航迹规划算法(BPSO)，在整体航迹规划评价值相差不多的情况下，航迹规划时间明显缩短；对比惯性权重线性变化的粒子群算法(LPSO)，整体航迹规划评价值和时间相近，而节点间航迹规划评价平均值明显更大，航迹规划时间也明显缩短，因此可以很好地满足无人机集群航迹规划搜索速度和精度的要求。但是，无论是LPSO还是IPSO，两部分航迹规划的时间总和都要比一次航迹规划时间要多，虽然很大程度上提高了解的精度，却在某些方面不能满足航迹规划实时性的需要，因此也为后续的研究指出了方向。

4 结束语

本文提出了一种基于改进粒子群算法的无人机航迹规划策略，相较于标准粒子群算法和传统航迹规划策略具有如下优点：

1)算法适应性强。对于惯性权重ω的分段式调整简单快捷，使得算法既满足了航迹规划前期的快速搜索要求又满足了后期高搜索精度要求，对于评价函数的两种设计使得不同阶段的航迹规划更加有针对性。

2)航迹规划策略灵活。采用的整体航迹规划和节点间航迹规划相结合的策略确保了在计算资源的高效利用下，快速搜索到满足要求的精确航迹。

该算法策略可以很好地满足航迹规划的需求，但仍存在一些不足之处，比如应对突发威胁时缺乏在线实时航迹规划手段，集中式计算负担过大有时不能满足需要等等。后续将在算法自主实时性方面寻求突破，重点关注在线实时航迹规划方法和分布式算法架构，完善本文所提出的无人机集群航迹规划策略。