无人机蜂群作战任务规划研究现状与展望*

孙 彧，潘宣宏*，戴定成，杨 杰，解学昊

(1.海军指挥学院,南京 210000;2.解放军31102部队,南京 210000)

0 引言

无人机具有低成本、无伤亡、操作简便、灵活可靠等作战优势［1-4］，在近来的局部冲突和战争中大放异彩，因此，各国都加大了对其相关概念技术的研究力度。而无人机蜂群［2］作为一种新型作战样式，主要以大量中小微型无人机为基础单元，根据作战任务搭载对应载荷，通过云计算、大数据、人工智能算法等关键技术形成自主协同的集群［5-6］，在任务规划指令的引导下遂行侦察预警、电子干扰、火力打击等任务［7-8］。

无人机蜂群作战任务规划，是组织实施无人机蜂群作战的核心，对其作战能力的发挥至关重要［9-10］。无人机蜂群作战任务规划通常分为任务分配和航迹规划两个核心部分。无人机蜂群任务分配（task assignment）是在满足环境和任务条件的基础上为无人机蜂群分配一个或一种有序的任务序列，使任务完成最大化和己方损失最小化［1，11-12］；无人机蜂群航迹规划（path planning）则是一个多约束的组合优化问题，其根据任务需求、战场环境、威胁源等约束条件，为蜂群规划出一条最优或次优的安全航迹，以保证作战任务的完成［7，13-16］。

本文按照分类方式、分配模型、典型方法的思路，对比分析了无人机蜂群任务分配方法；按照规划流程、约束条件、规划算法的思路，阐述了无人机蜂群航迹规划方法；展望了无人机蜂群任务规划的关键问题和未来发展趋势。

1 无人机蜂群作战任务规划概念及流程

1.1 无人机蜂群作战任务规划基本概念

作战任务规划是在综合作战环境、作战企图、任务需求、作战资源、作战规则等约束条件情况下，为实现作战目的，运用科学规划方法对整个作战行动进行设计的过程［17-20］。无人机蜂群作战任务规划是以无人机为基础单元，以不同任务载荷为集群划分［21-23］，囊括任务分配、航迹规划、仿真推演等多步流程的作战概念，与传统无人机作战任务规划相比，其更强调蜂群行动协同的优化和群体智能的涌现［5-6，24-25］，是无人机蜂群作战的核心环节。

1.2 无人机蜂群作战任务规划流程

由于无人机蜂群作战无飞行人员直接参与，蜂群按照远程指令完成作战任务，且作战任务规划中各要素互相耦合，约束条件复杂多变。因此，对规划过程的细致性和准确度要求更高。典型的无人机蜂群作战任务规划流程为：1）输入上级作战行动构想，包括战场态势、作战任务、行动设想等；2）根据约束条件进行任务预先分配和航迹规划；3）如果战场态势发生变化，则临机调整任务分配计划；4）对任务规划结果进行仿真推演，如果未达到预期作战目标，则调整行动构想，迭代规划过程；5）如果达到预期作战目标，则输出规划结果，并以指令的方式引导无人机蜂群完成作战任务。无人机蜂群实际作战行动中涉及更为复杂的观察—调整—决定—行动（observe-orient-decide-act，OODA）指挥控制流程［17，26-27］，不在本文作战任务规划的研讨范围之内。

本文的方法介绍涵盖临机任务预先分配、任务分配和航迹规划等各任务规划环节，但分类方式有所不同。

2 无人机蜂群任务分配及典型方法

无人机蜂群任务分配是其任务规划流程的第一步，任务分配是指在给定无人机蜂群种类和数量的前提下，基于战场环境和任务需求，充分考虑无人机各项性能指标，研究如何将合适的任务在合适的时间或合适的地点分配给合适的蜂群，进而形成对应的任务∕目标点序列，最终实现最优作战效能和最小己方代价［1，9，11，13］。不同无人机蜂群通过高效的任务分配可完成综合作战行动。

2.1 任务分配模型

