采用新型蚁群算法的UAV动态航迹规划

李皓婧

(新乡广播电视大学，河南新乡453000)

采用新型蚁群算法的UAV动态航迹规划

李皓婧*

(新乡广播电视大学，河南新乡453000)

航迹规划对UAV完成任务具有重要的意义。为解决突发威胁下的UAV航迹规划问题，提出了一种改进蚁群算法。采用全新的目标吸引策略、引入信息素增量调节因子并将优先级和信息素挥发系数进行组合优化来对基本蚁群算法进行了改进，提高了算法的求解效率，并进行仿真验证。根据战场已知威胁源生成Voronoi加权图，并与所提的改进蚁群算法相结合求解规划空间中的最优航迹。仿真结果表明，利用改进的蚁群算法能够有效地提高收敛速度和寻优能力，可以较好地解决突发威胁下的UAV航迹规划问题，保证UAV能够回避战场威胁，顺利飞抵目标点。

航迹规划;UAV;蚁群算法;信息素;突发威胁

航迹规划是UAV任务规划的重要组成部分，近年来各种优化算法在航迹规划中得到广泛的应用，具有代表性的算法有Voronoi图法［1］，RRT算法［2］，粒子群算法［3］，A*算法［4］，动态规划算法［5］等。这些智能算法均有各自不同的优越性，但由于战场环境是动态变化的，很难预先获得全局精确的威胁信息，涉及到突发威胁下的UAV航迹规划时，这些算法也将不能保证全局最优解，并且可能导致计算时间过长，很难应用于实时规划。蚁群算法［6-7］作为一种随机优化方法，它的搜索特点具有良好的动态特性，这对于航迹规划中的实时航迹规划问题特别有效。另外，在动态问题中蚁群算法具有良好的寻优计算能力，但是时间复杂度的限制使得必须对蚁群算法进行优化，而且算法运算过程其实是一个搜索过程，需要一个已知的可行航迹网来作为研究基础，采用Voronoi图法可以很好的解决这一问题。因此，本文提出了一种改进蚁群算法来解决突发威胁下的UAV航迹规划问题。受人工势场法的启发，采用全新的目标吸引策略;引入信息素增量调节因子，改进信息素更新方式;通过优先级和信息素挥发系数的组合优化，对信息素挥发系数进行调整变化来对算法进行了改进。本文首先根据战场已知威胁源生成Voronoi加权图，然后与所提的改进蚁群算法相结合求解规划空间中的最优航迹。仿真结果表明，利用改进蚁群算法能够有效地提高收敛速度和寻优能力，可以较好地解决突发威胁下的UAV航迹规划问题，保证UAV能够回避战场威胁，顺利飞抵目标点。

1 基于Voronoi图的威胁环境建模

1.1 规划空间及威胁区域建模

Voronoi图应用于UAV航迹规划问题是根据战场环境中威胁的分布情况依次作出相邻威胁源的中垂线，将空间划分成围绕各个威胁源的多边形区域，构建初始可选路径集，确定航迹的走向和航区。然后依据UAV航迹规划的性能指标计算出边界的总权值，最后采用优化算法来获得最优航迹。具有计算速度快，编程相对简易的优点。

本文在整个规划空间中根据威胁源的分布点集将每个威胁源的点的中心位置视为Voronoi图的点集，现在问题简化为在Voronoi图上寻找UAV从起始点到目标点的最小航迹代价可行航迹，将无限维搜索问题缩减为有限的图形搜索问题，大大提高了计算效率，能够满足突发威胁下的UAV航迹规划问题的实时性要求［8］。

1.2 航迹性能指标

通过对UAV的飞行区域进行建模得到任务态势Voronoi图后，还需要确定各段航迹的性能指标。UAV航迹规划不仅要依据预先获得的威胁信息寻找安全的飞行轨迹，而且还要做到从起始点到目标点所用油耗最小。因此，本文采用按最短航迹和最小可探测性指标加权方法作为航迹的性能指标，如下式所示:

