多无人机多目标任务分配问题，我在研究生阶段啃了整整三个月的文献，才终于把这块硬骨头啃出点味道来。这篇笔记是系列整理的第一篇，重点梳理问题定义、建模方式和主流求解算法，顺带记录我自己复现和避坑的经验。如果你正准备进入这个方向，或者被“多对多分配”这种组合爆炸问题折磨过，这篇内容应该能帮你少走很多弯路。

1. 问题定义：多无人机多目标任务分配到底在解什么

1.1 任务分配的数学描述

先把问题说得朴素一点：现在有一群无人机，它们的编号集合是 U = {U1, U2, ..., Un}，这些无人机可能是异构的，有的飞得快但载荷小，有的续航长但速度慢；同时又有一批目标任务点，编号集合是 T = {T1, T2, ..., Tm}，每个任务点有自己的类型、权重、时间窗、所需执行能力。任务分配要做的，就是决定“哪架无人机、在什么时间、按什么顺序，去执行哪些任务”。

从数学角度看，这个问题的标准形式可以写成：

min J = w1 * Σ cost_i + w2 * Σ time_i + w3 * Σ risk_i s.t. 每架无人机的能力约束 每个任务的执行次数约束 时间窗约束 通信约束

这里的 cost、time、risk 都是归一化后的指标，w1、w2、w3 是权重系数，代表指挥员对不同目标的偏好。一般文献里用的目标函数还包括总航程最短、任务完成价值最大、资源消耗最均衡等等。实际工程中很少只优化单一指标，所以大部分论文实际做的是“加权多目标优化”，然后再用帕累托前沿去讨论多组解的折中关系。

我自己的理解是：任务分配不像普通TSP（旅行商问题）那样只求一条最短回路，它更接近“带多重约束的Pickup and Delivery Problem”和“多旅行商问题”的合体。每架无人机对应一个旅行商，每个任务点可能被不止一架无人机覆盖，也可能多架无人机协同完成同一个复合任务（比如先侦察再打击），这就产生了“任务拆分”和“任务协同”的额外维度。这类问题几乎没有解析最优解，绝大多数时候只能靠启发式算法和分布式协商去逼近。

1.2 与单机任务规划的区别

很多人刚开始接触时会混淆“任务分配”和“航迹规划”。航迹规划解决的是“给定起点和终点，怎么走最安全、最省油”；任务分配解决的是“哪些任务给谁做，以及做任务的顺序是什么”。两者虽然经常串联使用，但思考层面完全不同。

单机任务规划的场景里，只有一架无人机、一组按一定顺序排列的任务，核心是求解一条满足约束的飞行路径。这时的决策变量是连续或者离散的点序列，规模小，常用动态规划、A*或者RRT就能处理。但转到多无人机多目标任务分配时，问题结构变成“无人机的组合×任务子集的组合×执行顺序的组合”，这是一个典型的组合爆炸问题。假设有8架无人机和12个任务点，即使不考虑协同和拆分，粗略排列组合数量也远超过常规暴力搜索能处理的范围。

更麻烦的是，多无人机场景下的约束通常是动态出现的。比如无人机A在飞行途中电量告急，原本分配给它的任务需要重新调配；或者无人机B临时被敌方火力威胁，需要立即改变航线。这些动态变化要求分配算法不能是一次性离线算完就完事，而是要在运行中不断循环“感知-分配-执行-再分配”的闭环。这也是“在线任务重分配”成为近些年研究热点的原因。所以我做综述的时候习惯把问题首先按“静态/动态”“集中式/分布式”两个维度分类，再往下看算法。

2. 主流建模方式：从指派问题到市场机制

2.1 基于分布式拍卖的典型流程

多无人机任务分配的建模方式，最经典的源头可以追溯到“指派问题”。举个例子，如果有4架无人机和4个任务，且每个任务只需要1架无人机完成，那这就是一个标准的线性指派问题，直接用匈牙利算法就能得到全局最优解。但实际工程很少这么理想，因为任务数通常不等于无人机数，任务之间存在优先级，无人机的载荷也不一样，于是必须引入更复杂的模型。

我强烈推荐先弄懂分布式拍卖算法（Auction Algorithm），因为它是理解后续很多方法（包括一致性束算法CBBA）的基础。拍卖算法的直观逻辑特别像拍卖场：每个任务被当成“拍卖品”，每架无人机根据自己的边际收益对任务出价，出价最高的无人机获得该任务。为了协调冲突，无人机之间只需要交换各自的出价和胜者信息，最后收敛到一组无冲突的分配结果。

