多约束随机进化因子的蚁群算法求解航迹规划

詹棠森，熊 峰，薛广富，赵世栋，施明勇，汤可宗

(景德镇陶瓷大学信息工程学院，333403，江西，景德镇)

0 引言

复杂环境下的飞行器航迹规划是实现智能飞行器控制的一项关键技术[1]。近年来，很多学者提出了很多改进航迹规划模型[2-4]，但这些模型容易陷入局部最优。另外，也有学者虽然提出解决局部最优的航线轨迹优化问题[5-7]，但这些问题都是在平面上的轨迹上的问题。目前，很多航线轨迹问题是在多约束条件下对飞行器进行航迹规划，往往受到地形、天气情况等因素的影响，很难预先获得精准信息。飞行器在飞行任务时，随着航程的增加，定位过程中的垂直误差和水平误差也随之积累，若误差没有及时纠正，会直接影响飞行任务的成败，文献[8-13]提出飞行器在飞行过程中智能优化算法，但这些智能优化算法由于其计算量随问题维数呈指数增长，难以在复杂环境下规划出优化航迹。文献[14-18]提出基 于即时架构的搜索算法研究，但这些算法降低了算法节点扩展的效率。文献[19]将即时修复式构架与SAS相结合算法(anytime repairing SAS, AR-SAS)，但没有考虑水平误差限及垂直误差的相互制约作用;另外，还要考虑校正次数最少的多目标问题。

近年来航迹规划的传统经典算法有Dijkstra算法、模拟退火算法和人工势场法。文献[20]基于Voronoi图使用Dijkstra算法求最优航迹，文献[21]基于可视图上使用Dijkstra算法求最短航迹，文献[22]同样用Dijkstra算法在三维网络上求最短航迹。诸如这些算法，对于高度差等约束就没有进行优化规划。

综上所述，本文根据各种算法的缺陷去改进，在多约束条件情况下，提出多约束下随机进化因子修正误差的蚁群算法，通过指定的校正点进行误差纠正后，利用信息素对飞行器的航迹进行合理的优化，使得飞行器的航迹最短，同时以减少飞行器通过的误差校正点。重点考虑提高算法的搜索效率和搜索精度。

1 数据处理及问题的约束

1.1 数据处理

针对文献[22]所要求的数据集1中含有306个水平误差校正点以及305个垂直误差校正点和数据集2中含有167个水平误差校正点以及158个垂直误差校正点。飞行器在飞行过程中，每飞行1 m，垂直误差和水平误差将各增加0.001个单位。到达终点时，只有垂直误差和水平误差均小于某确定单位时，飞行器才能按照规划路径飞行。进行垂直误差校正需要此时的垂直误差不大于某确定单位，水平误差不大于某确定单位。进行水平误差校正需要此时的垂直误差不大于某确定单位，水平误差不大于某确定单位。以飞行器从出发点出发，进行误差校正只能寻找与出发点距离小于某确定值的垂直误差点或与发点距离小于某确定值的水平误差点，通过计算可知，符合条件的第一个水平误差校正点有19个点；符合条件的第一个垂直误差校正点有7个点。到达终点时，只有垂直误差和水平误差均小于20个单位时，飞行器才能按照规划路径飞行，因此飞行器要到达终点，必须经过距离终点B 20 000 m以内的校正点，通过计算可知，符合距离终点B为20 000 m以内的水平误差校正点有20个点；符合距离终点B为20 000 m以内的垂直误差校正点有13个点。

同理由数据集2可知，出发点A到终点B的直线距离为：103 045.12 m。飞行器在飞行过程中，每飞行1 m，垂直误差和水平误差将各增加0.001个单位。进行垂直误差校正需要此时的垂直误差不大于20个单位，水平误差不大于10个单位。进行水平误差校正需要此时的垂直误差不大于15个单位，水平误差不大于20个单位。所以飞行器从出发点A出发，进行误差校正只能寻找与A点距离小于10 000 m的垂直误差点或与A点距离小于15 000 m的水平误差点，通过计算可知，符合条件的第一个水平误差校正点6个点；符合条件的第一个垂直误差校正点有4个点。到达终点时，只有垂直误差和水平误差均小于20个单位时，飞行器才能按照规划路径飞行，因此飞行器要到达终点，必须经过距离终点B 20 000 m以内的校正点，通过计算可知，符合距离终点B 20 000 m以内的水平误差校正点有7个点；符合距离终点B 20 000 m以内的垂直误差校正点有3个点。

1.2 问题的约束

该智能飞行器的航迹约束如下。

1)飞行器在飞行过程中，每飞行1 m，垂直误差和水平误差将各增加δ个单位，到达终点时，假设只有垂直误差和水平误差均小于θ个单位时，飞行器才能按照规划路径飞行。

2)飞行器到达垂直校正点时能够进行垂直的误差校正，使得该垂直的误差变为0，另一个类型的误差保持不变。

3)进行垂直误差校正需要此时的垂直误差不大于α1个单位，水平误差不大于α2个单位。

4)进行水平误差校正需要此时的垂直误差不大于β1个单位，水平误差不大于β2个单位。