建立任务分配模型是构建任务分配方法的先决条件。根据无人机蜂群所执行作战任务的不同，可以将任务分配模型划分为单任务模型和多任务模型两大类。单任务分配模型是指无人机蜂群共同执行单一任务的分配模型，主要有多旅行商模型（multiple travelling salesman problem，MTSP）［28-30］和车辆路径模型（vehicle routing problem，VRP）［31-33］；多任务分配模型是指多个蜂群协同执行多项任务的分配模型，主要包括动态网络流模型（dynamic network flow，DNF）［34-37］、多维多选择背包模型（multidimensional choice knapsack problem，MCKP）［38-41］、混合整数线性规划模型（mixed-integer linear programming，MLP）［42-44］、合作多任务分配模型（cooperative multiple task allocation problem，CMTAP）［45-47］等。各分配模型主要特点如下页表1所示。

表1 典型任务分配模型及特点Table 1 Typical task allocation model and characteristics

2.2 任务分配方法

任务分配方法在现有分配模型的基础上通过运行计算实现任务分配。根据已有文献资料，无人机蜂群任务分配方法有多种分类方式，按任务规划架构可以分为集中式［48-51］和分布式［52-54］；按分配时机可以分为预先式［55-58］和临机式［59-61］；按任务特性可以分为动态［62-65］和静态［66-69］；按目标数量可以分为单目标［70-73］和多目标［74-78］。任务分配方法的分类方式如表2所示。

表2 任务分配方法Table 2 Task allocation method

2.3 典型任务分配方法

任务分配方法按照共性特点包含数学归纳类、启发类、智能优化类、协商机制类等多种类型方法。

2.3.1 数学规划类方法

数学规划类（mathematical programming）［79-80］方法主要通过构建目标函数和约束条件解决单目标静态预先任务分配问题，该类方法简单易行，但随着问题维度和约束的显著增加，方法会因计算量过大而难以产生最优解。比较典型的有穷举法（exhaustive method，EM）［81-83］、匈牙利算法（hungarian algorithm，HA）［84-85］、分支定界法（branch and bound，BB）［47，86-87］、动 态 规 划 法（dynamic programming，DP）［88-89］等。

穷举法是一种常见的适应函数寻优算法，其原理是枚举解空间中的所有可能解，通过比对找到最优解。穷举法原理简单，易于实现，理论上一定可找到最优解，但面对复杂性较高的问题时，运算量巨大。该方法通常用于求解简单任务分配问题。

匈牙利算法是早期任务分配研究的经典方法，核心是构造并求解分配代价矩阵以实现目标分配，实质是一种指派问题求解算法。该算法实现简单，但容错能力较差，只适合求解单任务分配问题。

分支定界法是一种求解整数规划问题的广度优先算法，其将任务解空间切分为较小的子集，随后计算每个子集目标上下界，并通过不断筛选迭代找到可行解。分支定界法在约束条件较少的情况下能够快速形成最优解，但矩阵计算量过大，对于硬件要求相对较高。

动态规划法将多阶段任务分配问题分解为多个单阶段子问题，并利用各阶段的对应关系分别求解。该方法通过分段式求解降低问题难度，可有效适用多目标分配场景，但其过度简化了分配模型，降低了分配结果可信度。

2.3.2 启发类方法

启发求解最初是应对NP-hard 类问题而提出的概念，即如找不到一个问题实例的最优解决方案，则通过启发式求解方式得到满足基本约束条件的次优解［90］。该类方法计算速度快，兼容性强，但计算量大，对初始数据要求高，一般难以得到理论上的最优解。常见的启发类方法包括遗传算法（genetic algorithm，GA）［47，91］、进 化 算 法（evolutionary algorithm，EA）［47，91］、禁忌搜索法（tabu search，TS）［92-93］等。

