TAMP_T8 多机器人 TAMP (Multi-Robot Task and Motion Planning)¶

难度: ⭐⭐⭐ ~ ⭐⭐⭐⭐ (本章是任务层的多机纵深，整体偏进阶到研究级) 前置知识: TAMP_T1（PDDL/FF、符号-几何鸿沟、TAMP 核心耦合）、TAMP_T2（MRTA 分类学、匈牙利/MILP、拍卖/CBBA、分配-规划耦合 §9）、TAMP_T3/T4（PDDLStream / LGP，单机集成范式）、多机器人协作线 Multi_03（MAPF/CBS）。无需多机控制（编队、分布式 MPC）——那是运动层，本章只讲任务层。 核心参考: Gerkey & Matarić (2004, IJRR 23(9)), MRTA 分类学; Korsah, Stentz & Dias (2013, IJRR 32(12)), iTax 依赖维度; Choi, Brunet & How (2009, IEEE T-RO 25(4)), CBBA; Schillinger, Bürger & Dimarogonas (2018, IJRR 37(7)), 时序逻辑下的同时分配与规划 (STAP); "Conflict-Based Task and Motion Planning for Multi-Robot, Multi-Goal Problems" (2024, ICRA); Sung, Shome & Stone (2024, ICRA), 异步任务计划精化的多机 TAMP; Motes, Chen, Bretl, Morales & Amato (2023, IEEE T-RO), "Hypergraph-based Multi-Robot Task and Motion Planning" 与既有章节的关系: 本章把 TAMP_T2 §9（分配-规划耦合，仅 ⭐⭐⭐⭐ 一节的纲要）彻底打开，做成完整的多机联合规划方法论；它把 TAMP_T1-T4 的单机 TAMP 沿"执行者数量"这一轴推广到多机，并在任务层与多机器人协作线（Multi_03 的 MAPF/CBS、Multi 线的分布式控制）划清边界——本章管"谁做什么、什么顺序、几何上可行吗"，运控层管"多机怎么无碰撞地动"。

0. 前置自测¶

本章站在三块地基之上——单机 TAMP（T1-T4：符号-几何鸿沟与集成范式）、多机分配（T2 §6-§9：MRTA 分类学、匈牙利/MILP/拍卖、分配-规划耦合的纲要）、以及多机路径（Multi_03：MAPF/CBS）。本章的全部工作，是把这三块在"多执行者"这个新维度上焊接成一个整体。开始之前，请先做下面五道题。如果三道以上答不出来，先回对应前置章节——否则本章的"耦合""联合""分布式"会失去落脚点。

#	问题	期望掌握程度	答不出来回到
Q1	单机 TAMP 的核心难题"符号-几何鸿沟"是什么？为什么"先把任务序列排好、再逐条做运动规划"会陷入指数级回溯？	能说出离散命题 vs 连续几何，以及两层解耦、信息单向导致盲目重试	TAMP_T1 §2.4-§2.5
Q2	Gerkey-Matarić 的 MRTA 三维分类学（ST/MT、SR/MR、IA/TA）各维度是什么？为什么"瞬时、单任务机器人、单机器人任务"那一格能用匈牙利算法多项式求解？	能复述三维含义，并说出 ST-SR-IA = 线性指派	TAMP_T2 §6
Q3	TAMP_T2 §9 已经指出"分配-规划耦合"与"任务-运动耦合"是同构的。请用一句话说出这个同构的共同结构。	能说出"上层决策依赖下层结果、下层结果又由上层决策决定"的鸡生蛋循环	TAMP_T2 §9.2
Q4	CBBA（基于共识的捆绑算法）的两个阶段（捆绑构建 + 共识冲突消解）各做什么？它收敛到无冲突分配需要得分函数满足什么性质？	能说出贪心建包 + 邻居间共识擦除被抢任务；得分需满足递减边际收益 (DMG)	TAMP_T2 §8.5，Multi_03 §3.2
Q5	MAPF（多智能体路径查找）与 CBS（冲突基搜索）解决的是什么问题？它在多机系统的"分配→规划→执行"流水线里位于哪一环、它的输入是什么？	能说出 MAPF = 给定各机器人起终点求无碰撞路径，位于"分配已定且任务独立"之后；CBS 用约束树消解路径冲突	Multi_03 §3.3-§3.4

参考答案（点击展开）

**Q1**：符号-几何鸿沟指任务层用**离散命题**描述世界（如 `On(cup, table)`、`HandEmpty`），运动层用**连续向量**描述世界（关节角 $\mathbf{q}\in\mathbb{R}^d$、物体位姿 $\in SE(3)$）。纯符号规划器看不到几何，它知道"架子是空的"却不知道"架子高 $1.2\,\mathrm{m}$、臂展 $0.8\,\mathrm{m}$"。于是"先排任务、再做运动"会反复在运动层撞上几何不可行，而符号层不知道为什么失败、只能盲目换序，最坏要试 $O(k^n)$ 种组合。把两层解耦、信息单向流动，是 TAMP 第一个要破除的迷思。 **Q2**：三维是——**ST/MT**（单任务机器人 / 多任务机器人：一台机器人一次能否同时执行多个任务）、**SR/MR**（单机器人任务 / 多机器人任务：一个任务需要一台还是多台机器人合作）、**IA/TA**（瞬时分配 / 时间扩展分配：只分当前一轮，还是要排未来的任务序列）。**ST-SR-IA**：每台机器人一次一个任务、每个任务一台机器人、只看当下——这正是线性指派问题 (Linear Assignment Problem)，代价矩阵 $C_{ij}$ 已知，匈牙利算法 $O(n^3)$ 求全局最优。 **Q3**：共同结构是"**上层决策依赖下层结果、下层结果又由上层决策决定**"的鸡生蛋循环。TAMP 里是"任务序列的可行性依赖运动规划、运动规划的起止又由任务序列定"；分配-规划里是"分配的代价依赖规划出的真实路线、路线又由分到的任务清单定"。认出这个同构，就明白"不能解耦"不是某个算法的毛病，而是分层决策的内在张力。 **Q4**：CBBA 第一阶段**捆绑构建 (bundle construction)**：每台机器人本地贪心，按"边际得分增量"把任务一个个塞进自己的捆绑（bundle）与路径（path），直到没有正收益的任务可加。第二阶段**共识冲突消解 (consensus)**：机器人与邻居交换"每个任务当前的最高出价者与出价值"，按确定性规则更新——如果发现某任务有人出价更高，就把它（及其之后建包的任务）从自己的捆绑里释放。两阶段交替直到全网对"谁赢哪个任务"达成一致。收敛（且有性能保证）要求得分函数满足**递减边际收益 (Diminishing Marginal Gain, DMG)**——多拿一个任务带来的边际增益不随捆绑变大而增大。 **Q5**：MAPF 指**给定每台机器人的起点和终点，求一组互不碰撞（不撞墙、不撞彼此）的路径**，通常在离散栅格 + 离散时间上定义，目标是最小化总到达时间或最大完成时间 (makespan)。它位于流水线中"**分配已经定了、且任务彼此独立**"之后——必须先有"谁去哪"，MAPF 才有起终点可走。CBS（冲突基搜索）用一棵**约束树**求解：底层为每台机器人单独规划最短路（忽略他人），高层检测路径间的冲突（同一时刻同一格），对冲突的某一方加约束（"机器人 $i$ 在时刻 $t$ 不许进格 $v$"）并分裂搜索，直到无冲突。本章把 MAPF/CBS 当作运动层/路径层的现成工具来对接，不重新推导——细节见 Multi_03。

1. 本章目标¶

学完本章后，你应当能够：

说清单机 TAMP（T1-T4）推广到多机时新增了哪些耦合——任务-运动耦合之上叠加的分配-规划耦合、机器人间的时空耦合、以及协作动作带来的同步耦合，并解释为什么"每台机器人各自跑一遍单机 TAMP"是错的。
定位多机 TAMP 在 MRTA 分类学（Gerkey-Matarić + Korsah iTax）地图上的坐标：它通常落在带跨机器人依赖 (XD) 甚至复杂依赖 (CD) 的格子里，并据此判断一个具体问题该用哪类方法。
解剖分配-规划耦合的内部机制：给出"顺路 (ID 依赖) 让边际代价非常数""避让 (XD 依赖) 让一台机器人的路线取决于他人"两类具体场景，并说明它们如何把分配问题从多项式可解推向 NP-hard、如何引发跨层回溯。
建立分配-排序-路由的联合优化模型：把多机任务分配写成带容量的车辆路径问题 (CVRP) / 任务分配-多旅行商 (TA-mTSP) 的 MILP，理解变量数随任务数的增长、子环消除约束、以及为什么这限制了精确解只能用于中小规模；了解列生成 (column generation) 等分解思路。
深化市场/拍卖机制：从序贯单物品拍卖 (SSI) 走到 CBBA 的分布式捆绑+共识，理解 DMG 性质为何是收敛的前提、如何把真实路径规划器嵌入出价以处理 ID 耦合、以及拍卖相对集中式 MILP 在通信/规模/鲁棒性上的取舍。
描述分布式多机 TAMP 的架构谱系（集中式 / 分布式 / 去中心化）与代表性技术：异步任务计划精化（避免预离散化与同步假设）、超图分解、几何耦合的多机 TAMP，并说清它们各自牺牲了什么、换来了什么。
协调多机时序：把单机的简单时序网络 (STN) 扩展为多机时序约束，识别"汇合 (rendezvous)""交接 (handoff)""资源互斥"三类时空冲突，并把任务层的离散时序与运动层的 MAPF/连续时空对接。
应用时序逻辑下的同时分配与规划 (STAP)：理解为什么把 LTL 任务规约先分配再规划会丢解、Schillinger 等人如何在自动机表示上"同时"分配与规划，并把这一思想接到本章的累积项目上。

本章知识导航¶

本章只回答一个问题，但回答得很深：当执行者从一台变成多台，任务层会发生什么、又该怎么办？ 答案的主线是"耦合的升级"——单机 TAMP 已有的"任务-运动耦合"（T1-T4 的主题）之上，多机又叠了两层新耦合：机器人之间抢任务（分配-规划耦合）、机器人之间抢空间和时间（时空耦合）。整章的结构就是顺着"识别耦合 → 建模耦合 → 求解耦合（集中式 / 分布式）→ 协调时空 → 用逻辑规约统一"展开：

              根问题：执行者从 1 台 → N 台，任务层怎么变？
                                  │
          ┌───────────────────────┼───────────────────────┐
          │                       │                       │
     【识别耦合】              【建模与求解】             【协调与统一】
          │                       │                       │
     §2 三重耦合              §4 耦合解剖(顺路/避让)      §8 时序协调
        单机→多机 新增什么      §5 联合优化(CVRP/MILP)     STN→多机→MAPF接口
     §3 MRTA 分类再深化        §6 市场/拍卖(SSI→CBBA)     §9 时序逻辑 STAP
        定位 XD/CD 格子        §7 分布式 TAMP(异步精化)     LTL 规约下同时分配规划
          │                       │                       │
          └────── 解决:看清问题 ──┴── 解决:算出方案 ───────┴── 解决:落地与形式化
                                  │
                       §10 与单机/Multi线边界  →  §11 工程实践  →  §12 累积项目

怎么读这张图：§2-§3 先把"多机比单机多了什么"看清楚（识别耦合，⭐⭐~⭐⭐⭐）；§4-§7 是本章主体，把耦合建模并给出两条求解路线——集中式联合优化（§5）与分布式拍卖/精化（§6-§7）（⭐⭐⭐⭐）；§8-§9 处理时间维度与逻辑规约（⭐⭐⭐⭐）；§10-§12 收尾：划边界、讲工程、做项目。

两条阅读路线： - 工程导向（想搭一个能跑的多机系统）：§2 → §3 → §6（拍卖）→ §8（时序）→ §11（工程）→ §12（项目），把 §4-§5 的联合优化当原理背景略读。 - 研究导向（想做方法创新）：§2 → §4（耦合本质）→ §5（联合优化）→ §7（分布式前沿）→ §9（时序逻辑）→ 延伸阅读，把 §11 工程部分速读。

一条暗线把八节串成螺旋：本章不是八个孤立方法的罗列，它们沿一条"耦合越来越深、必须联合的理由越来越硬"的螺旋上升。§4 揭示 ID/XD 耦合让解耦丢最优性；§5-§7 给出处理它的三档手段（集中联合 / 分布拍卖 / 前沿分解），核心都是"修信息通道、只为真耦合付代价"；§8 把耦合推进到时间维（时序冲突）；§9 推到顶端——LTL 规约下解耦丢的是可行性（比丢最优更严重）。读的时候不妨始终带一个问题："这一节的耦合，比上一节深在哪？为什么这个深度需要这个新方法？"——抓住这条螺旋，八节就连成了一个有机整体，而非八张需要分别记忆的方法卡片。另一条更细的暗线是"惰性/按需 + 冲突驱动"——DFJ 割、列生成、异步协调、超图、冲突基都是它的化身，留意它在不同节的反复出现。

前置知识桥接¶

本章大量复用前置章节的工具，这里先把三条最关键的桥重新激活，省得你来回翻：

回顾 TAMP_T1 §2.4-§2.5（符号-几何鸿沟与不能解耦）：单机 TAMP 的核心是"任务序列的可行性依赖几何（够不够得到），而符号层看不到几何"，所以两层必须协同、不能先任务后运动单向下达。本章把这个"两层耦合"升级成"分配-规划-运动三层耦合"——同一种鸡生蛋结构，多套了一层。
回顾 TAMP_T2 §6-§9（MRTA 分类学与分配-规划耦合）：T2 给了 Gerkey-Matarić 三维分类、匈牙利/MILP/拍卖三套求解器，以及 §9 那一节关于"分配代价不是常数、依赖规划出的路线"的纲要性论证。本章 §3-§7 正是把 T2 §9 那一节（仅 ⭐⭐⭐⭐ 一节）展开成完整的多机联合方法论——T2 提出问题、点到为止，本章正面求解。
回顾 Multi_03（多机器人协作线第 3 章，MAPF/CBS）：那里讲了"分配已定、任务独立"后如何为多机求无碰撞路径——MAPF 问题、CBS 约束树、PIBT/LaCAM 可扩展求解、ECBS/EECBS 有界次优。本章不重新推导任何 MAPF 算法，而是把它当作运动层/路径层的现成接口，讨论任务层如何与它对接（§8）、以及任务层的"冲突树"（§7）与 CBS 的"冲突树"在思想上如何同源、在层次上如何区分。

如果跳过本章会怎样¶

两个具体场景说明本章不可省略：

场景一（次优到离谱的仓库）：你有三台搬运机器人和二十个订单，你用 T2 的匈牙利算法按"机器人到货架的直线距离"做了分配，每台机器人再各自跑单机 TAMP。系统能跑，但实际总行驶里程比最优方案高了三成以上——因为直线距离忽略了"顺路"（一台机器人去远处取货时顺手带回沿途的几件几乎免费），分配时没看见这个边际效应。本章 §4-§6 告诉你这三成是怎么丢的、怎么找回来。
场景二（死锁的窄道）：两台机器人分别被分了通道两端的任务，各自的单机 TAMP 都规划出"穿过中间窄道"的最优路线——然后它们在窄道正中相遇，谁也不让，双双卡死。单机 TAMP 永远发现不了这个问题，因为它眼里只有自己。本章 §8 讲这种跨机器人时空冲突如何在任务层被预见和消解、以及它和运动层 MAPF 的分工。

一句话：不学本章，你会把多机系统当成"N 个单机系统的拼装"，而这恰恰是多机 TAMP 第一个、也是最贵的错误。

预计阅读时间¶

模式	时长	路径
精读（推导 + 代码 + 练习全做）	10-13 小时	全章顺序，§4/§5/§7/§9 的推导逐行跟、代码跑通
速读（建立方法地图，跳过部分代码）	4-5 小时	§2-§3 + §4 本质洞察 + §5/§6 结论表 + §8 + §10，代码只看注释
速查（已学过，回头查某个方法）	0.5-1 小时	知识点总表 + 方法速查表 + 对应小节

2. 从单机 TAMP 到多机：多出来的三重耦合 ⭐⭐¶

2.1 动机：一个看似无害的"复制粘贴"¶

你已经在 T1-T4 学会了单机 TAMP：给一台带臂的移动机器人一个目标（"把这些物体各归其位"），它能在符号层排出动作序列、在几何层为每个动作求出可行轨迹，还能在够不到时回头重排。现在老板说："再买两台一模一样的机器人，三台一起干，快三倍。"

最自然的工程直觉是复制粘贴：把任务平均分成三份，每台机器人拿一份，各自跑一遍单机 TAMP，互不干涉。这个方案如此诱人，以至于它几乎是每个人写多机系统的第一版。它也几乎总是错的——而且错得有规律、有层次。本节的任务，就是把"为什么复制粘贴会错"拆成三个清晰的层次，它们正好对应本章后续的三条主线。

2.2 反面：复制粘贴会在三个地方崩¶

我们用贯穿整条 TAMP 线的仓库场景（T0 §2 建立、T1-T2 反复使用）来看复制粘贴的三种崩法。场景：三台机器人 $R_1, R_2, R_3$，一批包裹散落在货架，要送到打包台；机器人臂展有限、一次只能抓一个、电量会耗尽。

崩法一：分得不好，因为"代价"在分的时候根本不知道。

把包裹平均分成三份——按什么分？按"机器人到包裹的直线距离"最便宜？可是 $R_1$ 去取一个远处包裹 $p_7$ 的路上，会经过另外两个包裹 $p_3, p_5$。如果这两个也分给 $R_1$，它顺手带回几乎不花额外代价；如果分给了在另一头的 $R_2$，$R_2$ 得专程跑一趟。也就是说，"把 $p_3$ 分给谁"的真实代价，取决于"$p_7$ 分给了谁、规划出什么路线"——而平均分配在分的那一刻对此一无所知。 这是 T2 §9 已经点破、本章 §4-§6 要正面求解的分配-规划耦合。

崩法二：分好了、各自规划了，却在空间里撞上。

假设分配侥幸合理，三台机器人各自跑单机 TAMP，各自得到一条"对自己最优"的无碰撞轨迹。但每台机器人的"无碰撞"只考虑了静态环境（货架、墙），没考虑另外两台移动的机器人。于是 $R_1$ 和 $R_2$ 的最优路线可能在某个路口同时到达、迎头相撞；更隐蔽的是窄道死锁——两台机器人各自规划穿过同一条单宽通道，在通道里相遇，谁也退不出去。单机 TAMP 的"可行"是相对静态世界的可行，多机里它不再充分。 这是本章 §8 要处理的时空耦合，也是它与运动层 MAPF（Multi_03）的接口所在。

崩法三：有些任务一台机器人根本做不了。

老板又加了一项："把那张两米长的桌子从 A 搬到 B。" 一台机器人搬不动——这个任务本质上需要两台机器人同时抓住、协同移动。复制粘贴的前提（每个任务归一台机器人独立完成）在这里直接失效：这是一个 Gerkey-Matarić 分类学里的 MR（多机器人任务），它要求两台机器人在同一时刻出现在桌子两端、以协调的速度移动。任务层必须排出"$R_1$ 和 $R_2$ 在时刻 $t$ 汇合于桌子两端"这样的同步约束。这是本章 §3 分类学、§8 时序协调都要照顾的协作同步耦合。

本质洞察：多机 TAMP 不是"单机 TAMP $\times N$"。从一台到多台，问题的维度不是线性增加，而是新长出了三类机器人之间的相互依赖——抢任务（谁做划算取决于别人做了什么）、抢时空（我的路可行取决于别人走哪）、需协同（有些事必须一起做）。这三类依赖，恰好对应 Korsah iTax 分类学里"跨机器人依赖 (XD)"和"复杂依赖 (CD)"两个维度（§3 详述）。把多机当成单机的复制，等于假装这三类依赖不存在——而它们恰恰是多机问题全部的难点和全部的价值所在。 单机 TAMP 教你跨越"符号-几何"一道鸿沟；多机 TAMP 教你在此之上再跨越"机器人-机器人"这道鸿沟。

2.3 历史：多机任务层方法的两条源流¶

多机 TAMP 不是凭空出现的，它是两条独立发展的学术源流在 2010 年代后期的交汇。理清这条历史，能帮你理解为什么本章既要讲"拍卖"又要讲"联合优化"——它们来自不同的传统。

源流甲：多机器人系统 / 运筹学传统  (关心"谁来做")
  1985  mTSP/VRP 运筹学奠基       多旅行商、车辆路径，分配+路由的经典 NP-hard
    │
  1997  Dias & Stentz 市场法      把拍卖引入多机器人协调 (M+ / TraderBots)
    │
  2004  Gerkey-Matarić 分类学     把 MRTA 各类问题映射到运筹学已知问题★
    │
  2009  Choi et al. CBBA          分布式捆绑+共识拍卖，成为事实标准★
    │
  2013  Korsah iTax 依赖维度       补上 ID/XD/CD，刻画"分配与规划耦合"★

源流乙：AI 规划 / TAMP 传统  (关心"做什么、几何可行吗")
  1971  STRIPS → 1998 PDDL        单体符号规划
    │
  2010s PDDLStream / LGP          单机 TAMP，缝合符号-几何 (T3/T4)
    │
  2018  Schillinger STAP          时序逻辑下"同时"分配与规划，两流首次深度融合★
    │
  2022+ 多机 TAMP 专门方法         异步精化 / 超图分解 / 冲突基 TAMP，
         (本章 §5/§7/§8)            把单机 TAMP 与多机分配/路径正式焊接

              ↓ 两流交汇 ↓
        多机 TAMP = 运筹学的"分配-路由" × AI 规划的"符号-几何" × MAPF 的"时空避让"

注意打★的五个里程碑：分类学（2004）、CBBA（2009）、iTax（2013）来自源流甲（你在 T2 已经学过它们的基础），STAP（2018）和近年的多机 TAMP 专门方法来自两流交汇。本章的独特之处，正是站在交汇点上——它不像 T2 那样只从运筹学角度看分配、也不像 T3/T4 那样只从 AI 规划角度看单机几何，而是把两者在"多执行者"维度上合起来。

为什么两条源流缺一不可？ 因为它们各自只回答了多机 TAMP 的半个问题：

源流甲（运筹学/MRTA）擅长"谁来做、怎么路由"，但把任务当抽象的"有代价的活"——它看不见几何。mTSP、CVRP、CBBA 里的"代价"是一个数（距离），它们不知道"这个抓取位姿够不够得到""这个放置会不会挡住别人"。把仓库问题交给纯运筹学方法，它能算出漂亮的分配和路线，却可能要求机器人去做几何上根本做不到的动作。
源流乙（AI 规划/TAMP）擅长"做什么、几何可行吗"，但传统上只管一台机器人——它看不见多体分工。PDDLStream、LGP 能为一台机器人缝合符号与几何，却没有"把任务分给谁、多台怎么协调"的概念。把多机问题交给纯单机 TAMP，就退回了 §2.2 的复制粘贴。

多机 TAMP 必须同时要这两半：既要源流甲的"分配-路由"（谁做、怎么走），又要源流乙的"符号-几何"（做什么、够不够得到），还要 MAPF 的"时空避让"（怎么不撞）。这就是 §2.3 那个交汇公式"多机 TAMP = 运筹学的分配-路由，乘上 AI 规划的符号-几何，再乘上 MAPF 的时空避让"的实质——三个传统各补一块，缺任何一块，多机系统都会在对应的地方崩（崩法一缺运筹、崩法三缺协作、崩法二缺 MAPF）。

本质洞察：本章站在两条源流交汇点上，这不是历史的偶然，而是问题结构的必然——多机 TAMP 的难，恰恰难在它同时是一个运筹学问题、一个 AI 规划问题、和一个时空协调问题。任何单一传统都只能解它的一个侧面：纯运筹学解出"几何上做不到"的分配，纯 AI 规划解出"没有分工"的单机计划，纯 MAPF 解出"不知道要做什么任务"的无目标路径。这就是为什么本章既要讲拍卖（源流甲）又要讲冲突基 TAMP（两流交汇）、还要对接 MAPF（源流乙的运动层伙伴）——它们不是可选的章节拼盘，而是同一个问题三个不可分割的侧面。理解了这一点，你就明白本章的知识结构为什么这样组织：§5-§6 是运筹侧（分配-路由），§7 是交汇侧（符号-几何的多机精化），§8 是 MAPF 接口侧（时空避让），三侧合起来才是完整的多机 TAMP。

2.4 理论：三重耦合的形式化刻画¶

把上面三种崩法形式化。设有机器人集合 $\mathcal{R}=\{R_1,\dots,R_m\}$、任务集合 $\mathcal{T}=\{\tau_1,\dots,\tau_n\}$。一个完整的多机 TAMP 解需要同时确定三样东西：

\[ \underbrace{a:\mathcal{T}\to 2^{\mathcal{R}}}_{\text{分配}},\qquad \underbrace{\sigma_k=(\tau_{k_1},\tau_{k_2},\dots)}_{\text{每台机器人 }R_k\text{ 的任务序列}},\qquad \underbrace{\xi_k(t)}_{\text{每台机器人的连续轨迹}}. \]

这里 $a$ 把每个任务映射到一个机器人子集（子集大小 $>1$ 表示协作任务 MR）；$\sigma_k$ 是 $R_k$ 被分到的任务的执行顺序；$\xi_k(t)$ 是实现该顺序所需的关节/底盘轨迹。三重耦合是说，这三者不能分别独立求解：

耦合	形式化表述	数学后果	对应崩法	本章
分配-规划耦合 (ID)	任务 $\tau_j$ 分给 $R_k$ 的代价 $c_{kj}$ 不是常数，而是 $c_{kj}=f(\sigma_k,\xi_k)$——依赖 $R_k$ 的整个序列与路线	代价矩阵不再固定，匈牙利失效，问题变 NP-hard (mTSP/CVRP)	崩法一	§4-§6
时空耦合 (XD)	$R_k$ 的轨迹可行性 $\text{feasible}(\xi_k)$ 依赖其他机器人轨迹：$\xi_k \cap \xi_l=\varnothing\ (\forall l\neq k)$，含时间	单机"无碰撞"不充分，需联合或事后协调 (MAPF)	崩法二	§8
协作同步耦合 (CD)	协作任务 $\tau_j$（$\lvert a(\tau_j)\rvert>1$）要求多台机器人在同一时间窗到达约定构型	引入跨机器人时序约束，序列不能独立排	崩法三	§3, §8

括号里的 ID / XD / CD 是 Korsah iTax 分类学（2013, IJRR）的三种依赖等级，§3 会精确定义。这里先建立直觉：ID 是机器人内部的（自己的任务之间顺路），XD 是机器人之间的（路线互相干扰），CD 是任务结构性的（任务本身要求协作）。复制粘贴方案假设这三者全为零——它假设代价是常数（无 ID）、机器人互不可见（无 XD）、每个任务独立（无 CD）。现实里只要有一个非零，复制粘贴就开始崩。

本质洞察：注意三重耦合的"作用对象"层层升级——ID 耦合发生在一台机器人的任务之间（顺路），XD 耦合发生在机器人与机器人之间（避让），CD 耦合发生在任务与任务的结构之间（协作）。这解释了为什么多机 TAMP 的方法会分化成不同流派：处理 ID 主要靠把规划嵌进分配代价（§6 拍卖的边际出价）；处理 XD 主要靠联合规划或事后路径协调（§5 / §8 MAPF）；处理 CD 主要靠在任务表示里显式编码同步约束（§9 时序逻辑）。你遇到的多机问题里这三类耦合各占多少，决定了你该往本章的哪几节深入。 这也是 §3 要先教你"给问题分类"的原因——分类是选型的前提。

2.5 一张总览：三重耦合与本章结构的对应¶

把本节的三重耦合和全章结构对齐，作为后续阅读的索引：

              单机 TAMP (T1-T4): 跨越"符号↔几何"一道鸿沟
                          │  执行者 1 → N
                          ▼
        ┌──────────────────────────────────────────────┐
        │  多机 TAMP: 在符号↔几何之上, 再跨三道机器人间鸿沟  │
        └──────────────────────────────────────────────┘
                          │
   ┌──────────────────────┼──────────────────────┐
   ▼                      ▼                      ▼
ID 分配-规划耦合        XD 时空耦合            CD 协作同步耦合
(顺路/避让代价)         (路线互相干扰)         (任务要求多机协同)
   │                      │                      │
§3 定位格子             §3 定位格子             §3 定位格子
§4 解剖耦合             §8 时序协调             §8 汇合/交接
§5 联合优化             §8 接 MAPF              §9 时序逻辑同步
§6 拍卖边际出价          §7 分布式冲突树         §9 LTL 协作规约
§7 分布式精化
   │                      │                      │
   └──── §10 边界 ────────┴──── §11 工程 ────────┴──── §12 项目

⚠️ 常见陷阱¶

陷阱 2-1（思维陷阱）：把多机 TAMP 当成"单机 TAMP × N"的并行复制。 - 错误描述：认为多机系统 = N 个独立单机系统，平均分任务后各自跑单机 TAMP 即可。 - 现象/后果：在仿真里看似能跑，实测总代价远超最优（崩法一），或机器人在空间里相撞/死锁（崩法二），或遇到协作任务直接无法表达（崩法三）。 - 根本原因：忽略了机器人之间的三类相互依赖（ID/XD/CD）。复制粘贴隐含假设这三者全为零，而现实里几乎总有非零项。 - 正确做法：先用 §3 的分类学判断问题含哪几类依赖，再选对应方法。无任何依赖（任务独立、空间宽敞、无协作）时复制粘贴才成立——这只是多机问题的最退化特例。

