基于改进ACO算法的多UAV协同航路规划*

张耀中，李寄玮，胡 波，张建东

（西北工业大学电子信息学院，西安 710129）

基于改进ACO算法的多UAV协同航路规划*

张耀中，李寄玮，胡 波，张建东

（西北工业大学电子信息学院，西安 710129）

针对无人机（Unmanned Aerial Vehicle，UAV）在执行任务过程中遇到的诸如敌方防空火力、地形障碍及恶略天气等各类威胁源，采用威胁源概率分布的方法进行威胁的量化处理，构建任务空间的威胁概率密度分布图，有效消除了威胁源的差异性。根据UAV在任务飞行过程中的性能约束与时、空协同约束，同时考虑任务过程中UAV的损毁概率最小、任务航程最短，构建了相应的综合任务航路代价最优化目标函数。结合传统蚁群优化算法（Ant Colony Optimization，ACO）在解决此类问题中的不足，给出了相应的改进策略，提出采用协同多种群ACO进化策略来实现多UAV在满足时、空协同约束下的协同航路规划。通过相应的仿真计算表明，改进后的ACO协同多种群进化策略算法更适用于多UAV协同任务航路规划问题，具有一定的实用性。从而为多UAV协同任务航路规划问题的求解提供了科学的决策依据。

航路规划，无人机，蚁群算法，协同进化

0 引言

多无人飞行器（Unmanned Aerial Vehicle，UAV）协同攻击任务规划系统是实现UAV功能互补、发挥多UAV集群作战优势、降低任务之间的复杂耦合程度以及提升UAV执行任务效率的保障，也是多UAV协同攻击所需要解决的关键技术［1-2］。航路规划作为UAV执行任务的基础，能够为UAV提供一条最优航迹，提高UAV的作战效能。合理地规划由起点到终点的任务航路，可使UAV快速有效地完成预定任务。近些年来，随着战场环境、任务难度的变化，多UAV协同航路规划越来越受到重视［3-6］。多UAV航路规划就是在满足UAV性能、战场环境、任务协同等约束条件下，为每架UAV制定从初始点到任务点的飞行轨迹使其任务效能指标达到最优。

目前在航路规划问题的研究上，主要集中在基于单元分解法的UAV航路规划方法，在该方法中具有代表性的求解方法如A*算法、蚁群算法（Ant Colony Optimization，ACO）、元胞自动机方法等搜索方法；基于电磁场理论的人工势场法；路标图法，在该方法中具有代表性的是基于Voronoi图的方法和概率路标图法两种。国外对多UAV协同航路规划的研究主要集中在航路规划方法和航路协调方法方面。如文献［1］提出通过调节各UAV的飞行速度使多UAV在规定的时间范围内到达任务区域，并且使多UAV协同完成信息收集任务的时间最短。文献［3］主要针对任务区中存在突发威胁与固定障碍环境，提出采用模型预测的方法在UAV机动能力下动态规划出最优任务航路。文献［4］针对任务区中存在规避区时的信息收集最大化问题，提出了一种改进的遗传算法来求解任务航路。文献［5］提出了一种基于引力搜素算法与离散粒子群算法混合的最优任务路径规划方法，来解决多移动机器人的最优化路径规划问题。文献［6］针对多UAV协同资源分配最优化问题，提出了一种基于Pythagorean Hodgraphs曲线的几何方法的多UAV协同航路规划算法，取得了较好的效果。文献［7］提出了将基于角度量编码的小生境伪并行自适应遗传算法和人有限干预情况下的智能决策结合起来UAV低空突防航迹规划技术。文献［8］对基本ACO算法采用精灵策略保留每次迭代最优解的基础上，提出了一种适用于航路规划的MAX-MIN自适应ACO算法，在UCAV航路规划中取得了较好的效果。文献［9］以自主驾驶车辆为应用背景，将非完整性约束条件与双向多步扩展RRT搜索算法相结合，提出了一种改进的RRT路径规划算法。文献［10］提出了一种基于Pythagorean Hodgraph曲线的UAV在线航迹生成算法，并给出了高动态环境下多UAV的实时动态避碰规划算法。