一个典型的分布式拍卖流程可以拆成四步：

1. 初始化：每架无人机维护一个本地任务列表、一个价格向量以及一个胜者列表。初始时这些列表可以是空的。
2. 出价阶段：每架无人机根据本地信息，计算出自己对每个未分配任务的“边际收益”。边际收益可以定义为“如果把这个任务插进我当前任务序列的某个位置，总目标函数能改善多少”。选边际收益最大的任务，提交一个出价。
3. 冲突消解：无人机之间通过通信交换出价信息。如果发现同一任务被多架无人机出价，比较谁的出价高，价高者暂时获得该任务，落选者回收自己的出价并继续寻找其他任务。
4. 终止判断：当所有无人机都无法找到边际收益为正的任务时，分配结束，输出结果。

这套流程的理解价值在于：它把全局最优化问题分解成了大量局部决策，无人机之间只需通信“出价”和“胜者”这两类信息，不要求所有信息集中到中心节点，因此在通信拓扑发生变化时也能继续运行。很多团队后来把拍卖算法和一致性协议结合起来，就是为了解决通信受限情况下的冲突消解问题。我在复现这类算法时，最大的体会是“边际收益的计算不能光看收益，还要考虑插入顺序”，因为任务序列不同，边际收益的计算结果完全不同。这个细节如果没处理好，算法收敛后任务序列的不合理性会很突出。

2.2 与其他优化模型的对比

除了拍卖模型，任务分配领域还有几类常见建模方式，我把它们整理成了下面几张“面孔”：

• 混合整数线性规划（MILP）模型：把任务分配建模成二进制变量的线性规划问题，用CPLEX/Gurobi这类求解器可以得到小规模问题的全局最优解。优点是解质量有保证，缺点是计算量随变量数量增长太快，一般只适合离线或者小规模实时场景。
• 马尔可夫决策过程（MDP）/部分可观察马尔可夫决策过程（POMDP）模型：把任务分配看作序贯决策问题，用强化学习或动态规划求解。适合处理不确定环境和动态威胁，但真实规模下维度灾难非常严重。
• 市场机制/合同网模型（Contract Net Protocol）：把任务分配看作“招标-投标-中标”过程。有些任务管理者发出招标信息，无人机们根据自身状态提交“执行条件”，管理者选择最合适的投标者。这种方式直观、易实现，但缺点是管理者节点容易成为通信瓶颈，且对动态环境的响应速度一般。
• 图论与匹配模型：把无人机与任务建模成二分图，用匹配算法求最大权重匹配。适合解决“一对一”或“一对多”的简单场景，扩展性不足。

我用表格简单对比一下：

读到这里你应该能感觉到：真实的多无人机多目标任务分配，并不是“一种模型打天下”，而是根据任务性质、通信条件、实时性要求，混合采用多种建模思路。综述笔记里最重要的工作，就是把这些模型各自的前提假设和适用边界画清楚，否则很容易出现“仿真里跑得很好，真机上完全不是一回事”的情况。

3. 算法选型：求解这类NP难问题的几条路线

3.1 集群智能方法：遗传算法与粒子群

任务分配问题通常被证明为NP难，这意味着在输入规模变大时，精确算法基本无法在有限时间内给出最优解。实战中大家更常用的是各种启发式算法，其中“集群智能”是热度非常高的一族。

**遗传算法（GA）**用来做任务分配并不复杂，关键在编码方式。最常见的编码方法是“基于任务排序的整数编码”。假设有3架无人机，6个任务，你就设计一段长度为6的基因串，每个基因位上的数字代表执行该任务的无人机编号，同时再用另一个数组保存任务执行顺序。这样就能保证一个基因唯一对应一个可行的任务序列。适应度函数可以直接用目标函数，也就是“总航程+惩罚项”，如果某个解违反了时间窗约束，就给它加上一个很大的惩罚值，让它在进化过程中被自然淘汰。

我在复现遗传算法时发现，真正影响效果的不是交叉变异算子，而是初始种群的生成方式。如果一开始全部用随机生成，很容易导致大量不可行解，算法要花非常多代才能把可行区域“捞”回来。更聪明的做法是先用贪心算法生成一部分较优个体，再让它们参与后续进化。这个“用启发式解做初始种群的种子”的小技巧，能让收敛速度提升一个量级。