陷阱 2-2（概念误区）：以为"多机 TAMP"主要是多机控制（编队、避障、分布式 MPC）问题。 - 错误描述：把本章和多机器人协作线（Multi 线的分布式 MPC、MARL 编队）混为一谈，期待这里讲怎么让多机协调地动。 - 现象/后果：找错方法——用控制层工具（共识、编队律）去解任务层问题（谁做哪个、什么顺序），或反之。 - 根本原因：没区分任务层（离散：分配 + 排序 + 几何可行性）与运动/控制层（连续：轨迹 + 协调控制）。多机 TAMP 是任务层问题。 - 正确做法：牢记分层——本章产出的是"谁做哪些任务、什么顺序、每个动作几何可行的参数"，把"多机怎么无碰撞协调地动"留给运动层（MAPF/分布式 MPC，Multi 线）。§10 专门划这条边界。

陷阱 2-3（概念误区）：认为只要分配做对了，各自规划就一定无冲突。 - 错误描述：把"好的分配"等同于"无冲突的执行"，以为分配层解决一切。 - 现象/后果：分配最优（每台机器人任务集合合理），执行时仍在窄道/路口冲突，因为分配只管"谁做什么"，不管"路线在时空上怎么交错"。 - 根本原因：分配-规划耦合 (ID) 和时空耦合 (XD) 是两类不同的耦合。把任务分得好（ID 处理好）不蕴含路线不打架（XD 仍需单独处理）。 - 正确做法：分配层处理 ID（用真实路线代价分配），时空层处理 XD（用 MAPF 或联合规划消解路径冲突）。二者都要做，缺一不可（§4 陷阱与 §8 详述）。

练习¶

（⭐⭐，分析） 回到仓库场景，自己构造一个 2 机器人 4 包裹的具体布局（给出坐标），使得"按直线距离平均分配 + 各自规划"分别触发崩法一（次优）和崩法二（路线冲突）。用文字说明每种崩法在你的布局里具体怎么发生。
（⭐⭐，概念） 对下面四个多机任务，判断各自含有 ID/XD/CD 中的哪些耦合，并说明理由：(a) 三台扫地机器人清扫互不相邻的三个房间；(b) 两台 AGV 在同一条主干道上往返运料；(c) 两台机械臂协同翻转一个大工件；(d) 五台无人机巡检一片区域、每个巡检点只需一架但要规划访问顺序。
（⭐⭐⭐，反事实） 假设你能瞬间消除三类耦合中的任意一类（让它恒为零），但只能选一类。对仓库场景，你会选消除哪一类来最大化系统效率？换成"两机械臂协同装配"场景呢？通过这个对比说明"不同应用里三类耦合的相对重要性不同"。

3. MRTA 分类学再深化：定位多机 TAMP 在地图上的格子 ⭐⭐⭐¶

3.1 动机：选型之前，先知道自己站在哪一格¶

§2 把多机比单机多出来的东西拆成了三类耦合（ID/XD/CD）。但"耦合"是个连续光谱——有的多机问题几乎没有耦合（三台扫地机各扫一个房间），有的耦合到了天花板（两台臂协同插装一个柔性件，既要 XD 避让又要 CD 同步）。面对一个具体的多机任务，你做的第一件事不该是挑算法，而该是给它在 MRTA 地图上钉一个坐标——坐标定了，该用匈牙利还是 CBBA、要不要走联合优化、需不需要时序逻辑，几乎是自动浮现的。

这一节不重新讲分类学（那是 T2 §6 的事），而是做一件 T2 没做、也无法做的事：把"多机 TAMP"这个特定问题族，精确地定位到地图的某几个格子里，并解释为什么它偏偏落在那里。T2 §6 教你"地图怎么读"，本节教你"我们这块地在地图的哪个区"。

回顾 T2 §6.2（Gerkey-Matarić 三维）：MRTA 问题由三个二元维度定位——ST/MT（单任务机器人 / 多任务机器人：一台机器人同一时刻能否并行多个任务）、SR/MR（单机器人任务 / 多机器人任务：一个任务需一台还是多台机器人合作）、IA/TA（瞬时分配 / 时间扩展分配：只分当下一轮，还是要排未来的任务序列）。最简单的格子 ST-SR-IA 就是线性指派，匈牙利算法 $O(n^3)$ 求全局最优。

回顾 T2 §6.4（Korsah iTax 依赖维度）：Gerkey-Matarić 默认"任务代价彼此独立"，iTax 补上这条缺失的轴，分四级——ND（无依赖，代价独立）、ID（同一机器人自己任务间的依赖，如顺路）、XD（跨机器人的依赖，如避让）、CD（复杂依赖，任务本身可多种分解）。一个完整的 MRTA 定位需要两套坐标：Gerkey-Matarić 的格子 + iTax 的依赖级。

3.2 多机 TAMP 的坐标：为什么它住在 XD/CD 区¶

把单机 TAMP 推广到多机，问题在两套坐标上同时向"难"的一端移动。逐维分析：

维度	单机 TAMP（T1-T4）	多机 TAMP（本章）	为什么移动
ST/MT	不适用（只有一台）	通常 ST（每台一次做一个任务）	移动操作机器人一般一次抓一个、走一条路；MT 仅见于特殊多臂平台
SR/MR	不适用	SR 为主，混入 MR	多数任务一台能做，但"搬两米桌子"这类必须 MR——一旦有 MR，问题就跳出纯指派
IA/TA	单机已是序列规划（排动作顺序）	必然 TA	多机要排"每台机器人的任务序列"，前瞻整个序列才能算顺路，这是 TA 的定义
iTax 依赖	任务-运动耦合（单机内部）	至少 XD，常含 CD	机器人路线互相干扰是 XD；协作任务的"怎么分解、谁配谁"是 CD

结论一目了然：多机 TAMP 的典型坐标是 ST-SR-TA（混 MR）+ XD（混 CD）。把它和 T2 §6.5 的算法地图对照，立刻看出问题所在——

回顾 T2 §6.5/§8.5（CBBA 的坐标与边界）：CBBA 精确地坐在 ST-SR-TA + ID（捆绑内顺路）+ 分布式 这一格。它用边际出价捕捉同一机器人捆绑内的顺路（ID），但解决不了 XD（任务代价依赖其他机器人走哪条路）、解决不了 MR（协作任务）、解决不了 CD（任务可多种分解）。

这就是多机 TAMP 与 T2 分配方法的分水岭：T2 的 CBBA/匈牙利住在 ND~ID 区，而多机 TAMP 住在 XD~CD 区——正好差了 iTax 那条最难的轴。T2 §6.4 那句"iTax 的 XD/CD 级，正是单纯分配算法失效、必须走向联合求解的分界线"，在本章兑现：本章 §4-§9 的全部方法，本质上都是为了跨过这条 XD/CD 分界线而生。

本质洞察：多机 TAMP 之所以是一个独立的、比 T2 分配更难的问题族，不是因为"机器人变多了"（数量），而是因为它强制进入 iTax 的 XD/CD 区（依赖结构）。一个落在 ND/ID 区的多机问题（任务独立、空间宽敞、无协作），哪怕有一百台机器人，也只是 T2 分配的放大版，CBBA 就够了。反过来，哪怕只有两台机器人，只要它们要在窄道避让（XD）或协同搬桌（CD），就已经是货真价实的多机 TAMP。判断"我该读 T2 还是读本章"的唯一标准，不是机器人数量，而是问题落在 iTax 的哪个区。 这也是为什么本章前置自测 Q2 要你复述分类学——不定位坐标，后面所有方法都失去了"为什么用它"的依据。

坐标直接映射到方法。把常见坐标和对应方法、本章节列成一张选型总表——钉好坐标后，查这张表就知道用什么、读哪节：

完整坐标	典型问题	该用什么方法	本章/前置节
`ST-SR-IA + ND`	此刻给空闲机器人各配最近任务	匈牙利算法（最优、多项式）	T2 §7
`ST-SR-IA + ND`（大规模）	大量独立任务的覆盖分配	子模贪婪（$1-1/e$ 界）	Multi 线 §3.6
`ST-SR-TA + ID`	每台机器人排顺路送货序列	SSI / CBBA（边际出价）	§6
`ST-SR-TA + XD`（弱，小规模）	偶尔交错的多机送货	CBBA + 执行层 MAPF 协调	§6 + §8.4
`ST-SR-TA + XD`（强，小规模）	路线深度纠缠、影响分配优劣	联合 MILP / 冲突基 TAMP	§5 / §7.5
`ST-SR-TA + XD`（强，大规模）	大车队共享拥挤路网	列生成 / 滚动时域 / 分布式混合	§5.6 / §6.6
`ST-MR-TA + CD`	含协作搬运、可多种分解	时序逻辑 STAP / 异步精化	§9 / §7.3
含几何精化（多臂近距离）	多臂共享工作空间重排物体	超图分解 / 集中式联合	§7.4 / §7.7

本质洞察：这张表把"定位"和"选型"焊成了一步——钉好 MRTA + iTax 坐标，方法几乎是查表查出来的。这正是 §3.1 说的"坐标定了，该用什么方法几乎自动浮现"。表的纵向是一条难度阶梯（从上到下耦合越来越深、方法越来越重），横向是"坐标→方法→章节"的映射。新手最该养成的习惯，是拿到问题先钉坐标、再查这张表，而不是凭手熟挑方法（"我会 CBBA 所以都用 CBBA"——这恰是 T2 陷阱 6-1 的错误）。当你能熟练地"钉坐标→查表→读对应节"，你就掌握了多机 TAMP 选型的完整工作流。这张表也是本章 §4-§9 的另一份索引：它从"问题坐标"切入，而 §1 知识导航从"耦合类型"切入，两份索引互补。

3.3 一张定位流程图：给你的多机问题钉坐标¶

把上面的分析做成一个可操作的流程，拿到任何多机任务都能走一遍：

拿到一个多机任务, 给它在 MRTA 地图上钉坐标:
│
├─ Step 1: 有没有"一台机器人做不了、必须多台合作"的任务?
│   ├─ 有 → 含 MR, 进而看这类任务能否多种分解
│   │        ├─ 只有一种合作方式(如固定双臂搬运) → MR, 依赖至少 XD
│   │        └─ 可多种分解(合搬/拆开/换序) → MR + CD ← 最难, 走 §9 时序逻辑
│   └─ 无 → 纯 SR, 继续
│
├─ Step 2: 任务代价是否依赖"机器人怎么排自己的序列"?(顺路)
│   ├─ 是 → 至少 ID, 用边际出价/捆绑(§6); 继续看 XD
│   └─ 否 → ND, 退化到 T2 匈牙利/MILP, 本章可略读
│
├─ Step 3: 一台机器人的路线代价/可行性是否依赖"别人走哪"?(避让)
│   ├─ 是 → 含 XD ← 多机 TAMP 的核心区, 走 §4 解剖 + §5 联合 + §8 接 MAPF
│   └─ 否 → 止于 ID, CBBA 类分布式拍卖足矣(§6), §7-§8 可略
│
└─ Step 4: 要不要排"未来一整段时间"的任务序列, 还含时间窗/资源?
    ├─ 是 → TA + 时序约束, 走 §8 时序协调(STN→多机)
    └─ 否(只分当下一轮) → IA, 问题大幅简化(但多机 TAMP 极少是纯 IA)

走完这四步，你手里就有了一个形如"ST-SR-TA + XD"或"ST-MR-TA + CD"的坐标，以及一串"该读本章哪几节"的指引。这张图是本章 §4-§9 的总索引：ID 走 §6，XD 走 §4/§5/§8，CD 走 §8/§9。

3.4 系统性分类：四类多机问题的"难度阶梯"¶

把 iTax 依赖级当主轴，给多机问题排一个难度阶梯——这能帮你判断手头问题在阶梯的第几级、要付出多少建模代价：

级别	iTax	典型场景	解法	本章对应
第 1 级（最易）	ND	多机巡检互不相邻区域，任务独立	T2 匈牙利（小）/ 子模贪婪（大）	略读，见 T2 §7
第 2 级	ID	单机顺路送多件货，机器人间不干扰	CBBA / SSI 边际出价	§6
第 3 级（核心）	XD	多 AGV 共享路网，路线互相阻塞	联合优化 / 分配 + MAPF 协调	§4, §5, §8
第 4 级（最难）	CD	协作搬运、多种分解、需同步	时序逻辑 STAP / 异步精化	§8, §9

本质洞察：这个阶梯揭示了多机 TAMP 方法论的内在逻辑——每上一级，分配和规划就更分不开一层。第 1 级 ND，分配和规划完全可解耦（先分后规划无损）；第 2 级 ID，分配要"看见"自己的路线（边际代价），但还不必看见别人；第 3 级 XD，分配要"看见"所有人的路线（互相阻塞），解耦开始丢解；第 4 级 CD，连"任务是什么、怎么拆"都和规划纠缠，必须把分配、分解、规划、时序一起求解。这条阶梯就是本章的脊椎：§4 解剖第 3 级为什么解耦会崩，§5-§7 给第 2-3 级的求解方法，§8-§9 啃第 4 级的硬骨头。

3.5 双重解读：同一个多机问题的两种看法¶

定位坐标这件事，还可以从两个互补的角度理解——这能帮你在不同语境下都抓住要害：

角度一（依赖视角）：多机问题的难度 = "任务之间纠缠多深"。ND 是任务全独立（可任意拆开并行）、CD 是任务深度纠缠（拆都拆不干净）。从这个角度，定位就是测量纠缠度——问"把任意两个任务（或两台机器人）分开处理，会丢多少信息？"丢得越多，纠缠越深，越往 CD 走。
角度二（信息流视角）：多机问题的难度 = "分配层要看见多少规划信息才能决策正确"。ND 下分配不需要任何规划信息（代价是常数）；ID 下要看见自己的路线；XD 下要看见所有人的路线；CD 下还要看见"任务怎么拆才合理"。从这个角度，定位就是测量信息需求——问"要把分配做对，分配层必须从规划层拿到什么？"拿得越多，耦合越强。

这两个角度描述的是同一件事的两面：纠缠越深（角度一），分配层需要的规划信息就越多（角度二）。依赖视角告诉你"问题有多难"，信息流视角告诉你"难在哪、该把什么信息接通"——后者直接指向解法（§4.5 的"修信息通道"）。

3.6 定位实例演练：跟着钉三个坐标¶

抽象的流程图不如跟着走几遍。下面用渐隐示例的方式，从"全程示范"过渡到"你来定"。

示例 1（完整示范）：三台快递机器人，每台今天要送一批包裹，路网宽敞、机器人间几乎不交错，但每台要规划自己最省的送货顺序。 - Step 1（MR？）：每个包裹一台机器人就能送，无协作 → 纯 SR。 - Step 2（顺路 ID？）：每台要排送货顺序、顺路省距离 → 含 ID。 - Step 3（避让 XD？）：路网宽敞、几乎不交错 → 几乎无 XD（弱到可忽略）。 - Step 4（TA？）：要排"今天一整批"的顺序 → TA。 - 坐标 = ST-SR-TA + ID，该读 §6（拍卖/CBBA）——这正是 CBBA 的主场。

示例 2（部分留白）：五台 AGV 在一个有几条单宽通道的车间运料，任务独立（每趟运一种料），但通道窄、AGV 常在通道口排队等待。 - Step 1（MR？）：每趟一台 AGV 即可 → 纯 ______。 - Step 2（顺路 ID？）：每台要排多趟运料的顺序 → 含 ______。 - Step 3（避让 XD？）：单宽通道导致排队等待、互相阻塞 → 含 ______，且因为通道是瓶颈、阻塞会影响"谁先走哪趟划算"，这个 XD 是 ______（强/弱）。 - 坐标 = ST-SR-TA + ______，该读 ______（提示：强 XD 走联合或冲突基）。

（参考：SR；ID；XD，强；XD；§5 联合优化 / §7 冲突基 / §8 时序协调。）

示例 3（你来定）：两台移动机械臂要把一块大玻璃从立式货架取下、翻转成水平、放到工作台。玻璃太大太重，必须两臂同时抓住协同搬运，且翻转过程要全程协调速度。 - 自己走完 Step 1-4，钉出坐标，并指出该读哪一节。（提示：注意"必须两臂同时"和"协调速度"分别触发哪个维度。）

本质洞察：做完这三个演练你会发现，定位的关键判断往往集中在一两个 Step 上——示例 1 的要害在"路网宽敞所以 XD 弱"，示例 2 的要害在"通道是瓶颈所以 XD 强"，示例 3 的要害在"必须同时所以是 MR+CD"。这告诉你定位不是机械地走完四步，而是识别问题里那个决定性的耦合特征：是不是有任务一台做不了（MR）？避让发生在瓶颈还是冗余里（强/弱 XD）？任务能不能跨机器人拆开（CD）？抓住这个决定性特征，坐标就钉准了。熟练之后，定位是一瞥之间的事——这正是 §6.2 选型决策树想培养的"快速定位问题坐标"的能力，是多机 TAMP 工程师最核心的直觉。

⚠️ 常见陷阱¶

陷阱 3-1（思维陷阱）：用机器人数量而非依赖结构判断问题难度。 - 错误描述：看到"一百台机器人"就觉得是难问题，看到"两台"就觉得简单，据此选重型或轻型方法。 - 现象/后果：给一百台任务独立的巡检机器人硬上联合优化（杀鸡用牛刀，求解器爆炸），或给两台要协同插装的臂用独立 CBBA（建模失真，根本表达不了同步约束）。 - 根本原因：难度由 iTax 依赖级（结构）决定，不由数量决定。数量影响的是"求解规模"，依赖级影响的是"该用哪类方法"。 - 正确做法：先用 §3.3 流程图钉 iTax 坐标，再据级别选方法（第 1-2 级用分配，第 3-4 级用联合/时序），最后才考虑规模（大规模在选定方法内换可扩展变体）。

陷阱 3-2（概念误区）：把 MR（多机器人任务）和 TA（时间扩展）混为一谈。 - 错误描述：认为"多台机器人参与"就是 MR，"要排多个任务"就是 MR。 - 现象/后果：把"三台机器人各送一个包裹"（其实是 SR：每个包裹一台机器人就够）误判成 MR，引入根本不存在的协作约束；或把"一台机器人排十个任务"（TA）误判成 MR。 - 根本原因：MR 是"单个任务需要多台机器人同时协作"（搬两米桌子），TA 是"单台机器人要排未来一串任务"——两者是不同维度。一个 SR-TA 问题里有很多机器人、每个排很多任务，但没有任何一个任务需要协作。 - 正确做法：判 MR 只看"有没有哪个任务一台机器人独立完成不了"。有才是 MR，否则不管多少台机器人参与系统、每台排多少任务，都是 SR。

陷阱 3-3（概念误区）：以为定位到 XD 就必须用最重的联合优化。 - 错误描述：一发现问题含 XD（避让），就直接上全局 MILP 联合求解。 - 现象/后果：中等规模就求解超时，工程上根本跑不动；而其实"分配用 CBBA + 执行层用 MAPF 消解避让"这种分层方案已足够。 - 根本原因：XD 有强弱之分——弱 XD（偶尔在路口交错）可在执行层用 MAPF 事后协调，强 XD（路线深度纠缠、影响分配优劣）才需联合。把所有 XD 当强 XD 是过度建模。 - 正确做法：先判 XD 强弱（避让是否影响"谁做哪个划算"）。弱则"分配 + MAPF 协调"（§8），强则联合优化（§5）。§4 会给出区分强弱 XD 的具体判据。

练习¶

（⭐⭐，分类） 给下列五个多机任务各钉一个完整坐标（Gerkey-Matarić 格子 + iTax 级别），并指出该读本章哪一节：(a) 四台无人机分别巡检四个互不相邻的塔架；(b) 三台 AGV 在一条主干道往返运料、会互相堵；(c) 两台移动臂协同把一块玻璃从竖直翻成水平；(d) 一台机器人今天要按最省路线送二十个包裹；(e) 五台机器人收拾仓库，有的物体重到要两台合搬、且既可合搬也可拆开搬。
（⭐⭐，对比） 对比"一百台任务独立的巡检机器人"和"两台协同搬桌的机器人"，说明为什么前者读 T2 §7 就够、后者必须读本章 §8-§9。从 iTax 依赖级的角度解释，而非从数量。
（⭐⭐⭐，反事实） 假设你能把某个多机问题的 iTax 级别强行降一级（XD→ID 或 CD→XD），代价是改变任务或环境设计。对"多 AGV 共享窄路网"场景，你会怎么改环境把 XD 降成 ID（提示：单向道）？这个降级在工程上付出了什么、换来了什么？

4. 分配-规划耦合的完整解剖：顺路与避让如何引发回溯 ⭐⭐⭐⭐¶

4.1 动机：把"代价不是常数"这句话算到底¶

T2 §9 已经点破了核心命题——任务的代价不是常数，而是依赖分配方案和规划出的路线——并给了三种应对策略的纲要。但 T2 §9 点到为止，它没有把"代价为什么不是常数"算给你看，也没有说清 ID 顺路和 XD 避让这两种"非常数"在数学上长什么样、它们各自如何把多项式可解的指派问题推向 NP-hard、又如何引发跨层回溯。这一节就做这件 T2 留下的事：把抽象的"耦合"落到具体的代价函数和数值算例上，让你亲眼看见解耦在哪一步、丢了多少。

回顾 T2 §9.2（解耦的诱惑与陷阱）：最自然的工程直觉是两步解耦——第 1 步用固定代价做分配（匈牙利/拍卖），第 2 步每台机器人对自己的清单各自排序规划。问题出在第 1 步"每个任务有固定代价"这个假设是错的：把包裹 $p_1$ 分给 $R_1$ 的真实代价，取决于 $R_1$ 还被分了哪些别的包裹（顺路则边际小，分散则边际大）。T2 §9.2 的本质洞察指出，这与 TAMP 的任务-运动耦合是"同一个结构性难题的两个实例"。

4.2 ID 顺路：边际代价为什么不是常数（一个能手算的例子）¶

先把 ID 依赖算清楚。设仓库里打包台 $D$ 在原点，三个包裹位置为 $$p_1=(2,0),\quad p_2=(2,1),\quad p_3=(8,0),$$ 机器人 $R_1$ 起点在 $D$。用欧氏距离、机器人一次抓一个但可在一趟里依次访问多点（走 mTSP 式路线），代价是总行驶距离。

问"把 $p_1$ 分给 $R_1$ 的代价是多少"——这个问题本身没有答案，除非你说清 $R_1$ 还做什么。 算三种情形：

情形 A：$R_1$ 只做 $p_1$。路线 $D\to p_1\to D$，代价 $2\times 2=4$。
情形 B：$R_1$ 做 $\{p_1,p_2\}$。最优路线 $D\to p_1\to p_2\to D$，代价 $2+1+\sqrt{5}\approx 5.24$。$p_2$ 的边际代价（在已含 $p_1$ 的路线上插入 $p_2$ 多花的）只有 $5.24-4=1.24$，远小于"$p_2$ 单独往返"的 $2\sqrt 5\approx 4.47$——这就是顺路：$p_2$ 几乎在 $p_1$ 旁边，插进来几乎免费。
情形 C：$R_1$ 做 $\{p_1,p_3\}$。最优路线 $D\to p_1\to p_3\to D$，代价 $2+6+8=16$。$p_3$ 的边际代价 $16-4=12$，比它单独往返的 $16$ 略小，但依然昂贵——$p_3$ 在远处，不顺路。

把这写成数学：任务 $\tau_j$ 对机器人 $R_k$ 的代价不是一个数 $c_{kj}$，而是一个依赖当前已分配集合 $S$ 的边际函数 $$ \Delta c_k(\tau_j \mid S)\;=\;\mathrm{route}_k\big(S\cup{\tau_j}\big)\;-\;\mathrm{route}_k\big(S\big), $$ 其中 $\mathrm{route}_k(\cdot)$ 是"$R_k$ 访问这组任务的最优路线长度"（一个 TSP 子问题）。边际代价 $\Delta c_k(\tau_j\mid S)$ 显式依赖 $S$——这就是"代价不是常数"的精确含义。情形 B 里 $\Delta=1.24$，情形 C 里 $\Delta=12$，同一个动作（不，是不同任务）对同一机器人，边际代价差了近十倍，全看它和谁打包。

回顾 T2 §8.3（SSI 边际出价）与 §8.5（CBBA 捆绑）：序贯单物品拍卖 (SSI) 的出价正是这个 $\Delta c_k(\tau_j\mid S)$——机器人对任务的出价 = 把它插入自己当前路线的边际代价；CBBA 的捆绑构建也按边际收益贪心加任务。所以 T2 的拍卖方法天生就在处理 ID——它们用边际出价绕过了"固定代价"假设。本章 §6 会把这条线接着往下走。

ID 如何把问题变难。 如果代价真是常数（ND），分配就是线性指派，匈牙利 $O(n^3)$ 搞定。但一旦代价是边际函数（ID），"最优分配"必须同时决定"每台机器人做哪些 + 按什么顺序走"——这就是 mTSP，NP-hard。

回顾 T2 §9.3：T2 §9.3 已给出这个结论——MRTA 常表达为 mTSP（NP-hard）；带容量约束时是 CVRP（NP-hard）。本节补上了"为什么"：因为 ID 让代价成了路线的函数，分配和排序再也切不开。§5 会把这个 mTSP/CVRP 写成精确的 MILP。

4.3 XD 避让：一台机器人的路，取决于别人走哪¶

ID 还只是"机器人内部"的耦合——$\Delta c_k$ 只依赖 $R_k$ 自己的集合 $S$。XD 把耦合升级到"机器人之间"：$R_1$ 的路线代价，还取决于 $R_2,R_3$ 走哪条路。

回到 §2 的窄道死锁。设环境中有一条单宽通道，$R_1$ 要从西侧任务点去东侧，$R_2$ 反向。各自独立规划，两条最短路都穿通道——在通道里相遇，谁也退不出。此时 $R_1$ 的"可行路线"不再是它自己能算出来的： $$ \mathrm{feasible}(\xi_1)\;\Longleftrightarrow\;\xi_1\cap\xi_2=\varnothing \text{(含时间维)}, $$ 而 $\xi_2$ 又依赖 $R_2$ 被分了什么。代价函数从 $\Delta c_k(\tau_j\mid S_k)$ 进一步变成 $\Delta c_k(\tau_j\mid S_k;\ \xi_{-k})$——多了一个"其他所有机器人的轨迹 $\xi_{-k}$"作为参数。

本质洞察：ID 和 XD 的数学差别，是边际代价函数多了一个参数。ID 的边际代价 $\Delta c_k(\tau_j\mid S_k)$ 只看自己的任务集 $S_k$——这是一个可分离的结构：每台机器人的代价独立于他人，分配问题虽是 NP-hard（mTSP），但至少能拆成 $m$ 个互不影响的子问题来近似（这正是 CBBA 能分布式的根基）。XD 的边际代价 $\Delta c_k(\tau_j\mid S_k;\xi_{-k})$ 多了 $\xi_{-k}$ 这个耦合项，破坏了可分离性——你没法在不知道别人走哪的情况下算自己的代价，于是分布式贪心失去了正确性基础。这一个参数的差别，就是 CBBA 够用（ID）和 CBBA 不够用（XD）的分水岭，也是 §3.4 难度阶梯第 2 级和第 3 级的本质区别。 多机 TAMP 的"难"，浓缩在 $\xi_{-k}$ 这三个字符里。

4.4 强 XD 与弱 XD：决定该分层还是该联合的判据¶

§3 陷阱 3-3 提到 XD 有强弱之分，这里给出可操作的判据。关键问题是：避让是否反过来影响"谁做哪个任务划算"？

弱 XD：避让只是偶尔在路口/走廊交错，绕一下或等一下就过去了，不改变分配的优劣排序。此时可以"先分配（当作 ND/ID）、执行层再用 MAPF 消解路径冲突"——分配层假装看不见 XD，把避让甩给运动层事后处理。
强 XD：避让代价大到会颠覆分配决策——比如某条路被占用导致 $R_1$ 必须大绕行，使得"$p_5$ 本该分给 $R_1$"变成"分给 $R_2$ 更好"。此时避让和分配深度纠缠，事后 MAPF 救不回来，必须在分配时就联合考虑路线冲突。

判据可以量化：设 $C_{\text{alloc}}^{\text{ind}}$ 是忽略 XD 的最优分配代价，$C_{\text{coord}}$ 是加上 MAPF 协调后的真实执行代价。定义协调代价比 $$ \rho\;=\;\frac{C_{\text{coord}}-C_{\text{alloc}}^{\text{ind}}}{C_{\text{alloc}}^{\text{ind}}}. $$ $\rho$ 小（经验上 $<10\%$）说明 XD 弱，分层方案的损失可接受；$\rho$ 大说明 XD 强，分层丢的太多，值得上联合优化。这把"该分层还是该联合"从拍脑袋变成了可测量的决策。

本质洞察：强弱 XD 的区分，本质是在问"避让发生在分配的关键路径上吗"。如果避让只动用了系统的冗余（宽敞空间、松弛时间），它就是弱的，可以局部化解；如果避让动到了瓶颈资源（唯一通道、紧时间窗），它就会向上传导、改变全局最优分配，是强的。这与 §3.4 难度阶梯一脉相承——弱 XD 实际上可当 ID 处理（停在第 2 级），强 XD 才真正把你推到第 3 级。工程上的智慧往往是把强 XD 想办法变成弱 XD：加一条单向道、错开时间窗、留出缓冲区，让避让退回到冗余里去（这正是 §3 练习 3 的降级思想）。能用环境设计消掉的耦合，就不要用算法去硬解——这是多机系统设计第一性的取舍。

