基于混沌灰狼优化的多无人机协同航路规划

吴坤，池沛，2，王英勋，2，侯琳

1.北京航空航天大学，北京 100191

2.北京航空航天大学飞行器控制一体化技术国防科技重点实验室，北京 100191

3.航空工业西安飞行自动控制研究所飞行器控制一体化技术国防科技重点实验室，陕西 西安 710065

航路规划(path planning)是根据任务需求规划出满足约束条件的飞行航路，是任务规划的关键技术之一[1]。航路规划的精度与速度能够直接对任务规划的效果产生影响。航路规划系统基本框架由环境信息、航路规划目标、机体物理约束以及航路规划器组成。根据平台规模，无人机航路规划分为单机航路规划、多机航路规划和有人/无人协同航路规划[2-3]；根据环境信息，可分为确定环境与突发威胁环境下的航路规划；根据实现功能可划分为静态航路规划与动态航路规划，其中前者为离线预规划，后者为在线实时规划。

受计算能力的约束，航路离线预规划问题由于不受计算时间约束，其更关注在可预测的已知任务环境下，如何得到评价最优的航路结果。而在线实时规划则是在已有规划结果的基础上，针对突发意外情况进行重新规划，对规划时间要求较高。

航路规划算法根据计算方法可以归纳为最优化方法与启发式搜索算法(HSA)。常用的最优化算法包括枚举法(EM)、牛顿法(NM)、梯度下降法(GD)、数学规划(MP)以及动态规划(DP)方法。

最优化方法在空间和时间上具有很强的复杂度，当规划范围增大、环境变复杂时，其求解时间与求解难度也随之急剧增加。而启发式算法是根据直观经验构造的一种搜索算法，在可接受的时间和空间复杂度下，能够得到待优化问题的一个可行的近似最优解。启发式搜索算法可进一步分为确定型搜索算法与随机型搜索算法两类。

通常确定型航路规划算法首先对规划区域进行栅格化处理，然后利用图论在地形网格的基础上搜索从起点到目标点的最短路径。确定性方法主要包括Dijkstra 算法、Floyd 算法[4]、A*算法[5-6]、人工势场法(APF)[7]以及Ⅴoronoi图法[8-9]等。随机型搜索方法通过在求解空间中进行随机采样，并按照一定的搜索规则寻找可行的较优解。典型的随机型搜索方法有粒子群算法[10]、蚁群算法[11]、快速扩展随机树(RRT)算法[12]、人工神经网络(ANN)[13]、禁忌算法(TS)[14]以及强化学习(RL)[15]等算法。

多无人机协同航路规划可以同时为多个无人机规划出多条可行航路，使每架无人机能够沿不同的航路飞行。这样生成的航路尽管对每架无人机来说不一定是最优的，但对整个多无人机系统来说是最优或次优的。参考文献[16]对于多无人机对地面区域的最小时间覆盖问题，首先采用K均值聚类对侦察区域进行划分，然后采用并行GA算法对每个簇中的航路规划问题进行计算。参考文献[17]提出一种分解策略，将多无人机协同航路规划问题分为三层框架结构，第一层采用Dubins为每架无人机规划可飞航路；第二层对多机航路的空间位置进行调整，生成避障与防撞航路；第三层对每条航路的长度进行调整，使得所有的航路长度近似相等，以实现同时到达的时间协同目的。参考文献[18]提出了三阶段航路预测算法(TPP)算法，首先利用A*算法对任务航路进行估计，然后根据预估结果为每架无人机分配代价最优的航路结果，最后利用三次B 样条差值算法实现可飞路径的规划。

多无人在协同执行任务过程中，要求多无人机应保持更加严格的占位和和攻击方向。本文以有人/无人协同执行多方向饱和攻击任务为研究背景，有人机担任主要攻击决策者，多无人机根据任务约束规划出满足要求的可行飞行航路。首先针对饱和攻击任务特点进行分析，给出了面向任务需求的航路评价指标；其次针对任务的时空约束提出了基于几何规划的航路点扩展策略；最后利用改进的灰狼优化算法对离线航路规划问题进行求解，得到满足要求的规划结果。