**粒子群算法（PSO）**相比遗传算法更贴合连续优化，但任务分配是离散的组合问题，所以通常需要把PSO改成分离散版本。常见做法是把粒子的位置向量映射成任务分配矩阵，比如粒子每一维的数值落在[0, n)区间，向下取整就能得到无人机编号。不过这种映射很容易造成多个粒子对应同一个无效解，需要额外的修正机制。我的经验是：PSO在任务规模较小（比如10架无人机、20个任务以内）时速度快、效果也可以接受，但任务一多，它的局部搜索能力会明显弱于遗传算法和禁忌搜索。

**蚁群算法（ACO）**也经常被用到，它天然适合处理“任务顺序”这类排列问题。把每个任务看成图上的节点，用信息素浓度引导无人机依次选择下一次要执行的任务。但ACO在多无人机场景下很容易陷入“早熟”，因为信息素衰减参数一旦设置不好，算法会过分集中在局部最优路径上。如果要用ACO，我建议配合2-opt局部搜索算子使用，每轮迭代后对每个解做一次邻域搜索，对所有解的质量提升非常明显。

3.2 一致性束算法（CBBA）常见实现细节

如果说近十年分布式任务分配领域哪个算法影响力最大，CBBA绝对排得上号。CBBA全称Consensus-Based Bundle Algorithm，它把“拍卖机制”和“一致性协议”结合起来，既能处理多无人机对多任务的争抢，又能适应通信距离受限、通信拓扑不固定的情况。我在做项目时最常用的就是CBBA，它的整体框架可以概括为两阶段循环：

• 束构建阶段（Bundle Construction）：每架无人机维护一个“束”，也就是它自认为要执行的任务序列。每轮迭代中，无人机计算把新任务插入束中某个位置能够增加的边际收益，选择增量最大的任务加入束中，并对它出价。
• 冲突消解阶段（Consensus）：无人机之间共享各自的出价向量“胜者”信息和“胜者价格”列表。如果发现邻居无人机对某个任务的出价更高，那么本机就让出该任务；如果发现冲突但双方信息不一致，就利用时间戳和节点编号来消解分歧。

CBBA的代码实现非常考验细节。有几个点我必须提醒大家：

第一，出价函数需要满足“递减边际收益”性质，否则算法无法保证收敛率。也就是说，随着束中任务越来越多，新增任务带来的边际收益应该逐步下降。现实中任务间可能存在强耦合，比如两个任务必须由同一架无人机配合执行，这就会破坏递减性。处理办法是预先做任务聚类，把强耦合任务打包成复合任务再参与分配。

第二，通信网络的时序管理是关键。很多复现CBBA翻车的场景，不是算法本身错了，而是节点之间的消息发送和接收顺序没有处理好。一般的做法是给每个消息打上时间戳，每次收到消息后先更新本机维护的“胜者时间表”，再用这个时间表去决定是否响应出价。我在Matlab里模拟时，特意把通信延迟建模成了固定延迟+随机抖动，结果发现CBBA仍能稳定收敛，但收敛轮数明显增加，这在实际中值得注意。

第三，CBBA默认“每架无人机最多执行K个任务”，K的选取直接影响解质量。如果K设置过大，单架无人机任务束会很长，导致部分无人机超载，反而浪费资源。较好的做法是在任务分配前先做一个粗略的“任务需求·无人机能力”匹配，估算出合理的K范围，然后跑多组K值对比。例如我有一次项目里8架无人机要处理28个任务，K=4时总体任务完成价值最高，K=5时虽然完成了更多任务但续航超限，整体方案反而不可行。

CBBA的好处是通信负载低、可扩展性强，很适合大规模异构无人机群。但它也不是万能的，它天然不擅长处理“任务间存在严格时序要求”的场景。如果某个任务必须等另一个任务完成后才能开始，需要额外引入时序约束预处理，或者在收益函数中加入“奖励扰动量”来引导顺序。这一块目前学术界还在不断扩展，很多新工作都是在CBBA基础上加时序和协同约束。

4. 我在复现和整理这类综述时的几点经验

4.1 仿真参数设置要均匀

做多无人机任务分配研究，最大的坑往往不是算法本身，而是参数对比不公平。很多人在仿真时，不同算法用不同迭代次数，或者对比较算法没有认真调参，导致实验结果“看起来我的算法最好”，其实是占了不公平的便宜。

我建议在综述笔记里设立一套固定的基准参数模板：