4.5 跨层回溯：耦合如何引发和 TAMP 同构的"盲目重试"¶

现在把 ID/XD 引发的回溯讲透——这是 T2 §9.2 说"与 TAMP 任务-运动耦合同构"的具体兑现。两步解耦法的执行链：

解耦法的回溯链(与 TAMP_T1 §2.4 同构):
  分配层: 用直线距离(假代价)把任务分给 R1/R2/R3
     │  (此时 ID 顺路、XD 避让全看不见)
     ▼
  规划层: 每台机器人规划真实路线
     │  发现: R1 被分的任务其实很分散(ID 假设错), 真实代价远超直线估计
     │  发现: R1 和 R2 的最优路线在窄道冲突(XD), 一方必须大绕行
     ▼
  失败/次优反馈: "这个分配的真实代价比估计高 40%"
     │  但分配层不知道该怎么改 —— 它当初按直线距离分, 现在只能
     │  换一种分配再试, 而它依然看不见顺路和避让
     ▼
  盲目重分 → 规划又在别处暴露新的 ID/XD 偏差 → 再重分 → ...
     最坏: 在分配-规划之间反复振荡, 不收敛

这条链和 T1 §2.4 的"任务层排计划→运动层执行失败→盲目换序→无限回溯"逐字同构——只是把"任务 vs 运动"换成了"分配 vs 规划"。根源也同构：两层解耦、信息单向流动、失败方不知道为什么失败。分配层把代价当常数下达给规划层，规划层算出真实代价却没有有效通道反馈"该怎么改分配"，于是只能盲目重试。

本质洞察：跨层回溯的病根，从来不是"算法不够强"，而是"信息流是单向的"。分配层向规划层单向下达任务清单，规划层的真实代价/冲突却流不回分配层去指导"下一次该怎么分"。T2 §9.4 的三种策略，本质都是在修这条信息通道：策略一（迭代修正）让真实代价事后流回去重分（慢通道）；策略二（规划嵌入代价）让分配出价时就调用规划器算真实边际（即时通道，处理 ID）；策略三（联合优化）干脆把两层焊成一个问题，不存在"流回去"的问题（无通道，因为无分层）。认清"修信息通道"是所有解法的统一目标，你就不会被各种方法的表面差异迷惑——它们都在回答同一个问题：怎么让分配层"看见"规划层的真相。§5 走策略三的极致（联合），§6 走策略二的极致（出价嵌规划），§7 走分布式版本。

4.6 修好信息通道：从盲目回溯到即时反馈¶

把上面的诊断变成解法。§4.5 的病灶是"分配层看不见规划层真相"，最直接的修法是策略二——把规划器嵌进出价，让真实边际代价在分配的那一刻就流入决策，从源头消除事后回溯：

策略二: 修好信息通道(对比 §4.5 的盲目回溯链):
  分配层准备出价:
     │  对每个候选"任务→机器人"组合, 不再猜直线距离
     ▼
  即时调用规划器: Δc_k(τ|S_k) = route(S_k∪{τ}) - route(S_k)
     │  ↑ 真实边际代价(含顺路、含避障) 当场算出, 流入出价
     ▼
  用真实边际做分配/出价(SSI 出价 / CBBA 捆绑)
     │  分配层"看见"了规划层真相, 不会再分出"以为顺路其实绕远"的错配
     ▼
  执行: 真实代价与分配假设一致, 无事后回溯(ID 已被消化)

对比 §4.5 那条"盲目重分→再失败→再重分"的振荡链，这里信息在分配前就流通了，回溯被前移消化。这正是 §6.4 TAMP 感知 CBBA、§11.3 最小循环里 marginal_cost 的来历。

读到这里你可能会问："既然策略二这么好，为什么还需要 §5 的联合优化（策略三）？" 答案在于策略二修的通道是单向加宽——它让分配层看见了规划层的真相（自己的真实路线），但规划器在算 $\Delta c_k(\tau\mid S_k)$ 时只看得到自己一台机器人，它算不出"$R_2$ 会不会堵在 $R_1$ 的必经之路上"。也就是说，策略二消化了 ID（$S_k$ 依赖），却消化不了 XD（$\xi_{-k}$ 依赖）——因为 XD 要求分配层看见所有机器人的路线如何互相干扰，而单机出价的规划器没有这个全局视野。要修 XD 的通道，要么把所有机器人的路线放进同一个问题（§5 联合优化，无分层故无通道问题），要么在执行层用 MAPF 做事后协调（§8）。这就是为什么本章需要三种策略而非一种：它们修的是不同层次的信息通道——策略二修 ID 通道，策略三/MAPF 修 XD 通道。

本质洞察：策略二和策略三的分工，对应 §4.3 那个"边际代价多一个参数"的洞察。策略二处理 $\Delta c_k(\tau\mid S_k)$ 里的 $S_k$ 依赖——这是机器人内部的，单机规划器看得见、算得出，所以"出价时调用自己的规划器"就够。策略三/MAPF 处理多出来的 $\xi_{-k}$ 依赖——这是机器人之间的，单机规划器看不见，必须要么联合（让一个问题同时看所有机器人）、要么事后协调（MAPF 检测并消解机器人间的实际冲突）。$S_k$ 和 $\xi_{-k}$ 这两个参数，精确地划分了"哪些耦合能靠加宽单机通道解决（ID）、哪些必须靠全局视野解决（XD）"。 这是理解本章所有方法分工的钥匙：看一个方法能不能处理 XD，就看它在算代价时有没有全局（所有机器人）视野。

4.7 量化解耦的损失：一个完整的对比手算¶

把"解耦丢多少"算成一个具体数字，让 §4 陷阱 4-1 的"30%-40%"不再是空话。场景：depot $D=(0,0)$，两台机器人 $R_1$ 起点 $(0,0)$、$R_2$ 起点 $(10,0)$，四个包裹 $$ p_1=(1,0),\quad p_2=(2,0),\quad p_3=(9,0),\quad p_4=(8,0). $$ 直觉上 $p_1,p_2$ 在 $R_1$ 那头、$p_3,p_4$ 在 $R_2$ 那头。代价 = 两台机器人各自路线长度之和（都从自己起点出发、回 depot $D$；为简化设送完回 $D$）。

方案甲——按"机器人到包裹直线距离"贪心分配（解耦法，ND 假设）。 直线距离矩阵（机器人到各包裹）：$R_1$ 到 $p_1,p_2,p_3,p_4$ 分别是 $1,2,9,8$；$R_2$ 到它们是 $9,8,1,2$。贪心/匈牙利按最近分：$R_1$ 拿 $p_1,p_2$，$R_2$ 拿 $p_3,p_4$——看起来很合理。但注意 $R_2$ 起点在 $(10,0)$、depot 在 $(0,0)$：$R_2$ 的真实路线是 $(10,0)\to p_3(9,0)\to p_4(8,0)\to D(0,0)=1+1+8=10$。$R_1$ 的路线 $(0,0)\to p_1\to p_2\to D=1+1+2=4$。总代价 $=4+10=14$。

方案乙——联合最优（看真实路线代价）。 关键洞察：$R_2$ 反正要从 $(10,0)$ 回到 depot $(0,0)$，它顺路就能把 $p_1,p_2$ 也带回来（它们在 $R_2$ 回程的必经直线上）！考虑分配 $R_1$ 拿 $\varnothing$（不出动）、$R_2$ 拿全部 $p_1,p_2,p_3,p_4$：$R_2$ 路线 $(10,0)\to p_3(9)\to p_4(8)\to p_2(2)\to p_1(1)\to D(0)=1+1+6+1+1=10$。$R_1$ 不出动代价 $0$。总代价 $=0+10=10$。

解耦的损失：$(14-10)/10 = 40\%$。 方案甲多跑了 $40\%$，原因正是 §4 陷阱 4-1 说的——直线距离让 $R_1$ "抢"了 $p_1,p_2$，却没看见"$R_2$ 反正要回 depot、顺路带回这两个几乎免费"。这就是 ID 顺路被直线距离掩盖的代价，和 T2 §9.3 仓库研究、Multi 线场景一的 $40\%$ 同一量级。

方案	$R_1$ 路线	$R_2$ 路线	总代价	相对最优
甲（直线距离贪心）	$D\to p_1\to p_2\to D=4$	$(10,0)\to p_3\to p_4\to D=10$	14	+40%
乙（联合最优，看顺路）	不出动 $=0$	$(10,0)\to p_3\to p_4\to p_2\to p_1\to D=10$	10	最优

本质洞察：这个手算把"代价不是常数"的抽象命题钉成了一个 $40\%$ 的数字。方案甲不是"算错了"——它在 ND 假设下完全正确（按直线最近分），它错在假设本身：它假装 $p_1$ 的代价是固定的（$R_1$ 去拿的直线距离 1），而真相是"$p_1$ 几乎免费——只要让顺路的 $R_2$ 带"。解耦法的 $40\%$ 损失，全部来自'在分配时看不见顺路'这一个信息缺口。这也直接示范了为什么 §5 联合优化值得——它把"谁顺路"这个信息纳入同一个问题，于是自然发现"让 $R_2$ 全包"比"按直线分"省 $40\%$。当你的应用里这种顺路结构普遍（仓库、配送），$40\%$ 就是联合优化相对解耦的真金白银。

⚠️ 常见陷阱¶

陷阱 4-1（思维陷阱）：用直线距离做分配代价，以为"差不多"。 - 错误描述：分配时图省事，用机器人到任务的直线（欧氏）距离当代价矩阵，跑匈牙利/拍卖。 - 现象/后果：分配看着合理，执行时总行驶里程比最优高 30%-40%（T2 §9.3 的仓库研究、Multi 线《任务分配与路径规划》场景一的 40% 都印证了这个量级），因为直线距离系统性低估了"分散任务的绕路"、忽略了"顺路的便宜"。 - 根本原因：直线距离是 ND 假设（代价独立且等于直线），而真实问题至少是 ID（边际代价依赖路线）。假设和现实系统性偏离。 - 正确做法：至少用"插入边际代价"$\Delta c_k(\tau_j\mid S_k)$ 当出价（调用一次路线规划器），即 T2 §9.4 策略二。直线距离仅可用于极粗的初筛或 $\rho$ 很小的弱耦合场景。

陷阱 4-2（概念误区）：以为处理好 ID（顺路）就处理好了耦合。 - 错误描述：把规划器嵌进出价、算准了自己的顺路边际，就认为耦合解决了。 - 现象/后果：单机路线都最优，多机一起跑却在窄道堵死或路口频繁让行，实际 makespan 远超预期。 - 根本原因：ID 和 XD 是两层耦合（§4.3）。算准自己的顺路（去掉 $S_k$ 依赖的偏差）不蕴含路线不打架（$\xi_{-k}$ 耦合项仍在）。 - 正确做法：ID 用边际出价处理；XD 另需处理——弱 XD 用执行层 MAPF 协调（§8），强 XD 用联合优化（§5）。两者正交，缺一不可。这正是 T2 陷阱 9-2 的延续。

陷阱 4-3（编程陷阱）：在出价里调用规划器，却每次从零重算整条路线。 - 错误描述：实现策略二时，每评估一个候选任务的边际代价，就把"当前集合 + 该任务"的整条 TSP 路线从头算一遍。 - 现象/后果：$n$ 个任务、$m$ 台机器人，光算边际代价就要 $O(nm)$ 次完整 TSP 求解，每次 TSP 又是指数/重启发，分配阶段慢到不可用。 - 根本原因：没利用"边际"的增量结构——插入一个点到已有路线，只需评估它在各相邻位置的插入增量，不必重解整条路线。 - 正确做法：用廉价插入启发（cheapest insertion）算边际：固定已有路线，只试新任务插在哪两点之间最省，$O(|S_k|)$ 而非完整 TSP。仅在最终确定路线时才精算。配合"惰性"策略（T2 §9.4 提到的 lazy），只对有竞争力的候选精算路径。

练习¶

（⭐⭐，手算） 在 §4.2 的坐标基础上加一个机器人 $R_2$ 起点 $(8,2)$，和一个包裹 $p_4=(8,1)$。分别计算：(a) 把 $\{p_3,p_4\}$ 都分给 $R_1$ 的总代价；(b) 把 $p_3$ 分给 $R_1$、$p_4$ 分给 $R_2$ 的总代价。哪个分配更优？用这个例子说明"$p_3$ 该分给谁"如何依赖"$p_4$ 分给谁"。
（⭐⭐⭐，分析） 设计一个 2 机器人场景，使协调代价比 $\rho$ 在两种环境下分别为"接近 0"（弱 XD）和"超过 50%"（强 XD）。提示：弱 XD 用宽敞空间，强 XD 用一条必经的单宽瓶颈通道。说明同样的任务、同样的分配，仅环境拓扑不同，就决定了该分层还是该联合。
（⭐⭐⭐⭐，综合，跨 §4-§5） 把 §4.5 的回溯链改造成一个"信息通道修好了"的版本：画出策略二（规划嵌入出价）下的数据流，说明真实边际代价如何在分配时就流入决策，从而消除事后回溯。再讨论它为什么仍处理不了 XD（提示：出价时调用的规划器只看得到自己一台机器人）。

5. 联合优化建模：把分配、排序、路由写进一个问题 ⭐⭐⭐⭐¶

5.1 动机：T2 §9.4 策略三需要一个真正的模型¶

T2 §9.4 给了三种应对耦合的策略，策略三是"联合优化：把分配、排序、路由写进一个优化问题"——但 T2 只给了名字和取舍表，没给模型。§4 已经论证了为什么必须联合（ID/XD 让代价非常数、解耦引发回溯）。这一节兑现策略三：把多机分配-排序-路由写成一个精确的混合整数线性规划 (MILP)，让你看清变量是什么、约束怎么写、规模为什么炸、以及列生成等分解思路如何救场。

回顾 T2 §7.4-§7.5（MILP 通用建模）：T2 §7 教过用 MILP 建模分配——引入 0/1 变量 $x_{ij}$（任务 $i$ 是否分给机器人 $j$），目标 $\min\sum c_{ij}x_{ij}$，约束"每任务分给恰一台"。但 T2 §7 的 MILP 是 ND 假设（$c_{ij}$ 常数、不含排序）。T2 §7.5 练习 3 已预告要把它扩展成"分配 + 排序"的 mTSP 式模型（引入 $x_{ijk}$ 表示机器人 $k$ 是否从任务 $i$ 直接去任务 $j$，加子环消除）。本节正面完成这个扩展。

5.2 把问题写成图：节点、弧、流¶

联合问题的标准载体是一张有向图。设： - 节点集 $V=\{0\}\cup\mathcal{T}$，其中 $0$ 是公共起讫点（depot，如打包台/出发位），$\mathcal{T}=\{1,\dots,n\}$ 是 $n$ 个任务（每个任务对应一个地点）。 - 弧集 $A=\{(i,j): i,j\in V,\ i\neq j\}$，弧 $(i,j)$ 上有代价 $d_{ij}$（从 $i$ 地到 $j$ 地的真实行驶代价——注意这里 $d_{ij}$ 是两地之间的代价，是常数；"代价非常数"的复杂性被转移到了"走哪些弧"的组合选择上）。 - 机器人集 $\mathcal{R}=\{1,\dots,m\}$。

核心决策变量是一族 0/1 流变量： $$ x_{ij}^{k}=\begin{cases}1,&\text{机器人 }k\text{ 紧接着从 }i\text{ 地驶向 }j\text{ 地},\0,&\text{否则}.\end{cases} $$ 一台机器人的"任务序列"就编码在它选中的那些 $x_{ij}^k=1$ 的弧里——它们首尾相接，构成一条从 depot 出发、串起若干任务、回到 depot 的回路。分配（哪些任务归 $k$）、排序（先去哪后去哪）、路由（走哪条弧）三层决策，被这一族变量一次性统一表达了——这正是"联合"的含义。

把变量画出来。 设 depot $0$、任务 $1,2,3$、两台机器人 $R_1,R_2$。一个具体的解（$R_1$ 做 $1,2$，$R_2$ 做 $3$）对应这些被选中（取 1）的弧：

2 机 3 任务的一个解, 用 x_ij^k 表示(只列取 1 的):
  R1 的路线 0→1→2→0:   x_01^1=1, x_12^1=1, x_20^1=1   (其余 R1 的弧全 0)
  R2 的路线 0→3→0:     x_03^2=1, x_30^2=1             (其余 R2 的弧全 0)

  读这组弧:
  ├─ 分配: 进入任务 1,2 的弧属 R1 → 1,2 归 R1; 进入 3 的属 R2 → 3 归 R2
  ├─ 排序: R1 的弧 0→1→2 串起来 → R1 先做 1 后做 2
  └─ 路由: 每条弧 (i,j) 对应从 i 地到 j 地的实际路径(代价 d_ij)

  覆盖(5.2)检查: 任务 1 被 x_01^1 进入一次✓, 2 被 x_12^1✓, 3 被 x_03^2✓
  流守恒(5.3)检查: 任务 1 进(x_01^1)一次、出(x_12^1)一次✓ ...

这组弧同时编码了"谁做哪些（分配）+ 什么顺序（排序）+ 走哪条路（路由）"——三层决策压进了同一族 0/1 变量。求解器要做的，就是从所有可能的弧组合里，挑出满足约束（覆盖、流守恒、无子环）且总代价最小的那一组。

本质洞察：联合优化的建模精髓，是用"流"把三层决策合并。解耦法把分配（集合划分）、排序（TSP）、路由（最短路）当三个问题先后解；联合法发现它们其实是同一张图上的同一件事——选一组弧，使每台机器人的弧构成一条合法回路、所有任务被覆盖、总弧代价最小。一旦看出"分配+排序+路由 = 选弧"，三层耦合就不再是三个纠缠的问题，而是一个统一的（虽然 NP-hard 的）组合优化问题。 这个视角的转换，是从 T2 §9 的"定性说耦合"到本章"定量解耦合"的关键一跃。

5.3 完整的 MILP：目标、度约束、子环消除¶

把上述写成完整 MILP（这是经典的多车辆路径问题 mTSP/VRP 形式）：

\[ \min_{x}\ \sum_{k\in\mathcal{R}}\sum_{(i,j)\in A} d_{ij}\,x_{ij}^{k} \tag{5.1} \]

约束一：每个任务恰好被一台机器人访问一次（覆盖 + 分配）。 $$ \sum_{k\in\mathcal{R}}\sum_{i\in V,\,i\neq j} x_{ij}^{k}=1,\qquad \forall j\in\mathcal{T}. \tag{5.2} $$ 这条同时表达了"每个任务被做"（覆盖）和"只被一台机器人做"（分配的互斥）——它取代了 T2 §7 那条 $\sum_k x_{jk}=1$，把"谁做"隐含进了"谁的弧进入 $j$"。

约束二：流守恒（进入某点必离开，保证路线连续）。 $$ \sum_{i\in V,\,i\neq h} x_{ih}^{k}=\sum_{j\in V,\,j\neq h} x_{hj}^{k},\qquad \forall h\in\mathcal{T}, \forall k\in\mathcal{R}. \tag{5.3} $$ 若机器人 $k$ 进了任务点 $h$，它必须从 $h$ 出去——否则路线断在 $h$。这保证每台机器人的弧串成连续路径。

约束三：每台机器人从 depot 出发、回 depot（路线闭合）。 $$ \sum_{j\in\mathcal{T}} x_{0j}^{k}\le 1,\qquad \sum_{i\in\mathcal{T}} x_{i0}^{k}=\sum_{j\in\mathcal{T}} x_{0j}^{k},\qquad \forall k\in\mathcal{R}. \tag{5.4} $$ 每台机器人最多用一次（$\le 1$ 允许它闲置不出动），出动则必返回。

约束四：子环消除 (Subtour Elimination) ——最关键也最麻烦的一条。

只有 (5.2)-(5.4) 还不够：它们允许出现脱离 depot 的孤立小环（subtour）——比如三个任务点 $i\to j\to l\to i$ 自己转圈、不连 depot，照样满足度约束和流守恒，但这不是一条合法路线（没有机器人能凭空在那个环上）。必须额外禁止子环。经典写法是 MTZ (Miller-Tucker-Zemlin) 约束，给每个任务点引入一个连续"位次"变量 $u_i\in[1,n]$： $$ u_i-u_j+n\sum_{k}x_{ij}^{k}\le n-1,\qquad \forall i,j\in\mathcal{T}, i\neq j. \tag{5.5} $$ 直觉：如果 $k$ 走了弧 $i\to j$（某个 $x_{ij}^k=1$），(5.5) 强制 $u_j\ge u_i+1$——访问位次严格递增，于是不可能绕回更小位次形成环。MTZ 的优点是约束数只有 $O(n^2)$；缺点是线性松弛较弱（求解慢）。另一种是 DFJ (Dantzig-Fulkerson-Johnson) 割： $$ \sum_{i\in S}\sum_{j\in S,\,j\neq i} x_{ij}^{k}\le |S|-1,\qquad \forall S\subseteq\mathcal{T}, |S|\ge 2, \forall k, \tag{5.6} $$ 对任意任务子集 $S$，内部弧数不超过 $|S|-1$（否则成环）。DFJ 松弛紧、但约束数 $O(2^n)$ 指数多，实务上按需添加（branch-and-cut：先不加，解出来发现子环再补对应的割）。

回顾 Multi 线《任务分配与路径规划》§3.4（CBS 的延迟约束）：CBS 也用"先不加约束、发现冲突再补"的思想——根节点无约束，检测到路径冲突才追加"某机器人某时刻不得占某格"。DFJ 的 branch-and-cut 与 CBS 的约束树异曲同工：都是"惰性地只加被违反的约束"，避免一次性写下指数多约束。区别在层次：DFJ 割禁的是图论子环（保证路线合法），CBS 约束禁的是时空冲突（保证多机无碰撞）。认出这个共同的"延迟约束生成"范式，你就理解了为什么 §7 的任务层冲突树和 §8 的 MAPF 冲突树在思想上同源——它们都是这个范式在不同层次的实例。

看一个"假最优解"长什么样（为什么必须有子环消除）。 设 5 个任务点 $1,2,3,4,5$ 和 depot $0$，单机器人。如果只写覆盖 (5.2) + 流守恒 (5.3)、漏掉子环消除，求解器可能返回这样一个解： $$ \underbrace{0\to1\to2\to0}{\text{合法回路}},\qquad \underbrace{3\to4\to5\to3}. $$ 检查一下：每个点都"进一次出一次"（满足流守恒），每个任务都被覆盖一次（满足 (5.2)），度约束全满足——}但 $3\to4\to5\to3$ 是一个脱离 depot 的孤立环，没有机器人能凭空在那个环上转。求解器却给它算了个很低的代价（因为它没被禁止），于是返回一个目标值低得离谱、物理上根本无法执行的"最优解"。

加上 DFJ 割就能禁掉它：对子集 $S=\{3,4,5\}$，约束 (5.6) 要求 $\sum_{i,j\in S}x_{ij}\le|S|-1=2$，但子环 $3\to4\to5\to3$ 用了 3 条内部弧（$x_{34}+x_{45}+x_{53}=3>2$），违反！branch-and-cut 检测到这个违反，补上这条针对 $S=\{3,4,5\}$ 的割，重解就排除了这个子环。MTZ (5.5) 则从一开始就用位次变量禁止：$3\to4$ 要求 $u_4\ge u_3+1$、$4\to5$ 要求 $u_5\ge u_4+1$、$5\to3$ 要求 $u_3\ge u_5+1$——三条相加得 $u_3+u_4+u_5\ge u_3+u_4+u_5+3$，即 $0\ge3$，矛盾，故这个子环在 MTZ 下根本不可行。这就是子环消除的作用：堵住"局部平衡但全局非法"的假解（§5 陷阱 5-1 正是栽在漏掉它）。

5.4 加容量：从 mTSP 到 CVRP¶

如果机器人一次只能装 $Q$ 件（电量/载重有限），每个任务 $j$ 有需求 $q_j$，就成了带容量的车辆路径问题 CVRP——把 MTZ 的位次变量换成"累计载量"变量 $u_j\in[q_j,Q]$： $$ u_i-u_j+Q\sum_k x_{ij}^k\le Q-q_j,\qquad \forall i,j\in\mathcal{T}, i\neq j, \tag{5.7} $$ 它同时消子环并强制每条路线累计需求不超过 $Q$。

回顾 T2 §9.3：T2 §9.3 已断言"带容量约束时这是 CVRP 实例，NP-hard"。(5.7) 就是那句话的模型实体——容量约束和子环消除被同一条不等式优雅地合并了。这也解释了为什么 T2 把容量当作 CVRP 的标志：它不是额外加一条简单上界，而是和路线结构（子环）耦合在一起。

5.5 规模为什么炸：变量计数与精确解的天花板¶

数一下变量规模就知道精确解的边界在哪：

量	数目	说明
流变量 $x_{ij}^k$	$O(n^2 m)$	每对节点 × 每台机器人
位次/载量变量 $u_i$	$O(n)$	每个任务一个
MTZ 约束	$O(n^2)$	每对任务一条
DFJ 割（若全展开）	$O(2^n m)$	每个子集每台机器人——故必须惰性

整数变量数 $O(n^2 m)$ 随任务数平方增长。MILP 是 NP-hard，分支定界最坏指数时间。经验天花板：用商业求解器（Gurobi/CPLEX）+ branch-and-cut，精确解 mTSP/CVRP 通常只能到几十个任务、个位数机器人；上百任务就要数小时甚至求不出。这就是 T2 §9.4 策略三"只适合中小规模"的定量含义。

把 $O(n^2m)$ 算成实数，天花板就很直观了（设 $m=3$ 台机器人）：

任务数 $n$	流变量数 $\approx n^2m$	MTZ 约束 $\approx n^2$	精确求解可行性
10	$\approx 300$	$\approx 100$	秒级求出最优 ✓
30	$\approx 2{,}700$	$\approx 900$	分钟级，仍可行 ✓
50	$\approx 7{,}500$	$\approx 2{,}500$	几分钟到数十分钟，临界 △
100	$\approx 30{,}000$	$\approx 10{,}000$	数小时～求不出 ✗
200	$\approx 120{,}000$	$\approx 40{,}000$	实际不可行 ✗✗

变量数本身只是平方增长（看着不吓人），但分支定界的搜索树随变量数指数膨胀——这才是真正的墙。$n=30$ 的几千变量求解器还能驾驭，$n=100$ 的三万变量搜索树就大到任何求解器都望而却步。这张表给了你一个实用的判断：任务数过 50 就要警惕、过 100 基本要放弃精确 MILP，转 §5.6 列生成或 §6 拍卖。

本质洞察：联合优化是"对的但贵的"——它正确地把三层耦合一次性求解、给出全局最优，但代价是组合爆炸，只能用于小规模。这印证了 §3.4 难度阶梯的代价律：越往难的级别走、越追求最优，付出的计算就越指数级增长。工程现实里，纯精确联合优化的适用面其实很窄（小车队、离线排程）；大规模场景几乎都要退到 §5.6 的分解或 §6 的分布式拍卖——用一点最优性换可扩展性。理解这一点，你就不会迷信"联合优化最好所以都用它"——它是金标准，但金标准往往太贵，工程是在金标准的阴影下做近似。

5.6 列生成：当弧变量太多时换个变量空间¶

当 $n,m$ 较大、(5.1) 直接求解不动时，运筹学的标准武器是列生成 (column generation) + 分支定价 (branch-and-price)。它换一个建模视角——不以"弧"为变量，而以"整条路线"为变量：

设 $\Omega$ 是所有可行路线（满足容量、闭合）的集合，每条路线 $r\in\Omega$ 有代价 $c_r$ 和"是否覆盖任务 $j$"的指示 $a_{jr}\in\{0,1\}$。引入变量 $\lambda_r\in\{0,1\}$（是否选用路线 $r$）： $$ \min_{\lambda} \sum_{r\in\Omega} c_r\lambda_r \quad\text{s.t.}\quad \sum_{r\in\Omega} a_{jr}\lambda_r=1 (\forall j),\quad \sum_{r\in\Omega}\lambda_r\le m. \tag{5.8} $$ 这是一个集合划分 (set partitioning) 模型——把任务集划分成若干条路线。问题是 $\Omega$ 指数大，不可能枚举所有列。列生成的妙处：只在需要时生成有用的列。 - 主问题 (Restricted Master)：只用 $\Omega$ 的一个小子集解 (5.8) 的线性松弛，得到约束的对偶价格 $\pi_j$（任务 $j$ 的"影子价格"）。 - 定价子问题 (Pricing)：找一条简约代价 (reduced cost) 为负的新路线——即 $c_r-\sum_j a_{jr}\pi_j<0$ 的 $r$。这本身是一个"带价格的最短路/ESPPRC"问题（在弧代价里减去对偶价格后找负代价回路），用动态规划解。 - 把找到的负简约代价列加入主问题，重解，迭代到再也找不到负简约代价列——此时线性松弛已最优。整数解再套分支（分支定价）。

把迭代过程画出来。 假设 3 个任务、初始只有"每个任务单独跑一条路"这 3 条平凡路线。列生成逐轮引入更好的合并路线：