1 面向饱和攻击任务的问题描述

1.1 航路规划问题描述

当多无人机在协同执行任务过程中，在满足任务约束的同时，每架无人机不仅需要具有自动规避威胁和障碍物的能力，还应当具有与团队内其他成员的防撞能力。而多无人机协同航路规划技术则是解决这一问题的有效途径，它是指航路规划层根据战场的环境信息，以任务需求为导向，综合考虑无人机的机动性能、燃油消耗等约束条件，为每架无人机设计出一条不仅能够满足团队间任务协同需求，还能够使团队整体生存能力达到最大的可飞的航路[19]。

通常无人机的航路是指由一组离散点列组成的集合，即无人机U(i)(i= 1,…,n)的航路可以表示为

1.2 饱和攻击任务描述

当使用无人机对敌方目标进行打击时，通常由于目标强度的限制以及单架无人机的性能约束，如果采用一对一的作战模式不能形成对目标的有效打击。所以需要采用饱和攻击(SA)的作战策略对目标进行打击，即利用多架无人机对同一目标进行多方向多批次的攻击模式，从而实现一击必毁的作战效果。根据到达攻击位置的时间要求与空间要求，可将饱和攻击任务分为两种，即分批次攻击任务(BAAT)与多方向攻击任务(MDAT)。其中BAAT是指多架无人机在一个规定的时间间隔ΔTa内陆续到达攻击位置的贯序到达问题；而MDAT 则要求多架无人机在同一时刻从多个攻击方向对目标实施打击，MDAT即为同时到达问题。所以多无人机执行SA 任务的航路规划方法的关键问题在于如何将SA 任务中的时间与空间约束转换到单条航路规划问题中。

1.3 航路评价指标

由于航路规划的目标为在满足无人机物理性能约束与飞行任务约束的前提下生成能够对威胁进行规避的飞行路径。如图2 所示，可将无人机航路评价指标分为战术生存性、飞行约束性以及任务有效性三类。

1.3.1 战术生存性

战术生存性是指无人机对敌方威胁进行规避的能力。一般能够对无人机的飞行安全产生影响的威胁源包括：探测性威胁(如雷达)、杀伤性威胁(如地空导弹或高炮等)以及障碍物或禁飞区威胁。因为威胁程度主要与距离有关，所以在无人机航路规划问题研究中，通常将威胁区域拟合为具有威胁半径与威胁等级的圆形或矩形区域。

假设在规划空间内任意一点位置为pi(x′,y′)，则威胁源Threatj为探测性威胁时对pi的威胁程度可以表示为

式中，Rminj与Rmaxj分别为杀伤性武器的攻击近界与远界；wmax为威胁源的威胁程度。

在执行任务过程中，运行航线穿过威胁区域，但禁止飞过障碍物与禁飞区，所以障碍物与禁飞区的威胁值可以表示为

1.3.2 飞行约束性

飞行约束性是指规划的航路结果应满足无人机的物理约束，主要包括飞行稳定性以及航程约束两部分。为了使控制系统能够更加容易实现对规划航线的跟踪以及提高飞行状态的稳定性，通常需要对航路规划的航点数量、转弯角度以及相邻航点间的距离进行约束。因为无人机在导航点处进行转弯飞行，所以需要对规划的航点数量进行限制即应满足m(i)≤mmax。

1.3.3 任务有效性

式中，Ψ0为无人机的初始驶出方向；Δψ为驶出方向范围限制。

式中，Tqs与Tqt分别为多无人机起始时间间隔与到达时间间隔。当Tqs= 0 且Tqt= 0 时的饱和攻击任务即为MDAT，否则表示BAAT。ΔTS与ΔTE表示时间间隔误差，即无人机从起飞到到达目标之间的时间误差应在区间[0,ΔTS+ ΔTE]内。

假设每架无人机以vi匀速飞行，据此可将饱和攻击任务中的同时到达问题转换为航程问题，当预期的到达时间为TM时，则每架无人机的总航程Si应满足

式中，ΔSM=(ΔTS+ ΔTE)vi为航程允许的误差范围，各无人机可通过在飞行速度微调实现总航程一致的目的。