5)飞行器在转弯时受到结构和控制系统的限制，前进的方向不可以突然改变，因此设定飞行器的最小转弯半径为200 m。

2 多约束下随机进化因子修正误差的蚁群算法

数据集1和数据集2中都含有大量的定位误差校正点，使用蚁群算法对路径进行随机搜索会加大程序的运算量。所以本文计划提前筛选出满足约束条件的第一个校正点集合F和最后一个校正点集合E。当蚂蚁从起点A出发时，只能从集合F中随机挑选一个误差校正点进行定位误差的校正，随后再进行航迹的搜索；当蚂蚁到达集合E中的校正点时，通过引入遗传算法中的选择运算[23]，加大终点B的个体适应度，从而加快算法的收敛速度。算法的具体步骤如下。

第1步：确定模型的决策变量与约束条件。

1)飞行区域中的校正点(Check Point)用集合CP表示：

CP={cp1,cp2,…,cpm}(m∈Ν)

(1)

其中cpi表示飞行区域中编号为i的校正点，这里面的下标i表示数据集1和数据集2中校正点的编号，在数据集1中，m的值为611；在数据集2中，m的值为325。

2)假设飞行器的航迹路线(flight path)由列表FP表示：

(2)

3)校正点cpi(x1,y1,z1),cpk(x2,y2,z2)的欧式空间距离：

(3)

4)校正点cpi是否被规划到了飞行器的航迹路线中：

(4)

5)校正点cpi的类型Type(cpi)：

(5)

(6)

(7)

(8)

(9)

8)若Type(cpk)=0，判断飞行器是否能到达校正点cpk进行误差校正：

(10)

其中1表示飞行器是能到达校正点cpk进行误差校正，0表示不能。

9)若Type(cpk)=1，判断飞行器是否能从校正点cpi到达校正点cpk进行误差校正

(11)

其中1表示飞行器是能到达校正点cpk进行误差校正，0表示不能。

10)判断飞行器是否能从校正点cpi到达终点B：

(12)

第2步：确定蚁群算法模型的信息素更新条件。

设信息素初始分布矩阵为：

τcpicpk(0)=3

(13)

DAB是起点A到终点B的欧式距离，m是飞行区域中校正点的数量。

为了避免残留的信息素过多所导致的启发信息被覆盖[6]，需要令每一只蚂蚁走到下一个节点或成功到达终点时对残留的信息素进行更新。t时刻在校正点cpicpk之间的残留信息更新方程如下：

τcpicpk(t)=(1-ρ)*ττcpicpk(t)+△ττcpicpk

(14)

(15)

判断出现新的路径是否能更新Ccpicpk和DTcpicpk：

(16)

算法中蚂蚁选择下一个误差校正点cpk的概率公式为：

(17)

按照遗传算法的选择策略求得的路径选择概率。

(18)

如果2个校正点中有新的路径产生，则计算该条新路径的校正点数量以及路径长度，由此来决定是否加强该路径的信息素浓度：

(19)

(20)

G为信息素加强的系数等于5 000。

第3步：确定圆弧上符合条件的F点坐标，以及求出圆弧arc(EF)的长度。

由于飞行器在转弯时受到结构和控制系统的限制，前进的方向不可以突然改变，并设定飞行器的最小转弯半径R。这样就不能继续使用二点的欧式距离来定义2个误差校正点的路程，需要计算飞行器到达第一个校正点的入射向量，通过下一个校正点的坐标确定一个平面，同时计算出该平面中与入射向量垂直的向量，并在该垂直向量上找到一个与入射点距离为200的点作为圆心，得出半径为200的圆。飞行路径如图1所示：假设飞行器从点D直线到达下一个校正点E,则校正点E到下一个校正点C的运动轨迹为先以半径200 m圆弧飞行，直到下一个校正点C出现在飞行器航行方向的直线上时，才开始走直线直接到达下一个校正点C。所以需要寻找圆弧上符合条件的F点坐标，该点与下一个校正点构成的直线会相切于圆，并且用于计算到达下一个误差校正点C的入射向量。

图1 飞行器从E点到C点的平面航线示意图

(21)

(22)

因为E到圆心O的距离为r=200，所以联立式(21)和(22)可得出圆心O的坐标求解如下：

(23)

则圆心O点的坐标通过计算可以表示为：

(24)

(25)

求∠FOC的角度β：

(26)

则∝ = 180-θ-β，参照圆心O的求解思路，可求出G点与F点的坐标：

(27)

(28)

所以EF的圆弧长度arc(EF)计算公式为：

(29)

(30)

第4步：确定模型的目标函数。

由题可知该模型的目标如下。目标1：尽可能地使飞行器的航迹长度达到最小；目标2：飞行器经过校正点的数量尽可能少。

由此可知，该问题是一个多目标优化的问题，所以在获得了可行解后，需要对得出的路径进行分析筛选，得出比较好的解决方案。

若通过模型得出的可行路线规划为集合Result:

Result={FP1,FP2,…,FPl}

(31)

(32)

C(FPi)=len(FPi)-2

(33)

其中len(FPi)为求该列表元素数量的函数，由于只需要计算经过校正点的数量，所以需要减去起点和终点。