轮	主问题里的列（路线）	解出的对偶价格 $\pi$	定价找到的新列（简约代价）	动作
0	$\{1\},\{2\},\{3\}$ 三条单任务路线	$\pi_1{=}4,\pi_2{=}4,\pi_3{=}9$	路线 $\{1,2\}$：$c{=}5.2$，简约代价 $5.2-4-4=-2.8<0$	加入 $\{1,2\}$
1	上 + $\{1,2\}$	$\pi_1{=}3,\pi_2{=}2.2,\pi_3{=}9$	路线 $\{1,2,3\}$：简约代价 $-1.5<0$	加入 $\{1,2,3\}$
2	上 + $\{1,2,3\}$	更新	定价：所有候选简约代价 $\ge 0$	停！线性松弛最优

每轮的逻辑：主问题解出"任务的影子价格"$\pi_j$（这个任务现在有多"贵"），定价子问题拿着 $\pi$ 去找"一条用了这些任务、但总代价低于影子价格之和"的新路线（简约代价为负 = 这条合并路线比当前拆开做更划算）。找到就加入、重解；找不到（所有简约代价 $\ge 0$）就说明当前路线组合已是线性最优。注意它从不枚举所有路线——3 个任务的所有路线有指数多条，列生成只碰了 5 条（3 初始 + 2 生成）就收敛了。这就是"惰性加变量"省下的指数代价。

本质洞察：列生成的思想内核，和 §5.3 的 DFJ 惰性割、Multi 线 CBS 的延迟约束是同一枚硬币的两面——DFJ 惰性地加约束（行），列生成惰性地加变量（列）。两者都拒绝"一次性写下指数多东西"，改为"只在它被需要（被违反 / 有改进潜力）时才引入"。这是处理指数规模组合问题的通用智慧：不要构造整个庞大问题，而是从一个小问题出发，让求解过程告诉你还缺哪一行或哪一列。掌握了这个元思想，你看 CBS、看 DFJ、看列生成，就看到的是同一种应对爆炸的策略，只是作用在约束侧还是变量侧的差别。

5.7 小结：联合优化在多机 TAMP 里的定位¶

联合优化（MILP/CVRP/列生成）回答的是 §3.4 难度阶梯第 3 级 XD 的"集中式最优解"。它的位置：

联合优化在本章方法谱里的位置:
  ID(顺路)     ──→ 边际出价/CBBA(§6) 够用, 联合是 overkill
  XD(避让), 小规模 ──→ 联合 MILP(本节) 给全局最优 ✓ 适用区
  XD(避让), 大规模 ──→ 列生成/分支定价(§5.6) 或退到分布式拍卖(§6)
  CD(协作+分解)    ──→ 联合 MILP 难以编码"任务怎么拆", 需时序逻辑(§9)

它的强项是全局最优 + 显式处理 XD，弱项是规模受限 + 难表达 CD/时序。下一节转向它的对立面——分布式拍卖，用最优性换可扩展性和鲁棒性。

⚠️ 常见陷阱¶

陷阱 5-1（编程陷阱）：写 mTSP 的 MILP 时忘了子环消除约束。 - 错误描述：只写了目标 (5.1)、覆盖 (5.2)、流守恒 (5.3)，就提交求解。 - 现象/后果：求解器返回一个"最优解"，目标值低得离谱——因为它包含了脱离 depot 的孤立子环（几个任务点自己转圈），这些环代价小但物理上不可执行。把解画出来才发现路线断成几截。 - 根本原因：度约束和流守恒只保证"每点进出平衡"，不保证"所有路线都连到 depot"。子环满足局部平衡却全局非法，必须用 MTZ (5.5) 或 DFJ (5.6) 显式禁止。 - 正确做法：小规模直接加 MTZ（$O(n^2)$ 条，一次写全）；大规模用 DFJ + branch-and-cut（惰性加割）。自检：把求解结果按机器人画出弧，确认每条弧链都从 0 出、回 0，无孤立环。

陷阱 5-2（思维陷阱）：以为 MILP 求解器"万能"，规模再大也能等出来。 - 错误描述：认为只要建好 MILP，丢给 Gurobi 多等等总能出最优解。 - 现象/后果：上百任务的实例跑几小时不收敛，或内存爆掉；项目 deadline 到了还没有可用方案。 - 根本原因：MILP 是 NP-hard，分支定界最坏指数时间。$O(n^2 m)$ 整数变量在上百任务时的搜索树规模超出任何求解器的实际能力。 - 正确做法：精确 MILP 只用于中小规模（几十任务）。预判规模超限时，提前转列生成（§5.6）、滚动时域（只优化近期一段，T2 §9.4 提的 rolling horizon），或干脆用 §6 的分布式拍卖拿"足够好"的解。给求解器设 MIP gap 容差和时限，拿有界次优解而非死等最优。

陷阱 5-3（概念误区）：把 MTZ 和 DFJ 当成"二选一的等价写法"。 - 错误描述：认为 MTZ 和 DFJ 只是子环消除的两种风格，效果一样，随便选。 - 现象/后果：在大实例上用了 MTZ，线性松弛太松，分支定界展开海量节点，慢得无法接受；本可用 DFJ 割大幅加速。 - 根本原因：两者数学等价（都禁子环）但松弛强度不同。MTZ 紧凑（$O(n^2)$ 约束）但线性松弛弱；DFJ 松弛紧（接近整数凸包）但约束指数多需惰性。强度差异直接决定分支定界的效率。 - 正确做法：小规模/快速原型用 MTZ（写起来简单）；追求性能的大实例用 DFJ + branch-and-cut（借强松弛剪枝）。理解"约束数 vs 松弛强度"的权衡，按规模选，而非随意。

练习¶

（⭐⭐⭐，建模） 把 §4 练习 1 的 2 机器人 4 包裹场景写成完整 MILP：列出所有 $x_{ij}^k$ 变量、目标 (5.1)、约束 (5.2)-(5.5)。手工或用 PuLP 求解，验证它给出的最优分配与你 §4 手算的一致。
（⭐⭐⭐，分析） 对 $n=20$ 任务、$m=3$ 机器人，计算流变量 $x_{ij}^k$ 的总数、MTZ 约束数、若全展开 DFJ 割的数量级。据此论证为什么 $n=20$ 还能精确解、$n=200$ 就不行。
（⭐⭐⭐⭐，综合，跨 §5-§6） 列生成的定价子问题要找"简约代价为负的路线"。解释这一步如何把规划信息注入分配——对偶价格 $\pi_j$ 扮演了什么角色？它和 §6 拍卖里任务的"出价/价格"在概念上如何对应？通过这个对应说明"列生成"和"拍卖"其实是同一思想（按价格组织路线选择）的集中式与分布式两种实现。

6. 市场/拍卖机制深化：从 SSI 到 CBBA 的分布式联合 ⭐⭐⭐¶

6.1 动机：当集中式 MILP 太贵、又没有中央黑板¶

§5 的联合优化给出全局最优，但有两个致命限制：规模一大就求不出（§5.5），而且它假设有一个中央节点掌握全局信息、统一求解。真实多机系统常常两条都不满足——几十上百台机器人、通信带宽有限、没有可靠的中央协调器（中央一旦宕机全系统瘫痪）。这时需要一种分布式方法：每台机器人只和邻居通信、本地决策，却能涌现出全局协调的分配。这就是市场/拍卖机制。

T2 §8 已经教过拍卖的基础（SSI、CBBA 流程），Multi 线《任务分配与路径规划》§3.2 给了 CBBA 的完整算法与 50% 界证明。本节不重复这些，而是做两件 TAMP 视角下的深化：（1）讲清 DMG（递减边际收益）为什么是拍卖收敛的前提、它和 §4 的 ID 顺路如何呼应；（2）讲清如何把真实路径规划器嵌进出价，让分布式拍卖也能处理多机 TAMP 的 ID 耦合——这正是 T2 §9.4 策略二的分布式版本。

6.2 回顾与定位：SSI 和 CBBA 在本章的角色¶

回顾 T2 §8.3（序贯单物品拍卖 SSI）：SSI 一轮拍一个任务——每台机器人对当前待拍任务出价，出价 = 把它插入自己已中标路线的边际代价 $\Delta c_k(\tau_j\mid S_k)$（§4.2 的那个边际函数），出价最低者中标，更新它的路线，再拍下一个。SSI 用边际出价天然处理 ID 顺路，但它是集中式的（需要一个拍卖商收集出价、判定中标）。

回顾 T2 §8.5 / Multi 线《任务分配与路径规划》§3.2（CBBA）：CBBA = 捆绑拍卖的"出价" + 分布式共识的"定标"。两阶段交替——捆绑构建（每台机器人本地贪心，按边际收益把任务塞进自己的 bundle 和 path，直到无正收益任务可加）+ 冲突消解（机器人间用带时间戳的最大值共识交换"每个任务的最高出价者"，发现被人出价更高就释放该任务及其之后建包的任务）。CBBA 去掉了中央拍卖商，真正分布式。

把它们放进本章的难度阶梯：SSI/CBBA 是第 2 级 ID 的主力解法——它们用边际出价处理顺路，但（如 §4.3 所示）处理不了 XD 的 $\xi_{-k}$ 耦合项。本节要把它们用到多机 TAMP 上，关键是让"边际出价"里的代价是真实路线代价而非直线距离。

6.3 DMG 为什么是收敛的前提：和 ID 的深层呼应¶