通过大量的文献分析可以看出目前相关文献针对航迹规划问题采用了多种改进智能算法，取得了一定的效果［11-15］。本文结合航路规划问题的特点，对基本ACO算法进行了系列改进，并对其进行了仿真验证，仿真结果表明改进后的ACO算法更适用于多UAV协同任务航路规划问题。

1 问题描述

在军事应用中，任务空间中分布着已知或未知的敌方威胁以及地形、障碍和天气等诸多因素，影响着UAV的任务执行过程。因此，UAV航路规划问题不仅需要考虑敌方威胁的变化，还需要考虑战区环境的变化，并将这些信息及时地存储和更新。航路规划的目的是制定UAV的任务路径使其能够更加高效地完成预定任务，可以表示为任务空间中的一系列航路点，相邻航路点之间可以用直线段连接，表示为如下的形式：

其中S表示起始点，G表示终点，Pi表示中间航路点，每一个航路点Pi需要预先知道该点的位置坐标（xi，yi）、航路代价等相关信息。

通常在对抗作战环境中，敌方的防空火力以及地形等因素都会造成UAV的损毁，为了便于分析，本文中采用概率的方法进行威胁的量化处理，将任务空间（x，y）处的威胁定义为UAV被地形障碍或防空火力等因素摧毁的概率。在威胁环境下UAV损坏的概率与地形、威胁分布、威胁强度有着密切的关系［12］。任务区中的威胁源是UAV在任务飞行过程中应当尽量避免进入的区域，假定位于（x，y）处的威胁源Wi在其作用范围内使UAV损毁的概率为fi（x，y），则威胁源可以表示为：

其中pi（x，y）表示威胁源Wi在其作用范围内的威胁分布概率密度函数。

式（2）将威胁源进行了量化，假设各威胁源相互独立，则空间（x，y）处受到n个威胁源作用的威胁值表示为：

式中n表示障碍与威胁源的总数，fi（x，y）与威胁源（或障碍）的特性有关。

式（3）构造了空间的威胁概率分布图（Probabilistic Threat Exposure Map，PTEM），从而消除了威胁的差异性。在PTEM中，将威胁值高于某阈值fr的区域看作UAV的禁飞区，则UAV的禁飞区表示为：

2 UAV航路规划问题建模

2.1 航路代价的表示方法

在UAV航路规划问题中，航路代价是反映航路规划结果优劣的指标，定义UAV在航路中两相邻航路节点的综合航路代价包括威胁代价和航程代价两个部分：

①威胁代价是指UAV在通过航路段时，由于威胁源的存在而损坏的概率，表示为：

式中f（x，y）为威胁源的分布概率密度。

②航程代价是UAV在通过该航路段时的飞行距离，表示为：

定义UAV在航路P中相邻两航路节点上的综合航路代价表示为：

由于UAV在任务执行过程中并不是总能避开全部威胁的，在特定情况下有时候也需要穿越威胁源，在此引入威胁因子δ，表示UAV对威胁的最大承受能力，δ越大表示UAV能承受的威胁值越高。在考虑威胁承受能力的情况下，UAV的综合航路代价可以表示为：

由此可以给出在综合考虑威胁代价和航程代价时的航路规划目标函数为：

多UAV协同航路规划是在UAV航路规划的基础上，综合考虑时间协同和空间协同等约束，使部分UAV能够在允许的时间范围内到达任务区域，且各UAV之间不发生碰撞。对n架UAV进行协同航路规划，使UAV整体的航路代价最小，则根据式（10）有：

2.2 约束条件分析

UAV协同航路规划需要考虑UAV自身性能约束以及多UAV间的协同约束，其中自身性能约束主要包括速度约束、航程约束以及最大转弯角约束，协同约束主要包括时间协同约束和空间协同约束。

2.2.1 速度约束

速度约束限制UAV在任务飞行过程中的速度保持在其最小最大速度之间，表示为：

2.2.2 最大航程约束

最大航程约束限制UAV在执行任务过程中可飞行的最远距离（Lmax），表示为：

2.2.3 最大转弯角约束

最大转弯角约束体现了UAV的转弯机动性能。设UAV在t时刻位于时刻位于，其中△t表示时间步长。设最大转弯角为θmax，则当前时刻位置、下一时刻位置、最大转弯角之间有如下关系：