式中，J为航迹性能目标函数，又称为广义代价;Jthreat，i为第i段航迹的威胁代价，与可探测性指标相关联; Jfuel，i为第i段航迹的油耗代价，是航程的函数;k为权重系数，表征航路制订人员根据任务安排在制订航路的过程中所做出的倾向性选择，k∈［0，1］。

雷达、导弹等威胁源构成了与其临近的Voronoi边的威胁因素，严格地讲，这两类威胁的原理以及对UAV构成的威胁程度是不同的，但当简化问题时，把两类威胁都看成同类威胁，将导弹威胁近似为雷达威胁，采用和雷达威胁相同的方法来量化处理。

理论上，雷达信号正比于1/d4(d为UAV到敌方雷达、导弹威胁阵地的距离)，UAV的雷达威胁代价是飞过该边的积分。为了简化计算，将每条边均匀地3等分，取两端端点和中间点来代替整条边的代价，如图1所示。

图1 雷达威胁量化图

因此第i条航迹段的威胁代价Jthreat，i可以表示为:

式中，m为雷达威胁的个数，li为第i条航迹段的长度，da，j、d1/2，j、db，j分别代表第j个威胁距离该路径端点Sa、Sb和1/2处的距离。

另一方面是UAV的油耗代价，假定UAV以恒速在同一高度飞行，油耗代价Jfuel，i是航程Li的函数，航程越短，则油耗代价越小，因此第i条航迹段的油耗代价Jfuel，i可以表示为:

此时根据任务态势构造的Voronoi 图就变成了加权Voronoi图，其每条边的代价为Ji，从而建立了UAV航迹规划时所有可行航迹的集合。

2 基于改进蚁群算法的航迹规划

2.1 目标吸引策略

基本蚁群算法求解UAV航迹规划时，启发信息选用了路径段长度的倒数，导致不同位置的航迹点的启发信息差异并不明显，不能很好地引导蚂蚁选择路径，从而降低对最优路径的搜索效率。为了克服上述不足，本文受人工势场法［9］的启发，在蚁群算法中引入人工势场的思想，采用全新的目标吸引策略，并重新定义了路径选择的启发函数。人工势场法航迹规划的基本思想为:为目标点定义吸引势能，威胁点定义排斥势能，UAV在势能的导向下，从起始点出发，避开威胁点，到达目标点。因此，本文采用UAV当前位置到目标位置的距离作为启发信息的一部分，引导对最短路径的搜索，使蚂蚁尽快向目标点移动。同时引入了方向信息，使蚂蚁在寻找路径时受到方向信息的影响，从而克服了基本蚁群算法的不足，更利于得到最优解。改进算法的启发信息函数公式如下:

式中，θ为可选结点b与目标结点的连线与初始终止点连线的夹角。da，end为UAV当前位置到目标位置的距离，其中，(xa，ya)为当前位置坐标，(xend，yend)为目标点坐标。

因此，在t时刻，设蚂蚁k在航迹点a处，则按照下式确定蚂蚁k在下一时刻将到达的节点s:

式中，α为信息素重要程度因子，其值越大，表示信息素的浓度在转移中起的作用越大;β为启发函数重要程度因子，其值越大，表示启发信息在转移中起的作用越大。allowed(a)是第k只蚂蚁由航迹点a出发待访问的所有可行航迹点的集合;τab(t)表示Voronoi图中边ab上的信息素值;r为(0，1)中均匀分布的随机数，ro∈(0，1)，可以动态地调整ro的值。

可见，转移概率pkab(t)与夹角θ的余弦值成正比。夹角θ越小，cosθ的值越大，蚂蚁选择结点b的可能性就越大。通过采用全新的目标吸引策略，可以使UAV在选择下一个节点时能尽快地趋近目标点，并找到最优航迹。

2.2 引入信息素增量调节因子

为了避免搜索的停滞，最大-最小蚂蚁系统［10］将各条路径上的信息素量的值域限制在［τmin，τmax］内。按照其思想，当所有蚂蚁完成一次路径选择时，Voronoi图上的的信息素可以更新为:

式中，

为了增加解空间的多样性，提高蚁群的全局搜索能力，避免出现局部收敛和早熟现象，本文引入信息素增量调节因子δ，根据每个蚂蚁所求得解的质量的不同，对该蚂蚁所经过路径上的信息素自适应地更新。