• 无人机数量、任务数量、地图尺寸、通信半径等环境参数保持一致；
• 所有比较算法使用相同的最大迭代次数或运行时间上限（比如统一跑5秒，而不是统一迭代1000次）；
• 每个算法至少跑30次蒙特卡洛仿真，报告均值和方差，而不是只贴一次最好结果；
• 设置至少两种任务规模，比如小规模（5机10任务）和大规模（20机80任务），分别看算法的收敛速度和解质量。

这套模板不是为了凑字数的，而是为了保证结论可信。我自己吃过亏：之前在对比遗传算法和蚁群算法时，遗传算法用了500代而蚁群只用了100代，得到的结果自然严重偏斜。后来把所有算法的运行时间统一到相同阈值，算法排名直接反转了。这个坑，希望大家一定不要踩。

4.2 评价指标要配套

任务分配的评价指标不能只盯“目标函数值”一个数，那样很容易掩盖算法的真实行为。我在综述笔记里常用的评价指标有4个：

• 完成任务总价值（Total Mission Value）：衡量整体收益，是最直观的指标。
• 平均任务完成率（Task Completion Ratio）：已执行任务数/总任务数，用来反映资源紧张的场景下算法能保住多少任务。
• 单机最大负载均衡度（Load Balance Index）：常用公式1 - max_load / avg_load或标准差来表示，如果一架无人机被塞了太多任务，其他无人机却闲着，系统的鲁棒性会很差。
• 计算时间（Computation Time）：包含算法收敛时间和通信时间，分布式算法的计算时间不能只算本机CPU时间，还得加上通信往返的仿真时间。

我见过很多论文只报第一个指标，不报完成率和均衡度，然后宣称“显著优于对比算法”。但把后三个指标补上后，其“优越性”往往会大打折扣。特别是负载均衡度，在动态环境中直接影响无人机群的整体存活能力。你总不希望某架无人机为了多完成任务而耗尽电量，最后导致整个系统没有了备份力量吧。所以在设计实验时，一定要把这几个指标同时看。

4.3 边界条件与通信问题

多无人机任务分配里最容易被忽略但最致命的是边界条件。所谓边界条件，包括无人机的留空时间、最大转弯半径、禁飞区约束、电子干扰区域等。很多仿真模型把这些条件过于简化，导致算法在实际部署时会出现“规划路线好看，但飞机根本飞不过去”或者“以为飞得过去，实际电量不够”的尴尬。

我个人的习惯是，在做任务分配之前，先用一个简易的“可达性分析”去筛掉一批不合理的任务-无人机配对。具体做法是，对每一对无人机-任务，用Bresenham直线或者简化动力学模型估算飞行距离和时间，再对比无人机剩余能量，生成一个“可行分配矩阵”。这个矩阵会作为后续分配算法的输入硬约束，强行排除那些不可达的匹配。虽然这一步会增加预处理时间，但能显著提升整体方案的工程可行性。

通信问题同样重要。分布式任务分配算法依赖无人机之间的信息交互，但真实环境下通信带宽有限、距离影响信号强度、GPS拒止等场景也经常出现。综述笔记里不能忽略对“通信拓扑动态变化”的仿真。我常用一个简单模型：每架无人机只与通信半径R内的邻居通信，仿真中让无人机的飞行位置实时改变，导致邻居关系不断刷新。这种动态拓扑下的算法性能，才更接近实战。凡是只靠全连通网络验证的算法，工程落地大概率要打折扣。

其实写综述笔记最大的价值不是把别人的方法罗列一遍，而是帮自己梳理清楚“现有方法分别在解决什么问题、遗留了什么问题”。我在整理多无人机多目标任务分配这个方向时，最大的体会是：离开具体的任务场景和约束去谈算法优劣，完全是耍流氓。明明任务规模只有10个，非要去上一个复杂的分布式共识算法，那是杀鸡用牛刀；反过来，任务规模上百、通信不稳定，还坚持用集中式MILP，那就很难满足实时性要求。所以读者在看任何文献时，建议先问自己四个问题：这是静态还是动态场景？通信条件是否理想？任务之间有没有时序耦合？评价指标是不是均衡考虑了完成率、负载和计算代价？问完这四个问题，再优秀的算法也能很快判断出它在你的场景下到底适不适合。后续我计划在这篇笔记的基础上，继续整理任务分配的在线重分配策略，以及融合学习与规划的新思路，到时候再和大家细聊。