2.2.4 时间协同约束

对多UAV协同航路规划，时间协同约束要求执行同一个任务的多个UAV都必须在允许的时间范围内到达任务区域，表示为：

2.2.5 空间协同约束

空间协同约束限制了UAV之间的距离，保证UAV之间的距离保持在安全范围之外，避免UAV之间在任务过程中发生碰撞。假设UAV的安全距离为Rs，任两架UAV的飞行位置为，则在全任务飞行过程中要求：

3 蚁群算法原理

蚁群优化算法（Ant Colony Optimization，ACO）是Dorigo于1991年根据蚂蚁觅食行为提出的一种智能优化算法［8，11，18-20］。

式中：

tabuk为蚂蚁Ak已走过的节点；

经过n个时刻，蚂蚁完成一次搜索，各路径上的信息素更新公式为：

3.1 蚁群算法的改进策略

通过国内外研究表明，基本蚁群算法具有计算时间长、收敛速度慢、容易陷入局部最优等缺点，为了有效克服这些缺点，本文给出蚁群算法的改进策略如下：

3.1.1 精英保留策略

在每一次迭代中保存当前的最优值，有效保证下一次迭代的结果不劣于上一步。

3.1.2 自适应航路节点的选择策略

基本蚁群算法在解的产生过程中，通过产生随机数的策略来选择，这种策略选择方法使得算法具有很大的随机性，导致算法收敛速度慢；利用正反馈原理进行选择容易出现停滞现象，导致算法陷入局部最优。将以上两种方式相结合构造节点选择策略，并且在搜索过程中动态调整节点的选择概率，在迭代次数到达一定程度后，适当地加大随机选择概率，从而对空间进行完全搜索［18-19］。

假定在t时刻蚂蚁处于位置i，则其选择位置j的概率可以表示为：

式中：

r为［0，1］中均匀分布的随机数；

r0为动态权值，表示随机选择策略的权值，当r＞r0时，根据pkab的值采用赌轮盘的方式选择j。

3.1.3 自适应调节信息素蒸发因子

由于路径上信息素随时间蒸发，使得那些长时间没有被搜索到的节点上信息素逐步趋于0，降低了算法的全局搜索能力。通过动态改变信息素蒸发因子ρ能够在算法的全局搜索能力与收敛速度之间进行平衡。一种自适应调节信息素蒸发因子的方法为：

ρmax为信息素挥发因子的最大值，防止信息素挥发过快降低算法的收敛速度。

3.1.4 蚂蚁可以选择走回头路策略

基本蚁群算法中，限制人工蚂蚁不能走回头路。但是在威胁区比较复杂的情况下，可能会出现蚂蚁前进的道路上信息素为0，从而使算法停滞。为了避免这种情况的出现，本文中设定蚂蚁可以走回头路，即可以回溯到前几步，并重新进行路径规划。

3.1.5 冗余航路段的裁剪策略

由于引入蚂蚁可以走回头路的机制，蚁群算法在求解的过程中会出现环状路径。此时需要进行裁剪，去掉环状路径。具体方法为：搜索航路中相同的位置，删除相同位置之间的航路。

3.2 改进蚁群算法的程序流程

依据上述改进蚁群算法模型，给出基于改进蚁群算法的航路规划算法流程如下：

Step 1：初始化任务飞行区域内各节点的信息素浓度值，形成一个信息素矩阵T；

Step 2：将m只人工蚂蚁放置在UAV的起始位置等待出发；

Step 3：每一只蚂蚁根据式（20）、式（21）的方法选择下一个节点，最终到达目标点，形成一条可行的航路，假设蚂蚁从当前节点移动到其相邻所有节点所用的时间相同；

Step 4：计算每一只蚂蚁得到的可行航路的目标函数，并保存航路代价最小的航路解；

Step 5：根据目标函数，按照信息素调整策略更新各节点的信息素浓度；

Step 6：判断是否完成迭代条件（达到最小目标函数或者迭代次数），若不满足，则返回Step 2重新执行，若满足，则完成搜索；

Step 7：根据冗余航路段裁剪策略，进行冗余航路的裁剪；

Step 8：输出最优路径。

3.3 多UAV协同航路规划的协同进化蚁群算法

