一种Q学习引导的进化超启发式方法用于动态多无人机联盟任务规划

《Swarm and Evolutionary Computation》：A Q-learning-guided evolutionary hyper-heuristic for dynamic multi-UAV coalition mission planning

　　

• 提出了一种耦合框架，用于建模动态异质多无人机联盟规划。• 三层编码统一了联盟形成、资源装载和任务顺序。• Q-learning自适应调度进化搜索中的低层算子。• 联盟块交叉与算子爆发增强了继承与搜索能力。

**引言**

无人机集群因其部署灵活、成本低廉、任务适应性强和环境适应性好，已广泛应用于战场侦察、目标打击、灾害救援和监视等复杂任务场景。与单架无人机相比，无人机集群可通过多平台协同和能力互补增强系统鲁棒性，同时减少复杂地形条件下的任务执行限制，从而为多样化任务执行提供新的技术支持[1]、[2]、[3]。在具体军事行动中，无人机集群可显著提升作战能力。然而，在受限环境下的任务分配、资源配置和协同规划方面仍存在诸多挑战[4]。

现有研究通常采用一对一的任务分配方式，即集群中的任务分配给单个无人机。然而，在目标打击等资源密集型任务中，单架无人机可能无法携带足够的资源来独立完成任务。因此，通常需要多架无人机组建联盟，通过联盟内的资源聚合来满足多类型资源需求。因此，在资源和环境约束下，确定合理的无人机联盟数量、为每架无人机配置适当的作战资源，并为不同的无人机联盟分配任务序列显得至关重要。针对这一问题，本研究提出了一种时空与资源受限的异质多无人机联盟任务规划模型，简称STRC-HMCMP。此处，"动态"是相对于预定义的固定联盟而言的，意味着联盟结构由优化过程根据任务需求自适应形成，而非在任务执行期间实时重组。

多无人机任务分配是无人机集群协同任务规划中的基本问题之一。其核心在于建立任务与平台之间的匹配关系，并确定每架无人机的任务执行顺序。现有研究通常将此类问题转化为多旅行商问题（MTSP）[5]、车辆路径问题（VRP）[6]、混合整数线性规划（MILP）[7]或协同多任务分配问题（CMTAP）。例如，Ramirez-Atencia等人将多无人机任务规划建模为约束多目标优化问题，并引入加权进化策略引导搜索朝解空间中的有希望区域进行[8]。邓等人将军事行动场景中的任务分配转化为CMTAP问题[9]。最近，Fan等人将多无人机侦察任务规划分解为目标分配和无人机路径规划，并开发了结合深度强化学习与模拟退火的混合方法[10]。异质平台、多种任务类型和时间窗等也在相关研究中得到了进一步考虑[11]、[12]、[13]。然而，大多数现有任务分配研究仍然聚焦于任务-无人机匹配、任务排序或多个无人机联合执行单一任务。当以联盟作为基本任务执行单元时，联盟内资源协同、资源装载和任务序列之间的耦合关系未得到充分关注。

当单架无人机无法独立满足任务的能力或资源需求时，需要动态多无人机联盟进行协同执行。由于同一联盟内的无人机通常在相同的时空范围内执行任务，动态联盟可以满足任务能力需求并提高资源利用效率。联盟形成在多智能体系统中有着悠久的研究历史。早期的多智能体和多机器人系统研究将任务分配描述为联盟形成问题，即构建智能体子集以满足任务能力需求并提高协同效率。

在无人机任务规划方面，Manathara等人提出了一种用于搜索-打击任务的多无人机联盟形成方法。他们的研究强调，目标打击通常需要多种类型资源的协同使用[14]。Afghah等人进一步发展了面向异质无人机网络的领导者-跟随者联盟形成机制。在该机制中，首先检测到目标的无人机可根据任务资源需求选择合适的成员协同完成任务[15]。随着任务场景和资源类型日益复杂，相关研究已从简单的成员选择扩展到任务分配与资源分配的联合建模，并针对无人机集群系统研究了分布式动态分配机制[16]。例如，Chen等人将异质无人机通信网络中的任务分配与频谱资源分配整合到联盟博弈框架中，利用稳定联盟结构来刻画任务-资源匹配关系[17]。Qi等人提出了一种任务驱动的序贯重叠联盟形成博弈，其中允许无人机将不同资源分配给多个任务联盟，同时考虑了任务执行顺序、任务等待时间和飞行能耗之间的权衡[18]。总体而言，现有动态联盟形成研究能有效处理能力互补和资源匹配问题。然而，大多数研究仍聚焦于联盟形成或任务间资源分配等局部决策。无人机-联盟形成、无人机资源装载和联盟任务序列很少被纳入统一的优化框架中。

