基于蚁群算法对飞行器航迹规划的研究

刘文文，朱家明

(1.中央民族大学 经济学院，北京100081; 2.安徽财经大学 统计与应用数学学院， 蚌埠233030)

飞行器航迹规划的任务就是在多种条件的约束下，为无人飞行器寻找一条从起点到终点的最优路径.飞行器在飞行过程中，由于系统结构的限制和飞行环境带来的各种扰动往往会产生累积的定位误差，这种误差会随着飞行时间和飞行距离的增加而不断累积，从而最终导致飞行任务失败.这一问题的通常解决办法是，在航迹的特定位置对累积误差进行校正，不仅能保证无人飞行器的安全，还能保证飞行任务的高精度完成.

蚁群算法是指蚁群可以在不同的环境下，寻找到达食物源的最短路径.因为蚁群内的蚂蚁可以通过“信息素”实现信息的传递.“信息素”浓度越高的路径有越大的概率被蚂蚁选择，而每只路过的蚂蚁都会在路上留下“信息素”，形成一种正反馈的机制，经过一段时间后，最终整个蚁群就会沿着最短路径到达食物源了[1].而航迹规划问题本质上就是在满足既定的飞行约束条件下，在众多可行的飞行路径中寻找一条最优(最短)的飞行路径，这与蚁群寻食的情景非常相似.因此，在解决航迹规划问题时最容易想到的现代智能优化算法就是蚁群算法.

目前国内外已有很多学者做了相关方面的研究，Zhao Q等(2015)针对雷达威胁环境下的多架无人机编队的路径规划问题，提出了一种基于改进蚁群算法的智能方法[2].Calik，Seda Kazdal(2016)提出了一种针对无人机的全局最优轨迹规划问题的解决方法，该模型被建模为具有多主体结构的蚁群优化(ACO)，仿真结果表明ACO极大地优化了航线长度，减少了无人机航路规划的平均飞行时间[3].赵丹和戚龙(2017)在满足无人机飞行约束条件的情况下, 为无人机航迹规划提供一种蚁群-粒子群融合算法, 充分利用蚁群算法良好的分布机制、信息反馈机制和粒子群算法收敛，保证了飞行器航线的完整性和最优性[4].Wu Zhenyu，Li Jinhuan，Zuo Jiaming等 (2018)针对动态环境下多无人机通信状态信息噪声引起的不一致问题，提出了一种基于卡尔曼算法的状态估计方法.为了实现飞机的航迹规划，最终计算出群集状态预测和碰撞概率，以避免编队无人机的群集在飞行过程中在路径上发生冲突[5].王琼，刘美万，任伟建等(2019)对航迹规划常用算法进行了综述，并且预测了无人机四维航迹规划算法的未来发展[6].

为了研究方便，本文主要以2019全国研究生数学建模竞赛F题所给的背景为主要研究背景，研究无人飞行器在系统定位精度限制下的航迹快速规划问题.首先，对实际的航迹规划问题进行适度的简化，提出一定的假设条件，在此基础上提出对航迹规划问题的数学模型，并利用蚁群算法对此数学模型进行求解.在模型求解过程中，我们将对利用蚁群算法求解航迹规划问题中的关键问题进行详尽分析.

1 数据来源

本文数据来源于2019全国研究生数学建模竞赛F题的附件1(本文的附录2列出了其中部分数据).附件1给出了612个矫正点(包括起点和终点)的三维空间坐标(X坐标、Y坐标、Z坐标)，坐标单位米(m).并标出了每个矫正点的矫正点类型和矫正点质量.对于矫正点类型：1表示垂直误差校正点，0表示水平误差校正点；对于矫正点质量：1表示可能出现问题的点，0表示正常校正点.

2 飞行器的航迹约束

飞行器的飞行区域如图1所示，出发点为A点，目的地为B点.形象地说，飞行器的航迹就是一条以A点(附件1中的出发点)为出发点，以B点(附件1中的终点)为终点，中间串连了许多矫正点的曲线.航迹的具体约束如下：

图1 飞行器航迹规划区域示意图

1)飞行器在运动过程中需要时刻进行定位，飞行过程中产生的定位误差包括水平误差和垂直误差.飞行器每飞行1 m，垂直误差和水平误差将各增加δ个专用单位，以下简称单位.飞行器到达终点时垂直误差和水平误差均应小于θ个单位，并且为简化问题，假设当垂直误差和水平误差均小于θ个单位时，飞行器依然可以根据规划路径飞行.

