第 3 章 任务分配与路径规划¶
本章性质：✅ 全方向共享——任务分配(task allocation)回答"谁干什么",多机路径规划(MAPF)回答"怎样不撞上"。这两件事是任何多机系统在"协调运动"之前必须先解决的离散决策层。后续每一章只要出现"一群机器人要分头去做多件事、还要在共享空间里互不阻塞",背后都是本章的算法在运转:第 6 章异构编队要先把侦察/搬运任务派给合适的机型,第 13 章 Mini-MultiBot 的综合调度直接复用本章的
planning/模块,而仓库 AGV、无人机蜂群的协同更是 MAPF 的主战场。 读者画像：已读完第 1 章(掌握通信图 \(G\)、邻接/度/Laplacian 矩阵、\(\lambda_2\)、三大架构)与第 2 章(掌握共识 \(\dot x=-Lx\)、双随机权重、收敛速率),熟悉 A* 与启发式搜索基础(g+h、可采纳启发、open/closed 表)的算法工程师。 在 Part 中的位置：本章是 Part 1(多机协作基础)的收官章。第 1 章给了"看待多机系统"的地图、第 2 章给了"连续协调"的数学引擎(共识/ADMM),本章补上**离散决策**这一块——任务到机器人的分配、路径的冲突消解。它一头复用第 2 章的共识(CBBA 用共识裁决分布式拍卖的冲突),一头为后续所有"先分工、再运动"的章节打底。读完本章,Part 1 的三件套(看系统、连续协调、离散决策)就配齐了。
前置自测¶
📋 答不出 \(\ge 2\) 题 → 标 ① ② 的回第 1、2 章,标 ③ ④ 的回 A* 与组合优化基础,再来读本章。本章会大量复用这些前置,但不重新教它们。
- （接第 2 章）什么叫**双随机矩阵**?为什么离散共识 \(x(k{+}1)=Wx(k)\) 要求 \(W\) 双随机才收敛到正确平均?本章 CBBA 的"冲突裁决"会用到共识的哪个性质——是收敛到平均,还是别的?
- （接第 1 章）通信图的**直径**(diameter)是什么?如果一条信息要从图的一端传到另一端,最少需要几轮邻居间转发?这个数会直接出现在本章 CBBA 的收敛轮数里。
- A* 搜索里,可采纳启发函数(admissible heuristic)的定义是什么?为什么可采纳能保证 A* 找到最优解?本章 CBS 的"低层搜索"就是一堆带约束的单体 A*。
- 什么是**指派问题**(assignment problem)?给定一个 \(n\times n\) 代价矩阵,把它求解到最优需要多少计算量(用大 \(O\))?你听说过匈牙利算法(Hungarian algorithm)吗?
- （接第 1 章）"集中式 \(O(N^3)\) 爆炸"在第 1 章是针对联合 QP 说的。如果把 \(N\) 个机器人的路径规划拼成一个"联合智能体"在 \(N\) 倍维度的空间里搜索,搜索空间会怎样随 \(N\) 增长?这正是本章 MAPF 要回避的爆炸。
本章目标¶
学完本章后,你应该能够:
- 建模并实现任务分配的基线:把多机任务分配建模为指派问题,用 Gerkey–Matarić 分类法(ST/MT、SR/MR、IA/TA)定位一个具体问题落在哪一类、说明为什么 ST-SR-IA 恰好可在多项式时间最优求解;并实现两种集中式基线——匈牙利算法(最优、\(O(n^3)\))与拍卖/贪婪(次优、可分布式),用代码量化二者的最优性差距。
- 推导并实现 CBBA:讲清它的两阶段结构(本地 bundle 构建 + 基于共识的冲突消解),说明**边际收益递减(DMG)**条件为何能保证它等价于集中式顺序贪婪、从而拿到 50% 最优界,并解释它的收敛轮数为何正比于通信图直径。
- 形式化 MAPF:写出顶点冲突与边冲突(交换冲突)的定义,区分 sum-of-costs 与 makespan 两种目标,说明 MAPF 最优求解为何是 NP-难,以及"耦合(joint A*)vs 解耦(单体规划)"这条谱系的两端各自的代价。
- 推导并实现 CBS:讲清两层结构(高层二叉约束树 CT + 低层单体 A*)、冲突如何分裂成两个加约束的子节点、为何"两个子节点都展开"能保证最优,并对比它与优先级规划(无完备性保证)的取舍。
- 解释可扩展 MAPF 的工程路线:优先级规划 + 预留表(reservation table)、PIBT 的优先级继承与回溯、LaCAM 的惰性后继生成,说明它们用什么换取了"上千智能体亚秒求解",以及终身 MAPF(lifelong MAPF)与一次性 MAPF 的区别。
- 把离散计划接到真机执行:说明离散 MAPF 的"同步、单位步、点机器人"假设为何在真机上失效,讲清连续时间 MAPF(CCBS)、把计划后处理成鲁棒执行的动作依赖图(ADG)与 \(k\)-robust,以及终身取送货 MAPD 与联合目标分配-路径 TAPF/CBM 如何把分配与路径在一个框架里联合求解。
- 建立质量-规模谱与选型能力:讲清有界次优(ECBS/EECBS,解 \(\le w\) 倍最优、带保证)与 anytime(MAPF-LNS,先可行再逐步逼近最优)两条路线、焦点搜索如何"有原则地放松最优性",把全章方法收进"最优性×完备性×规模"的总表,认识学习式 MAPF(PRIMAL、GNN、学习引导搜索)这条与搜索式/规则式并列的路线及其"无保证、难泛化"的取舍,并能按"规模×最优性需求×是否终身×是否上真机"为一个真实问题选对方法。
本章知识导航¶
一句话定位：本章把"多机协调"从连续控制层往上推一层到**离散决策层**——先决定"谁去做哪件任务"(任务分配),再决定"每个机器人走哪条路、如何不在共享空间里相撞"(路径规划)。两件事都在第 1 章的图上进行,而任务分配的分布式版本(CBBA)又直接调用第 2 章的共识。
本章四条主线及其递进关系:
| 主线 | 解决的问题 | 关键工具 | 对应小节 |
|---|---|---|---|
| 任务分配(集中) | \(N\) 机器人 \(\times\) \(M\) 任务,谁干什么最划算? | 指派问题、匈牙利、拍卖、贪婪、Gerkey 分类 | §3.1 |
| 任务分配(分布) | 没有中央分配器,各自拍卖如何不冲突? | CBBA(bundle + 共识冲突消解)、DMG、50% 界 | §3.2 |
| 路径规划(最优) | 多机不撞上,如何搜最优解又不爆炸? | MAPF 定义、CBS(约束树 + 低层 A*) | §3.3-3.4 |
| 路径规划(可扩展) | 上千机器人、实时、终身,怎么办? | 优先级规划、预留表、PIBT、LaCAM | §3.5 |
| 边界与组合 | 离散 MAPF 与连续编队的界?如何把分配+路径接起来? | 子模任务分配、warehouse vs formation | §3.6 |
| 路径规划(有界次优/anytime) | 既要规模、又要质量保证,怎么办? | 焦点搜索、ECBS/EECBS、MAPF-LNS/LNS2 | §3.7 |
| 从规划到执行 | 真机有形状/延迟/速度差,离散计划怎么安全跑? | CCBS、动作依赖图 ADG、k-robust、MAPD/TAPF | §3.8 |
| 方法全景与选型 | 这么多方法,拿到问题该选哪个?学习式是什么? | 学习式 MAPF(PRIMAL/GNN)、全景总表、选型决策框架 | §3.9 |
推荐阅读路径：§3.1 是地基(分配问题与基线,必读)→ §3.2 是本章与第 2 章的接合点(CBBA,分布式方向必读、需动手实现)→ §3.3 把问题从"分配"切换到"路径",建立 MAPF 语言(必读)→ §3.4 是最优 MAPF 的核心(CBS,必读且需跟着搭一遍)→ §3.5 是工程落地的可扩展路线(PIBT/LaCAM,做仓库/蜂群必读,理论方向可速读结论)→ §3.6 讲分配与路径如何组合、离散与连续的边界 → §3.7 补上"质量×规模"二维谱(有界次优 ECBS/EECBS 与 anytime LNS,做大规模 MAPF 必读)→ §3.8 把离散计划接到真机鲁棒执行(CCBS/ADG/MAPD,做真实部署必读)→ §3.9 是全景与选型收口(学习式 MAPF + 总表 + 决策框架,建议最后通读、当索引常查)。§3.2、§3.4、§3.7、§3.8 是四个 ⭐⭐⭐⭐ 的硬核小节,值得花最多时间。
前置知识桥接¶
本章紧接第 1、2 章,这里把最关键的前置点重新激活——你不必翻回去就能跟上:
- 回顾第 1 章:通信图与直径。第 1 章我们用图 \(G=(V,E)\) 建模"谁能和谁通信",并定义了 Laplacian \(L\)、代数连通性 \(\lambda_2\)。本章 §3.2 的 CBBA 在这张图上运行——它的收敛轮数正比于图的**直径**(信息从一端传到另一端要几跳),而第 2 章告诉我们这类"图上迭代"的速度由谱(\(\lambda_2\))决定。任务分配的"图"和路径规划的"图"是两张不同的图:前者是机器人间的**通信图**,后者是环境的**栅格/路网图**——别混淆。
- 回顾第 2 章:共识作为"分布式裁决"的原子操作。第 2 章证明了共识能让各 agent 只靠邻居通信收敛到一致。CBBA 的冲突消解阶段本质上是一种**带时间戳的最大值共识**:每个机器人维护"每个任务当前已知的最高出价",通过邻居交换不断刷新,最终全网对"每个任务归谁"达成一致。你会看到第 2 章的共识在这里换了层皮再次出场。
- 回顾 A* 搜索。单体最短路用 A*:维护 open 表(按 \(f=g+h\) 排序)、closed 表,可采纳启发 \(h\) 保证最优。本章 §3.4 的 CBS"低层"就是给单个机器人跑 A*,只不过多了一组"某时刻不能在某顶点/某条边"的时空约束;§3.5 的优先级规划则是在"已被占用的时空"上跑 A*(cooperative A*)。
如果跳过本章会怎样¶
- 场景一(贪婪分配看着合理,总代价却差一截)：你给 5 台机器人分 5 个任务,图省事用"每台机器人各自挑离自己最近的任务"。结果两台机器人抢同一个近任务、剩下的远任务没人愿意去,总行程比最优解长出 40%。§3.1 会告诉你:这是贪婪/拍卖的固有次优——指派问题有最优的匈牙利算法(\(O(n^3)\)),而当你必须分布式、放弃中央分配器时,CBBA 这类方法只能保证拿到最优的一半(50% 界),这个差距是"分布式 + 可扩展"必须付的税,得心里有数。
- 场景二(多机路径各自规划,跑起来全堵死)：你让每台机器人独立用 A* 规划自己的最短路,然后一起执行,心想"反正各走各的"。结果在狭窄走廊里两台机器人正面顶牛、谁也不让,或者交叉路口同时进入同一格子相撞。§3.3-3.4 会告诉你:多机路径规划不是 \(N\) 个独立的单体规划——必须显式处理**顶点冲突**(同一时刻同一格)与**边冲突**(同一时刻交换位置),要么用 CBS 求最优解,要么用优先级规划/PIBT 这类有协调机制的方法,否则死锁(deadlock)几乎必然发生。
预计阅读时间¶
| 模式 | 时长 | 适合 |
|---|---|---|
| 精读(跟着推完 CBBA 的 DMG/50% 界、搭一遍 CBS、实现优先级规划 + MAPF-LNS + ADG 执行) | 22–30 小时 | 第一次系统学多机任务分配与 MAPF 的工程师 |
| 速读(读懂各算法流程与适用边界,跳过证明细节) | 7–9 小时 | 已有背景,查漏补缺 |
| 速查(分配方法对比表 + CBBA 两阶段 + CBS 流程 + MAPF 质量×规模二维谱 + 执行鲁棒性 + 故障排查) | 50–60 分钟 | 实现调度/MAPF 时回查 |
§3.1 任务分配问题与拍卖机制 ⭐⭐⭐¶
这一节解决什么问题：一支机器人队伍面对一批任务,第一个要回答的不是"怎么走",而是"谁去做哪件"。这一节把这个问题形式化为指派问题,给出它的最优解法(匈牙利)与可扩展解法(拍卖/贪婪),并用 Gerkey–Matarić 分类法帮你判断手头的问题到底属于哪一类、有没有多项式最优解。它是 §3.2 分布式 CBBA 的地基——CBBA 本质上就是"拍卖 + 共识"。
动机：谁去做哪件任务¶
设想三台巡检机器人 \(\{r_1,r_2,r_3\}\) 和三个待巡检点 \(\{t_1,t_2,t_3\}\)。每台机器人去每个点都有一个"代价"(比如行驶距离或耗时),写成代价矩阵 \(C\),其中 \(c_{ij}\) 是机器人 \(i\) 去任务 \(j\) 的代价。我们要给每台机器人各派一个任务(一对一),让**总代价最小**。
这看似简单——三个任务三种排法也就 \(3!=6\) 种,枚举即可。但任务一多就不行了:\(N\) 个任务有 \(N!\) 种分法,\(N=15\) 时已超过一万亿种。更现实的是,任务分配几乎从不孤立出现——它是后续运动的入口:仓库里"哪台 AGV 去取哪个货架"、灾后搜救里"哪架无人机扫哪个区"、多臂装配里"哪只手装哪个件"。分配得好不好,直接决定整个系统的效率上限。把这个离散决策问题搞清楚,才谈得上后面的路径规划与协同控制。
如果用最朴素的办法会怎样¶
最朴素的两种做法,都各有致命问题。
其一,枚举所有分法取最优。理论最优,但 \(N!\) 的复杂度让它在 \(N>12\) 左右就彻底失效——这是组合爆炸,和第 1 章联合优化的 \(O(N^3)\) 爆炸是同一类敌人(只是更猛)。其二,贪婪:每台机器人挑自己最便宜的任务。快、可分布式,但会"撞车"——两台机器人可能都觉得 \(t_1\) 最近,于是抢同一个任务,而没人愿意去那个偏远的 \(t_3\)。即便加上"先到先得"的消解规则,贪婪得到的总代价也可能显著高于最优。
问题的关键在于:任务分配是一个**有全局耦合**的问题——某台机器人选了某个任务,会改变其他机器人的最优选择。朴素贪婪只看局部(自己最便宜),忽略了这种耦合,所以次优;枚举看了全局但代价爆炸。我们需要既考虑全局耦合、又多项式可解的方法。好消息是:对最常见的"一对一、一次性"分配,这样的方法存在(匈牙利);坏消息是,一旦任务可被多机协作、或随时间到达,问题就变难了。所以先得搞清楚"我的问题到底是哪一类"。
历史：从匈牙利算法到市场机制¶
任务分配的数学源头是**指派问题**,1955 年 Kuhn 提出匈牙利算法(Hungarian algorithm)给出最优解,Munkres 1957 年完善并证明其多项式复杂度——所以它也叫 Kuhn–Munkres 算法。匈牙利算法把"最小代价完美匹配"在 \(O(n^3)\) 内解决,是组合优化的经典成果。
到了机器人领域,人们更看重**可扩展**与**分布式**,于是市场/拍卖机制兴起:把任务当作待拍卖的商品,机器人作为竞标者出价,价高(或代价低)者得。Bertsekas 在 1980 年代提出的拍卖算法(auction algorithm)用"价格上涨 + \(\epsilon\)-互补松弛"逼近最优指派。2004 年 Gerkey 与 Matarić 发表了多机任务分配(MRTA)的奠基性分类法,把这个领域的问题按三个维度厘清(下面理论部分详述),让大家第一次能清楚地说"我研究的是哪一类问题、它的复杂度如何"。同年 Dias 等人系统综述了市场化方法。这条"拍卖"的线,正是下一节 CBBA 的直接前身——CBBA = 分布式拍卖 + 共识。
理论¶
一、线性指派问题(LAP)¶
最基础的形式:\(N\) 台机器人、\(N\) 个任务,一对一分配,最小化总代价。引入指派变量 \(x_{ij}\in\{0,1\}\)(\(x_{ij}=1\) 表示机器人 \(i\) 做任务 \(j\)),问题写成:
两组等式约束分别表示"每台机器人恰好一个任务"和"每个任务恰好一台机器人"。这是一个整数规划,但它的约束矩阵是**全幺模**(totally unimodular)的,因此线性松弛(\(x_{ij}\in[0,1]\))的最优解天然是整数——这是指派问题能多项式最优求解的根本原因。匈牙利算法正是利用这一结构,在 \(O(N^3)\) 内求得最优解。若用最大化效用 \(u_{ij}\) 而非最小化代价,令 \(c_{ij}=-u_{ij}\) 即可。
二、Gerkey–Matarić 分类法:先认清问题属于哪一类¶
不是所有任务分配都像 LAP 那样好解。Gerkey 与 Matarić 用三个二元维度刻画 MRTA:
- ST vs MT(single-task vs multi-task robots):一台机器人同时只能做一个任务,还是能并行多个。
- SR vs MR(single-robot vs multi-robot tasks):一个任务只需一台机器人,还是需要多台协作(如多机搬一件重物——这正是第 5 章的主题)。
- IA vs TA(instantaneous vs time-extended assignment):只做一次瞬时分配,还是要为每台机器人规划一个随时间展开的任务序列(考虑未来任务)。
这三维组合出 8 类问题,复杂度天差地别:
- ST-SR-IA:恰好是式 (3.1) 的 LAP,匈牙利 \(O(N^3)\) 最优可解。这是最幸运的一类。
- ST-SR-TA:每台机器人要做一串任务(序列),与车辆路径问题(VRP)相关,NP-难。CBBA 处理的正是这一类(每个 agent 维护一个 bundle/序列)。
- 任何带 MR 的类:任务需多机协作,涉及联盟形成(coalition formation),通常 NP-难,且和第 5 章的协同搬运、第 6 章的异构编组耦合。
这张分类法的价值:拿到一个分配问题,先定位它的三个维度,你就立刻知道"能不能最优解、该用什么方法"。把一个 MR 任务(需两机协作)错当成 SR 来分配,是初学者最常见的建模错误。
三、拍卖算法:可分布式的次优解法¶
拍卖算法把分配看成市场:每个任务 \(j\) 有一个当前价格 \(p_j\),机器人 \(i\) 对任务 \(j\) 的"净收益"是 \(u_{ij}-p_j\)。每轮,未分配的机器人挑净收益最高的任务竞标,把价格抬高到刚好让它仍是最优、且超过次优一个 \(\varepsilon\)。价格单调上涨,过程在有限步收敛到一个 \(\varepsilon\)-近似最优指派(总效用与最优差距 \(\le N\varepsilon\))。拍卖算法的妙处在于:它**天然分布式**——每个机器人只需知道任务价格(全局共享的少量标量)就能独立竞标,不需要中央求解器看到整个代价矩阵。这正是它在机器人领域比匈牙利更受欢迎的原因,也是 CBBA 的直接灵感。
上面是 Bertsekas 式的"单任务竞价拍卖"。机器人领域还有一类更贴近多任务场景的市场机制——顺序单项拍卖(Sequential Single-Item auction, SSI, Koenig 等)。它的流程是:把任务一个一个拿出来拍,每一轮所有机器人对**当前这件**任务报一个价(报价 = 把该任务加进自己已有任务集后的**边际代价**),出价最低者赢得该任务、把它纳入自己的集合;然后拍下一件。SSI 介于两个极端之间:逐件拍而非一次性整体优化(所以比集中最优快、可分布式),但每件的报价考虑了"已接任务"的协同(所以比"各自独立挑最近任务"的纯贪婪质量高)。它和 SGA 的区别在拍卖顺序:SGA 每轮在**所有**(机器人,任务)对里挑全局边际最优的一对,SSI 则固定"逐个任务"的外层顺序、每件只在机器人间竞价。SSI 因实现简单、通信量小、质量尚可,是仓库与多机器人系统里常见的实用折中。
四、顺序贪婪(SGA)与"边际收益递减"¶
当一台机器人要做多个任务(TA),它对一个任务的价值依赖于它已经接了哪些任务——比如已经要去东边了,再接一个东边的任务边际成本就低。顺序贪婪算法(Sequential Greedy Algorithm, SGA)每轮在所有"(机器人, 任务)对"里挑边际收益最高的一对、分配掉,重复直到无任务可分。SGA 是集中式的,但它有一个关键性质:当效用函数满足**边际收益递减**(Diminishing Marginal Gain, DMG)——即一个任务的边际价值不会因为先接了别的任务而**增加**——SGA 的解保证不差于最优解的一半。这个 50% 界,以及 SGA 与 CBBA 的等价,是下一节 CBBA 拿到性能保证的全部理论依托,这里先埋下。
把本节四种任务分配方法摆在一起,坐标是"集中还是分布 × 最优还是次优":
| 方法 | 集中/分布 | 最优性 | 通信/计算 | 适用 |
|---|---|---|---|---|
| 匈牙利(Kuhn–Munkres) | 集中(需全代价矩阵) | ✅ 最优(一对一) | \(O(n^3)\),需全局信息 | 小规模、一对一、要最优 |
| 拍卖(Bertsekas) | 可分布(只需共享价格) | \(\varepsilon\)-近似(差距 \(\le N\varepsilon\)) | 多轮竞价,通信少 | 要可分布、近最优 |
| SGA(顺序贪婪) | 集中 | \(\ge\tfrac12\) 最优(DMG 下) | 每轮全局挑最优对 | 多任务、要保证、可集中 |
| SSI(顺序单项拍卖) | 可分布 | 启发式(介于贪婪与最优) | 逐件竞价,实现简单 | 多任务、分布式、实用折中 |
这张表是 §3.2 的跳板:CBBA 要做的,正是把"SGA 的 50% 保证"和"拍卖/SSI 的可分布"合二为一——用共识让分布式的竞价结果等价于集中式 SGA。
代码验证：匈牙利 vs 贪婪的最优性差距¶
我们用代码把"贪婪次优、匈牙利最优"看清楚。scipy.optimize.linear_sum_assignment 就是匈牙利算法的实现。
import numpy as np
from scipy.optimize import linear_sum_assignment
rng = np.random.default_rng(0)
def greedy_assignment(C):
"""贪婪:每轮挑全局最小代价的(机器人,任务)对,分配掉。"""
n = C.shape[0]
C = C.copy().astype(float)
rows, cols = set(range(n)), set(range(n))
total, assign = 0.0, {}
while rows:
# 在未分配的行列里找全局最小
sub = C[np.ix_(list(rows), list(cols))]
ri, ci = np.unravel_index(np.argmin(sub), sub.shape)
i, j = list(rows)[ri], list(cols)[ci]
assign[i] = j; total += C[i, j]
rows.remove(i); cols.remove(j)
return total, assign
def hungarian_cost(C):
r, c = linear_sum_assignment(C) # 最优
return C[r, c].sum()
# 随机实验:多个规模上比较贪婪与最优的差距
for n in [3, 5, 10, 20]:
gaps = []
for _ in range(200):
C = rng.uniform(1, 100, size=(n, n))
opt = hungarian_cost(C)
gre, _ = greedy_assignment(C)
gaps.append((gre - opt) / opt * 100) # 贪婪比最优贵百分之几
print(f"n={n:2d}: 贪婪平均比最优贵 {np.mean(gaps):5.1f}% , 最坏 {np.max(gaps):5.1f}%")
运行要点:你会看到贪婪平均比最优贵百分之十几到几十,且**最坏情况差距随规模拉大**。这量化了"局部贪婪 vs 全局最优"的代价——也解释了为什么当我们在 §3.2 为了分布式而放弃集中最优时,要的不是"和匈牙利一样好",而是"有一个可证明的界"(50%)。匈牙利之所以能最优,是因为它利用了式 (3.1) 的全幺模结构做全局优化;贪婪每步只看当前最小,丢掉了全局耦合。
下面再看拍卖算法如何分布式地逼近最优:
def auction_assignment(U, eps=1e-3):
"""拍卖算法(最大化效用 U)。返回总效用与分配。
每个机器人只看任务价格 p 竞标——这是它可分布式的关键。"""
n = U.shape[0]
p = np.zeros(n) # 任务价格(全局共享)
owner = -np.ones(n, dtype=int) # 每个任务当前归谁
unassigned = list(range(n))
while unassigned:
i = unassigned.pop()
net = U[i] - p # 各任务净收益
j = int(np.argmax(net)) # 最优任务
best = net[j]
second = np.partition(net, -2)[-2] # 次优净收益
bid = p[j] + (best - second) + eps # 抬价:超过次优一个 eps
if owner[j] != -1:
unassigned.append(owner[j]) # 原主被挤掉,重新竞标
owner[j] = i; p[j] = bid
total = sum(U[owner[j], j] for j in range(n))
return total, owner
rng = np.random.default_rng(1)
n = 10
U = rng.uniform(1, 100, size=(n, n))
opt = -hungarian_cost(-U) # 最大化效用的最优
auc, _ = auction_assignment(U, eps=1e-2)
print(f"拍卖总效用 {auc:.2f} vs 最优 {opt:.2f} , 差距 {(opt-auc)/opt*100:.3f}%")
运行要点:拍卖的总效用与最优只差极小一点(由 \(\varepsilon\) 控制,理论上界 \(N\varepsilon\)),却只靠"每个机器人看价格竞标"实现——没有任何一处需要看到完整效用矩阵。把 \(\varepsilon\) 调小,差距进一步缩小但迭代变多。这个"价格作为全局协调信号、各 agent 独立竞标"的结构,就是下一节 CBBA 的骨架——只不过 CBBA 把"价格"换成了通过**共识**传播的"中标信息"。
⚠️ 常见陷阱¶
💡 概念误区:把多机协作任务(MR)当成单机任务(SR)来分配 - 错误描述:有个任务实际需要两台机器人协作(如合抬一件重物),却用 LAP/匈牙利做一对一分配,给它派一台机器人。 - 现象/后果:分配出的方案物理上不可执行(一台机器人抬不动),或系统在执行阶段才发现要临时拉人,打乱整个调度。 - 根本原因:LAP 的模型假设是 ST-SR-IA(任务只需一机);MR 任务属于联盟形成问题,数学结构完全不同(NP-难、需考虑机器人组合)。 - 正确做法:动手前先用 Gerkey–Matarić 三维给问题归类。带 MR 的问题不能用 LAP,要用联盟形成/分组方法(并会与第 5 章协同搬运、第 6 章异构编组耦合)。
🧠 思维陷阱:默认"最小化总代价"就是唯一目标 - 错误描述:不加思考地把目标设成总行程/总耗时之和(sum),用匈牙利求解。 - 现象/后果:得到的方案总和最小,但某一台机器人被派了极远的任务、单独干到天黑(完工时间 makespan 很大),团队整体要等它。 - 根本原因:sum(总和)与 makespan(最大单体完工时间)是不同目标——前者优化吞吐,后者优化"最后一个干完的时间"。匈牙利默认优化 sum,对 makespan 不直接适用。 - 正确做法:先明确业务目标。要均衡负载/抢时间用 min-max(makespan),它一般比 min-sum 更难(常需另设算法或迭代)。把目标写清楚再选算法。
⚠️ 编程陷阱:代价矩阵的行列方向或非方阵处理出错 - 错误描述:用
linear_sum_assignment时把"机器人×任务"的矩阵转置了,或机器人数 ≠ 任务数时直接塞进去不补齐。 - 现象/后果:分配结果张冠李戴(把任务的索引当成机器人),或在非方阵上得到部分分配却没意识到有任务/机器人被漏掉。 - 根本原因:linear_sum_assignment(C)约定C[i,j]为第 \(i\) 行(行=机器人)指派到第 \(j\) 列(列=任务)的代价,返回row_ind, col_ind配对;非方阵时它做的是最大匹配,会有一侧未被完全覆盖。 - 正确做法:统一约定"行=机器人、列=任务"并写进注释;机器人数 ≠ 任务数时显式补齐(用大代价的虚拟行/列填成方阵)或确认 SciPy 的矩形矩阵语义符合预期;务必用返回的(row_ind, col_ind)成对取值,别假设顺序。
练习¶
- [实现] 实现并对比三种分配:匈牙利(
linear_sum_assignment)、贪婪、拍卖。在 \(n\in\{5,10,20,50\}\) 上各跑 200 次随机代价矩阵,画出"贪婪/拍卖相对最优的差距百分比"随 \(n\) 的变化曲线。验证:拍卖差距由 \(\varepsilon\) 控制且很小,贪婪差距随 \(n\) 变大。 - [建模/思考] 对下面三个场景,用 Gerkey–Matarić 三维(ST/MT、SR/MR、IA/TA)分别归类,并说明能否用匈牙利最优求解:(a) 5 台扫地机各扫一个房间;(b) 3 台无人机轮流巡逻 8 个点位(每机要去多个点);(c) 4 台四足合抬 2 件重物(每件需 2 机)。
- [实现/分析] 把目标从 min-sum 改成 min-max(makespan):给定机器人到任务的"耗时"矩阵,要求最小化"最后一个机器人的完工时间"。先用匈牙利求 min-sum 解,再实现一个"二分 + 可行性检查(用匈牙利判定)"的 min-max 求解器,在同一组数据上对比两种目标给出的分配差异,观察 min-sum 解里是否存在"某机器人严重超载"。
- [推导] 证明拍卖算法的总效用与最优指派的差距不超过 \(N\varepsilon\)。提示:从 \(\varepsilon\)-互补松弛条件出发(每个机器人分到的任务净收益在最优的 \(\varepsilon\) 邻域内),对 \(N\) 台机器人求和。这道题让你理解 \(\varepsilon\) 如何换取"接近最优"与"收敛快慢"。
- [思考,接 §3.2] 拍卖算法里"价格 \(p_j\)"是全局共享的协调信号。设想没有中央黑板来维护这个价格,每台机器人只能和邻居通信。它们要怎样才能就"每个任务当前的最高出价是多少、归谁"达成一致?(这正是 CBBA 用共识解决的问题——带着这个问题进入下一节。)
§3.2 CBBA：基于共识的分布式拍卖 ⭐⭐⭐⭐¶
这一节解决什么问题：§3.1 的拍卖算法虽然"每个机器人看价格独立竞标",但那个价格仍假设有一块全局共享的黑板。真实多机系统没有黑板——每台机器人只能和通信范围内的邻居交换信息。CBBA(Consensus-Based Bundle Algorithm)解决的正是:在只有邻居通信的图上,如何分布式地把任务分配好且不冲突。它把任务分配的"拍卖"与第 2 章的"共识"焊接在一起,是本章与第 2 章的正式接合点,也是分布式 MRTA 最经典的算法。
动机：没有中央黑板的拍卖¶
回到 §3.1 末尾那个问题。拍卖算法需要一块全局黑板记录每个任务的当前价格,所有机器人都能读写。但在野外的无人机蜂群、灾后搜救的地面车队里,根本没有这样的中央节点——每台机器人只能和它通信范围内的几个邻居说话(这正是第 1 章的通信图)。我们想要的是:每台机器人**自己决定**接哪些任务,通过和邻居反复交换"我打算接哪些、出价多少",最终全队达成一个**无冲突**(每个任务至多一台机器人)且**总效用不太差**的分配——全程不依赖任何中央节点。
这件事难在哪?难在"无冲突"是个全局性质,而每台机器人只有局部信息。两台相距很远、暂时不能直接通信的机器人,可能各自都把同一个任务加进了自己的清单。如何让这种冲突最终被发现并消解?CBBA 给出的答案是:用**共识**——让"每个任务当前最高出价是谁"这个信息像第 2 章的共识一样在图上传播,直到全网一致。
如果用最朴素的办法会怎样¶
最朴素的分布式做法:每台机器人各自贪婪挑任务(把对自己价值最高的几个任务收入清单),然后执行。问题立刻浮现:冲突。机器人 \(r_1\) 和 \(r_3\) 可能都把 \(t_5\) 收进了清单,执行时两个一起冲向 \(t_5\),要么撞上、要么白跑一个。
退一步,加个"先到先得"的简单消解:谁先宣告接了某任务,该任务就归谁。但在只有邻居通信的图上,"先到"本身就模糊——\(r_1\) 的宣告要好几跳才能传到 \(r_3\),在这期间 \(r_3\) 早已基于过时信息做了决定。更糟的是,如果消解规则设计不当(比如允许机器人随意反悔、释放任务的顺序混乱),系统会陷入**活锁**(livelock):任务在机器人间反复易手、永不稳定。
朴素做法缺的是两样东西:一是一致的、带时间戳的冲突裁决规则(让"谁该拥有某任务"在信息不同步时也有确定答案);二是对"释放任务"的纪律约束(防止活锁,并保住性能保证)。CBBA 正是把这两样补齐——前者用带时间戳的共识,后者用 bundle 的有序结构 + DMG 条件。
历史：Choi、Brunet、How 的 CBBA¶
CBBA 由 Choi、Brunet 与 How 于 2009 年在 IEEE Transactions on Robotics 上提出(《Consensus-Based Decentralized Auctions for Robust Task Allocation》)。它有两个版本:CBAA 处理单任务分配(每机一个任务),CBBA 处理多任务分配(每机一串任务,即 bundle)。论文的核心贡献是:把拍卖的分布式竞标与共识的冲突消解结合,并**证明**了在 DMG 条件下,CBBA 产生的解与集中式顺序贪婪(SGA)完全相同,从而继承 SGA 的 50% 最优界,且在有限轮数内收敛到无冲突。这一组合至今仍是分布式 MRTA 的基准,后续大量变体(处理时间窗、异步、动态任务、预算约束等)都建立在它之上。
理论¶
一、两个数据结构:bundle 与 path¶
每台机器人 \(i\) 维护两个有序列表:
- bundle \(\mathbf b_i\):按**加入顺序**排列的任务列表——记录"我是按什么顺序把这些任务收进来的"。
- path \(\mathbf p_i\):按**执行顺序**排列的同一批任务——记录"我打算按什么顺序去做"。
区别在于:加入 bundle 时,新任务可以插进 path 的任意位置(选使总收益最大的插入点),但在 bundle 里永远追加在末尾。这个区别至关重要——冲突消解时按 **bundle 顺序**释放任务,正是保证 DMG 性质成立的关键。
二、阶段一:bundle 构建(本地贪婪)¶
每台机器人独立地、贪婪地往自己的 bundle 里加任务。给定当前 path \(\mathbf p_i\),任务 \(j\) 的**边际得分** \(c_{ij}[\mathbf p_i]\) 定义为"把 \(j\) 插入 \(\mathbf p_i\) 的最佳位置所能带来的得分增量":
其中 \(S_i^{\mathbf p}\) 是机器人 \(i\) 执行路径 \(\mathbf p\) 的总得分(如"任务奖励之和减去行程代价"),\(\oplus_k\) 表示在第 \(k\) 个位置插入。机器人每轮挑边际得分最高、且高于该任务当前已知最高出价的任务加入,直到 bundle 满(达到容量 \(L_t\))或没有任务能再提升得分。每次加入都记下自己对该任务的出价 \(y_{ij}=c_{ij}\)。
三、阶段二:基于共识的冲突消解¶
每台机器人维护三个向量(长度 = 任务数 \(M\)):
- 中标价 \(\mathbf y_i\in\mathbb R^M\):\(y_{i}(j)\) = 机器人 \(i\) 当前**已知**的任务 \(j\) 的最高出价。
- 中标者 \(\mathbf z_i\in\{1,\dots,N\}^M\):\(z_i(j)\) = 机器人 \(i\) 当前认为任务 \(j\) 归谁。
- 时间戳 \(\mathbf s_i\):记录 \(i\) 最近一次从各机器人收到信息的时间(用于裁决信息新旧)。
每个通信周期,机器人和邻居交换 \((\mathbf y,\mathbf z,\mathbf s)\),然后对每个任务按一组**确定性规则**更新(论文给出完整的"action rules"表,核心是):若邻居对任务 \(j\) 的中标价更高,就更新 \(y_i(j),z_i(j)\) 为邻居的值;若发现自己 bundle 里某个任务被别人以更高价抢走(自己被 outbid),就**把该任务连同它之后(在 bundle 里)的所有任务一起释放**,然后回到阶段一重新竞标剩余任务。时间戳用于在信息冲突时判断该信任谁的版本。
把论文的规则归纳一下,接收方 \(i\) 收到邻居 \(k\) 关于任务 \(j\) 的信息后,无非做三类动作之一——更新(采纳 \(k\) 的 \(y,z\))、重置(把 \(y_i(j)\) 清零、\(z_i(j)\) 置空)、保留(维持自己的)。具体做哪个,由"发送方 \(k\) 认为 \(j\) 归谁"和"接收方 \(i\) 认为 \(j\) 归谁"这两维共同决定:
| \(k\) 认为归谁 ＼ \(i\) 认为归谁 | \(i\) 自己 | \(k\) 自己 | 第三方 \(m\) | 无人 |
|---|---|---|---|---|
| \(k\) 自己 | \(y_k>y_i\) → 更新,否则保留 | 更新 | \(y_k>y_i\) 或 \(k\) 信息更新 → 更新 | 更新 |
| \(i\) 自己 | 保留 | 重置 | \(k\) 信息更新 → 重置 | 保留 |
| 第三方 \(m\) | \(y_k>y_i\) → 更新 | 更新 | \(k\) 信息更新且 \(y_k>y_i\) → 更新 | 更新 |
| 无人 | 保留 | 更新 | \(k\) 信息更新 → 重置 | 保留 |
读这张表的钥匙是:发送方对"自己中标的任务"最有发言权(第一行几乎都更新),而**"重置"专门处理信念矛盾**——当 \(k\) 说"这任务归你 \(i\)"、\(i\) 却以为归别人时,说明 \(i\) 的信念已过时,清零重判最稳妥。本节代码用的是同步精简版(直接取"出价更高者胜、等价按编号裁决"),它抓住了上表最主导的"更高出价者胜"情形;真实异步 CBBA 用完整的时间戳 + 上表来应对消息乱序、丢包与信息不一致,鲁棒性更强。
这一步的本质,是第 2 章的**最大值共识**:把"每个任务的最高出价" \(\mathbf y\) 当作要共识的量,通过邻居间反复取最大值(带时间戳裁决),最终全网对 \(\mathbf y,\mathbf z\) 达成一致——而 \(\mathbf y,\mathbf z\) 一致就意味着所有机器人对"每个任务归谁"看法一致,即无冲突。第 2 章共识收敛速率由图谱决定,这里则体现为:收敛轮数正比于通信图直径。
四、为什么"按 bundle 顺序释放"?DMG 与 50% 界¶
这是 CBBA 最精妙之处。当机器人被 outbid 而要释放任务 \(j\) 时,它必须把 \(j\) **以及 bundle 里排在 \(j\) 之后的所有任务**一并释放,哪怕那些后续任务没被任何人抢。原因:后加入的任务的边际得分,是在"\(j\) 已在 path 中"的前提下算出来的(见式 3.2);一旦 \(j\) 被拿走,这些后续任务的得分就不再有效。只有按加入顺序释放,才能保证每个保留下来的任务的出价始终反映其真实边际价值。
正是这条纪律,让 CBBA 等价于集中式 SGA(每轮全局挑边际最高对)。而 SGA 在效用满足**边际收益递减(DMG)**——任务 \(j\) 的边际得分不随 path 中先有别的任务而增加,即 \(c_{ij}[\mathbf p]\ge c_{ij}[\mathbf p']\) 当 \(\mathbf p\subseteq\mathbf p'\)——时,保证解不差于最优的一半:
直觉:贪婪每步拿走的边际收益,至少是它"挡掉"的最优分配中对应收益的一半(因为 DMG 保证后者的边际价值只会更低)。若效用不满足 DMG,可对得分做单调化变换(warping)强制其满足,但会牺牲一些最优性。
五、收敛性:正比于通信图直径¶
CBBA 的收敛性可这样理解:对单个任务,全网就"它归谁"达成一致,所需轮数不超过通信图直径 \(D\)(信息从中标者传到最远机器人要 \(D\) 跳);\(M\) 个任务的冲突在最坏情况下需要 \(O(N_{\min}D)\) 轮(\(N_{\min}=\min(M,NL_t)\) 为可分配任务上限)。这把第 2 章"图谱决定迭代速度"的结论具体化为一句可操作的话:通信图越"扁"(直径越小),CBBA 收敛越快。这也给工程一个直接抓手——想让分布式分配更快收敛,就让通信拓扑更连通(但别忘了第 2 章的告诫:加边增大 \(\lambda_2\) 的同时也增大 \(\lambda_N\),对时延更敏感)。
走一遍最小实例:2 台机器人、2 个任务,每机容量 1,通信图是一条链 \(R_1\!-\!R_2\)(直径 1)。出价矩阵(机器人对任务的得分)为 \(R_1:[9,8]\)、\(R_2:[7,6]\)——两台都最想要任务 1。跟着 CBBA 跑:
| 轮次 | 阶段 | \(R_1\) 的 \((\mathbf y,\mathbf z)\) | \(R_2\) 的 \((\mathbf y,\mathbf z)\) | 说明 |
|---|---|---|---|---|
| 0 | bundle 构建 | \(y{=}[9,-],z{=}[1,-]\) | \(y{=}[7,-],z{=}[2,-]\) | 两台各自拍下任务 1 |
| 1 | 共识(交换) | \(y{=}[9,-],z{=}[1,-]\) | \(y{=}[9,-],z{=}[1,-]\) | \(R_2\) 见 \(R_1\) 出价 9>7,更新:任务 1 归 \(R_1\) |
| 1 | 释放 + 重建 | \(z{=}[1,-]\) 不变 | 释放任务 1,改拍任务 2 → \(z{=}[1,2]\) | \(R_2\) 被 outbid,转而拿次优的任务 2 |
| 2 | 共识 | \(y{=}[9,6],z{=}[1,2]\) | \(y{=}[9,6],z{=}[1,2]\) | 全网一致:\(R_1\)→任务1,\(R_2\)→任务2,无冲突 |
结果与集中式 SGA 完全一致(SGA 也是先把全局最高的 \(9\) 即"\(R_1\)-任务1"定下,再定剩下的"\(R_2\)-任务2")——这正是"CBBA \(=\) SGA"的微观写照。注意收敛只用了与直径同量级的轮数。本节代码把这套逻辑在完全图/环/链三种拓扑上验证了一遍,你会看到轮数随直径(1/2/4)单调上升、而最终分配三图完全相同。
代码验证：CBBA 无冲突 + 50% 界 + 收敛随直径¶
下面实现一个精简版 CBBA(单任务版 CBAA 的多任务推广骨架),在一张通信图上运行,验证三件事:最终无冲突、总得分不差于最优一半、收敛轮数随图直径增长。
import numpy as np
import networkx as nx
rng = np.random.default_rng(2)
def cbba(reward, comm_graph, capacity):
"""精简 CBBA。reward[i,j]: 机器人 i 完成任务 j 的得分(此处用 DMG 的简单可加得分)。
comm_graph: networkx 图(机器人间通信)。capacity: 每机最多接几个任务。
返回:每机的任务集合、总得分、收敛所用通信轮数。"""
N, M = reward.shape
y = np.zeros((N, M)) # 各机已知的任务最高出价
z = -np.ones((N, M), dtype=int) # 各机认为任务归谁
bundle = [[] for _ in range(N)] # 各机 bundle(按加入顺序)
def build_bundle(i):
# 阶段一:贪婪加任务,直到满或无利可图
while len(bundle[i]) < capacity:
# 仅考虑"我出得起价"(我对它的得分 > 当前已知最高价)的任务
cand = [j for j in range(M) if j not in bundle[i]
and reward[i, j] > y[i, j]]
if not cand:
break
j = max(cand, key=lambda j: reward[i, j]) # 边际得分最高(可加得分下即 reward)
bundle[i].append(j)
y[i, j] = reward[i, j]; z[i, j] = i
for i in range(N):
build_bundle(i)
rounds = 0
changed = True
while changed:
changed = False
rounds += 1
new_y, new_z = y.copy(), z.copy()
# 阶段二:与邻居做带 agent 编号裁决的最大值共识(同步版)
for i in range(N):
for k in comm_graph.neighbors(i):
for j in range(M):
# 出价更高者胜;等价出价用 agent 编号 tie-break(模拟时间戳裁决)
if (new_y[i, j], -new_z[i, j]) < (y[k, j], -z[k, j]):
new_y[i, j] = y[k, j]; new_z[i, j] = z[k, j]
if not np.array_equal(new_y, y) or not np.array_equal(new_z, z):
changed = True # 关键:共识仍在传播就继续迭代
# 释放被抢的任务(连同 bundle 中其后的任务)
for i in range(N):
release_from = None
for idx, j in enumerate(bundle[i]):
if new_z[i, j] != i: # 我已被 outbid
release_from = idx; break
if release_from is not None:
for j in bundle[i][release_from:]: # 按 bundle 顺序释放其后全部
if new_z[i, j] == i: # 仅清掉仍以为归自己的
new_y[i, j] = 0; new_z[i, j] = -1
bundle[i] = bundle[i][:release_from]
changed = True
y, z = new_y, new_z
for i in range(N):
before = len(bundle[i]); build_bundle(i)
if len(bundle[i]) != before: changed = True
if rounds > 200: break
assign = {i: list(bundle[i]) for i in range(N)}
total = sum(reward[i, j] for i in range(N) for j in bundle[i])
return assign, total, rounds
# --- 构造一个可加得分的实例(可加得分满足 DMG) ---
N, M, cap = 5, 8, 2
reward = rng.uniform(1, 50, size=(N, M))
# 集中式上界:把它当作"每个任务分给对它得分最高的机器人(忽略容量)"的松弛上界
upper = sum(reward[:, j].max() for j in range(M))
for diam_graph, name in [
(nx.complete_graph(N), "完全图(直径1)"),
(nx.cycle_graph(N), "环(直径2)"),
(nx.path_graph(N), "链(直径4)")]:
assign, total, rounds = cbba(reward, diam_graph, cap)
# 无冲突检查:每个任务至多被一台机器人接
all_tasks = [j for i in assign for j in assign[i]]
conflict = len(all_tasks) != len(set(all_tasks))
diam = nx.diameter(diam_graph)
print(f"{name}: 收敛 {rounds:2d} 轮 | 直径 {diam} | 无冲突={not conflict} "
f"| 总得分 {total:.1f} (松弛上界 {upper:.1f})")
运行要点:三种拓扑都收敛到**无冲突**分配(每个任务至多一台机器人),且总得分相对松弛上界处于合理区间(可加得分下贪婪通常远好于 50% 的最坏界,但理论保证就是 50%)。关键观察是**收敛轮数随直径单调增长**——完全图(直径 1)几轮搞定,链(直径 4)需要更多轮。这就把第 2 章"图谱/直径决定迭代速度"的抽象结论,变成了你能在屏幕上读出的数字。注意这是同步精简版;真实 CBBA 用论文的完整 action rules 表(含时间戳裁决)来处理异步与信息不一致,鲁棒性更强。
⚠️ 常见陷阱¶
💡 概念误区:以为 CBBA 给的是最优分配 - 错误描述:把 CBBA 当成"分布式的匈牙利",期望它给出和集中最优一样的解。 - 现象/后果:在对比实验里发现 CBBA 的总效用低于匈牙利,误以为实现有 bug,反复排查。 - 根本原因:CBBA 等价于集中式**贪婪**(SGA),不是最优;它的理论保证是"不差于最优的一半"(DMG 条件下),这是分布式 + 可扩展必须付出的代价。 - 正确做法:把 CBBA 和"集中贪婪 SGA"对比(应当几乎一致),而不是和匈牙利对比;需要更优可上 CBBA 的改进变体或在小规模回退到集中最优。心里要清楚 50% 是**最坏界**,典型实例往往好得多。
🧠 思维陷阱:释放任务时不按 bundle 顺序、只释放被抢的那一个 - 错误描述:机器人被 outbid 某任务 \(j\) 时,只把 \(j\) 释放掉,保留 bundle 里 \(j\) 之后的任务。 - 现象/后果:保留任务的出价不再有效(它们是在"\(j\) 还在"的前提下算的边际价值),导致分配次优甚至持续抖动、活锁。 - 根本原因:后加入任务的边际得分依赖于先加入的任务(式 3.2);\(j\) 一走,其后任务的得分前提就塌了。只有连同其后任务一起释放,才能保持"每个出价反映真实边际价值",这也是 50% 界成立的前提。 - 正确做法:严格按 bundle(加入顺序)释放——从被抢任务起,把它及其后所有任务全部释放再重新竞标。代码里用 bundle 的索引切片
bundle[i][release_from:]实现,别用 path 顺序。⚠️ 编程陷阱:得分函数不满足 DMG 却直接套用 50% 界 - 错误描述:用了一个边际得分会**随已接任务增多而上升**的效用(如"任务越多协同奖励越高"),仍指望 CBBA 收敛且有 50% 保证。 - 现象/后果:CBBA 可能不收敛(反复加任务)、或收敛到很差的解,50% 界完全失效。 - 根本原因:50% 界与"CBBA=SGA"的等价**都以 DMG 为前提**;非 DMG(如超可加、协同增益)破坏了贪婪的次模性,保证不再成立。 - 正确做法:先验证得分函数是否 DMG(边际得分非增)。常见的"奖励固定 - 行程代价"型得分通常 DMG;若有协同增益(违反 DMG),要么改用专门处理超可加的方法,要么对得分做单调化 warping(牺牲部分最优性换取收敛与保证)。
练习¶
- [实现] 在上面 CBBA 代码基础上,系统扫描通信图直径(完全图、环、链、星)与机器人数 \(N\),记录收敛轮数,画出"收敛轮数 vs 直径"的关系图。验证轮数大致正比于直径,并和第 2 章"共识收敛随图谱"的结论对照。
- [实现/验证] 构造一个集中式 SGA(每轮在所有未分配的(机器人,任务)对里挑全局边际得分最高的一对分配),在同一批随机实例上验证 CBBA 的解与 SGA 完全相同。这道题让你亲手坐实"CBBA = 分布式的 SGA"这一核心命题。
- [实现/反例] 故意构造一个**违反 DMG** 的得分函数(例如机器人接的任务越多、每个任务的得分越高,模拟协同增益),在 CBBA 里运行,观察:它是否收敛?总得分相对最优差多少?再对得分做单调化 warping 后重跑,对比效果。亲手看到"DMG 是保证的前提"。
- [推导] 证明式 (3.3):在 DMG 条件下,顺序贪婪 SGA 的总效用不小于最优的一半。提示:对贪婪每步选中的(机器人,任务)对,论证它"挤掉"的最优分配里的对的边际收益不超过它本身(用 DMG)。这把 50% 界的来历讲透。
- [设计/思考,接 §3.4 与 Ch13] CBBA 解决"谁去做哪个任务",但没说"怎么走过去不撞上"。设想把 CBBA 的输出(每台机器人一串任务及其顺序)交给一个 MAPF 求解器去规划无冲突路径。请设计这个"分配 → 路径"的接口:CBBA 该输出什么(任务序列?还是带时间窗的目标序列?),MAPF 需要什么输入,以及如果 MAPF 发现某个分配根本走不通(路径互相死锁)该如何反馈给 CBBA 重分配。这正是第 13 章 Mini-MultiBot 调度要落地的结构。
§3.3 多机路径规划(MAPF)与最优性 ⭐⭐⭐¶
这一节解决什么问题：§3.1-3.2 决定了"谁去做哪个任务"。但任务往往在不同地点,机器人要**走过去**——一群机器人在共享空间里移动,如何保证谁也不撞谁?这一节把这个问题形式化为 MAPF(Multi-Agent Path Finding):给出顶点冲突与边冲突的精确定义、两种优化目标、为何最优求解是 NP-难,以及"把多机当一个联合智能体来搜"为何会爆炸——这正是 §3.4 的 CBS 要绕开的。
动机：从"谁去做"到"怎样走不撞"¶
任务分好了:机器人 \(r_1\) 要去 \(t_3\)、\(r_2\) 要去 \(t_7\)……现在每台机器人都有了起点和目标,要在同一张地图(仓库地面、路网、栅格)上走过去。如果只有一台机器人,这就是单体最短路,A* 即可。但**一群**机器人同时在动,问题质变了:它们共享同一片空间,两台机器人不能同时占据同一个格子,也不能在同一时刻交换位置(否则就是穿模或正面相撞)。
这就是 MAPF——给定一张图、若干机器人各自的起点与目标,为**所有**机器人同时找到无碰撞的路径。它是仓库机器人(亚马逊 Kiva 系统调度上万台 AGV)、自动化港口、游戏寻路、无人机蜂群的核心问题。MAPF 看似只是"单体 A* 做 \(N\) 次",但正是"无碰撞"这个全局耦合,让它从多项式问题跃升为 NP-难。
如果用最朴素的办法会怎样¶
两种朴素极端,正好是这个领域的两端。
其一,各自独立 A*:每台机器人无视他人、各规划自己的最短路,然后一起跑。问题:必然碰撞。狭窄走廊里两台对向机器人会正面顶牛(边冲突),十字路口会同时进入同一格(顶点冲突)——而且谁也不知道该让谁,系统死锁。这是**解耦**(decoupled)的极端:快,但既不完备也不安全。
其二,联合智能体 A*:把 \(N\) 台机器人看成一个"超级智能体",它的状态是所有机器人位置的组合 \((v_1,v_2,\dots,v_N)\),在这个 \(N\) 维联合空间里跑 A*。问题:状态空间随 \(N\) 指数爆炸——每台机器人每步有约 5 个动作(上下左右 + 等待),联合分支因子就是 \(5^N\),\(N=10\) 时单步就近千万种组合。这是**耦合**(coupled)的极端:最优、完备,但计算上不可行。
MAPF 的全部技术张力就在这两端之间:解耦快但会撞,耦合对但会爆。CBS(§3.4)的精妙在于——它**搜索时是单体的(像解耦),但通过约束逐步消解冲突来保证最优(像耦合)**,从而在两端之间找到甜区。但要讲清 CBS,先得把 MAPF 本身定义严格。
历史：从拼图问题到现代 MAPF¶
MAPF 的理论源头是组合数学里的"华容道/拼图"问题:1984 年 Kornhauser 等人研究了图上的"卵石移动"(pebble motion),给出了可解性判定。机器人领域真正把它做成系统问题,是亚马逊收购的 Kiva Systems——Wurman 等人 2008 年描述了如何协调成百上千台仓库机器人,把 MAPF 推上工业舞台。理论上,Yu 与 LaValle 在 2013 年证明了 MAPF 在 sum-of-costs 与 makespan 目标下的**最优求解都是 NP-难**。2019 年 Stern 等人发表了 MAPF 的标准术语与基准(benchmark)综述,统一了顶点/边冲突的定义、目标函数、地图集合——此后 MAPF 研究有了公共的比较基准(后续 §3.5 的 LaCAM 等都在这套基准上刷分)。
理论¶
一、MAPF 的形式化定义¶
给定无向图 \(G=(V,E)\)(顶点是可站位置,边是可走的相邻移动)和 \(k\) 台机器人。机器人 \(i\) 有起点 \(s_i\in V\) 和目标 \(g_i\in V\)。时间离散为 \(t=0,1,2,\dots\)。每个时间步,每台机器人执行一个动作:移动**到相邻顶点,或**等待(停在原地)。机器人 \(i\) 的路径 \(\pi_i=(\pi_i(0),\pi_i(1),\dots)\) 是它在各时刻所在的顶点序列,满足 \(\pi_i(0)=s_i\)、最终停在 \(g_i\)、相邻时刻要么相同(等待)要么是 \(G\) 中的一条边(移动)。
二、两类冲突:顶点冲突与边冲突¶
两条路径"无碰撞"具体指什么?MAPF 定义两类冲突:
- 顶点冲突(vertex conflict)\(\langle i,j,v,t\rangle\):两台机器人在同一时刻 \(t\) 占据同一顶点 \(v\),即 \(\pi_i(t)=\pi_j(t)=v\)。
- 边冲突 / 交换冲突(edge / swap conflict)\(\langle i,j,u,v,t\rangle\):两台机器人在 \(t\to t{+}1\) 之间交换位置,即 \(\pi_i(t)=\pi_j(t{+}1)=u\) 且 \(\pi_i(t{+}1)=\pi_j(t)=v\)。这对应"两车在一条边上对向相遇穿模"。
一个 MAPF **解**是一组路径 \(\{\pi_1,\dots,\pi_k\}\),两两之间既无顶点冲突也无边冲突。(有些变体还定义"跟随冲突"等更严格的碰撞模型,但顶点 + 边是经典 MAPF 的标准两类。)漏掉边冲突是初学者最常见的错误——只查"同一格"会让对向交换的两台机器人"擦肩穿过"。
除了顶点和边,Stern 等人 2019 的基准还梳理了几种更严格的碰撞模型,工程上按机器人物理尺寸与控制能力选用:跟随冲突(following)——机器人 \(i\) 在 \(t{+}1\) 进入 \(j\) 在 \(t\) 刚离开的格子(像紧贴车尾跟车,若担心刹车不及需禁止);循环冲突(cycle)——三台及以上机器人首尾相接地"转圈"换位(\(i\to j\) 的位置、\(j\to k\) 的位置、\(k\to i\) 的位置同时发生),虽然两两之间不构成交换,但整体是一次不该允许的同步轮转;膨胀冲突(把机器人当成占多个格的圆盘,需保证间距)。经典 MAPF 只取顶点 + 边,是因为它假设机器人是点、动作同步、每步等长——这套最简模型抓住了碰撞的本质又便于搜索;一旦机器人有真实尺寸、速度差异或刹车距离,就要加上跟随/膨胀约束,或干脆转向 §3.8 的连续时间几何模型。选哪套碰撞模型,本质是在"安全裕度"与"通行效率/求解难度"之间权衡——模型越严越安全,但可行解越少、越难找。
| 冲突类型 | 何时发生 | 物理含义 | 何时需要禁止 |
|---|---|---|---|
| 顶点冲突 | 两机同时刻占同一格 | 两机撞在一点 | 总是(最基本) |
| 边/交换冲突 | 两机同时刻对穿一条边 | 两车对向穿模 | 总是(最基本) |
| 跟随冲突 | \(i\) 进入 \(j\) 刚离开的格 | 紧贴车尾跟车 | 担心刹车不及/惯性大时 |
| 循环冲突 | 三机及以上首尾相接同步轮转 | 一圈机器人集体转位 | 要求严格无环依赖时 |
| 膨胀/几何冲突 | 两机间距小于安全距离 | 占多格的圆盘相刮 | 机器人有真实尺寸时 |
经典 MAPF 只取前两类(点机器人 + 同步假设);后三类对应真实尺寸、刹车距离与连续运动,要么以附加约束加进搜索,要么交给 §3.8 的连续时间几何模型处理。
三、两种优化目标:sum-of-costs 与 makespan¶
无碰撞的解通常有很多,我们要最优的。两种主流目标:
- 代价和(sum-of-costs, SOC):\(\sum_{i} \mathrm{cost}(\pi_i)\),其中 \(\mathrm{cost}(\pi_i)\) 是机器人 \(i\) 到达并停在目标所用的时间步数。优化总吞吐。
- 完工时间(makespan):\(\max_i \mathrm{cost}(\pi_i)\),即最后一台机器人到达目标的时刻。优化"全部完成"的时间。
二者一般给出不同的最优解(类比 §3.1 的 min-sum vs min-max),且**都是 NP-难**(Yu & LaValle 2013)。CBS 默认优化 SOC。
举个让二者**分道扬镳**的小例子:三台机器人因共享一条窄道,无法都走最短路,必须有机器人绕行或等待。方案甲——让一台绕远(代价 10)、另两台走最短(各 2):\(\text{SOC}=14\)、\(\text{makespan}=10\)。方案乙——让三台**均摊**绕行(各 6):\(\text{SOC}=18\)、\(\text{makespan}=6\)。SOC 偏好甲(\(14<18\),总行程/总吞吐更优),makespan 偏好乙(\(6<10\),最后一台更早完成)。同一实例,两个目标给出截然不同的最优解。直觉:SOC 鼓励"牺牲少数、成全多数",makespan 鼓励"负载均衡、不让任何一台拖后腿"。所以选目标不是细节——仓库讲究整体吞吐多用 SOC,而"一批机器人必须全部就位才能开工"(如编队集结、协同搬运的预备)更看重 makespan。求解器必须明确自己在优化哪个,否则"最优"二字无从谈起。
四、耦合 vs 解耦:一条连续谱¶
把 MAPF 算法摆在"耦合↔解耦"的谱上看最清楚:
- 完全耦合(联合 A*):在 \(\prod_i\) 的联合状态空间搜索,分支因子 \(\sim b^k\)(\(b\) 为单体分支因子)。最优、完备,但指数爆炸,\(k>10\) 基本不可行。
- 完全解耦(独立规划 + 优先级):各机器人单独 A*,靠优先级/预留表避让(§3.5)。快、可扩展,但一般**不完备、不最优**。
- CBS(§3.4)居中:搜索是单体的(低层单体 A*),但用"约束树"逐步消解冲突来恢复最优性——兼得解耦的搜索效率与耦合的最优保证。这正是 CBS 被称为"耦合与解耦的连续统一"的原因。
理解了这条谱,后面所有 MAPF 算法你都能一眼定位:它在哪个位置、拿什么换什么。
代码验证：冲突检测与联合搜索的爆炸¶
先把两类冲突的检测写清楚(这是 §3.4 CBS 的基础工具),再用联合 A* 在极小实例上亲眼看分支爆炸。
import numpy as np
from itertools import product
from heapq import heappush, heappop
def pad(path, T):
"""把路径补齐到长度 T(到目标后原地等待)。"""
return list(path) + [path[-1]] * (T - len(path))
def find_first_conflict(paths):
"""检测一组路径里的第一个冲突。返回 ('vertex', i, j, v, t) 或 ('edge', i, j, u, v, t) 或 None。"""
T = max(len(p) for p in paths)
P = [pad(p, T) for p in paths]
k = len(P)
for t in range(T):
# 顶点冲突
for i in range(k):
for j in range(i + 1, k):
if P[i][t] == P[j][t]:
return ('vertex', i, j, P[i][t], t)
# 边冲突(交换)
if t + 1 < T:
for i in range(k):
for j in range(i + 1, k):
if P[i][t] == P[j][t + 1] and P[i][t + 1] == P[j][t]:
return ('edge', i, j, P[i][t], P[i][t + 1], t)
return None
def neighbors(grid, p):
r, c = p; R, C = grid.shape
out = [(r, c)] # 等待
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and grid[nr, nc] == 0:
out.append((nr, nc))
return out
def joint_astar(grid, starts, goals, max_expand=2_000_000):
"""完全耦合的联合 A*:状态=所有机器人位置的元组。用来演示分支爆炸。"""
k = len(starts)
def h(state):
return sum(abs(state[i][0] - goals[i][0]) + abs(state[i][1] - goals[i][1]) for i in range(k))
start = tuple(starts); goal = tuple(goals)
openh = [(h(start), 0, start)]; gbest = {start: 0}; expanded = 0
while openh:
f, g, s = heappop(openh); expanded += 1
if expanded > max_expand:
return None, expanded
if s == goal:
return g, expanded
# 联合后继:每台机器人各取邻居,做笛卡尔积
per_agent = [neighbors(grid, s[i]) for i in range(k)]
for moves in product(*per_agent):
# 同步检查顶点冲突与交换冲突
if len(set(moves)) != k: # 顶点冲突
continue
swap = any(moves[i] == s[j] and moves[j] == s[i]
for i in range(k) for j in range(i + 1, k))
if swap:
continue
ns = tuple(moves); ng = g + k # 每步每机 +1(SOC 近似)
if ng < gbest.get(ns, 1e9):
gbest[ns] = ng; heappush(openh, (ng + h(ns), ng, ns))
return None, expanded
# 4x4 空地,机器人数从 2 增到 5,看联合 A* 展开节点数的爆炸
grid = np.zeros((4, 4), dtype=int)
corners = [(0, 0), (3, 3), (0, 3), (3, 0), (1, 1)]
for k in range(2, 6):
starts = corners[:k]
goals = [corners[(i + k // 2) % k] for i in range(k)] # 打乱目标制造交叉
cost, expanded = joint_astar(grid, starts, goals)
print(f"k={k}: 联合 A* 展开 {expanded:>9,} 个状态 | 解代价 {cost}")
运行要点:展开的状态数随机器人数 \(k\) **超指数式**增长——这就是"把多机当一个联合智能体搜"的代价,联合分支因子 \(\sim 5^k\)。find_first_conflict 则是后面 CBS 的核心工具:它必须同时查顶点冲突**和**边冲突(注意 t+1 那段),漏掉边冲突会让对向交换的机器人"穿模"而检测不出。把这两段代码吃透,你就握有了 MAPF 的"问题语言"。
⚠️ 常见陷阱¶
💡 概念误区:只检测顶点冲突,漏掉边/交换冲突 - 错误描述:判断两条路径无碰撞时,只检查"是否在同一时刻占同一格",不检查"是否在一条边上对向交换"。 - 现象/后果:两台对向机器人在一条边上交换位置(你过来我过去)被判为"无冲突",实际执行时正面对撞或穿模。 - 根本原因:碰撞有两类——顶点冲突(\(\pi_i(t)=\pi_j(t)\))和边/交换冲突(\(\pi_i(t)=\pi_j(t{+}1)\wedge\pi_i(t{+}1)=\pi_j(t)\));只查前者漏掉后者。 - 正确做法:冲突检测必须同时查两类(见代码
find_first_conflict的t+1分支)。某些应用还需考虑"跟随冲突"等更严格模型,按机器人实际尺寸/动力学决定碰撞模型。🧠 思维陷阱:把 MAPF 当成"\(N\) 个独立单体 A*" - 错误描述:认为多机路径规划就是每台机器人各跑一次 A*,拼起来就行。 - 现象/后果:得到的路径集大概率含冲突(尤其拥挤场景),执行即死锁;或误以为"加点避让逻辑"就能补救,陷入无穷打补丁。 - 根本原因:MAPF 的难度全部来自"无碰撞"这个**机器人间的耦合约束**;去掉耦合它就退化成 \(N\) 个平凡的单体最短路。耦合正是它 NP-难的根源。 - 正确做法:从一开始就把它当作有耦合约束的联合问题对待——要么用 CBS 这类保证无冲突且最优的方法,要么用优先级规划/PIBT 这类有显式协调机制的可扩展方法,而不是 \(N\) 个独立 A* 拼凑。
⚠️ 编程陷阱:sum-of-costs 与 makespan 混用,或到达目标后等待的代价算错 - 错误描述:实现目标函数时,把 SOC(各路径长度之和)和 makespan(最长路径长度)混为一谈;或机器人到目标后继续等待时,把等待也计入代价。 - 现象/后果:不同目标给出不同最优解,混用导致"最优解"对不上;到达目标后的等待若计入代价,会错误地惩罚那些早到却需为他人让路的机器人。 - 根本原因:SOC=\(\sum_i\mathrm{cost}(\pi_i)\)、makespan=\(\max_i\mathrm{cost}(\pi_i)\) 是两个不同目标;且 \(\mathrm{cost}(\pi_i)\) 的标准定义是"到达并**留在**目标所需的时间步",到达后停在目标通常不再计费。 - 正确做法:明确选定目标(CBS 默认 SOC)并在代码里统一;计算单体代价时,只算到"最后一次离开目标后再不离开"的时刻,目标处的最终停留不计费(否则为他人让路的早到者被冤枉)。
练习¶
- [实现] 扩展
find_first_conflict,让它不仅返回第一个冲突,而是返回**所有**冲突的列表,并统计一组随机路径里顶点冲突与边冲突各占多少。在不同密度(机器人数/地图大小)下观察两类冲突的比例随拥挤程度的变化。 - [实现/分析] 用上面的
joint_astar,在固定 \(4\times 4\) 地图上把机器人数从 2 加到 6,记录展开状态数与运行时间,在对数坐标上画出来,拟合其增长阶。验证它确实随 \(k\) 指数增长,并估算在你的机器上联合 A* 大约到 \(k=?\) 就跑不动了——这给你一个"耦合方法的天花板"的体感。 - [推导/思考] 说明为什么 sum-of-costs 最优解与 makespan 最优解可能不同。构造一个 2 机器人的小例子,其 SOC 最优解的 makespan 不是最小、且 makespan 最优解的 SOC 不是最小。这道题让你理解两个目标的内在冲突(类比 §3.1 的 min-sum vs min-max)。
- [实现] 实现一个"解的合法性验证器":输入一组路径,检查 (a) 每条路径起于 \(s_i\)、终于 \(g_i\),(b) 相邻时刻是等待或合法边,(c) 无顶点冲突,(d) 无边冲突。这个验证器在 §3.4 实现 CBS、§3.5 实现优先级规划时都要反复用来确认输出正确。
- [思考,接 §3.4] 联合 A* 的爆炸来自"同时为所有机器人决策"。CBS 的思路是反过来:先让每台机器人**独立**规划(忽略他人),发现冲突后只针对冲突"打补丁"(加约束、重规划被约束的那台)。请预测:这种"先独立、按需加约束"的策略,在什么情况下会很快(冲突少时)、什么情况下仍可能退化(冲突极多、约束树爆炸)?带着预测进入下一节验证。
§3.4 CBS：冲突基搜索 ⭐⭐⭐⭐¶
这一节解决什么问题：§3.3 给出了 MAPF 的两端——独立 A* 会撞、联合 A* 会爆。CBS(Conflict-Based Search)在两端之间找到甜区:它**搜索时是单体的**(低层给每台机器人单独跑带约束的 A*),却**保证全局最优且无冲突**(高层用约束树逐个消解冲突)。这是最优 MAPF 的核心算法,也是理解后续一切 MAPF 加速方法的基线。
动机：要最优,又不想爆炸¶
我们想要 MAPF 的**最优**解(像联合 A* 那样),但联合 A* 的 \(5^N\) 分支让它在 \(N>10\) 就死。能不能既拿最优、又让搜索保持在"单体规模"?关键观察是:大多数时候,大多数机器人的路径其实互不干涉——真正冲突的往往只是少数几对机器人在少数几个位置。既然如此,何必把所有机器人的决策耦合进一个巨大的联合空间?不如让每台机器人先独立规划,只在**真正发生冲突**的地方,才施加最小的额外约束去消解它。CBS 正是这个思路的精确实现。
如果用最朴素的办法会怎样¶
朴素的"独立规划 + 打补丁"会怎么做?发现机器人 \(i,j\) 在顶点 \(v\)、时刻 \(t\) 冲突,于是"让其中一个等一步"。但**让哪一个等?** 如果只武断地让 \(i\) 等,可能错过"让 \(j\) 绕路反而总代价更小"的更优解——这就丢了最优性。这正是优先级规划(§3.5)的做法:固定一个优先级,低优先级的给高优先级的让路。它快,但**不完备也不最优**(优先级选得不好甚至无解)。
CBS 的关键改进是:面对一个冲突,它**不武断选边**,而是**两种消解都试**——开两个分支,一个约束 \(i\) 不能在 \((v,t)\)、另一个约束 \(j\) 不能在 \((v,t)\),分别重规划、分别算代价,在高层按代价做最优优先搜索。"两个分支都展开"正是 CBS 保住最优性的命门。
历史：Sharon 等人的 CBS 及其变体谱系¶
CBS 由 Sharon、Stern、Felner、Sturtevant 于 2015 年发表在 Artificial Intelligence(《Conflict-based search for optimal multi-agent pathfinding》),迅速成为最优 MAPF 的标准算法。此后衍生出一整个谱系:ICBS(Boyarski 等 2015)优先消解"关键冲突"(cardinal conflict,即消解它必然使两个子节点代价都上升的冲突)以剪枝;CBSH/CG/WDG(Felner 等 2018、Li 等 2019)给高层搜索加入可采纳启发(对约束树的代价下界估计),大幅加速;ECBS(Barer 等 2014)放宽到有界次优(用 focal search 换速度)。这些变体的共同点是:都保留 CBS 的两层骨架,只在"选哪个冲突分裂""高层如何估代价"上做文章。吃透原始 CBS,这些变体一通百通。
理论¶
一、两层结构¶
CBS 把 MAPF 拆成两层搜索:
- 高层:约束树(Constraint Tree, CT)。CT 是一棵二叉树,每个节点 \(N\) 含三样东西:一组**约束** \(N.\text{constraints}\)(形如"机器人 \(i\) 不能在时刻 \(t\) 占顶点 \(v\)"或"……不能在 \(t\) 走边 \((u,v)\)")、一组满足这些约束的**路径** \(N.\text{solution}\)(每台机器人一条)、以及代价 \(N.\text{cost}=\text{SOC}(N.\text{solution})\)。高层在 CT 上做**最优优先搜索**(按 cost 出队)。
- 低层:带约束的单体 A*。给定某机器人的约束集,低层为它单独搜一条满足所有约束的最短路(时空 A*:状态是"(顶点, 时刻)",避开被约束的时空点)。低层是**单体**的——这是 CBS 不爆炸的根本。
二、算法流程¶
- 根节点:无约束,每台机器人各跑一次普通 A*(忽略他人),得到初始路径(可能含冲突)。
- 取出代价最小的 CT 节点 \(N\)(最优优先),用
find_first_conflict检验 \(N.\text{solution}\): - 无冲突 → \(N\) 是目标节点,返回 \(N.\text{solution}\),这就是最优解。
- 有冲突 \(\langle i,j,v,t\rangle\) → 分裂:生成两个子节点 \(N_i,N_j\)。\(N_i\) 在 \(N\) 的约束上**追加** \(\langle i,v,t\rangle\)(禁止 \(i\) 在 \(t\) 占 \(v\)),\(N_j\) 追加 \(\langle j,v,t\rangle\)。对每个子节点,只重规划被新约束的那台机器人(低层 A*),其余路径不变,更新代价,入高层队列。
- 重复 2,直到取出无冲突节点。
边冲突 \(\langle i,j,u,v,t\rangle\) 的分裂类似:一个子节点禁 \(i\) 走边 \((u,v)\) at \(t\),另一个禁 \(j\) 走 \((v,u)\) at \(t\)。
三、为什么 CBS 最优且完备¶
三点合起来保证最优:(1) 低层最优——每台机器人在给定约束下走的是满足约束的最短路;(2) 高层最优优先 + 代价可采纳——CT 节点的代价 SOC 是"在该节点约束下任何无冲突解的代价下界",最优优先搜索因此像 A* 一样首次弹出的目标节点即全局最优;(3) 分裂穷尽两种消解——对每个冲突,"\(i\) 让"和"\(j\) 让"两种可能都被保留为子节点,不会因武断选边而漏掉最优解。完备性同理:若存在解,CT 的某个叶子必对应它。代价是:最坏情况下 CT 节点数随冲突数指数增长(这也是 ICBS/CBSH 等变体要剪枝/加启发的原因)。
四、与优先级规划的对比¶
| 维度 | CBS | 优先级规划(PP) |
|---|---|---|
| 最优性 | ✅ 最优(SOC) | ❌ 一般次优 |
| 完备性 | ✅ 完备 | ❌ 不完备(优先级不当可能无解) |
| 速度/可扩展 | 中(冲突少时快,多时爆) | 快,可扩展到大规模 |
| 思路 | 冲突两种消解都试 | 固定优先级,低让高 |
一句话:CBS 用"两个子节点都展开"买来了最优与完备,代价是约束树可能爆炸;PP 用"武断选边"换来了速度,代价是丢掉最优与完备。§3.5 会看到 PIBT/LaCAM 如何在 PP 这一侧把可扩展性推到极致。
五、手把手走查一棵约束树¶
抽象描述不如跟着走一遍。用最经典的"对穿"实例:\(3\times3\) 空栅格,机器人 0 从 \((1,0)\) 去 \((1,2)\),机器人 1 从 \((1,2)\) 去 \((1,0)\)——它们必须穿过同一行。
- 根节点:无任何约束,各自跑最短路。\((1,0)\to(1,2)\) 唯一的两步最短路是 \((1,0)\to(1,1)\to(1,2)\),\((1,2)\to(1,0)\) 同理走 \((1,1)\)。两条路都在 \(t{=}1\) 占用中点 \((1,1)\) → 顶点冲突 \(\langle 0,1,(1,1),1\rangle\)。根节点代价 \(\text{SOC}=2+2=4\)。
- 分裂成两个子节点,各加一条约束:
- 子节点 A:约束"机器人 0 在 \(t{=}1\) 不得在 \((1,1)\)"。只重规划机器人 0,它绕行 \((1,0)\to(0,0)\to(0,1)\to(0,2)\to(1,2)\)(代价 4),机器人 1 不变(代价 2),\(\text{SOC}=6\)。
- 子节点 B:约束"机器人 1 在 \(t{=}1\) 不得在 \((1,1)\)"。对称地让机器人 1 绕行,\(\text{SOC}=6\)。
- 高层按代价最优优先:根(\(\text{SOC}=4\))弹出后压入两个 \(\text{SOC}=6\) 的子节点;弹出其中一个,检测到**无冲突**即返回——最优解 \(\text{SOC}=6\)。
注意三个关键点:一,只重规划被约束的那台机器人(另一台路径原样保留),这是 CBS 比联合搜索高效的核心;二,两个子节点都进队列,不武断决定"谁让谁",这是最优性的来源;三,代价单调不减——加约束只会让路径变长或不变,所以根的 \(\text{SOC}\) 是全局下界,最优优先才成立。本章代码在这个实例上报告展开 4 个 CT 节点(而非最简故事里的 2 个)——多出的来自"等待"产生的等代价或更低代价、但引入了**交换冲突**的中间路径(如机器人先在起点等一步再穿过中点,就会与对向机器人在那条边上对穿),CBS 会继续对这些冲突分裂,直到弹出真正无冲突的叶子。这恰好展示了 CBS 的工作方式:把每一个冒出来的冲突,都用"两种消解各试一支"系统地化解掉。
六、CBS 的主要变体:都在跟"约束树爆炸"作斗争¶
朴素 CBS 的瓶颈只有一个——约束树随冲突数指数膨胀。后续一连串改进,几乎都是围绕"如何让约束树更小、更快收敛"展开,理解它们就理解了 CBS 这条线的演化:
| 变体 | 加了什么 | 收益 | 仍最优? |
|---|---|---|---|
| ICBS(改进 CBS) | 优先消解 cardinal 冲突(分裂后两支代价都必涨的冲突) | 优先处理"必涨"冲突,更快逼近无冲突 | ✅ |
| CBSH / CG / DG / WDG | 给高层 A* 加**可采纳启发**(用冲突图/依赖图估计还要涨多少代价) | 高层更像有信息的 A*,展开节点大减 | ✅ |
| 对称性消解(mutex 等) | 识别并一次性排除对称的等价冲突 | 避免在对称子树上重复劳动 | ✅ |
| 绕行(bypassing) | 冲突可通过等代价改路"绕开"时,不分裂、直接换路 | 省下大量本要分裂的节点 | ✅ |
| ECBS / EECBS(§3.7) | 高低层改**焦点搜索**,放弃最优换有界次优 | 规模与速度大增 | ❌(有界次优) |
前五种保持最优、只把树修小,第六种(§3.7 详述)则干脆放松最优性换规模。一句话:CBS 框架的强大,正在于这些改进都能**正交地叠加**进"约束树 + 低层搜索"这套骨架而不破坏其正确性。
代码验证：CBS 求最优无冲突解¶
下面实现一个最小但完整的 CBS:低层是带时空约束的 A*,高层在约束树上做最优优先搜索。复用 §3.3 的 find_first_conflict 与 neighbors。
from heapq import heappush, heappop
import itertools
def astar_st(grid, start, goal, vc, ec, max_t=64):
"""时空 A*:vc=该机器人的顶点约束集{(v,t)},ec=边约束集{(u,v,t)}(t->t+1 禁走 u->v)。
返回到达并可停留在 goal 的最短路径(顶点序列)。"""
last_goal_con = max([t for (v, t) in vc if v == goal], default=-1) # 目标上最晚的约束
def h(p): return abs(p[0] - goal[0]) + abs(p[1] - goal[1])
start_s = (start, 0)
openh = [(h(start), 0, start, 0)]
came, g_best = {}, {start_s: 0}
while openh:
f, g, p, t = heappop(openh)
if p == goal and t > last_goal_con: # 到目标且其后无约束逼它离开
path = [p]
while (p, t) in came:
p, t = came[(p, t)]; path.append(p)
return path[::-1]
for np_ in neighbors(grid, p):
nt = t + 1
if (np_, nt) in vc: continue # 顶点约束
if (p, np_, t) in ec: continue # 边约束(t 时刻从 p 走到 np_)
ns = (np_, nt)
if nt <= max_t and g + 1 < g_best.get(ns, 1e9):
g_best[ns] = g + 1; came[ns] = (p, t)
heappush(openh, (g + 1 + h(np_), g + 1, np_, nt))
return None
def soc(paths): return sum(len(p) - 1 for p in paths)
def cbs(grid, starts, goals, max_nodes=100000):
"""最优 CBS(sum-of-costs)。返回(无冲突路径集, 代价, 展开的CT节点数)。"""
k = len(starts)
def low_level(constraints):
paths = []
for i in range(k):
# 顶点约束 ('v',agent,v,t) 与边约束 ('e',agent,u,v,t) 混在一个集合里:
# 先按首元素区分类型,再各自解包(不同长度的元组不能统一解包)
vc = {(v, t) for c in constraints if c[0] == 'v'
for (_, a, v, t) in [c] if a == i}
ec = {(u, v, t) for c in constraints if c[0] == 'e'
for (_, a, u, v, t) in [c] if a == i}
p = astar_st(grid, starts[i], goals[i], vc, ec)
if p is None: return None
paths.append(p)
return paths
root_paths = low_level(set())
counter = itertools.count()
openh = [(soc(root_paths), next(counter), set(), root_paths)]
expanded = 0
while openh:
cost, _, constraints, paths = heappop(openh); expanded += 1
if expanded > max_nodes: return None, None, expanded
conf = find_first_conflict(paths)
if conf is None:
return paths, cost, expanded # 首个无冲突节点即最优
if conf[0] == 'vertex':
_, i, j, v, t = conf
children = [('v', i, v, t), ('v', j, v, t)]
else:
_, i, j, u, v, t = conf
children = [('e', i, u, v, t), ('e', j, v, u, t)]
for con in children:
new_con = set(constraints); new_con.add(con)
new_paths = low_level(new_con)
if new_paths is not None:
heappush(openh, (soc(new_paths), next(counter), new_con, new_paths))
return None, None, expanded
# --- 经典交叉:3x3 空地,两机对角互换,直行会在中心交换冲突 ---
grid = np.zeros((3, 3), dtype=int)
starts = [(1, 0), (1, 2)] # 左、右
goals = [(1, 2), (1, 0)] # 互换
paths, cost, expanded = cbs(grid, starts, goals)
print(f"CBS: SOC={cost} | 展开CT节点 {expanded} | 无冲突={find_first_conflict(paths) is None}")
for i, p in enumerate(paths):
print(f" 机器人{i}: {p}")
运行要点:两台机器人要在 \(3\times 3\) 地图上互换位置,直行会在中心格交换冲突;CBS 通过约束树发现冲突、分裂出"机器人 0 不走中心边 / 机器人 1 不走中心边"两个子节点,最终让其中一台绕行一格,返回**无冲突且 SOC 最优**的解,且只展开了少数几个 CT 节点(冲突少 → 树小)。你可以把它和 §3.3 联合 A* 在同一实例上对比:CBS 的搜索全程是单体 A*(低层),却拿到了和联合 A* 一样的最优解——这就是"耦合的最优性 + 解耦的效率"。把机器人数加多、地图改窄,你会看到展开节点数随冲突增多而上升,直观感受 CBS 的可扩展边界。
⚠️ 常见陷阱¶
💡 概念误区:冲突只展开一个子节点(只让一方避让) - 错误描述:发现冲突后,只生成"让机器人 \(i\) 避让"这一个子节点,不生成"让 \(j\) 避让"的另一个。 - 现象/后果:退化成了优先级规划——丢掉最优性(可能"让 \(j\)"才是更优解),甚至丢掉完备性(唯一可行解恰在被砍掉的那支)。 - 根本原因:CBS 最优性的核心论证是"对每个冲突,两种消解都保留为子节点";只展开一支等于武断选边,违背了这条命门。 - 正确做法:每个冲突**必须**分裂出两个子节点(顶点冲突约束 \(i\)/约束 \(j\);边冲突约束两个方向),都入高层队列。要想加速,用 ICBS 优先选 cardinal conflict、用 CBSH 加可采纳启发,而不是砍子节点。
🧠 思维陷阱:低层 A* 只避当前冲突点,不遵守该节点的全部约束 - 错误描述:在子节点重规划时,只让被约束的机器人避开"这次新加的"那个时空点,忽略它从祖先节点继承下来的其它约束。 - 现象/后果:重规划出的路径违反了祖先约束,导致已消解的旧冲突复活,约束树陷入死循环、永不收敛。 - 根本原因:CT 节点的约束是**沿树路径累积**的——子节点继承父节点的全部约束再加一条;低层必须遵守该节点的**完整**约束集。 - 正确做法:低层 A* 的输入是该 CT 节点的**全部**约束(代码里
new_con = set(constraints); new_con.add(con)),时空 A* 在扩展时对每条约束都检查(顶点约束查(v,t)、边约束查(u,v,t))。⚠️ 编程陷阱:时空 A* 的目标判定忽略"目标点上的未来约束" - 错误描述:低层 A* 一旦机器人到达目标顶点就立即返回,不管目标点在更晚的时刻是否还有约束。 - 现象/后果:机器人"提前到达"并停在目标,但目标点在后续某时刻有约束(比如它得给路过的他人让出目标格),返回的路径其实违反约束,上层据此判定无冲突却是错的。 - 根本原因:MAPF 里机器人到达目标后要**停留**,若目标格在更晚时刻被约束(他人要路过),机器人必须先离开再回来或延后到达;只看"首次到达"会漏掉这种约束。 - 正确做法:目标判定要求"到达目标且其后**不再**有针对该机器人在目标格的约束"(代码里
t > last_goal_con,last_goal_con为目标格上最晚的顶点约束时刻);否则继续搜索更晚到达或绕行的路径。
练习¶
- [实现/验证] 跑通上面的 CBS,然后用 §3.3 练习 4 的"合法性验证器"确认 CBS 输出确实无冲突且起讫正确。再把同一实例喂给 §3.3 的联合 A*,验证两者 SOC 相同(都最优)。这道题坐实"CBS 用单体搜索拿到了联合最优"。
- [实现/分析] 在 \(8\times8\) 地图上随机布置 \(k\in\{2,\dots,8\}\) 台机器人(随机起讫),对每个 \(k\) 跑 CBS 多次,记录展开的 CT 节点数与求解时间。画出它们随 \(k\) 的增长,并和 §3.3 联合 A* 的曲线叠在一起——直观看到 CBS 的增长比联合 A* 平缓得多(但冲突极多时仍会上扬)。
- [实现] 给 CBS 加一个小优化:在选择"分裂哪个冲突"时,优先选 cardinal conflict(分裂后两个子节点代价都严格上升的冲突)。对比加与不加时展开的 CT 节点数。这就是 ICBS 的核心思想,你会看到它显著减小约束树。
- [实现/对比] 实现一个**优先级规划**(给机器人固定优先级,按序用时空 A* 规划、把已规划者的路径作为后规划者的动态障碍),在同一批实例上和 CBS 比较:(a) 优先级规划快多少;(b) 它的 SOC 比 CBS 差多少;(c) 是否存在 CBS 有解而某些优先级顺序下优先级规划无解的实例。亲手看到"速度 vs 最优/完备"的取舍(这也铺垫 §3.5)。
- [推导/思考] 论证 CBS 的最优性:为什么 CT 节点的代价(SOC)是"该节点约束下任何无冲突解代价的下界"?为什么"高层最优优先 + 两子节点都展开"就能保证首个弹出的无冲突节点是全局最优?把这条论证讲清楚,你就真正理解了 CBS 为何能"单体搜索却最优"。
§3.5 可扩展 MAPF：优先级规划、PIBT 与 LaCAM ⭐⭐⭐⭐¶
这一节解决什么问题：CBS 最优、完备,但 §3.4 末尾你已看到——冲突一多,约束树就爆,它撑不到上千台机器人。可仓库里有上万台 AGV、空中有成百架无人机,而且任务**源源不断**(终身运行),根本等不起最优求解。这一节讲工程上真正用来"上规模"的方法:优先级规划 + 预留表(快但不完备)、PIBT(亚毫秒级、上千智能体)、LaCAM(惰性搜索、完备且能逼近最优)。它们用"放弃或推迟最优性"换来了可扩展与实时。
动机：当机器人有上千台、任务永不停止¶
CBS 在几十台机器人、冲突不太密时很好用,但两个现实需求把它逼到墙角。其一,规模:亚马逊仓库里上万台机器人同时跑,CBS 的约束树在这种密度下会爆炸到无法求解。其二,终身性(lifelong):仓库机器人不是"一次性从起点到目标就完事"——送完一个包裹立刻领下一个目标,系统永远在跑。每次都从头跑一遍最优 MAPF 既不现实也无必要。
工程上需要的是:**亚秒级出解、随规模近线性、能在线持续重规划**的方法,哪怕解不是最优——只要"足够好且无碰撞"。这就要回到 §3.4 一开始放弃的那一侧:解耦/优先级。但纯独立规划会死锁(§3.3 已见),所以关键是设计**轻量却有协调机制**的方法。这正是优先级规划、PIBT、LaCAM 这条线干的事。
如果用最朴素的办法会怎样¶
最朴素的可扩展尝试就是 §3.3 的"各自独立 A*"——结果死锁。稍进一步,优先级规划(给机器人排个优先级,低的给高的让路)能消除大部分死锁,也确实快。但它有两个固有缺陷,你在下面的代码里会亲眼看到:一是**不完备**——优先级排得不好,低优先级机器人可能根本找不到路(被高优先级机器人"停在目标上"堵死);二是**不最优**——固定优先级武断地决定了谁让谁,常常不是全局最优的避让方式。
更麻烦的是死锁的"升级版"——活锁(livelock):在终身、滑动窗口的设定里,如果协调规则设计不当,机器人可能反复避让、互相礼让到谁也走不动。所以可扩展方法的核心挑战是:既要轻量快速,又要有足够强的协调机制来避免死锁/活锁,最好还能带点完备性保证。PIBT 用"优先级继承 + 回溯"解决避让的局部死锁,LaCAM 在 PIBT 之上套一层搜索来恢复完备性——这是这条线的两个关键跃迁。
历史：从优先级规划到 PIBT、LaCAM¶
优先级规划是最老的多机路径思路,Erdmann 与 Lozano-Pérez 早在 1987 年就提出。2005 年 Silver 的 Cooperative A*(及其滑动窗口版 WHCA*)把"预留表 + 时空 A*"做成游戏 AI 里的标准多机寻路。真正的可扩展突破来自 Okumura 等人:2019 年提出 PIBT(Priority Inheritance with Backtracking, IJCAI 2019,期刊版 2022 年发表于 Artificial Intelligence),一个极轻量的"单步" MAPF 规划器,能在亚毫秒内为上千台机器人生成下一步的无碰撞配置。2023 年 Okumura 在 AAAI 提出 LaCAM(lazy constraints addition search for MAPF),用惰性后继生成把搜索做到既完备又能扩展到上千智能体;同年 IJCAI 的 LaCAM* 加入 anytime 机制,使它最终收敛到最优。2024 年 AAMAS 的工程化 LaCAM* 进一步优化。一个标志性事件:2023 年首届 MAPF 竞赛(League of Robot Runners)的 825 份提交中,夺冠策略的核心正是 PIBT。这条线证明了:放对了协调机制,解耦方法能在保证(完备性)与规模(上千)上同时取胜。
理论¶
一、优先级规划(PP)与预留表¶
PP 的机制:给 \(k\) 台机器人定一个优先级顺序,按序**逐台规划。规划第 \(i\) 台时,把所有已规划的高优先级机器人的路径当作**时空障碍——它们占用的每个"(顶点, 时刻)"都被记进**预留表**(reservation table),第 \(i\) 台用时空 A*(§3.4 的低层)在"未被预留的时空"里找最短路。预留表必须同时记**顶点占用**(防顶点冲突)和**边占用/反向禁止**(防交换冲突),还要处理"机器人到达目标后停在那儿"的占用(否则后续机器人会撞上停着的它)。
PP 的代价:(1) 不完备——高优先级机器人若停在某个咽喉要道(如它的目标恰在唯一通道上),低优先级机器人可能永远绕不过去,即便整体存在解;(2) 不最优——固定优先级武断决定避让方式。Silver 的 WHCA* 用**滑动窗口**(只规划未来 \(w\) 步、滚动重规划)来降低单次规划量、适应动态,但窗口太短会引入活锁。PP 快、实现简单、在不太拥挤的场景里够用,是一切可扩展 MAPF 的起点。
二、PIBT:优先级继承与回溯¶
PIBT 把视角缩到"单步":给定当前所有机器人的配置(各自所在顶点),它生成**下一时刻**的一个无碰撞、可转移的配置——即一个"one-step MAPF"求解器,反复调用就得到完整路径。它的三个关键机制:
- 自适应优先级:机器人的优先级随"等待时间"动态上升(越久没到目标、优先级越高),保证每台机器人最终都能获得高优先级、被照顾到。
- 优先级继承(priority inheritance):高优先级机器人先选它最想去的相邻顶点;若那个顶点被一台低优先级机器人占着,这台低优先级机器人就**继承**高优先级,被"推着"也得给前者让位、去找自己的下一步。
- 回溯(backtracking):若被推的机器人发现自己无处可去(所有相邻顶点都不可行),它向上回传一个"无效"信号,触发上层机器人改选次优顶点。
PIBT 的完备性有一个漂亮的图论条件:当环境图满足"任意一对相邻顶点都属于某个简单环"(例如双连通图)时,无论多少台机器人,所有机器人都能在有限时间内到达各自目标。直觉:简单环提供了"绕行让路"的回旋余地,不会出现死胡同顶死。PIBT 极轻量——每次配置生成对上千台机器人也只要亚毫秒,这正是它能撑起 2023 竞赛冠军的原因。但它是**短视的**(只看一步),整体路径质量不保证最优。
走一遍优先级继承:取一条三格走廊 \(A\!-\!B\!-\!C\)。机器人 1(高优先级)当前在 \(A\),目标在 \(C\),这一步最想去 \(B\);机器人 2(低优先级)当前正占着 \(B\)。PIBT 按优先级从高到低决策:(1) 机器人 1 先挑,它最想去的 \(B\) 被机器人 2 占着;(2) 触发**优先级继承**——机器人 2 临时获得机器人 1 的高优先级,被要求"让位",它必须为自己找一个不与已决策者冲突的下一步;(3) 机器人 2 的相邻格是 \(A\)(机器人 1 的当前位置,但机器人 1 正打算离开它去 \(B\))和 \(C\);为避免与机器人 1 的目标格 \(B\) 冲突、也避免占住 \(A\) 造成对穿,机器人 2 选择移到 \(C\);(4) 机器人 2 让出 \(B\) 后,机器人 1 顺利移入 \(B\)。最终这一步:机器人 1 走 \(A\to B\)、机器人 2 走 \(B\to C\),无碰撞,且高优先级的机器人 1 朝目标推进了一格。
再看**回溯**何时发生:若机器人 2 的所有相邻格都不可行(例如 \(C\) 也被另一台更低优先级、且同样无处可去的机器人占死),机器人 2 就向上回传"无效"信号;机器人 1 收到后放弃 \(B\)、改选次优动作(如原地等待),本步重新决策。正是"继承让高优先级能推开挡路者、回溯在推不动时优雅退让"这套机制,让 PIBT 在双连通图上既快又不会卡死——而它只看一步、不展开搜索,所以单步亚毫秒、却不保证全局最优。这与 §3.4 的 CBS"全局展开约束树求最优"形成鲜明对照:一个把算力花在"这一步谁让谁"、一个花在"全局最优排布"。
三、LaCAM:惰性约束添加搜索¶
PIBT 虽快却短视、且其完备性依赖图的环结构。LaCAM(Okumura 2023)在 PIBT 之上套一层搜索,换来**完备性**:它是一个搜索式算法(结构上类似 A*),完备、次优,核心创新是**惰性后继生成**(lazy successor generation)——本质是一个"在配置空间上的惰性深度优先搜索"。
LaCAM 的每个搜索节点存三样东西:(i) 一个**配置**(所有机器人当前所在顶点的组合)、(ii) 一棵用队列表示的**约束树**(决定从该配置生成后继时,优先尝试哪些"低层约束")、(iii) 指向**父节点**的指针(用于回溯出最终路径)。生成后继配置时,LaCAM 调用 PIBT 作为配置生成器——PIBT 负责快速产出一个满足当前约束的、无碰撞的下一配置。"惰性"体现在:不一次性枚举一个配置的所有后继(那会爆炸),而是按约束树一点点、按需地生成。LaCAM 的完备性来自:只要给足时间,它最终会搜遍整个状态空间——因此若有解必能找到。这把 PIBT 的"快但不完备/短视"升级为"快且完备"。
四、LaCAM* 与终身 MAPF¶
LaCAM*(Okumura, IJCAI 2023)给 LaCAM 加上 anytime 机制:它先快速给出一个可行解,然后随着时间推移不断改进,最终收敛到最优(当解的代价定义为"累积转移代价"时)。这正契合工程需求——先要一个能用的解,再在剩余时间里优化质量。在 MAPF 标准基准(33 张四连通栅格、共 13900 个实例、机器人数最多 1000)上,LaCAM* 解出的实例数远超此前方法。由于 MAPF 最优求解是 NP-难(Yu & LaValle 2013),"先可行、再 anytime 逼近最优"是大规模实例的务实路线。
终身 MAPF(lifelong MAPF, LMAPF)是另一个工程维度:机器人到达目标后立刻被分配**新目标**,系统持续运行(正是仓库取送货的常态)。它不是"一次性"MAPF,而需要**在线、滚动地重规划**:常用做法是周期性地用快速求解器(如 PIBT/LaCAM)对当前活跃目标重新求解一小段时间窗。LMAPF 把 §3.2 的任务分配(不断来的新任务派给谁)与本节的路径规划(派定后怎么走)**耦合**在一个永不停止的循环里——这也是 §3.6 要讨论的"分配与路径如何接起来"在终身设定下的极致形态。
把本节四种可扩展方法摆在一起对比,它们恰好是"从纯解耦逐步加回协调/搜索"的一条演进线:
| 方法 | 核心机制 | 完备性 | 最优性 | 单步/整体开销 | 典型定位 |
|---|---|---|---|---|---|
| 优先级规划 PP | 固定优先级 + 预留表,低让高 | ❌ 不完备 | ❌ 次优 | 一次规划,快 | 不拥挤场景的最简基线 |
| PIBT | 单步配置生成 + 优先级继承 + 回溯 | 双连通图上完备 | ❌ 短视次优 | 单步亚毫秒,上千台 | 实时、终身、超大规模底座 |
| LaCAM | 在配置空间上惰性 DFS,用 PIBT 作生成器 | ✅ 完备 | ❌ 次优 | 搜索,但极省内存 | 要完备 + 规模 |
| LaCAM* | LaCAM + anytime 改进 | ✅ 完备 | ✅ 最终最优 | anytime,随时可停 | 要完备 + 规模 + 渐进最优 |
这张表读下来有一条清晰主线:从 PP 到 LaCAM*,是不断给"纯解耦"加回协调与搜索——PP 完全武断,PIBT 用继承/回溯加了局部协调(换来环上完备),LaCAM 在外面套一层搜索(换来全局完备),LaCAM* 再加 anytime(换来渐进最优)。每加一层,能力更强,但也更重——这又是本章那根"协调质量 vs 计算代价"权衡轴在可扩展这一侧的细分。
代码验证：优先级规划 + 预留表(看它的快与不完备)¶
下面实现 PP + 预留表(复用 §3.4 的 astar_st、find_first_conflict、soc),并在一个**瓶颈地图**上演示它的"顺序依赖 / 不完备"——同一实例,换个优先级顺序,结果从"无解"变"有解",而 CBS 不依赖顺序、总能解。
def prioritized_planning(grid, starts, goals, order=None, max_t=48):
"""优先级规划 + 预留表。按 order 逐台规划,每台把已规划者的时空占用当障碍。
返回 (路径集, None) 成功;或 (None, 卡住的机器人) 失败——PP 不完备。"""
k = len(starts)
if order is None: order = list(range(k))
res_v, res_e = set(), set() # 预留表:顶点(v,t)、边(v,u,t)禁反向
paths = [None] * k
for i in order:
p = astar_st(grid, starts[i], goals[i], set(res_v), set(res_e), max_t)
if p is None:
return None, i # 第 i 台被堵死
paths[i] = p
for t, v in enumerate(p): res_v.add((v, t))
for t in range(len(p), max_t + 1): res_v.add((p[-1], t)) # 到目标后永久占用
for t in range(len(p) - 1):
u, v = p[t], p[t + 1]; res_e.add((v, u, t)) # 阻止他人反向交换
return paths, None
# 瓶颈+口袋地图:(1,0)、(1,2)是墙,(1,1)是连接上下两行的唯一通道
g = np.zeros((3, 3), dtype=int); g[1, 0] = 1; g[1, 2] = 1
starts = [(0, 0), (2, 0)]; goals = [(1, 1), (0, 2)] # 机器人0的目标恰是瓶颈格
for order in [[0, 1], [1, 0]]:
paths, stuck = prioritized_planning(g, starts, goals, order=order)
if paths is None:
print(f"PP order={order}: 失败! 机器人{stuck}被堵死(高优先级机器人停在瓶颈)")
else:
ok = find_first_conflict(paths) is None
print(f"PP order={order}: 成功 SOC={soc(paths)} 无冲突={ok}")
r = cbs(g, starts, goals, max_nodes=20000) # 同实例,CBS 不依赖顺序
print(f"CBS(同实例): SOC={r[1]} 展开{r[2]}个CT节点 (无论顺序都能解)")
运行要点:order=[0,1] 时,机器人 0(高优先级)规划到瓶颈格 (1,1) 并永久停在那里,把唯一通道堵死,机器人 1 找不到任何路径——PP 失败。仅仅把顺序换成 order=[1,0],让机器人 1 先过、机器人 0 后到并适当等待,就**成功**了。而 CBS 在同一实例上不依赖任何顺序、总能找到无冲突最优解。这就把"PP 快但不完备、且对优先级顺序敏感"变成了你能复现的现象——也解释了为什么工程上用 PIBT(优先级继承让被堵的机器人能推开挡路者)、用 LaCAM(套一层搜索恢复完备性)来补 PP 的这两个洞。PIBT/LaCAM 的完整实现较长(可参考 Okumura 的 pypibt 最小 Python 实现),其机制已在上面理论部分讲清。
⚠️ 常见陷阱¶
💡 概念误区:以为优先级规划/PIBT 给的是最优解 - 错误描述:把 PP 或 PIBT 的输出当成最优 MAPF 解,用它替代 CBS 还期望同样的质量。 - 现象/后果:解的总代价明显比最优差(某些机器人绕了大远路),在质量敏感的场景(如能耗、节拍)上吃亏却不自知。 - 根本原因:PP/PIBT 都在"解耦/优先级"这一侧,用最优性换可扩展;PIBT 还是**短视**的(只规划一步),整体路径不保证最优。 - 正确做法:明确需求——要最优且规模不大用 CBS;要规模/实时可接受次优用 PIBT/LaCAM;要"先可行再逼近最优"用 LaCAM*(anytime)。把"我能接受多少次优"想清楚再选。
🧠 思维陷阱:预留表只记顶点占用,漏掉边(交换)与目标永久占用 - 错误描述:实现预留表时只记录"某顶点某时刻被占",不记边的反向禁止,也不处理"机器人到目标后一直停在那儿"的占用。 - 现象/后果:后规划的机器人与已规划者发生交换冲突(穿模),或一头撞上停在目标格的高优先级机器人。 - 根本原因:多机碰撞有顶点 + 边两类(§3.3);且机器人到达目标后通常**停留**,该格在后续所有时刻都被占用,必须记进预留表。 - 正确做法:预留表三样都要记——顶点占用
(v,t)、边反向禁止(v,u,t)、目标到达后对所有未来时刻的占用(代码里for t in range(len(p), max_t+1))。这也正是 PP 不完备(目标永久占用堵死通道)的来源,要心里有数。⚠️ 编程陷阱:终身/滑动窗口里重规划不当导致活锁 - 错误描述:在终身 MAPF 里用很短的滑动窗口反复重规划,或每次重规划都重置优先级/不保留历史承诺。 - 现象/后果:机器人在路口反复"你让我、我让你",谁也不前进——活锁;或机器人在两个状态间来回抖动。 - 根本原因:窗口太短看不到死锁的"出路",或优先级/承诺不稳定导致决策反复横跳,系统进入周期性僵局。 - 正确做法:用带完备性保证的求解器(LaCAM)做底,或保证优先级单调(PIBT 的自适应优先级让久等者优先级升高、最终被照顾),滑动窗口要足够长以越过常见瓶颈,并对"长期不前进"的机器人做兜底处理(提权或全局重规划)。
练习¶
- [实现/分析] 在上面 PP 代码基础上,实现一个"随机重启"策略:PP 失败时随机打乱优先级顺序重试若干次。在多个含瓶颈的地图上统计"需要几次重启才成功"以及"成功解的 SOC 比 CBS 最优差多少"。亲手量化 PP 的不完备程度与次优程度。
- [实现] 给 PP 加滑动窗口(只规划未来 \(w\) 步、到窗口末尾再滚动重规划),做成一个简易 WHCA*。在一个机器人持续被分配新目标的终身场景里运行,观察窗口长度 \(w\) 对吞吐与活锁的影响:\(w\) 太小会活锁,\(w\) 太大退化回全局规划。
- [实现/对比] 实现一个 PIBT 的单步配置生成器(给定当前配置,按自适应优先级 + 优先级继承 + 回溯,生成下一无碰撞配置),反复调用得到完整路径。在一张双连通栅格上跑上百台机器人,记录每步耗时(应为亚毫秒级)与到达率,并和 CBS 在同规模上的求解时间对比,直观感受"亚秒 vs 跑不动"的差距。(可参考 Okumura 的
pypibt实现。) - [思考/设计] PIBT 的完备性要求"任意相邻顶点对都在某个简单环上"(如双连通)。请举出一个**不满足**该条件的地图(如带死胡同的树状走廊),说明 PIBT 在上面可能让某些机器人永远到不了目标。再设计一个最小的地图改动(加一条边)使其变双连通,恢复完备性。这道题让你理解"图的环结构 = 让路的回旋余地"。
- [思考,接 §3.6 与 Ch13] 终身 MAPF 把"任务分配(新任务派给谁)"和"路径规划(派定后怎么走)"耦合进一个永不停止的循环。请设计这个循环的架构:多久重分配一次任务、多久重规划一次路径、两者如何交接、当某机器人的路径长期走不通时如何反馈去重新分配。这正是第 13 章 Mini-MultiBot 仓库调度的核心循环。
§3.6 边界、子模视角与编队的对照 ⭐⭐⭐¶
这一节解决什么问题：前五节给了任务分配(集中/分布)与路径规划(最优/可扩展)的全套工具。这一节往后站一步,看清三件事:一,任务分配的种种"贪婪保证"(50%、\(1-1/e\))背后是同一个数学结构——子模性;二,"分配"与"路径"如何拼成一个完整系统,以及它们的耦合难点;三,本章的**离散 MAPF** 与下一 Part 的**连续编队**到底是什么关系、各自的适用边界。它把本章收口,并接通 Part 2。
动机：把碎片拼成一张完整的图¶
读到这里,你手里有一堆算法:匈牙利、拍卖、CBBA、CBS、PIBT、LaCAM。但真实系统不是单个算法——它要先分配(谁去做哪个任务)、再规划路径(怎么走不撞),而且这两步互相影响:分配时若不考虑路径会不会堵,可能派出一个"看着近、实际堵死"的方案;路径规划时分配已定,只能在既定目标下腾挪。同时你可能困惑:第 2 章讲的编队(连续、平滑)和本章的 MAPF(离散、栅格)看着像两个世界,它们到底什么关系?这一节把这些线索拧成一股。
理论¶
一、子模视角:50% 与 1−1/e 背后的同一结构¶
回看 §3.1-3.2:SGA/CBBA 在 DMG 条件下有 50% 界。这个"边际收益递减"其实就是组合优化里的**子模性**(submodularity):集合函数 \(f\) 子模 \(\iff\) 往小集合里加一个元素的增益 \(\ge\) 往它的超集里加同一元素的增益——正是 DMG。子模性是多机"分工"问题能被贪婪高效逼近的根本原因,它有两个经典保证:
- 基数约束(最多选 \(K\) 个)下,贪婪最大化单调子模函数,解 \(\ge (1-1/e)\approx 0.63\) 倍最优(Nemhauser–Wolsey–Fisher 1978)。覆盖、传感、信息增益这类多机任务效用大多是单调子模的,所以贪婪派活儿天然好用。
- 拟阵约束(matroid,如"每台机器人容量上限"这类更一般的结构)下,贪婪的保证降为 \(1/2\)——这正是 §3.2 CBBA 的 50% 界的来历(任务分配的约束是拟阵)。
把任务分配放进子模优化的框架,\(1-1/e\) 与 \(1/2\) 这些界就不再是孤立结论,而是同一棵树上的果子。分布式子模**则把这套搬到多机:Corah 与 Michael(Autonomous Robots 2019)用机器人间的顺序贪婪做分布式子模最大化并保持近似比;Xu、Garimella 与 Tzoumas(IEEE T-RO 2025)进一步处理分布式与**抗失效(部分机器人掉线仍有保证)的子模任务分配。这条线是第 2 章"分布式优化"的**离散表亲**——第 2 章的 ADMM 切分连续优化,这里的分布式贪婪切分组合优化,内核都是"用局部计算 + 有限协调逼近全局最优"。
二、把"分配"与"路径"接起来¶
一个完整的多机调度系统通常是三段:任务分配(task → robot)→ 指派/排序(每台机器人的任务序列)→ 路径规划(MAPF,把序列变成无冲突时空路径)。难点在于这三段**互相耦合**:
- 分配时**不知道**真实路径代价——你用直线距离估代价派活,但实际路径可能因拥堵远比直线长,导致"看着最优的分配,执行起来很堵"。
- 路径规划时分配**已经定死**——MAPF 只能在既定的起讫点下找无冲突路径,若分配本身就让两台机器人必然抢一条窄道,MAPF 再优也回天乏术。
务实的做法有几种:串行(先分配再规划,简单但易堵)、迭代(规划发现某分配走不通就反馈重分配,如 §3.2 练习 5)、联合(把分配与路径放进一个优化/搜索里同时解,最优但难)。终身 MAPF(§3.5)更是把这个循环做成永不停止的在线过程。第 13 章 Mini-MultiBot 的综合调度要落地的,正是这个"分配 ↔ 路径"的接口与反馈环。
三、离散 MAPF 与连续编队的边界¶
本章的 MAPF 和第 2 章的编队,看似两个世界,实则是**同一个问题在不同抽象层的两种建模**——都在回答"多个机器人如何在共享空间里不相撞地完成各自目标":
- 离散 MAPF:把空间离散成图/栅格,时间离散成步,机器人占格子、走边。适合**结构化、密集**的环境——仓库巷道、货架阵列、路网,那里位置天然离散(货位、车道),且机器人数量大、需要组合调度。
- 连续编队/控制(第 2 章 + Part 2):在连续空间里用控制律/MPC 让机器人保持队形、平滑运动。适合需要**平滑运动、物理交互、连续协调**的场景——编队飞行、协同搬运、需要考虑动力学与力的任务。
二者常常**混合**:用 MAPF 在离散层规划出无冲突的**路点序列**(谁先过路口、谁走哪条巷),再用连续控制/MPC 去**平滑跟踪**这些路点(处理动力学、避免急停急转)。这正是从本章(离散决策层)通往 Part 2(连续控制层)的桥——第 4 章的分布式 MPC 编队,可以把本章 MAPF 的离散路点当作参考轨迹来跟踪。
| 维度 | 离散 MAPF(本章) | 连续编队/控制(第 2 章 + Part 2) |
|---|---|---|
| 空间/时间 | 图/栅格 + 离散步 | 连续空间 + 连续时间 |
| 决策对象 | 走哪格、何时走、谁先过 | 控制量(速度/加速度/力) |
| 处理什么 | 组合避让、路口排序 | 动力学、平滑、物理交互 |
| 擅长场景 | 密集结构化(仓库巷道、路网) | 平滑机动、编队、协同搬运 |
| 不擅长 | 动力学、力、连续协调 | 大规模离散排序、密集路口调度 |
| 典型衔接 | 输出离散路点序列 | 跟踪这些路点(MPC 参考轨迹) |
这里最该记住的一点:它们不是竞争关系,而是**抽象层次**关系——离散 MAPF 在"决策层"决定宏观走法,连续控制在"执行层"实现微观运动。仓库里上千台 AGV 先用 MAPF 排出谁先过路口(离散),每台再用底层控制器平滑地开过去(连续);这正是第 4 章把二者接起来的出发点。
代码验证：子模贪婪的 1−1/e 界,与违反子模时的失效¶
§3.1-3.2 反复出现的"贪婪有保证"在这里有了可亲手验证的根。下面实现一个**覆盖类**任务分配:\(K\) 台传感机器人,每台覆盖一组目标点,效用 = 被覆盖的**不同**目标数(单调子模——已覆盖的目标再被覆盖不增益,正是边际递减),贪婪每轮选"新增覆盖最多"的那台。我们在小规模上枚举最优,验证贪婪解恒 \(\ge (1-1/e)\) 倍最优;再把效用换成"目标需被 \(\ge 2\) 台**同时**覆盖才算数"(协同/超可加,**违反**子模),看保证如何崩掉。
import numpy as np, math
from itertools import combinations
def make_instance(n_cand, n_targets, seed, p=0.25):
"""n_cand 个候选(机器人放置点),每个随机覆盖一组目标。"""
rng = np.random.default_rng(seed)
return [set(np.where(rng.random(n_targets) < p)[0]) for _ in range(n_cand)]
def coverage(selected, cover): # 单调子模效用:被覆盖的不同目标数
s = set()
for i in selected: s |= cover[i]
return len(s)
def greedy_cover(cover, K):
n = len(cover); sel = []
for _ in range(K): # 每轮选边际增益最大的候选
best, gain = None, -1
for i in range(n):
if i in sel: continue
g = coverage(sel + [i], cover) - coverage(sel, cover)
if g > gain: gain, best = g, i
sel.append(best)
return coverage(sel, cover)
def optimal_cover(cover, K): # 小规模枚举最优作对照
return max(coverage(c, cover) for c in combinations(range(len(cover)), K))
bound = 1 - 1 / math.e # ≈ 0.632
ratios = [greedy_cover(c := make_instance(10, 20, s), 3) / optimal_cover(c, 3)
for s in range(80)]
print(f"子模覆盖: 贪婪/最优 均值={np.mean(ratios):.3f} 最差={min(ratios):.3f} | 1-1/e={bound:.3f}")
print(f" 所有实例都 ≥ 1-1/e ? {min(ratios) >= bound - 1e-9}")
# 违反子模:目标需被 >=2 台同时覆盖才得分(协同/超可加效用 -> 边际递增,不是递减)
def coop_value(selected, cover, nt):
cnt = np.zeros(nt, dtype=int)
for i in selected:
for t in cover[i]: cnt[t] += 1
return int(np.sum(cnt >= 2))
def greedy_coop(cover, K, nt):
sel = []
for _ in range(K):
best, gain = None, -1
for i in range(len(cover)):
if i in sel: continue
g = coop_value(sel + [i], cover, nt) - coop_value(sel, cover, nt)
if g > gain: gain, best = g, i
sel.append(best)
return coop_value(sel, cover, nt)
nt = 20
cr = [greedy_coop(c := make_instance(10, nt, s, p=0.35), 3, nt) /
max(coop_value(x, c, nt) for x in combinations(range(10), 3))
for s in range(80) if max(coop_value(x, make_instance(10, nt, s, p=0.35), nt) for x in combinations(range(10), 3)) > 0]
print(f"协同(超可加,违反子模): 贪婪/最优 最差={min(cr):.3f} | 跌破 1-1/e ? {min(cr) < bound}")
运行要点:子模覆盖下,贪婪解在 80 个随机实例上的最差比值约 0.87、均值约 0.99,全部 \(\ge 1-1/e\approx0.63\)——这正是 Nemhauser–Wolsey–Fisher 定理的实测体现(它是最坏界,典型实例远好于此)。而一旦把效用换成"需两台同时覆盖才算"的协同形式(边际收益变成**递增**而非递减,违反子模),贪婪的最差比值跌到 0.5,击穿了 \(1-1/e\) 界。这把 §3.1-3.2 所有贪婪保证(CBBA 的 50%、覆盖的 \(1-1/e\))的共同前提——子模性——变成了你能在屏幕上看到的分水岭:守住子模,贪婪就有常数比保证;违反子模(强协同任务),保证就失效,这也是第 5 章协同搬运为何更难的根本原因。
多视角、对比与本质洞察¶
三个看待本章的视角:
- 优化视角:任务分配是匹配/整数规划(指派问题、子模最大化),MAPF 是带耦合约束的最短路问题。难度都来自"耦合"——去掉机器人间的约束,两者都退化成平凡问题。
- 市场/经济视角:拍卖、价格、竞标(§3.1-3.2)。任务是商品,机器人是买家,价格是协调信号——CBBA 把这个信号用共识在图上传播。
- 搜索视角:CBS、LaCAM 本质都是树搜索——在"约束/配置"空间里做最优优先或惰性 DFS,启发与剪枝决定效率。
三组对比性思维:
- CBS ↔ PIBT/LaCAM:最优 + 完备(但会爆)↔ 可扩展 + 实时(但次优/短视);分别站在 §3.3 那条"耦合↔解耦"谱的两端附近。
- 匈牙利 ↔ CBBA:集中 + 最优 ↔ 分布 + 50% 界;最优性换来了可分布式与鲁棒,这是 §3.1 到 §3.2 的核心代价。
- 一次性 MAPF ↔ 终身 MAPF:离线求一次最优 ↔ 在线滚动求"够用解";后者把分配与路径耦合进永不停止的循环,是仓库的常态。
两个本质洞察(用引用块标注):
本质洞察一:减耦合换可扩展、保耦合换最优,是贯穿整个离散决策层的同一根权衡。 匈牙利/CBS 保住全局耦合 → 最优但成本爆;贪婪/优先级/PIBT 砍掉耦合 → 可扩展但次优。这和第 1 章"全局协调 vs 局部自主"、第 2 章 ADMM 的 \(\rho\) 旋钮是**同一个权衡的不同化身**——多机系统反复在"协调的质量"与"计算/通信的代价"之间做这道选择题。认清这一点,本章十来个算法就不再是孤立技巧,而是同一根轴上的不同落点。
本质洞察二:边际收益递减(子模性)是多机"分工"可被高效逼近的统一数学根源。 它让任务分配的 50% 界(拟阵)、覆盖/传感的 \(1-1/e\) 界(基数)、CBBA 与集中贪婪的等价、分布式贪婪的近似比,统统从同一个性质里长出来(上面的代码已实测)。一旦效用违反子模(出现协同增益/超可加),这些保证就集体失效——这也是为什么"多机协作搬一件重物"(强协同、超可加)比"多机分头巡逻"(子模)在算法上难得多,并把我们引向第 5 章的协同搬运。
⚠️ 常见陷阱¶
💡 概念误区:把子模性当成凸性或线性 - 错误描述:看到"贪婪有保证"就以为目标函数是凸的/线性的,套用连续优化的直觉。 - 现象/后果:误用连续优化方法或误判问题难度;或反过来,对一个其实超可加(违反子模)的协同任务硬套贪婪 50% 界。 - 根本原因:子模是**集合函数**上的"边际收益递减",与连续函数的凸性是不同概念(虽有类比);子模最大化是 NP-难但贪婪有常数比,凸优化是多项式可解——别混。 - 正确做法:先判断效用是不是单调子模(加元素增益非增)。是,则贪婪有 \(1-1/e\)(基数)或 \(1/2\)(拟阵)保证;不是(如协同增益),换专门方法。把"子模"和"凸"严格分开。
🧠 思维陷阱:分配与路径割裂优化,分配只看直线距离 - 错误描述:任务分配阶段用"机器人到任务的直线/曼哈顿距离"当代价求最优分配,完全不考虑执行时的拥堵与路径冲突。 - 现象/后果:分配在纸面上最优,一执行就发现多台机器人挤向同一窄道、实际完工时间远超预期——"分配最优"与"系统最优"脱节。 - 根本原因:分配与路径耦合——真实代价是无冲突路径的长度,不是直线距离;在拥挤环境里两者差距巨大。 - 正确做法:在拥挤场景里,分配阶段就用更接近真实的代价估计(如考虑拥堵的路径代价、或用历史路径长度),或采用迭代/联合方法(路径规划反馈给分配),而不是一锤子直线距离分配。
⚠️ 编程陷阱:把任务分配的"通信图"和路径规划的"环境图"搞混 - 错误描述:实现时只维护一张图,把"机器人间谁能通信"(CBBA 用)和"环境里哪些位置相邻可走"(MAPF 用)混为一张。 - 现象/后果:CBBA 在错误的图上传播中标信息(收敛行为错乱),或 MAPF 在通信拓扑上找路(完全无意义)。 - 根本原因:本章有**两张本质不同的图**——通信图(节点=机器人,边=通信链路,§3.2)与环境图/栅格图(节点=位置,边=可走的相邻移动,§3.3-3.5);它们的节点集、语义、规模都不同。 - 正确做法:代码里用不同的数据结构和命名清晰区分(如
comm_graphvsenv_grid);CBBA 的收敛分析用通信图的直径,MAPF 的搜索用环境图——别让它们串味。
练习¶
- [实现/推导] 实现一个覆盖类任务的贪婪选择(如"用 \(K\) 台传感机器人覆盖最多目标点",效用=被覆盖目标数,单调子模),验证贪婪解 \(\ge (1-1/e)\) 倍最优(小规模上枚举最优对比)。再构造一个**违反子模**的协同效用(两台机器人同时覆盖才算数),观察贪婪保证失效。把 \(1-1/e\) 界与 §3.2 的 50% 界放一起,理解它们都源于子模。
- [实现/分析,综合] 搭一个最小的"分配 + 路径"流水线:用 §3.1 的匈牙利按**直线距离**分配任务,再用 §3.4 的 CBS 规划无冲突路径,记录"分配阶段估计的总距离"与"CBS 实际总路径长度"的差距。在拥挤地图上,你会看到两者差距明显——直观看到"分配与路径割裂"的代价。再尝试用"实际路径长度"迭代重分配一次,看差距是否缩小。
- [思考/设计] 给定一个具体场景,判断该用离散 MAPF、连续编队、还是混合方案,并说明理由:(a) 50 台 AGV 在网格化仓库取送货;(b) 4 架无人机保持菱形编队巡线;(c) 6 台机器人先各自到达指定货位(密集巷道)、再两两协同把大件抬到打包区。对混合方案,说明 MAPF 与连续控制各负责哪一层、如何交接。
- [推导] 说明为什么"基数约束 + 单调子模"贪婪是 \(1-1/e\),而"拟阵约束"降为 \(1/2\)。提示:\(1-1/e\) 来自每步贪婪至少拿到"剩余最优增益的 \(1/K\)",拟阵情形则用交换论证给出 \(1/2\)。把这两个界的证明骨架讲清,你就理解了 §3.1-3.2 所有贪婪保证的统一来源。
- [思考,接 Part 2] 本章末尾说"MAPF 出离散路点,连续控制平滑跟踪"。设想第 4 章的分布式 MPC 编队要跟踪本章 MAPF 给出的离散路点序列,会遇到哪些离散到连续的衔接问题:路点间如何插值成平滑参考轨迹?机器人动力学约束(不能瞬间转向/急停)与 MAPF 的"每步走一格"假设如何调和?当连续跟踪偏离离散计划(如避障绕了一下)时,是否需要触发 MAPF 重规划?带着这些问题进入 Part 2。
§3.7 有界次优与 anytime 大规模 MAPF：ECBS/EECBS 与 MAPF-LNS ⭐⭐⭐⭐¶
这一节解决什么问题：§3.4 的 CBS 最优但会爆,§3.5 的 PIBT/LaCAM 快但(除 LaCAM* 外)不给质量保证。真实工程最常落在中间地带——既要能上规模、又要对解的质量有个**可证明的把握**。这一节讲两条主流路线:有界次优(解的代价不超过最优的 \(w\) 倍,带保证)的 ECBS/EECBS,以及 anytime 大邻域搜索(先快速出一个解、再逐步改进逼近最优)的 MAPF-LNS。它们是当前大规模 MAPF 的实际主力,填上了"最优↔极速"之间最有用的那段。
动机：要规模,也要对质量心里有数¶
把 §3.4-3.5 的方法摆出来看:CBS 给最优,但几十台、冲突一密就跑不动;PIBT 亚毫秒能上千台,但路径可能绕很多冤枉路、且不给任何"离最优多远"的保证;LaCAM* 虽 anytime 最终最优,但"最终"可能很久。工程上反复出现的真实诉求是:"给我一个解,质量别太离谱(比如保证不超过最优的 1.5 倍),而且要快、要能扩展。"这就是**有界次优**(bounded-suboptimal)的用武之地——用一个用户指定的次优因子 \(w\ge 1\) 换速度,同时保证 \(\text{SOC}\le w\cdot\text{SOC}^\*\)。另一条诉求是:"先给我个能用的,然后有多少时间就优化多少。"这就是 anytime 的思路。这两条路线不是 §3.5 的替代,而是把"质量保证"这一维补回来。
如果用最朴素的办法会怎样¶
最朴素的"次优"做法:把 CBS 的最优优先随便放松一下——比如高层不严格按代价出队,挑个"看着快收敛"的节点先展开。问题:这样得到的解**没有任何质量保证**,可能离最优很远,你却不知道有多远。次优不可怕,可怕的是**无界**的次优——你无法向上游(调度系统、客户)承诺任何质量下限。所以关键不是"放松",而是**有原则地放松**:放松到什么程度、对应多大的质量损失,必须可量化、可保证。焦点搜索(focal search)正是这套原则的载体。
另一种朴素的 anytime 做法:反复用不同随机种子从头跑 PP,留最好的(random restart)。它能改进,但每次都**从零开始**、丢掉之前的搜索成果,效率低。MAPF-LNS 的关键改进是:不重启,而是**在已有解上做局部手术**——只重规划一小撮智能体,保留其余,逐步把解改好。
历史：焦点搜索、ECBS、EECBS 与 LNS¶
有界次优的工具是**焦点搜索**(focal search, Pearl & Kim 1982):在最优优先的基础上,用一个次优因子框出一批"足够好"的节点,在其中按另一个启发(如冲突数)优先展开。把它用到 MAPF,Barer 等人 2014 年提出 ECBS(Enhanced CBS),在 CBS 的高层和低层都用焦点搜索,首个有界次优 MAPF 算法。2021 年 Li、Ruml 与 Koenig 提出 EECBS(Explicit Estimation CBS, AAAI 2021),把高层的焦点搜索换成显式估计搜索(EES)并用**在线学习**估计每个 CT 节点解的代价,成为当时最快的有界次优求解器,并整合了绕行、冲突优先级、对称性消解等一系列 CBS 改进。anytime 这条线,Li 等人 2021 年提出 MAPF-LNS(基于大邻域搜索的 anytime MAPF),2022 年的 LNS2(AAAI 2022)进一步能从**带碰撞**的初始解出发,通过修复把碰撞消到零——专攻大规模实例上"连一个可行解都难找"的困境。
理论¶
一、焦点搜索与有界次优¶
回忆 A*/最优优先:用一个优先队列 OPEN 按 \(f=g+h\) 排序,每次弹出 \(f\) 最小的。**焦点搜索**在此之上加一个 FOCAL 列表:
即所有 \(f\) 值不超过当前最小 \(f\) 的 \(w\) 倍的节点。算法**从 FOCAL 里**按另一个(可不可采纳的)启发 \(h_2\)(比如"这个节点的解里还有多少冲突")挑一个展开。关键性质:由于 \(f_{\min}\) 始终是最优解代价的下界,而我们只展开 \(f\le w\cdot f_{\min}\) 的节点,最终解的代价保证 \(\le w\cdot\text{SOC}^\*\)——有界次优。\(w=1\) 时 FOCAL 退回 OPEN,就是最优搜索;\(w\) 越大,FOCAL 越宽,越能用 \(h_2\) 引导快速冲向目标,牺牲的质量上界也越大。这就是"有原则地放松最优性"。
二、ECBS 与 EECBS¶
ECBS 把焦点搜索用在 CBS 的**两层**:高层 CT 上,FOCAL 里按"解中冲突数最少"优先展开(冲突少的节点更可能接近无冲突解);低层单体 A* 上,也用焦点搜索,在"足够短"的路径里挑**与他人冲突最少**的——这能直接减小 CT 的规模(低层路径冲突少 → 高层要消解的冲突少)。整体保证 \(\text{SOC}\le w\cdot\text{SOC}^\*\)。
EECBS 指出 ECBS 的高层焦点搜索在两个启发(代价下界 vs 冲突数)负相关时会变低效,于是把高层换成**显式估计搜索**(EES):它额外维护一个对"每个 CT 节点最终解代价"的**不可采纳估计**(用在线学习从已展开节点拟合),用这个更准的估计来决定先展开谁,同时仍用可采纳的代价下界保证 \(w\)-界。EECBS 配合绕行(bypassing)、冲突优先级、对称性消解等改进,显著快于 ECBS,是有界次优 MAPF 的代表。它的骨架仍是 §3.4 的 CBS——约束树 + 低层单体搜索——只是"选哪个节点展开"用了更聪明、且仍带保证的策略。
三、MAPF-LNS:anytime 大邻域搜索¶
MAPF-LNS 走完全不同的路子——先有一个解,再改进:
- 初始解:用一个快速方法(如 §3.5 的优先级规划 PP,或 PIBT)拿一个可行但可能次优的解。
- 破坏(destroy):选一小撮智能体(一个"邻域",如随机若干个、或冲突/绕路最多的若干个),把它们的路径删掉。
- 修复(repair):把这撮智能体的路径**重新规划**——把其余智能体的当前路径当作固定的时空障碍(预留表),用 PP 或低层搜索为这撮重规划。
- 若新解总代价更低,接受;否则保留旧解。回到第 2 步,直到时间用完。
这是个 anytime 过程:任何时候停下都有一个合法解,且解随时间单调变好、逼近最优。邻域怎么选很关键(随机、基于冲突、基于代价、甚至用学习来选),直接决定改进速度。LNS2 把这套用于**修复可行性**:从一个带碰撞的初始解出发,反复选"还有碰撞的"智能体子集重规划以减少碰撞数,直到为零——这在超大规模、连可行解都难找的实例上特别有效。
四、把所有 MAPF 方法放进一张二维谱¶
到这里,本章的 MAPF 方法可以摆进一张二维图——横轴"规模/速度",纵轴"质量保证":
| 方法 | 质量保证 | 规模/速度 | 代表 |
|---|---|---|---|
| 最优 | 最优(SOC*) | 小(冲突少时尚可) | CBS、CCBS |
| 有界次优 | \(\le w\cdot\)SOC* | 中到大 | ECBS、EECBS |
| anytime | 先可行、随时间→近最优 | 大 | MAPF-LNS、LaCAM* |
| 无界次优/规则 | 无保证(但通常够用) | 极大、实时 | PP、PIBT、LaCAM、LNS2(修复) |
选型就是在这张图上按"我能接受多少次优 × 我要多大规模/多快"落点。这也呼应了贯穿本章的那根权衡:质量与代价的取舍,只是这里把"质量"精确成了"离最优的可证明倍数"。
代码验证一：ECBS-lite——有界次优用 \(w\) 换速度¶
先实现一个 ECBS-lite:在 §3.4 CBS 的高层换成焦点搜索(FOCAL = 代价 \(\le w\cdot\) 当前最小代价的 CT 节点,其中选**冲突最少**者展开),保证 \(\text{SOC}\le w\cdot\) 最优。复用前文的 astar_st、soc、find_first_conflict、pad。
import heapq, itertools
def count_conflicts(paths):
"""一组路径的冲突总数(顶点+边)——焦点搜索的副启发(越少越接近无冲突)。"""
T = max(len(p) for p in paths); P = [pad(p, T) for p in paths]; k = len(P); n = 0
for t in range(T):
for i in range(k):
for j in range(i + 1, k):
if P[i][t] == P[j][t]: n += 1
if t + 1 < T and P[i][t] == P[j][t + 1] and P[i][t + 1] == P[j][t]: n += 1
return n
def ecbs_lite(grid, starts, goals, w=1.5, max_nodes=100000):
"""有界次优 CBS:高层焦点搜索。OPEN 按代价排,FOCAL={cost<=w*最小代价}内选冲突最少者。
保证 SOC <= w * 最优(最小代价是最优下界)。"""
k = len(starts)
def low_level(cons):
ps = []
for i in range(k):
vc = {(v, t) for c in cons if c[0] == 'v' for (_, a, v, t) in [c] if a == i}
ec = {(u, v, t) for c in cons if c[0] == 'e' for (_, a, u, v, t) in [c] if a == i}
p = astar_st(grid, starts[i], goals[i], vc, ec)
if p is None: return None
ps.append(p)
return ps
root = low_level(set()); cnt = itertools.count()
OPEN = [(soc(root), next(cnt), frozenset(), root)]; heapq.heapify(OPEN); expanded = 0
while OPEN:
fmin = OPEN[0][0] # 当前最小代价 = 最优下界
focal = [nd for nd in OPEN if nd[0] <= w * fmin] # FOCAL: 代价在 w 倍界内
node = min(focal, key=lambda nd: count_conflicts(nd[3])) # 在 FOCAL 内选冲突最少者
OPEN.remove(node); heapq.heapify(OPEN)
cost, _, cons, paths = node; expanded += 1
if expanded > max_nodes: return None, None, expanded
conf = find_first_conflict(paths)
if conf is None: return paths, cost, expanded # 首个无冲突节点,SOC <= w*最优
if conf[0] == 'vertex':
_, i, j, v, t = conf; ch = [('v', i, v, t), ('v', j, v, t)]
else:
_, i, j, u, v, t = conf; ch = [('e', i, u, v, t), ('e', j, v, u, t)]
for c in ch:
nc = set(cons); nc.add(c); np_ = low_level(nc)
if np_ is not None:
heapq.heappush(OPEN, (soc(np_), next(cnt), frozenset(nc), np_))
return None, None, expanded
g = np.zeros((10, 10), dtype=int) # 10x10,中间一道带缺口的竖墙
for r in range(2, 8):
if r not in (4, 5): g[r, 4] = 1
s = [(2, 7), (5, 4), (4, 4), (0, 3), (7, 3), (5, 9), (7, 7), (8, 7)] # 8 台机器人
go = [(7, 1), (0, 6), (9, 6), (2, 2), (4, 8), (0, 1), (1, 5), (6, 1)]
opt = cbs(g, s, go, max_nodes=30000)
print(f"CBS 最优: SOC={opt[1]} 展开 {opt[2]} 个 CT 节点")
for w in [1.0, 1.3, 1.8]:
p, c, e = ecbs_lite(g, s, go, w=w)
print(f" ECBS-lite w={w}: SOC={c} 展开{e:>5} | SOC≤w·最优={c <= w * opt[1] + 1e-9}")
运行要点:这个实例里 CBS 求最优(SOC=66)要展开**两千多**个 CT 节点(冲突密、约束树爆)。而 ECBS-lite 只要放松一点点——\(w{=}1.3\)(允许 SOC 最多到 \(1.3\times66\))——就只展开**十几个**节点拿到 SOC=67 的解(只比最优多 1),提速约**两个数量级**,且解始终满足 \(\text{SOC}\le w\cdot\) 最优。这把 §3.7 的核心思想变成了你能在屏幕上读到的震撼数字:用可证明的微小质量损失,换取巨大的速度提升——这正是大规模 MAPF 里有界次优远比死磕最优实用的原因。注意 \(w{=}1\) 时它退回最优(SOC=66),但因焦点搜索的最少冲突引导,展开数通常已少于朴素 CBS。
代码验证二：MAPF-LNS——anytime 改进¶
下面在一张带短墙(制造拥堵)的 \(6\times6\) 栅格上,先用 §3.5 的优先级规划拿初始解,再用 MAPF-LNS 破坏-修复地改进,看 SOC 如何 anytime 地降到 CBS 最优。复用前文的 astar_st、find_first_conflict、soc、prioritized_planning、cbs。
def replan_subset(grid, starts, goals, paths, subset, max_t=50):
"""把 subset 之外的智能体当固定时空障碍,为 subset 重规划(LNS 的'修复')。"""
res_v, res_e = set(), set()
for i, p in enumerate(paths):
if i in subset: continue
for t, v in enumerate(p): res_v.add((v, t))
for t in range(len(p), max_t + 1): res_v.add((p[-1], t)) # 目标永久占用
for t in range(len(p) - 1):
u, v = p[t], p[t + 1]; res_e.add((v, u, t)) # 禁反向交换
new = {}
for i in subset: # subset 内顺序规划,彼此也要避让
p = astar_st(grid, starts[i], goals[i], set(res_v), set(res_e), max_t)
if p is None: return None
new[i] = p
for t, v in enumerate(p): res_v.add((v, t))
for t in range(len(p), max_t + 1): res_v.add((p[-1], t))
for t in range(len(p) - 1):
u, v = p[t], p[t + 1]; res_e.add((v, u, t))
return new
def mapf_lns(grid, starts, goals, init_paths, iters=200, nbr=4, seed=0):
"""anytime 大邻域搜索:反复'破坏一小撮 + 修复',接受更优解。"""
rng = np.random.default_rng(seed); k = len(starts)
paths = [list(p) for p in init_paths]; best = soc(paths); hist = [best]
for _ in range(iters):
subset = list(rng.choice(k, size=min(nbr, k), replace=False)); rng.shuffle(subset)
new = replan_subset(grid, starts, goals, paths, subset)
if new is not None:
cand = [new.get(i, paths[i]) for i in range(k)]
if find_first_conflict(cand) is None and soc(cand) < best: # 更优才接受
paths = cand; best = soc(cand)
hist.append(best)
return paths, best, hist
g = np.zeros((6, 6), dtype=int); g[3, 1] = g[3, 2] = g[3, 3] = 1 # 第3行一道带缺口的短墙
s = [(1, 0), (4, 5), (0, 2), (0, 1), (4, 4), (5, 0)] # 6 台机器人起点
go = [(3, 0), (1, 2), (5, 2), (4, 0), (2, 3), (0, 0)] # 目标(制造拥堵与绕行)
pp, _ = prioritized_planning(g, s, go, order=list(range(6)), max_t=50) # 初始解
fp, fs, hist = mapf_lns(g, s, go, pp, iters=200, nbr=4, seed=3)
opt = cbs(g, s, go, max_nodes=30000)[1] # CBS 最优作参照
print(f"PP 初始 SOC={soc(pp)} -> LNS 最终 SOC={fs} (CBS 最优={opt})")
print(f"SOC 改进轨迹(每25轮): {[hist[i] for i in range(0, 201, 25)]}")
print(f"最终无冲突={find_first_conflict(fp) is None}")
运行要点:优先级规划给出的初始解 SOC 偏高(本例 48,因为拥堵地图下固定优先级让一些机器人绕了大圈),MAPF-LNS 在**数十轮**破坏-修复内就把它压到 35——恰好等于 CBS 的最优解。改进轨迹是单调下降的(anytime 的标志):任何时刻停下都有合法解,给的时间越多越接近最优。这正是大规模 MAPF 的务实哲学——不追求一步到位的最优,而是"快速可行 + 持续改进"。把邻域选择从随机改成"优先重规划绕路最多的智能体",还能更快收敛(见练习)。
⚠️ 常见陷阱¶
💡 概念误区:把"有界次优"和"无界次优/无保证"混为一谈 - 错误描述:看到 ECBS/EECBS"次优"就以为和 PIBT 一样没质量保证,或反过来以为随便放松 CBS 就有界。 - 现象/后果:向上游错误承诺质量(把无保证当有保证),或放着有界次优不用、在不需要最优时硬扛最优 CBS 的爆炸。 - 根本原因:有界次优有可证明的上界 \(\text{SOC}\le w\cdot\text{SOC}^\*\)(来自焦点搜索的 \(f_{\min}\) 下界);随意放松最优优先则没有任何界。 - 正确做法:要质量保证就用焦点搜索类方法(ECBS/EECBS),并明确写出 \(w\);只要"够用、极快"且能接受无保证,才用 PIBT/LaCAM。别把两类的保证级别搞混。
🧠 思维陷阱:LNS 的邻域(破坏哪些智能体)随便选 - 错误描述:每轮都纯随机选一撮智能体重规划,不看哪些智能体真的"有改进空间"。 - 现象/后果:大量轮次花在重规划"本来就最优"的智能体上,改进极慢,看似 anytime 实则原地踏步。 - 根本原因:LNS 的改进速度高度依赖邻域质量——重规划那些**绕路多、与他人冲突多**的智能体,才最可能降代价。 - 正确做法:用有信息的邻域选择——基于"当前路径比其单体最短路长多少"、基于冲突图的连通分量、或学习式选择(MAPF-LNS 原文比较了多种)。随机只作基线。
⚠️ 编程陷阱:LNS 修复时没把其余智能体当完整的时空障碍 - 错误描述:重规划子集时,只避开其余智能体当前所在的格子,忽略它们的边占用、以及到达目标后的永久占用。 - 现象/后果:修复出的新路径与"固定"的其余智能体产生新的边冲突或撞上停在目标的智能体,接受后整体解反而非法。 - 根本原因:修复=在"其余智能体路径固定"的子问题上重规划,这等价于优先级规划里把它们当障碍——必须包含顶点、边、目标永久占用三类预留(同 §3.5)。 - 正确做法:
replan_subset里对每个非子集智能体登记完整的时空占用(顶点(v,t)、反向边(v,u,t)、目标永久占用),并在接受前用find_first_conflict复核整体无冲突再接受。
练习¶
- [实现/分析] 在上面 MAPF-LNS 基础上,把邻域选择从"随机"改成"优先重规划当前路径比其单体最短路长得最多的智能体"。在同一拥堵实例上对比两种邻域选择的 SOC 改进曲线,验证有信息的邻域收敛更快。
- [实现] 实现一个 ECBS-lite:在 §3.4 的 CBS 上,把高层的最优优先改成焦点搜索(FOCAL = 代价 \(\le w\cdot\) 当前最小代价的 CT 节点,其中按"解中冲突数最少"优先展开)。扫描 \(w\in\{1.0,1.1,1.5,2.0\}\),记录展开的 CT 节点数与解的 SOC,验证:\(w\) 越大越快、但 SOC 越高,且始终 \(\le w\cdot\) 最优。
- [实现/对比] 在 \(w=1.5\) 下,对比你的 ECBS-lite 与 MAPF-LNS 在一批中等规模实例上的"达到该质量所需时间"。体会有界次优(一次给出带保证的解)与 anytime(持续改进、随时可停)两种范式的不同适用场景。
- [实现,接 LNS2] 改造 MAPF-LNS 为"修复可行性"模式:从一个**带碰撞**的初始解(例如各自独立 A* 拼起来)出发,每轮选"仍有碰撞的"智能体子集重规划以减少碰撞总数,直到无碰撞。这就是 LNS2 的核心思想,在 CBS 都难找到可行解的拥挤实例上试试它。
- [推导] 证明焦点搜索的有界次优性:为什么"只展开 \(f\le w\cdot f_{\min}\) 的节点"能保证返回解的代价 \(\le w\cdot\text{SOC}^\*\)?提示:\(f_{\min}\) 在搜索全程是最优解代价的下界。把这条讲清,你就理解了所有有界次优 MAPF 算法的共同根基。
§3.8 从规划到执行：连续时间、运动学约束与鲁棒执行 ⭐⭐⭐⭐¶
这一节解决什么问题：前面所有方法都默认了三个理想化假设——时间离散成等长步、机器人是无尺寸的点、所有机器人**同步**执行。真实机器人有形状、有运动学约束(不能瞬间转向/急停)、速度不一、还会被各种意外**延迟**。这一节把离散计划接到真实机器人的**鲁棒执行**:连续时间 MAPF(CCBS)、把计划后处理成时序调度(MAPF-POST / 动作依赖图 ADG)、对延迟鲁棒的 \(k\)-robust 计划,以及终身取送货 MAPD 与联合目标分配-路径 TAPF。这是让 MAPF 真正落到机器人上的"最后一公里",也是通往 Part 2 连续控制的桥。
动机：一个完美的离散计划,上了真机却撞了¶
设想你用 CBS 求出了一个完美的离散 MAPF 计划——每个时间步谁在哪格、绝无冲突。可一旦放到真机上:机器人 A 因为轮子打滑慢了半拍,机器人 B 照原计划准时到达路口,结果两者撞在一起。问题出在哪?离散 MAPF 的"无冲突"保证,建立在"所有机器人同步、每步等长"的假设上;真机一旦有延迟、有速度差异,这个时间对齐就崩了,基于时间戳的安全性随之失效。更何况真机不是点——它有尺寸(两机距离太近就刮蹭)、有运动学约束(差速轮机器人不能瞬间掉头),离散网格的"每步走一格"根本没刻画这些。
所以,从"算出一个离散计划"到"机器人安全地把它执行出来"之间,还有一大段路。这一节就讲这段路上的关键工具——它们让 MAPF 从纸面算法变成真能驱动仓库机器人、无人机蜂群的技术。
如果用最朴素的办法会怎样¶
最朴素的鲁棒执行:给每步都留出大段时间余量、让机器人慢慢走,确保"就算慢一点也不会撞"。问题:极度浪费——为了应付偶发延迟,所有机器人全程龟速,吞吐暴跌;而且余量定多大全凭拍脑袋,延迟一旦超过余量照样撞。另一种朴素做法:延迟发生时整个系统**全局重规划**。问题:重规划开销大、频繁触发会让系统卡顿,且重规划期间机器人不知所措。
真正的解法是**结构化**地处理执行不确定性:要么在规划时就把延迟容忍度**显式建模**进去(\(k\)-robust),要么把计划**后处理**成一个不依赖绝对时间、只依赖**相对顺序**的执行策略(动作依赖图)——只要保持"谁先过某个路口、谁后过"这个顺序,无论各机器人快慢、延迟多少,都不会撞。后者优雅且高效,是工业部署的主流。
历史：CCBS、MAPF-POST/ADG、k-robust 与 MAPD¶
连续时间这条线:Phillips 与 Likhachev 2011 年的 SIPP(安全区间路径规划)能在动态障碍中求时间最优路径;Andreychuk 等人 2019 年(期刊版 2022 于 AIJ)提出 CCBS(连续时间 CBS),把 CBS 框架搬到连续时间 + 几何体智能体,用 SIPP 做低层、用连续时间冲突做高层,最优且无需时间离散。执行鲁棒性这条线:Hönig 等人 2016 年(ICAPS)提出 MAPF-POST,用简单时序网络把 MAPF 计划后处理成可在非完整约束机器人上执行、保证安全距离的时序调度;2019 年(RA-L)的**动作依赖图**(Action Dependency Graph, ADG)进一步把计划编码成动作间的依赖顺序,保证延迟下仍无碰撞执行。Atzmon 等人 2018 年(SoCS)提出 \(k\)-robust MAPF,规划出能容忍至多 \(k\) 次延迟的计划。终身这条线:Ma 等人 2017 年(AAMAS)提出 MAPD(终身取送货)与 Token Passing,Ma 与 Koenig 2016 年(AAMAS)提出 TAPF / CBM(联合目标分配与路径)。这些工作把 MAPF 从"理想离散一次性"推向"真机、连续、终身"。
理论¶
一、连续时间 MAPF 与 CCBS¶
经典 MAPF 假设时间离散、每个动作恰好一步。MAPF_R(连续时间 MAPF)放开这两点:时间连续、动作时长可不同(走对角线比走直线久)、智能体有几何形状(碰撞要按形状判定)。CCBS 是它的最优解法,沿用 CBS 的两层骨架但做两处关键改造:低层用 SIPP——它在"(顶点, 安全时间区间)"的状态空间里搜索,把动态障碍(其他智能体)留下的"不安全区间"挖掉,直接求连续时间下的时间最优路径;高层的冲突变成"两个带时刻的动作 \((a_i,t_i)\) 与 \((a_j,t_j)\) 在几何上相撞",约束则指定"某动作必须避开的不安全时间区间"。CCBS 证明了在连续时间下仍保持最优与完备。它把 §3.4 的离散 CBS 推广到真机更需要的连续时间几何设定,是离散 MAPF 与连续运动之间的一座重要桥。
SIPP 的核心想法值得单独看一眼,因为它是从"离散步"跨到"连续时间"的关键。普通时空 A*(§3.4)的状态是 \((\text{顶点}, t)\),\(t\) 取整数步——若时间连续,\(t\) 有无穷多取值,状态空间炸成无穷。SIPP 的洞察:对一个顶点,真正重要的不是"哪个精确时刻能到",而是"哪些**连续时间区间**里它是安全的(无动态障碍占用)"。它把每个顶点的时间轴按其他智能体的占用切成若干**安全区间**(safe interval),状态就压缩成 \((\text{顶点}, \text{第几个安全区间})\)——有限个!走查一下:设顶点 \(v\) 被一个动态障碍在时间 \([3,5]\) 占用,则 \(v\) 的安全区间是 \([0,3)\) 与 \((5,\infty)\) 两段;SIPP 搜索时,机器人到达 \(v\) 只需记录"落在哪个安全区间",并在该区间内取**最早可行到达时刻**(越早越优)。这样连续时间被有限个区间"离散化"了,却没有丢掉任何时间精度。CCBS 把 SIPP 当低层,正是用它在连续时间里为单个智能体高效求时间最优路径;高层每加一条"避开某不安全区间"的约束,低层就在更新后的安全区间上重搜——和离散 CBS"加约束→重规划"的节奏完全一致,只是把"禁止某 \((v,t)\)"换成了"禁止某段连续区间"。
二、执行鲁棒性:从时间戳到依赖顺序¶
离散计划给的是"绝对时间戳"(第 \(t\) 步谁在哪),这在真机延迟下很脆。两类工具让执行鲁棒:
- MAPF-POST:把离散计划后处理成一个**时序调度**(plan-execution schedule)。它用一个简单时序网络(STN)编码动作间的时间约束,产出能在**非完整约束**机器人上执行、考虑运动学限制(最大平移/转向速度)、并保证机器人间**安全距离**的执行方案——多项式时间完成。
-
动作依赖图(ADG):更彻底地抛弃绝对时间,只保留**相对顺序**。ADG 把每个机器人的每个动作作为节点,加两类依赖边:同机顺序(机器人 \(i\) 的第 \(k\) 个动作必须在第 \(k{+}1\) 个之前)与**跨机顺序**(若计划中机器人 \(i\) 比 \(j\) 先经过某格 \(v\),则"\(i\) 离开 \(v\)"必须先于"\(j\) 进入 \(v\)")。执行时,只要每个机器人按**与 ADG 一致的任意顺序**推进(谁慢了就等它,绝不抢在依赖前面),则**无论各机器人速度如何、延迟多久,都保证无碰撞**。这把"安全"从脆弱的时间对齐,变成了鲁棒的顺序约束。
-
\(k\)-robust MAPF:换个思路,在**规划时**就预留延迟容忍——要求计划满足"即使任意智能体累计延迟不超过 \(k\) 步,也不会碰撞"(直观上给每个智能体留 \(k\) 步的时空缓冲)。\(k\) 越大越鲁棒、但代价越高。它和 ADG 互补:前者规划时建模延迟,后者执行时吸收延迟。
三、终身取送货 MAPD 与联合目标分配-路径 TAPF¶
把 §3.5 的终身 MAPF 落到仓库的具体形态,就是 MAPD(Multi-Agent Pickup and Delivery):任务不断到达,每个任务是"去取货点取货、再送到送货点";机器人完成一个立刻领下一个。Token Passing(TP)是其经典分布式解法——用一个"令牌"在机器人间传递,持有令牌的机器人为自己挑一个任务并规划路径(把其他机器人已规划的路径当约束),它能解所有"良构"(well-formed)实例。MAPD 正是 §3.6 那个"任务分配 ↔ 路径规划耦合"在**终身、在线**下的完整形态——分配(挑哪个任务)与路径(怎么走)在一个永不停止的循环里交织。
当任务/目标是**可互换的**(anonymous,谁去都行,只要有机器人到位),问题变成 TAPF(联合目标分配与路径,Combined Target-Assignment and Path-Finding)。它的优雅解法 CBM(Conflict-Based Min-cost-flow)把 CBS 的高层约束树保留,但低层不再是单体 A*——而是一个**最小费用最大流**:在"机器人-目标"二分结构上同时解出"谁去哪个目标"和"对应的无冲突路径"。CBM 是 §3.6"分配与路径如何接起来"这个问题最干净的**算法级**回答:当目标匿名时,分配与路径可以在一个 CBS 式框架里联合最优求解,而不必串行割裂。
把本节"从离散计划到真机"的几样工具按"在规划层还是执行层、解决什么"归一下类:
| 工具 | 作用层 | 解决的问题 | 关键机制 |
|---|---|---|---|
| CCBS | 规划层 | 连续时间、几何体、动作时长不一 | CBS + SIPP 安全区间 + 连续时间冲突 |
| MAPF-POST | 规划→执行 | 把离散计划变成可执行的运动学调度 | 简单时序网络,保证安全距离 |
| 动作依赖图 ADG | 执行层 | 延迟/速度差下仍无碰撞 | 同机 + 跨机相对顺序,谁慢等谁 |
| \(k\)-robust MAPF | 规划层 | 预留延迟容忍 | 时空缓冲,容忍至多 \(k\) 步延迟 |
| MAPD / Token Passing | 终身调度 | 持续到达的取送货任务 | 令牌传递,解良构实例 |
| TAPF / CBM | 规划层 | 目标匿名时联合分配-路径 | CBS 高层 + 最小费用流低层 |
一条清晰的分工:规划层(CCBS/k-robust/CBM)管"算出什么样的计划",执行层(ADG/MAPF-POST)管"怎么把计划安全跑出来",终身层(MAPD/TP)管"任务源源不断时怎么持续转"。三层叠起来,就是 §3.9 选型走查里那个完整仓库执行栈。
代码验证：动作依赖图(ADG)让执行对延迟鲁棒¶
下面用 §3.4 CBS 解出的 \(3\times 3\) 互换计划,构建 ADG,然后注入延迟,对比两种执行方式:朴素按时间戳执行(延迟即错位)与 ADG 顺序执行(保持依赖、谁慢等谁)。复用前文的 cbs、find_first_conflict。
def build_adg(paths):
"""构建动作依赖图(简化):记录每个格子按计划被访问的先后次序。
后访问者进入该格前,须等先访问者离开——这就是跨机顺序依赖。"""
visits = {} # cell -> [(进入步, 机器人)]
for i, p in enumerate(paths):
seen = None
for t, v in enumerate(p):
if v != seen: # 进入一个新格子(跳过原地等待)
visits.setdefault(v, []).append((t, i)); seen = v
for v in visits: visits[v].sort() # 按计划访问时间排序 = 依赖顺序
return visits
def execute_naive(paths, delay_agent, delay_steps):
"""朴素按时间戳执行:被延迟者整体后移 delay_steps,其余照原计划。返回是否无碰撞。"""
T = max(len(p) for p in paths) + delay_steps + 2
pos = []
for i, p in enumerate(paths):
pp = ([p[0]] * delay_steps + list(p)) if i == delay_agent else list(p)
pos.append(pp + [pp[-1]] * (T - len(pp)))
return find_first_conflict(pos) is None
def execute_adg(paths, visits, delay_agent, delay_steps):
"""按 ADG 执行:想进入格子 v 前,须等所有'计划中更早访问 v 的机器人'已离开 v。
被延迟者起步晚 delay_steps。返回 (无碰撞?, 全到达?)。"""
k = len(paths)
comp = [] # 各机'压缩路径'(去掉原地等待)
for p in paths:
c, seen = [], None
for v in p:
if v != seen: c.append(v); seen = v
comp.append(c)
rank = {} # (格子) -> {机器人: 访问次序}
for v, lst in visits.items():
for r, (t, i) in enumerate(lst): rank.setdefault(v, {})[i] = r
ptr = [0] * k; cur = [comp[i][0] for i in range(k)]
left = {v: 0 for v in visits} # 某格已被多少个'更早访问者'离开
start = [delay_steps if i == delay_agent else 0 for i in range(k)]
for step in range(200):
if all(ptr[i] == len(comp[i]) - 1 for i in range(k)):
return True, True
occ = {cur[i] for i in range(k)}
for i in range(k):
if step < start[i] or ptr[i] >= len(comp[i]) - 1: continue
nxt = comp[i][ptr[i] + 1]
if left[nxt] < rank[nxt][i]: continue # ADG 依赖:更早访问者还没离开 nxt
if nxt in occ: continue # 物理顶点占用
old = cur[i]; cur[i] = nxt; ptr[i] += 1
occ.discard(old); occ.add(nxt)
left[old] = rank[old][i] + 1 # 我离开 old,更新其离开计数
if len(set(cur)) != k: # 顶点碰撞
return False, False
return True, all(ptr[i] == len(comp[i]) - 1 for i in range(k))
grid3 = np.zeros((3, 3), dtype=int)
s3, g3 = [(1, 0), (1, 2)], [(1, 2), (1, 0)] # 两机互换
plan = cbs(grid3, s3, g3)[0]
visits = build_adg(plan)
for D in [0, 2, 4]:
naive = execute_naive(plan, delay_agent=0, delay_steps=D)
adg, done = execute_adg(plan, visits, delay_agent=0, delay_steps=D)
print(f"延迟{D}步: 朴素时间戳执行 无碰撞={naive} | ADG执行 无碰撞={adg} 全到达={done}")
运行要点:无延迟时两种执行都安全。一旦机器人 0 被延迟(2 步、4 步),朴素按时间戳执行就会碰撞——因为机器人 1 照原时刻推进,而机器人 0 滞后,原本错开的时空对齐被打破。而 ADG 执行始终无碰撞且全员到达:机器人 1 在要进入某个"机器人 0 计划中更早经过的格子"前,会自动等机器人 0 先离开,无论它慢多少。这把执行的安全性从"脆弱的绝对时间"转成了"鲁棒的相对顺序"——正是仓库里上千台速度不一、时有延迟的机器人能安全跑 MAPF 计划的关键。注意这是简化版 ADG(只演示跨机格子顺序);完整 MAPF-POST/ADG 还要处理边、运动学限制与安全距离。
⚠️ 常见陷阱¶
💡 概念误区:以为离散 MAPF 计划可以直接在真机上同步执行 - 错误描述:把 CBS/PIBT 算出的"第 \(t\) 步谁在哪格"直接当指令发给真机,假设所有机器人严格同步、每步等长。 - 现象/后果:真机一有速度差异或延迟,基于时间戳的无冲突保证立刻失效,发生碰撞。 - 根本原因:离散 MAPF 的安全性依赖"同步 + 单位步长"假设;真机有运动学、有延迟、速度不一,绝对时间对齐不成立。 - 正确做法:计划与执行解耦——用 MAPF-POST 后处理成考虑运动学的时序调度,或用 ADG 把安全性转成相对顺序(执行时谁慢等谁),或用 \(k\)-robust 在规划时预留延迟容忍。绝不裸用时间戳直发真机。
🧠 思维陷阱:用加大时间余量来对抗延迟 - 错误描述:为应付延迟,给每步加大段固定余量、让机器人慢行,以为"够慢就不会撞"。 - 现象/后果:吞吐暴跌(全程龟速),且余量是拍脑袋定的——延迟一旦超过余量照样撞,鲁棒性是假的。 - 根本原因:固定时间余量既浪费又无保证;它没有从根本上解决"绝对时间对齐脆弱"的问题。 - 正确做法:用依赖顺序(ADG)而非时间余量来保证安全——ADG 下机器人按需等待(只在依赖未满足时等),既不浪费、又对任意延迟鲁棒;要在规划层建模就用 \(k\)-robust 给出可证明的延迟容忍。
⚠️ 编程陷阱:ADG 只建同机顺序、漏掉跨机的格子访问顺序(或反之) - 错误描述:构建 ADG 时只连"同一机器人前后动作"的边,忘了连"不同机器人对同一格子的访问先后"的边。 - 现象/后果:执行时后到的机器人不会等先到的离开,照样撞;ADG 形同虚设。 - 根本原因:ADG 的安全性来自**两类**依赖——同机顺序(保证单机动作有序)与跨机格子顺序(保证共享格子按计划次序使用);缺一类就不安全。 - 正确做法:两类边都要建。跨机边:对每个格子,按计划访问时间排序,后访问者"进入"依赖于前访问者"离开"(代码里
left[nxt] < rank[nxt][i]即在检查这条依赖)。完整实现还需处理边的依赖与目标停留。
练习¶
- [实现/扩展] 给上面的 ADG 执行加入**随机延迟**:每步每个机器人以概率 \(p\) 停一拍。在多组随机延迟下运行,验证 ADG 执行始终无碰撞、全员到达,而朴素时间戳执行的碰撞率随 \(p\) 上升。统计 ADG 执行的总完成时间随 \(p\) 如何增长。
- [实现] 把 ADG 的依赖从"格子访问顺序"扩展到**边**:若计划中机器人 \(i\) 在 \(i\) 先走过边 \((u,v)\)、\(j\) 后走同一条边,加一条依赖边。验证在更密集的实例上,加了边依赖的 ADG 执行仍无碰撞。
- [实现/对比,接 \(k\)-robust] 实现一个简单的 \(k\)-robust 检查:给定一个 MAPF 计划,验证"任意单个机器人延迟至多 \(k\) 步时是否仍无碰撞"。对比一个普通(0-robust)计划与一个人工加了缓冲的计划在这个检查下的表现,体会规划时建模延迟与执行时吸收延迟两条路线的差异。
- [思考/设计:CCBS] 在连续时间几何设定下,两台圆形机器人沿交叉直线运动可能在某个连续时刻"擦碰"。说明为什么离散 MAPF 的"顶点/边冲突"无法刻画这种连续碰撞,以及 CCBS 用"带时刻的动作冲突 + 不安全时间区间约束"如何解决。不必实现 SIPP,讲清思路即可。
- [综合设计:MAPD/TAPF,接 Ch13] 设计一个仓库 MAPD 系统的执行栈:上层用 Token Passing 做终身任务分配(或当目标匿名时用 TAPF/CBM 联合分配-路径),中层用 §3.5 的 LaCAM/PIBT 快速规划路径,底层用 ADG 做对延迟鲁棒的执行。说明三层如何交接、各自的输入输出、以及某机器人长期延迟时如何反馈到上层重分配。这正是第 13 章 Mini-MultiBot 仓库调度要落地的完整执行栈。
§3.9 方法全景：学习式 MAPF 与选型决策 ⭐⭐⭐¶
这一节解决什么问题：前八节给了一大堆方法——匈牙利、CBBA、CBS、ECBS/EECBS、MAPF-LNS、PP、PIBT、LaCAM、CCBS、ADG……面对一个真实问题,到底该选哪个?这一节做两件事:一,补上方法谱的**第三条路**——学习式 MAPF(用神经网络/强化学习直接学策略或引导搜索),它是近年的活跃前沿、也通往第 10-11 章的 MARL;二,把全章方法收进**一张总表 + 一套选型决策框架**,让你拿到问题能快速定位该用什么。这是本章的收口与索引。
动机：方法很多,怎么选才不踩坑¶
工程里两种典型的错都很常见:过度工程——明明几十台机器人、实时性要求高,却非要上最优 CBS,结果跑不动;欠工程——需要质量保证或完备性的场合,图省事用了优先级规划,结果偶发死锁或解很差还不自知。选对方法,一半靠理解每个方法"拿什么换什么"(这正是前八节反复强调的),一半靠一个能落地的决策流程。与此同时,这几年又冒出一条新路线——学习式 MAPF,它不再显式搜索,而是让神经网络从数据里学会"怎么走/怎么搜",在去中心化、实时、不确定的真实场景里有独特优势,但也带来"无保证、难泛化"的新问题。把它纳入全景,你对 MAPF 的认知地图才完整。
理论¶
一、学习式 MAPF:搜索与规则之外的第三条路¶
前面的方法可归为两类:搜索式(CBS、ECBS/EECBS、LaCAM、CCBS——在某种空间里搜索)与**规则式**(PP、PIBT——按固定规则一步步生成)。**学习式**是第三类:用机器学习从数据里获得求解能力。它有三种典型用法:
- 直接学策略:把 MAPF 当成多智能体强化学习问题,每个机器人学一个"看局部观测 → 选下一步动作"的策略,执行时**去中心化、反应式**地走。代表是 PRIMAL(Sartoretti 等,RA-L 2019)——结合强化学习与模仿学习(用专家 MAPF 规划器的演示来训练),学出完全去中心化的策略,在部分可观测世界里反应式规划、隐式协调,实验做到上千智能体;其终身版 PRIMAL2 面向密集仓库。这条路天然适配"中央规划器缺席、需在线重算"的真实部署。
- 学习引导搜索:不取代搜索,而是用学习让搜索更快——比如学习 CBS 里"先消解哪个冲突"、或学习 MAPF-LNS 里"破坏哪个邻域"(Huang 等 2022),还有学习"对这张地图该用哪个 MAPF 算法"(算法选择)。这类保留了搜索的保证,只把启发式换成学出来的。
- 学习 + 经典混合:把学习与经典方法的长处结合,如 LNS2+RL 用强化学习指导 LNS2 的修复,在复杂结构地图上超过 LNS2、LaCAM、EECBS。
**通信学习**这条线常用图神经网络(GNN)让机器人学会"和邻居交换什么信息以协调",如 MAGAT(消息感知图注意力网络,Li、Lin、Liu、Prorok,RA-L 2021)——这与第 1-2 章的通信图、第 10-11 章的 MARL 直接接续。
学习式的取舍很鲜明:优点**是去中心化、亚秒反应、能在线应对不确定与动态、可扩展;**代价**是**没有完备性/最优性保证、训练成本高、且面临**泛化/分布偏移**——在训练没覆盖的地图密度或团队规模上可能失效。所以当前实践中,学习式更多用于"快速反应的底座"或"引导经典搜索",纯学习独当一面尚需谨慎。它的完整机理(怎么训练这些去中心化策略、如何在团队里把全局回报分配给每台机器人、训练与执行如何解耦)是第 10-11 章 MARL 的主题,这里只把它定位进 MAPF 方法谱。
把三类范式正面对比,它们的"长板"和"软肋"几乎互补:
| 范式 | 代表 | 怎么求解 | 完备/最优 | 规模/实时 | 软肋 |
|---|---|---|---|---|---|
| 搜索式 | CBS、EECBS、LaCAM、CCBS | 在约束/配置空间搜索 | ✅ 强保证 | 中(冲突密时受限) | 约束树可能爆 |
| 规则式 | PP、PIBT | 按固定规则单步生成 | 弱/无(PIBT 限双连通) | ✅ 极强、亚毫秒 | 短视、不最优 |
| 学习式 | PRIMAL、MAGAT | 神经网络学策略/启发 | ❌ 无保证 | ✅ 去中心化反应 | 训练成本、泛化/分布偏移 |
正因互补,前沿趋势是**取长补短的混合**:用学习引导搜索(保留搜索的保证、用学习提速)、或学习 + LNS(如 LNS2+RL)。理解这张表,你就明白为什么没有"银弹"——选型(下面两小节)的本质,就是按你的问题在这三类的长短板之间做匹配。
二、本章方法全景:一张总表¶
把全章方法收进一张表,横看类别、纵看取舍:
| 方法 | 类别 | 最优性 | 完备性 | 规模 | 何时用 |
|---|---|---|---|---|---|
| 匈牙利 | 分配·集中 | 最优 | — | 中(\(O(n^3)\)) | 一对一一次性分配、要最优 |
| 拍卖 | 分配·(可分布) | \(\varepsilon\)-近似 | — | 大 | 要可分布、近最优 |
| CBBA | 分配·分布 | 50%(DMG) | — | 大 | 无中央节点、多任务序列分配 |
| 子模贪婪 | 分配 | \(1{-}1/e\)/\(\frac12\) | — | 大 | 覆盖/传感等子模效用 |
| 联合 A* | 路径·耦合 | 最优 | 完备 | 极小(\(b^k\)) | 教学/极少智能体 |
| CBS | 路径·搜索 | 最优 | 完备 | 小-中 | 要最优、冲突不太密 |
| ECBS/EECBS | 路径·搜索 | \(\le w\cdot\)最优 | 完备 | 中-大 | 要质量保证 + 规模 |
| MAPF-LNS | 路径·anytime | 趋近最优(无界) | — | 大 | 先可行再改进、随时可停 |
| LNS2 | 路径·修复 | 无界次优 | — | 极大 | 连可行解都难找时 |
| 优先级规划 | 路径·规则 | 次优 | 不完备 | 大 | 不拥挤、要快、可接受次优 |
| PIBT | 路径·规则 | 次优(短视) | 双连通图上完备 | 极大、实时 | 上千台、亚毫秒、终身 |
| LaCAM / LaCAM* | 路径·搜索 | 次优 / anytime最优 | 完备 | 极大 | 要完备 + 规模(*再要最优) |
| CCBS | 路径·连续时间 | 最优 | 完备 | 小-中 | 连续时间、几何体、运动学 |
| 学习式(PRIMAL 等) | 路径·学习 | 无保证 | 无保证 | 大、反应式 | 去中心化、在线、不确定环境 |
这张表是本章的索引——任何时候忘了"某方法拿什么换什么",回看这一行。
三、选型决策框架¶
拿到一个问题,按这个顺序问下去:
- 是分配还是路径?(本章两张图、两类问题)——分配走第 2 步,路径走第 3 步,完整系统两者都要(回 §3.6)。
- 分配:一对一一次性?→ 匈牙利(最优)。多任务序列、要分布式?→ CBBA(确认 DMG)。覆盖/传感类子模效用?→ 子模贪婪。需多机协作(MR)?→ 这是另一类(联盟形成,第 5-6 章)。
- 路径,先问规模与实时性:几十台、离线、要最优 → CBS(+ICBS/CBSH)。要质量保证又要规模 → ECBS/EECBS。要"先可行再逼近最优" → MAPF-LNS / LaCAM*。上千台、实时、终身 → PIBT/LaCAM;超大规模或连可行解都难 → LNS2/PIBT。
- 再问场景特性:连续时间/几何体/运动学 → CCBS。去中心化、在线、强不确定 → 学习式(或学习引导的经典法)。
- 最后问执行:要上真机?→ 计划用 ADG/MAPF-POST 转成鲁棒执行,或规划时上 k-robust(回 §3.8)。终身取送货?→ 上层 MAPD/Token Passing,目标匿名则 TAPF/CBM。
把上面的决策浓缩成一张"按你的处境查方法"的速查表(与前面"列方法"的总表互补——那张从方法看适用,这张从需求看方法):
| 你的处境 | 首选 | 备选/补充 |
|---|---|---|
| 一对一分配、要最优、规模小 | 匈牙利 | 拍卖(要分布式) |
| 多任务、分布式、无中央节点 | CBBA(确认 DMG) | SSI(更简单) |
| 路径要最优、几十台、可离线 | CBS | +ICBS/CBSH 提速 |
| 路径要规模 + 质量保证 | EECBS | ECBS |
| 路径先要可行、再慢慢优化 | MAPF-LNS / LaCAM* | — |
| 上千台、实时、终身 | PIBT / LaCAM | 可行性吃紧加 LNS2 |
| 连续时间/几何体/运动学 | CCBS | — |
| 去中心化、在线、强不确定 | 学习式 / 学习引导搜索 | PIBT 作底座 |
| 要上真机(有延迟/速度差) | ADG 执行 | MAPF-POST / k-robust |
| 目标可互换的联合分配-路径 | TAPF / CBM | — |
这张表配合下面的 recommend_mapf_solver 函数,就是一份"输入需求、输出方案"的随手查工具——把本章十来个方法的取舍,压缩成了你拍板时能一眼扫过的清单。
代码：把选型框架写成一个决策函数¶
把上面的决策流程固化成一个小函数,输入问题特征、输出推荐方法——它本身就是这张全景表的可执行版。
def recommend_mapf_solver(num_agents, need_optimal, need_guarantee,
lifelong=False, continuous_time=False,
decentralized=False, real_robot=False):
"""根据问题特征推荐 MAPF 方法(§3.9 选型框架的可执行版)。返回(求解器, 执行层)。"""
if continuous_time:
solver = "CCBS(连续时间+几何体,SIPP 低层)"
elif decentralized:
solver = "学习式(PRIMAL 等)或 PIBT(去中心化、反应式;注意学习式无保证)"
elif need_optimal:
solver = "CBS(+ICBS/CBSH 提速)" if num_agents <= 40 else \
"LaCAM*(anytime 最终最优,规模大时)"
elif need_guarantee: # 要有界质量保证
solver = "ECBS/EECBS(SOC ≤ w·最优)"
elif num_agents >= 500 or lifelong:
solver = "PIBT/LaCAM(上千台、实时、终身);可行性难则 LNS2"
else:
solver = "MAPF-LNS(anytime,先可行再改进)或优先级规划(不拥挤时)"
execution = "ADG/MAPF-POST 转鲁棒执行" + ("(终身:上层 Token Passing/TAPF-CBM)" if lifelong else "") \
if real_robot else "仿真同步执行即可"
return solver, execution
scenarios = [
dict(num_agents=8, need_optimal=True, need_guarantee=False), # 小规模要最优
dict(num_agents=200, need_optimal=False, need_guarantee=True), # 中大规模要保证
dict(num_agents=2000, need_optimal=False, need_guarantee=False, lifelong=True, real_robot=True), # 仓库终身真机
dict(num_agents=12, need_optimal=True, need_guarantee=False, continuous_time=True), # 连续时间
dict(num_agents=100, need_optimal=False, need_guarantee=False, decentralized=True), # 去中心化在线
]
for sc in scenarios:
solver, execu = recommend_mapf_solver(**sc)
print(f"{sc}\n -> 求解器: {solver}\n 执行层: {execu}\n")
运行要点:这个函数把 §3.9 的决策框架变成了可调用的代码——给它问题特征(规模、是否要最优/保证、是否终身/连续时间/去中心化/上真机),它返回推荐的求解器与执行层。它不是什么"智能"算法,而是把全章对"每个方法拿什么换什么"的理解结构化下来;你完全可以按自己项目的约束扩展它(加预算、加异构、加通信受限等维度)。把它和上面的全景表对照,你就拥有了一份能随手查的选型地图。
综合选型走查¶
拿一个具体场景走一遍:某电商仓库,800 台 AGV,货位网格化,任务(取货→打包)持续到达,要上真机、有通信网络。按框架:这是"分配 + 路径"完整系统(第 1 步);分配上,任务不断来、无中央调度器最稳,用 CBBA(或终身设定下的 Token Passing)在 AGV 通信图上做(第 2 步);路径上,800 台 + 实时 + 终身,选 PIBT/LaCAM 做快速规划,若某时段特别拥挤、可行性吃紧则用 LNS2 修复(第 3-4 步);上真机有延迟/速度差,计划用 ADG 转成对延迟鲁棒的执行(第 5 步);整个系统是 MAPD 的终身循环。于是落地方案 = CBBA/TP 分配 + PIBT/LaCAM 路径 + ADG 执行,外加 LNS2 兜底可行性。这正是第 13 章 Mini-MultiBot 仓库调度的蓝本。
⚠️ 常见陷阱¶
💡 概念误区:以为学习式 MAPF 是"免费午餐",能直接替代经典方法 - 错误描述:看到 PRIMAL 等能上千智能体、去中心化,就以为可以无脑用它替代 CBS/LaCAM,且期望同样可靠。 - 现象/后果:在训练分布外的地图密度/团队规模上成功率骤降、出现死锁或绕路;且无法给出任何完备性/最优性保证,质量敏感场景翻车。 - 根本原因:学习式用"无保证 + 训练/泛化成本"换"去中心化 + 反应式";它擅长的是在线、不确定、去中心化,而非"保证质量"。 - 正确做法:把学习式用在它的强项(去中心化反应、引导经典搜索、混合如 LNS2+RL),质量/完备性要求高时仍用搜索式(CBS/EECBS/LaCAM);评估时务必测训练分布外的泛化。
🧠 思维陷阱:不按需选型——过度工程或欠工程 - 错误描述:不分场景一律上最优 CBS(过度),或图省事一律用优先级规划(欠)。 - 现象/后果:过度工程在大规模/实时场景跑不动;欠工程在需要保证/完备的场景偶发死锁、解很差。 - 根本原因:没有按"规模 × 最优性需求 × 是否终身 × 真机"匹配方法——每个方法的取舍是为特定场景设计的。 - 正确做法:走 §3.9 的决策框架(或用
recommend_mapf_solver起步),按问题特征落点,而非凭习惯用同一个方法打天下。⚠️ 编程陷阱:把全景表的"规模"列当成绝对阈值硬编码 - 错误描述:把"CBS 只能到几十台""PIBT 上千台"当成精确硬阈值写进代码,不做实测。 - 现象/后果:实际规模上限高度依赖地图结构、冲突密度、时限与实现——硬编码阈值会在你的具体场景上误判(CBS 在稀疏图上能撑更多,在拥挤图上几台就爆)。 - 根本原因:表里的"规模"是数量级的经验指引,不是与你的地图/硬件无关的常数;真正的边界要在你的实例分布上测。 - 正确做法:用全景表做**初选**,再在自己的实例分布上跑基准(求解时间、成功率、SOC)确定真实边界与时限回退策略(如 CBS 超时回退 EECBS/LNS)。
练习¶
- [实现/扩展] 给
recommend_mapf_solver加更多维度:通信是否受限、是否异构机型、是否有预算约束。再补上分配侧的推荐(匈牙利/CBBA/子模贪婪/联盟形成),做成一个完整的"分配 + 路径 + 执行"选型助手,并为你自己的一个真实场景跑一遍。 - [分析] 选三个真实系统(如亚马逊仓库、无人机表演、自动化港口),分别用 §3.9 全景表与决策框架推断它们最可能用了哪类方法,并说明理由(规模、实时性、是否终身、是否上真机)。查资料验证你的推断。
- [实现/对比,接 Ch10-11] 复现一个**最小的学习式 MAPF**:在小栅格上用表格 Q-learning 或简单策略梯度,让 2-3 个智能体学"看局部观测选动作"的去中心化策略,和 §3.4 的 CBS 对比成功率与路径质量。亲手感受学习式的"反应式、无保证"与搜索式的"最优、需全局"的差异(完整 MARL 机理见第 10-11 章)。
- [思考] 学习引导搜索(如学习 CBS 选哪个冲突、学习 LNS 选哪个邻域)既保留了搜索的保证、又用学习提速。请设计一个这样的"学习 + 搜索"接口:学习模块的输入输出是什么、如何保证加入学习后仍不破坏原算法的最优性/有界次优性。这道题连接本章(搜索)与第 10-11 章(学习)。
综合练习¶
下面几道题跨越本章多个小节,把"分配 + 路径"作为一个整体来练——这正是真实多机调度系统的样子,也是第 13 章 Mini-MultiBot 要落地的能力。
- [综合实现:分配 → 路径的完整流水线] 在一张 \(10\times10\) 含障碍的栅格上,随机布置 6 台机器人和 10 个任务点(每个任务=一个要访问的格子)。先用 §3.2 的 CBBA 在一张通信图上把任务分配给机器人(每机最多 2 个,得分=固定奖励 − 路径代价,验证其 DMG),再为每台机器人确定任务访问顺序,最后用 §3.4 的 CBS 为所有机器人规划到各自首个任务的无冲突路径。报告:CBBA 的分配、收敛轮数、CBS 的 SOC 与展开节点数。这道题把 §3.1-3.4 串成一条线。
- [综合分析:三种路径方法同台对比] 在同一批 MAPF 实例(机器人数 \(k\in\{4,8,16,32\}\)、\(16\times16\) 栅格)上,跑 CBS(最优)、优先级规划(快但不完备)、以及一个 PIBT 单步生成器(可扩展)。对每个 \(k\) 记录:求解时间、SOC、成功率(完备性)。画出三条曲线,标出每种方法"撑到多大规模就力不从心"的拐点。这道题让你对 §3.4-3.5 三种方法的工程边界形成量化直觉。
- [综合设计:终身仓库调度环] 设计并实现一个简化的终身 MAPF 循环:任务持续到达一个队列,每隔 \(T_a\) 步用 CBBA 把队列中的新任务分配给空闲机器人,每隔 \(T_p\) 步用优先级规划(或 PIBT)对所有活跃路径重规划一小段窗口。机器人到达任务点即领取下一个任务。运行 500 步,统计吞吐(完成任务数)与平均任务等待时间,扫描 \(T_a,T_p\) 观察其影响。这道题是第 13 章 Mini-MultiBot 调度的原型。
- [综合推导:把本章的保证串起来] 用一页纸讲清本章所有"近似保证"的逻辑链:DMG/子模性 → 顺序贪婪 SGA 的 50%(拟阵)/\(1-1/e\)(基数)界 → CBBA 等价于 SGA 故继承 50% 界;另一条线:低层 A* 最优 + 高层最优优先 + 两子节点穷尽 → CBS 全局最优。指出这两条线分别属于"任务分配"与"路径规划",以及它们各自在什么条件下失效(违反子模 / 约束树爆炸)。
- [综合思考:离散与连续的接力] 综合 §3.6 与第 2 章:设计一个"MAPF + 编队"的混合方案,让 4 台机器人先以 MAPF 离散路径穿过一片密集障碍区(各自避让),出区后立即合成菱形编队(第 2 章的 displacement 控制)继续前进。说明两个阶段的切换条件、离散路点如何平滑成编队参考、以及若编队阶段遇到新障碍是否退回 MAPF。这道题正式接通 Part 1(离散决策)与 Part 2(连续协调)。
- [综合实现:规模上量后换求解器] 把综合练习 1 的"CBBA 分配 + 路径规划"流水线搬到更大、更拥挤的地图(如 \(20\times20\)、20 台机器人)。在路径层,分别用 CBS、ECBS-lite(\(w{=}1.5\))、MAPF-LNS 求解,记录三者的求解时间、SOC、是否在时限内出解。验证:CBS 在此规模可能超时,而 ECBS-lite/LNS 仍快速给出带保证或 anytime 改进的解——亲手体会 §3.7"规模上量就换求解器"的工程现实。
- [综合实现:从计划到鲁棒执行] 取综合练习 6 得到的一组无冲突路径,用 §3.8 的方法执行:先构建 ADG,再注入随机延迟(每步每机以概率 \(p\) 停一拍),对比"朴素时间戳执行"与"ADG 执行"在 \(p\in\{0,0.1,0.2,0.3\}\) 下的碰撞率与总完成时间。验证 ADG 执行始终零碰撞、全员到达,而朴素执行碰撞率随 \(p\) 飙升。这把"算出计划"与"安全跑出来"接成完整闭环——正是真机部署的样子。
本章常见误解汇总¶
| 常见误解 | 正确理解 |
|---|---|
| 任务分配就是"每台机器人挑最近的任务" | 那是贪婪,有全局耦合时显著次优;一对一一次性分配有最优的匈牙利(\(O(n^3)\)),贪婪/拍卖是为可扩展/分布式才用的次优解法 |
| 所有任务分配问题都能最优求解 | 仅 ST-SR-IA(一对一一次性)是多项式最优(LAP);带 MR(多机协作任务)、TA(时间展开序列)的一般 NP-难 |
| CBBA 是"分布式的匈牙利",给最优解 | CBBA 等价于集中式**贪婪**(SGA),保证是 50% 界(DMG 下),不是最优;50% 是最坏界,典型实例往往好得多 |
| CBBA 释放被抢任务时只释放那一个 | 必须连同 bundle 里其后的所有任务一起释放——后续任务的出价依赖于先有该任务,否则保证失效、易活锁 |
| CBBA 对任何得分函数都有 50% 界 | 仅当得分满足 DMG(边际收益递减/子模);违反 DMG(协同增益)时保证失效,需 warping 单调化 |
| 多机路径规划=每台机器人各跑 A* | 那必然死锁;MAPF 的难度全在"无碰撞"耦合约束,要么 CBS 求最优、要么 PIBT/LaCAM 这类有协调机制的方法 |
| 无碰撞只要"不在同一时刻占同一格" | 还有边/交换冲突(两机在一条边上对向交换);只查顶点冲突会让对向机器人穿模 |
| sum-of-costs 和 makespan 是一回事 | 前者是各路径代价之和(优化吞吐),后者是最长路径(优化全部完成时间);一般给出不同最优解,都 NP-难 |
| CBS 发现冲突让一方避让即可 | 必须分裂出"让 \(i\)"和"让 \(j\)"两个子节点都展开;只展开一支就退化成优先级规划,丢最优与完备 |
| 优先级规划/PIBT 给的是最优解 | 都在解耦侧,用最优性换可扩展;PIBT 还是短视(只一步);要最优用 CBS,要"先可行再逼近最优"用 LaCAM* |
| 优先级规划总能找到解 | 不完备——高优先级机器人停在咽喉要道可堵死低优先级者,即便整体有解;且对优先级顺序敏感 |
| PIBT 在任何地图上都完备 | 完备性要求"任意相邻顶点对在某简单环上"(如双连通);带死胡同的图上某些机器人可能永远到不了 |
| 子模性就是凸性 | 子模是集合函数的"边际收益递减",与连续凸性是不同概念;子模最大化 NP-难但贪婪有常数比 |
| 任务分配的图和路径规划的图是同一张 | 两张本质不同的图:通信图(节点=机器人)与环境/栅格图(节点=位置);CBBA 用前者、MAPF 用后者 |
| 分配用直线距离最优,系统就最优 | 真实代价是无冲突路径长度;拥挤时与直线差距巨大,"分配最优"可能"执行很堵",需迭代/联合 |
| 次优 MAPF 都没有质量保证 | 有界次优(ECBS/EECBS)保证 SOC \(\le w\cdot\) 最优(来自焦点搜索的下界);只有规则式(PIBT)与随意放松才无保证 |
| anytime 算法就是"跑久点的最优算法" | MAPF-LNS 随时可停且总有合法解,通过破坏-修复在已有解上局部改进逼近最优,不是从头跑到最优 |
| 离散 MAPF 计划可直接发给真机同步执行 | 真机有延迟/速度差/形状,时间戳对齐会失效;须用 ADG(转相对顺序)、MAPF-POST 或 k-robust |
| 用加大时间余量就能让执行鲁棒 | 既浪费又无保证(延迟超余量照撞);ADG 用依赖顺序按需等待,既不浪费又对任意延迟鲁棒 |
| 任务分配与路径规划必须串行分两步 | 当目标匿名时,TAPF/CBM 在一个 CBS 式框架里用最小费用流联合求解分配与路径,无需割裂 |
| 学习式 MAPF 能直接取代经典方法且一样可靠 | 它用"无保证+训练/泛化成本"换去中心化反应式;质量/完备性要求高仍用搜索式,且须测训练分布外泛化 |
| 一个方法可以打天下 | 每个方法的取舍是为特定场景设计的;要按规模×最优性×终身×真机选型,过度/欠工程都会踩坑 |
本章小结¶
本章把多机协调从连续控制层往上推到**离散决策层**,补齐了 Part 1 的最后一块。
任务分配(§3.1-3.2):谁去做哪件任务?一对一一次性分配是线性指派问题,有最优的匈牙利算法(\(O(n^3)\));但工程上更要可扩展与分布式,于是有拍卖(价格作协调信号)、贪婪/顺序贪婪(SGA)。Gerkey–Matarić 三维分类法(ST/MT、SR/MR、IA/TA)告诉你问题属于哪一类、能否最优解。CBBA 把拍卖与第 2 章的共识焊接——本地贪婪构建 bundle,再用带时间戳的最大值共识消解冲突;在边际收益递减(DMG)条件下它等价于集中贪婪 SGA,继承 50% 最优界,收敛轮数正比于通信图直径。第 2 章的共识在这里换层皮再次出场。
路径规划(§3.3-3.5):怎样走不撞?MAPF 形式化了顶点冲突与边冲突、sum-of-costs 与 makespan 两种目标,而最优求解是 NP-难。把算法摆在"耦合↔解耦"谱上看最清楚:联合 A*(完全耦合)最优但 \(5^N\) 爆炸;独立 A*(完全解耦)快但死锁。CBS 居中——低层单体 A*(解耦的效率)+ 高层约束树两子节点穷尽(耦合的最优),拿到最优 + 完备,代价是约束树可能爆。要上千台、要实时、要终身,就回到解耦侧:优先级规划 + 预留表(快但不完备)、PIBT(优先级继承 + 回溯,亚毫秒/上千台)、LaCAM(惰性后继搜索恢复完备)、LaCAM*(anytime 逼近最优)。
边界与统一(§3.6):任务分配的种种贪婪保证(50%、\(1-1/e\))背后是同一个**子模性**;分配与路径耦合成一个完整系统(分配不知路径代价、路径规划分配已定);本章的离散 MAPF 与第 2 章的连续编队是同一"共享空间不相撞"问题在不同抽象层的建模,常混合使用(MAPF 出离散路点、连续控制平滑跟踪)。
质量×规模与真机执行(§3.7-3.8):最优 CBS 与极速 PIBT 之间,有最有用的中间地带——有界次优(ECBS/EECBS,焦点搜索保证 SOC \(\le w\cdot\) 最优)与 anytime(MAPF-LNS,先可行再破坏-修复逼近最优;LNS2 还能从带碰撞解修复出可行解)。把所有 MAPF 方法摆进"质量保证 × 规模"的二维谱,选型就是按需落点。而把算出的离散计划接到真机,还要跨过"同步、单位步、点机器人"三个理想假设:连续时间几何设定用 CCBS(SIPP 安全区间),延迟鲁棒执行用动作依赖图 ADG(把安全性从脆弱的绝对时间转成鲁棒的相对顺序)或 \(k\)-robust(规划时预留容忍),终身取送货用 MAPD/Token Passing、目标匿名时用 TAPF/CBM 联合分配-路径。这一段把 MAPF 从理想算法推到了能驱动真实仓库与蜂群的工程技术,也搭好了通往 Part 2 连续控制的桥。
回到章首的两个"如果跳过会怎样":现在你知道贪婪/拍卖分配比最优差一截是**分布式必须付的税**(50% 界),也知道各自独立规划必然死锁、必须显式处理顶点 + 边冲突(用 CBS 或 PIBT/LaCAM)。更重要的是,你看清了贯穿本章的主线——减耦合换可扩展、保耦合换最优,是和第 1 章"全局协调 vs 局部自主"、第 2 章 ADMM 的 \(\rho\) 旋钮同源的同一根权衡;而子模性则是让"分工"可被高效逼近的统一数学根源;有界次优与 anytime 则把"质量"精确成了"离最优的可证明倍数",ADG 把"安全"精确成了"动作的相对顺序"。
术语速查表¶
| 术语(中) | English | 一句话定义 |
|---|---|---|
| 任务分配 | task allocation | 把任务指派给机器人的离散决策 |
| 线性指派问题 | linear assignment problem (LAP) | 一对一最小代价匹配;全幺模,多项式最优 |
| 匈牙利算法 | Hungarian / Kuhn–Munkres | LAP 的 \(O(n^3)\) 最优解法 |
| 拍卖算法 | auction algorithm | 任务为商品、机器人竞标、价格上涨;\(\varepsilon\)-近似最优 |
| 顺序贪婪 | sequential greedy (SGA) | 每轮挑全局边际最高对;DMG 下 50% 界 |
| Gerkey–Matarić 分类 | MRTA taxonomy | ST/MT、SR/MR、IA/TA 三维刻画任务分配 |
| ST-SR-IA | — | 一对一一次性=LAP,多项式最优 |
| 边际收益递减 | diminishing marginal gain (DMG) | 任务边际价值不随先接别的任务而增;即子模 |
| CBBA | consensus-based bundle algorithm | 分布式拍卖+共识冲突消解;Choi-Brunet-How 2009 |
| bundle / path | bundle / path | CBBA 双结构:加入序(释放用)/执行序(插入用) |
| 中标价/中标者 | winning bids / winning agents | CBBA 共识传播的 \(y\)(最高价)、\(z\)(归谁) |
| MAPF | multi-agent path finding | 为多机同时找无碰撞路径 |
| 顶点冲突 | vertex conflict | 同时刻同顶点 \(\langle i,j,v,t\rangle\) |
| 边/交换冲突 | edge / swap conflict | 同时刻交换位置 \(\langle i,j,u,v,t\rangle\) |
| 代价和 | sum-of-costs (SOC) | 各路径代价之和;优化吞吐 |
| 完工时间 | makespan | 最长路径;优化全部完成时间 |
| 耦合 vs 解耦 | coupled vs decoupled | 联合空间搜索 vs 单体规划;最优↔可扩展 |
| 联合 A* | joint A* | 在联合状态空间搜索;最优但 \(b^k\) 爆炸 |
| CBS | conflict-based search | 高层约束树+低层单体 A*;最优 MAPF |
| 约束树 | constraint tree (CT) | CBS 高层二叉树;节点=约束+路径+代价 |
| 时空 A* | space-time A* | 状态含时刻、避被约束时空点的低层搜索 |
| cardinal conflict | cardinal conflict | 分裂后两子节点代价都上升的冲突;ICBS 优先 |
| ECBS | enhanced CBS | 有界次优 CBS(focal search) |
| 优先级规划 | prioritized planning (PP) | 固定优先级、低让高;快但不完备/次优 |
| 预留表 | reservation table | 记录已规划者的时空占用,作动态障碍 |
| Cooperative A* / WHCA* | cooperative A* | 预留表+时空 A*(滑动窗口版 WHCA*) |
| PIBT | priority inheritance w/ backtracking | 亚毫秒单步配置生成器;优先级继承+回溯 |
| 优先级继承 | priority inheritance | 高优先级机器人推开挡路的低优先级者 |
| LaCAM | lazy constraints addition search | 惰性后继搜索;完备、用 PIBT 作生成器 |
| LaCAM* | LaCAM* | LaCAM 的 anytime 版,最终最优 |
| 终身 MAPF | lifelong MAPF (LMAPF) | 到目标即领新目标,在线滚动重规划 |
| 子模性 | submodularity | 集合函数边际收益递减;贪婪有常数近似比 |
| \(1-1/e\) 界 | \((1-1/e)\) bound | 基数约束下单调子模贪婪的近似比(\(\approx 0.63\)) |
| 分布式子模 | distributed submodular | 多机顺序贪婪;Corah-Michael、Xu-Tzoumas |
| 有界次优 | bounded-suboptimal | 解代价 \(\le w\cdot\) 最优,带保证;\(w\ge 1\) 为次优因子 |
| 焦点搜索 | focal search | OPEN 内框出 \(f\le w f_{\min}\) 的 FOCAL,按副启发展开;保 \(w\)-界 |
| ECBS | enhanced CBS | 高低层都用焦点搜索的有界次优 CBS |
| EECBS | explicit estimation CBS | 高层用显式估计搜索+在线学习的有界次优 CBS;当前主力 |
| anytime MAPF | anytime MAPF | 先快速可行解,再随时间改进逼近最优,随时可停 |
| MAPF-LNS | large neighborhood search | 破坏一小撮+修复,anytime 改进解质量 |
| LNS2 | LNS2 | 从带碰撞解出发,修复减少碰撞至零;专攻大规模可行性 |
| 破坏-修复 | destroy-repair | LNS 的核心循环:删一撮智能体路径再重规划 |
| 连续时间 MAPF | MAPF_R / continuous-time | 时间连续、动作时长不一、智能体有几何形状 |
| CCBS | continuous-time CBS | CBS+SIPP 低层+连续时间冲突;连续时间最优 |
| 安全区间路径规划 | SIPP | 在(顶点,安全区间)状态空间搜,避动态障碍;CCBS 低层 |
| MAPF-POST | MAPF-POST | 用简单时序网络把计划后处理成考虑运动学的执行调度 |
| 动作依赖图 | action dependency graph (ADG) | 把计划编码成动作相对顺序;延迟下仍无碰撞执行 |
| k-robust MAPF | k-robust MAPF | 规划时预留缓冲,容忍至多 \(k\) 步延迟仍无碰撞 |
| MAPD | multi-agent pickup & delivery | 终身取送货;任务=取货点→送货点,持续到达 |
| Token Passing | token passing (TP) | MAPD 的分布式解法;令牌传递、解所有良构实例 |
| TAPF / CBM | target-assignment & path-finding | 目标匿名时联合分配-路径;CBM 用最小费用流做低层 |
| 学习式 MAPF | learning-based MAPF | 用神经网络/RL 学策略或引导搜索;去中心化反应式,无保证 |
| PRIMAL | PRIMAL | RL+模仿学习的去中心化反应式 MAPF 策略(Sartoretti 2019) |
| 学习引导搜索 | learning-guided search | 学"选哪个冲突/邻域/算法"提速,保留经典法的保证 |
知识点总表¶
| 编号 | 知识点 | 核心要点 | 对应节 | 难度 |
|---|---|---|---|---|
| 3.1 | 线性指派问题 | 式(3.1);全幺模→多项式最优,匈牙利 \(O(n^3)\) | §3.1 | ⭐⭐⭐ |
| 3.2 | Gerkey–Matarić 分类 | ST/MT、SR/MR、IA/TA;定位问题复杂度 | §3.1 | ⭐⭐ |
| 3.3 | 拍卖算法 | 价格作协调信号、独立竞标;\(\varepsilon\)-近似,差距 \(\le N\varepsilon\) | §3.1 | ⭐⭐⭐ |
| 3.4 | 顺序贪婪与 DMG | SGA 每轮挑边际最高对;DMG 下 50% 界 | §3.1 | ⭐⭐⭐ |
| 3.5 | CBBA 两阶段 | bundle 构建(本地贪婪)+ 共识冲突消解 | §3.2 | ⭐⭐⭐⭐ |
| 3.6 | CBBA=SGA 与 50% 界 | DMG 下等价集中贪婪;式(3.3) \(M_{OPT}\le 2\)CBBA | §3.2 | ⭐⭐⭐⭐ |
| 3.7 | 按 bundle 顺序释放 | 被抢任务连其后全释放;保出价有效性 | §3.2 | ⭐⭐⭐⭐ |
| 3.8 | CBBA 收敛 | 正比通信图直径 \(D\);最坏 \(O(N_{\min}D)\) 轮 | §3.2 | ⭐⭐⭐ |
| 3.9 | MAPF 形式化 | 图+机器人+起讫+离散步;移动/等待 | §3.3 | ⭐⭐ |
| 3.10 | 顶点冲突与边冲突 | \(\langle i,j,v,t\rangle\) / \(\langle i,j,u,v,t\rangle\);漏边冲突→穿模 | §3.3 | ⭐⭐⭐ |
| 3.11 | SOC vs makespan | 总和 vs 最长;不同最优解,都 NP-难 | §3.3 | ⭐⭐ |
| 3.12 | 耦合↔解耦谱 | 联合 A* 爆 ↔ 独立 A* 死锁;CBS 居中 | §3.3 | ⭐⭐⭐ |
| 3.13 | CBS 两层结构 | 高层约束树 CT + 低层单体时空 A* | §3.4 | ⭐⭐⭐⭐ |
| 3.14 | CBS 冲突分裂 | 两子节点各加一约束,只重规划被约束者 | §3.4 | ⭐⭐⭐⭐ |
| 3.15 | CBS 最优性 | 低层最优+高层最优优先+两子节点穷尽 | §3.4 | ⭐⭐⭐⭐ |
| 3.16 | CBS 变体 | ICBS(cardinal)、CBSH/CG/WDG(启发)、ECBS(次优) | §3.4 | ⭐⭐⭐ |
| 3.17 | 优先级规划+预留表 | 低让高、时空障碍;快但不完备/次优 | §3.5 | ⭐⭐⭐ |
| 3.18 | PIBT | 单步配置生成;优先级继承+回溯;亚毫秒/上千台 | §3.5 | ⭐⭐⭐⭐ |
| 3.19 | PIBT 完备性 | 相邻顶点对在简单环上(双连通)→有限时间到达 | §3.5 | ⭐⭐⭐⭐ |
| 3.20 | LaCAM / LaCAM* | 惰性后继搜索完备;LaCAM* anytime 最终最优 | §3.5 | ⭐⭐⭐⭐ |
| 3.21 | 终身 MAPF | 到目标即领新目标;在线滚动重规划 | §3.5 | ⭐⭐⭐ |
| 3.22 | 子模性与近似界 | 基数→\(1-1/e\)、拟阵→\(1/2\);统一贪婪保证 | §3.6 | ⭐⭐⭐⭐ |
| 3.23 | 分布式子模 | 多机顺序贪婪;Corah-Michael、Xu-Tzoumas 抗失效 | §3.6 | ⭐⭐⭐⭐ |
| 3.24 | 分配↔路径耦合 | 分配不知路径代价;串行/迭代/联合 | §3.6 | ⭐⭐⭐ |
| 3.25 | 离散与连续边界 | MAPF(结构化密集)vs 编队(平滑物理);可混合 | §3.6 | ⭐⭐⭐ |
| 3.26 | 焦点搜索 | 式(3.4)FOCAL=\(\{f\le w f_{\min}\}\);按副启发展开,保 \(w\)-界 | §3.7 | ⭐⭐⭐⭐ |
| 3.27 | 有界次优保证 | SOC \(\le w\cdot\)SOC*;\(f_{\min}\) 是最优下界 | §3.7 | ⭐⭐⭐ |
| 3.28 | ECBS | 高低层都焦点搜索;低层减冲突→缩小 CT | §3.7 | ⭐⭐⭐ |
| 3.29 | EECBS | 高层显式估计搜索+在线学习不可采纳启发;主力 | §3.7 | ⭐⭐⭐⭐ |
| 3.30 | MAPF-LNS | 破坏-修复 anytime;从快速初始解局部改进 | §3.7 | ⭐⭐⭐⭐ |
| 3.31 | LNS2 | 从带碰撞解修复减碰撞至零;大规模可行性 | §3.7 | ⭐⭐⭐ |
| 3.32 | 连续时间 MAPF / CCBS | MAPF_R 连续时间+几何体;CCBS=CBS+SIPP+连续冲突 | §3.8 | ⭐⭐⭐⭐ |
| 3.33 | SIPP | (顶点,安全区间)状态空间;避动态障碍时间最优 | §3.8 | ⭐⭐⭐ |
| 3.34 | MAPF-POST | 简单时序网络后处理成考虑运动学的执行调度 | §3.8 | ⭐⭐⭐ |
| 3.35 | 动作依赖图 ADG | 同机+跨机两类依赖;保相对顺序→延迟下无碰撞 | §3.8 | ⭐⭐⭐⭐ |
| 3.36 | k-robust MAPF | 规划时预留缓冲,容忍至多 \(k\) 步延迟 | §3.8 | ⭐⭐⭐ |
| 3.37 | MAPD / TAPF-CBM | 终身取送货 Token Passing;目标匿名时 CBM 联合分配-路径 | §3.8 | ⭐⭐⭐⭐ |
| 3.38 | 学习式 MAPF | PRIMAL(RL+模仿,去中心化反应式)、GNN 通信、学习引导搜索;无保证 | §3.9 | ⭐⭐⭐ |
| 3.39 | 方法全景与选型 | 搜索/规则/学习三类;按规模×最优性×终身×真机选型 | §3.9 | ⭐⭐⭐ |
累积项目：本章新增模块¶
本章给 Mini-MultiBot 加入**离散决策层**——任务分配与多机路径规划,这是后续所有"先分工、再运动"任务的入口,也是第 13 章仓库调度的核心依赖。
本章新增 planning/ 目录,含两个模块:cbba.py(分布式任务分配,即 §3.2 的 CBBA)和 cbs.py(最优多机路径规划,即 §3.4 的 CBS,内含时空 A* 低层与冲突检测)。仓库进展:
mini-multibot/
├── communication/
│ ├── ros2_multi_ns.launch.py
│ ├── world_anchor.py
│ └── consensus.py # Ch2:Laplacian/Metropolis/共识迭代——被 cbba 复用
├── controllers/
│ └── distributed_mpc/
│ └── admm_coordinator.py # Ch2
├── planning/ # 本章新增
│ ├── cbba.py # 本章:CBBA 分布式任务分配(bundle+共识冲突消解)
│ ├── cbs.py # 本章:CBS 最优 MAPF(约束树+时空 A*+冲突检测)
│ ├── lns.py # 本章:MAPF-LNS 破坏-修复 anytime(§3.7)
│ └── pipeline.py # 本章:分配→路径 的串行流水线(供 Ch13 接终身循环)
├── execution/ # 本章新增
│ └── adg.py # 本章:动作依赖图,延迟下鲁棒执行(§3.8)
├── envs/ # Ch4/Ch8 起
└── evaluation/ # Ch13
设计要点:cbba.py 把"通信图 + 得分函数"作为输入,输出无冲突的任务分配——得分函数定义成可注入的接口(第 6 章异构机型会把"机型能力"编码进得分),并复用 communication/consensus.py 的图工具算通信图直径来预估收敛轮数。cbs.py 把"环境栅格 + 起讫点"作为输入,输出无冲突最优路径,低层时空 A* 与冲突检测都做成独立函数(供 §3.5 的优先级规划/PIBT、§3.7 的 LNS 复用)。lns.py 实现 §3.7 的破坏-修复 anytime 改进(初始解可来自优先级规划),供大规模实例在 CBS 跑不动时使用;execution/adg.py 实现 §3.8 的动作依赖图,把无冲突计划转成对延迟鲁棒的执行(谁慢等谁),是离散计划落到真机的最后一层。pipeline.py 把它们串起来——先 CBBA 分配、再选求解器(CBS / LNS)规划、最后 ADG 执行,并预留"路径不可行→反馈重分配"的钩子,第 13 章把它扩成永不停止的终身调度环。
# planning/pipeline.py —— 分配 → 路径 的最小串行流水线(本章版;Ch13 扩为终身循环)
import numpy as np
from .cbba import cbba # §3.2 验证过的 CBBA
from .cbs import cbs, find_first_conflict # §3.4 验证过的 CBS 及冲突检测
def plan_assign_then_route(env_grid, robot_starts, task_cells,
comm_graph, capacity, reward_fn):
"""先用 CBBA 把 task_cells 分给机器人,再用 CBS 规划到各自首个任务的无冲突路径。
env_grid: 环境栅格(0 可走/1 障碍)——路径规划用的"环境图"
comm_graph: 机器人间通信图——任务分配用的"通信图"(两张图严格区分!)
reward_fn: reward_fn(i, j) -> 机器人 i 做任务 j 的得分(须满足 DMG)
返回:分配字典、到首个任务的无冲突路径、CBBA 收敛轮数、CBS 展开节点数。"""
N, M = len(robot_starts), len(task_cells)
reward = np.array([[reward_fn(i, j) for j in range(M)] for i in range(N)])
# ① 分配:CBBA 在通信图上跑(共识裁决冲突)
assign, _, rounds = cbba(reward, comm_graph, capacity)
# ② 排序:每台机器人按得分降序定任务访问顺序(简化;可换 TSP/插入式)
for i in assign:
assign[i].sort(key=lambda j: reward[i, j], reverse=True)
# ③ 路径:为有任务的机器人,用 CBS 规划到"首个任务格"的无冲突路径
routed = [i for i in assign if assign[i]]
starts = [robot_starts[i] for i in routed]
goals = [task_cells[assign[i][0]] for i in routed]
paths, _, expanded = cbs(env_grid, starts, goals) if routed else ([], 0, 0)
# ④ 反馈钩子:CBS 无解 -> 交给上层重分配(Ch13 在此闭环)
feasible = paths is not None and (not paths or find_first_conflict(paths) is None)
return {"assign": assign, "paths": paths, "rounds": rounds,
"expanded": expanded, "feasible": feasible}
到本章末,Mini-MultiBot 已具备"多机通信底座(Ch1)+ 共识/ADMM 协调内核(Ch2)+ 任务分配/路径规划(Ch3)"——离散决策层就绪。Part 2 起,我们把这些离散决策接到连续控制:第 4 章的分布式 MPC 编队会跟踪本章 MAPF 给出的离散路点。
延伸阅读¶
教材(打地基): - LaValle, Planning Algorithms, Cambridge, 2006(免费在线,⭐⭐⭐):运动规划与搜索的权威教材,A*、组合规划、多机的基础都在这里;§3.3-3.4 的搜索框架可在此补全。 - Bullo, Cortés, Martínez, Distributed Control of Robotic Networks, 2009(⭐⭐⭐):分布式机器人网络(含分布式任务/覆盖)的系统教材,与第 2 章共用一套数学语言。
综述/经典论文(看脉络): - Gerkey & Matarić, A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems, IJRR 23(9):939-954, 2004(⭐⭐⭐⭐):§3.1 三维分类法的源头,MRTA 领域的奠基综述,做任务分配必读。 - Choi, Brunet, How, Consensus-Based Decentralized Auctions for Robust Task Allocation, IEEE T-RO 25(4):912-926, 2009(⭐⭐⭐⭐):§3.2 CBBA 原文,含 DMG、50% 界、收敛证明,分布式 MRTA 基准。 - Sharon, Stern, Felner, Sturtevant, Conflict-Based Search for Optimal Multi-Agent Pathfinding, Artificial Intelligence 219:40-66, 2015(⭐⭐⭐⭐):§3.4 CBS 原文,最优 MAPF 的标准算法。 - Stern et al., Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks, SoCS 2019(⭐⭐⭐):§3.3 顶点/边冲突、目标函数、基准的统一标准,MAPF 研究的公共语言。 - Yu & LaValle, Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs, AAAI 2013(⭐⭐⭐):MAPF 最优求解 NP-难的证明出处。 - Nemhauser, Wolsey, Fisher, An Analysis of Approximations for Maximizing Submodular Set Functions, Math. Programming 14:265-294, 1978(⭐⭐⭐):§3.6 子模贪婪 \(1-1/e\) 界的源头。
前沿(看标杆): - Okumura, LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding, AAAI 2023(⭐⭐⭐⭐):§3.5 惰性后继搜索,完备且可扩展到上千智能体。 - Okumura, Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding(LaCAM*), IJCAI 2023(⭐⭐⭐⭐):anytime 版,最终收敛最优;33 栅格/13900 实例/至 1000 智能体基准。 - Okumura, Machida, Défago, Tamura, Priority Inheritance with Backtracking for Iterative MAPF, Artificial Intelligence 310, 2022(原 IJCAI 2019,⭐⭐⭐⭐):§3.5 PIBT,亚毫秒单步,2023 MAPF 竞赛冠军核心。 - Xu, Garimella, Tzoumas, Distributed and Resilient Submodular Task Allocation, IEEE T-RO 41:3480-3499, 2025(⭐⭐⭐⭐):§3.6 分布式 + 抗失效的子模任务分配前沿。 - Corah & Michael, Distributed Submodular Maximization on Partition Matroids for Planning on Large Sensor Networks, Autonomous Robots, 2019(⭐⭐⭐):多机顺序贪婪做分布式子模的代表。 - Li, Ruml, Koenig, EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding, AAAI 2021:12353-12362(⭐⭐⭐⭐):§3.7 有界次优 CBS 的代表,显式估计搜索 + 在线学习。 - Li, Chen, Harabor, Stuckey, Koenig, Anytime Multi-Agent Path Finding via Large Neighborhood Search(MAPF-LNS), IJCAI 2021;以及 MAPF-LNS2: Fast Repairing ..., AAAI 2022:10256-10265(⭐⭐⭐⭐):§3.7 anytime 破坏-修复与从带碰撞解修复。 - Andreychuk, Yakovlev, Surynek, Atzmon, Stern, Multi-Agent Pathfinding with Continuous Time, IJCAI 2019 / Artificial Intelligence 305, 2022(⭐⭐⭐⭐):§3.8 连续时间 MAPF(CCBS)与 SIPP 低层。 - Hönig, Kiesel, Tinka, Durham, Ayanian, Persistent and Robust Execution of MAPF Schedules in Warehouses, IEEE RA-L 4(2):1125-1131, 2019;以及 Hönig 等, MAPF with Kinematic Constraints(MAPF-POST), ICAPS 2016(⭐⭐⭐⭐):§3.8 动作依赖图与鲁棒执行。 - Ma, Li, Kumar, Koenig, Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks(MAPD/Token Passing), AAMAS 2017;Ma & Koenig, Optimal Target Assignment and Path Finding(TAPF/CBM), AAMAS 2016(⭐⭐⭐):§3.8 终身取送货与联合分配-路径。 - Sartoretti, Kerr, Shi, Wagner, Kumar, Koenig, Choset, PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning, IEEE RA-L 4:2378-2385, 2019;Li, Lin, Liu, Prorok, Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planning(MAGAT), IEEE RA-L 6, 2021(⭐⭐⭐):§3.9 学习式 MAPF 与 GNN 通信,通往第 10-11 章。
工程(动手查):
- scipy.optimize.linear_sum_assignment:匈牙利算法实现,§3.1 任务分配基线。
- pypibt(github.com/Kei18/pypibt):Okumura 本人的 PIBT 最小 Python 实现,§3.5 想读代码看这个。
- EECBS(github.com/Jiaoyang-Li/EECBS)与 MAPF-LNS2(github.com/Jiaoyang-Li/MAPF-LNS2):§3.7 有界次优与 anytime 的官方 C++ 实现,内含 SIPPS、对称性消解等工业级优化。
- MAPF benchmark(movingai.com / Stern et al. 2019):标准栅格地图与实例集,LaCAM/EECBS/LNS 等都在上面评测。
- networkx:构造与分析通信图(直径、连通性),CBBA 收敛分析用。
本章与后续章节的关系¶
| 后续章节 | 关系 | 本章铺垫的知识点 |
|---|---|---|
| 第 4 章 分布式 MPC 编队 | MAPF 出离散路点,MPC 平滑跟踪;§3.8 的连续时间/运动学视角直接过渡到连续控制层 | MAPF 路点、CCBS 连续时间、耦合↔解耦权衡 |
| 第 5 章 协同搬运与力控 | MR(多机协作)任务=超可加/违反子模,正是本章子模框架的边界,引向联盟形成 | Gerkey MR 类、子模性边界 |
| 第 6 章 异构多机协同 | 任务分配要匹配异构机型能力——把"能力"编码进 CBBA 的得分函数 | CBBA、Gerkey 分类、得分函数接口 |
| 第 10–11 章 MARL | 学习式的任务分配/路径协调,用策略替代显式搜索(可与 CBS/EECBS/PIBT 对比) | MAPF、分配作为可学习决策 |
| 第 12 章 MARL+规控混合 | 学习的高层调度 + 有安全保证的路径层 | MAPF、优先级/PIBT、终身循环 |
| 第 13 章 综合实战 | 仓库调度复用 planning/(CBBA+CBS+LNS)与 execution/(ADG),扩成终身分配↔路径↔执行环 |
全章,尤其 pipeline、MAPD、ADG 执行 |
🔧 故障排查手册¶
| 症状 | 可能原因 | 排查步骤 | 相关节 |
|---|---|---|---|
| CBBA 不收敛 / 反复抖动 | 得分非 DMG;或释放任务没按 bundle 顺序 | 1. 验证得分边际非增(DMG) 2. 检查是否连同 bundle 其后任务一起释放 3. 加 warping | §3.2 |
| CBBA 收敛了但仍有冲突 | 共识更新/时间戳规则错;或通信图不连通 | 1. 算通信图 \(\lambda_2\) 查连通 2. 检查中标价更新与释放逻辑 | §3.2 |
| 分配总代价远高于预期 | 用了贪婪/拍卖却期望最优;或代价矩阵行列方向反 | 1. 与匈牙利对比 2. 检查"行=机器人、列=任务" | §3.1 |
| MAPF 路径执行时相撞 | 漏检边/交换冲突;或到目标后占用没处理 | 1. 检查冲突检测的 t+1 分支 2. 加目标到达后的永久占用 |
§3.3, §3.5 |
| CBS 不返回 / 极慢 | 冲突太多约束树爆;或低层没遵守全部约束(旧冲突复活) | 1. 确认低层用 CT 节点的完整约束集 2. 上 ICBS/CBSH 剪枝或改 ECBS 次优 | §3.4 |
| CBS 返回的解不是最优 | 高层没按 cost 最优优先;或只展开了一个子节点 | 1. 确认高层队列按 SOC 出队 2. 确认每个冲突分裂两个子节点都入队 | §3.4 |
| 优先级规划无解 | 高优先级机器人停在咽喉要道堵死(不完备);或顺序差 | 1. 换优先级顺序/随机重启 2. 改用 PIBT(优先级继承)或 LaCAM(完备) | §3.5 |
| PIBT 某些机器人到不了目标 | 图非双连通(有死胡同),不满足完备性条件 | 1. 检查"相邻顶点对是否都在简单环上" 2. 加边使图双连通 | §3.5 |
| 终身 MAPF 活锁(谁也不走) | 滑动窗口太短;或优先级反复横跳 | 1. 加长窗口越过瓶颈 2. 保证优先级单调(久等者升优先级) 3. 对久停机器人提权/全局重规划 | §3.5 |
| 分配纸面最优、执行却很堵 | 分配用直线距离忽略拥堵 | 1. 改用考虑拥堵的真实路径代价 2. 路径反馈给分配迭代一次 | §3.6 |
| 行为整体错乱(信息乱传/找路无意义) | 把通信图当环境图(或反之) | 1. 代码里分开命名 comm_graph/env_grid 2. 核对节点语义(机器人 vs 位置) |
§3.2, §3.6 |
| MAPF-LNS 不改进 / 改进极慢 | 邻域纯随机、总重规划已最优的智能体;或修复未把他人当完整障碍 | 1. 改有信息邻域(选绕路/冲突最多者) 2. 修复时登记顶点+边+目标占用并复核无冲突 | §3.7 |
| 有界次优解质量没保证 | 把无界放松当有界;或焦点搜索的 FOCAL 阈值/下界算错 | 1. 确认按 \(f\le w f_{\min}\) 框 FOCAL 2. 确认 \(f_{\min}\) 取自 OPEN 的真实最小 | §3.7 |
| 离散计划在真机上偶发相撞 | 裸用时间戳同步执行,真机有延迟/速度差 | 1. 改用 ADG(相对顺序执行) 2. 或 MAPF-POST 后处理 3. 或规划时上 k-robust | §3.8 |
| 加了时间余量真机仍相撞 | 余量是定值、延迟超出即失效 | 1. 换 ADG 按依赖按需等待 2. 需可证明容忍则规划层用 k-robust | §3.8 |
| ADG 执行仍碰撞 | 只建了同机顺序、漏跨机格子顺序(或漏边依赖) | 1. 对每格按计划访问序加"后到等先到离开"依赖 2. 补边依赖与目标停留 | §3.8 |
| 学习式 MAPF 在某些地图骤然失效 | 测试地图密度/团队规模在训练分布外(分布偏移) | 1. 在目标分布上重训/微调 2. 质量敏感场景回退搜索式 3. 用学习引导经典法而非纯学习 | §3.9 |
| 选了方法却跑不动/解很差 | 过度工程(大规模上最优 CBS)或欠工程(要保证却用 PP) | 1. 走 §3.9 决策框架/recommend_mapf_solver 重新选型 2. 在自己实例上测真实规模边界 |
§3.9 |
API 速查表¶
| API / 工具 | 用途 |
|---|---|
scipy.optimize.linear_sum_assignment(C) |
匈牙利算法,最优指派,\(O(n^3)\)(行=机器人、列=任务) |
networkx.diameter(G) |
通信图直径,预估 CBBA 收敛轮数 |
时空 A* astar_st(grid,s,g,vc,ec) |
低层带约束最短路;CBS 与优先级规划共用 |
find_first_conflict(paths) |
同时检测顶点 + 边冲突;MAPF 核心工具 |
| CBBA 双结构 bundle / path | bundle 按加入序(释放用)、path 按执行序(插入用) |
拍卖出价 bid=p_j+(best−second)+ε |
\(\varepsilon\)-近似最优,总差距 \(\le N\varepsilon\) |
CBS 顶点冲突分裂 → (i,v,t)/(j,v,t) |
两子节点各禁一方在 \((v,t)\),都展开 |
CBS 边冲突分裂 → (i,u,v,t)/(j,v,u,t) |
两子节点各禁一方走对应方向边 |
预留表三件套:(v,t)、(v,u,t)、目标永久占用 |
优先级规划防顶点/边冲突 + 目标停留 |
pypibt(github.com/Kei18/pypibt) |
PIBT 最小 Python 实现,可扩展单步规划 |
| 子模贪婪近似比:基数 \(1-1/e\)、拟阵 \(1/2\) | 任务分配贪婪保证的统一来源 |
| 焦点搜索 FOCAL = \(\{f\le w f_{\min}\}\) | 有界次优:在 FOCAL 内按副启发(冲突数)展开,保 SOC \(\le w\cdot\) 最优 |
| ECBS / EECBS | 有界次优 CBS:高低层焦点搜索 / 高层显式估计搜索+在线学习 |
MAPF-LNS replan_subset 破坏-修复 |
anytime:删一撮智能体重规划(他人当固定障碍),更优才接受 |
SIPP 状态 (顶点, 安全区间) |
连续时间/动态障碍下的低层搜索;CCBS 用它 |
| ADG 两类依赖:同机顺序 + 跨机格子顺序 | 把计划转成相对顺序;执行时谁慢等谁,延迟下无碰撞 |
| k-robust 检查:任意延迟 \(\le k\) 步仍无冲突 | 规划层预留缓冲的鲁棒性验证 |
recommend_mapf_solver(...) |
§3.9 选型决策函数:按规模/最优性/终身/真机推荐求解器+执行层 |
| 方法全景总表(§3.9) | 一张表查每个方法的最优性/完备性/规模/适用——选型的索引 |
研究实践建议¶
给初学者:务必**亲手把匈牙利 → CBBA → CBS → 优先级规划这四个跑通**——本章代码都给了可验证的现象(贪婪比最优贵多少、CBBA 收敛轮数随直径、CBS 与联合 A* 同最优、PP 换顺序从无解到有解)。重点踩三个坑:看贪婪/拍卖与匈牙利的差距、把 CBBA 的得分改成违反 DMG 看保证失效、在瓶颈地图上换优先级顺序看 PP 从无解变有解。再往后,跑通 §3.7 的 MAPF-LNS 看它 anytime 地把 PP 初始解压到最优、跑通 §3.8 的 ADG 看它在延迟下不撞而朴素时间戳执行会撞——这两个现象会让你真正理解"质量保证"与"鲁棒执行"是什么。先把**一次性 MAPF**(CBS)彻底吃透,再碰终身 MAPF。从一开始就把"两张图"(通信图 vs 环境图)在脑子里和代码里分清——这是本章最容易串味的地方。
给有经验者:路径方法选型按"规模 × 最优性需求 × 是否终身"三维定位,落在 §3.7 那张"质量×规模"二维谱上——中小规模要最优用 CBS,加 ICBS(优先 cardinal conflict)/CBSH(可采纳启发)提速;要规模 + 质量保证用 ECBS/EECBS(明确写出次优因子 \(w\));要"先可行再逼近最优"用 MAPF-LNS / LaCAM*(anytime);超大规模或连可行解都难找用 LNS2(从带碰撞解修复)或 PIBT 当亚毫秒底座。任务分配上,集中小规模用匈牙利,分布式用 CBBA 但务必确认得分 DMG(否则上 warping)。别把分配与路径割裂——拥挤场景里分配阶段就要用接近真实的路径代价,或用迭代/联合方法(目标匿名时直接上 TAPF/CBM 联合求解)。真机部署务必把"算计划"与"跑计划"解耦:用 ADG 或 MAPF-POST 把离散计划转成对延迟鲁棒的执行,或在规划层用 k-robust;需要连续时间/几何精度时上 CCBS。关注前沿:MAPF 的 LaCAM 系、EECBS、终身竞赛(League of Robot Runners),以及分布式子模的抗失效结果(Xu-Tzoumas)。最后记住:需要**多机强协同**的任务(合抬重物,效用超可加、违反子模)是另一类问题,本章的贪婪保证在那里失效——它把我们引向第 5 章的协同搬运与第 6 章的异构编组。
任务分好了、路也规划好了——但本章给的路径是**离散**的(每步走一格)、是**运动学**层面的(没考虑机器人的动力学、惯性、力)。真实机器人不能瞬间转向、急停,编队飞行要平滑、协同搬运要控力。把本章离散决策层的输出,接到能处理动力学与物理交互的**连续控制层**,正是 Part 2 的任务。
第 3 章完结。 Part 1(多机协作基础)到此收官——你已掌握看待多机系统的地图(Ch1)、分布式协调的数学引擎(Ch2)、以及任务分配与路径规划的离散决策层(Ch3)。下一章进入 Part 2(协同运动控制):我们把第 2 章的 ADMM 协调器接上真实的单体 MPC,让一支机器人编队在**连续空间**里分布式地保持队形、平滑机动——并且,它跟踪的参考路点,正可以来自本章的 MAPF。离散与连续,在第 4 章交汇。
版本信息速查¶
本章涉及的工具与算法参考(截至 2026 年中):
| 项目 | 版本 / 出处 | 说明 |
|---|---|---|
| MRTA 分类法 | Gerkey & Matarić 2004, IJRR 23(9) | §3.1 任务分配三维分类 |
| CBBA | Choi, Brunet, How 2009, IEEE T-RO 25(4) | §3.2 分布式拍卖 + 共识、50% 界 |
| CBS | Sharon et al. 2015, Artificial Intelligence 219 | §3.4 最优 MAPF |
| MAPF 定义/基准 | Stern et al. 2019, SoCS | §3.3 顶点/边冲突、目标、benchmark |
| MAPF NP-难 | Yu & LaValle 2013, AAAI | §3.3 最优求解难度出处 |
| PIBT | Okumura et al. 2022, AIJ 310(原 IJCAI 2019) | §3.5 亚毫秒单步、竞赛冠军核心 |
| LaCAM / LaCAM* | Okumura 2023, AAAI / IJCAI | §3.5 惰性搜索完备 / anytime 最优 |
| 子模 \(1-1/e\) 界 | Nemhauser, Wolsey, Fisher 1978 | §3.6 贪婪近似比源头 |
| 分布式子模 | Xu et al. 2025, IEEE T-RO 41;Corah & Michael 2019, AuRo | §3.6 分布式/抗失效任务分配 |
| ECBS / EECBS | Barer et al. 2014, SoCS / Li, Ruml, Koenig 2021, AAAI 12353 | §3.7 有界次优 MAPF |
| MAPF-LNS / LNS2 | Li et al. 2021, IJCAI / Li et al. 2022, AAAI 10256 | §3.7 anytime 破坏-修复 / 修复可行性 |
| CCBS / SIPP | Andreychuk et al. 2019, IJCAI(AIJ 305, 2022)/ Phillips & Likhachev 2011 | §3.8 连续时间 MAPF / 安全区间 |
| MAPF-POST / ADG | Hönig et al. 2016, ICAPS / Hönig et al. 2019, RA-L 4(2) | §3.8 鲁棒执行 |
| k-robust MAPF | Atzmon et al. 2018, SoCS | §3.8 延迟容忍规划 |
| MAPD / TAPF-CBM | Ma et al. 2017, AAMAS / Ma & Koenig 2016, AAMAS | §3.8 终身取送货 / 联合分配-路径 |
| 学习式 MAPF | Sartoretti et al. 2019, RA-L 4(PRIMAL);Li et al. 2021, RA-L 6(MAGAT) | §3.9 学习式路线 |
| NumPy / SciPy | ≥ 1.24 / ≥ 1.10 | linear_sum_assignment、本章仿真 |
| networkx | ≥ 3.0 | 通信图构造与直径/连通性 |
说明:论文的作者、年份、期刊以正文引用与延伸阅读为准;工具版本随上游更新,复现时以官方发行说明为准。