从求解方法的角度看，STRC-HMCMP是一个具有高度离散决策和强耦合约束的NP难问题。对于此类问题，早期方法主要采用规则驱动的启发式方法，通过贪心插入、最近邻选择等策略快速构建可行解。这些方法结构简单、计算效率高，但其搜索行为严重依赖人工设计的规则，难以完全捕捉复杂的耦合关系。遗传算法（GA）、粒子群优化（PSO）[19]和差分进化（DE）[20]等元启发式算法也被广泛应用于相关的组合优化问题[21]。例如，郭等人建立了多智能体联盟形成问题的若干变体，并开发了具有启发式初始化和修复策略的遗传算法，以在能力约束下最小化联盟成本[22]。阎等人提出了一种改进的遗传算法来解决多无人机多目标打击中的耦合任务分配与路径规划问题，设计了定制的交叉和变异算子以提高求解效率[23]。翟等人提出了一种基于粒子群优化和熵权法的多异质飞行器协同任务分配方法，利用任务序列编码和任务紧急度更新粒子位置，以满足时敏目标的到达时间要求[24]。然而，元启发式算法的性能通常高度依赖于编码方案和控制参数。固定算子或固定参数机制往往无法在整个迭代过程中维持高效搜索，可能导致探索不足或早熟收敛。

近年来，混合算法成为提高元启发式方法在复杂组合优化问题中适应性的一个重要方向。现有研究将不同的优化机制集成以增强探索、开发或搜索控制。例如，Qu等人将简化灰狼优化器与改进共生体搜索算法结合用于无人机路径规划[25]，而Gupta等人将粒子群优化与郊狼优化算法集成用于三维约束无人机轨迹规划[26]。

强化学习也被嵌入到群体和进化算法中以支持动态搜索控制。Wang等人将强化学习机制引入多群体优化器以提高大规模优化的搜索效率[27]。Li等人进一步发展了基于强化学习的速度向量生成策略与邻域差分变异，以动态协调探索与开发[28]。此外，超启发式方法已与低层启发式算子或问题特定规则相结合以提高搜索策略的通用性。Yuan等人提出了一种面向复杂约束下异质无人机协同任务分配的能量学习超启发式算法[29]。Zhang等人开发了一种面向不确定环境下多任务制造服务组合的超启发式算法[30]。这些研究表明，混合和超启发式框架可以通过组合互补的优化机制来提高搜索性能。然而，大多数现有混合方法仍依赖于预定义的搜索结构、固定的算法组合或问题特定的分解策略。对于STRC-HMCMP而言，主要困难不仅在于全局搜索，还在于处理多样的结构耦合。主导搜索瓶颈可能在不同阶段发生变化，如联盟结构、资源约束、时间窗、飞行范围或种群多样性。因此，需要一种状态感知的高层决策机制来自适应选择适当的低层启发式算子。基于此，本研究将强化学习与超启发式框架相结合，提出了一种基于Q-learning的超启发式算法来解决STRC-HMCMP问题。

综上所述，在多无人机任务分配、联盟形成和智能优化算法方面已取得实质性进展。然而，在复杂战场环境下的异质多无人机动态联盟任务规划中仍存在若干局限性。首先，在建模层面，现有研究通常将任务分配、资源约束和联盟形成分别处理，这些因素之间的耦合关系刻画不足。如果忽略这些耦合关系，规划方案可能在任务分配层面可行，但在实际执行中可能出现资源短缺、飞行范围违规或时间窗违规。其次，在解表示层面，现有编码方法主要关注任务排列、平台选择或联盟划分，难以同时表示无人机-联盟分配、资源装载矩阵和联盟任务序列，这可能在搜索过程中产生大量不可行解，也不利于继承已被验证有效的联盟结构。最后，在求解机制层面，固定算子或单一元启发式搜索方法难以适应不同搜索阶段的优化需求。在搜索早期，任务覆盖更为重要；在中段，应处理主要约束冲突；在后期，应进一步细化效益-成本关系和结构多样性。缺乏状态感知的算子调度机制可能导致算法搜索效率降低、早熟收敛或局部修复能力不足。