2)飞行区域中有一些安全位置(校正点)可以对飞行中的飞行器进行误差校正，飞行器到达校正点根据矫正点类型进行误差校正.垂直和水平误差的校正位置可以根据地形在航迹规划前确定(如图1为某条航迹的示意图,图中●是水平误差校正点，▲是垂直误差校正点，A点出发，终点B，曲线表示飞行器的一条航迹).地形影响可校正的飞行区域分布，无统一规律，若垂直误差、水平误差都能得到及时校正，则飞行器按规划航迹进行飞行，经过若干个校正点的校正后到达终点.

3)飞行器的出发点为A，垂直和水平误差均为0.

4)在垂直误差校正点，飞行器校正垂直误差使其为0，水平误差不变.

5)在水平误差校正点，飞行器校正水平误差使其为0，垂直误差不变.

6)飞行器垂直误差校正的条件为：垂直误差不大于α1个单位，水平误差不大于α2个单位.

7)飞行器水平误差校正的条件为：垂直误差不大于β1个单位，水平误差不大于β2个单位.

8)由于结构和控制系统的限制，飞行器无法完成即时转弯(即前进方向无法突然发生变化)，假设飞行器的最小转弯半径为200 m.

为了方便模型建立与求解，我们首先将上述航迹约束条件进行数学抽象表达.

(1)

其中：H为上一个水平校正点或起点，其中V为上一个垂直校正点或起点，P(x，y，z)为当前位置点.Jh={H1,H2,…HN}为水平校正点集合，Jh={J1,J2,…JN}为垂直矫正点集合.此式为水平误差和垂直误差的累积方式.

(2)

其中：Hend、Vend、Pend分别为航迹中的最后1个水平矫正点、最后1个垂直矫正点和终点.此式为飞行器成功飞抵终点的条件.

δh=0,如果:P∈JH,且δh<α1,δv<α2

δv=0,如果:P∈JV,且δh<α1,δv<β2

(3)

如果到达矫正点，且飞行误差在矫正点的可矫正范围之内，则将相应的误差清零.

3 基础模型

为了建立有效的数学模型，必须把现实问题进行适当的假设与简化，进而映射到数学空间.本文本着由易到难的研究办法，首先建立较为基础模型，在完成基础模型的求解之后，进一步改进数学模型，考虑更多现实因素，使模型更加贴近实际情况.

3.1 模型的建立

基础模型基于3个假设：首先假设航迹从A出发，B结束，且只需要满足上述航迹约束的前7条，其次假设航迹是折线，即矫正点之间直线飞行，在矫正点处突然改变航向.最后上述约束中参数为：α1=25，α2=15，β1=20，β2=25，θ=30，δ=0.001.数学模型的求解目标是寻找一条使得飞行器航迹尽可能短、航迹上的矫正点尽可能少的航迹，其数学表达形式为：

(4)

其中：α、β分别为航迹长度和矫正点数的权重因子，Li为航迹上矫正点间的距离，这里所有的矫正点包括起点和终点，其计算公式如下：

(5)

3.2 基于蚁群算法的模型求解

根据蚁群算法解决航迹规划问题的整体解决思路，模拟蚁群在遵守约束条件的情况下从A点爬到B点(Nm是指蚁群中蚂蚁的个数)，然后对蚂蚁走过的所有路径进行评分，从Nm条蚂蚁走过的路径中选择出一条最优路径，更新最优路径上各校正点的评分，同时更新历史最优路径，并判断最优路径的评分是否收敛，确定收敛则得出最优路径，否则回到开始继续模拟蚂蚁从起点到终点.蚁群算法的整体流程框图如图2所示.

图2 蚁群算法的整体流程框图

3.2.1 每只蚂蚁的模拟过程

为了能在最短的时间内找到最优航迹，并且保持一定的全局最优性.我们将每只蚂蚁视为独立的个体，且具有一定的智能性，蚂蚁之间只通过信息素交换信息.模拟蚂蚁从起始点到终点的算法框图如图3所示，具体流程为：

图3 蚂蚁从起始点到终点的算法流程框图

1)参数初始化，包括蚂蚁个数N，出发点和到达点等.

2)读入已知的数据，建立规划空间模型，获取飞行区域校正点类型信息.

3)开始循环.

4)在当前误差选择在下一个校正点要校正水平误差δH还是垂直误差δV.若校正δH，则h_or_v=0(注：h_or_v=0，指校正水平误差；h_or_v=1，指校正垂直误差).

5)根据当前误差和h_or_v的值计算最大飞行距离，即可行域半径R.

6)根据R和h_or_v的值选择可行域中的校正点，并且把这些点作为候选点.

7)对所有候选点进行评分，分数用s表示.