CBBA 的收敛性与 50% 最优界，都依赖得分函数满足递减边际收益 (Diminishing Marginal Gain, DMG)——多拿一个任务带来的边际增益，不随已有捆绑变大而增大。形式化：设 $S_k$ 是机器人 $k$ 当前捆绑，得分函数 $f_k$ 满足 DMG 当且仅当对任意 $S\subseteq S'$ 和任意任务 $\tau$， $$ f_k(S\cup{\tau})-f_k(S) \ge f_k(S'\cup{\tau})-f_k(S'). \tag{6.1} $$ 即"任务 $\tau$ 加到更小的集合里，边际增益不小于加到更大的集合里"。这正是子模性 (submodularity) 的定义。

回顾 Multi 线《任务分配与路径规划》§3.2/§3.6（DMG 与子模、50% 界）：Multi 线证过——CBBA 在 DMG 下收敛于 $O(n_t D)$ 轮通信（$D$ 是通信图直径），且对子模值函数，序贯贪婪达全局最优的 50%（最坏界）。Multi 线 §3.6 还演示了违反子模（如"目标需 $\ge 2$ 台同时覆盖才得分"导致边际递增）时，贪婪 1−1/e 界失效。

为什么 DMG 是前提？因为 CBBA 的捆绑构建是贪心的——每台机器人独立地按边际收益加任务。贪心要正确（不至于贪过头互相打架到不收敛），需要边际收益"越加越少"，这样任务的吸引力有个递减的天花板，共识才能稳定地把每个任务判给唯一的最高出价者。若边际收益递增（超可加，如协作任务"凑齐才值钱"），贪心会鼓励机器人疯狂囤积、互相哄抢，共识震荡不收敛。

本质洞察：DMG 不是一个技术性的数学假设，它精确对应了 §4 的 ID 耦合结构。ID 顺路天然满足 DMG——当机器人路线上的任务越来越多，新插入一个任务的边际绕路代价（负的边际收益）只会越来越大（路线越满越难顺路插入），等价于边际收益递减。这就是为什么拍卖（CBBA）和 ID 是天作之合：ID 的物理结构（顺路的边际递减）恰好提供了拍卖收敛所需的 DMG。反过来，CBBA 处理不了 CD 协作任务，根子也在 DMG——协作任务"凑齐才值钱"是超可加（边际递增），直接违反 DMG，所以 §3 难度阶梯第 4 级 CD 必须跳出拍卖、走 §9 时序逻辑。DMG 把"什么问题适合拍卖"这件事，从经验判断变成了可验证的数学条件：检查你的得分函数是不是子模的，就知道 CBBA 会不会收敛。

一个能手算的 DMG 验证。 把上面的洞察落到数字上。设机器人 $k$ 完成任务集 $S$ 的得分 $f_k(S)=\text{(总收益)}-\text{(路线长度)}$。先看一个满足 DMG（覆盖型收益）的例子——每个任务完成得 $+10$ 收益，任务点在 §4.2 的坐标 $p_1=(2,0),p_2=(2,1),p_3=(8,0)$，depot 在原点：

取 $S=\{p_1\}$，$S'=\{p_1,p_2\}$（注意 $S\subseteq S'$），考察加入 $p_3$ 的边际增益： $$ \begin{aligned} f_k(S\cup{p_3})-f_k(S)&=\big(20-\mathrm{route}({p_1,p_3})\big)-\big(10-\mathrm{route}({p_1})\big)=10-(16-4)=-2,\ f_k(S'\cup{p_3})-f_k(S')&=\big(30-\mathrm{route}({p_1,p_2,p_3})\big)-\big(20-\mathrm{route}({p_1,p_2})\big)=10-(17.24-5.24)=-2. \end{aligned} $$ 这里 $\mathrm{route}(\{p_1,p_2,p_3\})\approx D\to p_2\to p_1\to p_3\to D=1+\sqrt5+6+8\approx 17.24$。两个边际相等（都是 $-2$），满足 DMG 式 (6.1) 的 $\ge$（恰好取等）——更一般地，路线越满，加 $p_3$ 的边际绕路只会更大、边际增益只会更小，DMG 成立。

再看一个违反 DMG（协作型收益）的例子：规定"$p_1,p_2$ 必须由同一机器人都完成才各得 $+10$，否则得 $0$"。则 $$ f_k({p_1})-f_k(\varnothing)=0-4=-4 \text{(只做 }p_1\text{ 不凑齐, 收益 }0\text{)},\qquad f_k({p_1,p_2})-f_k({p_1})=20-1.24-0=+18.76. $$ 加 $p_2$ 到更大集合 $\{p_1\}$ 的边际（$+18.76$）远大于加 $p_1$ 到更小集合 $\varnothing$ 的边际（$-4$）——边际递增，直接违反 DMG。这正是协作任务"凑齐才值钱"的超可加性，CBBA 在这种得分上会震荡不收敛。你只需算这两个边际、比一下大小，就能预判 CBBA 行不行——这就是把 DMG 从抽象条件变成手算检查的方法。

6.4 把路径规划器嵌进出价：分布式处理 ID¶

现在做本节的核心：让 CBBA 处理多机 TAMP 的 ID。朴素 CBBA 的出价常用直线距离——但 §4 陷阱 4-1 已说明这系统性失真。改法是把出价里的"边际代价"换成真实路线规划器算出的边际：

TAMP 感知的 CBBA 捆绑构建(每台机器人本地):
  while 还有任务可加:
    for 每个未在我 bundle 里的候选任务 τ:
      # 关键: 用真实路线规划器算边际, 而非直线距离
      Δ(τ) = route_plan(my_path ∪ {τ}) - route_plan(my_path)
             ↑ 调用 §4.4 的廉价插入启发, 必要时精算避障路径
    选边际收益最大(Δ 最小)的 τ*, 加入 bundle 和 path
  # 之后进入共识阶段, 与邻居消解冲突(与朴素 CBBA 相同)

其中 route_plan 是真实的路线规划器（含避障的最短路），而非 dist(a,b) 直线。

回顾 T2 §9.4 策略二与 Multi 线 §3.1（route_length）：T2 §9.4 策略二就是"把规划嵌进分配的代价计算"，并引用了"把路径规划器集成进拍卖阶段的奖励计算，考虑实际避障行驶距离而非理想直线距离"。本节的 TAMP 感知 CBBA 正是这条策略的分布式落地——每台机器人在本地捆绑构建时调用自己的路线规划器，把 ID 顺路的真实边际算进出价。

这样改之后，CBBA 在保持分布式、可扩展的同时，出价反映了真实顺路代价——ID 耦合被正确处理。但它仍处理不了 XD：每台机器人的 route_plan 只看自己一台，算不出"别人会不会堵我的路"（$\xi_{-k}$ 耦合项）。XD 仍需 §8 的执行层 MAPF 协调或 §5 的联合优化。这与 §4 练习 3 的结论一致。

6.5 共识阶段怎么"擦掉被抢的任务"：一个三机器人走查¶

CBBA 的捆绑构建好理解（本地贪心加任务），共识阶段对初学者最绕。这里走一遍，让你看清"擦除"机制。设三台机器人 $R_1,R_2,R_3$ 在一条链上通信（$R_1$–$R_2$–$R_3$，$R_1$ 和 $R_3$ 不直接通信，直径 $D=2$）。每台维护一张表：对每个任务，记"我所知的最高出价者 + 出价值"。

CBBA 共识走查(任务 τ 被 R1 和 R3 都想要):
  初始(各自捆绑构建后, 本地视角):
    R1 的表: τ → (赢家=R1, 价=8)      ← R1 出价 8, 自认为赢
    R2 的表: τ → (赢家=空, 价=0)      ← R2 没要 τ
    R3 的表: τ → (赢家=R3, 价=5)      ← R3 出价 5, 也自认为赢
       ↑ 冲突! R1、R3 都以为自己赢了 τ (因为没直接通信, 互不知道)

  共识第 1 轮(邻居交换, 取每个任务的最高出价):
    R2 收到 R1 的 (R1,8) 和 R3 的 (R3,5) → R2 表更新为 (R1,8)  [8>5, R1 赢]
    R1 收到 R2 的(此时还是旧的) → 暂不变
    R3 收到 R2 的(旧的) → 暂不变

  共识第 2 轮(信息再传一跳, 因为直径=2):
    R3 收到 R2 的 (R1,8) → 发现 τ 的真正赢家是 R1(8>自己的5)
       → R3 "擦除" τ: 从自己捆绑里释放 τ, 以及在 τ 之后建包的所有任务
         (因为那些任务的边际收益是基于"我有 τ"算的, τ 没了它们也得重算)
    R1 收到 R2 确认自己仍是赢家 → 保留 τ

  收敛: 全网对"τ 归 R1"达成一致, 共 D=2 轮(印证 O(n_t·D))

注意两个关键点：(1) 擦除是连锁的——$R_3$ 丢了 $\tau$，它在 $\tau$ 之后建包的任务也要一起释放（因为那些任务的边际是"假设我有 $\tau$"算的，前提没了得重算），这保证了捆绑的内部一致性；(2) 收敛轮数 = 通信图直径 $D$——信息从 $R_1$ 传到 $R_3$ 要 2 跳，所以 2 轮才收敛，这正是 Multi 线证的 $O(n_t D)$。

本质洞察：CBBA 共识的精髓是"用局部通信达成全局一致，无需中央拍卖商"。没有任何一个节点掌握全局——$R_1$ 一开始根本不知道 $R_3$ 也想要 $\tau$。是"取最高出价"这条简单规则 + 沿通信图逐跳传播，让冲突在 $D$ 轮内自然消解。这就是 §6.1 说的"自由市场"——每个参与者只看局部、按统一规则（高价者得）行事，全局协调自动涌现。 而"连锁擦除"保证了即使中途释放任务，每台机器人的捆绑始终是基于一致信息的——这是 CBBA 既分布式又能收敛到无冲突的关键工程细节。理解了这个走查，你就懂了为什么 CBBA 的收敛速度取决于通信图直径（信息传播的跳数），以及为什么稀疏通信图（大直径）会拖慢收敛。

6.6 拍卖 vs 集中式 MILP：四维取舍¶

把分布式拍卖（§6）和集中式联合优化（§5）正面对比，这是多机 TAMP 选型的核心决策：

维度	集中式 MILP（§5）	分布式拍卖 CBBA（§6）
最优性	全局最优（小规模）	50% 界（子模时），一般次优
可扩展性	差（$O(n^2m)$ 变量，几十任务封顶）	好（本地贪心 + 共识，可上百台）
通信	需中央汇聚全局信息	只需邻居通信，收敛 $O(n_t D)$ 轮
鲁棒性	中央单点故障全瘫	去中心化，单机失效可重分（动态拍卖）
耦合处理	ID + XD（显式建模避让）	ID（边际出价），XD 需外挂 MAPF
适用	小车队、离线、要最优	大车队、在线、抗扰、可接受次优

本质洞察：集中式和分布式不是"谁更好"，而是在最优性 ↔ 可扩展性/鲁棒性这条轴上的两端。集中式 MILP 像一个无所不知的总调度——掌握全局、算出最优，但慢且脆（中央一倒全完）。分布式拍卖像一个自由市场——每个参与者只看局部、按价格自利决策，涌现出全局协调，快且韧（个体失效不影响整体），但放弃了全局最优（只到 50% 界）。这正是 §5.5 那句"工程是在金标准的阴影下做近似"的具体化：MILP 是金标准，CBBA 是为现实（规模、通信、故障）做的妥协。一个成熟的多机 TAMP 系统，往往是两者的混合——小范围用 MILP 求局部最优，大范围用拍卖做粗分配，再用 §5.6 列生成在两者间架桥（§5 练习 3 已点破列生成 = 拍卖的集中式版本）。

混合架构怎么搭，怎么选。 实务中"集中 or 分布"很少是非此即彼，常见的是分层混合 + 一个简单的选型判断：

分配方法选型(给定规模、通信、最优性要求):
│
├─ 规模小(≤ 几十任务) 且 有可靠中央节点 且 要最优?
│   └─ 是 → 集中式 MILP(§5), 拿全局最优
│
├─ 规模大 或 无可靠中央 或 要抗单点故障?
│   └─ 是 → 分布式 CBBA(§6), 接受 50% 界换可扩展+鲁棒
│
└─ 规模中等、又想要好质量又怕中央太脆?
    └─ 混合: 把机器人分组(geographic clustering),
            组内用 MILP 求局部最优(小规模, 能算),
            组间用 CBBA 做粗协调(分布式, 抗扰),
            边界任务用列生成在组间重分配(§5.6)

混合架构的逻辑：把问题按地理/功能分组，组内小规模用集中式拿质量、组间大规模用分布式拿扩展性。比如一个跨三个车间的多机系统，每个车间内十几台机器人用 MILP 排得最优，三个车间之间用 CBBA 协调（车间是分布式节点），跨车间的边界任务用列生成动态再分配。这样既避免了"全局 MILP 跑不动"、又避免了"全局 CBBA 质量太差"，是规模和质量的折中。

本质洞察：混合架构印证了一个工程通则——没有哪个单一方法在所有"规模 × 通信 × 最优性"象限都最优，成熟系统是按问题结构把不同方法拼起来。这和 §7.7"集中式何时仍是对的"是同一智慧：方法选择要匹配问题的局部结构，而真实问题往往是"局部稠密（适合集中）+ 全局稀疏（适合分布）"的混合，所以最佳方案也是混合的。学会按'规模 × 耦合 × 通信'象限给问题的不同部分配不同方法，是多机 TAMP 系统架构师区别于'只会一个算法'的工程师的核心能力。

⚠️ 常见陷阱¶

陷阱 6-1（思维陷阱）：不验证 DMG 就用 CBBA，遇到协作任务还纳闷为什么不收敛。 - 错误描述：把任何多机分配都套 CBBA，不检查得分函数是否子模。 - 现象/后果：在含协作任务（超可加效用，凑齐才值钱）的问题上，CBBA 共识阶段震荡、不收敛，或收敛到很差的解。 - 根本原因：CBBA 的收敛性与 50% 界依赖 DMG（子模）。协作任务的"凑齐才值钱"是边际递增（违反 DMG），贪心 + 共识失去理论保证（Multi 线 §3.6 演示过）。 - 正确做法：用 CBBA 前先验证得分函数子模（检查式 (6.1) 是否成立，或确认任务效用可加/递减）。含协作任务（CD）时改用 §9 的时序逻辑方法或专门的联盟形成算法，别硬套 CBBA。

陷阱 6-2（编程陷阱）：CBBA 出价用直线距离，部署后实际里程暴涨。 - 错误描述：实现 CBBA 时图快，出价里的边际代价用 dist(robot, task) 直线距离。 - 现象/后果：仿真里收敛得很漂亮，实机部署后总行驶里程比预期高三四成——因为直线距离忽略了避障绕路和顺路便宜（§4 陷阱 4-1 的 CBBA 版本）。 - 根本原因：直线距离是 ND 假设，而真实问题是 ID。出价失真导致"看似最优"的分配其实很差。 - 正确做法：出价用真实路线规划器算边际（§6.4 的 TAMP 感知 CBBA）。性能上配合廉价插入启发（§4 陷阱 4-3）和惰性精算，避免每次出价都跑完整 TSP。

陷阱 6-3（概念误区）：以为分布式拍卖"消除"了对规划的依赖。 - 错误描述：认为既然 CBBA 分布式、各机器人本地决策，就不需要规划信息了，纯靠通信就能分好。 - 现象/后果：分配在通信层面达成一致、无冲突，但执行时代价远超预期或路线打架。 - 根本原因：分布式说的是"决策的组织方式"（去中心化），不等于"不需要规划信息"。出价的质量仍取决于本地路线规划的真实性（ID），而 XD 根本没被 CBBA 触及。 - 正确做法：分布式不等于免规划。本地出价要嵌真实规划器处理 ID（§6.4）；XD 仍要在执行层用 MAPF 协调（§8）。CBBA 解决的是"谁做什么"的分布式裁决，不是"路线对不对"。这里再强调一次：去中心化只改变了"决策在哪里发生"，不改变"决策需要什么信息"——规划信息（自己的真实路线）始终是出价质量的来源，分布式只是把"用这些信息做决策"这件事从中央挪到了各机器人本地。

练习¶

（⭐⭐⭐，验证） 给定三个任务，机器人 $k$ 的得分函数定义为"完成任务集 $S$ 的总收益减去最优路线长度"。构造具体数值，验证当收益可加时式 (6.1) 的 DMG 成立；再把收益改成"协作型"（任务 1、2 必须同一机器人都做才各得 10，否则得 0），验证 DMG 被违反。说明后者为什么会让 CBBA 不收敛。
（⭐⭐⭐，实现） 在 T2 §8.6 的 SSI 代码或 Multi 线 §3.2 的 CBBA 代码基础上，把出价函数从直线距离改为"廉价插入边际"（固定当前路线、试新任务插在哪两点间最省）。在一个 3 机器人 9 任务实例上对比改前改后的总里程，量化 ID 处理带来的改进。
（⭐⭐⭐⭐，对比，跨 §5-§6） 同一个 5 机器人 15 任务实例，分别用 §5 的 MILP（设 5 分钟时限，记录 MIP gap）和 §6 的 CBBA 求解。对比：解质量（总代价）、求解时间、以及"如果中途一台机器人失效"各自如何恢复。据此论证 §6.6 取舍表里"鲁棒性"那一行。

7. 分布式多机 TAMP：去中心化架构与异步精化 ⭐⭐⭐⭐¶

7.1 动机：从"分配"前沿到"分配 + 几何"前沿¶

§5（集中式 MILP）和 §6（分布式拍卖）解决的主要是分配-排序-路由层面的耦合——它们把任务当作"有地点的活"，代价是行驶距离。但真正的多机 TAMP 还有一层 §5/§6 没正面碰的硬骨头：几何精化 (geometric refinement)——每个动作的抓取位姿、放置位置、无碰撞轨迹，而且多台机器人在近距离同一工作空间里操作时，这些几何量互相约束（$R_1$ 把物体放哪，决定 $R_2$ 的臂能否伸进去）。这是单机 TAMP（T3/T4）的核心难题，乘上多机后变成本节的主题。

这一节走到多机 TAMP 的研究前沿，回答："当几何精化也必须多机联合时，架构该怎么搭？"我们先给架构谱系（集中/分布/去中心），再讲三类近年（2022-2024）的代表性方法——异步精化、超图分解、冲突基 TAMP，并说清它们各自牺牲了什么、换来了什么。

7.2 架构谱系：集中式 / 分布式 / 去中心化¶

多机 TAMP 的架构按"决策权在哪"分三档，这是 §6.6 取舍的推广：

架构	决策权	几何精化怎么做	优点	代价	代表
集中式 (centralized)	单一规划器掌握全局	一个 TAMP 求解器为所有机器人联合精化	全局最优、显式处理所有耦合	规模差、单点故障、状态空间随机器人指数膨胀	联合 LGP/PDDLStream 扩展
分布式 (distributed)	多个规划器协作、共享部分信息	各机器人本地精化 + 协调约束/共识	可扩展、容错、并行	协调开销、可能次优、需消解冲突	异步精化、CBBA+本地 TAMP
去中心化 (decentralized)	完全自主，仅局部交互	每台机器人独立精化，碰撞时反应式避让	最强扩展性与鲁棒性	几乎无全局保证、易死锁	反应式 + 优先级

回顾 T2 总论 §3.7 / 本章 §6.6：集中-分布的取舍轴（最优性 ↔ 可扩展性/鲁棒性）在 §6.6 已就分配层讲过。本节把它推广到几何精化层——同一条轴，但纠缠的量从"任务清单"升级到"抓取位姿、轨迹、时空占用"。轴的两端取舍逻辑相同，只是赌注更大（几何耦合比分配耦合更难事后修复）。

本质洞察：架构选择的本质，是在"状态空间爆炸"和"协调复杂度"之间转移负担。集中式把所有机器人的构型空间做笛卡尔积——状态空间随机器人数指数膨胀（$d$ 维单机 × $m$ 台 = $dm$ 维联合空间），但一旦能搜就给最优。分布式把这个巨型空间切成每台机器人的小空间分别搜，避免了指数膨胀，代价是要额外处理"切开后如何保证拼起来不冲突"的协调复杂度。没有免费的午餐：耦合的难度守恒，你要么在集中式里以状态空间爆炸的形式付，要么在分布式里以协调复杂度的形式付。 近年前沿方法（§7.3-§7.5）的全部创新，本质都是在找"更聪明的切分方式"，让协调复杂度尽可能小——超图分解切得巧（§7.4），异步精化协调得省（§7.3），冲突基只在冲突处才协调（§7.5）。

7.3 异步任务计划精化：摆脱预离散化与同步假设¶

第一类前沿方法针对集中式 TAMP 的两个隐藏简化。集中式多机 TAMP 为了可解，常做两个假设：预离散化时间（把时间切成固定步长，所有机器人同步推进）和同步动作（所有机器人在每个"回合"同时开始/结束动作）。这两个假设让问题好写，却严重削减了可行解空间——现实里机器人动作时长不一（抓一个小件 1 秒、搬一个大件 5 秒），强行同步会浪费大量时间（快的等慢的）。

核心方法（Sung, Shome & Stone, 2024, ICRA，"Asynchronous Task Plan Refinement for Multi-Robot Task and Motion Planning"）：该工作把"给定任务计划、求各变量（轨迹）的有效赋值"这一精化问题，建模为一个混合约束满足问题 (hybrid CSP)。它的两个关键创新——隐式时间与 roadmap 表示（不预先把时间离散成固定步长、不预建固定 roadmap，而是按需生成），以及最小必要的协调诱导约束（只在机器人真正会冲突的地方引入协调约束，不做"全程同步"这种过度简化）。结果：异步方案在 makespan（总完工时间）上优于同步方案——因为它不再强迫快机器人空等慢机器人。

把异步的价值用一句话说清：

同步 vs 异步(三机器人, 动作时长不同):
  同步(预离散+同步假设):
    回合1: R1[抓小件1s] R2[搬大件5s] R3[移动3s]  → 整回合耗时 = max = 5s (R1,R3 空等)
    回合2: ...                                    → 每回合都被最慢的拖累
  异步(隐式时间+按需协调):
    R1 做完小件立刻去做下一个, 不等 R2  → 时间轴上各自推进
    仅在 R1、R2 真要用同一空间时才插入协调约束  → makespan 显著缩短

本质洞察：异步精化的洞察是"协调应该是按需的，不是默认的"。预离散化 + 同步假设，本质是"默认所有机器人时时刻刻都要协调"——用全局时钟把所有人锁在一起。但绝大多数时刻机器人之间根本不干扰（各在各的角落干活），强行同步是把"偶尔需要的协调"误当成"时时需要的协调"，白白浪费。异步方法把协调约束惰性化——只在真冲突处引入。这与 §5.3 的 DFJ 惰性割、§5.6 的列生成、Multi 线 CBS 的延迟约束是同一个元思想在时间维的体现：不要默认构造全部约束（全程同步），只在被需要时引入（真冲突时协调）。"惰性/按需"是贯穿本章所有可扩展方法的统一密码——从约束生成到变量生成到时间协调，无一例外。

7.4 超图分解：把联合空间切成线性增长的块¶

第二类前沿针对状态空间爆炸。§7.2 说集中式的联合构型空间随机器人/物体数指数膨胀。超图分解的思路：不在巨型联合空间里搜，而是把规划空间分解成若干"模式"的块，用超图组织它们之间的转移。

核心方法（Motes, Chen, Bretl, Morales & Amato (2023, IEEE T-RO), "Hypergraph-based Multi-Robot Task and Motion Planning"；后续 DaSH 系列）：把规划空间分解为三类元素——单独的机械臂（manipulator alone）、单独的物体（object）、机械臂持有物体（manipulator holding object）。用一张超图 (hypergraph) 组织：顶点是这些分解后的子空间，超弧 (hyperarc) 是子空间之间的转移（如"机械臂抓起物体" = 从"臂 + 物体"两个顶点转移到"臂持物体"一个顶点）。关键收益在规模——超图顶点数随机器人数或物体数线性增长、超弧数随机器人数二次/物体数线性增长，而朴素图表示是随机器人和物体数指数增长。后续 Lazy-DaSH（2024）用惰性思想进一步把规模翻倍、求解快三个数量级。

为什么分解能避免指数爆炸？因为大部分时间机器人和物体是解耦的（臂没抓物体时，臂的运动和物体无关）——只有"抓 / 放"的瞬间才耦合。超图显式地把"解耦态"和"耦合态"分开表示，只在耦合态（持物）付高维代价，解耦态用低维子空间，于是总规模线性而非指数。

一个具体的超图走查。 设两台臂 $A_1,A_2$ 要重排两个物体 $o_1,o_2$。朴素联合表示是 $A_1,A_2,o_1,o_2$ 全部状态的笛卡尔积——随物体/臂数指数膨胀。超图把它拆成下面这些顶点和超弧：

超图分解(2 臂 2 物体, 部分):
  顶点(子空间):
    [A1]       [A2]              单独的臂(臂可自由动, 与物体无关)
    [o1]       [o2]              单独的物体(物体静止在某处)
    [A1·o1] [A1·o2] [A2·o1] [A2·o2]   臂持物体(耦合态, 高维)
  超弧(转移):
    抓取: {[A1],[o1]} ──pick──→ [A1·o1]   (两个解耦顶点 → 一个耦合顶点)
    放置: [A1·o1] ──place──→ {[A1],[o1@新位置]}  (耦合顶点 → 两个解耦顶点)
    移动: [A1] ──move──→ [A1]              (臂自己动, 留在解耦态, 低维)

数一下规模就看出妙处：顶点里"单独的臂/物体"有 $2+2=4$ 个（线性），"臂持物体"有 $2\times2=4$ 个（臂数 × 物体数）——总顶点数随臂/物体数线性/双线性，而非笛卡尔积的指数。规划就是在这张超图上找一条从初始布局到目标布局的超路径——大部分走在低维的"单独臂/物体"顶点（解耦态），只在抓/放的超弧处短暂进入高维"臂持物体"顶点（耦合态）。这就是"只为耦合付代价"的字面实现：高维只在抓/放那一瞬出现。

本质洞察：超图分解的精髓是"按耦合度组织状态空间"——把"何时耦合、何时解耦"显式编码进表示。朴素联合规划把所有机器人和物体永远绑在一个巨型空间里（假装时时耦合），超图则识别出"绝大多数时刻是解耦的"，只在真正耦合的转移（抓/放）处付高维代价。这和 §7.3 异步精化"协调按需"是同一智慧的空间版：异步在时间维只在冲突处协调，超图在状态维只在耦合处升维。两者合起来给出一条多机 TAMP 可扩展的总原则——识别并利用问题中的解耦结构，只为真正的耦合付代价。这也回扣 §3.4 难度阶梯：耦合度（iTax 级别）越低的部分，就该用越低维、越解耦的表示去处理，把昂贵的联合求解留给真正高耦合的局部。

7.5 冲突基 TAMP：把 CBS 的思想搬到任务层¶

第三类前沿把 Multi 线的 CBS 思想从"路径层"提升到"任务+运动层"。

回顾 Multi 线《任务分配与路径规划》§3.4（CBS）：CBS 两层——高层约束树（检测路径冲突、分裂、对冲突一方加"某时刻不得占某格"约束），低层带约束的单体 A*。它的最优性来自"对每个冲突，两种消解都展开为子节点"，可扩展性来自"只重规划被约束的那台机器人"。

核心方法（"Conflict-Based Task and Motion Planning for Multi-Robot, Multi-Goal Problems," 2024, ICRA）：把 CBS 的"检测冲突 → 加约束 → 重规划单体"循环，用到多机多目标 TAMP 上——每台机器人先独立解自己的单机 TAMP（忽略他人），高层检测机器人间的冲突（不只是路径碰撞，还包括操作冲突——比如两台同时想用一个工作面、或一台的放置挡了另一台的取放），对冲突加约束，只重新精化被约束的那台机器人的 TAMP。这把 CBS 的"分而治之 + 冲突驱动协调"从纯路径推广到含几何操作的 TAMP。另一条相关线（Bhattacharya, Kumar, Likhachev 等）则增量地一次调一台机器人的路径以匹配任务约束，逐步增加违约代价直到收敛到最优——同样是"一次只动一台、冲突驱动"的精神。

本质洞察：冲突基 TAMP 揭示了一个统一框架——"独立求解 + 冲突驱动协调"是多机问题的通用范式，无论在哪个层次。Multi 线把它用在路径（CBS），本节把它用在 TAMP（冲突基 TAMP），§8 还会把它用在时序（时空冲突树）。这个范式的威力在于它自动地、最小地引入协调：先让每台机器人各自最优（独立求解，这步并行、快），再只在它们真冲突的地方加约束、只重算被影响的那台（冲突驱动，这步最小代价）。它把 §7.3 异步、§7.4 超图共享的"只为真耦合付代价"做成了一个可操作的算法骨架——冲突就是耦合的显式信号，检测到冲突才协调，没冲突就让它们各跑各的。理解了这一点，你就明白为什么 CBS 的思想能跨层复用：它不是一个路径算法，而是一种应对耦合的元策略。

7.6 三类前沿方法的统一视角¶

把 §7.3-§7.5 三类方法对齐，它们在做同一件事的不同切面：

方法	切分什么	"按需/惰性"体现在	牺牲	换来
异步精化（§7.3）	时间（不预离散）	只在真冲突处加协调约束	全局同步的简单性	更短 makespan、更大可行解空间
超图分解（§7.4）	状态空间（按耦合度）	只在抓/放耦合态升维	单一联合空间的统一性	线性而非指数的规模
冲突基 TAMP（§7.5）	机器人（独立求解）	只在冲突处加约束、重算	一次性全局最优求解	并行 + 最小协调 + 可扩展

本质洞察：这张表是本章前沿部分的总纲——三类方法看似各异（动时间、动空间、动机器人），内核完全一致：识别问题的解耦结构，默认让各部分独立，只为真正的耦合付代价。这是对 §7.2"耦合难度守恒"那个洞察的积极回应——既然耦合的负担无法消除，那就尽量把它局部化到真正耦合的小局部，让系统的绝大部分以解耦、并行、低维的方式运行。这也是多机 TAMP 从"能解小问题"走向"能解大问题"的根本路径：不是发明更强的求解器去硬刚指数爆炸，而是更聪明地识别和利用问题里本就存在的解耦结构。

三类方法可以组合，因为它们切的是正交的维度。注意 §7.6 表的"切分什么"一列——异步切时间、超图切状态空间、冲突基切机器人，这三个维度互不冲突，所以一个系统可以同时用：

三类方法在一个多臂重排系统里叠加(它们切正交维度):
  冲突基(§7.5): 高层 —— 每台臂独立解自己的 TAMP, 冲突处加约束
       │  (切机器人维: 独立求解 + 冲突驱动)
       ▼
  超图分解(§7.4): 每台臂的单机 TAMP 内部 —— 用超图组织"臂/物体/持物"
       │  (切状态空间维: 只在抓放升维)
       ▼
  异步精化(§7.3): 时间表示 —— 不预离散时间, 各臂动作异步推进
          (切时间维: 只在真冲突处加协调约束)

这三层叠加后，系统在机器人维（冲突基）、状态空间维（超图）、时间维（异步）上同时只为真耦合付代价——这是当前可扩展多机 TAMP 的典型组合拳。它也再次印证"惰性/按需"这条暗线：三个维度各自惰性化，叠加起来就把"处处都要付的代价"压缩到了"三个维度上各自真正耦合的那一小部分"。

本质洞察：三类前沿方法能正交叠加，揭示了多机 TAMP 复杂度的一个深层结构——它的耦合分布在多个独立的维度上（谁和谁、什么状态、什么时刻），每个维度都可以单独地"只为真耦合付代价"。这就是为什么不存在"一个万能方法"、而是一组各管一维的方法：因为复杂度本身就是多维的，降低它也得多维地降。掌握这一点，你面对一个新的多机 TAMP 难题时，就会本能地问"它的耦合分布在哪几个维度上？每个维度我能用哪个方法局部化？"——而不是寄希望于某个单一的强求解器。这是从"找银弹"到"分维度各个击破"的思维升级，也是多机 TAMP 研究近年真正的方法论进步。

7.7 反过来想：什么时候集中式仍是对的¶

前面三节都在讲"如何避开集中式联合的爆炸"，容易给人一个误导——好像集中式总是错的、分布式/分解总是对的。这是矫枉过正。用反事实推理校准一下：如果一个问题本身就高度耦合、且规模小，会怎样？

设两台臂在一个狭小空间里协同插装一个柔性件——两臂全程都在彼此的工作空间里、几乎每个时刻都互相约束（强耦合）、但只有两台机器人和一个件（小规模）。这时： - 用分解（超图 §7.4）：分解的前提是"大部分时刻解耦"，但这里大部分时刻都耦合，分解切不出多少独立子空间，省不了多少——分解的收益来自解耦结构，没有解耦结构就没有收益。 - 用分布式（异步 §7.3）：异步的前提是"协调是偶尔的"，但这里协调是持续的（两臂时时刻刻要协调），异步省不下同步开销——异步的收益来自稀疏的协调需求，持续协调就没收益。 - 用集中式联合：两台臂 + 一个件，联合构型空间维度有限（小规模），集中式能搜得动，而且它天然处理持续的强耦合（一个问题里同时看两臂，约束自动满足）——这时集中式反而是最对的。

本质洞察：架构选择不是"分布式 vs 集中式"的站队，而是匹配问题的耦合结构与规模。分解/分布式方法的全部威力都来自"利用解耦结构"——当问题确实有大量解耦（机器人多在各自空间作业），它们大获全胜；当问题高度耦合且规模小（紧密协同的少数机器人），它们的前提失效，集中式联合反而又快又对。§7.1-§7.6 讲的"只为真耦合付代价"有一个隐含前提：存在可利用的解耦。当解耦不存在（处处耦合），就老老实实付集中式的代价——前提是规模还撑得住。这就是为什么 §7.2 把集中式、分布式、去中心化并列为谱系而非"淘汰序列"：它们各有适用的耦合×规模象限。判断用哪个，先问两件事：耦合稀疏吗（决定分解/分布式有没有收益）？规模大吗（决定集中式撑不撑得住）？ 稀疏耦合用分解/分布式，稠密耦合 + 小规模用集中式，稠密耦合 + 大规模——那是当前最难的开放问题（§研究建议）。

⚠️ 常见陷阱¶

陷阱 7-1（思维陷阱）：默认用集中式联合 TAMP，不评估状态空间爆炸。 - 错误描述：把多机 TAMP 直接建成"所有机器人构型的笛卡尔积"上的单机 TAMP，丢给求解器。 - 现象/后果：三四台机器人 + 若干物体，联合构型空间维度爆炸，采样/搜索几乎不收敛，规划时间不可接受。 - 根本原因：集中式联合空间随机器人/物体数指数膨胀（§7.2）。没利用"大部分时刻机器人解耦"的结构。 - 正确做法：评估耦合度——若机器人多在各自空间独立作业（弱耦合），用分解方法（超图 §7.4）或分布式（异步 §7.3）；只在真正高耦合（近距离协同操作）的小局部才用集中式联合精化。

陷阱 7-2（概念误区）：以为"分布式"必然牺牲很多最优性、不值得。 - 错误描述：认为分布式方法（异步、冲突基）都是"凑合能用"的次优近似，要质量就得集中式。 - 现象/后果：在大规模问题上死磕集中式求不出解，或为了用集中式人为缩小问题规模，丢掉真实需求。 - 根本原因：混淆了"分布式架构"与"次优"。冲突基 TAMP 这类方法保持最优性（对每个冲突两种消解都展开），异步精化甚至扩大了可行解空间（去掉同步简化）——分布式不等于次优。 - 正确做法：区分方法的保证。冲突基（CBS 式）在框架内保持最优；超图分解是完备的分而治之；只有纯反应式去中心化才显著牺牲保证。按问题规模选架构，别因"分布式 = 次优"的偏见而错过可扩展又有保证的方法。

陷阱 7-3（思维陷阱）：把多机 TAMP 的"协调"理解成"全程同步"。 - 错误描述：一想到多机协调，就给所有机器人加全局时钟、强制同步推进每个动作。 - 现象/后果：快机器人大量空等慢机器人，makespan 远超必要；预离散时间还削减了可行解空间，本可行的方案被排除。 - 根本原因：把"偶尔需要的协调"误当"时时需要"。绝大多数时刻机器人互不干扰，全程同步是过度协调（§7.3）。 - 正确做法：协调按需——用异步表示（隐式时间）、只在真冲突处插入最小必要的协调约束（§7.3 的方法）。把"协调"从"默认开启"改成"冲突触发"。

练习¶

（⭐⭐⭐，分析） 对一个"3 台机械臂在共享桌面重排 6 个物体"的问题，估算集中式联合构型空间的维度（每臂 7 自由度），并说明为什么朴素采样式 TAMP 在这个维度上几乎不可行。再说明超图分解（§7.4）如何把它降到线性规模——分解出哪些子空间、哪些是解耦态、哪些是耦合态。
（⭐⭐⭐，对比） 用一个具体的"两机器人，动作时长一长一短"的例子，画出同步方案和异步方案的时间轴，计算两者的 makespan 差距。说明异步精化（§7.3）的收益来自哪里、它在什么情况下收益最大（提示：动作时长差异越大）。
（⭐⭐⭐⭐，综合，跨 §7-§8） 冲突基 TAMP（§7.5）和 Multi 线的 CBS 都用"检测冲突→加约束→重算单体"。列出三点相同、两点不同。不同点提示：CBS 的冲突只是"时空碰撞"，冲突基 TAMP 的冲突还包括什么（操作层面的冲突）？这个推广为什么更难（提示：操作冲突的"消解"不像路径冲突那样只是"绕开"）？

8. 多机时序协调与冲突消解：从 STN 到时空冲突树 ⭐⭐⭐⭐¶

8.1 动机：耦合的时间维，以及与 MAPF 的接口¶

前面几节处理的耦合主要在"空间/分配"维度：谁做什么（§5/§6）、几何上放哪（§7）。但 §2 的 XD（避让）和 CD（协作）还有一个绕不开的时间维——避让是"同一时刻不能在同一地点"，协作是"同一时间窗必须一起到位"。这一节专门处理时间：把单机的简单时序网络扩展到多机，识别三类时空冲突，并讲清任务层的离散时序如何与运动层的 MAPF/连续时空对接。

这一节也是本章与 Multi 线《任务分配与路径规划》的关键接口章——§3-§7 反复说"XD 弱则在执行层用 MAPF 协调"，到底怎么对接？本节给出答案。

8.2 回顾并扩展：从单机 STN 到多机时序约束¶

回顾 T2 §5 / 总论 §7.4（简单时序网络 STN）：单机时序规划用简单时序网络 (Simple Temporal Network, STN) 表达动作的时间约束——节点是时间点（动作的开始/结束事件），边是约束"事件 $b$ 与事件 $a$ 的时间差落在 $[l,u]$ 区间"：$l\le t_b-t_a\le u$。STN 的好处是这族约束构成一个差分约束系统，可用最短路（Bellman-Ford）在多项式时间内检查一致性、求出可行时刻。

单机 STN 只约束一台机器人自己的动作时序。多机时序要把不同机器人的时间点也连起来。设机器人 $k$ 的动作 $\alpha$ 有开始/结束时间点 $t_\alpha^{s,k},t_\alpha^{e,k}$，多机时序约束新增跨机器人的时间边：

\[ l\ \le\ t_\beta^{s,l}-t_\alpha^{e,k}\ \le\ u,\qquad k\neq l, \tag{8.1} \]

即"机器人 $l$ 的动作 $\beta$ 必须在机器人 $k$ 的动作 $\alpha$ 结束后的 $[l,u]$ 时间内开始"。这条跨机器人边，正是 §2 三重耦合在时间维的载体。

本质洞察：单机 STN 到多机 STN 的扩展，结构上只是"多加了几条跨机器人的时间边"，但意义天差地别——单机 STN 的所有时间点同属一台机器人，它的一致性是"自洽"问题；多机 STN 的时间点分属不同机器人，跨机器人边把它们耦合成一个整体，一致性变成"协同可行"问题。一条跨机器人时间边 (8.1)，就把两台原本独立的机器人在时间轴上锁在了一起——这正是 §4.3 那个 $\xi_{-k}$ 耦合项在时序层的显形。多机时序协调的全部工作，就是管理好这些跨机器人时间边：既要它们表达必要的协作（汇合、交接），又不能让它们过度约束导致无解（死锁的时序根源就是一组互相矛盾的跨机器人边）。

8.3 系统性分类：三类时空冲突¶

多机时序里要处理的耦合，可穷举为三类。这是 §2 三重耦合在时空层的细化分类：

类型	定义	时序约束形态	iTax	例子
汇合 (rendezvous)	多台机器人必须在同一时间窗到达约定构型	$\lvert t_\alpha^{e,k}-t_\beta^{e,l}\rvert\le \epsilon$（几乎同时）	CD	两台臂同时抓住桌子两端才能抬
交接 (handoff)	一台机器人完成后另一台才能开始（物料/位置传递）	$t_\beta^{s,l}\ge t_\alpha^{e,k}$（严格先后）	XD/CD	$R_1$ 把件放到中转台后 $R_2$ 才来取
资源互斥 (mutex)	同一时刻只能有一台机器人占用某资源（空间/工具）	时间区间不重叠：$[t_\alpha^{s,k},t_\alpha^{e,k}]\cap[t_\beta^{s,l},t_\beta^{e,l}]=\varnothing$	XD	窄道/路口/单件工具同一时刻只容一台

三类冲突的处理难度递增的方式不同： - 汇合是"必须同时"——最强的耦合，对应 CD 协作任务，需 §9 时序逻辑显式编码"同步点"。 - 交接是"必须先后"——一个偏序约束，相对好处理（拓扑排序 + 时间传播）。 - 资源互斥是"不能同时"——这恰好是 MAPF 解决的问题（顶点/边冲突就是空间资源的互斥）。

为什么"必须同时"最难？ 因为它把两台机器人的时间轴双向锁死。交接（必须先后）只要求 $t_\beta^s\ge t_\alpha^e$——这是单向约束，$R_2$ 只要"不早于"$R_1$ 即可，$R_2$ 晚多少都行，时间轴有充裕的松弛。互斥（不能同时）只要求两区间不重叠——这是排他约束，但谁先谁后都行，给了消解自由（§8.5 时空冲突树正是利用"两种顺序都试"）。唯独汇合（必须同时）要求 $\lvert t_\alpha^e-t_\beta^e\rvert\le\epsilon$——两台机器人必须在同一瞬间都到位，谁早谁晚都不行，这把两条时间轴几乎焊成一条。后果是：汇合点上游的任何延迟都会双向传播——$R_1$ 慢了 $R_2$ 要等、$R_2$ 慢了 $R_1$ 要等，且这个"同时"还要求两台的运动层执行（搬运时的速度协调）也同步，于是它必然外溢到运动层（Multi 线力控）。这就是为什么汇合是 CD、要 §9 时序逻辑显式编码，而交接/互斥停在 XD、用偏序或 MAPF 就能处理。

回顾 Multi 线《任务分配与路径规划》§3.3-§3.4（MAPF 顶点/边冲突）：MAPF 的两类冲突——顶点冲突（同一时刻两机器人占同一格）和边冲突（同一时刻交换位置）——本质就是"空间资源在某时刻的互斥"。所以本表的"资源互斥"行，正是 MAPF 处理的对象。这给出了任务层时序与运动层 MAPF 的精确分工：任务层管汇合（CD 同步）和交接（偏序），把资源互斥（XD 空间冲突）下放给运动层 MAPF。

8.4 任务层时序与运动层 MAPF 的接口¶

现在正面回答"XD 弱则用 MAPF 协调"到底怎么接。完整的多机系统是任务层时序 + 运动层 MAPF 的两级流水线：

任务层时序 ←→ 运动层 MAPF 的接口(双向):
┌──────────────────────────────────────────────────┐
│ 任务层(本章 §8):                                    │
│   排出每台机器人的动作序列 + 多机时序约束 (8.1)      │
│   处理汇合(CD 同步点)、交接(偏序)                    │
│   产出: 每台机器人"何时该在何处"的时间窗            │
└───────────────────────┬──────────────────────────┘
                        │ 下达: 各机器人的"地点序列 + 时间窗"
                        ▼
┌──────────────────────────────────────────────────┐
│ 运动层 MAPF(Multi 线《任务分配与路径规划》):         │
│   给定各机器人起终点(任务层定的地点), 求无碰撞路径   │
│   用 CBS/PIBT/EECBS 消解顶点冲突、边冲突(资源互斥)   │
│   产出: 每台机器人无碰撞的时空轨迹                  │
└───────────────────────┬──────────────────────────┘
                        │ 反馈: 若 MAPF 无解或 makespan 超时间窗
                        ▼
        回到任务层: 放松时序约束 / 重排序列 / 重分配

关键是下行接口（任务层给 MAPF 什么）和上行接口（MAPF 给任务层什么反馈）： - 下行：任务层把"谁去哪、何时到"的地点 + 时间窗交给 MAPF。MAPF 接管"具体走哪条无碰撞路"。 - 上行：若 MAPF 发现无解（时间窗太紧、空间太挤排不开）或 makespan 超出任务层的时序约束，反馈回任务层——任务层放松时间窗、改顺序、或重分配。这是 §4.5 那条失败反馈链在时序层的兑现。

本质洞察：任务层和 MAPF 的分工，是"离散时序"和"连续/栅格时空"的分工——这正是 T0 总论 §1.3 那条"符号 vs 几何"鸿沟在多机时间维的再现。任务层管离散时序（动作的偏序、时间窗、同步点），它不关心机器人具体走哪格；MAPF 管栅格时空（每个时刻在哪格、避开谁），它不关心任务的语义。两者通过"地点 + 时间窗"这个接口对接——任务层给目标和时限，MAPF 给无碰撞实现。 弱 XD（§4.4）之所以能"甩给 MAPF"，正因为它的避让只是空间资源互斥（MAPF 的本职），不影响任务层的分配优劣；强 XD 之所以甩不掉，是因为它的避让会反过来改变时间窗甚至分配，必须任务层和运动层联合考虑（这时退回 §5 联合或 §7 冲突基）。这个接口是整个多机栈"任务层 ↔ 运动层"那条缝的具体焊点。

8.5 时空冲突树：把 CBS 思想用于任务层时序¶

当 XD 不够弱、不能纯甩给 MAPF 时，可以在任务层就用"冲突驱动"的方式处理时序冲突——这是 §7.5 冲突基思想在时序维的实例。

任务层时空冲突树(CBS 思想的时序版):
  根: 每台机器人按自己的时序约束(忽略他人)排出动作时间表
     │  (此时跨机器人资源互斥可能被违反)
     ▼
  检测冲突: 两台机器人的动作时间区间在同一资源上重叠
     │  冲突 ⟨R_k 的动作 α, R_l 的动作 β, 资源 r, 时段重叠⟩
     ▼
  分裂(两种消解都展开, 保最优):
     子节点 A: 加约束 "α 必须在 β 之前" (t_α^e ≤ t_β^s)
     子节点 B: 加约束 "β 必须在 α 之前" (t_β^e ≤ t_α^s)
     每个子节点只重新传播被约束机器人的 STN 时间表
     ▼
  按 makespan 最优优先, 直到弹出无资源冲突的时间表

这棵树和 Multi 线 CBS 的约束树逐点对应——只是"约束"从"某时刻不得占某格"变成"某动作必须在另一动作前/后"，"低层重规划"从"单体 A* 重算路径"变成"单机 STN 重传播时间表"。

本质洞察：时空冲突树是"冲突驱动协调"范式（§7.5）的第三个化身——Multi 线用它处理路径冲突（CBS），§7.5 用它处理操作冲突（冲突基 TAMP），本节用它处理时序冲突（资源互斥的时间消解）。三者共享同一骨架：独立求解 → 检测冲突 → 两种消解都分裂 → 只重算被影响者 → 最优优先。这第三次出现，应该让你彻底确信：这不是某个算法的偶然，而是应对多机耦合的通用元算法。掌握了这个骨架，你遇到任何"多个个体在共享资源上冲突"的问题——无论资源是空间、操作面还是时间区间——都能套用同一套"冲突基"框架去解。这正是教学要传递的"思考方式"而非"知识清单"：一个范式，三处复用，融会贯通。

8.6 一个能手算的多机 STN：交接 + 互斥¶

把多机 STN 落到数字上走一遍。场景：$R_1$ 取一个件、运到中转台 $T$；$R_2$ 从 $T$ 取件、送到办公室（交接：$R_2$ 必须在 $R_1$ 送达 $T$ 后才能取）；两台都要经过同一条窄道（互斥：同一时刻只一台）。设各动作时长：

$R_1$：取件 $t_{\text{pick}}^{1}\in[0,2]$（用时 2），过窄道 $[?,?]$（用时 3），到 $T$（用时 1）。
$R_2$：过窄道（用时 3），从 $T$ 取件（用时 2），到办公室（用时 4）。

建多机 STN。设事件 $e_1=R_1$ 到达 $T$ 的时刻、$e_2=R_2$ 开始取件的时刻。交接约束（跨机器人边，式 8.1）： $$ e_2 \ge e_1\quad\Longleftrightarrow\quad e_2-e_1\in[0,+\infty). \tag{8.2} $$ $R_1$ 从 $0$ 出发，顺次取件(2)+窄道(3)+到 T(1)，若无等待则 $e_1=2+3+1=6$。窄道互斥约束：设 $R_1$ 进窄道在 $[2,5]$、$R_2$ 进窄道在 $[w,w+3]$，要求两区间不重叠： $$ [2,5]\cap[w,w+3]=\varnothing\quad\Longrightarrow\quad w\ge 5 \text{或} w+3\le 2. \tag{8.3} $$ 后者 $w\le-1$ 不可能（时间非负），故 $w\ge 5$——$R_2$ 必须等 $R_1$ 出窄道（$t=5$）后才进。于是 $R_2$ 进窄道最早 $w=5$，过窄道到 $T$ 旁 $5+3=8$，此时 $e_2\ge\max(8,e_1)=\max(8,6)=8$（交接 (8.2) 在此自动满足，因为 $R_2$ 被窄道拖到 8 才到，已晚于 $e_1=6$）。$R_2$ 取件(2)+到办公室(4)，完工 $8+2+4=14$。整个系统 makespan = 14。

跑一遍 STN 一致性检查（Bellman-Ford 在约束图上找负环）：(8.2)(8.3) 加各动作时长边，构成的差分约束系统无负环 → 一致 → 有可行时刻表。这就是多机 STN 的用法：把交接、互斥、动作时长全写成时间边，整体检一致性，得出可行时刻与 makespan。

读到这里你可能会问："窄道互斥 (8.3) 不是应该下放给 MAPF 吗（§8.4），为什么在任务层 STN 里就处理了？" 好问题——这取决于 XD 强弱（§4.4）。这个例子里窄道把 $R_2$ 拖到 $t=8$，改变了 makespan（强 XD），所以任务层 STN 显式处理它（决定谁先过）是值得的；如果窄道只造成零点几秒的偶尔等待（弱 XD），就该甩给 MAPF、任务层 STN 不必管。任务层 STN 和 MAPF 的分工不是死的——强 XD 的互斥值得在任务层 STN 里预先排序（避免 MAPF 反复试错），弱 XD 的互斥下放 MAPF 更省事。 这正是 §8.4 接口"哪些上提、哪些下放"的判断依据。

8.7 死锁：时序协调失败的典型病灶¶

多机时序最常见的失败是死锁 (deadlock)——一组机器人互相等待对方让出资源，谁也动不了。从 §8.2 的多机 STN 看，死锁就是一组跨机器人时间边构成了正权环（差分约束系统无解）：$R_1$ 等 $R_2$、$R_2$ 等 $R_3$、$R_3$ 又等 $R_1$，时间约束首尾相接成环且不可满足。

回顾 Multi 线《任务分配与路径规划》§3.3 场景二（死锁必然性）：Multi 线演示过——各机器人独立 A* 规划、一起执行，在窄道正面顶牛或路口相撞，死锁几乎必然。那是运动层的死锁。本节的死锁是任务层时序的死锁——交接环（$R_1$ 等 $R_2$ 交接、$R_2$ 又等 $R_1$ 交接）、资源互斥环。两者层次不同但病理同源：都是"互相等待形成环"。

检测与消解：用 STN 一致性检查（Bellman-Ford 检负环 / 差分约束检无解）能预先发现时序死锁；消解靠打破环——引入优先级（固定谁先谁后，破对称）、或加缓冲资源（让出空间避免互斥）。这与运动层用优先级规划破死锁同理。

⚠️ 常见陷阱¶

陷阱 8-1（思维陷阱）：以为分配做对了、各自规划路径就不会死锁。 - 错误描述：把死锁当成"分配没分好"的症状，以为优化分配就能避免。 - 现象/后果：分配最优（每台机器人任务集合合理），执行时仍在窄道/路口死锁——因为分配不管时空交错（T2 陷阱 9-2、本章陷阱 4-2 的时序版）。 - 根本原因：死锁是 XD（时空资源互斥）问题，不是分配（谁做什么）问题。分配对了不蕴含时序无环。 - 正确做法：分配层处理"谁做什么"，时序层单独处理资源互斥——用 STN 一致性检查预测死锁，用优先级/缓冲消解，或下放给 MAPF（§8.4）。两者正交，都要做。

陷阱 8-2（概念误区）：把汇合、交接、互斥三类冲突用同一种约束处理。 - 错误描述：不区分"必须同时"（汇合）、"必须先后"（交接）、"不能同时"（互斥），都写成一种时间约束。 - 现象/后果：把协作任务的"同时"误写成"先后"（桌子一头先抬另一头后抬→翻了），或把互斥的"不能同时"误写成"无约束"（窄道相撞）。 - 根本原因：三类冲突的时序约束形态本质不同（§8.3 表）——汇合是 $\lvert\cdot\rvert\le\epsilon$，交接是 $\ge$，互斥是区间不交。混用导致约束语义错误。 - 正确做法：先判冲突类型（§8.3 三类），用对应约束形态。汇合用近似等时约束（且属 CD，常需 §9 时序逻辑）；交接用偏序；互斥用区间不重叠（或下放 MAPF）。

陷阱 8-3（编程陷阱）：实现多机 STN 时只检查单机时序，漏掉跨机器人边。 - 错误描述：给每台机器人单独建 STN、单独检一致性，没把跨机器人时间边 (8.1) 纳入统一的约束图。 - 现象/后果：每台机器人自己的时序都"一致"，合起来执行却冲突/死锁——因为跨机器人约束根本没被检查。 - 根本原因：多机时序的一致性是全局问题，必须把所有机器人的时间点和跨机器人边放进一张约束图统一检查（Bellman-Ford 全局检负环），分开检查会漏掉耦合。 - 正确做法：建一张包含所有机器人时间点 + 所有跨机器人边的统一 STN，对它整体做一致性检查。跨机器人边是耦合的载体，绝不能在分机器人检查时被忽略。

练习¶

（⭐⭐，建模） 给"两台臂协同搬桌子"写出完整的多机时序约束：哪些是汇合（同时抓住）、哪些是交接、哪些是互斥？用式 (8.1) 的形式写出至少三条跨机器人时间边。
（⭐⭐⭐，分析） 构造一个三机器人交接死锁的具体例子（$R_1$ 等 $R_2$、$R_2$ 等 $R_3$、$R_3$ 等 $R_1$），画出对应的多机 STN，指出其中的正权环。再说明引入优先级如何打破这个环。
（⭐⭐⭐⭐，综合，跨 §8 与 Multi 线） 给一个"4 AGV 在含一条单宽瓶颈通道的路网运料"场景，说明哪些冲突应该在任务层时序处理（汇合/交接）、哪些应该下放给运动层 MAPF（资源互斥）。画出两层的接口数据流（任务层下达什么、MAPF 反馈什么），并讨论当瓶颈通道导致 MAPF 的 makespan 超出任务层时间窗时，上行反馈该触发什么调整。

9. 时序逻辑下的同时分配与规划 (STAP) ⭐⭐⭐⭐¶

9.1 动机：当任务是"一句逻辑规约"而非"一张任务清单"¶

到目前为止，本章假设任务是一份离散的清单——"送这些包裹""搬这张桌子"，每个任务地点明确、可以一个个分配。但很多真实多机任务不是清单，而是一句时序逻辑规约 (temporal logic specification)："巡逻区域 A 和 B，且每次清空垃圾桶后必须把文件送到办公室，永远不要让两台机器人同时进充电间。"这类规约用线性时序逻辑 (Linear Temporal Logic, LTL) 表达——它描述的是"随时间展开的行为模式"（总是、最终、直到），而非一组静态任务点。

这一节处理本章难度阶梯的顶端——CD（复杂依赖）的形式化版本：任务规约是 LTL 公式，需要在多机间同时决定"谁负责满足规约的哪部分"（分配）和"具体怎么动作满足它"（规划）。这就是 STAP（Simultaneous Task Allocation and Planning，同时分配与规划）。

回顾 §3.4 难度阶梯第 4 级 / §6.3（CD 与 DMG）：CD 是"代价依赖任务如何被分解"——任务本身可多种拆法。LTL 规约正是 CD 的典型：一句 LTL 公式可以分解成多种"子任务划分"，不同划分对应不同的机器人分工。§6.3 已说明 CD 违反 DMG（协作的超可加性），所以 CBBA 这类拍卖处理不了它，必须用本节的方法。

9.2 反面：为什么"先分配 LTL、再各自规划"会丢解¶

最自然的想法是把 LTL 规约先拆成子任务、分配给机器人、再让每台机器人各自规划满足自己那部分。这和 §4 的两步解耦同病，但在 LTL 下更隐蔽、后果更严重——它会直接丢掉可行解（不只是次优）。

考虑规约"最终把文件送到办公室，且送之前必须先盖章"。盖章机在 $R_1$ 附近，办公室在 $R_2$ 附近。若先分配： - 把"盖章 + 送文件"整体分给 $R_1$——$R_1$ 要跑到远处办公室，代价高。 - 把它整体分给 $R_2$——$R_2$ 要先跑到远处盖章机，代价也高。 - 最优解其实是 $R_1$ 盖章、$R_2$ 送文件——但这要求把一个 LTL 子目标跨机器人拆开（盖章和送文件由不同机器人接力完成），还要满足"盖章在送之前"的时序约束。先分配的方案在拆分那一刻，往往就把"跨机器人接力"这种解排除了——因为它默认每个子任务由一台机器人完整负责。

本质洞察：LTL 规约下"先分配再规划"丢解的根子，比 §4 的次优更深一层。§4 里解耦是丢最优性（解还在，只是没找到最好的）；LTL 里解耦可能丢可行性（满足规约的解被分配阶段直接排除了）。原因是 LTL 规约的"可分解性"是和时序、和谁能到哪深度耦合的——一个子目标该不该拆、怎么拆、拆给谁，必须看每台机器人的实际能力和时序约束才能定，而这些信息只有规划阶段才有。在分配阶段就固定分解，等于在信息最不足的时候做了最不可逆的决定。 这就是为什么 LTL 多机任务必须"同时"分配与规划，而不能先后——"同时"不是为了更优，是为了不丢解。这是本章"不能解耦"主题的最强形式。

9.3 理论：STAP 如何在自动机上"同时"分配与规划¶

核心方法（Schillinger, Bürger & Dimarogonas, 2018, IJRR 37(7):818-838，"Simultaneous Task Allocation and Planning for Temporal Logic Goals in Heterogeneous Multi-Robot Systems"）：该工作把 LTL 规约的自动机分解结果，与资源受限的多智能体规划，整合进一个统一的 STAP 框架，从而能高效处理多于两三台机器人的团队。在办公室服务场景（机器人在拓扑地图上巡航、清空纸篓、运送文件）中，多机比基线快约 25%。

STAP 的核心机制分三步，关键是它不把"分配"和"规划"分成两个阶段，而是在同一个自动机搜索里同时决定：

第一步：把 LTL 规约编译成自动机。 LTL 公式 $\varphi$ 通过标准构造转成一个 Büchi 自动机（接受满足 $\varphi$ 的无穷序列的自动机）。自动机的状态编码"规约已完成到哪一步"，转移对应"做了某个动作/到达某个命题"。满足规约 = 在自动机上走出一条被接受的路径。

第二步：分解自动机，识别可独立/可协作的部分。 Schillinger 的关键贡献是分解 (decomposition)——分析自动机的结构，识别出哪些转移序列可以由不同机器人独立完成、哪些必须协作/接力。这把"一个全局规约"切成"若干可分配的片段"，但切的方式不是预先拍定的，而是从自动机结构里推出来的（保留了跨机器人接力的可能）。

这一步是 STAP 区别于"先分配"的核心——它不是把规约切给机器人，而是把规约切成"片段"，每个片段还没定归谁。归谁的决定留到第三步的搜索里现场做，这就保住了跨机器人接力的可能（一个片段链可以由多台机器人接力走完）。

第三步：在团队模型上搜索，同时定分配与计划。 把分解后的片段映射到一个团队自动机 / 乘积模型上搜索——搜索的每一步同时决定"这个片段交给哪台机器人"（分配）和"它怎么动作完成"（规划），并满足资源约束（如每台机器人的能力、容量）。因为分配和规划在同一次搜索里联合决定，跨机器人接力这种解不会被提前排除。

STAP 的"同时"在哪里(对比先后解耦):
  先后解耦(会丢解):
    LTL φ → [拆成子任务] → [分配给机器人] → [各自规划]
                ↑ 拆分在此固定, 跨机器人接力的解被排除
  STAP(Schillinger, 不丢解):
    LTL φ → [编译 Büchi 自动机] → [分解识别可独立/协作片段]
          → [团队模型上联合搜索: 每步同时定"片段归谁"+"怎么做"]
                ↑ 分配与规划在同一搜索里联合决定, 接力解被保留

本质洞察：STAP 把"分配"从一个独立的前置阶段，变成了联合搜索里的一个决策维度。这是处理 CD 耦合的终极手段——既然"任务怎么分解、谁负责哪部分"和"具体怎么规划"深度纠缠（§9.2），那就不要分阶段，把分配选择和规划选择放进同一个搜索空间，让搜索同时探索两者的组合。这与 §5 联合优化（把分配+排序+路由写进一个 MILP）是同一哲学在不同表示上的体现——§5 用 MILP 的变量空间联合，STAP 用自动机的搜索空间联合。区别在于 LTL 能表达 MILP 难表达的时序模式（总是、最终、直到、互斥），所以 STAP 是联合优化思想在"任务是逻辑规约"这个更难场景下的推广。到这里，本章的"不能解耦"主题走完了一个完整的螺旋：从 §4 的分配-规划耦合（丢最优），到 §9 的 LTL 同时分配规划（丢可行），耦合的层次越来越深，"必须联合"的理由越来越硬。

9.4 LTL 与 Büchi 自动机：一个能看懂的最小例子¶

§9.3 的三步里第一步"编译成自动机"对没接触过形式化方法的读者最陌生，这里用最小例子讲清楚，让你不必另查资料就能跟上。

LTL 语法速建（够用即可）。线性时序逻辑在普通命题逻辑（与 $\wedge$、或 $\vee$、非 $\neg$）之上，加了四个时序算子，描述"命题随时间怎么变"：

算子	读法	含义	仓库例子
$\lozenge\varphi$	eventually（最终）	未来某时刻 $\varphi$ 成立	$\lozenge\,\mathrm{at\_office}$：最终到办公室
$\square\varphi$	always（总是）	所有时刻 $\varphi$ 都成立	$\square\,\neg\mathrm{collide}$：永不碰撞（安全性）
$\varphi\,\mathcal{U}\,\psi$	until（直到）	$\varphi$ 一直成立直到 $\psi$ 成立	$\mathrm{stamped}\,\mathcal{U}\,\mathrm{delivered}$ 之前要保持已盖章状态
$\square\lozenge\varphi$	总是最终（活性）	无限次地 $\varphi$ 成立	$\square\lozenge\,\mathrm{at\_A}$：无限次巡逻到 A

§9.2 的"盖章后送文件"规约，形式化就是 $$ \varphi\;=\;\lozenge\big(\mathrm{stamped}\wedge\lozenge\,\mathrm{delivered}\big)\;\wedge\;\big(\neg\mathrm{delivered} \mathcal{U} \mathrm{stamped}\big), \tag{9.1} $$ 读作"最终先盖章、再送达，且在盖章之前不得送达"。注意 $\mathcal{U}$ 那部分正是时序约束——它精确编码了"先后顺序"，这是普通 PDDL 目标（只说终态）表达不了的。

Büchi 自动机：把 LTL 变成"可走的图"。把式 (9.1) 编译成 Büchi 自动机，得到一个状态机——状态记录"规约进展到哪一步"，转移对应"机器人做了什么动作/到达什么命题"：

式(9.1)的 Büchi 自动机(简化, 三状态):
   q0(初始: 还没盖章) ──盖章 stamped──→ q1(已盖章, 待送达)
        │                                      │
   (在 q0 时若 delivered → 死状态, 违反"盖章前不得送达")
        │                                      │
        └─────────────────────────── q1 ──送达 delivered──→ q2(接受: 规约满足)✓

满足规约 = 在这张图上从 $q_0$ 走到接受状态 $q_2$。关键来了：从 $q_0$ 到 $q_2$ 这条路径上，"盖章"这个转移和"送达"这个转移可以由不同机器人触发——$R_1$ 触发 $q_0\to q_1$（盖章），$R_2$ 触发 $q_1\to q_2$（送达）。STAP 的联合搜索正是在这张自动机（与团队模型的乘积）上走，每走一个转移就决定"这一步谁来做"——于是"$R_1$ 盖章、$R_2$ 送达"这条接力解自然地被搜索到。先分配的方案则是在编译前就把规约拆给某一台机器人，等于把这张图整个塞给一台机器人走，接力路径根本不在它的搜索空间里。

本质洞察：Büchi 自动机是 STAP 能"不丢解"的几何根源。LTL 规约编译成自动机后，"满足规约"变成了"在图上走出一条接受路径"——而这条路径上的每个转移可以归不同机器人，跨机器人接力天然地表达为"相邻转移由不同机器人触发"。先分配的根本错误，是在把规约变成图之前就切分，于是切掉了"一条路径跨多台机器人"的可能。STAP 把切分推迟到在图上搜索时进行（每个转移现场决定归谁），这就是"同时"分配与规划在自动机表示下的精确含义。 这也解释了为什么必须用自动机而非普通规划——只有把时序规约展开成可走的图，"跨机器人接力"才有了显式的、可搜索的载体。

练手：把仓库规约翻成 LTL（渐隐示例）。 用上表的算子，从"跟着写"过渡到"独立写"。

Phase 1（完整示范）："最终把所有包裹送到打包台"——只要求最终达成，用 $\lozenge$： $$ \varphi_1=\lozenge\big(\mathrm{at_dock}(p_1)\wedge\mathrm{at_dock}(p_2)\wedge\cdots\big). $$
Phase 2（填空）："永远不要让两台机器人同时进充电间"——这是安全性（总是不发生），用 $\square\neg(\cdots)$： $$ \varphi_2=\square\,\neg\big(\underline{\quad在充电间(R_1)\quad} \wedge \underline{\quad在充电间(R_2)\quad}\big). $$ （填空答案：$\mathrm{in\_charger}(R_1)$、$\mathrm{in\_charger}(R_2)$。）
Phase 3（给框架）："无限次巡逻 A 点，且每次到 A 后最终要回 depot"——活性（无限次）+ 响应（到 A 后最终回）。框架：$\square\lozenge(\cdots)\wedge\square(\cdots\to\lozenge\cdots)$，你补全两个括号。
Phase 4（独立写）："清空垃圾桶后必须把文件送到办公室，且送文件前要先盖章"——综合 $\lozenge$、$\to$、$\mathcal{U}$ 写出完整公式，并画出它的 Büchi 自动机骨架（标出哪个转移可跨机器人）。

本质洞察：做完这四阶你会发现，把自然语言规约翻成 LTL 的关键，是先识别它属于哪类时序模式——"最终达成"是 $\lozenge$（可达性）、"永不发生"是 $\square\neg$（安全性）、"无限次"是 $\square\lozenge$（活性）、"A 之后必然 B"是 $\square(A\to\lozenge B)$（响应）、"B 之前保持 A"是 $A\,\mathcal{U}\,B$（顺序）。这五类模式覆盖了绝大多数多机任务规约——识别模式、套对算子，翻译就完成了大半。这正是 STAP 工程的第一步能力：把模糊的"机器人该怎么行为"的需求，精确成一个可编译成自动机、可联合搜索的 LTL 公式。翻译准了，后面 STAP 的"不丢解"才有意义；翻译错了（如把安全性写成可达性），自动机就编码了错误的行为，再好的搜索也是错的。

9.5 前沿延伸：分层时序逻辑与实时反应式 STAP¶

STAP 是一个活跃的前沿，近年（2024-2025）有两个值得知道的方向：

分层时序逻辑 STAP（2024）：用分层 LTL (hierarchical temporal logic) 表达更结构化的多机规约——把复杂规约组织成层级（高层目标 / 低层子目标），降低单层自动机的爆炸，便于分配与规划。这呼应了 T2 §4 的 HTN 思想（用层级压缩搜索），只是从经典规划搬到了时序逻辑。
实时反应式 STAP（Chen & Kan, 2025, IJRR）：面向大规模异构多机系统的实时、反应式分配与规划——能在执行中根据环境变化重新分配与重规划，把 STAP 从离线推向在线。这把本章 §8 的时序协调和 T5 行为树的反应式执行接上了。

回顾 T2 §4（HTN 分层）/ T5（反应式执行）：分层时序逻辑 STAP 复用了 HTN 的"层级压缩搜索"思想；实时反应式 STAP 复用了行为树的"执行中重规划"思想。这说明 STAP 不是孤立的前沿，而是把本章和整条 TAMP 线的多个工具（联合优化、HTN、反应式执行）在"LTL 多机"这个场景下汇聚起来——它是 T2、T5、本章 §5/§8 的一个交汇点。

⚠️ 常见陷阱¶

陷阱 9-1（思维陷阱）：把 LTL 多机任务当成普通任务清单先分配再规划。 - 错误描述：拿到 LTL 规约，习惯性地先拆成子任务清单、分配、再各自规划。 - 现象/后果：不只是次优——可能直接无解（明明存在满足规约的方案，却因为分配阶段排除了跨机器人接力而找不到），系统报"无可行计划"。 - 根本原因：LTL 规约的可分解性与时序、机器人能力深度耦合（§9.2），分配阶段信息不足以正确分解，过早固定分解会丢可行解。 - 正确做法：用 STAP（§9.3）——把 LTL 编译成自动机、分解识别可协作片段、在团队模型上联合搜索，让分配与规划同时决定。绝不在规划前固定分解。

陷阱 9-2（概念误区）：以为 LTL 只是"把任务写得更花哨"，可以转成普通目标。 - 错误描述：认为 LTL 规约（总是、最终、直到）本质上和"达成某个目标状态"一样，可以降级成普通 PDDL 目标处理。 - 现象/后果：丢失时序语义——"永远不要同时进充电间"（安全性，always）、"无限次巡逻"（活性，always-eventually）这类无穷行为模式，用一次性目标根本表达不了，规划出的计划违反规约。 - 根本原因：LTL 表达的是时序模式（含无穷行为、安全性、活性），普通目标只表达"终态命题为真"。两者表达力不同，不能简单降级。 - 正确做法：LTL 规约必须用自动机方法（Büchi 自动机）处理，保留其时序语义。需要无穷行为/安全活性约束时，STAP 这类时序逻辑方法是必需的，不能用普通规划替代。

陷阱 9-3（思维陷阱）：认为机器人越多，STAP 一定越慢、越不可行。 - 错误描述：以为 STAP 的自动机搜索随机器人数指数膨胀，多机必然不可行。 - 现象/后果：因畏惧规模而放弃 STAP，退回会丢解的先分配方案。 - 根本原因：Schillinger 的分解正是为可扩展性设计的——它分解自动机、识别独立片段，使框架能高效处理多于两三台机器人的团队（原文明确针对此），而非朴素地在联合空间搜索。 - 正确做法：用分解式 STAP（§9.3），它通过结构分解控制规模；大规模异构场景用实时反应式 STAP（§9.5）。规模问题用"分解 + 反应式"应对，而非放弃形式化保证。

练习¶

（⭐⭐⭐，分析） 用 §9.2 的"盖章后送文件"例子，具体说明"先分配再规划"如何排除了"$R_1$ 盖章、$R_2$ 送文件"这个最优接力解。再说明 STAP 的联合搜索为什么能保留它。
（⭐⭐⭐，建模） 把"两台机器人无限次巡逻 A、B 两点，且永远不同时在 A"写成 LTL 公式（用 $\square$ always、$\lozenge$ eventually）。指出哪部分是活性（巡逻）、哪部分是安全性（不同时在 A），说明为什么普通 PDDL 目标表达不了"无限次"。
（⭐⭐⭐⭐，综合，跨 §5-§9） STAP（§9.3）和 §5 联合 MILP 都"把分配和规划联合求解"。列出两点相同、两点不同。不同点提示：MILP 联合的是"分配+排序+路由"（都是静态量），STAP 联合的还有什么（时序模式/无穷行为）？为什么 LTL 场景不能直接用 §5 的 MILP（提示：MILP 难编码"总是/最终/直到"）？

10. 与单机 TAMP 及多机协作线的关系 ⭐⭐¶

10.1 动机：把本章放回整张地图¶

学到这里，本章的方法已经铺开。但一个常见的困惑是："本章和我学过的单机 TAMP（T1-T4）、和多机协作线（Multi 线）到底什么关系？哪些是本章的活、哪些不是？"这一节专门划边界——不划清楚，你会在选型时拿错工具（用控制层方法解任务层问题，或反之）。

10.2 与单机 TAMP（T1-T4）的关系：沿"执行者数量"轴的推广¶

本章是单机 TAMP 沿"执行者数量"这一轴的推广，但推广不是简单复制（§2 已反复强调）。精确关系：

维度	单机 TAMP（T1-T4）	多机 TAMP（本章）	推广方式
核心鸿沟	符号 ↔ 几何（一道）	符号↔几何 + 机器人↔机器人（两道）	在原鸿沟上叠加机器人间鸿沟
耦合	任务-运动耦合	+ 分配-规划耦合(ID) + 时空耦合(XD) + 同步耦合(CD)	叠加三类机器人间耦合
几何精化	单机轨迹	多机联合精化（近距离互相约束）	单机精化 × 协调
求解	PDDLStream / LGP	联合优化 / 分布式拍卖 / 冲突基	单机求解器 + 多机协调层

本质洞察：单机 TAMP 和多机 TAMP 的关系，不是"小问题和大问题"，而是"一道鸿沟和两道鸿沟"。单机 TAMP 教你跨越"符号↔几何"——任务序列的可行性依赖几何。多机 TAMP 在此之上再加一道"机器人↔机器人"——你的可行性还依赖别人。本章所有方法，本质都是在单机 TAMP 求解器外面，套一层处理"机器人间鸿沟"的协调层：冲突基 TAMP（§7.5）的低层就是单机 TAMP，高层是协调；TAMP 感知 CBBA（§6.4）的出价里嵌的就是单机路线规划，外面是分布式协调。理解了"多机 = 单机 + 协调层"，你就知道本章不是要你重学 TAMP，而是要你学会在已有的单机 TAMP 之上正确地加协调——这也是为什么本章把 T1-T4 列为前置：没有单机 TAMP 这个"低层"，本章的"协调层"无处安放。

10.3 与多机协作线（Multi 线）的关系：任务层 vs 运动/控制层¶

这是最容易混淆的边界。多机协作线讲的是多机的运动层和控制层（MAPF、分布式 MPC、MARL、编队、协同力控），本章讲的是多机的任务层。精确分工：

问题	归谁	章节
谁做哪个任务、什么顺序	本章（任务层）	§3-§6
任务的几何可行性（够不够得到、放哪）	本章（任务层）	§7
多机时序（汇合/交接/同步点）	本章（任务层）	§8
分配已定后求无碰撞路径（MAPF）	Multi 线《任务分配与路径规划》	Multi 线第 3 章
多机无碰撞协调地动（分布式 MPC）	Multi 线《分布式 MPC 多足编队》	Multi 线第 5 章
协同搬运的力分配与力控	Multi 线《协同搬运与力控》	Multi 线第 6 章
学习式多机协调（MARL）	Multi 线《MARL 多机运动协调》	Multi 线第 12 章

一句话边界：本章产出"谁做哪些任务、什么顺序、每个动作几何上可行的参数 + 多机时序约束"，把"多机具体怎么无碰撞、协调地动"交给 Multi 线的运动/控制层。

回顾 T0 总论 §1.2-§1.3（任务层 vs 运动层）/ 本章 §8.4（任务层↔MAPF 接口）：T0 已立下大原则——任务层管离散决策（做什么/谁做/顺序），运动层管连续执行（轨迹/控制）。本章 §8.4 给了任务层和 MAPF 的具体焊点（地点 + 时间窗下行，无解反馈上行）。本节把这条边界推广到 Multi 线的所有运动/控制章：本章是它们的"上游大脑"，给目标和约束；它们是"下游小脑/脊髓"，给无碰撞、协调的实现。

本质洞察：本章和 Multi 线的关系，是 T0 总论"大脑 vs 小脑"那条线在多机场景的落地。它们处理的是同一批机器人，但回答不同的问题——本章问"谁该去做什么、几何上行不行、时序怎么排"，Multi 线问"既然定了谁去哪，怎么让它们不撞、协调地动"。混淆两者会犯两类错：用 Multi 线的控制工具（共识、编队律、MPC）去解任务层问题（谁做哪个——这是组合优化，不是控制），或用本章的分配工具去解运动层问题（怎么避碰——这是 MAPF/MPC，不是分配）。判断一个问题归本章还是归 Multi 线，只问一句：它是"离散决策（做什么/谁做/顺序/时序）"还是"连续执行（轨迹/避碰/协调控制）"？ 前者本章，后者 Multi 线。这条边界，是把多机系统正确分层、不拿错工具的关键。

10.4 一个完整系统里各层各司其职¶

把抽象边界落到一个具体的"三台机器人收拾仓库"系统，看每层各做什么、交接什么——这是 T0 总论栈图、本章 §8.4 接口图、§10.3 边界表的合体：

"三台机器人收拾仓库"完整分层(从意图到电机):
  人: "把所有包裹送到打包台, 那张重桌子也归位"
     │
     ▼ 【本章 §3-§6】分配-排序: 包裹分给 R1/R2/R3(顺路聚类),
     │   重桌子标记为 MR(需 R1+R2 合搬)。产出: 各机器人任务序列
     ▼ 【本章 §8】时序协调: 重桌子的"两台同时抬"= 汇合约束;
     │   "盖章后送" = 交接偏序; 窄道 = 互斥(下放 MAPF)。产出: 多机 STN
     ▼ 【T1-T4 单机 TAMP】几何精化: 每台机器人为自己每个动作
     │   求抓取位姿/放置/轨迹。够不到 → 反馈回本章重排(§4.5)
     ▼ 【Multi 线 MAPF】路径协调: 给各机器人地点+时间窗,
     │   求无碰撞时空路径(CBS/PIBT)。窄道冲突在此消解
     ▼ 【Multi 线 协同搬运/力控】重桌子: R1+R2 的力分配与协同力控
     ▼ 【Multi 线 分布式 MPC / 控制层】把路径跟踪成电机指令
     ▼ 电机执行

注意三个交接点正是本章反复焊接的缝：本章→T1-T4（任务序列下达给单机几何精化，够不到则反馈）、本章→Multi 线 MAPF（地点+时间窗下达，无解则反馈，§8.4）、本章→Multi 线力控（协作任务的汇合约束下达给协同搬运的力分配）。每个交接点都是"离散→连续"的转换，也都有上行的失败反馈通道。

读到这里你可能会问："为什么重桌子的'两台同时抬'是本章（§8 汇合约束）的活，而'两台各出多大力'是 Multi 线（力控）的活？它们不都是'协作搬运'吗？" 关键区别在离散 vs 连续："什么时候两台必须同时到位、谁抓哪头"是离散的时序/分配决策（本章——它决定动作的偏序和归属），"抬起后每台实时出多大力让桌子不倾斜"是连续的力控（Multi 线——它在轨迹执行时实时调节力）。本章排出"$R_1,R_2$ 在 $t_0$ 同时抓住桌子两端"这个离散同步点，Multi 线接管这个同步点之后"怎么协调地出力把桌子搬平稳"的连续控制。同一个"协作搬运"任务，被这条"离散决策 vs 连续执行"的线干净地切成了本章和 Multi 线两半。

本质洞察：这个分层走查揭示了一个容易被忽略的事实——一个真实多机任务往往被同一条"离散 vs 连续"的线，反复切分到不同的层。重桌子任务既有本章的离散部分（谁抓哪头、何时同时抬），又有 Multi 线的连续部分（实时力分配）；窄道既有本章的离散部分（要不要错开时间窗），又有 MAPF 的连续部分（具体怎么排队走）。学会沿这条线切分任务，是多机系统设计的核心技能——你不是在"本章 or Multi 线"之间二选一，而是把每个任务沿离散/连续切开、离散部分交本章、连续部分交 Multi 线，并在切口处设好双向接口（下行约束、上行反馈）。这也是为什么本章和 Multi 线不是竞争而是接力：它们是同一批机器人、同一批任务的两个互补侧面。

⚠️ 常见陷阱¶

陷阱 10-1（概念误区）：把多机 TAMP 当成多机控制（编队、避障、分布式 MPC）问题。 - 错误描述：期待本章讲"怎么让多机协调地动"，把它和 Multi 线的分布式 MPC、MARL 编队混为一谈。 - 现象/后果：找错方法——用控制层工具（共识、编队律、MPC）去解任务层问题（谁做哪个、什么顺序），或反之，问题根本对不上工具。 - 根本原因：没区分任务层（离散：分配+排序+几何可行性+时序）和运动/控制层（连续：轨迹+协调控制）。多机 TAMP 是任务层（§10.3）。 - 正确做法：牢记分层——本章产出"谁做哪些、什么顺序、几何可行参数、时序约束"，把"怎么无碰撞协调地动"交给 Multi 线。按"离散决策 vs 连续执行"判断问题归属。

陷阱 10-2（思维陷阱）：以为学了多机 TAMP 就不用学单机 TAMP 了。 - 错误描述：认为多机是单机的超集，直接学本章就够，跳过 T1-T4。 - 现象/后果：看不懂本章——冲突基 TAMP 的低层、TAMP 感知 CBBA 的出价里嵌的都是单机 TAMP，不懂单机就不懂这些"低层"在干什么。 - 根本原因：多机 TAMP = 单机 TAMP（低层）+ 协调层（§10.2）。单机 TAMP 是本章方法的内核，不是可跳过的前菜。 - 正确做法：先扎实 T1-T4 的单机 TAMP（符号-几何鸿沟、PDDLStream/LGP），再学本章如何在其上加协调。本章前置自测 Q1 考的就是这个。

练习¶

（⭐⭐，分类） 给下列问题判断归本章（任务层）还是归 Multi 线（运动/控制层）：(a) 三台 AGV 谁去哪个货架取货最省；(b) 三台 AGV 在路口怎么排队不撞；(c) 两台臂搬桌子时各出多大力；(d) 两台臂搬桌子谁抓哪头、什么时候同时抬。说明判断依据（离散决策 vs 连续执行）。
（⭐⭐，对比） 用一句话分别概括"单机 TAMP""多机 TAMP""Multi 线 MAPF"各自回答什么问题，并说明三者如何在一个"多机收拾仓库"系统里串成流水线。
（⭐⭐⭐，综合） 画一张"多机收拾仓库"的完整分层图，从"人下达目标"到"电机执行"，标出每一层归哪一章（本章 / T1-T4 / Multi 线 / 控制层），以及层间传递什么。这道题综合了 T0 总论的栈图、本章 §8.4 接口图和 §10.3 边界表。

11. 工程实践：把多机 TAMP 跑起来 ⭐⭐⭐¶

11.1 动机：从方法到能跑的系统¶

前面九节是方法。这一节回答"怎么把它们落成能跑的代码"——求解器/框架怎么选、规模超限怎么办、以及一个能跑的最小多机分配-规划循环长什么样。本节代码以 Python 为主（便于教学验证），工程部署常用 C++（OMPL/MoveIt 的多机扩展、or-tools 的 C++ 接口）。

11.2 工具选型：分配求解器与 TAMP 框架¶

按本章方法对应的工具谱：

本章方法	推荐工具	说明
联合优化 MILP（§5）	Gurobi / CPLEX（商业）、OR-Tools CP-SAT（开源）	OR-Tools 的路由库 (`pywrapcp`) 直接支持 VRP/mTSP，含子环消除
列生成（§5.6）	自建主问题（PuLP/Gurobi）+ 定价 DP	无现成黑盒，需手写定价子问题
分布式拍卖 CBBA（§6）	自建（算法简单）/ 开源 CBBA 实现	核心是捆绑构建 + 共识，几百行可实现
MAPF 接口（§8）	开源 MAPF 库（EECBS / PIBT / LaCAM 实现）	见 Multi 线《任务分配与路径规划》，本章只对接
单机 TAMP 低层（§7）	PDDLStream / RAI(LGP)	见 T3/T4，作为多机协调的低层
时序逻辑 STAP（§9）	LTL→Büchi 工具（如 Spot）+ 自建团队搜索	Spot 做 LTL 编译，分配搜索需自建

本质洞察：多机 TAMP 工程的现实是"没有一个端到端黑盒"——它是把分配求解器、单机 TAMP 框架、MAPF 库、（可能的）LTL 工具拼起来的系统。这印证了本章反复的分层视角：每一层有成熟工具（OR-Tools 管路由、EECBS 管 MAPF、PDDLStream 管单机几何），但"把它们正确接起来、处理层间反馈"是工程师的活，没有现成轮子。所以多机 TAMP 工程能力的核心，不是会用某个库，而是懂得各层接口（§8.4）、知道在哪一层放哪个工具、以及如何处理层间的失败反馈。 这也是为什么本章花大力气讲接口和边界（§8、§10）——它们才是工程落地真正的难点。

11.3 一个能跑的最小多机分配-规划循环¶

把 T2 §9.4 策略一（解耦 + 迭代修正）实现成一个最小可跑的循环——它整合了本章的边际代价（§4.2）、拍卖式分配（§6）、真实路线（§4.4）：

import numpy as np
from itertools import permutations

# ===== 最小多机分配-规划循环(策略一: 解耦+迭代修正) =====
# 教学简化版: 用真实路线代价(而非直线)做分配, 迭代到稳定
# depot 在原点, 任务是平面上的点, 代价 = 总行驶距离

def route_length(depot, pts):
    """给一组任务点求最优访问路线长度(小规模穷举 TSP, 教学用)。
       这是 §4.2 的 route_k(·) —— 真实路线代价, 不是直线距离。"""
    if not pts:
        return 0.0
    best = float('inf')
    for perm in permutations(pts):           # 穷举所有访问顺序(仅适合 <=8 点)
        seq = [depot] + list(perm) + [depot]  # 从 depot 出发, 回 depot
        d = sum(np.linalg.norm(np.array(seq[i+1]) - np.array(seq[i]))
                for i in range(len(seq) - 1))
        best = min(best, d)
    return best

def marginal_cost(depot, current_pts, new_pt):
    """§4.2 的边际代价 Δc: 把 new_pt 加入 current_pts 路线多花多少。
       注意: 依赖 current_pts —— 这就是'代价不是常数'。"""
    return route_length(depot, current_pts + [new_pt]) - route_length(depot, current_pts)

def ssi_allocate(depot, robots_pos, tasks):
    """序贯单物品拍卖(SSI, 见 T2 §8.3): 每轮把一个任务判给边际代价最小的机器人。
       出价 = 真实边际代价(§6.4 TAMP 感知出价), 天然处理 ID 顺路。"""
    assign = {k: [] for k in range(len(robots_pos))}   # 每台机器人的任务列表
    remaining = list(tasks)
    while remaining:
        best_bid, best_k, best_t = float('inf'), None, None
        for t in remaining:
            for k in range(len(robots_pos)):
                # 机器人 k 的"路线起点"是它的位置, 已分任务 + 候选 t
                base = [robots_pos[k]] + assign[k]
                bid = marginal_cost(depot, assign[k], t) if assign[k] \
                      else np.linalg.norm(np.array(t) - np.array(robots_pos[k]))
                if bid < best_bid:                        # 取全局最低边际出价
                    best_bid, best_k, best_t = bid, k, t
        assign[best_k].append(best_t)                     # 判给出价最低者
        remaining.remove(best_t)
    return assign

# ---- 运行: 复现 §4.2 的"顺路 vs 不顺路"直觉 ----
depot = (0.0, 0.0)
robots = [(0.0, 0.0), (8.0, 2.0)]                         # R0 在 depot 附近, R1 在远处
tasks  = [(2.0, 0.0), (2.0, 1.0), (8.0, 0.0), (8.0, 1.0)] # p1,p2 近 R0; p3,p4 近 R1
alloc = ssi_allocate(depot, robots, tasks)
for k, ts in alloc.items():
    print(f"R{k}: 任务={ts}, 路线长={route_length(robots[k], ts):.2f}")
# 期望: SSI 把 p1,p2 给 R0(顺路), p3,p4 给 R1(顺路) —— 而非按直线乱分

这段代码的关键教学点：出价用 marginal_cost（真实边际，§4.2）而非直线距离——这就是 §6.4 TAMP 感知出价、T2 §9.4 策略二的最小实现。它处理 ID，但不处理 XD（没有任何机器人间路线协调）——要处理 XD，需在 alloc 之后接一个 MAPF 步骤（§8.4），用 Multi 线的 EECBS 给 alloc 里每台机器人的路线消解冲突。

11.4 接上 XD：分配后的 MAPF 协调桩¶

§11.3 只做了分配（ID）。这一节把 §8.4 的"分配→MAPF"接口落成可读代码——一个最小的优先级规划（cooperative A*）协调桩，检测并消解机器人间的路径冲突（XD），并算出协调代价比 $\rho$（§4.4）。这演示了"任务层下达地点、运动层消解冲突"的完整下行接口。

# ===== XD 协调桩: 分配后用优先级规划消解路径冲突(§8.4 下行接口) =====
# 教学简化: 栅格世界, 离散时间, 优先级规划(高优先级先占时空, 低优先级避让)
# 这是把 §11.3 的 alloc 接到运动层的最小实现

def grid_path(start, goal, grid, reserved, t0):
    """带时空预留的单体 A*(cooperative A*): 避开 reserved 里已被占的(格,时刻)。
       这就是 Multi 线 §3.5 优先级规划的低层。reserved 是 XD 的载体。"""
    from heapq import heappush, heappop
    def h(p): return abs(p[0]-goal[0]) + abs(p[1]-goal[1])   # 曼哈顿启发
    openq = [(h(start), 0, start, t0, [start])]
    seen = set()
    while openq:
        f, g, pos, t, path = heappop(openq)
        if pos == goal:
            return path, t                                    # 返回路径和到达时刻
        if (pos, t) in seen:
            continue
        seen.add((pos, t))
        for dx, dy in [(0,1),(0,-1),(1,0),(-1,0),(0,0)]:      # 含原地等待(0,0)
            nxt = (pos[0]+dx, pos[1]+dy)
            if nxt in grid and (nxt, t+1) not in reserved \
               and (pos, nxt, t+1) not in reserved:           # 避顶点冲突 + 边冲突
                heappush(openq, (g+1+h(nxt), g+1, nxt, t+1, path+[nxt]))
    return None, None                                          # 无解 → 上行反馈(§8.4)

def coordinate(alloc_paths, grid, priority):
    """优先级规划: 按 priority 顺序为各机器人规划, 先规划的占住时空, 后规划的避让。
       这消解 XD(机器人间路径冲突), 返回总 makespan。"""
    reserved = set()                                          # 已占的(格,时刻)+(边,时刻)
    coord_makespan = 0
    for k in priority:                                        # 高优先级先占, 体现 XD 协调
        full_path = []
        t = 0
        for leg_start, leg_goal in alloc_paths[k]:            # 该机器人的地点序列
            seg, t = grid_path(leg_start, leg_goal, grid, reserved, t)
            if seg is None:
                return None                                   # 排不开 → 反馈任务层重排
            full_path += seg
        for i, p in enumerate(full_path):                     # 把这条路径占进 reserved
            reserved.add((p, i))
            if i > 0: reserved.add((full_path[i-1], p, i))    # 边占用(防对穿)
        coord_makespan = max(coord_makespan, len(full_path))
    return coord_makespan

# ---- 用法: 分配(§11.3) → 协调(本节) → 算协调代价比 ρ ----
# ind_cost: 忽略 XD 时各机器人路线长之和(并行, 取 max 作 makespan)
# coord_makespan: 加 MAPF 协调后的真实 makespan
# rho = (coord - ind) / ind  —— §4.4 的协调代价比, 量化 XD 强弱

本质洞察：这段协调桩把"任务层 vs 运动层"的接口（§8.4）变成了一行 coordinate(alloc_paths, ...) 调用——分配（§11.3）产出"谁去哪"，协调（本节）消解"路上会不会撞"，两者通过 alloc_paths（地点序列）这一个数据结构对接。注意 reserved 集合是整个 XD 的载体：它记录"哪些时空点已被占"，后规划的机器人据此避让——这就是 $\xi_{-k}$ 耦合项（§4.3）在代码里的样子。而 grid_path 返回 None 时（排不开）正是 §8.4 的上行反馈触发点——它该回到任务层放松时间窗或重分配。当你能把 §8.4 那张抽象的接口图写成这段代码，你就真正掌握了多机栈最关键的那条焊缝：离散分配如何下达给连续协调、连续协调的失败如何反馈回离散分配。

11.5 规模应对：当任务/机器人多到求解器跑不动¶

工程上规模超限是常态，应对手册：

症状	应对	本章依据
MILP 几十任务就超时	转列生成 / 滚动时域 / 退到拍卖	§5.5-§5.6, §6
拍卖出价慢（每次精算 TSP）	廉价插入启发 + 惰性精算	§4 陷阱 4-3
联合几何精化状态空间爆炸	超图分解 / 分布式异步	§7.3-§7.4
MAPF 大规模求不出最优	退 ECBS/EECBS（有界次优）/ PIBT	Multi 线 §3.5, §3.7
时序协调死锁	STN 一致性预检 + 优先级破环	§8.7

本质洞察：规模应对的统一策略是"用一点最优性换可扩展性，且对损失心里有数"。本章每个方法都有它的"降级版"——MILP 降到列生成/拍卖、最优 MAPF 降到有界次优、联合精化降到分解。工程的成熟度，体现在你知道每次降级丢了多少（MIP gap、50% 界、有界次优的 $w$ 倍）、以及这个损失在你的应用里是否可接受。 这呼应了 §5.5"工程是在金标准的阴影下做近似"——降级不是认输，是清醒地用可量化的次优换来可运行的系统。盲目降级（不知道丢了多少）和拒绝降级（死磕最优跑不出来）是两个相反的工程错误，本章给你的是中间那条清醒之路。

⚠️ 常见陷阱¶

陷阱 11-1（编程陷阱）：用穷举 TSP 算路线代价，任务一多就卡死。 - 错误描述：像 §11.3 教学代码那样用 permutations 穷举求最优路线，直接用到几十个任务的实际场景。 - 现象/后果：$n!$ 增长，10 个任务就 360 万种排列，20 个任务宇宙年龄也算不完，分配阶段彻底卡死。 - 根本原因：穷举 TSP 是 $O(n!)$，仅适合教学演示（$\le 8$ 点）。实际路线代价要用启发式或专用求解器。 - 正确做法：实际用 OR-Tools 路由库（含 Lin-Kernighan 等强启发）或廉价插入估边际（§4 陷阱 4-3）。教学穷举只用于验证小例子正确性，绝不上生产。

陷阱 11-2（思维陷阱）：以为有了分配代码就完成了多机 TAMP。 - 错误描述：实现了 §11.3 的分配循环，就认为多机 TAMP 做完了。 - 现象/后果：分配出来了，机器人一起跑却撞车/死锁——因为只做了分配（ID），没接 MAPF（XD）、没处理时序（§8）。 - 根本原因：多机 TAMP = 分配 + 几何精化 + 时序协调 + MAPF 接口，分配只是其中一环（§10.2）。 - 正确做法：分配后必须接运动层协调——把 alloc 的路线交给 MAPF 消解冲突（§8.4），有协作/时序的还要处理汇合交接（§8.3）。完整系统是多层流水线，不止分配。

陷阱 11-3（编程陷阱）：迭代修正循环不设收敛判据，无限振荡。 - 错误描述：实现策略一（解耦+迭代）时，循环"重分配→重规划"却不判断何时停。 - 现象/后果：分配在两个方案间反复横跳（A 方案规划后真实代价偏高→改 B，B 规划后又偏高→改回 A），永不收敛（T2 §9.4 策略一已警告"可能振荡"）。 - 根本原因：解耦+迭代不保证收敛（§4.5 回溯链的振荡）。没有收敛判据就可能死循环。 - 正确做法：设双重停止条件——分配不再变化（收敛）或达到迭代轮数上限（强制停，取当前最好）。振荡时取历史最优解返回，别死等收敛。

练习¶

（⭐⭐⭐，实现） 给 §11.3 的代码加一个 MAPF 接口桩：分配后，把每台机器人的路线离散成栅格时空路径，用一个简单的优先级规划（cooperative A*）检测并消解顶点冲突。观察哪些分配会产生路径冲突、消解后 makespan 增加多少（这就是协调代价比 $\rho$，§4.4）。
（⭐⭐⭐，调试） §11.3 代码在 assign[k] 为空时用直线距离、非空时用边际——这个分支有什么隐患？（提示：第一个任务的"边际"其实也该是从机器人当前位置出发的真实代价。）修正它，使第一个任务的代价也一致地用"从机器人位置出发的路线增量"。
（⭐⭐⭐⭐，综合，跨 §5-§11） 把 §11.3 的 SSI 分配换成 §5 的 MILP（用 OR-Tools 路由库），在同一个 4 任务实例上对比两者的分配结果和总代价。讨论：什么规模下 MILP 还能跑、什么规模下必须退回 SSI/CBBA？结合 §6.6 取舍表给出你的选型判断。

12. 累积项目：给 Mini-TAMP 加上多机联合层 ⭐⭐⭐¶

12.1 项目定位：本章新增模块¶

回顾累积项目（TAMP 线贯穿项目 Mini-TAMP）：TAMP 线的累积项目是从零搭一个单机长时域移动操作系统——T1 搭符号规划骨架、T3/T4 加几何精化、T5 加行为树执行、T6 加信念空间、T7 加 LLM 前端。到本章为止，它一直是单机的。本章的任务：给 Mini-TAMP 加一个多机联合层，让它从"一台机器人收拾仓库"升级到"多台机器人协同收拾仓库"。

本章新增模块：多机分配-规划联合层，插在"任务规划"和"单机几何精化"之间。它接收一份任务清单，输出"每台机器人做哪些任务、什么顺序、含多机时序约束"，再把每台机器人的子任务交给已有的单机 Mini-TAMP（T1-T4 搭的）精化。

12.2 模块架构：把本章方法接进 Mini-TAMP¶

Mini-TAMP 多机版数据流(本章新增"多机联合层"):
  仓库目标("把所有包裹送到打包台")
     │
     ▼
  [已有] 任务规划层(T1/T2): 拆出任务清单 {p1,...,pn}
     │
     ▼
  [本章新增] 多机联合层:
     ├─ 分配-排序: SSI/CBBA(§6) 用真实边际代价(§4) 把任务分给 R1..Rm
     ├─ 时序协调: 识别汇合/交接/互斥(§8), 建多机 STN
     └─ (强 XD 时) 联合优化(§5) 或冲突基精化(§7)
     │  产出: 每台机器人的"子任务序列 + 时间窗"
     ▼
  [已有] 单机几何精化(T3/T4): 每台机器人各自精化抓取/放置/轨迹
     │  够不到 → 反馈回多机层重排/重分配(§4.5 失败链)
     ▼
  [接 Multi 线] MAPF 协调(§8.4): 消解路径冲突, 输出无碰撞时空轨迹
     │
     ▼
  [已有] 行为树执行(T5): 稳健执行, 异常恢复, 一台失效则触发重分配

12.3 本章模块的实现骨架¶

把多机联合层写成一个挂接已有 Mini-TAMP 的类（教学骨架，关键部分留给练习填充）：

class MultiRobotLayer:
    """Mini-TAMP 多机联合层(本章新增模块)。
       挂在任务规划层和单机几何精化之间。"""

    def __init__(self, robots, depot, single_tamp_solvers):
        self.robots = robots                  # 各机器人初始位姿
        self.depot = depot
        self.tamp = single_tamp_solvers       # 已有的单机 Mini-TAMP(T3/T4), 每台一个

    def allocate(self, tasks):
        """§6: 用 TAMP 感知 SSI/CBBA 分配。出价 = 真实路线边际(§4.2/§11.3)。"""
        return ssi_allocate(self.depot, self.robots, tasks)   # 复用 §11.3

    def build_temporal_constraints(self, alloc):
        """§8: 识别汇合/交接/互斥, 建多机 STN。
           教学骨架: 检测同一资源(地点)被多台机器人在重叠时段占用 → 互斥约束。"""
        constraints = []
        # TODO(练习): 遍历 alloc, 对协作任务加汇合约束(同时), 
        #             对交接任务加偏序约束, 对共享地点加互斥约束(式 8.1)
        return constraints

    def refine_geometry(self, alloc, constraints):
        """T3/T4: 每台机器人各自跑单机 Mini-TAMP 精化。
           够不到则抛出反馈, 触发 §4.5 失败链(重排/重分配)。"""
        plans = {}
        for k, task_seq in alloc.items():
            try:
                plans[k] = self.tamp[k].solve(task_seq)       # 复用已有单机 TAMP
            except InfeasibleError:                            # 几何不可行
                return None, ('infeasible', k)                 # 上报, 触发重分配
        return plans, None

    def solve(self, tasks, max_realloc=5):
        """主循环: 分配 → 时序 → 精化, 失败则重分配(策略一, §11.3)。"""
        for _ in range(max_realloc):                           # 收敛判据: 轮数上限(陷阱 11-3)
            alloc = self.allocate(tasks)
            cons = self.build_temporal_constraints(alloc)
            plans, fail = self.refine_geometry(alloc, cons)
            if plans is not None:
                return alloc, cons, plans                      # 成功
            # 失败: 把不可行任务标记, 下轮分配避开该机器人(简化的失败反馈)
            tasks = self._adjust_after_failure(tasks, fail)
        raise PlanningFailure("达到重分配上限仍不可行")          # 强制停, 返回失败

这个骨架把本章方法（§4 边际、§6 分配、§8 时序、§4.5 失败链）和已有 Mini-TAMP（T3/T4 的单机精化、T5 的执行）焊在一起。它故意把 build_temporal_constraints 和 XD 协调留空——那是练习要补的、也是本章最难的部分。

跑起来会看到什么。 在一个"3 机器人收拾仓库"实例上调用 solve，逐层的产出大致是：

MultiRobotLayer.solve 的一次成功运行(三机器人收拾仓库, 含一个重物):
  [分配 §6] SSI 用真实边际出价:
     R0 ← [p1, p2, p3]   (顺路聚在货架A一带, 边际小)
     R1 ← [p4, p5]       (货架B一带)
     R2 ← [heavy_table]  (重物, 标记需协作)
  [协作识别] heavy_table 是 MR → 需 R1+R2 → 触发汇合约束
  [时序 §8] build_temporal_constraints 产出:
     汇合: |t_R1@table_end - t_R2@table_end| ≤ 0.5   (两端几乎同时抓住)
     互斥: R0、R1 共享窄道 → 时间区间不重叠
  [几何精化 T3/T4] 各机器人单机 TAMP:
     R0: p1,p2,p3 抓放轨迹 ✓
     R1: p4 ✓; p5 放置位姿够不到! → InfeasibleError
  [失败反馈 §4.5] p5 转给 R0(下轮重分配), R1 改去帮 R2 搬桌
  [重分配后] 再精化全部可行 → 返回 (alloc, 时序约束, 各机器人计划)

注意这次运行把本章的几条主线都演了一遍：分配看真实边际（§6，顺路聚类）、MR 触发汇合（§8 协作同步）、几何不可行触发跨层失败反馈（§4.5，p5 够不到 → 重分配）。这正是 §10.2"多机 = 单机 + 协调层"的活演示——refine_geometry 里复用的 self.tamp[k].solve() 就是原封不动的单机 Mini-TAMP，新增的全是它外面那层"分配 + 时序 + 失败反馈"的协调壳。

本质洞察：这个运行轨迹里最有教学价值的一幕，是 p5 够不到 → 转给 R0 这个跨层失败反馈。它把全章最抽象的"信息通道"（§4.5）变成了一行 _adjust_after_failure——几何层（T3/T4）发现的不可行，逆着数据流向上反馈到分配层（§6），触发重分配。这正是 §4.5 那条"修好信息通道"的完整闭环：不是盲目重试，而是带着"R1 够不到 p5"这个具体信息回去，让分配层知道"p5 别再给 R1"。当你在自己的实现里看到这个反馈真的让系统从失败中恢复，你就彻底理解了为什么本章反复强调"失败要能逐层上传、且带着原因"——这是多机 TAMP 从"demo 能跑"到"鲁棒可用"的分水岭。

12.4 项目里程碑与验收¶

本章模块完成后，Mini-TAMP 应能演示：

里程碑	验收标准	用到本章
基本多机分配	多台机器人分到任务、总代价优于平均分配	§4, §6
顺路处理	出价用真实边际，顺路任务聚到同一机器人	§4.2, §6.4
时序协调	协作任务有汇合约束、交接任务有偏序	§8.3
失败重分配	一台机器人够不到时，任务自动转给别人	§4.5
接 MAPF	分配后路线交 MAPF，执行无碰撞	§8.4

本质洞察：这个累积项目最重要的教学价值，是让你亲手验证"多机 = 单机 + 协调层"（§10.2）——你不重写单机 Mini-TAMP，而是在它外面套一个 MultiRobotLayer。当你发现已有的 self.tamp[k].solve()（单机精化）原封不动地被复用、新增的只是"分配 + 时序 + 协调"这层壳，你就真正理解了本章在整个 TAMP 体系里的位置：它不是另起炉灶的新系统，而是给单机 TAMP 加的一顶"多机协调帽子"。 这也是为什么本章的难点全在协调层（分配耦合、时空冲突、时序），而非几何精化（那是 T3/T4 已解决的、被直接复用的）。

至此，本章开篇 §2 那个"复制粘贴会崩"的反面教材，在 §12 得到了正面的回答——MultiRobotLayer 正是"不复制粘贴、而是加一层正确协调"的具体实现。它把全章八节的方法收拢成一个能跑的模块：§4 的真实边际进了出价、§6 的拍卖做了分配、§8 的时序约束管了协作、§4.5 的失败反馈接住了几何不可行。当你跑通它，你就不再把多机系统当成"N 个单机的拼装"，而是当成"单机求解器 + 一层处理机器人间耦合的协调"——这正是本章从第一行到最后一行想让你完成的认知转变。

练习¶

（⭐⭐⭐，实现） 补全 build_temporal_constraints：检测 alloc 中是否有协作任务（需多台机器人），为它加汇合约束（式 8.1 的近似等时）；检测共享地点的时段重叠，加互斥约束。用 §8 练习 1 的搬桌场景测试。
（⭐⭐⭐，实现） 补全 XD 协调：在 refine_geometry 后加一步，把各机器人路线离散成栅格时空路径，调用一个简单 MAPF（优先级规划）消解冲突，返回协调代价比 $\rho$（§4.4）。
（⭐⭐⭐⭐，综合，贯穿全章） 设计一个"3 机器人收拾仓库"完整实例：含顺路（ID）、窄道避让（XD）、一个需两台合搬的重物（CD）。跑通 MultiRobotLayer.solve，报告：分配结果、时序约束、协调代价比、以及当你把重物的"两台合搬"去掉同步约束时系统如何失败（验证 §8 陷阱 8-2、§9 的"丢解"）。

本章常见误解汇总¶

误解	正确理解	出处
多机 TAMP = 单机 TAMP × N，平均分任务各自跑即可	多机新长出三类机器人间耦合（ID/XD/CD），复制粘贴假设它们全为零，几乎总崩	§2.2, 陷阱 2-1
多机 TAMP 主要是多机控制（编队、避障、MPC）	它是任务层问题（分配+排序+几何可行+时序），控制归 Multi 线运动/控制层	§10.3, 陷阱 2-2
问题难度由机器人数量决定	难度由 iTax 依赖级（ND/ID/XD/CD）决定，数量只影响求解规模	§3.2, 陷阱 3-1
分配做对了，各自规划就不会冲突	分配（ID）和时空（XD）是两类耦合；分得好不蕴含路线不打架	§4.4, 陷阱 4-2
用直线距离做分配代价"差不多"	直线距离是 ND 假设，真实问题至少 ID，实测里程常高 30%-40%	§4.2, 陷阱 4-1
MILP 求解器万能，规模再大也能等出来	MILP 是 NP-hard，几十任务封顶；大规模需列生成/拍卖/滚动时域	§5.5, 陷阱 5-2
CBBA 适用于任何多机分配	CBBA 需 DMG（子模），处理不了 CD 协作（超可加违反 DMG）	§6.3, 陷阱 6-1
分布式方法必然牺牲很多最优性	冲突基 TAMP 保持最优、异步精化扩大可行解空间；分布式不等于次优	§7.6, 陷阱 7-2
多机"协调"就是给所有机器人加全局时钟同步	协调应按需——只在真冲突处加约束，全程同步浪费且削减解空间	§7.3, 陷阱 7-3
LTL 多机任务可先分配再规划	LTL 下先分配会丢可行解（排除跨机器人接力），必须 STAP 同时决定	§9.2, 陷阱 9-1
LTL 只是把任务写花哨，可转普通目标	LTL 表达时序模式（总是/最终/直到、安全活性），普通目标表达不了	§9.2, 陷阱 9-2

本章小结¶

本章把单机 TAMP 沿"执行者数量"轴推广到多机，主线是"耦合的升级"——

§2 三重耦合：从一台到多台，新长出三类机器人间依赖——ID（顺路，机器人内部）、XD（避让，机器人之间）、CD（协作，任务结构），对应复制粘贴的三种崩法。这是全章的总纲。
§3 分类学定位：多机 TAMP 住在 MRTA 地图的 ST-SR-TA + XD~CD 区——比 T2 的 CBBA（ND~ID）正好难了 iTax 那条轴。难度由依赖级而非数量决定。
§4 耦合解剖：ID 让边际代价非常数（可手算）、XD 让代价多一个 $\xi_{-k}$ 耦合项、$\rho$ 判据区分强弱 XD、解耦引发与 TAMP 同构的跨层回溯。
§5 联合优化：把分配+排序+路由写成 MILP（流变量 + 子环消除 MTZ/DFJ），$O(n^2m)$ 变量限制精确解到几十任务，列生成/分支定价救大规模。
§6 市场/拍卖：SSI→CBBA 分布式，DMG（子模）是收敛前提且对应 ID 的物理结构，TAMP 感知出价嵌真实规划器处理 ID，拍卖 vs MILP 是最优性↔可扩展性的取舍。
§7 分布式前沿：架构谱系（集中/分布/去中心）+ 三类近年方法（异步精化、超图分解、冲突基 TAMP），统一内核是"识别解耦结构、只为真耦合付代价"。
§8 时序协调：多机 STN（跨机器人时间边）、三类时空冲突（汇合/交接/互斥）、任务层↔MAPF 接口（地点+时间窗下行、无解反馈上行）、时空冲突树、死锁正权环。
§9 时序逻辑 STAP：LTL 规约下先分配会丢可行解，Schillinger 在自动机上同时分配规划，是"不能解耦"的最强形式。
§10-§12：与单机 TAMP（=单机+协调层）、Multi 线（任务层 vs 运动层）划界；工程工具谱与最小循环；给 Mini-TAMP 加多机联合层。

一条暗线贯穿全章："惰性/按需 + 冲突驱动"是应对多机耦合爆炸的通用密码——DFJ 惰性割、列生成惰性变量、异步按需协调、超图按耦合升维、冲突基只在冲突处协调，全是同一智慧的不同切面。

术语速查表¶

术语	一句话定义
多机 TAMP (Multi-Robot TAMP)	多执行者的任务与运动规划，在符号-几何鸿沟上叠加机器人间的分配-时空-同步耦合
ID 依赖 (In-schedule)	任务代价依赖同一机器人自己的其他任务（顺路），边际代价非常数
XD 依赖 (Cross-schedule)	任务代价依赖其他机器人的安排（避让），边际代价含 $\xi_{-k}$ 耦合项
CD 依赖 (Complex)	任务代价依赖任务如何被分解（协作可多种拆法），违反 DMG
边际代价 $\Delta c_k(\tau\mid S)$	把任务 $\tau$ 插入机器人 $k$ 已分集合 $S$ 路线多花的代价，拍卖出价的基础
协调代价比 $\rho$	(协调后真实代价 − 忽略 XD 分配代价)/忽略 XD 分配代价，区分强弱 XD
mTSP / CVRP	多旅行商 / 带容量车辆路径，多机分配-排序-路由的经典 NP-hard 模型
子环消除 (Subtour Elimination)	MILP 中禁止脱离 depot 的孤立环，MTZ（紧凑弱松弛）或 DFJ（指数紧松弛）
列生成 (Column Generation)	以"整条路线"为变量、只在需要时生成负简约代价列的大规模求解法
DMG (递减边际收益)	边际收益不随集合变大而增大（=子模），CBBA 收敛与 50% 界的前提
TAMP 感知出价	拍卖出价用真实路线规划器算边际、而非直线距离，分布式处理 ID
异步精化	不预离散时间、不强制同步，只在真冲突处加协调约束的多机 TAMP 精化
超图分解	按耦合度把规划空间分解为臂/物体/持物子空间，规模从指数降到线性
冲突基 TAMP	CBS 思想用于 TAMP：独立求解→检测冲突→两种消解分裂→只重算被影响者
多机 STN	含跨机器人时间边 (8.1) 的简单时序网络，多机时序一致性的载体
汇合/交接/互斥	三类时空冲突：必须同时 / 必须先后 / 不能同时占用资源
STAP (同时分配与规划)	LTL 规约下把分配作为联合搜索的决策维度、不分阶段，避免丢可行解

符号表¶

符号	含义	首次出现
$\mathcal{R},\mathcal{T}$	机器人集合、任务集合	§2.4
$a:\mathcal{T}\to 2^{\mathcal{R}}$	分配（任务→机器人子集，子集>1 表协作）	§2.4
$\sigma_k$	机器人 $R_k$ 的任务序列	§2.4
$\xi_k(t)$	机器人 $R_k$ 的连续轨迹	§2.4
$\xi_{-k}$	除 $k$ 外所有机器人的轨迹（XD 耦合项）	§4.3
$\Delta c_k(\tau\mid S)$	边际代价函数	§4.2
$\mathrm{route}_k(\cdot)$	机器人 $k$ 访问一组任务的最优路线长度	§4.2
$\rho$	协调代价比	§4.4
$x_{ij}^k$	0/1 流变量：$k$ 是否从 $i$ 直接去 $j$	§5.2
$d_{ij}$	弧 $(i,j)$ 的行驶代价（两地间，常数）	§5.2
$u_i$	MTZ 位次 / CVRP 累计载量变量	§5.3
$Q,q_j$	机器人容量、任务 $j$ 需求	§5.4
$\pi_j$	列生成中任务 $j$ 的对偶价格	§5.6
$f_k(S)$	机器人 $k$ 完成集合 $S$ 的得分函数	§6.3
$D$	通信图直径（CBBA 收敛 $O(n_tD)$ 轮）	§6.3
$t_\alpha^{s,k},t_\alpha^{e,k}$	机器人 $k$ 动作 $\alpha$ 的开始/结束时间点	§8.2
$\varphi$	LTL 规约公式	§9.3
$\square,\lozenge$	LTL 时序算子：总是、最终	§9.4

知识点总表¶

#	知识点	核心要点	对应节	难度
1	三重耦合	ID/XD/CD，复制粘贴的三种崩法	§2	⭐⭐
2	MRTA 定位	多机 TAMP 住 ST-SR-TA + XD~CD 区	§3.2	⭐⭐⭐
3	难度阶梯	难度由 iTax 级别而非数量决定	§3.4	⭐⭐⭐
4	ID 边际代价	代价非常数、依赖路线（可手算）	§4.2	⭐⭐⭐⭐
5	XD 耦合项	代价多一个 $\xi_{-k}$，破坏可分离性	§4.3	⭐⭐⭐⭐
6	强弱 XD 判据	$\rho$ 区分该分层还是该联合	§4.4	⭐⭐⭐⭐
7	跨层回溯	与 TAMP 任务-运动耦合同构，病根是单向信息流	§4.5	⭐⭐⭐⭐
8	联合 MILP	流变量 + 子环消除（MTZ/DFJ）	§5.3	⭐⭐⭐⭐
9	规模天花板	$O(n^2m)$ 变量，精确解几十任务封顶	§5.5	⭐⭐⭐⭐
10	列生成	惰性加变量（路线列），与 DFJ 惰性加约束同源	§5.6	⭐⭐⭐⭐
11	DMG 与拍卖	子模是 CBBA 收敛前提，对应 ID 物理结构	§6.3	⭐⭐⭐
12	TAMP 感知出价	出价嵌真实规划器，分布式处理 ID	§6.4	⭐⭐⭐
13	拍卖 vs MILP	最优性↔可扩展性/鲁棒性取舍	§6.6	⭐⭐⭐
14	架构谱系	集中/分布/去中心，耦合难度守恒	§7.2	⭐⭐⭐⭐
15	异步精化	不预离散、只在冲突处协调，优于同步 makespan	§7.3	⭐⭐⭐⭐
16	超图分解	按耦合度升维，规模指数→线性	§7.4	⭐⭐⭐⭐
17	冲突基 TAMP	CBS 思想用于 TAMP，独立求解+冲突驱动	§7.5	⭐⭐⭐⭐
18	多机 STN	跨机器人时间边，多机时序载体	§8.2	⭐⭐⭐⭐
19	三类时空冲突	汇合/交接/互斥，约束形态不同	§8.3	⭐⭐⭐⭐
20	任务层↔MAPF 接口	地点+时间窗下行，无解反馈上行	§8.4	⭐⭐⭐⭐
21	时空冲突树	CBS 思想的时序版（冲突基第三次复用）	§8.5	⭐⭐⭐⭐
22	STAP	LTL 下同时分配规划，避免丢可行解	§9.3	⭐⭐⭐⭐
23	多机=单机+协调层	本章是给单机 TAMP 加协调帽子	§10.2	⭐⭐
24	任务层 vs 运动层边界	离散决策归本章，连续执行归 Multi 线	§10.3	⭐⭐

延伸阅读¶

分类学与分配基础（建立坐标系，按推荐顺序）： - Gerkey & Matarić (2004), "A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems," IJRR 23(9):939-954. ⭐⭐ —— MRTA 三维分类学奠基，本章 §3 的地图。 - Korsah, Stentz & Dias (2013), "A Comprehensive Taxonomy for Multi-Robot Task Allocation," IJRR 32(12):1495-1512. ⭐⭐⭐ —— iTax 依赖维度（ND/ID/XD/CD），本章 §3-§4 的核心轴。 - Choi, Brunet & How (2009), "Consensus-Based Decentralized Auctions for Robust Task Allocation," IEEE T-RO 25(4):912-926. ⭐⭐⭐ —— CBBA 原文，DMG/50% 界，本章 §6 的基础。

联合优化与路径（集中式求解）： - Toth & Vigo (2014), Vehicle Routing: Problems, Methods, and Applications, SIAM. ⭐⭐⭐ —— VRP/CVRP 与列生成的标准参考，本章 §5 的运筹学背景。 - Sharon et al. (2015), "Conflict-Based Search for Optimal Multi-Agent Pathfinding," Artificial Intelligence 219:40-66. ⭐⭐⭐ —— CBS 原文，本章 §7.5/§8.5 的思想源头（细节见 Multi 线）。

多机 TAMP 前沿（研究方向，近五年）： - Sung, Shome & Stone (2024), "Asynchronous Task Plan Refinement for Multi-Robot Task and Motion Planning," ICRA. ⭐⭐⭐⭐ —— 异步精化（隐式时间 + 最小协调），本章 §7.3。 - Motes, Chen, Bretl, Morales & Amato (2023), "Hypergraph-based Multi-Robot Task and Motion Planning," IEEE T-RO 39(5):4166-4186（及后续 DaSH / Lazy-DaSH, 2024）. ⭐⭐⭐⭐ —— 超图分解，规模指数→线性，本章 §7.4。 - "Conflict-Based Task and Motion Planning for Multi-Robot, Multi-Goal Problems" (2024), ICRA. ⭐⭐⭐⭐ —— 冲突基 TAMP，本章 §7.5。

时序逻辑下的分配与规划（CD 形式化）： - Schillinger, Bürger & Dimarogonas (2018), "Simultaneous Task Allocation and Planning for Temporal Logic Goals in Heterogeneous Multi-Robot Systems," IJRR 37(7):818-838. ⭐⭐⭐⭐ —— STAP 奠基，本章 §9 的核心。 - Chen & Kan (2025), "Real-time reactive task allocation and planning of large heterogeneous multi-robot systems with temporal logic specifications," IJRR. ⭐⭐⭐⭐ —— 实时反应式 STAP，本章 §9.5。 - "Simultaneous Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications" (2024, arXiv). ⭐⭐⭐⭐ —— 分层时序逻辑 STAP，本章 §9.5。

本章与后续章节的关系¶

后续/相关章节	关系	本章为它铺垫的知识点
T9 长时域移动操作综合实战	整合收尾	本章的多机联合层是 T9 全栈集成的一块；T9 把单机/多机/执行整合成可运行系统
Multi 线《任务分配与路径规划》	运动层接口	本章 §8.4 把分配结果（地点+时间窗）下放给该章的 MAPF（CBS/PIBT/EECBS）求无碰撞路径
Multi 线《分布式 MPC 多足编队》	运动层下游	本章产出任务+时序，该章产出多机无碰撞协调控制
Multi 线《协同搬运与力控》	CD 任务的执行	本章 §8 排出协作搬运的汇合约束，该章实现搬运时的力分配与力控
Multi 线《MARL 多机运动协调》	学习式运动层	本章是符号/优化式任务层，该章是学习式运动层，二者上下游
T5 行为树与执行监控	执行层	本章 §9.5/§12 的反应式重分配接行为树的执行监控与失败恢复
T2 任务规划与任务分配	直接前置	本章把 T2 §9（分配-规划耦合纲要）展开成完整多机联合方法论

本章在 TAMP 线的位置：本章（T8）是 TAMP 线的进阶分支之一（与 T6 不确定性、T7 大模型并列），沿"执行者数量"轴推广 T1-T4 的单机 TAMP，向下接 Multi 线的运动/控制层。学完本章，建议走 T9 把单机/多机/执行整合，或转 Multi 线深入运动层协调。

🔧 故障排查手册¶

症状	可能原因	排查步骤	相关节
分配看着合理，实际总里程超预期 30%+	用了直线距离当代价（ND 假设），未处理 ID 顺路	1. 检查出价是否用真实路线边际 2. 换 `marginal_cost`（§11.3）3. 对比改前改后里程	§4.2, 陷阱 4-1
分配最优但执行时机器人撞车/死锁	只处理了分配（ID），没接 MAPF（XD）、没处理时序	1. 确认分配后有 MAPF 协调步 2. 检查是否建了多机 STN 3. 用 STN 一致性预检死锁	§8.4, 陷阱 4-2
MILP 几十任务就求不出来	NP-hard，$O(n^2m)$ 变量超求解器能力	1. 设 MIP gap 容差和时限 2. 转列生成或滚动时域 3. 退到 CBBA	§5.5, 陷阱 5-2
MILP 解里有脱离 depot 的孤立环	漏了子环消除约束	1. 检查是否加了 MTZ (5.5) 或 DFJ (5.6) 2. 按机器人画弧验证每条链回 depot	§5.3, 陷阱 5-1
CBBA 在某些问题上不收敛/震荡	得分函数非子模（含协作任务，违反 DMG）	1. 检查式 (6.1) 是否成立 2. 确认无超可加协作任务 3. 含 CD 改用 STAP	§6.3, 陷阱 6-1
解耦+迭代修正循环不停	无收敛判据，在两方案间振荡	1. 加轮数上限 2. 加"分配不变即停" 3. 振荡时取历史最优	§11, 陷阱 11-3
协作搬运任务执行时把工件弄翻/拉裂	汇合（同时）约束写成了交接（先后），或没加同步约束	1. 确认协作任务有近似等时约束（§8.3）2. 检查是否误用偏序	§8.3, 陷阱 8-2
LTL 多机任务报"无可行计划"	先分配排除了跨机器人接力的可行解	1. 确认用 STAP 而非先分配 2. 检查分解是否保留接力 3. 改自动机联合搜索	§9.2, 陷阱 9-1
联合几何精化在 3-4 台机器人就爆	集中式联合构型空间随机器人数指数膨胀	1. 评估耦合度 2. 弱耦合用超图分解/异步 3. 只在高耦合局部用集中式	§7.2, 陷阱 7-1

API 与方法速查表¶

OR-Tools 路由库（mTSP/CVRP，§5 的工程求解器）：

from ortools.constraint_solver import pywrapcp, routing_enums_pb2
# 创建路由模型: num_tasks 个节点, num_robots 辆"车", depot 索引
manager = pywrapcp.RoutingIndexManager(num_nodes, num_robots, depot_index)
routing = pywrapcp.RoutingModel(manager)
# 注册弧代价回调(返回 d_ij, 即 §5.2 的弧代价)
transit_idx = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)
# 加容量维度(CVRP, §5.4): 需求回调 + 容量上界 Q
routing.AddDimensionWithVehicleCapacity(demand_idx, 0, [Q]*num_robots, True, "Capacity")
# 求解(子环消除由库内部处理, 无需手写 MTZ/DFJ)
params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
solution = routing.SolveWithParameters(params)