针对上述问题，本研究在建模层面统一刻画了异质平台能力、复合任务需求、动态联盟、资源装载与消耗以及禁飞区感知距离。采用分层目标首先确保完成任务数量，然后优化效益-成本比。在解表示层面，设计了一种三层染色体编码结构，以便在统一候选解中描述联盟形成、资源配置和联盟任务序列。在求解层面，构建了两层QLHH框架：高层通过Q-learning根据搜索状态选择低层启发式算子；低层中，所选算子作用于三层编码结构，并通过后代生成和选择机制生成候选子代。由此，可实现强约束动态联盟任务规划的自适应搜索。

本研究的主要贡献总结如下：

（1）提出了一种STRC-HMCMP模型。采用分层目标来刻画完成任务数量、效益-成本比、成本与效益之间的优先关系，因此模型更符合复杂战场环境下多无人机协同任务规划的实用需求。

（2）设计了一种能统一表示联盟、资源和任务序列的染色体编码机制。与仅编码任务排列、无人机选择或联盟划分的方法不同，所提出的三层编码结构同时描述无人机-联盟形成、资源装载矩阵和联盟任务序列，使算法可直接在耦合解空间中搜索。

（3）提出了一种QLHH求解框架。与固定算子或单一元启发式搜索方法不同，所提出的QLHH将Q-learning作为高层算子选择机制。根据状态信息（如任务完成压力、近期改进趋势、主导约束瓶颈、资源稀缺程度和种群结构多样性）自适应选择低层启发式算子。此外，还纳入了状态依赖引导、联盟块交叉、算子爆发、可行性修复和分层奖励机制，提高了算法对强约束动态联盟任务规划的搜索适应性和解的可行性。

本文其余部分组织如下。第2节描述STRC-HMCMP模型，阐述任务、无人机、资源和环境约束的建模方法，并构建相应的目标函数。

第3节设计了QLHH解决方案框架，详细介绍了可行解初始化、低层启发式算子、高层策略学习和后代生成机制。第4节通过多尺度性能分析、简单场景与复杂场景中的详细模拟研究、算法比较以及消融实验，验证了所提出模型和算法的有效性。第5节总结了全文，并讨论了所提方法的局限性及未来研究方向。

STRC-HMCMP任务场景描述
在资源消耗型协同任务中，单架无人机往往受到平台能力和载荷容量的限制，因此难以独立满足复杂任务的复合能力要求和多类型资源需求。因此，需要多架异构无人机形成动态联盟，以实现能力互补和资源聚合。联盟形成后，其成员组成……

QLHH总体框架
为解决上述问题，本研究提出了一种QLHH算法。需要强调的是，Q学习并非直接用于生成任务分配方案，而是作为高层启发式选择策略来采用：根据当前搜索状态，选择合适的低层启发式算子，然后将所选算子作用于染色体（[g,Q,S]），从而在联盟结构、资源装载等方面执行基于扰动的搜索。

模拟实验
为了验证所提出的QLHH在异构多无人机动态联盟任务规划中的有效性，基于第2节建立的STRC-HMCMP模型和第3节提出的QLHH搜索框架进行了模拟实验。与传统的任务分配问题不同，本研究所考虑问题的可行解必须同时满足多个约束条件，包括无人机能力匹配、资源库存、载荷消耗……

结论
本研究在空间限制、资源库存约束以及载荷-航程耦合约束下，研究了多架无人机的动态联盟任务规划问题。此处"动态联盟"指的是在任务规划与优化阶段自适应地形成联盟结构，而联盟成员构成在任务执行期间保持不变；实时联盟分裂、重组或重构不在考虑范围内。

作者贡献声明
Mengji Shi：撰写—审阅与编辑、撰写—原稿、软件、方法学。Xiao Cheng：撰写—审阅与编辑、撰写—原稿、方法学。Yu Wu：撰写—审阅与编辑、项目管理、方法学、概念化。Tong Li：撰写—审阅与编辑、监督、资源。Yuncong Gao：验证、软件、形式化分析。Weihao Li：可视化、软件、资源。Boxian Lin：验证、调查、基金获取。

基金资助
本研究得到中央高校基本科研业务费项目（项目编号ZYGX2026J020）及航空工业集团成都飞机设计研究所预研项目资助。

利益冲突声明
作者声明，他们不存在可能影响本文所述工作的已知的竞争性经济利益或个人关系。

Mengji Shi|Xiao Cheng|Yu Wu|Tong Li|Yuncong Gao|Weihao Li|Boxian Lin