每种航迹路线的累计路程为：

(34)

目标函数：

min(CAB)

(35)

min(DT(FPi))

(36)

约束条件：

Hcpk≤α1且Vcpk≤α2

(37)

Hcpk≤β1且Vcpk≤β2

(38)

(39)

(40)

加入转弯半径作为新的约束条件，即下一个校正点cpk与飞行器沿圆弧航行的圆心O(x0,y0,z0)的欧式距离需要大于200。

D(cpk,0)≥200

(41)

3 数据仿真

结合遗传算法中的自然选择策略来改进蚁群算法，通过信息素的浓度来分派每个校正点的适应度，在此基础上加入剪枝策略，预先筛选出符合要求的第一个校正点，从而降低寻优过程中的网络维数，加快收敛速度。同时增加处于终点附近的校正点选择终点B作为下一个节点的概率，在数据集1和数据集2中，本文设定模型的参数如下：

α=1,β=1,ρ=0.5,τcpicpk(0)=3,G=5 000

(42)

其中最大迭代次数设定为10 000，蚂蚁的数量为100 000个。运行得出的结果如下。

3.1 数据集1的运行结果

经过计算得出，航迹路线中的校正点数量最少为8个，按航行路程从小到大排序的航迹规划如表1所示，由于模型得出可行解比较多，所以只挑选出前10中的航迹规划。

表1 数据集1的航迹规划表

由表1可知，飞行器通过误差校正点的数量最少为8个，其中最短的航迹路程为105 205.858 7 m。

表1中序号为1的航迹规划示意图如图2及航迹规划结果如表2所示。

表2 校正点最少且航行路程最小的航迹规划结果表

图2 校正点最少且航程最短的航迹示意图

3.2 数据集2的运行结果

在飞行器经过校正点数量最少的情况下，按航行路程从小到大排序的航迹规划如表3所示。

表3 数据集2中校正点数量最少的航迹规划表

由表3可知，数据集2中校正点数量最少且路径最短的航线规划为：

[A,275,104,128,227,305,309,121,123,45,160,92,93,61,B]。

飞行器通过误差校正点的数量最少为12个，其中最短的航迹路程为115 471.921 9 m。表3中序号为1的航迹规划如图3及航迹规划结果如表4所示。

表4 航行路程最小且校正点最少的航迹规划结果表

图3 航行路程最小且校正点最少的航迹示意图

3.3 结果分析

数据集1中不考虑飞行器在转弯半径约束，航线的航程为104 526.940 7 m，一共经过10个校正点。数据集2中不考虑飞行器在转弯半径时，飞行器通过误差校正点的数量为12个，其中航迹路程为104 526.940 7 m。数据集1中考虑飞行器在转弯半径时，航线的航程为105 205.858 7 m，一共经过8个校正点。数据集2中考虑飞行器在转弯半径时，飞行器通过误差校正点的数量为13个，其中航迹路程为115 471.921 9 m。

因为考虑飞行器在转弯半径约束，使得在寻找下一个误差校正点时，除了需要考虑到达该点时的水平和垂直误差是否超过阈值，还要考虑下一个校正点是否处于飞机的最小转弯半径范围内。通过计算飞行器到达每一个校正点的入射角，来确定符合飞机最小转弯半径的圆心坐标，从而求出飞行器在绕圆心航行中脱离圆弧的坐标。由此来计算出飞行器绕圆心航行的圆弧长度和脱离圆弧时到达下一个点的欧式距离，用来定义飞行器转弯性能受到限制的情况下，到达下一个校正点的航程。

4 总结

为了解决蚁群算法容易陷入局部最优解且收敛速度慢的特点，结合了遗传算法中的自然选择策略来改进的蚁群算法，通过改变节点的适应度大小对各节点的信息素进行更新，同时更新2个校正点之间的最短路径的路程和中间节点数量，用此来删除Allowed表中较差的路径，从而加快算法的收敛速度。此外，还引入随机因子来解决陷入局部最优解问题。在进行求解前，通过剪枝使得第一个校正点和最后一个校正点的数量大幅度减少，同时引入的随机进化因子急速地加快了算法的收敛速度。信息素的二次加强为算法寻找最优路径提供方向，在寻找最优解和搜索速度上相互平衡，能够得到一个又快又好的解。通过对模型求解出结果进行分析，进一步地验证了模型的准确性，能够快速地解出符合约束条件的航迹路线，同时与起点A和终点B的直线距离相比，模型得出的航迹路程已经很逼近直线距离。同时模型对于蚁群算法中各个参数的初始设定依赖于别人模型的经验，需要在今后多测试几组参数，尽可能地加快模型的收敛速度，同时能够较准确地得出最优解。结合遗传算法中的自然选择策略来改进蚁群算法，通过信息素的浓度来分派每个校正点的适应度，在此基础上加入剪枝策略，由于剪枝策略的引入，在删除路径时容易错过最优解，且更新一些路径时，会导致飞行器无法到达下一个误差校正点，所以需要更新剪枝的约束条件，让模型在减少节点数量的同时，又不会错过最佳的路径选择。