多无人机协同作战过程中，除需要对时间进行约束外，还应考虑空间中防撞问题。因为在同一规划空间内，随着无人机数量的增多，无人机间的航路容易出现时空重叠的现象，即出现碰撞现象。为了避免这一现象的发生，规划的航路在瞬时位置上应具有一定的安全间隔，即∀i,j∈{1,…,n}ijs

式中，pi(t)表示Ui在t时刻的位置；ds为无人机间的安全距离。

1.3.4 被控对象

多无人机协同航路规划中，被控对象特性建模比较关键，决定了算法性能的优劣，本文假设无人机有一个可靠的飞行控制系统，该系统有效地控制空气动力表面，以精确跟踪速度和转弯率指令，无人机的运动学方程为[20]

式中，v和ψ分别为无人机的速度和航向，u和ω分别为加速度和航向角速度。

2 基于混沌灰狼优化算法的协同规划方法

2.1 混沌灰狼优化算法

近年来，引入自然进化思想的元启发式算法，因其遵循“优胜劣汰”原则通过选择和变异来实现对问题的寻优过程，特别适合解决较大规模的优化问题。由于元启发式算法需要通过大量的迭代计算对问题进行求解，所以其不适用于航路的在线规划。但对于计算时间要求不高但更注重规划结果最优性的离线规划问题，采用元启发式算法能够获得更好的规划结果。

2.1.1 灰狼优化算法

灰狼优化(GWO)算法是Mirjalili等于2014年提出的一种元启发式优化算法[21]，通过模仿自然界中灰狼群的等级制度与捕食策略以迭代计算的方式实现对猎物（最优值)的搜索。种群中灰狼个体的位置更新满足如下公式11×D时，表示灰狼个体向猎物位置（当前全局最优解）进行移动。而Ai表示GWO 算法对猎物的最优位置进行探索。因为a从2线性递减至0，所以随机数∈[-a,a]的取值范围也逐渐减少，当算法迭代到一定程度时，个体只能在猎物周围小范围内进行移动。当迭代次数t=tmax，a=0时，则有Xi(t+1)=Ai，即实现整个算法对最优解的收敛。

GWO 算法通过式(11)实现了对猎物位置的探索与包围。然而在实际过程中猎物的位置是未知的，所以根据狼群中的等级制度，将当前适应度最优的前三个灰狼个体称为首领狼，分别用α、β与δ进行表示，剩余的灰狼个体称为ω。在GWO 算法中，α、β与δ引领整个狼群向猎物位置进行靠近。将首领狼的位置Xi,i=α,β,δ当成猎物的位置代入式(11)中，则可得到

2.1.2 混沌算子

在使用群智能算法对优化问题进行求解的过程中，首先随机生成一组初始解，并选取其中适应度最小的解作为当前状态的目标解。然后种群中的其他个体通过一定的机制与策略不断向此目标解靠近。同时个体的运动方向还会发生随机偏移以实现更优解的搜索。最后在每次迭代过程中更新适应度最小解为目标解，当达到最大迭代次数后认为目标解即寻优问题的最优解。

尽管GWO算法在收敛性、全局搜索性等方面优于其他优化方法，但仍然存在易陷入局部最优解和收敛速度慢等缺点[22]。所以本节针对此问题对GWO算法进行改进，通过引入混沌搜索策略以增加算法在解空间中的遍历性，从而提高整个算法的全局寻优能力与收敛速度。

混沌优化算法(COA)是指受混沌现象启发的一种全局性优化算法，其中混沌现象是指无固定周期的循环行为。混沌优化算法具有随机性、遍历性以及对初始条件敏感等特点。

本文从算法参数与搜索机制两方面对GWO 算法进行改进，提出了基于COA的混沌灰狼优化(CGWO)算法，以提高原算法的全局寻优能力与寻优速度。如式(13)所示，GWO 算法主要利用参数a实现了对最优解的全局搜索与局部开发能力。根据迭代次数的增加，参数a从2线性递减至0。如图4所示，当a=2时表示算法前期具有较强的全局寻优能力，随着a逐渐减少算法搜索精确解的能力逐渐加强。在算法初期即搜索到最优解附近时，利用此机制能够较快地收敛到最优解。但在初期没有搜索到最优解时，容易陷入局部最优解。所以本节将GWO算法的线性递减操作改为混沌搜索，使得整个算法能够一直具有全局搜索能力。参考文献[23]已经证明采用混沌变量能够跟线性递减变量一样使算法收敛到最优解，同时具有更快收敛速度。