式中，信息素增量调节因子δ可由下式求得:

以上各式中，Δτab(t)为本次循环产生的信息素增量; Δτkab(t)为本次循环中第k只蚂蚁经过边ab后的信息素增量;num是蚂蚁的总数量，ρ为信息素挥发系数; Q值是一个常数;Jk为第k只蚂蚁选择的航迹广义代价，Jave为蚂蚁在本次循环选择的航迹平均代价。

引入信息素增量调节因子，使得在短时间内可以通过信息素增量上的差别来区分开次优和其他路径，在促使蚂蚁找到最优路径的同时，也大大提高了收敛速度，缩短了搜索时间。首先计算了每次循环以后所有蚂蚁选择的航迹代价的平均值，再跟据个体蚂蚁选择的航迹代价与该平均值之间的差异来对信息素进行相应的改变。实验证明，改进后的蚁群算法比单纯地改变全局最优解或局部最优解路径中信息素的强度具有更好的搜索最优解的能力。

2.3 优先级和信息素挥发系数的组合优化

蚁群算法中，信息素挥发系数ρ的大小直接关系到算法的全局搜索能力及其收敛速度。为了避免算法陷入局部最优，本文引入一个优先级参数，用ξ(0＜ξ＜1)表示。ξ可以分为三级ξ1，ξ2，ξ3，如果一条路径上的信息素浓度过大，则令ξ为一个较大的值，动态地调整信息素挥发系数ρ，使得路径上的信息素浓度越高，挥发越快，信息素浓度越低，挥发越慢，平衡各路径的信息素浓度，使蚂蚁在较大范围内进行搜索。当循环达到一定次数时，令ξ为一常数，使蚂蚁找到最优路径。基于优先级ξ和信息素挥发系数ρ的组合优化如下式所示:

式中，ρmax，ρmin分别是信息素挥发系数ρ的上限和下限，通过设定ρ的最大、最小值，可以避免算法的收敛速度过慢，容易陷入局部最优解。

优先级ξx可由下式给出:式中，x=1时表示该条路径的优先级最高，而当x=3时表示该条路径的优先级最低。经过优先级和信息素挥发系数的组合优化后，使各条路径上的信息素浓度趋于平衡，从而有效地避免算法陷入局部最优。

在信息素挥发系数ρ根据优先级ξ调整变化的同时，信息素τ也随着动态更新，即式(8)变为:

从而通过将信息素挥发因子ρ用随迭代自适应的ρ(t)来代替，提高了算法的全局性。为了提高算法的搜索速度和全局搜索能力，在每次循环搜索结束时，都将最优解保留，作为判断ρ根据路径优先级调整变化的条件。

2.4 改进算法的具体实现步骤

本文采用Voronoi图和改进蚁群算法求解UAV航迹规划问题的具体步骤如下:

Step 1根据战场威胁源分布构造任务态势Voronoi图，并计算Voronoi图中每条边的总代价;参数初始化，对Voronoi图所有边赋初始信息素值;

Step 2将所有蚂蚁置于距离出发点最近的Voronoi图节点，并根据式(4)～式(7)将每只蚂蚁由当前节点移动到可行的相邻节点，直到所有蚂蚁均到达目标点;

Step 3根据式(1)～式(3)计算出可行航迹的代价，并更新所找到的最优航迹;

Step 4对所有Voronoi边的信息素值进行更新，其规则如式(8)～式(11);

Step 5应用式(12)、式(13)调节信息素挥发系数，并根据式(14)对信息素进行更新;

Step 6若满足循环结束条件，即当前迭代次数达到最大值或已经找到最优解，则循环结束并输出计算结果，否则转入Step 2。

2.5 突发威胁下的航迹规划

任务区域的复杂性使得UAV不能预先掌握全部的环境信息。有些威胁源只有当UAV飞抵其附近一定距离后才能获知，因此UAV在遇到突发威胁时的航迹规划具有重要意义［11］。在UAV按原有航线飞行的过程中，若探测到有突发威胁出现，则采用改进蚁群算法进行UAV航迹规划，其步骤如下:

