多目标群多基地多无人机协同任务规划*

刘 畅，谢文俊，张 鹏，郭 庆

(空军工程大学装备管理与无人机工程学院， 西安 710051)

0 引言

无人机任务规划的目的是找出一条从基地到目标点并且满足某种性能指标的最佳飞行航线[1-2]，在众多约束条件下完成各项任务。任务分配[3-4]和航迹规划[5-6]是任务规划中的核心问题。无人机任务规划问题可由智能优化领域的许多方法进行求解，目前研究的方法有蚁群(ACO)算法、遗传算法(GA)等。GA作为群智能算法的典型代表，已广泛用于无人机任务规划领域。文献[7]在求解过程中由于其搜索的随机性，产生许多劣质搜索过程，导致求解效率和精度不高。文献[8]中运用ACO算法很好地实现了多无人机协同任务规划，ACO算法威力的发挥取决于数学问题的规模。

文中针对多目标群多基地多无人机协同任务规划问题，同时考虑任务分配和航迹规划，将共同分配策略引入任务规划中来，同时提出“双重优化”思想，运用贪心算法对群内路径进行第一重优化，对构建的基地和目标群中心位置坐标的中心无向图用PFSGA进行第二重优化。为提高搜索速度和解的精度，PFSGA通过引入最优搜索算子对种群进行快速搜索，寻找最优解。

1 问题描述

某无人机作战部队有4个无人机基地且每个基地均装备2架R系列无人机，主要遂行侦察任务，需要完成10个目标群的侦察任务，每个目标群包含数量不等的地面目标，巡航飞行速度为200 km/h，最长巡航时间为10 h。

为了使问题简化，文中作如下假设：

1)每架无人机都在固定的巡航高度飞行，从而无人机之间没有冲突；

2)飞行空间没有任何限制、燃油充足；

3)所有目标的优先级都是一样的，即没有执行次序的差别；

4)无人机经过目标，任务即完成。

基于以上假设可把无人机任务规划问题简化为二维平面上的旅行商问题进行求解，即无人机侦察时需遍历各目标群和各目标群内的节点。各目标群中心位置坐标和各无人机基地坐标如图1所示，黑色实心原点为各目标群中心位置坐标，方块为各无人机基地坐标。

图1 基地和目标群中心位置坐标

2 多目标群多基地多无人机任务规划数学模型

2.1 各目标群内任务规划数学模型

Dantzing等人在1959年提出TSP问题，并将其用数学方法进行描述[9]。TSP问题描述的是某旅行者由起点出发，遍历各需求点之后，最后再回到起点的最低代价[10]。文中在求解中，需从某点出发，遍历所有目标群中的节点，但不需回到原点，因为无人机完成一个目标群的侦察将会立即前往下一个目标群进行侦察。即在给定图G=(V,E,W)中，其中V为顶点集合，V=n，n为各目标群含有的目标数目，E为边集合，W为边权函数，求集合{1,2，…，n}的一个全排列使得下式最小。

(1)

TSP问题求解有多种方法，如蚁群算法[11]、模拟退火算法[12]、PSO算法[13]等。文中采用贪心算法求解。首先构造距离矩阵，任意节点到自身节点的距离为无穷大，借助距离矩阵将TSP问题求解简化，在第一行找到最小项a[1][j]，从而跳到第j行；再跳到第j行最小值a[j][k]，再跳到第k行进行查找，以此类推。然后构造各行、各列允许数组，即row[n]={1,…,1}，column[n]={0,1,…,1}，其中1表示允许访问，即该节点未被访问；0表示不允许访问，即该节点已被访问，如果该行该列不允许访问，则跳过该节点访问下一节点。

由于已有TSP问题的求解算法不能在多项式时间内得到最优解，已经被证明是一个典型的NP-hard问题[14]。故无需证明其贪心选择性质，只需找到近似解，并在多项式时间内结束。由于目标群中目标点的个数较少，因此求解速度较快，并且能得到最优解，即初步的最佳路线。

由于无人机在侦察时有一定的侦察范围，实际上只需要初步的最佳路线所包含的目标点在有效侦察区域即可。此外，为减少无人机转弯次数，需要对路线做相应的平滑处理以满足实际需要。根据侦察机有效侦察范围，做出某一目标群中各个目标的有效侦察区域，如图2所示。