8)依据概率密度函数f(s)随机从候选点中选择一个点作为下一个校正点.

9)蚂蚁到达下一个校正点后，更新当前位置点和当前误差.

10)判断是否到达终点B，如果是，对此次蚂蚁走过的路径进行评分，输出这条路径的所有点和路径评分；否则，回到步骤4)继续执行[7-8].

11)算法结束.

3.2.2 矫正类型选择方法

在航迹规划中，选择下一个矫正点矫正类型的方式，对航迹的规划结果至关重要，不但影响航迹的长短和矫正点的多少，而且有可能让蚂蚁陷入“死胡同”，无法继续航行，这种情况为：

当α2-δh>0，β1-δv>0时，同时无法矫正δh和δv.因此，下一个矫正点的矫正方式应慎重选择，本文的选择方法是首先考虑矫正的可行性，即选择的下一个矫正类型必须在可矫正的误差范围之内.具体方法为：当α2-δh>0，β1-δv<0时，矫正δv；当α2-δh<0，β1-δv>0时，矫正δh.其次矫正的紧迫性，离可矫正误差上限越近的误差类型，被矫正的需求就越紧迫，具体方法为：当α2-δh<0，β1-δv<0时，同时可矫正δh和δv.

H_or_V=argmin{(α1-δv),(β2-δh)}

(6)

其中：H_or_V为矫正类型，H_or_V=0表示水平矫正，H_or_V=1表示垂直矫正.

3.2.3 选择可行域半径的方法

可行域半径的选取同样十分重要，如果半径过小，不但会使航迹的矫正点数增加，还容易导致可行域内没有可用的矫正点.如果半径过大，会导致剩余误差裕度过小，从而致使本次航行失败.我们的选择办法具体为：

(7)

其中：R表示可行域半径.即可行域半径由当前两个误差裕度中的最小的一个决定，最小误差裕度除以误差因子就是当前的可行域半径的长度.

3.2.4 可行域的选取方法

可行域是指下一个所有可能矫正点所在的区域，建立可行域将为形成下一个矫正点的候选点集合提供方便.我们建立的可行域是一种球面椎体，可行域中的矫正点P同时满足如下两个条件：

(8)

(9)

3.2.5 对候选点的评分方法

对候选点的评分方法是蚂蚁智能性的直接体现，好的评分方法将会引导蚂蚁走更优的路径，反之，蚂蚁蚂蚁将会直接失去大脑.我们对候选点的评分方法具体如下：

(10)

其中：P为候选点的位置，Pend为终点位置，αs为评分因子，评分将会在下文详细介绍.Js可行域中候选点的集合.即与终点越近的候选点评分越高，这种启发式有点类似于贪婪搜索方法，总是给最短路径评高分.评分因子刻画的是蚂蚁的信息素，评分因子越高，对应候选点的评分越高[10-11].

3.2.6 下一矫正点的选取方法

为了模拟蚂蚁在选择路径时候的真实情况，根据上述对候选点的评分和概率密度函数f(s)选择下一个矫正点.概率密度函数的表达式为：

(11)

其中：μ=0,σ=0.5，s为对矫正点的评分.即矫正点评分越高，被选择的概率越大，矫正点的评分越低，被选择的概率越小.

3.2.7 更新当前误差的方法

为了满足题目的约束条件，蚂蚁每到达一个矫正点都需要更新水平误差和垂直误差.具体的更新方法为：

当H_or_V=0时：

δh=0

(12)

当H_or_V=1时：

δv=0

(13)

其中：Pi为当前矫正点的位置，Pi-1为前一矫正点的位置.

3.2.8 更新矫正点评分因子的方法

矫正点的评分因子对应一群的信息素，对于蚁群，信息素是蚂蚁间交换信息的主要媒介，也是蚁群总能找到到达食物的最短路径的最主要原因.对于蚁群算法，评分因子是决定其收敛性的最主要因素，我们计算评分因子的方法为：

(14)

其中：Vq为信息素的释放速度，Vh为信息素的挥发速度，Jm为当前最优路径上的矫正点集合.即每个矫正点的信息素都会在每次迭代中以一定的速度挥发，而最优路径上的矫正点的信息素则会以一定速度增加.

3.2.9 路径评分方法

路径评分方法直接对应于算法的优化目标，由于优化目标一和二基本类似.优化目标中的路径评分方法为：

(15)

其中：α、β分别为航迹长度、矫正点数和到达终点概率的权重因子，Li为航迹上矫正点间的距离，这里的矫正点包括起点和终点，n是航迹上矫正点的个数.可以明显看出，不同于对候选点的评分，对路径的评分越低越好.