Step 1在UAV执行任务飞行的过程中，若探测到有突发威胁，则转Step 2，否则UAV继续按原航迹飞行;

Step 2更新任务态势Voronoi图和Voronoi图所有边上的启发信息;

Step 3在更新后的任务态势Voronoi图上，使用改进蚁群算法进行航迹规划;

Step 4 UAV按照规划出的新航迹进行飞行。

3 算法仿真分析

为了验证本文所提的改进蚁群算法在Voronoi图中进行UAV航迹规划的可行性和有效性，进行仿真实验，UAV的航迹规划空间为140 km×140 km，UAV的起飞点坐标为(18，18)，目标点坐标为(125，125)，进入敌方防御区域后，UAV需要根据自身所处的威胁环境完成航迹优化计算。利用仿真技术对UAV任务航迹进行了规划，其中各参数的取值分别为:num=40，α=1.5，β=4.5，Q=100，ρmin=0.15，ρmax=0.9，r0=0.75，τmax=9.95，τmin=0.05，最大迭代次数为100。首先针对战场威胁源建立相应的Voronoi图，然后采用本文所提的改进蚁群算法在Voronoi图中进行UAV航迹规划。图2给出了UAV进入威胁区域执行作战任务时的航迹规划结果，图中的点代表雷达、导弹等威胁源、“*”代表UAV出发点、“Θ”代表UAV任务目标点，可行航迹则用实线表示。所得航迹具有较短的航程，同时有效地规避了已知的威胁区域，能够保证UAV迅速、安全地飞抵目标位置，仿真结果表明这种航迹规划方法是可行和有效的。

图2 已知威胁下的UAV航迹规划图

图3为UAV遇到突发威胁后的航迹规划结果。图中的“⊙”代表突发威胁，突发威胁的坐标可以自由设定，本次实验设定为(84，70)。当UAV在执行任务飞行过程中，探测到有突发威胁存在，则更新任务态势Voronoi图，并调用改进蚁群算法进行航迹规划，得到新的可行航迹如图3中实线所示。通过仿真图3可以看出，航迹能有效地避开威胁，并能使航迹代价指标最小。仿真实验中航迹规划的优化时间为5.7 s，能够满足实时性要求。可见，利用改进蚁群算法行航迹规划，可以满足UAV应对突发威胁下航迹规划的要求。

图3 突发威胁下的UAV航迹规划图

图4为生成UAV可行航迹的改进蚁群算法的各代迭代收敛曲线图，其中虚线为各代平均代价收敛曲线;实线为最小代价收敛曲线。从图4可以看出，航迹代价随着迭代的进行，逐渐收敛到全局航迹最小代价，表明改进蚁群算法确实有效可行，保证了求解的多样性，且收敛速度较快。最终获得全局最优航迹的代价为22.89。

图4 改进蚁群算法的UAV航迹规划迭代收敛曲线图

图2、图3中所给出威胁源数量相对较少，且分布较为稀疏，当威胁源的数量增加时，再次用本文所提的改进蚁群算法对其进行航迹规划，最后得到的仿真结果如图5所示。为了验证本文所提的改进蚁群算法在增加威胁源的情况下，对于突发威胁的实时规划依旧可行，增加突发威胁，设定其坐标为(80，60)，航迹规划结果如图6所示。

由图5和图6可见，本文所提出的改进蚁群算法可以有效地解决不同态势环境下的UAV航迹规划问题。

图5 增加威胁源后的UAV航迹规划图

图6 增加威胁源后在突发威胁下的UAV航迹规划图

4 结束语