图2 各个目标的有效侦察区域图

为侦察到所有目标，只需要以一定的角度到达有效侦察范围即可。故此问题的优化转换为求经过所有圆域的最少线段数。采用下述算法对初始路线进行优化。

①根据TSP问题得到的解，从初始点到终点，依次选取3个点A、B、C，通过3个点构建三角形ABC；

②判断B与AC的距离是否在有效侦察范围内，如果在有效范围内，则去掉B点，如果不在，则整体往下推移一个点；

③如此反复，直到最后无法缩减；

④最后没有被去掉的点，即为优化后的路线。

对于飞机转弯所多花的时间，根据文献[15]提出的Ω形转弯方法，计算额外时间花销，每个转弯多出3.2 km，换算出一个转弯补偿的时间为0.016 h。按照上述算法，无人机在侦察完所有目标需要转弯的次数为6次，则转弯补偿的时间为0.144 h。根据各自的路线解算得出侦察各目标群所花的时间(h)如表1所示。

2.2 目标群间无人机任务规划数学模型

2.2.1 任务共同分配策略

共同分配是将共同分发任务策略引入到任务规划中来，指具有指挥权的大型无人机基地主导的协作型任务分配，即由具有指挥权的大型无人机基地统一集中任务，再将任务分配给参与合作的无人机基地，它们共同协作完成任务。共同分配策略具有如下优势：①任务由多基地配合完成，可减少一个基地需完成任务的数量，确保所有任务顺利完成；②可实现战场态势的共享与快速反馈，更好的适应未来战场需求。

2.2.2 目标函数及数学模型

无人机在执行侦察任务时，需保证无人机滞留防御方雷达有效探测范围内的时间总和最小[16]，才能提高无人机的生存概率，即无人机从基地起飞到回到基地的总时间最少，由于R系列无人机全程匀速飞行，时间与路程成正比，故可以令无人机的飞行路径总长最短。目标函数的优化包括总路径代价和多基地协调调度合理化代价。

假设4个基地向N个目标群(编号为i=1,2,…,N)分配R系列无人机，在第i个目标群的滞留时间为qi，目标群的中心位置坐标为(xi,yi)；4个基地的坐标分别为(x11,y11)、(x12,y12)、(x13,y13)、(x14,y14)，无人机每千米飞行消耗的代价为pck，每架无人机的固定代价为wk。

1)出动无人机的总路径代价

无人机的固定代价和变动代价共同组成出动无人机的总路径代价。无人机固定代价一般包括地面站操控员工资、无人机折旧费用、无人机制造成本等代价，为了使代价函数简化，文中的固定代价特指出动无人机所需承担的固定代价。假设基地拥有K架无人机，记第k架无人机的固定代价为wk(k=1,2,…,K)，则出动无人机架次的总固定代价为：

(2)

式中:sk为0-1决策变量。若sk=1，表示基地的第k架无人机出动，否则sk=0。

对于出动无人机的变动代价方面，包括无人机的维修保养、航油油耗等代价，为了使问题简化，文中只计算航油油耗代价，此代价大致上同无人机所飞行的路径长度成正比，其变动代价可以表示为：

(3)

式中:xijk为0-1决策变量。xijk=1表示目标群i和j节点之间有飞行计划，否则xijk=0。dijk为目标群i和j节点之间的航路长度。

2)多基地协调调度合理化代价

在多无人机任务规划时，还要充分考虑侦察无人机等存储资源和基地设施的不确定性，主要是由执行任务的无人机、地面站操控人员的不确定性引起的。为解决此问题，按照“少出动架次”原则合理运用基地无人机架次。特别是在无人机架次非常少、调度合理化与出动代价有一定关系的情况下，应最大程度上减少出动架次以充分利用无人机的侦察载荷资源。

在基地无人机架次比较紧张的情况下，合理进行任务规划和优化调度，对各基地出动架次和降低无人机执行任务的代价是极其重要的。