遗传算法模拟达尔文进化论中的自然选择和遗传机制，利用遗传算子完成交叉变异过程，通过对解空间进行搜索迭代演化出近似最优解。该方法不受搜索空间限制，具有较强的并行能力，但容易陷入局部最优解。提出一种自适应的遗传算法用于无人机蜂群协同问题求解，较好克服了其局部最优问题；通过算法混合的方式，提升了标准遗传算法的搜索能力，增加了分配精确度；分别从异构蜂群和三维环境为切入点，对分配模型和遗传算法种群进行改进，取得了良好的任务分配效果。

进化算法是一种以进化论为基础，模仿自然界遗传机制进行自适应∕自组织的全局搜索方法，其搜索流程主要包括选择、重组、变异3 个环节，经过多次迭代遗传后，算法选择适应度最强的个体作为最优解。进化算法与遗传算法原理相似，优点为不受搜索空间限制，并行能力较强，在任务分配领域应用较普遍。缺点为易陷入局部最优。目前与其他方法结合是比较常见的改进方法，如文献［47，91，94-95］等。

禁忌搜索法让仿真实体从随机的可行解出发，按照探索方向不断移动，最终选择目标函数变化最大的作为最优分配解，另外算法在探索过程中使用禁忌表规范可能的移动方向，防止盲目迭代造成死循环。相比其他方法，禁忌搜索法探索能力较强、收敛速度较快，分配效率高。

2.3.3 智能优化类方法

智能优化类方法本质是模拟动物种群自交互行为，通过在分配空间内进行顺次迭代找到近似最优解。其特点是计算复杂度低，针对特定问题的自适应能力强，具有全局优化性和智能性，因此，逐渐成为大规模动态多目标任务分配的主流方法。当然，该类方法缺乏显式的数学基础和理论分析，有效的任务分配评价指标较少，分配结果的可信度存疑。典型算法包括蚁群优化算法（ant colony optimization，ACO）［96-98］、粒子群优化算法（particle swarm optimization，PSO）［99-101］等。

蚁群优化算法模仿蚂蚁找食过程的仿生学原理，即将任务分配搜索问题等效为蚂蚁找食过程，通过分泌信息素引导搜索源朝路径最短的方向移动，从而得出最优解。该方法适用于建模困难的任务分配问题，具有较强的可扩展性和泛化搜索能力，但求解速度比较慢，易陷入局部最优。

粒子群优化算法是一种模拟鸟群飞行行为的仿生学智能优化类算法，其通过模仿粒子为寻求历史最优位置而演化聚合的进程来选择解空间，最后利用适应度函数实时评估得到最优解，实现最优搜索。该方法简单高效，易于求解建模困难问题，但分配精细度不高，全局搜索能力差。其中，文献［101］将任务分配变量离散化以适应粒子群求解框架，并考虑距离、角度、时间等因素构造相对成熟的分配函数，实现了高效的任务分配；针对粒子群算法分配精细度差的缺点，文献［102］提出了一种基于变邻域搜索的局部收敛策略，并同步设计了重分配方法，实现了异构蜂群的精确任务分配；文献［100］则聚焦提升全局搜索能力进行算法改进，强化了较高数量无人机蜂群的任务分配能力。

2.3.4 协商机制类方法

该类方法主要通过设预设分布式协商竞价的框架，并使用无人机蜂群自身收益代价模型和数据通信实现任务指派与交换，适合高动态多目标实时分配问题。协商机制类方法简单直观，可操作性较强，分配效率较高，但也存在个体利益与整体最优互相冲突，进而影响分配效果。其典型方法有合同网算法（contract net algorithm，CNA）［103-104］等。

合同网算法将任务分配看成市场交易的买卖过程，通过“招标—投标—中标”（auction-bidaward）的市场竞拍机制模拟分配过程，每个蜂群单机将自身无法处理的任务对外拍卖，由其他单机投标购买，最终以整体最低代价完成最优任务分配。近来，对合同网算法的改进方法层出不穷，如文献［105］通过在原始方法中增加原则性约束条件，实现了复杂条件下的动态任务分配；文献［103］则在标准方法的基础上，设置了相应的拍卖机制，解决了突发情况下任务再分配问题；文献［106-107］也针对相应场景对合同网算法进行了改进。当前该方法绝大多数研究主要面向不完全信息条件下多目标动态分配问题。类似的改进的方法也有许多，如文献［108-110］等。

