基于遗传算法的协同航迹规划算法研究*

赵庆璐，周成平

（华中科技大学自动化学院多谱信息处理技术国家级重点实验室，武汉 430074）

0 引言

由于防空体系的不断完善、战场环境的瞬息万变，单个飞行器的突防概率明显降低，与此同时，在实际应用中往往需要同时对多个目标进行协同攻击甚至饱和攻击。因此，多任务的协同航迹规划是当前亟待解决的问题。所谓协同航迹规划是指在指定的规划空间中，满足飞行器自身约束、环境约束、协同约束等条件下，规划出从发射点集到目标点集的无碰撞的最优航迹组合，使得发射时间区间和到达目标时间区间尽可能小。Chandler［1］等和 Mclain［2］等提出了基于Voronoi图的协同航迹规划方法，该方法减小了解空间，加快了收敛速度，但没有包括地形高度信息，无法通过调整高度规避威胁，并且无法解决基于匹配辅助制导的规划问题;郑昌文［3］、严平［4］、史战伟［5］、叶嫒嫒［6］等提出了基于进化算法的协同航迹规划方法，该类方法虽然隐含了单任务与协同航迹共同进化的机制，但对单任务进化方向的引导力较弱，收敛速度慢，当任务数较多时不能满足规划的时间约束。

文中提出了一种基于遗传算法的协同航迹规划方法。该方法的主要特点是采用双层进化机制，不同飞行器形成各自的航迹种群用于下层进化，对不同飞行器的航迹进行不同的组合形成协同航迹组种群用于上层进化。在规划的过程中，通过状态表征矩阵表征各飞行器在协同航迹组中的贡献，进而引导飞行器向使协同代价变小的方向进化，收敛速度快，可以减少协同规划的时间。

1 基于遗传算法的协同航迹规划

1.1 协同规划模型

根据协同作战的应用背景，协同规划主要有以下几种模式:指定发射时间序列，使到达时间窗口尽可能小;指定到达时间序列，使发射时间窗口尽可能小;指定发射时间序列和到达时间序列，使到达时间误差尽可能小;指定某个任务的发射时间或到达时间，使发射时间窗口和到达时间窗口尽可能小。在真实的作战环境下，某个任务可能具有战略意义，对该任务的发射时间或到达时间也就有强约束，因此文中的研究内容针对最后一种模式，即指定某个任务的发射时间或到达时间，使发射时间区间和到达时间区间尽可能小。

1.2 协同规划算法

1.2.1 双层进化机制

本算法首先将协同规划问题拆分成多个子问题，每个子问题为单任务规划，所有子问题的解的组合构成协同规划问题的一个完整解。利用遗传算法为每个子问题初始化一个子种群，从不同的子种群中选择航迹进行组合形成协同航迹组种群，子种群在进化的过程中受到协同航迹组种群提供的信息的引导，同时协同航迹组种群随着各子种群的进化而进化。其中，子种群的进化对应本算法的下层进化，协同航迹组种群的进化对应本算法的上层进化。

1.2.2 下层进化评价与引导信息

下层进化是指各飞行器的可行航迹种群的进化，为了提高进化效率、加快收敛速度，文中首次提出了状态表征矩阵的概念，用于表征各飞行器的航迹在协同航迹组中的贡献，状态表征矩阵如下式所示:

式中:N为任务数;K为协同航迹组数;m为指定的任务编号;aij表示第j个任务在第i个协同航迹组中的贡献，aij的定义如下:

式中:lengthij表示第i个协同航迹组中任务j的航迹长度，lengthim表示第i个协同航迹组中指定任务的航迹长度。根据状态表征矩阵求出引导每个任务进化的αi、β算子，其中 αi引导任务i进化，β引导指定的任务进化，αi、β的定义如下式所示:

1.2.3 上层进化评价与引导信息

上层进化是指协同航迹组种群的进化，它通过协同评价函数引导，协同航迹组的评价函数应综合考虑影响协同性能的各种因素，文中结合实际应用背景以及协同规划模型，主要从以下两个方面进行评价:

1）协同航迹组中各任务的单航迹代价;

2）发射时间窗口与到达时间窗口。

评价函数的定义如下:

式中:T1为发射时间窗口;T2为到达时间窗口为协同航迹组中单航迹的代价之和;fi为任务i对应的航迹代价;ω1、ω2、ω3为权系数，通过调节权系数的大小可以使协同航迹组向不同的方向进化。

1.2.4 碰撞检测与调整

航迹碰撞检测的空间是四维空间，即在同一时刻不同航迹的三维坐标之间的距离是否小于最小安全距离，具体的检测方法是:以最早的发射时间tmin为起点，按照一定的时间间隔Δt沿时间轴采样，计算航迹在当前时刻的三维坐标进而求出飞行器之间的距离，直到达到最晚到达时间tmax。若在所有时刻飞行器之间的距离均大于最小安全距离，则飞行器之间无碰撞，否则首先通过局部速度调节避免碰撞，若不能满足要求，则通过高度调整避免碰撞。

1.2.5 算法描述

在本算法中，若任务数为N，则协同航迹组由N条航迹组成，算法的终止条件为:达到最大进化代数或最优个体满足代价要求，具体步骤如下:

1）为每个任务随机生成大小为M的可行航迹种群;

2）随机生成K个协同航迹组;

3）若终止条件满足，转7），否则，转4）;

4）若达到上层最大进化代数，转6），否则，转5）;

5）按适应度大小选择协同航迹组执行上层进化，转4）;

6）计算αi、β算子引导各任务的可行航迹种群执行下层进化，转3）;