多UAV协同航路规划是在单UAV航路规划的基础上，考虑执行任务的多个UAV之间在空间协同性和时间协同性等的约束关系，使UAV飞行航线在任务空间上能够避免碰撞，在时间上能够在要求的时间顺序内到达任务区域，这是一个复杂的优化问题。在单UAV航路规划方法的基础上，结合协同进化（Co-Evolution）的思想，引入了多蚂蚁种群协作机制，对不同种群内各蚂蚁的状态选择概率进行改进，设计了协同进化多种群蚁群算法（Co-Evolution Multi-Ant Colony Algorithm，CEMACA） 对多UAV协同航路规划问题进行求解。

基于提出的蚁群算法改进策略，结合协同进化思想，引入nv个种群的蚂蚁，先求解每架UAV的航路，不同种群的蚂蚁在进化过程中，维护各自种群的信息素，其间不存在竞争关系。各种群的蚂蚁需要与其他种群的蚂蚁进行空间和时间上的协同，主要表现为：

①各种群的蚂蚁不能实现时间协同时，通过调整其自身选择概率pij，使距离任务区域远的蚂蚁以更大概率选择较近的航路，距离任务区域近的蚂蚁以更大的概率选择较远的航路，设计时间协同系数和时间协同约束条件下的蚂蚁选择概率为：

式中：

ti为从i到终点的剩余时间；

tj为从j到终点的剩余时间；

ti，ave为各种群中蚂蚁到终点的平均剩余时间；

σ为系数调节因子，取较小的正常数；

②各种群的蚂蚁在不能实现空间协同时，通过调整冲突航路的选择概率pij，使蚂蚁对冲突航路的选择概率减小，从而避免UAV之间的碰撞。

协同进化多种群多UAV航路规划结构图如图1所示。

图1 协同进化多种群蚁群算法结构图

协同进化多种群蚁群算法运行流程为：

Step1.初始化各种群ACi，及各种群的相关参数；

Step2.对坌Anti，j∈ACi，执行以下操作：

Step2.1各种群中蚂蚁在每一步中按照式（23）、式（24）构造选择概率pij（m，n），其中m表示蚂蚁当前位置，n表示蚂蚁在当前位置可选择的位置；

Step2.2通过调整pij（m，n），对各种群中对应蚂蚁的位置进行时间和空间协调；

Step2.3各种群的蚂蚁通过式（20）、式（21）选择航路节点；

Step2.4重复step2，直至蚂蚁到达终点。

Step3.对各种群的信息素进行更新；

Step4.从各种群选择满足协同条件的航路。

4 仿真实验

4.1 仿真设定

图2 任务空间威胁分布示意图

图3 任务空间栅格化示意图

构造了具有8个威胁源的任务场景，每个威胁源具有不同的威胁属性和威胁等级，任务空间为40 km*40 km的二维战场环境，如图2所示威胁分布情况。威胁源处的高度信息代表了在当前位置（x，y）处UAV被损毁的概率，为了分析问题方便，将图2所示威胁分布中的损毁概率投影到二维平面中，并对规划空间进行栅格化处理，如图3所示。

仿真采用Intel 2.2 GHz主频、4 G内存的PC机，Windows 7操作系统，Matlab2012b仿真环境。UAV的最大航程Lmax=100 km，UAV的最大转弯角速率△θmax=3°/s。设定算法中蚂蚁数量为20个，迭代次数为50次，初始参数设置分别为：α=5，β=2，Q=10，δ=0，ρ=0.7，θ=0.1，其中：θ为信息素蒸发因子；ρ为搜索因子，随着迭代次数减小。

4.2 改进蚁群算法的单UAV航路规划问题仿真分析

假设UAV的起点坐标为S=（5 km，2 km），UAV需要到达的待执行任务点坐标为G=（30 km，14km）。分别设定改进蚁群算法中的威胁因子δ=0及δ=0.2进行仿真计算，根据设定的初始仿真条件，改进蚁群算法的航路规划结果分别如图4、图5所示。

图4 δ=0时的任务航路规划结果

图5 δ=0.2时的任务航路规划结果

