多基地多目标无人机协同任务规划算法研究*

潘楠，刘海石，陈启用，颜礼贤，郭晓珏

(1.昆明理工大学a.民航与航空学院;b.材料科学与工程学院，云南 昆明 650500;2.昆明智渊测控科技有限公司，云南 昆明 650500)

0 引言

无人飞行器(unmanned aerial vehicle,UAV) 是一种以自身程序或人在回路控制的不载人飞行器。现代战争中，无人机需对多个目标进行攻击，同时也面临着多个威胁源的威胁，而单机的作战能力有限，因此未来军事斗争中，更多的将是机群协同对地目标的攻击[1]。任务规划是多无人机协同作战任务技术中的重要组成部分，在军事领域，UAV任务规划的主要目的是依据战场环境信息，综合考虑UAV的性能，到达时间、油耗、威胁等约束条件[2]，为每个UAV规划出一条或多条从基地到目标最优或满意的航路，使UAV的生存概率和作战效能达到最佳。多无人机协同作战任务规划分为任务分配和航迹规划2部分，在任务规划的过程中，由于UAV自身的动力特点以及所执行任务的协同性，给解决多目标多基地UAV任务规划问题带来很大的困难，对此，国内外开展了大量的研究。

在UAV协同任务规划技术的相关研究中，无论是航迹优化还是任务分配，智能优化算法都必不可少[3-5]。Voronoi图是由若干个围绕障碍物的共边多边形产生的连接图[6]。文献[7]利用Voronoi图以及粒子群(particle swarm optimization,PSO)算法对单基地单目标进行路径规划，没有考虑多基地多目标。文献[8]利用Voronoi图及快速扩展随机树算法进行航迹规划，并基于博弈策略来选择最优航迹。文献[9]提出一种周期性快速搜索遗传算法(periodic fast search genetic algorithm,PFSGA) 与人工势场法(artificial potential field,APF) 的联合算法，作多基地多无人机任务规划时对航迹没有做圆滑处理，没有考虑到UAV的物理限制。文献[10]提出了基于动态权值的A*算法，并利用其进行航迹搜索，取得了一定的效果。文献[11]提出的任务规划模型中一机攻打多个目标，加大了任务难度，一旦发生意外，便不能很好地完成任务，而且该方法也不能满足现代战争中的同时性。文献[12]中对于飞行空间不作限制，没有考虑到UAV的航路距离约束。Dijkstra算法确定了赋权网络中从某点到所有其他节点的具有最小权的路径[13]。

目前，大多数研究中，没有针对多基地、多目标、多无人机，这对算法的实际应用造成了困难。文献[14]分别对两目标和三目标决策运用多目标优化算法得到了所需结果,目标太少，不能很好体现多目标的复杂性。文献[15]提出利用小生境克隆选择算法为无人机生成满足要求的航路，有效解决了多机航迹规划问题，但是没有进一步进行任务分配。

文献[16]针对传统粒子群优化算法收敛速度慢的问题，改进了粒子群算法，从而得到最优侦察任务方案。虽然以上研究均针对无人机航迹规划问题以及任务分配问题进行了算法的改进，并验证了所提算法的逼近性，但是没有验证算法的均匀性，也没有完成航迹规划与任务分配的耦合。

本文针对多基地、多目标、多UAV协同任务规划问题复杂且耦合的特点，在较为完善的约束条件下提出了一种基于模拟退火粒子群算法的规划方法，先用Voronoi图和Dijkstra算法进行第1重优化找到基地到目标之间的最优化航路，然后再用基于模拟退火的粒子群算法进行再优化，找到一种满意的任务分配方式，通过反馈回来的各UAV的航线长度并根据各UAV的速度，进而控制各UAV起飞时间，从而完成航迹规划与任务分配的耦合，达到协同作战目的。最后仿真结果表明，文中所提算法具有较好的逼近性以及均匀性，符合军事上多无人机执行对地多目标攻击任务的工程应用。

1 问题描述

1.1 问题描述

针对多基地、多目标、多无人机在对地攻击背景下协同任务规划问题，考虑到目标位置以及固定障碍物区域已知，因此，对地攻击任务的关键在于如何保证各UAV航迹的距离最短、威胁代价最小，即整体航迹的最优，以及各目标向各基地派出的无人机数量。

1.2 任务场景