典型任务分配方法及特点如表3所示。总体而言，无人机蜂群作战任务分配从原始的单任务、小空间、集中式，逐渐向异构型、协同化、多任务方向发展，多种类型方法结合成为主要求解模式。

表3 典型任务分配方法及特点Table 3 Typical task allocation methods and characteristics

3 无人机蜂群航迹规划及典型方法

无人机蜂群航迹规划主要在任务分配的基础上，综合考虑蜂群平台、任务区域、威胁源、打击目标、协同关系等诸多约束条件，规划出从出发点到打击目标点之间的最优飞行航迹，使得己方损失最小化和任务完成最大化［13-16，111-112］。

3.1 航迹规划流程

无人机蜂群航迹规划流程有以下步骤：1）输入任务分配指令；2）设置约束条件，包括蜂群平台自身约束、任务条件约束、战场环境约束等；3）确定目标函数，主要依据侦察识别、干扰佯动、集群打击等具体任务分配指令确定；4）选取相应规划方法生成最优航迹；5）通过仿真推演验证规划航迹的有效性。

3.2 航迹规划约束条件

无人机蜂群航迹规划约束条件大致可分为蜂群平台自身约束、任务条件约束、战场环境约束三大类。其中，平台自身约束包含飞行高度、飞行速度、转弯能力、最小航迹长度、最大航程等无人机性能指标；任务条件约束包括战场威胁、任务载荷、协同关系等作战任务要素；战场环境约束则包括作战时间、战场空间、地形地貌等外部条件。约束条件如下页表4所示。

表4 无人机蜂群航迹规划约束条件Table 4 Constraints for UAV swarm trajectory planning

3.3 典型航迹规划方法

无人机蜂群航迹规划典型算法主要可分为基于图搜索、基于采样、基于智能三大类。

3.3.1 基于图论的航迹规划方法

基于图论的航迹规划方法将无人机蜂群的所有可能航迹点转化为状态空间图，通过初始状态到目标状态路径构成可行航迹［113］。典型方法有单元分解法（cell decomposition，CD）［114］、栅格法（grid method，GM）［115］、路标图法（roadmap method，RM）［116］等。

单元分解法将作战环境切分为若干多边形区域，在区域内联通出发点到目标点形成代价最小的航迹路径。该方法航迹规划的质量取决于多边形区域的细分程度。

栅格法将作战空间分割为多个栅格网格，并通过启发式搜索的方式在栅格中寻找最优航迹。对该方法而言，栅格网格颗粒度的大小往往决定算法的精细程度和内存消耗。现实场景中很少单独使用栅格法进行航迹规划，比较常见的是先用栅格划分规划区域，再利用其他算法搜索求解最优航迹。

路标图法本质上是对作战环境进行采样，综合目标威胁因素和航迹规划空间构建多种类型的路标图，之后通过搜索得到最优或次优航迹。该方法根据图形样式可细分为Voronoi 图［117-118］、概率路标图（probabilistic roadmap，PR）［119］、可 视 图（visible roadmap，VR）［120］等多个子类。Voronoi 图将环境中相邻两个目标点的中垂线连接成多边形网图，特征与元素表征威胁区域，通过权值搜索得到最优航迹；随机路标图将规划目标随机采样生成路标网络，进而把航迹规划问题转化为图搜索问题；可视图规定相邻点和威胁区顶点连线为“可视”，并顺次连接“可视”点得到航迹规划结果。路标图法构造简单、数量级低，可规划出安全性较高的航迹，但规划颗粒度较大，且可选航迹有限。

3.3.2 基于搜索的航迹规划方法

基于搜索的航迹规划方法对航迹规划空间进行搜索评估，进而确定到目标位置的最优航迹点集，最终实现航迹规划。该类方法航迹搜索距离短，因此，规划效率较高。典型的有A*算法（A* algorithm）［121-122］、模拟退火算法（simulated annealing algorithm，SAA）［123-125］、人工势场法（artifical potential field，APF）［123-125］、快速随机搜索树法（rapidly-exploring random tree，RRT）［126］等。

