基于改进蚁群算法的无人机协同航迹规划研究

吴 蕊， 赵 敏， 李可现

(南京航空航天大学自动化学院，南京 210016)

0 引言

无人机多机协同作战越来越受到广泛关注，将具有不同功能的无人机组成网络化无人机群能大大提高其作战能力。无人机网络的管理模式、作战方式以及如何根据瞬息万变的战场环境任务调度直接决定了作战效率和生存能力［1］。在多机协同作战模式方面，文献［2］提出了一种无人机任务分配的通用模型，该模型能对无人机执行复杂作战任务间的时序约束关系进行有效建模，但该方法未考虑到某个作战任务需要多架无人机共同完成的情况，并且该方法信息传递量大，耦合性强，实用性不高。文献［3］采用了分层规划的思想，将整个动态、大规模、强耦合的优化问题化解为3个层次:航迹规划层、协同规划层和航线平滑层。这种方法可把高维、强耦合的优化问题分解成低维、计算量少、信息交流少的问题［4］，因此降低了规划的难度。其中，航迹规划层作为协同任务规划的关键技术，受到国内外学者的广泛关注。

基于Voronoi图方法在无人机航迹规划方面有着广泛的应用，文献［5］中通过构建作战环境的V图模型，采用遗传算法求解UAV航迹。这种方法能够在空间规模较大的情况下进行，但也存在着效率不高的缺陷。蚁群算法是Dorigo M等人于1991年首次提出，并应用于TSP问题，它是对自然界中真实蚁群觅食机制的模拟，通过引入启发信息和基于正反馈机制的信息素更新机制，提高算法的求解效率［6－7］。由于 TSP问题和无人机航迹规划具有一定的相似性，相比于进化算法，采用蚁群算法求解时不用编码、求解效率高、易于计算机实现。

在研究已有的无人机协同航迹规划方法的基础上，采用层次分解策略，利用Voronoi图构造无人机作战空间模型，根据问题特点对算法要素进行设计和改进。在蚁群算法的基础上，一方面提出带有方向性引导性的信息素更新策略，使其对人工蚂蚁的搜索行为具有更强的引导作用，以提高算法效率;另一方面减少迷失蚂蚁对算法收敛性的影响，有效地提高了算法的寻优能力，以此来对多无人机的协同航迹规划问题进行了研究。

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

压制敌防空火力(SEAD)任务是研究多机协同航迹规划的典型作战任务，如图1所示，其中一个重要目标就是避开威胁。采用Voronoi图来处理多无人机的航迹规划问题，主要因为Voronoi图在计算最佳航迹各方法中是最简单的，其最大优点在于它将航迹规划从无限维搜索问题缩减为有限的图形搜索问题［8］，大大降低了计算量，能够满足多机协同问题的实时性要求。

图1 无人机航迹规划模型Fig.1 UAV path-planning model

若威胁场中存在N个雷达和导弹，则Voronoi图将威胁场分成N个凸多边形。每个凸多边形中仅包含一个威胁，多边形内的任一点到相应雷达站的距离最近。由于是在二维上规划航迹，无人机沿着Voronoi图边飞行时，只考虑两方面代价:一是无人机的燃料限制;二是雷达、导弹等对无人机的威胁代价。

对于第一方面的代价，可以假定无人机以恒速在同一高度飞行，燃料限制与路径长度相关，则第i条路线的燃料代价表示为 wlength，i。

对于第二方面的代价，若假设各威胁对航路的影响因子相同，则各威胁的Voronoi图的第i条边作用效果为无人机到各威胁距离的四次方分之一。威胁模型表示为式中:lr，s是边 L(r，s)的长度;dr，j、ds，j、d1/2，j分别是第 j个威胁距该路径端点r、s和1/2处的距离。

由此，第i条路径的广义航迹代价表示为

其中，系数k表示威胁代价的权重，它反映了航迹规划时决策人的倾向性选择。这样，就得到了一个赋权有向网络图［9－10］。无人机航迹规划的目标就是在满足式(2)的两方面代价的前提下求解多无人机的多条初始航迹，且使得求得的航迹的广义航迹代价最小化。

2 基于改进蚁群算法的多无人机航迹规划算法设计

2.1 算法描述