某作战部队有4个基地，分别在不同的区域，各基地分别有6架某型号无人机。某次攻打任务有7个敌方目标群，经侦察得到战场上敌方探测雷达威胁以及禁飞区域、每个目标群的火力情况以及面积，经综合评估攻打任务目标所需该型号无人机的数量如表1所示。其中每次任务所有无人机可不完全出动，并要求4 h内完成攻打任务。

表1 攻击任务评估结果

2 任务规划模型

2.1 模型假设

(1)为了简化模型故将UAV设为质点，不考虑各UAV之间的距离过短产生碰撞。

(2)为了方便数字地图模型的建立，把山体建筑物等禁飞区域简化为圆形。

(3)将飞行空间由三维转化为二维，故各目标群中心位置，基地位置，固定障碍物以及雷达位置如图1示。

(4)在考虑飞机机动性能时仅考虑最大作战半径约束、最小转弯半径约束、最大(最小)速度约束。

(5)如果各飞机航线重合，将采用线性编队。

图1 任务场景示意图

2.2 模型建立

2.2.1 航路代价建模

符号描述如表2所示。

表2 符号描述

由于将作战空间简化为二维空间，故cij为节点j-1 和节点j之间的距离。

(1)

ci则为第i条路线上各小段的求和。当第i条路线有m段时：

(2)

当UAV具有相同雷达反射截面时，其反射雷达回波的强度与到达雷达距离的4次方成反比。为了简化计算，实际上通常取某一段上的几个点进行加权平均。为了让威胁代价更加贴近于真实值，这里取5个点进行威胁代价计算，如图2所示。计算结果为

(3)

式中：l为第i条航迹上，节点j-1和节点j之间的距离，即l=cij；dij1,dij2,…,dij5分别为在某航迹段上所取的5个点到雷达威胁源的距离。

(4)

图2 计算威胁代价取点示意图

由于威胁代价和燃油代价数量级的不同，因而利用线性函数归一化方法对代价函数中的指标进行归一化处理。

(5)

(6)

故目标函数为

(7)

式中：ω1为燃油代价的权重；ω2为威胁代价的权重。

2.2.2 约束条件

(1) 最大作战半径约束，该约束限制了航路的长度。

L≤Lmax，

(8)

Lmax=300 km.

(9)

(2) 最小转弯半径约束，限制生成的航路转弯半径必须大于UAV最小转弯半径，该约束条件取决于UAV的性能。

K≤Kmax，

(10)

Kmax=50 km.

(11)

(3) 最大、最小速度约束，限制飞机飞行的最长最短时间。

vmin≤v≤vmax，

(12)

vmin=25 km/h，vmax=150 km/h.

(13)

3 算法描述

3.1 基于Voronoi图法的航迹规划

(1) 初始化雷达坐标、禁飞区域、基地中心坐标、目标中心位置以及各代价权重。

(2) 根据禁飞区域和雷达坐标生成威胁点。

(3) 根据威胁源的分布情况，用Voronoi图法快速初始化航路，各威胁源连线的中垂线对应了Voronoi图的各边，形成初始航路选择图，此初始航路选择图中边上的各点距离威胁源最远，如图3所示。

(4) 进行航路的再规划：删去超出飞行区域，以及在禁飞区域内的节点，产生安全路径。

(5) 生成代价矩阵：Voronoi图上每相邻的两节点的距离和所有雷达对该段航路的威胁程度构成代价矩阵。

(6) 用Dijkstra算法快速搜索各基地到各目标的最小代价航路。

(7) 用贝塞尔曲线对最小代价航路进行平滑处理。

图3 初始航路选择图

3.2 标准粒子群算法

在PSO算法中，在可行解空间中初始化一群粒子，每个粒子都代表问题的一个潜在最优解，每个粒子都有自己的位置、速度、适应度值，其中由适应度函数计算得到适应度值，其值好坏表示其代表粒子的优劣。粒子在解空间中运动，粒子的速度决定了粒子移动的方向和距离，速度随自身以及其他粒子的移动经验进行动态调整，实现个体在可解空间中找到自己的最好位置，称为个体极值Pbest。粒子群中所有粒子搜索到的适应度的最优值称为群体极值Gbest。各粒子经过不断的迭代过程找到最优解。算法运行过程中，为了防止粒子的盲目搜索，一般建议将其位置和速度限制在一定的区间[-Xmax,Xmax],[-vmax,vmax]。

3.3 模拟退火算法

