基于改进人工鱼群算法的无人直升机编队航迹规划

马梓元，龚华军，王新华

（南京航空航天大学 自动化学院，南京211100）

随着科学技术的进步及其在航空领域的应用，无人化、智能化已经成为航空装备的发展趋势。无人直升机（Unmanned Helicopter，UH）作为先进航空装备的代表，具备多环境、多领域下的执行任务能力。而航迹规划作为无人直升机编队执行任务的关键环节，是指在初始状态、任务目标、威胁区和一些已知或者未知环境信息的情况下获得性能最优的规划问题，其是任务规划系统的关键技术之一，具有规划范围大、约束条件多及动态性高等特点［1-4］。因此，对航迹规划的研究也是业内关注的重点。

在当前的研究成果中，文献［1］在考虑侦察任务重叠和多机协同侦察的同时，以最小化侦察路径长度为性能指标，相邻侦察点间采用Dubins曲线进行航迹规划，利用引入精英机制的混合粒子群优化（PSO）算法实现侦察任务序列优化，实现具有持续侦察时间约束的协同航迹规划，提高了算法的有效性。文献［2］在三维复杂地形下，建立了满足无人机机动约束条件的航迹规划模型。文献［3］针对复杂环境中多无人机编队突发威胁规避问题，提出了一种基于凸优化算法的实时路径规划方法。文献［4］比较分析了人工势场法、模糊逻辑算法对无人机碰撞规避路径规划的性能，并针对人工势场法易陷入局部极小值的缺陷提出了通过增加垂直引导斥力来使无人机逃离局部极小值的改进措施。文献［5］采用了协同非支配排序进化算法，根据多架无人机的航行距离、安全性、时间及空间的协同性进行航迹上的规划。文献［6］针对无人机集群在未知环境中无先验信息条件下的搜索问题，提出了一种以信息素为决策机制的无人机集群搜索算法，提高了搜索效率。文献［7］针对无人机航迹规划问题，在遗传算法的基础思路上引入差分进化变异策略，并与模拟退火算法结合起来，增加了算法变异的多样性。文献［8］针对规划环境中存在相交威胁的特点，采用路标导引法解决了双机协同规划中的陷阱问题，同时利用探测步长限制2个相邻航迹节点间的速度方向变化范围。文献［9］针对多无人机的航迹规划问题，采用了一种混合粒子群优化算法进行规划，使得各个无人机所经路径的代价函数总和最小。文献［10］针对无人机在复杂战场环境下的航迹规划问题，提出了一种基于传统蚁狮算法中蚂蚁随机游走的行为和混沌算子相结合的混沌蚁狮（CALO）算法的航迹规划算法，提高了算法寻找全局最优值的能力。文献［11］针对快速扩展随机树（RRT）算法进行改进，通过引入动态步长和自适应目标引力策略，在二维规划空间为无人机有效、快速地规划出一条满足实际飞行性能的较优航线。文献［12］将动态域快速随机搜索树与线性二次高斯运动规划相结合，在威胁环境不确定的条件下，实现了具有良好安全性能的单机航线在线规划。文献［13］运用数学方法伪谱法应用于多无人飞行器，实现了满足多约束的多无人机航迹规划。文献［14］将无人机雷达散射截面（RCS）考虑进去，利用遗传算法进行了在动态RCS基础上的航迹实时规划，实现了飞行过程中对威胁的合理规避。

以上成果显著提高了无人直升机航迹规划能力和水平，但是搜索效率低及求解精度差等问题仍然存在。针对以上两方面问题，本文提出了一种基于改进人工鱼群算法（Improved Artificial Fish Swarm Algorithm，IAFSA）的无人直升机编队航迹规划算法。

1 改进人工鱼群算法

人工鱼群算法（Artificial Fish Swarm Algorithm，AFSA）是李晓磊博士在对生物鱼类群体的社会行为特性进行观察和总结的基础上于2002年首次提出的［15］，是一种模仿鱼群行为的寻优算法，其具有并行性、简单性、寻优速度快等优点，同时也存在着寻优精度不高、后期收敛速度变慢等缺点。

当前业界对于智能算法的改进，通常从算法参量和算法机理两方面开展。针对人工鱼群算法的固有缺点，本文同样从以上两方面入手，分别对人工鱼的视野和人工鱼群进化策略进行改进。

1.1 人工鱼视野模型

人工鱼的视野决定了算法整体的收敛速度和收敛精度，因此学术界对其的研究也较为深入，文献［16-17］分别提出了不同的改进自适应视野模型。在以上成果的基础上，本文从邻域学习和算法特性2个角度出发，提出了一种人工鱼自适应视野模型，如下：

式（1）给出的模型实现了人工鱼的视野依据鱼群寻优情况进行动态调整。在genuc内人工鱼的适应度值保持变化的情况下，视野动态调整，以此保证人工鱼向最优解靠拢，进行精细搜索。而作为相反的情况，若人工鱼的适应度值在其中未发生变化，说明人工鱼可能陷入了局部收敛区域，此时需要重新全局大范围搜索，genuc因此将人工鱼的视野重置为初始值。