将蚁群算法用于多无人机航迹规划时，首先将m只蚂蚁放在起始点处，开始沿着由n个威胁构成的Voronoi图边从起始点出发寻找到达目标点的最优主航迹和两条辅航迹。假设迭代NC_max次，在每次迭代的一步转移中，根据Voronoi图的特点，该蚂蚁从当前节点出发，最多有3个下一步可选节点，首先计算每一节点的转移概率，然后用轮盘赌法选择下一节点，这样依次计算选择直到到达目标点，完成一次候选航迹。

由于在每一步的待选点集中，可能存在无穷大节点，或是已经走过的节点，因此蚂蚁很可能在两点之间徘徊无法前进，造成算法停滞，甚至无法得到满足条件的多条初始航迹。为此定义迷失蚂蚁，并令该蚂蚁的本次广义航迹代价为无穷大，即:

当所有蚂蚁完成一次迭代后，首先选出本次迭代的前三优航迹记录保存，再根据目标点信息强度修改规则更新每一节点的生物信息强度，这一过程使得更多的信息素分配到具有更小航迹代价的节点上，有利于蚂蚁更快地寻找到最好的航迹。

2.2 算法实现

1)算法的方向性引导。为了保证在一次迭代中有尽可能多的蚂蚁到达目标点，在目标点处放置一生物信息素源，每时每刻都散发出生物信息激素，吸引蚂蚁向目标点移动。假设目标点散布的生物激素随距离的增加而减弱，且呈倒数变化关系，则可定义目标点信息强度为

式中:A为目标点处生物信息激素源的强度;Rr和Rs分别为节点r和节点s距目标点的距离;lr，s为边L(r，s)的长度，如图1所示。

为了将蚁群算法用于Voronoi图的航迹规划，方便计算各个点的参数值，定义生物信息强度矩阵Τn×5和节点可见性矩阵Ηn×5，其中第r行的Τr和Ηr可表示为

式中:xr，yr为可选节点 r的 x 和 y 方向的坐标;τs1，τs2，τs3为与点 r相连的 s1，s2，s3点的目标点信息强度;ws1，ws2，ws3为与点 r相连的 s1，s2，s3点的广义航迹代价。

2)状态转移规则。第k只蚂蚁按照轮盘赌选择规则，来决定下一步移向哪一个航迹点，如果蚂蚁当前位于航迹点r，下一步可行的航迹点的集合为J(r)，则从航迹点r到航迹点s的转移概率为

式中:τ(r，s)与 η(r，s)分别表示两航迹点的信息强度和启发式信息值;α与β两个常数，分别决定了信息强度和启发式信息的相对影响力，α表示距目标点的相对重要性，β表示能见度的相对重要性。

3)目标点信息强度修改规则。当所有蚂蚁完成一次航迹选择后，必须对各点上的目标点信息强度作一次全面的修正，修正规则为

其中:m为蚂蚁的数量;0＜ρ＜1为信息挥发参数;Δτk(r，s)表示蚂蚁 k 经过边 L(r，s)后的信息强度增量;Q值用来控制信息素的强度;Wk为蚂蚁k本次广义航迹代价。

4)时空上的协同。在协同任务中，各UAV抵达目标执行任务的时间有一定的时间窗要求。若在该时间窗内各无人机都能够到达目标位置，即认为可以完成该协同任务。这里，假设无人机的速度范围为［vmin，vmax］，则无人机到达给定目标点的时间为［tmin，tmax］。那么通过调整无人机的飞行速度即可满足时间协同。同时，由于无人机是依次到达目标点，任意时刻各无人机所处的位置不同，这样既避免了无人机的碰撞，保证了一定的安全距离。

3 算法仿真实例

在Voronoi图上应用改进的蚁群算法求解多无人机的协同规划的初始多条航线，如图1所示敌方阵地大小为70 km×70 km，菱形代表无人机的起始位置，五角星表示目标点，圆点代表雷达、导弹等威胁。在仿真实验中(算法流程见图2)，算法的参数设置如下:NC_max=100，m=30，ρ=0.3，K=0.5，Q=2，A=50。我方出动4架UAV(编号1～4)，分两队分别执行任务1和任务2，各UAV的飞行速度取值范围为［4，6］。测试样本如表1所示。