核心方法速查：

方法	输入	输出	复杂度	适用
匈牙利（T2 §7）	代价矩阵（ND）	最优一对一分配	$O(n^3)$	ST-SR-IA, ND
MILP 联合（§5）	弧代价 + 容量	全局最优分配+路由	NP-hard（几十任务）	小规模, 要最优
列生成（§5.6）	路线列 + 对偶	大规模线性松弛最优	迭代（定价 DP）	中大规模
SSI（§6, §11.3）	边际代价函数	序贯分配	$O(n^2m\cdot\text{TSP})$	ID, 集中
CBBA（§6, Multi 线）	得分函数（子模）	分布式无冲突分配	$O(n_tD)$ 轮通信	ID, 分布, 大规模
MAPF/CBS（Multi 线）	起终点	无碰撞时空路径	指数（最优）/多项式（PIBT）	XD 路径协调
多机 STN 检查（§8）	时间点+跨机器人边	一致性/死锁判定	$O(VE)$ Bellman-Ford	时序协调
STAP（§9）	LTL 公式 + 团队	联合分配+计划	自动机搜索（分解控规模）	CD, LTL 规约

研究实践建议¶

给初学者（先建立选型直觉）： - 先把 §3.3 的定位流程图练熟——拿到任何多机问题，先钉 iTax 坐标，再选方法。这是不拿错工具的前提。 - 动手实现 §11.3 的最小循环，亲手验证"边际代价 vs 直线距离"的里程差距（陷阱 4-1）。这比读十遍 ID 定义都管用。 - 把"多机 = 单机 + 协调层"（§10.2）刻进脑子——本章不是新系统，是给单机 TAMP 加协调帽子。