A*算法是一种启发式方法，其通过计算当前点到目标点的实际代价函数值不断扩展搜索选择，最终得出最优航迹，该方法通常用于求解二维或三维环境下蜂群协同规划问题。其搜索航迹短、效率高；同时，由于计算量较大、规划时间较长，算法很难应对大空间复杂航迹规划。其改进点包括多机协同性、环境适应度、规划精度、规划效率等方面。

模拟退火算法是一种基于迭代策略的随机搜索方法，其特点是利用概率的突变性找出目标函数中的最优解，该方法可以有效避免局部最优，鲁棒性较高，但需要复杂的作战环境量化过程。

人工势场法将战场环境中的目标点和威胁区分别定义为对无人机机体产生引力和斥力的实体，并建立对应的势能函数，无人机蜂群通过引力和斥力的叠加合力控制自身运动，并根据约束条件和势能函数进行航迹规划。该类方法无需复杂的搜索优化，计算量较小、实时性强，但易陷入局部最小值，且势能函数需要根据特定场景定制。

快速随机搜索树法的基本原理是先随机采样产生多个节点，再利用节点在任务空间中构建随机树，该方法能够在复杂规划环境中快速找到最优航迹，但易陷入局部最优。其主要应用于考虑平台自身约束的航迹规划问题。

3.3.3 基于智能的航迹规划方法

基于智能的航迹规划方法可分为传统智能和人工智能两大类。传统智能类算法包括粒子群优化算法［127-128］、蚁群优化算法［129-131］、人工蜂群算法［132］及其多种改进型，该类方法将与上述智能优化类任务分配方法相同的搜索原理应用于航迹规划场景。

近年来，利用以深度强化学习（deep reinforcement learning，DRL）［133］为代表的人工智能类方法进行航迹规划成为较为火热的研究方向。该类方法主要基于马尔科夫决策过程（Markov decision process）［134］，利用状态转移对区域进行探索和预测，并使用回报函数训练最优航迹，具有极强的实效性和实时性，非常适合处理复杂未知作战空间的航迹规划问题。比较典型的有Q-learning［135-136］、分层强化学习（hierarchical reinforcement learning，HRL）［137-139］、DQN［140-141］、DDPG［142］、MADDPG［143-144］等。

Q-learning 是一种早期经典强化学习方法，其利用Q 表存储回报值，通过在预定空间内不断试错训练出最优航迹，该方法常用于无人机航迹规划及避障类场景。其缺点为只适合解决离散空间规划问题，难以满足现实作战环境的规划需要。

分层强化学习方法将复杂的规划问题分段为多个简单子问题并依次求解，从一定程度上缓解了强化学习算法难以收敛的问题，但还是无法彻底解决连续动作选择的难题。

DQN 将深度神经网络（deep neural network，DNN）引入经典强化学习算法，使用值函数近似器预估动作，能够较好地模拟连续动作空间航迹规划。该方法的改进型较多，如文献［140-141］等。

DDPG 主要解决两个方面的问题，1）使用策略梯度模型仿真连续动作空间中的动作策略和算法输入状态，通过训练直接输出最优动作，并由连续时间点的动作组合成最优航迹；2）引入Actor-Critic机制，由Critic 网络监督Actor 网络选取最优动作。DDPG 真正意义上实现了连续动作空间的航迹规划，但算法无法体现蜂群间的协同行为，且一旦无人机数量上升极易导致维度灾难而难以收敛。

MADDPG 可以被看作DDPG 算法在解决多智能体环境中竞争合作问题的改进型方法，其核心思想可用集中训练分散执行（centralized training and decentralized execution，CTDE）概括，即使用集中式的神经网络进行统一训练，按照蜂群的组成结构分布式执行，从而可有效提升蜂群间的自主协同规划能力。该方法适合多种类异构型蜂群协同航迹规划，但也存在训练量较大，对硬件需求较高的不足。