3.3 模型的求解结果

根据题中给出的各误差裕度，利用上述蚁群算法处理附件1数据，绘出以下航迹规划路径如图4所示，程序仿真结果见表1，航迹规划结果见表2.

表1 程序仿真结果

表2 航迹规划结果

由图4可以看出除终点B外，需要校正的8个点的具体位置.由表1、2可以看出，校正点里包括4个水平误差校正点，4个是垂直误差校正点，且校正前垂直误差和水平误差都比较大.满足前7个约束条件的飞行器最佳航迹长105 244.151 m.

图4 航迹规划路径

4 改进模型

4.1 模型的建立

即使在飞行前确定了校正点，飞行器的飞行环境可能随时发生意想不到的变化，导致飞行器在部分误差校正点无法达到理想的校正状态(即将某个误差精确校正为 0)，例如风向，气流等不可控因素的影响.由于这个原因，提出基于4个假设的改进数学模型：1)假设航迹从A点出发，到B结束，且不只需要满足上述前7条航迹约束，还要满足第8条约束，即飞行器不能完成即刻转弯;2)假设两矫正点之间的距离为直线距离加半径大于200 m的圆弧距离，且直线航迹与圆弧航迹是完美相切的;3)假设飞行器在部分校正点(质量标记为1的校正点)能够百分百将误差校正为0，在部分校正点(质量标记为0的校正点)能够成功将误差校正为0的概率是 80%.如果校正失败，校正后的剩余误差为 min(error，5)个单位，并且假设飞行器到达该校正点时即可知道在该点处是否能够校正成功，但不论校正成功与否，均不能改变规划航迹;4)上述约束中参数为α1=25，α2=15，β1=20，β2=25，θ=30，δ=0.001.我们的优化目标是基于这3条假设，寻找一条使得飞行器航迹尽可能短、航迹上的矫正点尽可能少、且能够到达终点的可能性尽可能大的航迹，其数学表达形式如下[12-13]：

(16)

其中：α、β、γ分别为航迹长度、矫正点数和到达终点的概率的权重因子，Li为航迹上矫正点间的距离，这里所的矫正点包括起点和终点，它的计算公式如下：

(17)

其中：Δ为矫正点间带圆弧的航迹与直线航迹的长度差.

4.2 模型的求解

对于改进的数学模型，求解过程与基础模型基本一致，也是利用蚁群算法进行求解，只是当前误差的更新方法(3.2.7所述)和路径的评分方法(3.2.8所述)有所变化.改进模型的当前误差的更新方法是：

当H_or_V=0时：

当H_or_V=1时：

改进模型的路径评分方法是：

(18)

其中：α、β、γ分别为航迹长度、矫正点数和到达终点概率的权重因子，L′i为航迹上矫正点间的航迹长度，这里的矫正点包括起点和终点，n是航迹上矫正点的个数，P为问题3中飞行器能从起点到达终点的概率.

4.3 模型的求解结果

根据题中给出的各误差裕度，利用上述蚁群算法处理附件1数据，绘出航迹规划路径如图5所示，程序仿真结果如表3所示，航迹规划表如表4所示.

图5 数据航迹规划路径

表3 程序仿真结果

表4 航迹规划结果

由图5可以看出，加入了飞行器前进方向无法突然发生变化的约束条件后，飞行器的航迹在校正点不再跟图4一样是折线，变成了曲线.由表3、4可以看出，除终点B外，校正点有8个，包括4个水平误差校正点，4个是垂直误差校正点，且校正前垂直误差和水平误差都比较大.满足8个全部约束条件的飞行器最佳航迹长106 970.774 m，飞行器成功到达终点B的可能性为0.8[14].

5 结 语

相比于基础模型，改进的模型校正点数量不变，但是航迹更长，这是因为加入了飞行器无法即刻转弯的约束条件，飞行器需要用曲线完成误差修正.蚁群算法作为一种新兴算法, 具有良好的分布式并行计算特点和较强的鲁棒性，并且易于同其他算法结合实现优势互补，在比较复杂的系统问题上展示出良好的性能，隐藏着无穷的潜力，并且拥有计算量少，计算复杂程度较低等优点[15].蚁群算法由于高度依赖各个参数，因此一个参数的微小改变可能会改变收敛方式，变使得结果大不相同.并且该模型存在收敛速度慢,易陷入局部最优解，通用性一般的问题.但是在本算法中，通过大量训练，增加蚁群的数量，加快信息素的挥发等办法使得蚁群算法跳出了局部最优解的缺陷.