因为初始值能够明显地影响群智能算法的收敛速度，所以可以利用混沌变量的遍历性增加算法初期的寻优能力。假设灰狼种群的个体数量为Np，然后根据混沌映射可以得到2 ×Np组解，并对所得解的适应度进行排列，为了防止陷入局部最优解，所以选取排序后2 ×Np组解中的奇数项作为CGWO算法的初始解。

因为粒子群等优化算法是将当前群体中的最优解看作全局最优进行寻优的，而GWO则考虑了群体间的交流，由前三个最优解共同决定的最优解的位置，当并没有考虑个体的历史最优解。所以为了增加算法的全局搜索能力，引入粒子群算法中个体最优位置概念ω(b)i,i= 1,…,Np知道个体的寻优，则在式(14)的基础上添加

在式(15)中灰狼个体的位置更新公式为X(i)(t),i=1,2,3的平均值。为了强化首领狼的领导作用，则根据适应度值确定权重系数得到灰狼个体的位置更新公式为

为了进一步加强算法的全局寻优能力，采用混沌搜索策略对式(18)的结果进一步搜索，但因为增加全局搜索能力势必会降低算法的收敛速度。为了使算法能够朝着最优解的方向发展，所以引入贪婪策略：在一定概率基础上只接受比当前适应度更好的结果。所以可以得到基于贪婪策略混沌搜索方法为：

（1）将Xi(t+ 1)映射到(0,1)区间。假设Xmin与Xmax为解空间的搜索范围，则可得映射函数为

（2）设迭代次数为Cmax，根据混沌映射进行迭代计算产生一组混沌变量ϑ(i),i= 1,…,Cmax，并通过逆映射将混沌变量转换至解空间，得到混沌解序列

式中，r3为区间[0,1]中的随机数。

2.2 基于CGWO的离线航路规划方法

航路的离线规划问题是指无人机在实际飞行前，根据任务需求预先在已知的规划空间中寻找一组满足航路评价指标的从起始点到目标点的离散点列。相比于在线规划问题，航路的离线规划主要有如下特点：

（1）威胁环境透明。在离线规划过程中，认为规划范围确定且其中的地形信息明确；同时假设敌方威胁源的位置分布、类型种类、威胁范围以及威胁等级等因素已知。

（2）威胁源慢变化。对于运动的威胁目标或任务目标，通常假设其运动规律已知或是将其运动过程的中不确定因素通过概率的形式进行描述。

（3）计算时间充足，规划算法所消耗的时间不是首要考虑因素，即离线规划是通过大量的计算时间与计算量换取高质量的规划结果。

（4）适用场景充分。基于历史案例以及场景假设，离线规划会对各种可能的情况进行充分考虑，使得规划结果具有很强的适应性。从而不仅减少了实际规划过程的不确定性，还有效地增加了任务的完成概率。

2.2.1 基于CGWO的单机航路规划方法

所以基于CGWO 算法的单机航路规划代价函数可以表示为

式中，wi为代价的权重，且有w1+w2+w3= 1。

2.2.2 基于几何规划的航路扩展法方法

执行多方向饱和攻击任务的关键是多无人机能够以预设的攻击方向进入目标区域，且从起始点到目标点间的航程相等。其中攻击方向是指无人机经过最后一个航点转向后的飞行方向，对于给定攻击目标的进入角的情况，如果按照从起始点开始搜索的方法，则预定的攻击方向为一个全局限制条件，明显增加了问题的复杂度。本节采用逆向航路节点扩展策略：从目标点出发以预设进入角方向进行逆向搜索，根据机体约束条件，寻找一条从目标点到起始点的满足任务需求的飞行航路。假设多方向饱和攻击任务的协同航程SM已经给定，则可根据椭圆第一定义建立基于几何规划的逆向节点搜索策略。