典型无人机蜂群航迹规划方法对比如下页表5所示。可以看出，基于图论的方法仅适合二维简单模型的航迹规划，对复杂作战环境的集群规划显得无能为力；基于搜索的航迹规划方法虽然搜索效率高，易得出最优解，但算法模型过于复杂，无法适应复杂的作战场景和规划要素；基于智能的航迹规划方法对于以智能体为基础单元，以无模型训练算法为具体执行对象，较为适合应用于无人机蜂群的编组和协同任务模式，能够以较为简单的模型构建实现蜂群作战灵活编组、群智涌现、动态规划等特性，是无人机蜂群航迹规划较为理想的求解方式和发展方向，具有极高的研究意义和价值。

表5 典型无人机蜂群航迹规划方法对比Table 5 Comparison of typical UAV swarm route planning methods

4 无人机蜂群作战任务规划关键问题及发展方向

由前所述，研究人员在无人机蜂群作战任务规划领域取得了较为丰硕的成果，各类模型方法层出不穷，军事场景的应用也可圈可点，但目前仍有较多关键问题亟待解决。本文分别从场景构设、规划模型、规划要素、推演评估、规划模式等5方面，总结了无人机蜂群作战任务规划的关键问题，并针对各问题方面对该领域的未来发展方向进行展望。

4.1 场景构设方面

场景构设方面的问题主要表现为：1）现有规划方法和仿真环境主要集中在二维空间问题的求解上，对于作战空间、战场环境、约束条件等复杂性要求更高的三维空间，其规划完成度和置信度都不够理想；2）为了降低规划复杂度，现有场景考虑的条件较为简单，大都只包括蜂群实体、任务类型、威胁条件、打击目标等有限要素，虽然简化了问题求解过程，但仿真真实度、全局度较低。

因此场景构设方面的发展方向主要包括：1）三维仿真场景逐渐成为主流，未来无人机蜂群作战任务规划场景构设重点在于研究和完善三维空间下的任务规划求解方法，以增加仿真规划的置信度；2）仿真场景要素更加细致全面，未来无人机蜂群作战任务规划将融入信息条件、体系支撑、地形气候等多类复杂要素，在强大算力和智能化方法的加持下，不断提升任务规划的真实度。

4.2 规划模型方面

任务规划模型方面的问题主要包括：1）现有规划模型和求解方法较为繁多，但不同模型只针对特定场景，很难形成通用的求解范式，这就导致规划模型的适应性和鲁棒性较弱；2）模型参数较为简化，对于多参数模型的研究不足，导致现有模型很难应对多蜂群多任务复杂规划场景。

未来无人机蜂群作战任务规划模型将逐渐向多任务、多场景、综合化的方向发展。即在通盘考虑多种参数指标综合影响的基础上，建立符合实际的标准化任务规划模型，以增加规划的普适性和鲁棒性。

4.3 规划模式方面

当前无人机蜂群作战任务规划自主化水平较低，可以预见随着规划方法与模型的不断迭代演进，智能自主的任务规划模式必将是未来发展方向。同时也应当看见，战争作为一种人与技术的结合体，指挥人员必须拥有最高决策权。因此，在不断建设智能任务规划体系的同时，也应当深入研究如何更好地将指挥人员的经验智慧与机器智能相结合，形成“人在回路”的规划模式，以赢得未来战争的主动权。无人机蜂群作战任务规划关键问题及发展方向对应关系如表6所示。

表6 无人机蜂群作战任务规划关键问题及发展方向对应关系Table 6 Key issues and corresponding development directions for UAV swarm combat mission planning

5 结论

无人机蜂群作战样式是未来智能化、无人化联合作战的重要组成部分，任务规划作为无人机蜂群执行各类作战行动的基础技术，在整个蜂群系统中将发挥举足轻重的作用。本文通过对任务规划流程，以及其中两个重点问题（任务分配、航迹规划）的模型及方法的介绍，深度分析了无人机蜂群作战任务规化的现状以及未来发展方向，以期在未来联合作战中赢得战场主动。