如图3所示，基地到目标群1和目标群2的距离分别为400 km和500 km，目标群1和目标群2之间的距离为900 km，目标群1和目标群2需要侦察载荷量均为0.5 t。基地有两架无人机可供使用，侦察载荷量均为1 t。若不考虑调度合理化代价，则可行的侦察方案有两种，分别为：①由两架无人机分别侦察两个目标群；②由一架无人机侦察，一次性侦察两个目标群。

比较这两种方案，虽然无人机总的航行距离是一致的，均为1 800 km，但是当基地无人机数量有限时，若采用方案①，则该基地可继续出动的无人机为0架；若采用方案②，则该基地可继续出动的无人机为1架。虽然只有一架的差别，但是在实际作战中考虑调度合理化是十分必要的。

因此文中在构建目标群间任务规划数学模型上引入“调度合理化代价”，其可表示为：

(4)

式中:c为调度代价系数；λ为放大因子；qi为侦察每个目标群需要的载荷量;Lk为无人机的固有载荷量。

综上所述，多目标群间无人机任务规划目标函数的数学模型为：

(5)

3 周期性快速搜索遗传算法

3.1 GA

GA是从一个问题的解集(种群)开始搜索的，解集中的每个解是由基因经特定编码构成的个体，由一定数目的个体组成种群[17]。GA的计算流程如下：①编码。编码方法是GA的关键步骤，既决定了染色体排列形式，又决定了个体的解码方法。②生成初始种群。③适应度值计算。个体的优劣性通过适应度函数值大小来表示，通常情况下，把目标函数的倒数作为适应度函数。④选择、交叉与变异。通过选择算子、交叉算子和变异算子执行此操作。如今，对GA的改进研究很多，如何有效配合使用选择、交叉和变异操作是当前的重要研究内容[18]。⑤终止。算法的终止条件为种群适应度不再上升或迭代次数已达到预设次数。⑥解码。最优个体经解码得到解决实际问题的方案。

3.2 PFSGA思想

仿照自然界生物进化的“突变学说”思想，地球每经过一次灾难，原有生物会发生退化，尔后新的物种会出现，如此循环往复，生物的种类、复杂性会有所增加[19-20]。PFSGA的设计思想模拟自然界周期性往复“进化-退化”的特点。为了能够保证算法朝着适应度函数值增加的方向进化。文中将GA中的选择算子进行改进，设计了最优算子，包括最优逆转序列算子和最优插入点算子，如图4所示。对于最优逆转序列算子，随机选取两个最优逆转点，如果将两点之间的序列反序能使种群适应度增加，则将其逆转，同时修改适应度值，否则相当于复制操作；对于最优插入点算子，随机选取两个最优插入点，如果将一个点插入到另一个点的前边能使适应度增加，则执行此操作，同时修改适应度值，否则相当于复制操作。目的是使种群适应值增加或不变，即保持种群进化。在种群进行重组的过程中始终保留适应值最大的个体，再通过自适应交叉、变异算子以一定的概率对种群进行演化，使种群发生暂时的退化，如此循环往复进行进化，即为PFSGA的一个进化周期，经过若干个这样的周期，最后可求得最优解。

3.3 PFSGA计算流程

首先要确定所研究问题的种群规模N，其次随机生成一定数量的由基因编码构成的个体组成初始种群，最后计算初始种群中每个个体的适应度函数值，保留初始种群中适应度函数值最高的个体，为在一个进化周期里重组种群使用，同时给定满足实际问题的进化周期数和一个进化周期所包含的进化代数。若进化周期数不满足设定的次数，并且一个周期所包含的进化代数也不满足给定的次数，使用文中设计的最优算子对初始种群进行选择操作，使种群发生暂时的进化，经过若干进化代数重新组成了新的初始种群；若重新组成的种群中个体的适应度函数值优于先前保留的个体，则将其替换，保留适应度函数值更高的个体。为了在下一进化周期前重组种群，由于种群的规模为N，按照锦标赛选择策略(竞赛度为2)从初始种群中继续选择N-1个个体组成新的种群，最后为了使种群发生暂时的退化，通过交叉、变异算子以一定的概率执行遗传操作重组种群，从而进入下一进化周期。周而复始，经过若干个这样的进化周期，就可以得到最优个体，经解码即可得出满足实际问题的最优解。PFSGA计算流程图如图5所示。