2.2.3 多机协同航路规划策略

在基于几何规划的航点扩展过程中，已将任务要求的协同航程与目标进入角作为规划条件进行考虑，但还需要考虑无人机间的防撞。多机间的防撞航路规划策略为：

首先规划出某架无人机的代价最优的航路LineA，然后将此规划结果作为约束条件对另一架无人机的航路进行规划，得到与LineA不相撞的航线LineB，最后以此类推得到满足防撞要求的n条协同航路。

式(10)给出了无人机航路间的安全间隔限制，但航路间的间隔过远会影响整体航路的协同性能，无人机航路应满足协同间隔

式中，∀i,j∈{1,…,n}。

如图6 所示，通过引入双曲正切函数可以将无人机间的间隔限制约束条件映射到[0,1]间[34]，令Δd表示缓存距离且有0 ＜Δd＜＜ds，则有

所以由式(23)、式(25)与式(35)可得多无人机协同航路的评价函数为

式中：wa+wb= 1为代价权重。

区别于单机航路规划，采用CGWO算法对多机协同航路规划问题求解的变量为辅助椭圆的随机搜索方向χ(i)j与扩展比例λ(i)j，其中i={1,…,n}表示无人机序号，j∈[1,m]为规划的航点序号。基于几何规划与CGWO 算法的多无人机协同航路规划流程如图7所示。

3 仿真分析与验证

3.1 混沌算子选取

利用混沌映射的遍历性以及与对初值的敏感性，本文所提出的混沌灰狼优化(CGWO)算法通过引入混沌映射以提高原算法的全局寻优能力。典型的混沌映射总共有12种，见表1，而不同的混沌映射将对原算法性能具有不同的改进程度。如图8所示，当初始值为x0=0.58，最大迭代次数为tmax= 100时，不同的混沌映射具有不同变化规律。根据结果可得，由于混沌映射的非周期性，使得映射结果具有较大的离散性。但不同的映射具有不同的离散程度。所以为了实现对原算法更好的改进，本节在同一仿真环境下采用不同的混沌映射，通过统计结果确定CGWO算法中所使用的混沌映射。

表1 典型的混沌映射Table 1 Typical chaotic mapping

假设CGWO 算法的种群数量Np= 30，最大迭代次数tmax= 200，维度D= 5。对于同一场景的单无人机航路规划问题，算法初始化以及变量a分别采用不同的混沌映射进行200 次运算，表2 给出了规划结果的最大值、最小值以及平均值如图9与图10分别给出了统计结果的盒图。

表2 不同混沌映射对航路规划结果的影响Table 2 Influence of different chaotic maps on path planning results

混沌初始化映射选取：根据统计结果可得，当CGWO算 法 采 用Piecewise 映 射(M9)、Chebyshev 映 射(M10)以 及Ⅰntermittency 映射(M12)时得到的航路规划结果最优。将三种映射做进一步比较可得，CGWO 算法采用Ⅰntermittency映射能够得到比较满意的结果，且实现简单。

混沌变量a选取：由表3 可得，采用Ⅰntermittency 映射(M12)、Sinusoidal 映射(M6)与Gauss 映射(M3)时能够得到较优的规划结果。如图10所示，M6存在较大的离散性，另外，因为M12对混沌初始化具有较为明显的优化结果，所以混沌变量a选择M12作为混沌算子。同时为了便于计算，式(21)同样采用M12作为混沌算子。

表3 不同混沌变量a对航路规划结果的影响Table 3 Influence of different chaotic variables a on path planning results

3.2 算法的比较以及有效性验证

为了验证本节所提出的算法的有效性，采用粒子群算法、灰狼优化算法与混沌灰狼优化对单无人机航路规划问题进行求解，可以得到如图11所示航路规划结果。其中种群数量Np= 50，最大迭代次数tmax= 150，维度D= 5，规划空间内威胁分布的情况见表4。本文在设计代价函数时进行了无量纲（量纲一）处理，所以仿真分析不考虑实际单位。

表4 规划空间中威胁的分别情况Table 4 Threats in the planning space