1.2 人工鱼群进化策略

自然界中的生物通过繁殖来完成物种的进化，繁殖分有性繁殖和无性繁殖2种方式。有性繁殖是一对父代个体产生一个子代个体，优点是拓展了种群多样性，缺点是无法保证子代个体的质量。无性繁殖是一个父代个体产生一个子代个体，优点是种群特性稳定，进化速度快，缺点是对父代个体质量的依赖性强。

考虑到无人直升机编队航迹规划问题的复杂程度和求解计算量，本文采用无性繁殖的方式作为人工鱼群的进化策略，但是为了保证其种群的整体质量，必须对其进行改进，具体如图1所示。图中：δ为拥挤度因子，nf为视野内鱼的数目，Yi、Yc、Ym分别为当前i、c、m位置的人工鱼的食物浓度。

从图1中可以看出，针对无性繁殖的特点，在进化策略上对其的改进思路是：根据每一代进化后的人工鱼适应度值进行排序，从而筛选出较差的人工鱼个体并加以淘汰，同时用适应度值较高的人工鱼进行对应的补充。具体人工鱼淘汰补充过程以伪代码的形式表示如下：

图1 人工鱼群进化策略改进示意图Fig.1 Schematic diagram of improvement of evolution strategy of artificial fish swarm algorithm

For i=1 to m

X=［x1，x2，…，xm］；//人工鱼群X

yj=Sort〈f（xi）〉，i，j=1，2，…，m；//按照人工鱼xi的适应度值从小到大进行排列

Choose〈｛ym-n+1，…，ym｝〉；//筛选n条淘汰的人工鱼个体

Substitude〈ym-i+1〉for〈yi〉，i=1，2，…，n；//对人工鱼个体进行替换

End

通过在每一代进化中淘汰较差个体，改进后的人工鱼群进化策略从原理上克服了无性繁殖中较差个体的产生，确保了人工鱼群整体搜索精度和效率的提升。

2 无人直升机编队航迹规划模型

2.1 规划原理

本文采用栅格法划分规划空间，航迹由相邻网格节点连接而成，每个网格节点包含着规划环境中的地形状况威胁、障碍、天气等因素，如图2所示。

图2 航迹连接示意图Fig.2 Schematic diagram of trajectory connection

图2描述了航迹点Pi→Pi+1的连接，即每个节点的下一个节点只能出现于相邻的8个节点中。由此，航迹规划可描述为

式中：S（xs，ys）为起始点；G（xg，yg）为目标点；P1（x1，y1）…Pn-1（xn-1，yn-1）为 中 间 航 迹 节 点；Γ（q）表示约束条件，q为航迹约束参数。

2.2 代价函数模型

以航迹代价最小作为算法的寻优目标，代价函数的设计影响着寻优算法的航迹生成质量，同时代价函数也是规划模型构建的基础，本文将从航程、威胁、时间等方面构建代价函数模型。

2.2.1 航程代价

无人直升机体积和起飞重量有限，故能量也有限，在规划航迹时应尽量实现和保证其飞行距离最短，本文将航程代价定义为所有航路段的长度之和：

式中：li为航迹段i的长度。

2.2.2 威胁代价

雷达、地形等外部干扰是无人直升机航迹规划中需要规避的威胁，航迹规划的目的是规避威胁且实现自身约束条件下的可飞路径，不同种类的威胁影响的范围不同，对无人直升机的威胁程度也不同。为了简化研究，本文将单机航迹的威胁代价JT定义为

式中：JT-i为航迹段i中无人直升机所受到的威胁代价，其模型为

本文考虑的威胁源包括雷达威胁、地空导弹威胁、地形威胁及气象威胁等，现给出其具体模型。

1）雷达威胁

针对雷达作战特性，将雷达威胁模型定义为式中：PR为雷达发现目标的概率；KR为表征雷达性能的参数；d为无人直升机到雷达的距离；Rmax为雷达最大作用距离。

2）地空导弹威胁

构建地空导弹威胁模型为

式中：Pm为地空导弹威胁概率；dsj为杀伤区近界水平距离；dsy为杀伤区远界水平距离；ds为无人直升机到地空导弹的水平距离。

3）地形威胁

基于编队飞行安全的考虑，构建地形威胁模型为

式中：PT为无人直升机所在高度；dT为无人直升机到地形障碍中心轴线的距离；HT为地形障碍高度；RT为高度h上地形障碍表面距离中心轴线的距离。

4）气象威胁

气象威胁Pw如下：

式中：dw为无人直升机距离气象威胁中心的距离；dwmax为气象威胁区域最大半径；dwmin为无人直升机因气象威胁出故障而不能完成任务的区域。

2.2.3 时间代价

时间代价体现为各个无人直升机到达目标终点的时间范围与指令时间的差别，因此其模型为

式中：t为无人直升机达到目标终点的实际时间；tc为无人直升机到达目标终点的指令时间；tmin和tmax分别为设置的允许时间下限和上限。