图5 PFSGA计算流程图

4 仿真算例

4.1 PFSGA的算例分析

10个目标群均配属雷达，一旦无人机进入某一目标群雷达探测范围，10个目标群的配属雷达均开机对空警戒和搜索目标，并采取相应对策，可能对无人机发射导弹予以摧毁，故无人机滞留目标群雷达探测范围内时间越长，被摧毁的可能性就越大。现需为R系列无人机完成10个目标群，共68个目标的侦察任务拟制最佳的路线和无人机调度策略，以保证无人机滞留雷达有效探测范围内的时间总和最小。

PFSGA的进化周期数设为150，种群规模设为100，一个进化周期所包含的进化代数为10。10个目标群分别对应编号(1,2,3,4,5,6,7,8,9,10)，4个无人机基地对应编号为(11,12,13,14)，运行该算法得到最优解为(4,5,9,3,1,10,8,7,6,2)，对应的出动无人机架次最优调度方案为(1,1,1,2,2,3,3,4,4,5)，1对应的无人机基地为11，2对应的无人机基地为12，3对应的无人机基地为13，4对应的无人机基地为14，5对应的无人机基地为11，4个基地派遣5架无人机即可完成侦察。经过解算可得任务规划方案如图6所示。任务规划结果如表2所示。PFSGA得到的种群适应度最优值、平均值和最小值的进化图如图7所示。

图6 任务规划方案图

路径距离/km耗时/h11-4-5-9-11840.784.2012-3-1-121 126.105.6313-10-8-13989.974.9514-7-6-14822.324.1111-2-11658.063.29

从仿真结果可以看出，PFSGA求解任务规划问题时，各基地无人机被分配的任务数量比较均衡，路径规划合理，各基地资源被充分利用，可以满足实际战场协同侦察的需要，验证了模型的有效性和算法的合理性。

图7 PFSGA适应度函数值进化图

4.2 PFSGA与GA、单亲遗传算法的比较

文中首先对同一算例采取GA对其进行求解，最大迭代次数设为1 500，种群规模设为100，分别将变异概率、交叉概率设为0.05和0.8，运行该算法得到最优解为(4,7,8,9,2,5,3,1,6,10)，对应出动无人机的架次为(1,1,2,2,3,3,4,5,5,6)，1对应的无人机基地为11，2对应的无人机基地为12，3对应的无人机基地为13，4对应的无人机基地为14，5对应的无人机基地为11，6对应的无人机基地为12，4个基地派遣6架无人机才能完成任务。相比于PFSGA多出动了一架无人机。其次运用文献[20]中提出的单亲遗传算法(SPGA)对此算例进行求解，最大迭代次数为1 500次，变异概率、交叉概率分别设为0.15和0.6，种群规模设为100，运行该算法可知，4个基地也需要出动5架无人机，但飞行的总路径却比PFSGA飞行的路径多208.71 km，同时侦察完所有目标的耗时也比PFSGA多花费1.04 h。将PFSGA、GA和SPGA分别运行6次，其适应度函数值的比较如表3所示。

表3 PFSGA、GA和SPGA适应度的比较

从表3中可知，参数设置大体相同的情况下，PFSGA所得到适应值更接近最优解，由于设计的最优算子指向性较强，搜索能力强，算法能够快速收敛，易于求得模型的最优解。

5 结论

文中构建了多目标群多基地多无人机协同侦察的任务规划数学模型，基于文中所做的假设可将其简化为TSP问题，同时在求解该问题时做了“双重优化”，第一重优化是运用贪心算法对各目标群群内的目标进行航路规划，第二重优化是运用PFSGA对各目标间的目标进行任务规划。通过仿真算例验证了任务规划数学模型的有效性和算法的合理性，同时通过与GA和SPGA进行比较，可知PFSGA中的最优算子具有较强的搜索能力，该算法收敛性较好，求解效率、精度高，易于求得最优解。在实际中执行侦察时，还应考虑随时出现的各种不确定威胁及已知威胁和地形限制，构建在不确定环境的任务规划决策数学模型。汲取当下人工智能的精华，搭建基于人机混合认知的任务规划系统，提升无人机作战效能。今后要在这两方面进行深入研究。