给进阶者（深入方法内核）： - 吃透"惰性/按需 + 冲突驱动"这条暗线（DFJ 割、列生成、异步协调、超图、冲突基都是它）——理解了这个元思想，本章的可扩展方法就融会贯通了。 - 对照实现 §5 MILP 和 §6 CBBA，在同一实例上量化最优性↔可扩展性取舍（§6.6），建立"什么规模用什么"的工程判断。 - 精读三篇前沿（Sung-Shome-Stone 异步、Motes 超图、Schillinger STAP），看它们各自如何"识别解耦结构、只为真耦合付代价"。

给研究者（找问题）： - 强 XD（§4.4 $\rho$ 大）下的高效联合求解仍是开放问题——精确 MILP 不可扩展、分布式拍卖处理不了强 XD，中间地带值得探索。 - CD（协作 + 分解）的分布式 STAP 是前沿——Schillinger 是集中式，大规模异构的分布式实时 STAP（Chen-Kan 2025 方向）刚起步。 - 学习式多机 TAMP（用 GNN/RL 学分配启发式、学冲突消解顺序）是新兴交叉，接 Multi 线 MARL 和 T7 大模型。

版本信息速查¶

项目	版本/出处	说明
本章定位	TAMP 线 T8（进阶分支）	沿执行者数量轴推广 T1-T4，接 Multi 线
MRTA 分类学	Gerkey-Matarić 2004 (IJRR 23(9))	ST/MT×SR/MR×IA/TA 三维
iTax 依赖维度	Korsah-Stentz-Dias 2013 (IJRR 32(12))	ND/ID/XD/CD 四级
CBBA	Choi-Brunet-How 2009 (IEEE T-RO 25(4))	收敛 $O(n_tD)$ 轮，50% 界（子模）
CBS	Sharon et al. 2015 (AIJ 219)	约束树 + 单体 A*，本章只对接
异步精化	Sung-Shome-Stone 2024 (ICRA)	hybrid CSP，隐式时间，优于同步 makespan
超图分解	Motes et al. 2023 (IEEE T-RO) + Lazy-DaSH 2024	规模指数→线性
冲突基 TAMP	ICRA 2024	CBS 思想用于多机多目标 TAMP
STAP	Schillinger-Bürger-Dimarogonas 2018 (IJRR 37(7))	LTL→Büchi，分解 + 团队搜索，约快 25%
实时反应式 STAP	Chen-Kan 2025 (IJRR)	大规模异构在线 STAP
工程求解器	OR-Tools（路由）、Gurobi/CPLEX（MILP）、Spot（LTL）	§11.2 工具谱
累积项目	Mini-TAMP 多机联合层	§12，挂接 T1-T4 单机 TAMP