图2 算法流程图Fig.2 Flow chart of the algorithm

表1 无人机样本参数Table 1 The UAV parameters

图3和图4表示为了完成任务1需要位于不同起始点的UAV1和UAV2出发到达目标点(45，65)执行任务的情况。由于考虑到两架飞机协同的需要，初始情况下应给出3条航迹供无人机选择。其中，图3a为满足约束条件下利用蚁群算法得到各无人机的最优主航迹，图3b和图3c为两条辅航迹。同样地，图5和图6是另一任务下的UAV3和UAV4航迹结果。

表2 各UAV抵达任务目标的时间Table 2 The arrival time of UAVs

图3 任务1中UAV1的最佳3条航迹表示Fig.3 The three optimum paths for UAV1 in task 1

图4 任务1中UAV2的最佳3条航迹表示Fig.4 The three optimum paths for UAV2 in task 1

图5 任务2中UAV3的最佳3条航迹表示Fig.5 The three optimum paths for UAV3 in task 2

图6 任务2中UAV4的最佳3条航迹表示Fig.6 The three optimum paths for UAV4 in task 2

表2为各UAV在［4，6］速度范围内保持一固定速度不变时抵达目标的时间，根据计算结果，在满足最小时间窗下从待选航迹中选择合适的航迹飞抵各自的目标，如图7和图8所示。

图7 任务1中UAV1和UAV2的协同航迹结果Fig.7 The planned cooperative paths for task 1

图8 任务2中UAV3和UAV4的协同航迹结果Fig.8 The planned cooperative paths for task 2

从图中可以看出，一方面各无人机从同一时刻出发，在协同容许的时间范围内到达目标，这样即可满足多机时间协同需要。另一方面在空间协同方面，保证初始时航迹的多样性，图7和图8的航迹虽然存在局部段重合的情况，但由于经过该段的时间不同，故任意时刻各UAV所处位置始终满足空域协同约束。从仿真结果可以看出，引入方向性引导策略的蚁群算法适合多无人机多航迹规划的需求。

4 结论

本文所述将Voronoi图和改进蚁群算法结合起来求解多无人机协同多条航线的方法，发挥了它们各自的优点。仿真实验表明，一方面利用Voronoi图构造的航线集合，可以保证UAV能够回避各种威胁，顺利地飞抵目标点;另一方面说明引入方向性引导的蚁群算法，提高了算法的优化能力，确保利用层次分解策略开始多机多任务规划时，快速找到多条可行航线，完成多任务下的多机协同，并为进一步优化规划结果奠定了基础。

［1］ 冯琦，周德云.军用无人机发展趋势［J］.电光与控制，2003，10(1):9-13.

［2］ SHIMA T，RASMUSSEN S J，SPARKS A G.Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms［J］.Computers ＆ Operations Research，2006，33(11):3252-3269.

［3］ MCLAIN T W，CHANDLER P R，PACHTER M.A decomposition strategy for optimal coordination of unmanned air vehicles［C］//Proceedings of American Control Conference，2000:369-373.

［4］ 宋绍梅，张克，关世义.基于层次分解策略的无人机多机协同航线规划方法研究［J］.战术导弹技术，2004，1(1):44-48.

［5］ 贺涛，谢军，王文娟，等.基于遗传算法的无人侦察机航迹规划［J］.弹箭与制导学报，2010，30(3):210-212.

［6］ DORIGO M.Special section on ant colony optimization［J］.IEEE Trans on Evolutionary Computation，2002，6(4):317-319.

［7］ 金飞虎，洪炳熔，高庆吉.基于蚁群算法的自由飞行空间机器人路径规划［J］.机器人，2003，24(6):526-529.

［8］ MCLAIN T，BEARD R.Trajectory planning for coordinated rendevousofunmanned airvehicles［C］//The Proceedings of the AIAA Guidance，Navigation，and Control Conference.Clearwater，Florida:AIAA，2000:1247-1254.

［9］ 何艳萍，张安，刘海燕.基于Voronoi图与蚁群算法的UCAV 航路规划［J］.电光与控制，2009，16(11):22-23.

［10］ 叶媛媛，闵春平.基于Voronoi图的无人机空域任务规划方法研究［J］.系统仿真学报，2005(6):1353-1355.