7）选择协同代价最小的协同航迹组进行碰撞检测与调整，进化过程结束。

2 在有向航迹网络图上的应用

文中将该算法应用于有向航迹网络图［7］，网络图的生成是在考虑飞行器自身约束和环境约束的条件下，将栅格规划空间按一定大小划分为格网空间，在格网中选择匹配点或GPS导航点，然后以某一网格为起点向其它网格扩展连接，直到所有的网格扩展完成。扩展过程中考虑的约束条件主要有:匹配辅助制导约束、禁飞区/威胁区约束、水平机动约束、高度机动约束、飞行管道约束、飞行高度约束。生成的有向航迹网络图如图1所示。

图1 网络图示意图

2.1 网络图存储结构

在有向航迹网络图上规划的实质是图搜索，即将合适的航迹段进行连接。为了减小内存访问数据库的频率、加快规划速度，将网络图分两层进行存储:规划层、节点层。其中，规划层包含在规划的过程中所用到的航迹段信息，节点层包含航迹段上的具体节点信息，两层之间的桥梁是航迹段编号。网络图在数据库中的存储结构如图2所示。

图2 航迹网络图存储结构示意图

2.2 种群初始化

本算法用染色体表示航迹，如图3所示。染色体上的节点（基因）包含如下信息:航迹段编号IDi、航迹段长度Li、航迹段代价Ci，即任务的可行航迹是航迹网络上特定航迹段的组合。对每个任务随机初始化M条航迹，组成该任务的可行航迹种群，用于下层进化。

图3 染色体结构

若任务总数为N，则初始化生成了M*N条染色体，从每个任务种群中随机选择一条染色体，N条染色体构成一个协同航迹组（个体），初始化K个个体组成协同航迹组种群，用于上层进化。

2.3 下层进化算子

在遗传算法中引导种群进化的算子多种多样，考虑到染色体的结构以及规划空间的特殊性，在下层进化中选择变异算子作为种群的进化算子。随机选择扰动点，若αi≥0，表示任务i的航迹在所有航迹中较长，则在扰动点处按概率选择较短的航迹段，否则选择较长的航迹段;同理，若β≥0，表示指定任务的航迹在所有航迹中较短，则在扰动点处按概率选择较长的航迹段，否则选择较短的航迹段。对航迹p的随机扰动点执行变异操作的公式如下:

2.4 上层进化算子

在上层进化中采用两种进化算子:交叉算子、变异算子，如图4所示。

图4 进化算子

交叉算子:按适应度大小选择两个父代个体，随机选择交叉点将两个体分割为两部分，然后将两父代个体的后半部分相互交换，生成两个新的子个体，两父个体的交叉点位置相同。

变异算子:按适应度大小选择父代个体，随机选择变异点，从变异点所对应的任务的航迹种群中随机选取一条替换原来的航迹，生成新的子个体。

3 实验结果

本算法在 CPU为 Core E7200 2.53 GHz、内存2.0 GB的PC机上进行了实验，运行环境为Windows XP，编程环境为VS2005。实验使用了分辨率为30*30的数字地形高程图和模拟生成的禁飞区数据，实验中的参数设置如下:ω1=0、ω2=0.9、ω3=0.1，实验结果如图5、图6所示。

图5 二维显示

图6 剖面显示

其中，多边形区域表示禁飞区，旗帜和三角形分别表示发射区和目标区，航迹上的圆点表示导航点。同时文中对标准遗传算法进行了实验，实验结果如图7、图8所示。

表1给出了以上任务的部分实验数据，实验中任务①为指定的任务，表示协同航迹组的收敛程度，式中:li为协同航迹组中任务i对应的航迹长度。实验结果表明，该算法与标准遗传算法相比，在两者规划出的协同航迹组的收敛程度相近的情况下，该算法能够大大的减少规划时间。

图7 二维显示

图8 剖面显示

表1 实验数据

4 结论

文中提出了一种基于遗传算法的协同航迹规划方法，该方法采用双层进化机制，即单任务进化、协同进化，并通过状态表征矩阵引导各任务种群进化，加快了收敛速度。实验结果表明，在满足飞行器自身约束、环境约束、协同约束的条件下，该方法能够在较短的时间内规划出较优的协同航迹组。

［1］Chandler P，Rasmussen S，Pachter M.UAV cooperative path planning［C］//Proc Guidance，Navigation and Control Conf，AIAA，2000.

［2］McLain T，Beard R.Trajectory planning for coordinated rendezvous of unmanned air vehicles［C］//Proc Guidance，Navigation and Control Conf，AIAA，2000.

［3］郑昌文，丁明跃，周成平，等.多飞行器协调航迹规划方法［J］.宇航学报，2003，24（2）:115－120.

［4］Yan Ping，Ding Mingyue，Zheng Changwen.Coodinated route planning via Nash equilibrium and evolutionary computation［J］.Chinese Journal of Aeronautics，2006，19（1）:18－23.

［5］史战伟，周成平，丁明跃，等.基于进化计算的多无人飞行器协同航迹规划［J］.战术导弹技术，2007（5）:49－53.

［6］叶媛媛，闵春平.多无人机协同航路规划的共同进化方法［J］.计算机仿真，2007，24（5）:37－39.

［7］周志鹏，周成平，赵庆璐.一种用于航迹规划的网络图构造方法研究［J］.弹箭与制导学报，2013，33（4）:67－70.

［8］吴昊，任敏，薛宏涛，等.航迹数据库及其在航迹规划中的应用研究［J］.系统仿真技术及其应用，2007（10）:534－537.