Metropolis等于1953年提出了模拟退火(simulated annealing,SA)算法。首先对固体物质高温加热，然后慢慢冷却，由高能向低能转变的降温过程成为退火。模拟退火算法，在迭代过程中和粒子群算法用更好的值来代替原来的位置不同，在SA算法中，是以概率接受新状态，所以模拟退火算法可以跳出局部最优。

3.4 基于模拟退火的粒子群算法优化多目标多基地无人机协同任务分配

算法流程图如图4所示。

图4 算法流程图

算法具体步骤：

(1) 初始化参数，设置每个目标被摧毁至少需要的无人机数量、粒子群数量、最大迭代次数、学习因子、惯性因子。

(2) 更新粒子群的个体极值和全局极值。

(3) 根据基本粒子群更新公式，更新粒子群中各粒子的速度和位置；基本粒子群速度更新公式为

vid=w·vid+c1r1(pid-xid)+c2r2(pgd-xid).

(14)

由于任务分配进行的是整数离散粒子群优化，每个粒子的位置表示基地派往目标的无人机数量，所以粒子群位置更新公式为

xid=xid+[vid].

(15)

(4) 计算更新后各粒子的适应度值，记为fi，位置记为xi。

(5) 随机扰动产生新的粒子群x_newi，计算其适应度值为f_newi。

(7) 降温并判断当前是否达到最低温度，如果达到退火结束，如果没有返回步骤(5)继续优化。

(8) 判断当前是否达到最大迭代次数，如果达到，优化结束并输出结果，如果没有，返回步骤(2)继续优化。

4 仿真算例

为了验证本文中基于模拟退火粒子群算法UAV任务规划的有效性，对图1所示的具有3个禁飞区域、10个威胁源的战场环境利用Matlab R2017a进行任务规划仿真。

采用Voronoi图并进行航路再规划之后得到的可飞行路径结果如图5所示。在此基础上，利用Dijkstra算法以及贝塞尔曲线获得最小代价路径并对最小代价路径进行平滑处理，得到最优路径，如图6所示。

图5 基于Voronoi图的可飞行路径

图6 最优路径

当得到最优路径之后，采用基于模拟退火的粒子群算法进行任务分配，得到从各基地到各目标出动的UAV数量如表3所示，从各基地到各目标的航迹长度如表4所示。

表3 从各基地到各目标出动的UAV的数量

表4 从各基地到各目标的航迹长度

采用基本PSO算法、SA算法以及SA-PSO算法一次运行过程中进行对比得到的仿真曲线如图7所示。3个算法30次运行过过程中得到的最优解、最差解以及平均值如表5所示，平均值的仿真曲线如图8所示。

从图7中可以看出，在相同进化次数和粒子群各参数相同的前提下，本文方法得到的代价函数值远低于基本PSO算法。基本PSO算法得到的目标函数的最小值为76.34，标准SA算法得到的目标函数最小值为92.74，而本文方法得到的目标函数的最小值为63.06。从图7，8可以看出，本文所提算法，无论是收敛速度还是收敛精度均要优于PSO算法和SA算法。从表5中可以看出，在3个算法运行30次的过程中，从最优解、最差解以及平均值3个指标中任一指标来看，本文所提算法的结果均为最优。因此可以得出结论，本文所提算法在解决多基地、多目标、多无人机任务规划这类大规模优化问题时，具有较快的收敛速度以及较高的收敛精度，SA-PSO算法具有较强的稳健性、均匀性。

图7 代价函数值随时间变化曲线

指标算法PSOSASA-PSO最优解56.41479.42856.351最差解94.80996.30666.528平均值76.01689.33262.689

5 结束语

本文在以攻击任务为背景的情况下，通过对多基地、多目标、多UAV任务规划进行分析，根据威胁点及障碍物分布情况，获得基于Voronoi图的可行路径，然后采用Dijkstra算法以及贝塞尔曲线对航迹进行优化以及平滑处理，得到最优航路，之后根据最优航路并利用基于模拟退火的粒子群算法进行任务分配。文中所述方法能够保证各UAV组成的整体以总燃油代价最小，总威胁代价最小的情况下完成任务，与其他方法相比提高了基本粒子群全局搜索能力，加快了优化的速度，提高了收敛精度。但仍存在一些不足之处，比如对UAV的物理限制不够完善，将作战空间简化为二维空间。下一步的工作是讨论如何在三维空间内，采用文中的基于模拟退火的粒子群算法面对突发威胁时的任务规划。