多无人机任务与航迹规划方法综述

张文博 刘君兰 李瑜 王海林

摘要：无人机具有体积小、灵活性好、经济效益高、操作简单等特点，因此，被广泛应用于民生和军事领域。面对复杂多任务需求，单无人机由于受到载荷数量、储能、单一功能等因素的限制，在执行任务时具有一定的局限性，多无人机协同作业更具优势。任务规划是多无人机协同作业的关键技术之一，主要包括任务分配、航迹规划、数据链路规划、任务载荷规划和应急处置规划等。对多无人机任务分配和航迹规划方法进行简单的介绍和对比，重点就任务分配集中式和分布式方法进行了讲解，分析了多无人机任务规划的進一步的研究方向。

关键词：任务分配；航迹规划；智能优化算法；集中式方法；分布式方法

中图分类号：TP18文献标志码：A文章编号：1008-1739（2022）20-52-5

0引言

多无人机任务规划是指根据无人机需要完成的任务、无人机的数量以及无人机的载荷类型，为各无人机分配任务、规划航线、合理调度，从而达到最大效益。无人机任务规划一般包括航迹规划、任务分配、数据链路规划、任务载荷规划和应急处置规划等。其中，任务分配和航迹规划是关键技术。任务分配的评价指标主要有任务均衡、飞行距离、消耗成本和毁伤代价等。任务分配需要遵循的原则是分配给无人机的任务要和无人机上的载荷相匹配，任务分配要保证任务均衡，尽量避免出现大量无人机“空闲”的情况。

1任务分配模型

多无人机任务分配典型模型有多旅行商模型、车辆路径模型和混合整数线性规划模型。这些模型相对简单，并且研究成熟，能用于表示一些简单的任务规划问题，任务分配如图1所示。

多旅行商模型映射到多无人机任务分配中，就是让无人机从各自起点出发，分别走一段路到达分配的一个或多个目标任务点，保证最终每个目标任务点有且仅只有一个无人机经过，无人机再返回到自身起点，使得总路径最短[1]。

车辆路径模型映射到多无人机任务分配问题上，无人机相当于配送中心，任务目标点相当于客户点。多个配送中心对应多个无人机，决定客户点由哪个配送中心服务相当于决定任务由哪个无人机执行。规划出合理的分配方式以及路径，使得收益最大化。

混合整数线性规划模型就是指拟合的目标函数是线性的，所有的约束也是线性的，同时部分求解的决策变量必须是整数。映射到多无人机任务分配上，就是要合理分配任务给每一个无人机，在满足各约束的情况下，使得任务效益函数值最大。常用求解方法有图解法、匈牙利法和分支定界法等。

2任务分配方法

多无人机任务分配方法根据是否有控制中心分为集中式方法、分布式方法以及二者相结合的分层次分布式方法。

2.1集中式方法

集中式任务分配方法由一个地面站或者中心无人机为每个无人机生成任务序列，通过通信链路将规划结果传递到各无人机上，基于地面站控制的多无人机任务分配如图2所示。集中式方法由控制中心完成规划，能对全局问题进行求解和优化，理论上可获得全局最优的任务分配方案[2]，但集中式方法计算量大、实时性差、动态规划能力弱、对通信网络要求高。

集中式方法主要分为最优化方法和启发式方法。

①最优化方法是将任务分配问题看作一个组合优化问题，主要包括穷举法、混合整数线性法和图论法等。穷举法简单易实现、鲁棒性强，但计算速度慢，适用于小规模任务分配。混合整数线性法根据任务约束条件来构建线性目标函数求极值，该方法精确度高、计算速度快。然而，混合整数线性法对于复杂高维环境，不一定能求出有效解。图论法将无人机与任务的关系映射到图中，通过图来设计合理的分配方案，适用于小规模多无人机多任务分配问题。

②启发式方法就是在一定时间范围内，在解空间中寻找满足各约束条件的局部最优解，主要有列表算法、聚类算法和智能类算法。列表算法给每一个任务构建一个优先级函数，确定任务执行的顺序，分配给每个无人机，适用于有明确优先级的任务分配情况。Levchuk等[3]利用多维动态列表规划方法完成了作战任务中的平台资源分配。聚类算法的目的是使得聚类后类内的节点尽量接近，类之间的节点尽量远离，通过将任务进行聚类，从而形成与无人机数量相等的任务簇，能有效规划出合理的分配方案。Zhao等[4]利用K-means聚类算法实现了多机任务分配。

智能类算法大多通过模仿自然界中生物群体的行为，来寻求最优解，典型算法有遗传算法、粒子群算法和蚁群算法等。

遗传算法是基于生物遗传进化过程的算法，通过交叉、变异和遗传等步骤进一步优化解。该算法不受问题限制，适用性强。遗传算法相较于其他启发式算法，有较好的应用前景和实用性[5]。王超等[6]利用多车场车辆路径规划模型，建立了多无人机多任务规划模型，利用改进的遗传算法对所建立的模型进行分析求解，获得无人机的任务执行的先后顺序以及安全的航迹。吴蔚楠等[7]提出改进分布式遗传算法来适应异构无人机。

蚁群算法是一种模仿蚂蚁觅食行为的算法，利用正反馈寻求最优解。蚁群算法收敛慢、易陷入局部最优解，针对这些缺陷，研究者对蚁群算法进行改进，如保留每次迭代中的最优值，动态调整节点的选择概率，兼顾全局搜索和局部搜索等[8]。苏梅梅等[9]利用启发式蚁群算法求解多任务分配问题，充分考虑了任务分配与路径规划的耦合性，有效地解决了多编队多任务分配和路径规划问题中部分无人机编队“空闲”问题。