本文根据UAV航迹规划问题的要求，在研究现有算法的基础上，提出了一种改进蚁群算法，对存在突发威胁情况下的航迹规划问题进行了研究。受人工势场法的启发，采用全新的目标吸引策略，使UAV在选择下一个节点时能尽快地趋近目标点，并找到最优航迹;引入信息素增量调节因子，在短时间内可以通过信息素增量上的差别来区分开次优和其他路径，促使蚂蚁找到最优路径的同时，也大大提高了收敛速度，缩短了搜索时间;采用优先级和信息素挥发系数的组合优化，使各条路径上的信息素浓度趋于平衡，从而有效地避免算法陷入局部最优。仿真实验表明，本文所提出的改进蚁群算法，不但成功规划出了从起始点到目标点的可行航迹，而且有效地躲避了突发威胁，提高了UAV的生存率及作战效率。仿真实验中突发威胁的位置以及起始点和目标点的位置都可以任意设定，此外还考虑了威胁源密集的情况，因而实验具有很强的随机性和可靠性。另外，规划算法非常简单，运算速度快，因而使得UAV在面对突发威胁时能够迅速做出规避动作，顺利飞抵目标点。根据战场威胁的动态特性，对算法进行进一步扩展研究，同样可以有效解决出现移动威胁时的航迹规划问题。

［1］Pehlivanoglu Y V.A New Vibrational Genetic Algorithm Enhanced with a Voronoi Diagram for Path Planning of Autonomous UAV［J］.Aerospace Science and Technology，2012，16(1):47-55.

［2］潘广贞，秦帆，张文斌.动态自适应快速扩展树航迹规划算法研究［J］.微电子学与计算机，2013，30(1):49-52.

［3］单敏瑜，刘以安，倪天权.QPSO在无人机侦察航路规划中的应用研究［J］.计算机工程与设计，2009，30(20):4690-4692.

［4］杜继永，张凤鸣，吴鹏飞，等.无人飞行器航迹规划的工程化稀疏A*算法［J］.计算机应用研究，2013，30(8):1756-1758.

［5］安柏义，曹云峰.基于动态规划的无人机航路优化问题研究［J］.计算机测量与控制，2008，16(8):1177-1179.

［6］Tang X，Zhang P，Jiang B，etal.Ant Colony Optimization Based on Maximum Selection Probability for Path Planning in Unknown Environment［J］.Journal of Computational Information Systems，2012，8(24):10325-10332.

［7］卢斌文，曲东才，杨晓龙.一种基于蚁群智能算法的航迹优化方法［J］.科学技术与工程，2013，13(2):398-401.

［8］税薇，葛艳，韩玉，等.基于混合蚁群算法的无人机航路规划［J］.系统仿真学报，2011，23(3):574-576.

［9］李猛，王道波，柏婷婷，等.基于蚁群优化算法和人工势场的无人机航迹规划［J］.应用科学学报，2012，30(2):215-220.

［10］牟廉明，戴锡笠，李坤，等.求解二次指派问题的最优迭代最大最小蚂蚁算法［J］.计算机应用，2014，34(1):199-203.

［11］刘月，魏瑞轩，刘敏，等.用改进变异粒子算法实现突发威胁下的无人机航迹规划［J］.电光与控制，2010，17(1):22-25.

李皓婧(1980-)，女，汉族，河南新乡人，新乡广播电视大学，云南大学计算机应用专业硕士研究生，高校讲师，研究方向为计算机应用，lihaojing_vip@ 163.com。

Dynam ic Route Planning for UAV Based on Novel Ant Colony Algorithm

LIHaojing*

(The Radio and TVUniversity of Xinxiang，Xinxiang He’nan 453000，China)

Route planning plays an important part in accomplishing task for UAV.Aiming at the route planning problem of UAV with unexpected threats，amethod based on improved ant colony algorithm is proposed.In order to improve the solution efficiency of the algorithm，the new target attract strategy，the pheromone increment adjustment factor and the priority are introduced to improve the basic ant colony algorithm.Simulations are carried out.The weighted Voronoi diagram is created according to the certain threat sources，with the improved ant colony algorithm to search the optimal path in the space.Simulation results show that the proposed method can improve the search speed and the ability in searching the whole best solution of the route planning problem effectively，which is applicable to route planning of UAV with unexpected threats.So，the UAV can avoid the battlefield threats，reach the target point smoothly.

route planning;UAV;ant colony algorithm;pheromone;unexpected threats

C:6140

10.3969/j.issn.1005－9490.2017.01.025

TP391.9

:A

:1005－9490(2017)01－0130－06

2014-08-10修改日期:2016-04-18