通过仿真分析可以看出，改进的蚁群算法能够快速有效地为UAV规划出较优的任务航路。当设定的威胁因子较大时，UAV能够承受的威胁更大，此时允许UAV穿过威胁区，体现了在任务飞行过程中，UAV对威胁程度与航路代价的协调；威胁因子较小时，UAV能够承受的威胁比较小，此时不允许UAV穿越威胁区，体现了在任务飞行过程中，对UAV的安全飞行要求更高一些。

4.3 改进协同进化蚁群算法的多UAV协同航路规

划仿真分析

假设我方3架UAV，记为U1、U2、U3，其初始坐标分别为S1=（5 km，1 km）、S2=（20 km，1 km）、S3=（30 km，1 km）；有2个需要到达的任务执行点，分别为t1=（12 km，15 km）和t2=（30 km，14 km）；要求U2与U3到达t2，U1到达t1，且3架UAV同时到达任务执行点，UAV之间的空间协同约束为Rmin=1 km，根据本文提出的改进协同进化蚁群算法进行协同航路规划，则多UAV协同航路规划的结果如图6所示。

图6 多UCAV协同航路规划结果

由仿真结果可以看出，各UAV的航路长度分别为15、18、18，满足时间协同约束，U2与U3在到达任务执行点之前的路径点距离能够满足空间协同要求。

4.4 算法的收敛性分析

文献［20］从数学理论的角度对蚁群算法的全局收敛性进行了分析，本文从不同迭代次数中各蚂蚁的平均路径长度分析蚁群算法的收敛性能。对上面给出的仿真设定，改进蚁群算法中的蚂蚁在每次迭代过程中的航路代价随着迭代次数的变化曲线如图7所示。

图7 蚁群算法收敛性分析

由图7可以看出，本文所给出的改进蚁群算法在收敛速度方面明显优于基本蚁群算法，并且改进的蚁群算法能够比基本蚁群算法找到航路代价更小的航路。由此，可以说明改进的蚁群算法效果要好于基本的蚁群算法。通过以上仿真算例的分析可以看出，本文提出的改进蚁群算法具有良好的寻优能力和收敛性。

5 结论

本文针对UAV在执行任务过程中遇到的各类威胁源，如敌方防空火力、地形障碍及恶略天气等，采用概率分布的方法进行威胁的量化处理，构建任务空间的威胁概率密度分布图，有效消除了威胁源的差异性。根据UAV在任务飞行过程中的性能约束与时、空协同约束，同时考虑任务过程中UAV的损毁概率最小、任务航程最短，构建了相应的综合任务航路代价最优化目标函数。针对传统遗传算法收敛速度慢、容易陷入局部最优等缺点，提出了采用精英保留策略、自适应信息素蒸发调节因子以及蚂蚁可以选择走回头路等策略，对传统蚁群算法进行了相应改进，并提出采用协同多种群ACO进化策略来实现多UAV在任务过程中的时、空协同能力，得出了满意的航路规划结果，具有一定的实用性。

［1］KLESH A T，KABAMBA P T，GIRARD A R.Path planning forcooperative time-optimal information collection［C］//American ControlConference， 2008.IEEE， 2008：1991-1996.

［2］SEBBANE Y B.Planning and decision making for aerial robots［M］.Springer，2014.

［3］LEE J W，WALKER B，CONEN K.Path planning of unmanned aerial vehicles in a dynamic environment［M］.AIAA Aerospace，St.Louis，Missouri，2011:29-31.

［4］ERGEZER H，LEBLEBICIOGLU K.Path planning for UAVs for maximum information collection［J］.Aerospace and Electronic Systems，IEEE Transactions on，2013，49（1）：502-520.

［5］PURCARU C，PRECUP R E，IERCAN D，et al.Multi-robot GSA-and PSO-based optimal path planning in static environments［C］//Robot Motion and Control（RoMoCo），2013 9th Workshop on.IEEE，2013：197-202.

［6］SHIN H S，LEBOUCHER C，TSOURDOS A.Resource allocation with cooperative path planning for multiple UAVs［C］// Control（CONTROL），2012 UKACC International Conference on.IEEE，2012：298-303.

［7］任鹏，高晓光.有限干预下的UAV低空突防航迹规划［J］.系统工程与电子技术，2014，36（4）：679-684.