2.3 约束条件分析

在文献［19-20］的基础上，给出以下约束条件。

1）航迹总长度

由于各类资源的限制，所规划出的航迹总长度要满足一定要求，由此给出最大航迹总长度约束：

式中：Lmax为最大航迹总长度。

2）航迹段长度

同样从资源的角度考虑，对航迹段的最小长度进行约束，具体描述为

式中：lmin为航迹段最小长度。

3）飞行高度

基于安全性考虑，给出航迹规划的飞行高度约束：

式中：Hj为第j架无人直升机的飞行高度；Hmax、Hmin分别为航迹规划的最大、最小飞行高度。

4）飞行速度

为了保证无人直升机编队协同完成任务，必须对其速度进行约束，具体如下：

式中：vj为第j架无人直升机的飞行速度；vmin、vmax分别为航迹规划出的最大、最小飞行速度。

5）俯仰角

从无人直升机飞行安全的角度出发，给出俯仰角约束：

6）转弯角

为了确保规划航迹的可行性，对其转弯角进行限制，如下：

7）安全距离

为了避免无人直升机编队在协同执行任务期间发生碰撞问题，建立如下安全距离模型：

2.4 编队航迹规划模型

编队航迹规划模型即为人工鱼群算法求解的目标函数。基于1.1节所建立的模型，构建编队航迹规划模型，如下：

3 基于改进人工鱼群算法的航迹规划算法

3.1 编码方式

为了兼顾算法搜索的效率和精度，本文基于变长度的实值形式对人工鱼个体进行编码，个体xi（i=1，2，…，m）的编码如下：

式中：n为航迹点的个数。

3.2 聚类策略

在协同航迹规划中，对无人直升机的初始航迹种群进行聚类。本文的聚类策略是指对指标优先级进行排序，按照优先级逐个计算出各指标对应的一定数量的较优秀个体作为子种群，剩下的个体作为最优个体存储种群，用来存储各个子种群好的个体。

3.3 算法流程

本文算法的具体流程如图3所示。

图3 基于改进人工鱼群算法的航迹规划算法流程Fig.3 Flowchart of trajectory planning algorithm based on improved AFSA

4 仿真分析

表1 无人直升机与目标信息Table 1 UH and target information

表2 威胁参数设置Table 2 Threat parameter setting

图4 水平面规划航迹Fig.4 Horizontal trajectory planning

图5 三维空间规划航迹Fig.5 3D space trajectory planning

仿真环境想定为3架无人直升机执行对3个目标的打击任务，需要对航迹进行规划。具体模型参数参考文献［21］，具体无人直升机与目标信息及威胁参数如表1和表2所示。根据以上参数，得到仿真结果如图4、图5及表3所示。

从图4和图5可以看出，本文算法实现了对3架无人直升机所构成的编队的航迹规划。首先，3架无人直升机组成的编队都是按照所规划的轨迹到达了目标点；其次，规划航迹成功规避掉了作战区域内的地形及各类威胁，同时算法规划出的航迹满足了本文所设立的约束条件。从表3可以看出，规划出的3架无人直升机实际到达时间与指令最初时间最多相差30 s左右。那么根据无人直升机本身具有悬停等待功能及在低烈度战争的前提条件下，该误差时间是可以容忍的，并且能够满足相应的要求，进而验证了本文算法的可行性。

为了与其他求解算法作更好的对比，本文选取了人工鱼群算法、进化算法（EA）、粒子群优化算法3种算法和改进后的人工鱼群算法进行无人直升机航迹规划问题的求解和对比，结果如图6所示。

从图6可以看出，在4种算法中，进化算法出现了早熟的情况，并且陷入了局部最优无法满足搜索要求，而粒子群优化算法虽然在初期收敛速度较快，但是后期同样陷入了局部最优，人工鱼群算法虽然在速度上有了较大的提高，但从精度上来看有提高却依然不够理想，而且同样未搜索到最优解，本文提出的改进人工鱼群算法相比于其他3种算法，收敛速度较快，且通过对视野模型和进化策略的改进，在收敛精度上存在着明显的优势。

表3 无人直升机实际到达时间Table 3 Actual arrival time of UH

图6 搜索算法性能对比Fig.6 Performance comparison of search algorithms

5 结束语

本文提出了一种基于改进人工鱼群算法的航迹规划算法。通过对人工鱼群算法的改进、航迹规划模型的建立等措施实现了对编队航迹规划问题的求解。仿真结果验证了所提算法的有效性。但是本文还存在着如下3点不足和需改进的地方：①在代价函数上考虑的还不够充分，可能还存在其他的威胁未考虑进去；②在参数设置上较为理想化，可能还存在较大的改进空间；③由于本文是根据无人直升机的终点悬停等待的特性采用的同步方式，导致在到达目的地的时间上会有所误差。后续工作将围绕以上3个方面问题进行更深入的研究，以期得到的规划算法能够更加贴近实战环境。