任务数 \(n\)	流变量数 \(\approx n^2m\)	MTZ 约束 \(\approx n^2\)	精确求解可行性
10	\(\approx 300\)	\(\approx 100\)	秒级求出最优 ✓
30	\(\approx 2{,}700\)	\(\approx 900\)	分钟级，仍可行 ✓
50	\(\approx 7{,}500\)	\(\approx 2{,}500\)	几分钟到数十分钟，临界 △
100	\(\approx 30{,}000\)	\(\approx 10{,}000\)	数小时～求不出 ✗
200	\(\approx 120{,}000\)	\(\approx 40{,}000\)	实际不可行 ✗✗

轮	主问题里的列（路线）	解出的对偶价格 \(\pi\)	定价找到的新列（简约代价）	动作
0	\(\{1\},\{2\},\{3\}\) 三条单任务路线	\(\pi_1{=}4,\pi_2{=}4,\pi_3{=}9\)	路线 \(\{1,2\}\)：\(c{=}5.2\)，简约代价 \(5.2-4-4=-2.8<0\)	加入 \(\{1,2\}\)
1	上 + \(\{1,2\}\)	\(\pi_1{=}3,\pi_2{=}2.2,\pi_3{=}9\)	路线 \(\{1,2,3\}\)：简约代价 \(-1.5<0\)	加入 \(\{1,2,3\}\)
2	上 + \(\{1,2,3\}\)	更新	定价：所有候选简约代价 \(\ge 0\)	停！线性松弛最优

算子	读法	含义	仓库例子
\(\lozenge\varphi\)	eventually（最终）	未来某时刻 \(\varphi\) 成立	\(\lozenge\,\mathrm{at\_office}\)：最终到办公室
\(\square\varphi\)	always（总是）	所有时刻 \(\varphi\) 都成立	\(\square\,\neg\mathrm{collide}\)：永不碰撞（安全性）
\(\varphi\,\mathcal{U}\,\psi\)	until（直到）	\(\varphi\) 一直成立直到 \(\psi\) 成立	\(\mathrm{stamped}\,\mathcal{U}\,\mathrm{delivered}\) 之前要保持已盖章状态
\(\square\lozenge\varphi\)	总是最终（活性）	无限次地 \(\varphi\) 成立	\(\square\lozenge\,\mathrm{at\_A}\)：无限次巡逻到 A

符号	含义	首次出现
\(\mathcal{R},\mathcal{T}\)	机器人集合、任务集合	§2.4
\(a:\mathcal{T}\to 2^{\mathcal{R}}\)	分配（任务→机器人子集，子集>1 表协作）	§2.4
\(\sigma_k\)	机器人 \(R_k\) 的任务序列	§2.4
\(\xi_k(t)\)	机器人 \(R_k\) 的连续轨迹	§2.4
\(\xi_{-k}\)	除 \(k\) 外所有机器人的轨迹（XD 耦合项）	§4.3
\(\Delta c_k(\tau\mid S)\)	边际代价函数	§4.2
\(\mathrm{route}_k(\cdot)\)	机器人 \(k\) 访问一组任务的最优路线长度	§4.2
\(\rho\)	协调代价比	§4.4
\(x_{ij}^k\)	0/1 流变量：\(k\) 是否从 \(i\) 直接去 \(j\)	§5.2
\(d_{ij}\)	弧 \((i,j)\) 的行驶代价（两地间，常数）	§5.2
\(u_i\)	MTZ 位次 / CVRP 累计载量变量	§5.3
\(Q,q_j\)	机器人容量、任务 \(j\) 需求	§5.4
\(\pi_j\)	列生成中任务 \(j\) 的对偶价格	§5.6
\(f_k(S)\)	机器人 \(k\) 完成集合 \(S\) 的得分函数	§6.3
\(D\)	通信图直径（CBBA 收敛 \(O(n_tD)\) 轮）	§6.3
\(t_\alpha^{s,k},t_\alpha^{e,k}\)	机器人 \(k\) 动作 \(\alpha\) 的开始/结束时间点	§8.2
\(\varphi\)	LTL 规约公式	§9.3
\(\square,\lozenge\)	LTL 时序算子：总是、最终	§9.4

耦合	形式化表述	数学后果	对应崩法	本章
分配-规划耦合 (ID)	任务 \(\tau_j\) 分给 \(R_k\) 的代价 \(c_{kj}\) 不是常数，而是 \(c_{kj}=f(\sigma_k,\xi_k)\)——依赖 \(R_k\) 的整个序列与路线	代价矩阵不再固定，匈牙利失效，问题变 NP-hard (mTSP/CVRP)	崩法一	§4-§6
时空耦合 (XD)	\(R_k\) 的轨迹可行性 \(\text{feasible}(\xi_k)\) 依赖其他机器人轨迹：\(\xi_k \cap \xi_l=\varnothing\ (\forall l\neq k)\)，含时间	单机"无碰撞"不充分，需联合或事后协调 (MAPF)	崩法二	§8
协作同步耦合 (CD)	协作任务 \(\tau_j\)（\(\lvert a(\tau_j)\rvert>1\)）要求多台机器人在同一时间窗到达约定构型	引入跨机器人时序约束，序列不能独立排	崩法三	§3, §8

方案	\(R_1\) 路线	\(R_2\) 路线	总代价	相对最优
甲（直线距离贪心）	\(D\to p_1\to p_2\to D=4\)	\((10,0)\to p_3\to p_4\to D=10\)	14	+40%
乙（联合最优，看顺路）	不出动 \(=0\)	\((10,0)\to p_3\to p_4\to p_2\to p_1\to D=10\)	10	最优

量	数目	说明
流变量 \(x_{ij}^k\)	\(O(n^2 m)\)	每对节点 × 每台机器人
位次/载量变量 \(u_i\)	\(O(n)\)	每个任务一个
MTZ 约束	\(O(n^2)\)	每对任务一条
DFJ 割（若全展开）	\(O(2^n m)\)	每个子集每台机器人——故必须惰性

类型	定义	时序约束形态	iTax	例子
汇合 (rendezvous)	多台机器人必须在同一时间窗到达约定构型	\(\lvert t_\alpha^{e,k}-t_\beta^{e,l}\rvert\le \epsilon\)（几乎同时）	CD	两台臂同时抓住桌子两端才能抬
交接 (handoff)	一台机器人完成后另一台才能开始（物料/位置传递）	\(t_\beta^{s,l}\ge t_\alpha^{e,k}\)（严格先后）	XD/CD	\(R_1\) 把件放到中转台后 \(R_2\) 才来取
资源互斥 (mutex)	同一时刻只能有一台机器人占用某资源（空间/工具）	时间区间不重叠：\([t_\alpha^{s,k},t_\alpha^{e,k}]\cap[t_\beta^{s,l},t_\beta^{e,l}]=\varnothing\)	XD	窄道/路口/单件工具同一时刻只容一台