［8］马冠军，段海滨，刘森琪，等.基于MAX-MIN自适应蚁群优化的无人作战飞机航路规划［J］.航空学报，2008，29（B05）：243-248.

［9］宋金泽，戴斌，单恩忠，等.一种改进的RRT路径规划算法［J］.电子学报，2010，38（2A）：225-228.

［10］张毅，杨秀霞，周硙硙.基于速度障碍法的多UAV可飞行航迹优化生成［J］.系统工程与电子技术，2015，37（2）：323-330.

［11］LU J，WANG N，CHEN J，et al.Cooperative path planning for multiple UCAVs using an AIS-ACO hybrid approach［C］//Electronic and Mechanical Engineering and Information Technology（EMEIT），2011 International Conference on.IEEE，2011，8：4301-4305.

［12］SWARTZENTRUBER L，FOO J L，WINER E.Multi-objective UAV path planning with refined reconnaissance and threat formulations［C］//Proceedings of 6th AIAA Multidisciplinary Design Optimization Specialist Conference，2010：1-14.

［13］TSOURDOS A，WHITE B，SHANMUGAVEL M.Cooperative path planning of unmanned aerial vehicles［M］.John Wiley&Sons，2010.

［14］SAMADI M，OTHMAN M F.Global path planning for autonomous mobile robot using genetic algorithm［C］//2013 International Conference on Signal-Image Technology& Internet-Based Systems.IEEE Computer Society，2013：726-730.

［15］EUN Y，BANG H.Cooperative task assignment/path plan

ning of multiple unmanned aerial vehicles using genetic algorithm［J］.Journal of Aircraft，2009，46（1）：338-343.

［16］GAO M，JIANG J，MING N K，et al.Cooperative path planning for UAVs with UAV loss considerations［C］//Computational Intelligence for Security and Defense Applications（CISDA），2013 IEEE Symposium on.IEEE，2013：38-44.

［17］倪天权，王建东，刘以安.交叉粒群算法在无人机航路规划中的应用［J］.系统工程与电子技术，2011，33（4）：806-810.

［18］MONTEMANNI R，WEYLAND D，GAMBARDELLA L M. An enhanced ant colony system for the team orienteering problem with time windows［C］//Computer Science and Society（ISCCS），2011 International Symposium on.IEEE，2011：381-384.

［19］KE L，FENG Z.A new ant colony optimization approach for the orienteering problem［C］//2008 7th World Congress on Intelligent Control and Automation，2008：2027-2032.

［20］段海滨，王道波.蚁群算法的全局收敛性研究及改进

［J］.系统工程与电子技术，2004，26（10）：1506-1509.

Cooperative Path Planning for Multi-UAVs Based on Improved ACO Algorithm

ZHANG Yao-zhong，LI Ji-wei，HU Bo，ZHANG Jian-dong
（School of Electronics and Information，Northwestern Polytechnical University，Xi’an 710129，China）

In this paper，a cooperative path planning method by utilizing improved ant colony optimization（ACO）is presented.In the military domain UAVs usually require the intelligence to safely maneuver along a task path to an intended target，avoiding obstacles such as enemy threats，terrain or bad weather.The method of probability distribution is adopted to deal with such obstacles is adopted. By constructing the obstacles probability density distribution map of the task area the individual diversity of the obstacles effectively can be eliminated.Then according to the flying performance，spatial and temporal constraints of the UAVs，a path cost optimization objective function is proposed by balancing the damage probability of UAV and shortest voyage.For the deficiency of standard ACO algorithm，an improved ACO algorithm is brought that some improvement strategies is put forward for such optimization problems，also a co-evolution multi-ant colony algorithm is proposed to solving the cooperative path planning problems for multi-UAVs.Simulation results show that the improved ACO algorithm can solve the problem effectively，and compared with standard ACO algorithm，it is also more efficiency.

path planning，unmanned aerial vehicle，ant colony optimization（ACO），cooperation evolution

TP391

A

1002-0640（2017）05-0139-07

2016-02-18

2016-05-18

军队预研基金（9140c470xxx14）；西北工业大学研究生创意创新种子基金资助项目（Z2016125）

张耀中（1974- ），男，河南舞阳人，硕士生导师。研究方向：先进火力控制原理，复杂系统的建模与仿真。