将式(25)中航路代价的权重系数设为wi= 1/3,(i=1,2,3)，则航路代价随迭代次数的变化情况如图12所示。通过对比可得，CGWO 算法的初始代价高于其他两种算法，为了增加在解空间中的遍历性，CGWO算法选取的初始解为2 ×Np组混沌初始解按序排列后的奇数项，所以存在随机初始解优于混沌初始解的情况。但是随着寻优过程的进行，CGWO 算法很快找到了最优解。航路规划的结果为1.18(CGWO) ＞1.21(GWO) ＞1.35(PSO)。

通过将式(25)中航路的代价权重进行调整可以得到不同规划目标下的规划结果。如图13所示，定义wi(i= 1,2,3)的取值分别为(0.8,0.1,0.1)、(0.1,0.8,0.1)与(0.1,0.1,0.8)时采用CGWO算法可以分别得到航程最优、安全最优以及平滑最优的规划结果。其中种群数量Np= 30，最大迭代次数tmax= 150，维度D=11。

为了进一步验证本节所提的CGWO算法的性能，采用随机生成威胁环境的方式进行仿真试验。在1000 × 1000的规划空间内设置10 个威胁源，威胁源的位置、威胁半径与威胁类型随机生成。CGWO 算法、GWO 算法与PSO 算法的种群数量为30，维度为D=5，最大迭代次数80，图14与图15给出了600次的仿真统计图，结果证明了CGWO算法在解决单机航路规划问题上具有明显优势。

在每次仿真过程中，三种算法都对同一个威胁环境进行仿真试验，而在不同的仿真中，由于规划环境不同，所以不能对仿真结果直接进行对比。假设算法的最优代价值分别为fCGWO、fGWO与fPSO，则采用式(36)所示的归一化操作，即可得到图14所示的统计盒图。CGWO算法的仿真结果明显优于其他两种算法，能够得到代价值更优的规划结果。

令ΔfˉGWO=fˉCGWO-fˉGWO，ΔfˉPSO=fˉCGWO-fˉPSO，则得到如图15所示的结果示意图。在600 次仿真中，可以得到CGWO 算法优于GWO 的情况为74%，优于PSO 的情况为54.8%。ΔfˉGWO与ΔfˉPSO的平均值分别为-0.0129与-0.0466，相应的方差值分别为0.0017、0.0080，即CGWO算法的平均水平优于GWO 与PSO 算法。另外根据仿真结果可得GWO 算法的寻优能力强于PSO算法。

3.3 多机协同规划结果分析

假设三架无人机U(i)(i= 1,2,3)分别从(10,350)、(0,0)以及(360,30)出发，目标位置为(990,990)。假设目标的进入角分别为μ1=150°,μ2=270°,μ3=390°，最小对准距离l(i)min=100。根据图7所示的多无人机协同航路规划流程，采用CGWO 算法对航路规划问题进行求解，得到的规划结果如图16所示。

假设各无人机以相同的速度匀速飞行，则可以得到协同航程为SM= 1755.7。各无人机基于几何规划策略构造的航路规划结果如图17 所示。图中五角星表示根据方位角χ(i)j确定的辅助椭圆O(i)j上的点，辅助椭圆根据剩余航程ΔS(i)进行构造。根据式(30)将参数(λ(i)j,χ(i)j)解码为参考的航路点，即如图中的符号*所示。

4 结论

本文针对多无人机协同执行饱和攻击任务，根据椭圆第一定义提出了基于几何规划的从目标点出发的逆向航点扩展策略，从而构造出满足任务攻击时间与攻击方位要求的航点序列。将混沌映射引入灰狼优化算法中，提出了基于混沌灰狼优化算法的多无人机协同航路规划方法。仿真结果表明，提出的CGWO算法能够根据任务需求生成满足方位与时间约束的协同航路，同时算法的收敛速度与寻优精度明显优于其他算法。

由于本文假设无人机为匀速运动，以便将“按时到达”问题转换为路径长度对话。但在实际工程应用中并不一定要求全部无人机按相同的速度到达，所以本文接下来的工作针对不同到达速度要求下的“同时到达”问题展开研究，并扩展到三维航路规划，为实飞验证提供必要的研究基础。