TAMP_T2 任务规划与任务分配 (Task Planning and Task Allocation)¶

难度: ⭐ ~ ⭐⭐⭐⭐ (逐级递进) 前置知识: TAMP_T1（STRIPS/PDDL/FF、Garrett 2021 分类）、A* 与可容许启发式、二部图匹配、整数规划基本概念 核心参考: Gerkey & Matarić (2004, IJRR); Korsah et al. (2013, IJRR); Nau et al. (2003, JAIR); Choi et al. (2009, IEEE T-RO) 与既有章节的关系: 本章是 TAMP_T1 第 3 节"经典任务规划"的纵深扩展，同时为多机任务分配补上 Multi_03（50_多机器人协作/40_任务分配与路径规划.md）所缺的理论骨架。

0. 前置自测¶

开始本章之前，请完成下面四道自测题。这些题目检验本章依赖的两类基础——符号规划（来自 TAMP_T1）与组合优化（来自数学基础）。如果有两道以上答不出来，建议先回到对应前置章节。

#	问题	期望掌握程度	答不出来回到
Q1	PDDL 的 domain 文件和 problem 文件分别描述什么？一个动作 (action) 由哪三部分定义？	能区分两个文件、写出动作的前提/正效果/负效果	TAMP_T1 §3.3
Q2	A* 的评价函数 $f(n)=g(n)+h(n)$ 中，启发式 $h(n)$ 满足什么条件时 A* 保证最优？这个条件叫什么？	能说出"可容许 (admissible)"并解释	TAMP_T1 §0、A* 基础
Q3	给定 $n$ 个工人、$n$ 项工作和一张 $n\times n$ 的代价矩阵，要求每个工人做且只做一项工作、每项工作被且只被一个工人做，使总代价最小——这是什么经典问题？它能在多项式时间内解出最优吗？	能识别"线性指派问题"并知道它多项式可解	组合优化基础
Q4	TAMP_T1 中指出"先做完整任务规划、再逐步检查运动可行性"这种朴素做法有什么致命缺陷？	能说出"指数级回溯"并解释信息不流动	TAMP_T1 §2.4

参考答案 (点击展开)

**Q1**: domain 文件描述"游戏规则"——类型 (types)、谓词 (predicates)、动作模板 (action schemas)；problem 文件描述"具体一局"——对象 (objects)、初始状态 (init)、目标 (goal)。一个动作由三部分定义：前提条件 $\text{Pre}$（执行前必须为真的命题集合）、正效果 $\text{Eff}^+$（add list，执行后变真的命题）、负效果 $\text{Eff}^-$（delete list，执行后变假的命题）。 **Q2**: 当 $h(n)$ **可容许 (admissible)** 时——即 $h(n)$ 永不高估从 $n$ 到目标的真实最优代价 $h^*(n)$，对所有 $n$ 有 $0 \le h(n) \le h^*(n)$——A* 保证找到最优解。一个更强的条件是**一致性 (consistency / monotonicity)**：$h(n) \le c(n, n') + h(n')$，一致必然可容许。 **Q3**: 这是**线性指派问题 (Linear Assignment Problem, LAP)**，也叫**二部图最小权完美匹配**。它能在多项式时间内解出全局最优——**匈牙利算法 (Hungarian / Kuhn-Munkres)** 的复杂度是 $O(n^3)$。这一点在本章 §7 是任务分配理论的基石：最简单的那类多机任务分配恰好等价于 LAP。 **Q4**: 致命缺陷是**指数级回溯 (exponential backtracking)**。任务规划器和运动规划器之间没有信息流动——运动规划器只回报"失败"，不告诉任务规划器"为什么失败"，所以任务规划器无法针对性修正，只能盲目换方案。$n$ 步计划、每步 $k$ 种失败原因，最坏要试 $O(k^n)$ 种组合。这个"解耦两层、单向检查"的反面教材，在本章 §9 会以另一种面貌重现：**先分配再规划**同样会陷入回溯。

1. 本章目标¶

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

区分运动规划之上的两类决策——任务规划 (task planning：做什么、按什么顺序) 与任务分配 (task allocation：谁来做)——并说清它们与运动规划构成的三层决策栈。
解释经典规划启发式的来源：从删除松弛 (delete relaxation) 推导出 $h^{\max}$、$h^{\text{add}}$、$h^{\text{FF}}$，理解地标 (landmark) 与抽象 (abstraction) 启发式各自的思路。
编写一个分层任务网络 (HTN) 的方法 (method) 分解，并说明 HTN 相对 STRIPS 在表达力与搜索效率上的取舍。
建模带时长与时序约束的规划问题：写出 durative action，用简单时序网络 (STN) 做一致性检查。
使用 Gerkey-Matarić 分类学 (ST/MT × SR/MR × IA/TA) 与 Korsah iTax 的依赖维度，给一个具体的多机任务正确归类，并据此选择求解方法。
实现两条任务分配主线：用匈牙利算法解线性指派、用 MILP 建模带约束的分配；用序贯单物品拍卖做分布式分配。
诊断规划与分配解耦带来的回溯陷阱，理解为什么需要联合 (joint) 求解，并把分配层接到 TAMP_T1 的 Mini-TAMP 上。

本章知识导航¶

本章围绕一个根问题展开：给定一个高层目标和一组执行者，决定"做什么、谁来做、按什么顺序"——这正是坐落在运动规划之上的"决策层"。这个根问题天然分成两根主干：

                       决策层：做什么 / 谁来做 / 什么顺序
                                    │
              ┌─────────────────────┴─────────────────────┐
              │                                            │
        【主干 A：任务规划】                         【主干 B：任务分配】
      单个执行者把目标分解为有序动作                把任务集合分给多个执行者
              │                                            │
   §3 经典规划深化（启发式从哪来）           §6 MRTA 分类学（问题有多难）
   ├─ 状态空间 vs 规划空间搜索               ├─ Gerkey-Matarić: ST/MT×SR/MR×IA/TA
   ├─ 删除松弛: h^max / h^add / h^FF         └─ Korsah iTax: ND/ID/XD/CD 依赖维度
   └─ 地标 / 抽象 启发式                              │
              │                            §7 优化式分配（要最优、规模小）
   §4 分层任务网络 HTN（用配方分解）         ├─ 线性指派 = 匈牙利算法 O(n³)
   ├─ compound/primitive/method             └─ 一般情形 = ILP/MILP 建模
   └─ SHOP2 有序分解 + 表达力对比                     │
              │                            §8 市场式分配（要分布式、规模大）
   §5 时序与数值规划（加时间与资源）          ├─ 单物品 / 序贯单物品拍卖 SSI
   ├─ PDDL 2.1 durative action              ├─ 组合拍卖（表达协同价值）
   └─ STN 一致性 + 数值流                    └─ CBBA（衔接 Multi_03）
              │                                            │
              └──────────────────┬─────────────────────────┘
                                 │
                    §9 规划 ↔ 分配的耦合（为什么不能解耦）
                    ├─ 解耦的回溯陷阱（plan-then-check 重现）
                    ├─ 联合分配+排序（VRP/TSP 视角）
                    └─ 接口：分配 → 每机器人各自跑 TAMP
                                 │
                    §10 工程实践 + §11 累积项目（多机分配层）

怎么读这张图：左边主干 A 是"一个聪明的大脑如何独自规划"，右边主干 B 是"一群大脑如何分工"。两根主干在 §9 汇合——因为真实机器人系统里，"谁来做"和"做什么、什么顺序"是纠缠的，不能先后解耦。§3 接续 TAMP_T1 的经典规划，§8 接续 Multi_03 的 CBBA，其余小节是新内容。

主干与分支：⭐⭐ 是必须掌握的主干（§2 决策栈、§3 删除松弛启发式、§6 分类学、§7 匈牙利+MILP）；⭐⭐⭐ 是进阶分支（§4 HTN、§5 时序、§8 拍卖）；⭐⭐⭐⭐ 是研究级（§9 联合求解）。第一遍可沿主干走，分支按需深入。

前置知识桥接¶

本章站在三块基石上，这里各用几行重新激活，读者不必翻回去也能跟上。

回顾 TAMP_T1 §2-§3：符号规划与"为什么需要 TAMP"。 TAMP_T1 指出机器人操作有两个层面——任务层（离散符号，回答"先做什么"）与运动层（连续构型空间，回答"怎么动过去"），二者之间横着一道"符号世界 vs 几何世界"的鸿沟。它还给出了经典任务规划的入门：STRIPS 用命题集合描述状态、用前提/效果定义动作；PDDL 把规划问题拆成 domain 与 problem 两个文件；FF 规划器用"松弛计划"做启发式。本章的主干 A 正是从这里往下挖——FF 的松弛计划只是冰山一角，§3 会讲清这类启发式背后统一的"删除松弛"原理，再往上扩展到 HTN 与时序规划。

回顾 TAMP_T1 §2.4：plan-then-check 的回溯陷阱。 TAMP_T1 用"先任务规划、再逐步检查运动"的朴素做法演示了一个反面教材：两层解耦、信息单向流动，导致指数级回溯。这个教训是本章 §9 的伏笔——把"任务 vs 运动"换成"分配 vs 规划"，同样的陷阱会重现。

回顾 Multi_03：CBBA 与 MAPF。 多机器人协作章节里，Multi_03 讲过分布式任务分配的代表算法 CBBA（基于共识的捆绑拍卖）与多智能体路径规划 CBS/LaCAM。那一章是从"多机路径规划"的应用角度切入的。本章 §6-§8 补上它缺失的理论骨架：任务分配作为一个问题族有完整的分类学（Gerkey-Matarić），CBBA 只是其中"时间扩展分配 + 分布式"那一格的一个解法。读完本章再回看 Multi_03，会发现 CBBA 在整张地图上的精确坐标。

如果跳过本章会怎样¶

场景一（只学了 TAMP_T1）：你能写出 pick-and-place 的 PDDL，但当任务变长（整理一整个房间、十几个物体）时，FF 规划器搜索爆炸、跑几分钟出不来。你不知道这是因为平铺的状态空间搜索没有利用任务的层次结构——而 HTN（§4）正是为此而生。
场景二（只学了 Multi_03 的 CBBA）：你会用 CBBA 做分布式分配，但遇到"任务有先后依赖""一个任务要两台机器人合作""需要全局最优解"时，你不知道 CBBA 不适用，也不知道该换匈牙利（§7）还是 MILP（§7）还是别的。缺了分类学（§6），你只有锤子，看什么都像钉子。

预计阅读时间¶

模式	覆盖范围	预计时间
精读	全部小节 + 推导 + 代码复现 + 练习	18-24 小时（约 1 周）
速读	§2/§3/§6/§7 主干 + 跳过 §4/§5/§8 代码细节	6-8 小时
速查	知识导航图 + §6 分类表 + §9 决策树 + 各节小结	1.5-2 小时

2. 决策层全景：规划、分配与运动 ⭐¶

2.1 动机：一个仓库的早晨¶

先把抽象的"决策层"落到一个具体场景，整章都会回到它。

某个小型仓库，早班开始。有 3 台移动机器人 $R_1, R_2, R_3$ 停在充电桩，5 个包裹 $p_1, \dots, p_5$ 散落在不同货架上，需要全部搬到打包台。听上去简单，但要让机器人自主完成，至少要回答三个层次完全不同的问题：

层次	这一层要回答的问题	在仓库场景里的具体形态
谁来做	5 个包裹分给 3 台机器人，怎么分？	$R_1$ 负责 $\{p_1,p_4\}$、$R_2$ 负责 $\{p_2,p_5\}$、$R_3$ 负责 $\{p_3\}$？还是别的分法？
做什么、什么顺序	单台机器人拿到自己的包裹清单后，动作怎么排？	$R_1$ 先去取 $p_1$ 还是 $p_4$？取完一个就送、还是两个都抓在手上一起送？
怎么动过去	每个"去取 $p_1$"具体怎么走、怎么抓？	从当前位姿到 $p_1$ 货架的无碰撞路径、抓取姿态、电机指令

这三层从上到下是 任务分配 → 任务规划 → 运动规划。它们的难点性质截然不同：

最底层"怎么动过去"是连续空间问题——构型空间里找无碰撞路径，这是 TAMP_T1 §4 复习过的 RRT/PRM 干的活。
中间层"做什么、什么顺序"是单体的离散序列决策——给定一台机器人和一组子目标，排出有序动作，这是经典任务规划。
最上层"谁来做"是多体的离散分配决策——把任务集合切分给执行者集合，这是任务分配。

本质洞察：运动规划回答"已知起点和终点，怎么过去"，但它回答不了"起点和终点应该是什么"。任务规划回答"一台机器人的子目标序列应该是什么"，但回答不了"这些子目标该归谁"。每一层都在为下一层生成问题实例——分配层产出"每台机器人的任务清单"，规划层把清单变成"动作序列"，运动层把每个动作变成"轨迹"。决策层的本质，就是一条把模糊的高层意图逐级具体化为可执行轨迹的流水线。

2.2 三层决策栈¶

把上面的直觉画成一张栈图，并标出每层的输入、输出与典型方法：

┌──────────────────────────────────────────────────────────────┐
│  任务分配 (Task Allocation)            「谁来做」               │
│  输入: 任务集合 T + 执行者集合 R + 代价/收益                    │
│  输出: 分配 a: T → R（每个任务归谁，可能含顺序）               │
│  方法: 匈牙利 / MILP（集中、最优）· 拍卖 / CBBA（分布、可扩展） │
│  本章 §6-§8                                                    │
└───────────────────────────┬──────────────────────────────────┘
                            │ 每台机器人拿到自己的任务清单
                            ▼
┌──────────────────────────────────────────────────────────────┐
│  任务规划 (Task Planning)              「做什么·什么顺序」      │
│  输入: 单体的初始状态 + 目标 + 动作模型 (PDDL/HTN)             │
│  输出: 有序（或偏序）动作序列 π = [a₁, a₂, ...]                │
│  方法: 启发式状态空间搜索 (FF/LAMA) · HTN (SHOP2) · 时序规划   │
│  本章 §3-§5，入门见 TAMP_T1 §3                                 │
└───────────────────────────┬──────────────────────────────────┘
                            │ 每个符号动作需要一段可行轨迹
                            ▼
┌──────────────────────────────────────────────────────────────┐
│  运动规划 (Motion Planning)            「怎么动过去」           │
│  输入: 构型空间 + 起止构型 + 障碍                              │
│  输出: 无碰撞轨迹 q(t)                                         │
│  方法: RRT/PRM/CHOMP（TAMP_T1 §4）                            │
└──────────────────────────────────────────────────────────────┘

这张栈图有一个容易误读的地方：它画成了自上而下的单向箭头，好像可以"分配完交给规划、规划完交给运动"层层下放。真实系统不是这样的——下层的失败必须反馈回上层。运动规划报告"这个抓取够不到"，规划层就得换动作；规划层报告"这台机器人完不成这份清单"，分配层就得重分。TAMP_T1 §2.4 已经讲过任务层与运动层之间这种反馈一旦缺失就会指数回溯；本章 §9 会讲分配层与规划层之间同样的故事。所以更准确的图景是：三层之间是双向耦合的，单向下放只是教学上的简化。

为什么本章从"运动规划之上"切入。 移动规控大纲的绝大多数章节（时空规划 T、采样 MPPI、不确定性 U、博弈 G）都在最底层那个框里——它们把"怎么动过去"做到极致。本章和 TAMP 系列则抬头看上面两层。这不是说上层比下层重要，而是说一个完整的自主系统两者都要有：再好的轨迹优化器，也需要有人告诉它"优化到哪里去"。

2.3 为什么把"规划"和"分配"放在一章¶

读者可能会问：任务规划是单体的序列决策，任务分配是多体的指派决策，看起来是两个独立话题，为什么合在一章？三个理由。

理由一：它们是同一层的两半。 二者都坐落在运动规划之上、都处理离散决策（动作要不要选、任务归不归你，都是离散的取舍），都不碰连续轨迹。把它们放在一起，读者才能看清"决策层"的完整版图，而不是把任务规划当成 TAMP 的附属、把任务分配当成多机的附属。

理由二：它们在数学上同源。 任务规划的核心是搜索（在状态/动作空间里找一条到目标的路径），任务分配的核心是优化（在所有可能的指派里找代价最小的）。但搜索与优化的边界是模糊的：带代价的最优规划本身就是一个优化问题，而分配里的序贯拍卖本质上是一种贪心搜索。§3 的启发式搜索和 §7 的整数规划，会让你看到"搜索"与"优化"是一枚硬币的两面。

理由三——最关键：它们在工程上耦合。 这是 §9 的主题，这里先埋下：你不能"先把包裹分给机器人，再让每台机器人各自规划"，因为分配的好坏取决于规划的结果。把 $p_1$ 分给 $R_1$ 划不划算，要看 $R_1$ 规划出来的路线有多长——而路线又取决于 $R_1$ 还被分了哪些别的包裹（顺路就便宜，绕路就贵）。分配需要规划的代价信息，规划又依赖分配的结果，这是一个鸡生蛋的循环。 只讲一半，就看不到这个循环。

本质洞察：任务规划和任务分配的关系，恰如"一个人怎么安排自己的一天"和"一个团队怎么分工"。它们看似一个是个人问题、一个是组织问题，但任何当过项目负责人的人都知道：分工的好坏，取决于每个人能把分到的活安排得多高效；而每个人怎么安排，又取决于他被分到了哪些活。两者必须一起想——这就是本章把它们合写的根本原因。这个类比像的地方：分工与个人安排的相互依赖，精确对应分配与规划的耦合（§9 的主题）。不像的地方：人类团队成员能主动沟通协商、临场调整，而机器人系统里"分工"和"安排"是两个算法模块，它们之间的信息交换必须由工程师显式设计成接口（§10.4）——耦合不会自动发生，这正是任务层工程的难点所在。

2.4 与 TAMP_T1、Multi_03 的精确边界¶

为避免和既有章节重复，这里明确画出本章的"领地"。

主题	TAMP_T1 讲到哪	Multi_03 讲到哪	本章的增量
经典任务规划	STRIPS→PDDL→FF 松弛计划（§3，作为 TAMP 上层引擎，压缩讲）	未涉及	启发式的统一原理（删除松弛）、状态空间 vs 规划空间、地标/抽象启发式（§3）
分层 / 时序规划	未涉及	未涉及	HTN（§4）、时序与数值规划（§5）全新
任务分配理论	未涉及	CBBA、CBS（从多机路径规划角度，无分类学）	MRTA 分类学（§6）、匈牙利/MILP（§7）全新
拍卖式分配	未涉及	CBBA（直接给算法）	拍卖家族全景（单物品/序贯/组合，§8），把 CBBA 安放进分类学
规划-分配耦合	任务-运动耦合（§5-§6）	未涉及	分配-规划耦合（§9）全新，与 TAMP 的接口

一句话概括边界：TAMP_T1 把任务规划当"黑盒引擎"用，本章打开引擎；Multi_03 把 CBBA 当"现成工具"用，本章给出工具所在的整张地图。

⚠️ 常见陷阱¶

陷阱 2-1（概念误区）：把任务分配等同于多机路径规划 (MAPF)。 - 错误描述：认为"多机器人 + 任务"就是 MAPF，套 CBS 就完事。 - 现象/后果：遇到"任务有先后依赖""任务需要多机协作""单机多任务排序"时，CBS 框架套不进去，硬套则建模严重失真。 - 根本原因：MAPF 只解决"已知每台机器人的起点终点，如何无碰撞地走"——它是分配之后、且任务彼此独立时的子问题。任务分配是更上游、更一般的问题：先决定"谁去哪"，MAPF 才有起终点可走。 - 正确做法：先用 §6 的分类学判断问题属于哪一格，再决定是否需要 MAPF。MAPF 对应"分配已定 + 任务独立"的特例；一般任务分配要用 §7/§8 的方法。

陷阱 2-2（思维陷阱）：以为决策三层可以严格自上而下、互不反馈。 - 错误描述：把 §2.2 的栈图理解成"分配→规划→运动"的单向流水线，每层独立干完交给下一层。 - 现象/后果：系统在仿真里看着能跑，一旦下层（运动）失败，整个流水线卡死或从头重来，效率极低。 - 根本原因：忽略了层间的失败反馈。下层的不可行性（够不到、走不通、来不及）携带着上层必须知道的信息。 - 正确做法：从设计之初就预留反馈通道。最简单的形态是"下层失败→上层加约束重规划"，更高级的形态见 §9 的联合求解与 TAMP_T1 §6-§7 的集成策略。

陷阱 2-3（概念误区）：认为有了大模型 (LLM) 就不需要分这几层了。 - 错误描述：既然 LLM 能直接"理解任务并输出步骤"，三层栈是不是过时了？ - 现象/后果：直接让 LLM 输出动作序列，在简单任务上看似可行，但在需要严格可行性保证、最优性或大规模分配时，输出不可靠、无法验证。 - 根本原因：LLM 擅长生成符号层的候选（像一个有常识的任务规划器），但它不做几何可行性检查、不解组合优化、不保证最优。它能替代或增强其中某一层（尤其是任务规划层的启发式），但替代不了整个栈的可验证性。TAMP_T1 §9 对此有详述。 - 正确做法：把 LLM 当成某一层的"启发式生成器"嵌进栈里（如用 LLM 提议任务分解，再用经典规划器验证可行性），而不是用它取代整个决策层。

练习¶

（⭐） 回到 §2.1 的仓库场景，明确写出三层各自的输入和输出（用集合/序列符号表示）。例如分配层的输出是一个映射 $a: \{p_1,\dots,p_5\} \to \{R_1,R_2,R_3\}$。然后举一个具体的失败反馈例子：哪一层的什么失败，应该反馈给上面哪一层、触发什么动作？
（⭐⭐） 找一个你熟悉的真实系统（送餐机器人、扫地机器人集群、自动化产线、网约车派单），把它映射到三层决策栈：哪一层在这个系统里最关键？哪一层被简化或省略了？为什么？
（⭐⭐） 反事实思考：如果一个系统只有任务分配层、没有任务规划层（即假设每个任务被分配后就是一个"原子动作"，无需再分解排序），会丢失对哪类问题的处理能力？给一个仓库场景里的例子说明这种简化何时成立、何时崩溃。

3. 经典任务规划深化：启发式从哪来 ⭐⭐¶

3.1 衔接：FF 的松弛计划只是冰山一角¶

回顾 TAMP_T1 §3.4：FF (Fast-Forward) 规划器之所以快，是因为它用了一个叫"松弛计划 (relaxed plan)"的启发式来引导搜索——把原问题简化成一个忽略负效果的版本，在简化版上快速求一个解，用这个解的长度估计"离目标还有多远"。TAMP_T1 给出了结论，但留下了三个没回答的问题：

为什么"忽略负效果"这个特定的简化是合理的？还有别的简化方式吗？
从这个简化出发，能不能推导出多个不同的启发式，而不只是 FF 那一个？
除了"简化问题"这条路，还有没有别的造启发式的思路？

本节回答这三个问题。这是本章主干 A 最硬核的一节——理解了启发式的来源，你就理解了现代规划器（FF、LAMA、Fast Downward）为什么能在几十万状态的空间里秒级找到解，也理解了为什么有些问题它们仍然搞不定（从而需要 §4 的 HTN）。

在挖启发式之前，先退一步看一个更基础的问题：规划器到底在什么空间里搜索？

3.2 两种搜索空间：状态空间 vs 规划空间¶

动机：同一个规划问题，可以在两种完全不同的图上搜索。 这个选择影响巨大，但 TAMP_T1 默认用了其中一种（状态空间）而没点明还有另一种。

搜索空间一：状态空间搜索 (state-space search)。

节点是世界状态（一组命题），边是动作。从初始状态出发，每次施加一个其前提被满足的动作，得到新状态，直到命中目标。

状态空间搜索（前向）：
  s₀ = {On(p1,shelf), HandEmpty, ...}
    │ apply pick(p1)
    ▼
  s₁ = {Holding(p1), ...}
    │ apply move(packing)
    ▼
  s₂ = {Holding(p1), At(packing), ...}
    │ apply place(p1, packing)
    ▼
  ... 直到 goal ⊆ sₙ

这就是 TAMP_T1 用 A* / 贪心搜索做的事。节点是状态，分支因子是"当前可执行的动作数"。前向 (forward / progression) 从初始态推向目标；也可以后向 (backward / regression) 从目标倒推前提。

搜索空间二：规划空间搜索 (plan-space search)，又称偏序规划 (Partial-Order Planning, POP)。

节点不是状态，而是一个未完成的计划（一组动作 + 它们之间的顺序约束 + 因果链接）。边是"对计划的一次修补"：加一个动作来满足某个尚未支持的前提、加一条顺序约束来消解冲突。

规划空间搜索（偏序）：
  节点 = ⟨动作集, 顺序约束, 因果链接, 待解前提⟩
  初始节点 = 只有 start 和 finish 两个虚拟动作，finish 的前提 = goal
    │ 为满足 finish 的某个前提 g，加入一个 add 了 g 的动作 a
    │ 加因果链接 a --g--> finish
    ▼
  ... 反复修补，直到没有"待解前提"且无冲突

POP 的妙处在于：它不强行决定无关动作的先后。如果"取 $p_1$"和"取 $p_2$"互不影响，POP 让它们保持无序 (unordered)，只在真正有冲突时才加顺序约束。这天然契合并发——偏序计划可以被多个执行者并行执行。

对比：什么时候用哪种？

维度	状态空间搜索	规划空间 (POP)
节点是什么	一个完整世界状态	一个未完成的（偏序）计划
分支来源	可执行的动作	待满足的前提 × 候选支持动作
强项	配合强启发式时极快（现代主流）	天然偏序，利于并发与解释
弱项	强制全序，需要好启发式	状态信息隐式，启发式难做
代表系统	FF, LAMA, Fast Downward	UCPOP, SNLP（历史上重要）

本质洞察：状态空间搜索和规划空间搜索的区别，是"具体化每一步的世界长什么样"与"只承诺动作之间的逻辑骨架、不承诺无关步骤的先后"之间的区别。前者像一帧一帧拍电影，后者像先画分镜脚本只标必要的镜头顺序。历史上 POP 曾是主流（因为它优雅、支持偏序），但 1990 年代末启发式状态空间搜索（HSP、FF）凭借"用松弛问题造强启发式"实现了数量级的提速，把 POP 挤出了主流。这个反转的关键，恰恰是下一节要讲的启发式。

接下来我们聚焦状态空间搜索（现代主流），把它的引擎——启发式——彻底讲清。

3.3 启发式的统一来源：删除松弛¶

动机：启发式 $h(n)$ 是搜索的灵魂，但它从哪来？ A* 需要一个估计"从状态 $s$ 到目标还要多少步"的函数 $h(s)$。人工设计太难、太脆弱（换个 domain 就失效）。规划领域的突破在于：从问题本身自动推导启发式。最成功的一族叫"松弛 (relaxation)"——把原问题改成一个更容易解的版本，用松弛问题的最优解代价当作原问题的启发式。

核心思路：删除松弛 (delete relaxation)。 回忆 STRIPS 动作的三件套：前提 $\text{Pre}$、正效果 $\text{Eff}^+$（add list）、负效果 $\text{Eff}^-$（delete list）。删除松弛做一件极简单的事——把所有动作的负效果删掉，得到松弛动作 $a^+ = \langle \text{Pre}, \text{Eff}^+, \varnothing \rangle$。

为什么删负效果就变简单了？因为这让问题变成单调 (monotone) 的：

在删除松弛问题 $\Pi^+$ 中，命题一旦变真就永远为真——没有任何动作能再把它删成假（负效果没了）。所以状态只增不减，是一个单调增长的命题集合。

单调性带来一个决定性的好处：删除松弛问题可以贪心求解，且没有"做了又被撤销"的浪费。在原问题里，你可能 pick 起一个物体（让 HandEmpty 变假），后面又不得不 place 它（恢复 HandEmpty），动作互相干扰。松弛后这种干扰消失了——你拿起东西后"手依然是空的"（负效果没了），可以无限并行地达成所有子目标。

一个直觉类比（标注边界）：删除松弛像"假设你做事永不留下副作用"。现实中你打开冰箱拿牛奶，冰箱门开着（副作用）挡住了抽屉；松弛世界里，你拿了牛奶但冰箱门"还是关着的"，于是任何两件事都不会互相挡道。像的地方：都让子目标之间解耦、可以分别达成。不像的地方：现实里副作用真实存在，所以松弛解通常低估真实代价——这恰恰是我们想要的（低估 = 可容许，见下）。

关键性质：删除松弛的最优代价 $h^+$ 是可容许的。 因为松弛问题去掉了约束（负效果带来的干扰），它的最优解不会比原问题更贵：原问题的任何真实计划，在松弛问题里也是一个合法计划（多删几个命题只会让前提更容易满足）。所以 $$ h^+(s) \le h^*(s) \quad \text{对所有状态 } s, $$ 其中 $h^*$ 是原问题的真实最优代价。$h^+$ 永不高估，是可容许启发式。

但有个坏消息：精确计算 $h^+$（求松弛问题的最优解）本身仍是 NP-hard。所以实践中我们不求 $h^+$ 的精确值，而是用可多项式计算的近似——这就引出 $h^{\max}$、$h^{\text{add}}$、$h^{\text{FF}}$ 三兄弟。它们都是 $h^+$ 的近似，区别在于"近似的姿势"。

3.4 从松弛问题到 h^max 与 h^add¶

怎么估计"达成一组命题的代价"？ 定义命题 $p$ 的代价 $h(p)$ = 在松弛问题里从当前状态首次让 $p$ 变真所需的最小动作代价。初始状态里已为真的命题代价为 0。一个动作 $a$ 能产出它的某个 add 效果 $p$，代价是"满足 $a$ 所有前提的代价" + "$a$ 自身的代价"。这里出现了关键的设计抉择：满足一组前提的代价怎么算？

有两种自然的定义，分别给出 $h^{\max}$ 和 $h^{\text{add}}$：

\[ \text{cost}(\text{Pre}) = \begin{cases} \max_{q \in \text{Pre}} h(q) & \Rightarrow\ h^{\max}\ \text{（取最贵的前提）} \\[4pt] \sum_{q \in \text{Pre}} h(q) & \Rightarrow\ h^{\text{add}}\ \text{（前提代价相加）} \end{cases} \]

于是命题代价的递推式（不动点方程）为：

\[ h(p) = \begin{cases} 0 & p \in s\ \text{（初始已真）} \\ \min_{a:\, p \in \text{Eff}^+(a)} \Big[\, \text{cost}(a) + \text{cost}(\text{Pre}(a)) \,\Big] & \text{否则} \end{cases} \]

把它对所有命题反复迭代到不动点（值不再变化），就得到所有命题的代价估计。目标的启发式就是"达成目标合取式的代价"：$h(s) = \text{cost}(\text{Goal})$，同样用 $\max$ 或 $\sum$ 聚合。

两者的含义与取舍——这是本节最该记住的对比：

	$h^{\max}$	$h^{\text{add}}$
聚合前提/目标	取最大 $\max$	求和 $\sum$
隐含假设	子目标可完全共享子计划（最乐观）	子目标完全独立、零共享（最悲观）
可容许？	是（永不高估）	否（会高估）
通常信息量	弱（太乐观，常严重低估）	强（更接近真实，导向性好）
典型用途	需要最优性保证时（配 A*）	只求快速找到解时（配贪心，FF 的基础）

本质洞察：$h^{\max}$ 和 $h^{\text{add}}$ 是同一个递推式在"前提代价聚合"上的两个极端选择，而它们各自的可容许性来自这个选择。$\max$ 假设"达成所有子目标的代价 = 达成最难那个的代价"（仿佛其余子目标都搭便车），这必然不超过真实代价，所以可容许但偏弱。$\sum$ 假设"代价完全可加、子目标间毫无共享"，这会把共享的工作重复计数，所以可能高估、不可容许，但正因为它'惩罚'了多子目标，导向性更强。真实情况介于两者之间——子目标部分共享子计划——这就是为什么需要第三个启发式 $h^{\text{FF}}$ 来更精细地处理共享。

对仓库场景的直觉：要把 $p_1$ 和 $p_2$ 都送到打包台。$h^{\text{add}}$ 把"送 $p_1$"和"送 $p_2$"的代价相加，但忽略了机器人去打包台的路程其实可以共享（顺路送两个）。$h^{\max}$ 只算两者中较贵的那个，又过于乐观。

3.5 h^FF：抽取一个松弛计划¶

动机：$h^{\max}$ 太乐观、$h^{\text{add}}$ 重复计数，能不能直接在松弛问题里'真的解一个计划'，用它的长度当启发式？ 这就是 FF 的做法 (Hoffmann & Nebel 2001)，得到 $h^{\text{FF}}$。

思路分两步：

第一步：构建松弛规划图 (relaxed planning graph, RPG)。 从当前状态出发，交替铺开"命题层"和"动作层"：第 0 层是当前为真的命题；动作层放入所有前提在上一命题层已满足的（松弛）动作；下一命题层 = 上一层命题 ∪ 所有这些动作的 add 效果。因为单调（只增不减），这个图会在有限层内"饱和"——再铺也不出新命题。如果目标的所有命题都出现在某一层，松弛问题可解。

第二步：反向抽取松弛计划。 从目标命题出发，反向走：对每个要达成的命题，挑一个能产出它的动作（通常挑首次产出它的、且优先选已被别的目标选中的动作以促成共享），把该动作的前提加入"还需达成"的集合，一直回溯到初始命题层。被挑中的动作集合就是一个松弛计划 $\pi^+$。

\[ h^{\text{FF}}(s) = \big|\pi^+\big| \quad \text{（松弛计划中的动作数，或其代价和）} \]

$h^{\text{FF}}$ 为什么好用？

它在抽取时主动促成子目标间的动作共享（同一个动作满足多个目标只数一次），所以不像 $h^{\text{add}}$ 那样重复计数。对仓库场景，它会识别出"去打包台"这一步被多个送货目标共享。
它通常比 $h^{\max}$ 信息量大得多（不那么乐观），导向性强，搜索更快。
它不可容许（抽取的松弛计划未必是松弛最优，且会受抽取策略影响），所以 FF 配的是贪心/加权 A*，不追求最优。

启发式	一句话本质	可容许	信息量	计算	常见搭配
$h^{\max}$	删负效果后取最贵子目标	是	弱	多项式	A*（求最优）
$h^{\text{add}}$	删负效果后子目标代价相加	否	中	多项式	贪心（求快）
$h^{\text{FF}}$	删负效果后真抽一个计划数长度	否	强	多项式	加权 A*/贪心（FF、LAMA）

3.6 代码：在小型 STRIPS 任务上实现 h^max / h^add / h^FF¶

下面在一个最小的 STRIPS 任务上动手实现三种启发式，让上面的递推式和图构建从公式变成可运行的代码。任务沿用仓库主题的极简版：一台机器人，要把一个包裹从货架送到打包台。

Step 1：先讲为什么这样组织代码。

为什么用"命题→代价"的字典 + 不动点迭代来算 h^max/h^add？

因为 §3.4 的递推式是一个不动点方程：每个命题的代价依赖于能产出它的
动作的前提代价，而前提代价又是别的命题的代价——存在循环依赖。
解不动点的标准做法是：所有命题代价初始化为 ∞（初始态命题为 0），
反复"松弛"（用动作更新命题代价）直到没有任何代价被降低为止。
这本质上是 Bellman-Ford 式的松弛迭代，对单调问题保证收敛。

数据结构选择：
  动作 = (前提集合, add集合)  —— 松弛问题里 delete 集合直接丢弃
  cost[p] = 达成命题 p 的估计代价

Step 2：正确写法。

import itertools

# ---- 用最小数据结构表示一个删除松弛任务 ----
# 动作: (name, preconditions:set, add_effects:set)  —— 已删除 delete 列表
# 状态: 命题的 frozenset

def relaxed_costs(state, actions, mode="max"):
    """计算删除松弛下每个命题的可达代价 (h^max 或 h^add)。
    mode='max' -> h^max(可容许); mode='add' -> h^add(信息强但不可容许)。"""
    INF = float("inf")
    cost = {}                      # 命题 -> 估计代价
    for p in state:
        cost[p] = 0                # 初始态命题代价为 0

    agg = max if mode == "max" else sum

    changed = True
    while changed:                 # 不动点迭代
        changed = False
        for (name, pre, add) in actions:
            # 满足该动作所有前提的代价
            if any(q not in cost for q in pre):
                continue           # 还有前提不可达, 暂时跳过
            pre_cost = agg([cost[q] for q in pre]) if pre else 0
            a_cost = 1             # 单位动作代价
            new = pre_cost + a_cost
            for p in add:          # 用该动作更新它能产出的命题
                if new < cost.get(p, INF):
                    cost[p] = new
                    changed = True
    return cost

def h_value(state, goal, actions, mode="max"):
    cost = relaxed_costs(state, actions, mode)
    agg = max if mode == "max" else sum
    if any(g not in cost for g in goal):
        return float("inf")        # 目标不可达
    return agg([cost[g] for g in goal]) if goal else 0

Step 3：错误写法并解释为什么错。

# ❌ 错误 1: 只迭代一遍, 不做不动点循环
def relaxed_costs_wrong(state, actions, mode="max"):
    cost = {p: 0 for p in state}
    for (name, pre, add) in actions:        # 只扫一遍动作
        if all(q in cost for q in pre):
            pre_cost = (max if mode=="max" else sum)([cost[q] for q in pre] or [0])
            for p in add:
                cost[p] = min(cost.get(p, 1e9), pre_cost + 1)
    return cost
# 问题: 动作之间有依赖链 (A 产出 x, B 需要 x 才能产出 y)。
#      只扫一遍, 若 B 排在 A 前面就永远算不出 y 的代价。
#      必须迭代到不动点 (changed=False) 才正确。

# ❌ 错误 2: 忘了删除 delete 列表, 直接拿原动作算
#   relaxed_costs(state, ORIGINAL_actions_with_deletes, ...)
# 问题: 这就不是"删除松弛"了。负效果会让命题代价的单调性被破坏,
#      不动点迭代可能不收敛或给出错误估计。删除松弛的前提就是先丢掉 delete。

# ❌ 错误 3: 用 h^add 却当它可容许, 拿去配 A* 求最优
#   h_value(s, goal, actions, mode="add") 作为 A* 的 h, 然后声称结果最优
# 问题: h^add 会高估 (重复计数共享子计划), 不可容许。
#      A* 配不可容许启发式不再保证最优解。求最优必须用 h^max。

Step 4：三种启发式的对比与 h^FF 的实现。

def relaxed_plan_graph(state, actions):
    """构建松弛规划图, 返回 (命题层列表, 动作层列表)。"""
    prop_layers = [set(state)]
    act_layers = []
    while True:
        applicable = [(n, pre, add) for (n, pre, add) in actions
                      if pre <= prop_layers[-1]]      # 前提已满足
        new_props = set(prop_layers[-1])
        for (n, pre, add) in applicable:
            new_props |= add
        act_layers.append(applicable)
        if new_props == prop_layers[-1]:              # 饱和, 不再增长
            break
        prop_layers.append(new_props)
    return prop_layers, act_layers

def h_ff(state, goal, actions):
    """h^FF: 构图 + 反向抽取松弛计划, 返回动作数。"""
    prop_layers, act_layers = relaxed_plan_graph(state, actions)
    if not (set(goal) <= prop_layers[-1]):
        return float("inf")                           # 目标不可达
    # 反向抽取: 从目标回溯, 贪心选首次产出该命题的动作
    needed = set(goal) - set(state)
    chosen = set()
    achieved = set(state)
    for layer in act_layers:                          # 由早到晚扫动作层
        for (n, pre, add) in layer:
            if add & needed:                          # 该动作能满足某个待达成命题
                chosen.add(n)
                needed -= add                         # 这些命题被满足
                needed |= (pre - achieved)            # 但引入新的前提需求
                achieved |= add
        if not needed:
            break
    return len(chosen)

# ---- 在仓库极简任务上对比三种启发式 ----
state = frozenset({"At_dock", "Empty", "On_p1_shelf"})
goal  = frozenset({"On_p1_packing"})
actions = [
    ("move_dock_shelf",  {"At_dock"},                {"At_shelf"}),
    ("pick_p1",          {"At_shelf", "Empty", "On_p1_shelf"}, {"Hold_p1"}),
    ("move_shelf_pack",  {"At_shelf"},               {"At_packing"}),
    ("place_p1",         {"At_packing", "Hold_p1"},  {"On_p1_packing"}),
]
print("h_max =", h_value(state, goal, actions, "max"))   # 较小(乐观)
print("h_add =", h_value(state, goal, actions, "add"))   # 较大(可能高估)
print("h_FF  =", h_ff(state, goal, actions))             # 介于其间, 抽出的松弛计划长度

运行后你会观察到 $h^{\max} \le h^{\text{FF}} \le h^{\text{add}}$ 的典型大小关系（在这个无共享的小例子上三者可能接近，子目标越多、共享越多，差距越明显）。动手建议：把目标改成同时送两个包裹 $\{On\_p1\_packing, On\_p2\_packing\}$，观察 $h^{\text{add}}$ 如何把"去打包台"重复计数、而 $h^{\text{FF}}$ 如何只数一次。

3.7 另外两类启发式：地标与抽象¶

删除松弛是造启发式的第一条路，但不是唯一一条。这里简介另外两条主流思路，让知识树完整（细节属于自动规划专门课程，本节给出直觉和入口）。

思路二：地标启发式 (landmark heuristics)。

核心直觉：有些命题或动作是任何解都绕不开的——它们叫地标 (landmark)。例如"把 $p_1$ 送到打包台"这个目标，任何计划都必须经过"$Hold\_p1$ 为真"这个中间命题（不抓起来就送不了）。地标数量给出一个朴素下界：至少要达成这么多个必经里程碑。
LM-cut (Helmert & Domshlak 2009) 是其中最重要的可容许变体，它通过反复在松弛问题里找"割 (cut)"来识别地标并累加代价，给出比 $h^{\max}$ 更强且仍可容许的下界。LM-cut 是当前最优规划 (optimal planning) 的主力启发式之一。
对比删除松弛：删除松弛问"简化后要多少动作"，地标问"有哪些步骤无论如何躲不掉"。两者从不同角度逼近真实代价。

思路三：抽象启发式 (abstraction heuristics)。

核心直觉：把原问题投影到一个更小的状态空间（忽略部分变量），在小空间里精确求最短距离，用它当原问题的下界。因为抽象只会合并状态、不会增加距离，所以抽象距离永不高估——可容许。
模式数据库 (Pattern Database, PDB)：选一组变量（一个"模式 pattern"），枚举这组变量的所有取值组合，预计算每种组合到目标的最短距离，存成一张表。搜索时查表即得启发式。
合并-收缩 (merge-and-shrink)：比 PDB 更一般的抽象框架，通过反复"合并两个变量的状态机 + 收缩状态数"来构造抽象，能表达 PDB 表达不了的抽象。
对比：删除松弛"放松约束"，抽象"缩小空间"。一个改问题、一个改状态表示。

本质洞察：三类启发式对应三种"如何让难问题变可算"的元策略——松弛（去掉约束，删除松弛）、分解（找必经子目标，地标）、投影（降到低维精确解，抽象）。这三种策略不止用于规划：你会在优化（松弛对偶）、强化学习（值函数抽象）、乃至本章 §7 的整数规划（LP 松弛给下界）里反复看到它们。认得这三种元策略，比记住任何一个具体启发式都重要。

⚠️ 常见陷阱¶

陷阱 3-1（概念误区）：把 $h^{\text{add}}$ 当可容许启发式配 A* 求最优。 - 错误描述：因为 $h^{\text{add}}$ 信息量强、搜索快，就拿去配 A* 并相信结果最优。 - 现象/后果：A* 返回的解不是最优，但程序不报错，你以为拿到了最优解。 - 根本原因：$h^{\text{add}}$ 对共享子计划重复计数，会高估真实代价，违反可容许性 $h \le h^*$。A* 的最优性证明依赖可容许（或一致），前提一破，结论失效。 - 正确做法：求最优用可容许启发式（$h^{\max}$ 或更强的 LM-cut / PDB）；用 $h^{\text{add}}$/$h^{\text{FF}}$ 时配贪心或加权 A*，并明确放弃最优性保证、只求快速可行解。

陷阱 3-2（编程陷阱）：算删除松弛代价时只迭代一遍，不到不动点。 - 错误描述：扫一遍动作列表就返回命题代价（见 §3.6 错误 1）。 - 现象/后果：存在依赖链的命题代价算成 $\infty$ 或偏大，启发式失真，搜索效率骤降甚至找不到解。 - 根本原因：命题代价存在循环/链式依赖，必须用不动点迭代（反复松弛直到无变化）才能收敛到正确值。单遍扫描受动作排列顺序影响。 - 正确做法：用 while changed 循环，任何一次代价被降低就标记 changed=True，直到一整轮无变化才停。

陷阱 3-3（思维陷阱）：以为删除松弛"删掉负效果"会丢失正确性。 - 错误描述：担心删掉 delete 列表后算出的启发式"不对"，因此不敢用。 - 现象/后果：回避现代启发式，退回手工启发式或无启发式的盲目搜索，性能差几个数量级。 - 根本原因：混淆了"启发式"与"解"。删除松弛不是用来求原问题的解的，它只用来估计代价。估计值即使粗糙，只要可容许（或导向性好）就能正确引导搜索，最终的解仍在原问题（带负效果）上验证。 - 正确做法：理解启发式的角色是"导航"而非"执行"。松弛只发生在估计代价这一步，真实搜索和解的验证始终在完整问题上进行。

陷阱 3-4（概念误区）：认为偏序规划 (POP) 已经过时、不值得了解。 - 错误描述：既然状态空间搜索是主流，POP 就是历史遗迹。 - 现象/后果：在需要并发执行、计划解释、或时序规划的场景里，错过了 POP 提供的"只约束必要顺序"这一关键思想。 - 根本原因：把"主流求解器用哪种"和"思想有没有价值"混为一谈。POP 在主流求解中被启发式状态空间搜索超越，但它的"偏序/因果链接"思想是 §5 时序规划、TAMP 中并发动作、以及多机协作的基础。 - 正确做法：理解 POP 作为思想（偏序、因果链接、冲突消解）的持续价值，即使具体求解器不再常用它。

练习¶

（⭐⭐，手推） 在 §3.6 的仓库任务上，手动构建松弛规划图（命题层 + 动作层），并手动抽取一个松弛计划。验证你的结果和代码输出一致。然后手算 $h^{\max}$ 和 $h^{\text{add}}$，确认 $h^{\max} \le h^{\text{add}}$。
（⭐⭐，实现/调试） §3.6 的 h_ff 抽取策略很朴素（按动作层从早到晚扫）。当目标是同时送两个包裹时，它能否正确识别"去打包台"这步被共享、只数一次？运行验证；若没有，分析原因并改进抽取顺序（提示：优先复用已选中的动作）。
（⭐⭐⭐，设计扩展） 给 §3.6 的动作加上代价（如 move 代价 2、pick/place 代价 1），把三种启发式从"数动作个数"改为"代价求和"。然后讨论：带代价后，$h^{\max}$ 取"最贵前提"是否仍可容许？给出论证或反例。
（⭐⭐⭐，跨节综合） 结合 §3.2，思考：如果改用偏序规划 (POP) 来解仓库任务，删除松弛启发式还能直接用吗？POP 的节点是"未完成计划"而非"状态"，启发式的输入变了——这正是历史上 POP 难以用强启发式的原因。用 2-3 句话说清这个困难。

4. 分层任务网络 HTN ⭐⭐⭐¶

4.1 动机：经典规划在长任务上为什么会爆炸¶

回到仓库场景，但把任务放大：不是搬 5 个包裹，而是"整理整个仓库"——盘点、分拣、补货、清扫，几十个子任务、上百步动作。这时 §3 的经典规划器会遇到麻烦。

问题出在搜索深度。 状态空间搜索的代价随解的长度指数增长（分支因子 $b$、解长度 $d$，最坏 $O(b^d)$）。即使有 $h^{\text{FF}}$ 这样的强启发式，当 $d$ 达到几十上百步时，搜索树仍可能爆炸——启发式只能"剪枝"，剪不掉问题的本质深度。

人类怎么做？用配方。 你不会从"手的关节角"层面去想"怎么整理仓库"。你会想："整理仓库 = 先盘点 + 再分拣 + 最后补货"；"分拣 = 对每个货架做一次分拣操作"；"分拣一个货架 = 取出 + 归类 + 放回"。你自顶向下地把抽象任务拆成更小的任务，直到拆成可直接执行的原子动作。每一步拆解都用一条"配方"——这正是分层任务网络 (Hierarchical Task Network, HTN) 的核心。

本质洞察：经典规划是"目标驱动"的——给一个目标状态，让规划器自己摸索怎么从初始态到那里，搜索空间是所有动作序列。HTN 是"任务驱动"的——给一个抽象任务和一组分解配方，规划器只在配方允许的分解里搜索。HTN 用领域知识（配方）换搜索效率：它不保证找到经典规划意义下的"任意可行解"，但它能在人类编码的结构内极快地找到解。这是一个表达力 vs 可控性的根本取舍，下文会精确刻画。

4.2 三个核心概念：原子任务、复合任务、方法¶

HTN 把"任务"分两种，再用"方法"连接它们。

概念	英文	含义	仓库例子
原子任务	primitive task	对应一个可直接执行的动作（有前提/效果，像 STRIPS 动作）	`pick(p1)`、`move(shelf, dock)`
复合任务	compound task	抽象任务，本身不可直接执行，必须被分解	`deliver(p1)`、`tidy_warehouse`
方法	method	一条分解配方：把某个复合任务在某前提下拆成一串子任务（可含复合也可含原子）	`deliver(p) = [go_to(shelf_of_p), pick(p), go_to(dock), place(p)]`

一个 HTN 规划问题给定：初始状态、一个初始任务网络（要完成的任务列表，通常是一个顶层复合任务），以及 domain 里的方法集合和原子动作集合。规划 = 反复用方法把复合任务分解，直到任务网络里全是原子任务，且它们的前提沿途都满足。

HTN 分解树（仓库送货）：
            tidy_warehouse              ← 复合任务（顶层）
                  │ method: tidy = [deliver(p1), deliver(p2)]
        ┌─────────┴─────────┐
    deliver(p1)         deliver(p2)      ← 复合任务
        │ method            │ method
   ┌────┼────┬────┐    ┌────┼────┬────┐
 go_to pick go_to place ...              ← 原子任务（叶子, 可执行）
(shelf) (p1)(dock)(p1)

一个复合任务可以有多条方法（多种拆法），规划器需要选一条其前提满足的。这就是 HTN 的搜索分支来源——不是"选哪个动作"，而是"选哪条配方"。

4.3 SHOP 与 SHOP2：有序分解¶

HTN 最有影响力的实现是 Nau 等人的 SHOP 系列。SHOP (Simple Hierarchical Ordered Planner) 与 SHOP2 (Nau et al. 2003, JAIR 20:379-404) 的核心特征是有序分解 (ordered decomposition)：规划器按执行顺序逐个处理任务，所以在分解每个任务时，它确切知道当前世界状态——因为前面的任务（按顺序）已经"执行"过了（在规划层面更新了状态）。

这个"边分解边推进状态"的设计为什么重要？ 因为它让方法的前提可以引用精确的当前状态，求解极其高效。对比经典规划要在庞大状态空间里摸索，SHOP2 沿着配方树几乎是"按图索骥"。SHOP2 凭此在 2002 国际规划竞赛 (IPC) 中获得杰出表现奖。

SHOP vs SHOP2 的关键区别：SHOP 要求全序 (total order)——同一方法的子任务严格按列出顺序执行，不同任务的子任务也不能交错。SHOP2 放宽为偏序 (partial order)——允许不同任务的子任务交错执行。这听起来是小改动，实则大幅增强了能力：很多问题（如两个需要交替推进的任务）用全序的 SHOP 要么写不出、要么得用别扭的编码，SHOP2 则自然处理。

全序 (SHOP):   taskA 的子任务必须全部做完, 才能开始 taskB 的子任务
               [a1, a2, a3] 然后 [b1, b2]   —— 不能交错

偏序 (SHOP2):  taskA 与 taskB 的子任务可交错, 只要不违反各自方法内的顺序
               [a1, b1, a2, b2, a3]          —— 合法

4.4 HTN vs STRIPS：表达力与可控性的取舍¶

读者可能会问：HTN 只是给经典规划加了点结构、是不是经典规划的"语法糖"？ 不是。这是一个需要澄清的关键点。

表达力上，HTN 严格强于 STRIPS。 Erol、Nau、Hendler (1994, AAAI-94) 证明：

无限制的 HTN 规划是不可判定的 (undecidable)——因为方法的递归分解可以模拟图灵机的计算。而命题 STRIPS 规划是可判定的（PSPACE-完全）。
即使是受限 HTN，它能表达的"解集合"也比 STRIPS 目标式规划更丰富。HTN 可以通过方法和顺序约束，规定"解必须具有某种结构"（如"必须先 A 类操作再 B 类操作"），而 STRIPS 只能指定"目标状态",无法直接约束解的结构。

但表达力强不全是好事——它换来的是另一种负担：

维度	STRIPS / 经典规划	HTN
输入	初始态 + 目标状态 + 动作	初始态 + 初始任务 + 方法（配方） + 动作
谁提供"怎么做"	规划器自己搜索	人类编码进方法里
搜索空间	所有动作序列（大）	配方允许的分解（小，受控）
可判定性	可判定	一般不可判定
适合	目标清晰但路径未知、需要发现新解法	领域知识丰富、有标准操作流程 (SOP)
工程负担	写动作模型	写动作模型 + 写全套方法

本质洞察：STRIPS 和 HTN 的对立，本质是"让机器搜索 vs 让人编码"的对立。STRIPS 把"怎么达成目标"的重担全压给搜索算法，人只需描述世界（动作）和愿望（目标）；HTN 把这个重担分给人——人用方法显式编码领域专家的"操作手册"，机器只在手册内填空。没有免费的午餐：STRIPS 省人力但费算力（可能搜爆），HTN 省算力但费人力（要写全配方，且配方写错就找不到本可行的解）。选哪个，取决于你的领域是"路径未知需探索"还是"流程已知需执行"。机器人操作大量属于后者（抓取、搬运有标准流程），所以 HTN 在机器人任务规划中很常用。

4.5 代码：一个最小 HTN 规划器与送货 domain¶

下面实现一个 SHOP 风格的总序 HTN 规划器（约 40 行核心逻辑），并写一个仓库送货 domain。现代工程中可直接用 Nau 团队的 GTPyhop（pyhop 的继任者，基于 Python），这里手写一个最小版以理解原理。

Step 1：为什么这样组织代码。

HTN 规划的核心是递归分解, 所以代码结构天然是递归 + 回溯:
  seek_plan(state, tasks):
    若 tasks 为空 -> 返回空计划(成功)
    取第一个任务 t:
      若 t 是原子动作 -> 检查前提, 施加效果, 递归剩余任务
      若 t 是复合任务 -> 逐条尝试它的方法, 每条方法把 t 展开成子任务,
                       递归求解 [子任务 + 剩余任务], 成功则返回, 否则回溯换方法

数据结构:
  operators: name -> 函数(state, *args) -> new_state 或 None(前提不满足)
  methods:   name -> [函数(state, *args) -> 子任务列表 或 None(不适用)]
  task:      (name, arg1, arg2, ...) 元组

Step 2：正确写法。

import copy

# ===== 仓库送货 domain =====
# 状态用 dict 表示: 位置、手是否空、包裹在哪

# ---- 原子动作 (operators): 返回新状态或 None ----
def op_move(state, frm, to):
    if state["robot_at"] != frm:
        return None                       # 前提: 机器人在 frm
    s = copy.deepcopy(state); s["robot_at"] = to; return s

def op_pick(state, p):
    if not state["hand_empty"]:
        return None
    if state["pkg_at"].get(p) != state["robot_at"]:
        return None                       # 前提: 包裹和机器人同位置
    s = copy.deepcopy(state)
    s["hand_empty"] = False; s["holding"] = p; s["pkg_at"][p] = "hand"; return s

def op_place(state, p, loc):
    if state.get("holding") != p or state["robot_at"] != loc:
        return None
    s = copy.deepcopy(state)
    s["hand_empty"] = True; s["holding"] = None; s["pkg_at"][p] = loc; return s

operators = {"move": op_move, "pick": op_pick, "place": op_place}

# ---- 方法 (methods): 把复合任务展开成子任务列表, 或 None(不适用) ----
def m_deliver(state, p):
    """deliver(p): 去包裹处取它, 再送到 dock。"""
    shelf = state["shelf_of"][p]
    return [("move", state["robot_at"], shelf),
            ("pick", p),
            ("move", shelf, "dock"),
            ("place", p, "dock")]

def m_deliver_all(state, pkgs):
    """deliver_all(pkgs): 逐个 deliver(顶层任务的一种分解)。"""
    if not pkgs:
        return []                          # 空任务列表 -> 完成
    return [("deliver", pkgs[0]), ("deliver_all", pkgs[1:])]

methods = {"deliver": [m_deliver], "deliver_all": [m_deliver_all]}

# ===== 最小 HTN 规划器 (总序, SHOP 风格) =====
def seek_plan(state, tasks, plan=None):
    if plan is None:
        plan = []
    if not tasks:
        return plan                        # 所有任务完成
    t = tasks[0]; name, args = t[0], t[1:]
    if name in operators:                  # 原子任务
        new_state = operators[name](state, *args)
        if new_state is None:
            return None                    # 前提不满足, 此分支失败
        return seek_plan(new_state, tasks[1:], plan + [t])
    elif name in methods:                  # 复合任务
        for method in methods[name]:       # 逐条方法尝试
            subtasks = method(state, *args)
            if subtasks is None:
                continue                   # 该方法不适用
            result = seek_plan(state, subtasks + tasks[1:], plan)
            if result is not None:
                return result               # 成功
        return None                        # 所有方法都失败, 回溯
    else:
        raise ValueError(f"未知任务: {name}")

# ===== 运行 =====
init = {
    "robot_at": "dock", "hand_empty": True, "holding": None,
    "shelf_of": {"p1": "shelf_A", "p2": "shelf_B"},
    "pkg_at": {"p1": "shelf_A", "p2": "shelf_B"},
}
plan = seek_plan(init, [("deliver_all", ["p1", "p2"])])
for i, step in enumerate(plan):
    print(f"{i+1}. {step}")
# 输出: move dock->shelf_A, pick p1, move shelf_A->dock, place p1 dock,
#       move dock->shelf_B, pick p2, move shelf_B->dock, place p2 dock

Step 3：错误写法并解释为什么错。

# ❌ 错误 1: 原子动作直接修改传入的 state, 不返回新状态
def op_move_wrong(state, frm, to):
    state["robot_at"] = to          # 就地修改!
    return state
# 问题: 回溯时状态被污染。当一条方法失败需要回退尝试另一条时,
#      state 已经被前面的动作改过了, 回溯到的不是原状态而是脏状态,
#      导致后续方法基于错误的世界状态判断前提。必须 deepcopy 后返回新状态。

# ❌ 错误 2: 复合任务的方法返回后, 忘了把"剩余任务"接在子任务后面
result = seek_plan(state, subtasks, plan)   # 漏掉 tasks[1:]
# 问题: 只规划了当前复合任务的子任务, 把它后面本该做的任务丢了。
#      正确是 subtasks + tasks[1:] —— 展开当前任务, 但保留其后的任务。

# ❌ 错误 3: 用 HTN 却不写终止方法 (base case)
#   m_deliver_all 若不处理 pkgs 为空的情况, 递归 deliver_all([]) 无方法可用 -> 失败
# 问题: HTN 的递归方法必须有 base case (空任务列表返回 [])。
#      这和写递归函数忘了递归终止条件是同一类错误。

Step 4：HTN 与经典规划的对比（同一任务两种解法）。

# === 同样是"送 p1 和 p2 到 dock", 两种范式的输入对比 ===

# 经典规划 (STRIPS/PDDL) 的输入: 只描述目标状态, 不说怎么做
#   (:goal (and (pkg_at p1 dock) (pkg_at p2 dock)))
#   规划器自己搜索动作序列 —— 可能找到任意可行解, 但长任务上会搜索爆炸

# HTN 的输入: 描述任务 + 配方, 显式编码"怎么做"
#   初始任务: deliver_all([p1, p2])
#   方法: deliver_all -> 逐个 deliver; deliver -> move/pick/move/place
#   规划器只在配方内填空 —— 极快, 但只能产出配方允许的解

# 对比表:
# | 维度       | STRIPS              | HTN                  |
# | 输入       | 目标状态            | 初始任务 + 方法      |
# | 解的来源   | 搜索发现            | 配方约束             |
# | 长任务效率 | 差(指数)            | 好(沿配方树)         |
# | 灵活性     | 高(可发现新解)      | 低(限于配方)         |

⚠️ 常见陷阱¶

陷阱 4-1（编程陷阱）：原子动作就地修改状态，破坏回溯。 - 错误描述：operator 直接改传入的 state 而非返回深拷贝（见 Step 3 错误 1）。 - 现象/后果：当一条方法失败、需回溯尝试另一条时，世界状态已被污染，前提判断全错，规划器要么找不到本存在的解、要么产出非法计划。 - 根本原因：HTN 搜索本质是带回溯的 DFS，回溯要求状态可还原。就地修改让"撤销"无法实现。 - 正确做法：operator 永远返回新状态（深拷贝后修改），原状态保持不变；失败回溯时自然用回未被污染的旧状态。

陷阱 4-2（概念误区）：以为 HTN 方法写得越少越好。 - 错误描述：只写一条方法覆盖"理想情况"，不写处理异常/变体的方法。 - 现象/后果：稍微偏离理想情况（包裹已在 dock、手里已拿着东西、货架够不到）规划就失败，因为没有适用的方法。 - 根本原因：HTN 的能力上限由方法集合决定。方法没覆盖到的情况，规划器无法"自己想办法"（这正是它和 STRIPS 的区别）。 - 正确做法：为每个复合任务写多条方法覆盖主要变体（含 base case 和异常处理）。这是 HTN 的工程负担，也是它换来效率必须付的代价。

陷阱 4-3（思维陷阱）：把 HTN 当成 STRIPS 的"加速版"，期望它能找 STRIPS 能找的所有解。 - 错误描述：以为 HTN 只是更快，解集合和 STRIPS 一样。 - 现象/后果：明明存在一个可行解，HTN 却返回失败——因为那个解不符合任何配方的结构。 - 根本原因：HTN 的解被方法严格约束。它不是"在所有可行解里搜得更快"，而是"只在配方允许的解里搜"。两者的解集合不同。 - 正确做法：理解 HTN 是用"限制解集合"换效率。若你需要"任意可行解"，用 STRIPS；若你接受"符合标准流程的解"，用 HTN。机器人操作多属后者。

练习¶

（⭐⭐，实现） 给 §4.5 的送货 domain 加一个新的复合任务 deliver_batch(pkgs)：机器人一次最多抓 1 个包裹（已有约束），但要求就近优先——每次选离当前位置最近的未送包裹先送。写出对应的方法（需要状态里有位置坐标和距离计算）。
（⭐⭐，调试） 故意把 m_deliver_all 的 base case 删掉（不处理空列表），运行观察失败现象，然后解释为什么递归 HTN 必须有终止方法。
（⭐⭐⭐，设计） 为送货 domain 写两条 deliver 方法：方法 A 是"取一个送一个"，方法 B 是"如果两个包裹在同一货架，一次抓不了但可以连续取送省去往返"。讨论规划器如何在两条方法间选择，以及这体现了 HTN 的什么特性。
（⭐⭐⭐⭐，跨节综合） 结合 §3：HTN 几乎不需要 §3 的删除松弛启发式，为什么？（提示：HTN 的搜索空间已被配方大幅压缩，分支因子小。）反过来，什么情况下你会想给 HTN 也加启发式？给一个场景。

5. 时序与数值规划 ⭐⭐⭐¶

5.1 动机：经典规划缺了时间、并发和资源¶

到目前为止，§3-§4 的规划都活在一个"无时间"的世界里：动作是瞬时的、串行的，世界状态只有"命题真假"没有"连续数值"。但真实机器人系统三样都缺不了：

时长 (duration)：移动到货架要 30 秒，充电要 10 分钟。动作占据一段时间，不是一瞬间。
并发 (concurrency)：$R_1$ 在搬货时 $R_2$ 同时在充电——多个动作时间上重叠。经典规划的串行序列表达不了"同时"。
数值/资源 (numeric / resource)：电量从 80% 降到 20%，载重不能超过 50kg。这些是连续量，不是命题。

本质洞察：从经典规划到时序规划，是从"逻辑世界"到"时空世界"的跨越——和 TAMP_T1 §2.5 描述的"符号 vs 几何"鸿沟是同一类跨越的不同侧面。经典规划只关心"命题在序列上的真假翻转"；时序规划必须把动作钉在时间轴上，处理"何时开始、持续多久、与谁重叠、消耗多少资源"。这不是给经典规划"加个时间戳"那么简单——并发让"前提何时需要满足""效果何时生效"都变成需要精确定义的语义问题。

5.2 PDDL 2.1：durative action¶

PDDL 2.1 (Fox & Long 2003, JAIR 20:61-124) 是为时序规划设计的 PDDL 扩展，核心是 durative action（有时长动作）。它把一个动作从"瞬时"展开为"一段时间"，并精确规定前提和效果在这段时间的哪个时刻起作用：

时间锚点	关键字	含义
开始时刻	`at start`	动作启动瞬间检查的前提 / 产生的效果
结束时刻	`at end`	动作完成瞬间检查的前提 / 产生的效果
全程	`over all`	动作执行期间必须始终保持的前提（不变式 invariant）

一个移动动作的 PDDL 2.1 写法（仓库机器人从 dock 到货架，耗时 30）：

(:durative-action move
  :parameters (?r - robot ?from ?to - location)
  :duration (= ?duration 30)
  :condition (and
    (at start (robot-at ?r ?from))      ; 启动时必须在 from
    (over all (charged ?r)))            ; 全程必须有电(不变式)
  :effect (and
    (at start (not (robot-at ?r ?from))); 一启动就离开 from
    (at end (robot-at ?r ?to))))        ; 30秒后到达 to

为什么需要 over all 这个"全程不变式"？ 这是并发语义的关键。考虑"机器人移动时必须保持有电"——如果只在 at start 检查有电，那么另一个动作可能在移动中途把电耗光，而经典规划无法表达"移动期间不许有电变成无电"。over all 正是为此：它声明一段持续的保护条件，让并发的其他动作不能破坏它。

并发从何而来？ 因为动作占据时间区间 $[t_{\text{start}}, t_{\text{end}}]$，两个动作的区间可以重叠——只要它们不冲突（一个的 over all 不被另一个的效果破坏）。时序规划器要做的，就是把所有动作的区间排在时间轴上，既满足因果（效果在需要它的前提之前发生），又不违反任何不变式。

5.3 简单时序网络 STN：约束传播与一致性¶

有了 durative action，规划器内部需要一个工具来管理"哪些事件先于哪些、间隔多少"——这就是简单时序网络 (Simple Temporal Network, STN)，由 Dechter、Meiri、Pearl (1991) 提出。

STN 是什么？ 一组时间点变量 $\{t_1, t_2, \dots\}$（每个代表一个事件发生的时刻，如"move 开始""move 结束"），加上一组二元时序约束，每条形如： $$ a \le t_j - t_i \le b $$ 即"事件 $j$ 比事件 $i$ 晚发生，间隔在 $[a, b]$ 之间"。例如 move 的时长固定 30，就是 $30 \le t_{\text{end}} - t_{\text{start}} \le 30$；"取货必须在到货架后 5 秒内开始"，就是 $0 \le t_{\text{pick}} - t_{\text{arrive}} \le 5$。

核心问题：这组约束自洽吗（consistent）？ 也就是说，存在一组时刻赋值同时满足所有约束吗？如果约束互相矛盾（如"A 在 B 后至少 10 秒"且"B 在 A 后至少 5 秒"），就无解。

关键技巧：把 STN 变成一张带权有向图（距离图 distance graph），用最短路检测一致性。

把每条约束 $t_j - t_i \le b$ 看作一条从 $i$ 到 $j$、权重为 $b$ 的边（约束 $t_j - t_i \ge a$ 等价于 $t_i - t_j \le -a$，是一条从 $j$ 到 $i$、权重 $-a$ 的边）。于是：

STN 一致当且仅当距离图中没有负权环 (negative cycle)。

为什么？一个负权环意味着"绕一圈回来，时间净减少了"——这是逻辑矛盾（你不可能比自己更早）。检测负权环的标准算法是 Floyd-Warshall（全源最短路，$O(n^3)$）或 Bellman-Ford（单源，$O(VE)$）：跑完后若任何节点到自己的最短距离为负，就存在负权环，STN 不一致。

这和大纲 T 线的 ST 图有什么关系？ 这是一个值得点明的跨章联系。T1（10_时空规划）的 ST 图（s-t 空间）处理的是"沿一条路径，在什么时刻到达什么位置"的连续轨迹时序；这里的 STN 处理的是"离散事件之间的时序约束"。像的地方：都把"时间"作为一等公民、都要保证时序自洽。不像的地方：ST 图是连续的几何对象（用于轨迹优化），STN 是离散的约束网络（用于符号规划的时序一致性）。一个面向运动层，一个面向任务层——又一次印证了 §2 的三层栈。

5.4 代码：STN 一致性检查¶

下面实现 STN 一致性检查：构建距离图，跑 Floyd-Warshall，检测负权环。

Step 1：为什么用 Floyd-Warshall 检测负权环。

STN 一致性 <=> 距离图无负权环。Floyd-Warshall 求出所有点对最短距离 d[i][j],
跑完后若存在 d[i][i] < 0, 说明从 i 出发绕一圈能回到 i 且总权重为负 ->
存在负权环 -> STN 不一致(约束自相矛盾, 无可行时刻赋值)。

约束 -> 边的转换:
  t_j - t_i <= b   ==>  边 i->j 权重 b
  t_j - t_i >= a   ==>  t_i - t_j <= -a  ==>  边 j->i 权重 -a
  所以一条双边约束 a <= t_j - t_i <= b 产生两条边。

Step 2：正确写法。

INF = float("inf")

def build_distance_graph(num_points, constraints):
    """constraints: 列表, 每项 (i, j, a, b) 表示 a <= t_j - t_i <= b。
    返回邻接矩阵 d (距离图), d[i][j] 为约束给出的 t_j - t_i 上界。"""
    n = num_points
    d = [[INF] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for (i, j, a, b) in constraints:
        # t_j - t_i <= b  -> 边 i->j 权重 b
        d[i][j] = min(d[i][j], b)
        # t_j - t_i >= a  -> t_i - t_j <= -a -> 边 j->i 权重 -a
        d[j][i] = min(d[j][i], -a)
    return d

def stn_consistent(num_points, constraints):
    """Floyd-Warshall 求全源最短路, 检测负权环 -> STN 是否一致。"""
    d = build_distance_graph(num_points, constraints)
    n = num_points
    for k in range(n):                    # Floyd-Warshall
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    for i in range(n):                    # 检测负权环
        if d[i][i] < 0:
            return False, d               # 不一致
    return True, d                        # 一致, d 含点对最短距离(可读出时间窗)

# ---- 仓库时序例子 ----
# 时间点: 0=move_start, 1=move_end, 2=pick_start
# 约束: move 时长固定 30; pick 必须在 move_end 后 0~5 内开始
cons = [
    (0, 1, 30, 30),    # 30 <= t_end - t_start <= 30
    (1, 2, 0, 5),      # 0  <= t_pick - t_end   <= 5
]
ok, dist = stn_consistent(3, cons)
print("一致?", ok)     # True

# ---- 制造一个矛盾: pick 必须在 move_end 之前(不可能, 货还没到) ----
cons_bad = cons + [(2, 1, 1, 10)]   # 1 <= t_end - t_pick <= 10, 即 pick 在 end 前
ok2, _ = stn_consistent(3, cons_bad)
print("一致?", ok2)    # False (与 pick 在 end 后矛盾 -> 负权环)

Step 3：错误写法并解释为什么错。

# ❌ 错误 1: 把双边约束当单边, 只加一条边
#   只写 d[i][j] = b, 漏掉 d[j][i] = -a
# 问题: 丢失下界约束 t_j - t_i >= a。一致性检查会漏报矛盾,
#      因为只有上界没有下界, 永远不会形成负权环。双边约束必须两条边都加。

# ❌ 错误 2: 用普通 Dijkstra 检测, 而非 Floyd-Warshall/Bellman-Ford
# 问题: Dijkstra 不能处理负权边 (STN 距离图必然有负权边, 因为下界约束 -a)。
#      负权边下 Dijkstra 给出错误最短路, 检测不出负权环。必须用能处理负权的算法。

# ❌ 错误 3: 检测一致性时只看 d[0][0], 不遍历所有 d[i][i]
#   if d[0][0] < 0: return False
# 问题: 负权环可能不经过节点 0。必须检查每个 d[i][i] < 0。

Step 4：STN 之上——能读出时间窗。

# Floyd-Warshall 跑完后, d 不仅判一致, 还给出每对事件的时间窗:
#   d[i][j]  = t_j - t_i 的上界 (最大间隔)
#  -d[j][i]  = t_j - t_i 的下界 (最小间隔)
# 这对调度极有用 —— 告诉你"pick 最早/最晚能在 move_start 后多久开始"

ok, d = stn_consistent(3, cons)
i, j = 0, 2     # move_start -> pick_start
print(f"pick_start 相对 move_start 的窗口: [{-d[j][i]}, {d[i][j]}]")
# 输出 [30, 35]: pick 最早在 move 开始后 30s(刚到货架), 最晚 35s(5s 容差内)

# 对比: 若只想判一致性, Floyd-Warshall 的全源最短路是"顺便"算出来的副产品,
#      而这些时间窗正是时序规划器排程、以及和运动层(T线 ST图)对接的接口。

⚠️ 常见陷阱¶

陷阱 5-1（概念误区）：以为 durative action 就是"瞬时动作加个时间戳"。 - 错误描述：把有时长动作理解为"动作照旧，只是记一下花了多久"。 - 现象/后果：忽略 over all 不变式和并发语义，规划出的"并发"计划实则在执行时冲突（一个动作中途破坏了另一个动作的保护条件）。 - 根本原因：时长引入了"动作执行期间"这个新的时间区域，前提/效果在 start/end/over-all 三处的语义截然不同。瞬时动作没有"期间"，所以没有这个复杂度。 - 正确做法：明确区分 at start/at end/over all，尤其用 over all 声明执行期间必须保持的不变式，让并发动作不能破坏它。

陷阱 5-2（编程陷阱）：用 Dijkstra 检测 STN 一致性。 - 错误描述：图算法默认抄 Dijkstra（见 Step 3 错误 2）。 - 现象/后果：STN 距离图必含负权边（下界约束转成 $-a$），Dijkstra 在负权边下给出错误结果，漏报不一致。 - 根本原因：Dijkstra 的正确性依赖非负权边假设；STN 天然有负权边。 - 正确做法：用 Floyd-Warshall（全源，还顺带给出时间窗）或 Bellman-Ford（单源，专测负权环）。

陷阱 5-3（思维陷阱）：把时序规划的"时间"和运动层的"时间"混为一谈。 - 错误描述：以为 §5 的 STN 时序和 T 线 ST 图的轨迹时序是同一回事。 - 现象/后果：试图用 STN 解决连续轨迹的时间分配，或用 ST 图解决离散事件的时序约束，工具用错层。 - 根本原因：STN 处理离散事件间的约束（任务层），ST 图处理连续轨迹的时空（运动层）。它们都关心时间，但抽象层级不同。 - 正确做法：任务层时序一致性用 STN；运动层轨迹时间分配用 ST 图/时空优化（见 T 线）。两者通过"动作的时间窗"接口对接（见 Step 4）。

练习¶

（⭐⭐，建模） 用 PDDL 2.1 的 durative-action 写一个"充电"动作：耗时 600 秒，启动时机器人必须在充电桩、全程必须不在移动，结束时电量变为满。明确标出哪些是 at start/at end/over all。
（⭐⭐，实现/调试） 给 §5.4 的 STN 再加两个事件（如 $R_2$ 的 move）和约束，构造一个"看似合理但实则矛盾"的约束集，用代码检测出不一致，并手动找出是哪几条约束形成了负权环。
（⭐⭐⭐，设计扩展） 扩展 §5.4 的代码：一致时，输出每个事件相对第一个事件（$t_0$）的最早/最晚发生时刻（提示：把 $t_0$ 设为参考点 0，读 $d[0][i]$ 和 $-d[i][0]$）。这就是一个最小调度器的雏形。
（⭐⭐⭐⭐，跨节综合） 结合 §2 和 T 线 ST 图：假设规划层用 STN 排出"$R_1$ 在 $[0,30]$ 移动到货架"，运动层需要为这段生成实际轨迹。运动层算出实际无碰撞轨迹要 35 秒（比 STN 假设的 30 长）。这个失败应该如何反馈给规划层的 STN？写出反馈触发的约束更新。

6. 任务分配总论：MRTA 分类学 ⭐⭐¶

6.1 动机：同样是"分配"，难度天差地别¶

回到仓库：5 个包裹分给 3 台机器人。最朴素的想法是枚举所有分法选最好的——但分法数量是 $3^5 = 243$，看似不多。可一旦问题稍变，组合就爆炸：如果每台机器人要送多个包裹且顺序影响代价（顺路便宜、绕路贵），就要枚举所有"分配 + 排序"的组合；如果某些包裹太重需要两台机器人合搬，又多一个维度。问题规模和难度，取决于问题的"种类"。

这就引出一个比"怎么解"更前置的问题：怎么判断我面对的是哪一类分配问题？ 没有这个判断，你会犯 §2 陷阱 2-1 的错误——拿一把锤子（比如 CBBA）砸所有问题。

多机器人任务分配 (Multi-Robot Task Allocation, MRTA) 领域的奠基性工作 Gerkey & Matarić (2004, IJRR 23(9):939-954) 给出了一套领域无关的分类学，把纷繁的 MRTA 问题归到几个格子里，并指出每个格子等价于哪个经典优化问题、有多难。掌握这套分类学，是本章主干 B 的第一要务。

6.2 Gerkey-Matarić 分类学：三个维度¶

分类沿三个二元维度展开，组合出 $2^3 = 8$ 类问题：

维度	两个取值	含义
机器人能力	ST (Single-Task) / MT (Multi-Task)	一台机器人同一时刻能执行 1 个任务 (ST) 还是多个任务 (MT)
任务需求	SR (Single-Robot) / MR (Multi-Robot)	一个任务需要 1 台机器人 (SR) 还是多台协作 (MR) 才能完成
分配时效	IA (Instantaneous) / TA (Time-extended)	只做当下一次性分配 (IA)，还是要规划未来一段的任务序列 (TA)

记法形如 ST-SR-IA（单任务机器人、单机器人任务、瞬时分配）。三个维度对仓库场景的含义：

ST vs MT：机器人一次只能抓一个包裹（ST），还是有多个机械臂能同时抓多个（MT）。
SR vs MR：每个包裹一台机器人就能搬（SR），还是有超重包裹要两台合搬（MR）。
IA vs TA：只决定"此刻每台机器人去搬哪一个"（IA），还是要排出"每台机器人接下来依次搬哪几个"（TA）。

6.3 每个格子有多难——这是分类学的真正价值¶

分类不是为了起名字，而是为了知道每类问题的复杂度和对应的经典优化问题。Gerkey-Matarić 的核心贡献正是把 MRTA 各格映射到运筹学/组合优化的已知问题：

类别	等价的经典问题	复杂度	仓库场景例子	本章对应解法
ST-SR-IA	线性指派问题 (LAP) / 最优二部匹配	多项式可解 $O(n^3)$	此刻把每个空闲机器人配一个最近包裹	§7 匈牙利算法
ST-SR-TA	调度 / 多旅行商 (mTSP) 类	NP-hard	给每台机器人排一串包裹，最小化总时间	§7 MILP；§8 拍卖近似
ST-MR-IA	集合划分 (set partitioning) / 联盟形成	NP-hard	此刻把机器人分组，每组合搬一个超重包裹	§7 MILP（小规模）；近似
MT-SR-IA	一台机器人可领多任务的指派	NP-hard	每台机器人同时处理多个包裹的指派	§7 MILP
MT-MR-TA	最一般，含上述所有困难	NP-hard（最难）	多臂机器人、合作任务、未来排程全有	分解 + 启发式

本质洞察：MRTA 分类学的精髓是一句话——"瞬时 + 单机器人任务 + 单任务机器人" (ST-SR-IA) 是唯一多项式可解的格子，其余全是 NP-hard。 这个"难度悬崖"告诉你：一旦你的问题离开 ST-SR-IA 那一格（要排未来 = TA、要协作 = MR、要并行多任务 = MT），就别指望多项式最优算法，必须在"小规模求精确 (MILP)"和"大规模求近似 (拍卖/启发式)"之间权衡。先用分类学定位，再选解法——这是避免 §2 陷阱 2-1（拿锤子砸一切）的根本方法。

为什么 ST-SR-IA 恰好多项式可解？ 因为它精确对应线性指派问题：$n$ 个机器人、$n$ 个任务、一张代价矩阵，每个机器人配一个任务、每个任务配一个机器人，最小化总代价。这是二部图最小权完美匹配，匈牙利算法 $O(n^3)$ 解出最优（§7 详解）。一旦加上"未来序列"(TA) 或"协作"(MR)，问题就从"匹配"变成"匹配 + 排序"或"匹配 + 分组"，组合结构变质，跌入 NP-hard。

6.4 Korsah iTax：补上"依赖"维度¶

Gerkey-Matarić 分类学有一个默认假设：任务的代价/收益彼此独立——把任务 A 分给某机器人的代价，不受它是否还被分了任务 B 影响。但真实问题常常违反这点（顺路送两个包裹比分开送便宜，这就是任务间的依赖）。Korsah、Stentz、Dias (2013, IJRR 32(12):1495-1512) 提出 iTax，显式补上"任务间依赖"这一维度，分成四级：

依赖级别	英文	含义	仓库例子
ND	No Dependencies	任务代价完全独立	每个包裹的搬运代价固定，与别的包裹无关
ID	In-schedule Dependencies	代价依赖同一机器人自己的其他任务	顺路：$R_1$ 送 $p_1$ 的代价取决于它还要不要送顺路的 $p_4$
XD	Cross-schedule Dependencies	代价依赖其他机器人的任务安排	避让：$R_1$ 的路线代价取决于 $R_2$ 走哪条路（会不会堵）
CD	Complex Dependencies	代价依赖任务如何被分解（任务本身可多种拆法）	超重包裹既可两台合搬、也可拆成两半分别搬，选哪种影响代价

本质洞察：Gerkey-Matarić 回答"问题有多大、多并行"，iTax 回答"任务之间有多纠缠"。两者正交、互补：一个完整的 MRTA 问题定位需要两套坐标——它在 ST/MT×SR/MR×IA/TA 的哪一格 + 它的依赖是 ND/ID/XD/CD 哪一级。依赖越往 CD 走，问题越接近本章 §9 要讲的"分配-规划耦合"——因为"任务怎么拆、谁顺路、谁避让"本质上需要规划信息才能算清代价，分配和规划再也分不开。iTax 的 XD/CD 级，正是单纯分配算法（如 CBBA）失效、必须走向联合求解的分界线。

6.5 把已知算法安放进地图¶

现在可以给本章和 Multi_03 涉及的算法一个精确坐标了——这正是 §2.4 承诺的"给 CBBA 找到它在整张地图上的位置"：

算法	所在格子	依赖级别	集中/分布	出处
匈牙利算法（§7）	ST-SR-IA	ND	集中	§7
MILP 通用建模（§7）	多数格子（小规模）	ND~XD	集中	§7
序贯单物品拍卖 SSI（§8）	ST-SR-TA	ND~ID	可分布	§8
CBBA（Multi_03，§8 回顾）	ST-SR-TA	ID（捆绑内顺路）	分布	Choi 2009
CBS / MAPF（Multi_03）	分配已定后的路径协调	XD（避让）	集中/分布	Sharon 2015

读到这里，§2.4 的承诺兑现了：CBBA 不是"任务分配"的全部，它精确地坐在 "ST-SR-TA + 分布式 + 处理捆绑内顺路依赖" 这一格。它解决不了 MR（协作任务）、解决不了 CD（任务可多种分解），那些要靠 §7 的 MILP 或 §9 的联合方法。

⚠️ 常见陷阱¶

陷阱 6-1（思维陷阱）：跳过分类、直接选算法。 - 错误描述：拿到多机分配问题，不分析它属于哪一格，直接套最熟悉的算法（常是 CBBA 或匈牙利）。 - 现象/后果：在 MR/CD 类问题上硬套 ST-SR 算法，建模严重失真（如把"两台合搬"拆成两个独立任务，丢失协作约束），结果不可行或远非最优。 - 根本原因：不同格子的问题结构本质不同，一类算法只覆盖特定格子。 - 正确做法：先用 Gerkey-Matarić + iTax 两套坐标定位问题，再查 §6.5 的地图选解法。定位是选型的前提。

陷阱 6-2（概念误区）：以为 TA（时间扩展）只是"做多次 IA”。 - 错误描述：认为"排未来序列"就是"反复做瞬时分配"。 - 现象/后果：用贪心地反复解 IA 来近似 TA，得到的序列质量差——因为它看不到未来，每步都局部最优、整体却很糟（如每次都派最近的，结果机器人来回折返）。 - 根本原因：TA 的最优性依赖前瞻整个序列，与 IA 的"只看当下"有本质区别。TA 是 NP-hard 正因为它要在指数多的序列里找最优，不是简单地重复 IA。 - 正确做法：TA 问题要么用 MILP 一次性优化整个序列（小规模），要么用专门的序贯/捆绑拍卖（§8）做前瞻近似，而非朴素重复 IA。

陷阱 6-3（概念误区）：忽视 iTax 依赖维度，把有依赖的任务当独立任务。 - 错误描述：明明任务间有顺路（ID）或避让（XD）依赖，却用代价独立的模型。 - 现象/后果：算出的"最优"分配在执行时代价远超预期（没算上绕路），或多机互相阻塞（没算上避让）。 - 根本原因：代价独立假设破裂时，独立模型的目标函数和真实代价系统性偏离。 - 正确做法：识别依赖级别（ID/XD/CD），用能表达依赖的模型——ID 可用捆绑拍卖（出价时考虑顺路），XD/CD 往往要走向 §9 的联合求解。

练习¶

（⭐，分类） 给下列仓库场景各自标出 Gerkey-Matarić 类别和 iTax 依赖级别：(a) 此刻把 3 个空闲机器人各配一个最近包裹；(b) 给每台机器人排出今天要送的 10 个包裹的顺序，顺路省时间；(c) 一个 80kg 包裹需要两台机器人合搬。
（⭐⭐，推理） 解释为什么"加上 MR（协作任务）"会让问题从多项式跌入 NP-hard。提示：MR 引入了"哪些机器人组成一个联盟"的选择，对应集合划分问题。
（⭐⭐⭐，综合） 设计一个仓库场景，它同时是 MT-MR-TA 且依赖级别为 CD。说清每个维度为什么取这个值，并讨论这种问题为什么几乎不可能用单一现成算法解决（提示：联系 §9）。

7. 优化式任务分配：匈牙利与 MILP ⭐⭐⭐¶

7.1 动机：ST-SR-IA 那一格怎么解到最优¶

§6 告诉我们 ST-SR-IA 等价于线性指派问题、多项式可解。本节兑现"怎么解"：先讲解这一格的专用利器匈牙利算法，再讲当问题离开这一格（带容量、带约束）时的通用工具整数规划 (MILP)。这两者构成"集中式、要最优"那条分配主线（与 §8 "分布式、可扩展"那条主线对照）。

7.2 线性指派问题与匈牙利算法¶

问题精确陈述。 $n$ 个机器人、$n$ 个任务，代价矩阵 $C \in \mathbb{R}^{n\times n}$，$C_{ij}$ = 机器人 $i$ 做任务 $j$ 的代价。要找一个一一对应（指派）$\sigma$，每个机器人恰好一个任务、每个任务恰好一个机器人，最小化总代价： $$ \min_{\sigma \in S_n} \sum_{i=1}^{n} C_{i,\sigma(i)} $$ 其中 $S_n$ 是所有排列。朴素枚举要算 $n!$ 种排列——$n=10$ 就是 360 万，$n=20$ 已是天文数字。匈牙利算法把它降到 $O(n^3)$。

匈牙利算法的核心洞察（Kuhn 1955）。 算法基于一个关键定理：

从代价矩阵的某一行（或某一列）的所有元素减去同一个常数，最优指派不变（只是总代价整体减少了那个常数）。

为什么？因为任何完美指派恰好在每行选一个元素，所以"某行整体减 $k$"会让所有指派的总代价都减少 $k$——相对优劣不变，最优解还是最优解。

利用这个定理，匈牙利算法的思路是：通过反复减行/列最小值，制造出尽量多的 0；目标是凑出一组"位于 0 上的完美指派"（总代价 = 0，显然最优）。具体迭代（概念版）：

1. 行规约: 每行减去该行最小值 (每行至少出现一个 0)
2. 列规约: 每列减去该列最小值 (每列至少出现一个 0)
3. 用最少的横线/竖线覆盖所有 0:
     - 若线数 = n, 存在仅在 0 上的完美指派, 完成
     - 若线数 < n, 在未被覆盖元素里找最小值 m,
       未覆盖元素减 m, 被覆盖两次的元素加 m, 回到第 3 步

每一轮制造新的 0、保持最优性不变，直到能找到完美的"0 指派"。这套"减常数不改最优 + 找覆盖"的机制，本质是线性规划对偶（行/列减的常数就是对偶变量），但工程上你几乎不需要手写——scipy 一行搞定。

本质洞察：匈牙利算法之所以能从 $O(n!)$ 降到 $O(n^3)$，是因为它没有枚举指派，而是利用"减常数不改最优"这个结构，把"找最优指派"转化为"凑出零代价指派"。这是组合优化的典型智慧——不暴力搜索解空间，而是利用问题的代数结构（这里是 LP 对偶）把搜索压缩。同样的智慧你在 §3 的删除松弛（用松弛结构造启发式）里见过，在 §8 的拍卖（用市场机制分布式逼近最优）里还会见到。

7.3 代码：用匈牙利算法解 ST-SR-IA¶

Step 1：为什么用 scipy.optimize.linear_sum_assignment。

匈牙利算法虽然原理清晰, 但完整 O(n³) 实现 (含覆盖线、增广路) 细节繁琐、
易写错。scipy 的 linear_sum_assignment 是经过验证的工业实现, 直接用即可。
工程原则: 标准算法用成熟库, 把精力放在"建对代价矩阵"上 ——
         代价矩阵建错(目标函数错), 算法再对也白搭。

输入: 代价矩阵 C (n×n, 或非方阵 m×n)
输出: row_ind, col_ind, 使 C[row_ind, col_ind] 之和最小

Step 2：正确写法。

import numpy as np
from scipy.optimize import linear_sum_assignment

# 仓库 ST-SR-IA: 3 台机器人, 3 个包裹, 代价 = 机器人到包裹的距离
# C[i][j] = 机器人 i 去取包裹 j 的代价(如行驶距离)
C = np.array([
    [4, 2, 8],     # R0 到 p0,p1,p2 的代价
    [4, 3, 7],     # R1
    [3, 1, 6],     # R2
], dtype=float)

row_ind, col_ind = linear_sum_assignment(C)   # 最小化总代价
total = C[row_ind, col_ind].sum()
print("最优指派:")
for r, c in zip(row_ind, col_ind):
    print(f"  机器人 R{r} -> 包裹 p{c}  (代价 {C[r, c]})")
print("总代价:", total)
# 最优: R0->p2? 不一定, 由算法全局最优决定; 关键是总代价最小

# 最大化收益版本: 取负号(或用 C.max()-C)再最小化
reward = np.array([[9, 7, 1], [5, 8, 3], [6, 4, 9]], dtype=float)
r2, c2 = linear_sum_assignment(-reward)        # 最大化 = 最小化负收益
print("最大收益指派总收益:", reward[r2, c2].sum())

Step 3：错误写法并解释为什么错。

# ❌ 错误 1: 贪心分配 —— 每台机器人选自己最便宜的任务
def greedy_assign_wrong(C):
    n = len(C); assigned = {}; used_tasks = set()
    for i in range(n):
        best = min((j for j in range(n) if j not in used_tasks),
                   key=lambda j: C[i][j])
        assigned[i] = best; used_tasks.add(best)
    return assigned
# 问题: 贪心不保证全局最优。R0 抢了 R2 唯一便宜的任务, 逼 R2 选很贵的,
#      总代价可能远大于匈牙利的最优解。ST-SR-IA 存在多项式最优算法,
#      没理由用贪心牺牲最优性。(贪心只在 §8 分布式、规模大到 MILP 跑不动时才用)

# ❌ 错误 2: 把"最大化收益"直接喂给最小化求解器, 不取负
#   linear_sum_assignment(reward)  # 这是在最小化收益! 结果完全相反
# 问题: linear_sum_assignment 永远最小化。最大化必须先取负或用 (max - reward)。

# ❌ 错误 3: 非方阵时误以为能完美匹配所有
#   C 是 3 机器人 × 5 任务, 期望 5 个任务都被分配
# 问题: linear_sum_assignment 对 m×n 非方阵只匹配 min(m,n) 对。
#      3 台机器人一次只能领 3 个任务(ST!), 剩 2 个本轮无人做 ——
#      这正是 ST-SR-IA 是"瞬时"分配的体现, 剩余任务要下一轮或转 TA 问题。

Step 4：匈牙利 vs 贪心的代价对比（量化）。

def greedy_cost(C):
    n = len(C); used = set(); total = 0
    for i in range(n):
        j = min((k for k in range(n) if k not in used), key=lambda k: C[i][k])
        used.add(j); total += C[i][j]
    return total

# 构造一个贪心吃亏的例子
C = np.array([[1, 9, 9], [1, 9, 9], [9, 1, 2]], dtype=float)
ri, ci = linear_sum_assignment(C)
print("匈牙利最优总代价:", C[ri, ci].sum())   # R0->p0(1) 或 R1->p0(1), 全局协调
print("贪心总代价:      ", greedy_cost(C))     # R0,R1 都抢 p0, 冲突后被迫选 9
# 典型结果: 匈牙利明显更低。规模越大、代价越"对抗", 差距越显著。

7.4 离开 ST-SR-IA：用 MILP 通用建模¶

匈牙利只解 ST-SR-IA 这一格。一旦问题带上容量（一台机器人最多领 3 个任务）、协作（MR）、预算（总成本上限）等约束，就超出指派问题，需要更通用的工具——混合整数线性规划 (Mixed-Integer Linear Programming, MILP)。

MILP 的威力在于"声明式建模"：你只需用线性约束和线性目标描述问题，求解器（CBC、Gurobi、CPLEX、OR-Tools）自动求最优。代价是 NP-hard，所以只适合中小规模。

广义指派问题 (Generalized Assignment Problem, GAP) 的 MILP 建模——这是带容量的 MT-SR 类：

决策变量：$x_{ij} \in \{0, 1\}$，机器人 $i$ 是否做任务 $j$。

\[ \begin{aligned} \min \quad & \sum_{i}\sum_{j} c_{ij}\, x_{ij} & \text{(总代价最小)}\\ \text{s.t.} \quad & \sum_{i} x_{ij} = 1 \quad \forall j & \text{(每个任务恰好一台机器人做)}\\ & \sum_{j} w_{ij}\, x_{ij} \le b_i \quad \forall i & \text{(机器人 } i \text{ 的容量约束)}\\ & x_{ij} \in \{0, 1\} & \text{(二元决策)} \end{aligned} \]

其中 $w_{ij}$ 是任务 $j$ 对机器人 $i$ 的资源占用（时间/载重），$b_i$ 是机器人 $i$ 的容量。注意：去掉容量约束、令 $i,j$ 等量，这个 MILP 就退化成 ST-SR-IA（匈牙利能解的那格）——MILP 是分配问题的"通用语言"，匈牙利是其中一个特例的快速专解。

7.5 代码：用 PuLP 建模 MILP 分配¶

Step 1：为什么用声明式建模工具。

MILP 不需要你写求解算法 —— 你只"声明"变量、目标、约束, 求解器(默认 CBC)自动解。
这是和匈牙利完全不同的范式: 匈牙利是"调一个特定算法", MILP 是"描述一个问题"。
PuLP 是轻量的 Python 建模库, 语法接近数学公式, 适合教学和中小规模。
工程上规模大、要商用时换 Gurobi/OR-Tools, 但建模思路一致。

Step 2：正确写法。

import pulp

# 仓库带容量的分配: 3 机器人, 5 包裹, 每台机器人最多载重 b_i
robots = [0, 1, 2]
pkgs   = [0, 1, 2, 3, 4]
cost = {(i, j): c for i, row in enumerate([     # 机器人i送包裹j的代价
            [4, 2, 8, 5, 7], [4, 3, 7, 6, 5], [3, 1, 6, 4, 9]])
        for j, c in enumerate(row)}
weight = {0: 10, 1: 15, 2: 20, 3: 12, 4: 8}     # 各包裹重量
cap    = {0: 30, 1: 30, 2: 25}                  # 各机器人载重上限

prob = pulp.LpProblem("warehouse_assignment", pulp.LpMinimize)
# 决策变量 x[i,j] ∈ {0,1}
x = pulp.LpVariable.dicts("x", [(i, j) for i in robots for j in pkgs],
                          cat="Binary")
# 目标: 总代价最小
prob += pulp.lpSum(cost[i, j] * x[i, j] for i in robots for j in pkgs)
# 约束1: 每个包裹恰好被一台机器人送
for j in pkgs:
    prob += pulp.lpSum(x[i, j] for i in robots) == 1
# 约束2: 每台机器人不超载
for i in robots:
    prob += pulp.lpSum(weight[j] * x[i, j] for j in pkgs) <= cap[i]

prob.solve(pulp.PULP_CBC_CMD(msg=0))
print("状态:", pulp.LpStatus[prob.status])
for i in robots:
    load = sum(weight[j] for j in pkgs if x[i, j].value() == 1)
    got  = [j for j in pkgs if x[i, j].value() == 1]
    print(f"  R{i} 送 {got}, 载重 {load}/{cap[i]}")
print("总代价:", pulp.value(prob.objective))

Step 3：错误写法并解释为什么错。

# ❌ 错误 1: 把二元变量声明成连续变量
#   x = pulp.LpVariable.dicts("x", ..., lowBound=0, upBound=1)  # 连续 [0,1]!
# 问题: 这是 LP 松弛, 解可能出现 x[i,j]=0.5(半个机器人送半个包裹), 无物理意义。
#      分配必须用 cat="Binary"。(LP 松弛有用 —— 它给 MILP 下界, 但不是最终解)

# ❌ 错误 2: 约束写成 <= 1 而非 == 1, 导致包裹可不被送
#   prob += pulp.lpSum(x[i,j] for i in robots) <= 1   # 每个包裹"至多"一台
# 问题: 求解器会发现"不送任何包裹"代价最低(0), 于是什么都不分配。
#      若要求全部送达, 必须 == 1; 若允许丢弃(带丢弃惩罚)才用 <= 1。

# ❌ 错误 3: 忘记容量约束, MILP 退化成无约束指派却还期望它"分散负载"
# 问题: 没有容量约束时, 求解器可能把所有便宜的包裹堆给同一台机器人。
#      "负载均衡"不会自动发生, 必须显式写成约束(或写进目标)。

Step 4：匈牙利 vs MILP 的适用边界。

# === 什么时候用匈牙利, 什么时候用 MILP ===
# | 场景                          | 工具       | 理由                         |
# | ST-SR-IA, n≤数千               | 匈牙利     | 多项式 O(n³), 最快, 保证最优  |
# | 带容量/预算/协作约束            | MILP       | 匈牙利表达不了约束            |
# | 规模中小(几十~几百变量), 要最优 | MILP       | 求解器可接受时间内求精确解    |
# | 规模巨大或要分布式/在线         | 拍卖(§8)   | MILP 跑不动, 牺牲最优换可扩展 |

# 关键判断: 先看是不是 ST-SR-IA(用 §6 分类) -> 是则匈牙利;
#          否则看规模 -> 中小用 MILP, 巨大/分布式用拍卖。

⚠️ 常见陷阱¶

陷阱 7-1（思维陷阱）：在 ST-SR-IA 问题上用贪心而非匈牙利。 - 错误描述：图省事用"每台机器人选最便宜任务"的贪心，牺牲最优性。 - 现象/后果：贪心解的总代价可能显著高于最优（见 §7.3 Step 4），机器人间因抢任务而被迫做高代价分配。 - 根本原因：贪心只看局部，ST-SR-IA 的最优需要全局协调（一台机器人"让出"某任务可能让整体更优）。 - 正确做法：ST-SR-IA 直接用匈牙利（linear_sum_assignment），它多项式时间保证最优，没有理由用贪心。贪心只在规模大到 MILP/匈牙利都跑不动、或必须分布式时才考虑（此时用 §8 的拍卖更系统）。

陷阱 7-2（编程陷阱）：MILP 把二元变量声明成连续变量。 - 错误描述：用 lowBound=0, upBound=1 的连续变量代替 cat="Binary"（见 §7.5 Step 3）。 - 现象/后果：解出分数分配（0.5 个机器人送 0.5 个包裹），无法执行。 - 根本原因：连续变量给的是 LP 松弛解；分配的物理含义要求整数（0 或 1）。 - 正确做法：分配变量用 cat="Binary"。LP 松弛另有用途（给 MILP 提供下界、做分支定界的界），但不是可执行的分配解。

陷阱 7-3（概念误区）：以为 MILP "总能在合理时间内"解出最优。 - 错误描述：因为 MILP 求解器强大，就把任意规模问题丢给它。 - 现象/后果：变量数上千、约束复杂时，求解器跑数小时甚至不收敛。 - 根本原因：MILP 是 NP-hard，最坏情况指数时间。求解器在中小规模快，但不存在多项式保证。 - 正确做法：MILP 适合中小规模（几十到几百变量）。规模大时：要么用 §8 拍卖近似，要么用启发式（如先聚类再分配），要么接受次优解（设置求解时间上限和 gap 容差）。

陷阱 7-4（概念误区）：把 ST-SR-IA 的"瞬时"理解成"一次解决所有任务"。 - 错误描述：用匈牙利解 3 机器人 × 5 任务，期望 5 个任务全被分配。 - 现象/后果：非方阵只匹配 3 对，2 个任务"消失"，以为算法出错。 - 根本原因：ST 意味着一台机器人同一时刻只做一个任务；瞬时分配只决定"此刻每台机器人做哪一个"。任务多于机器人时，多出的本轮无人做。 - 正确做法：理解 IA 是"当下快照"。任务多于机器人时，要么分多轮 IA，要么升级为 TA 问题（排未来序列，用 §7 MILP 或 §8 拍卖）。

练习¶

（⭐⭐，实现） 用 linear_sum_assignment 解一个 5×5 的随机代价矩阵，并写一个暴力枚举 $5! = 120$ 种排列的函数验证匈牙利结果确实是最优。
（⭐⭐，建模） 修改 §7.5 的 MILP：加一个新约束"包裹 $p_0$ 和 $p_3$ 必须由同一台机器人送"（它们是一套，不能拆）。提示：对每台机器人 $i$ 加约束 $x_{i,0} = x_{i,3}$。
（⭐⭐⭐，建模扩展） 把 §7.5 的目标从"最小化总代价"改为"最小化最大单机负载（makespan 思路）"——即让最忙的机器人尽量轻。提示：引入辅助变量 $z \ge \sum_j w_{ij} x_{ij}$ 对所有 $i$，最小化 $z$。这把目标从 sum 变成 min-max，体现负载均衡。
（⭐⭐⭐⭐，跨节综合） 结合 §6 和 §9：§7.5 的 MILP 假设代价 $c_{ij}$ 是已知常数。但若代价是"机器人 $i$ 送包裹 $j$ 的实际路径长度"，而路径又取决于它同时被分了哪些别的包裹（ID 依赖），$c_{ij}$ 就不再是常数。这时 MILP 模型为什么不再准确？这正是 §9 要解决的耦合——简述困难。

8. 市场/拍卖式分配 ⭐⭐⭐¶

8.1 动机：当集中式最优解不可行时¶

§7 的匈牙利和 MILP 都是集中式的：需要一个中心节点掌握完整代价矩阵、统一求解、再把结果下发。这在两类场景下行不通：

规模太大：上千个任务、上千台机器人，MILP 跑不动（NP-hard 的指数墙），匈牙利的 $O(n^3)$ 在 $n$ 极大时也吃力，而且构造完整代价矩阵本身就要 $O(n^2)$ 次代价计算。
没有中心、通信受限：多台机器人分散在大场地，彼此只能局部通信，没有一个能看到全局的中心节点。仓库里三台机器人尚可集中，但几十架无人机在野外协同时，集中式既脆弱（中心失效全瘫）又不现实（通信带宽不够回传所有信息）。

市场机制提供了另一条路：把任务当成"商品"放到市场上拍卖，让机器人（"买家"）根据自己的代价出价 (bid)，价高者（或代价最低者）得标。这是一种分布式、可扩展的分配范式，用"局部决策 + 有限通信"逼近全局最优。它对应 §6 分类学里"分布式"那一栏，是与 §7"集中式、要最优"主线并列的第二条分配主线。

本质洞察：拍卖式分配的核心智慧，是把"全局组合优化"这个难题，分解成每个机器人各自能算的局部决策（我对这个任务出多少价）+ 一个简单的全局协调规则（谁出价最优谁得）。这和 §3 删除松弛"用结构化简化换可算性"、§7 匈牙利"用对偶结构换多项式"是同一种思想谱系——不正面强攻指数级的解空间，而是用某种机制把它拆解成可分布、可并行的小决策。代价是通常得不到全局最优，但换来了可扩展性与鲁棒性。市场机制之所以在经济学和多机器人里都有效，正因为"价格"是一种极其高效的信息压缩——它把一个机器人对一个任务的全部复杂考量（距离、电量、顺路与否）压缩成一个数。

8.2 拍卖的三个基本要素¶

任何拍卖式分配都由三件事定义：

要素	含义	仓库例子
拍卖什么 (items)	单个任务？还是一组任务打包（捆绑 bundle）？	单个包裹 / 一组顺路的包裹
怎么出价 (bidding rule)	机器人对一个任务出的"价"代表什么	把这个包裹加入我现有路线的边际代价（多走多远）
怎么定标 (winner determination)	收到所有出价后，按什么规则把任务判给谁	出价最低（代价最小）者得；或按 regret 最大定标

这三个要素的不同组合，长出了拍卖家族的不同成员。下面从最简单的单物品拍卖讲起，逐步加复杂度。

8.3 单物品拍卖与序贯单物品拍卖 (SSI)¶

最简单：一次性单物品拍卖。 一个任务、所有机器人各出一价、最低者得。这只能分配一个任务，对应 §6 的 ST-SR-IA 单次决策，本质和"取代价矩阵某一列的最小值"无异——太弱，不展开。

真正实用的：序贯单物品拍卖 (Sequential Single-Item auction, SSI)。 这是 Koenig 等人 2006 年起系统研究的方法，专治"给多台机器人分配多个任务"（ST-SR-TA，§6 那个 NP-hard 的格子）。它的精髓在于序贯 + 边际出价：

SSI 拍卖流程：
  未分配任务集 U = 全部任务
  while U 非空:
    1. 出价阶段: 每个机器人 r 对每个未分配任务 t∈U 出价
                bid(r,t) = 把 t 加入 r 当前路线的"边际代价"
                         = cost(r 的路线 ∪ {t}) - cost(r 的当前路线)
    2. 定标阶段: 在所有 (机器人,任务) 出价里, 选边际代价最小的那对 (r*,t*)
                把 t* 分配给 r*, 从 U 移除 t*
    3. r* 更新自己的路线(把 t* 插进去), 进入下一轮

每个机器人对每个未分配目标的出价，是它在已分配给自己的所有目标之外、再访问所投标目标所增加的机器人代价——这就是"边际代价"出价规则的精确含义。

为什么"边际代价"出价这么关键？ 因为它天然捕捉了 §6.4 的 ID 依赖（顺路）。如果任务 $t$ 正好在机器人 $r$ 已有路线的顺路上，那把 $t$ 加进去的边际代价很小，$r$ 的出价就低、容易得标——这正是我们想要的"顺路的人来做顺路的活"。SSI 不需要显式建模顺路，边际出价自动实现了它。

本质洞察：SSI 是一种贪心 + 前瞻的混合。它贪心地每轮只定一个任务（最小边际代价者），所以快；但"边际代价"这个出价规则让每次决策都前瞻了机器人已有的承诺（已分配的任务构成的路线），所以不像纯贪心那样短视。这解释了 §6 陷阱 6-2 的要点——TA 问题不能用"朴素重复 IA"来解，但 SSI 这种"序贯 + 边际"恰恰是重复单物品拍卖的正确做法：区别就在于出价考虑了已有路线，而非每轮从零评估。

定标规则的改进：regret clearing。 标准 SSI 每轮分配"边际代价最小"的那个任务。一个改进是 regret clearing：SSI with regret clearing 分配 regret 最大的任务，即两个最小出价之间差距最大的那个任务，这能提升性能。直觉是：如果某个任务只有一台机器人能低价做、其余都很贵（regret 大），就应该优先把它分配掉、锁定那台机器人，免得它被别的任务抢走后这个任务只能高价完成。

8.4 组合拍卖：表达协同价值¶

SSI 一次只卖一个任务，无法表达"打包折扣"——一组任务一起做可能比分开做的代价之和更省（如三个包裹都在同一条走廊上）。组合拍卖 (combinatorial auction) 允许机器人对任务的子集（捆绑 bundle） 出价，从而表达这种协同。

组合拍卖: 机器人对任务子集出价
  R1 对 {p1}      出价 5
  R1 对 {p1,p2}   出价 7   ← 协同! 一起做只要7, 不是5+另算
  R1 对 {p1,p2,p3} 出价 8
  ...
  定标: 选一组互不重叠的捆绑, 覆盖所有任务, 总出价最小(集合划分问题)

组合拍卖的代价：定标是 NP-hard。 它的胜者裁决等价于"加权集合划分问题 (weighted set partitioning)"——在指数多的捆绑组合里选一组不重叠、覆盖全部、总代价最小的，这本身就是 NP-hard。而且每个机器人要对指数多个子集出价，通信和计算都爆炸。序贯单物品拍卖虽然比组合拍卖需要更少的计算资源，但产生的目标分配也更差——这是 SSI 与组合拍卖之间清晰的取舍：SSI 快但分配质量次优，组合拍卖质量高但计算昂贵。

中间道路：固定大小的捆绑拍卖。 Koenig 等人 2007 年拍卖固定大小的捆绑，使 SSI 更接近组合拍卖。即不允许任意子集，只允许大小不超过 $k$ 的捆绑——在 SSI 的速度和组合拍卖的质量之间取一个可调的折中。这正是通往 CBBA 的桥——CBBA 就是一种分布式的、基于捆绑的拍卖。

8.5 CBBA：把 Multi_03 安放进分类学¶

现在回到 §6.5 埋下的承诺：给 Multi_03 的 CBBA 一个精确坐标。

回顾 Multi_03 的 CBBA。 多机协作章节里讲过，CBBA (Consensus-Based Bundle Algorithm, Choi et al. 2009, IEEE T-RO 25(4):912-926) 是分布式任务分配的代表。它分两个交替阶段：

捆绑构建 (bundle construction)：每个机器人本地地、贪心地往自己的任务捆绑里加任务（按边际收益排序），构建一个它想要的任务序列——这一步本质就是 §8.3 的 SSI 边际出价思想，但在本地进行。
冲突消解 (conflict resolution via consensus)：机器人之间通过共识 (consensus) 交换各自的"中标价"信息，发现冲突（两台都想要同一任务）时按一致的规则消解（出价高者保留），直到全局无冲突。

本质洞察：CBBA 的名字精确地拆解了它的两半——"Bundle"（捆绑）来自 §8.4 的捆绑拍卖思想（每个机器人要一串任务而非单个），"Consensus"（共识）来自 Multi_02 的分布式共识机制（用局部通信达成全局一致，不需要中心拍卖商）。CBBA = 捆绑拍卖的"出价" + 分布式共识的"定标"。它把 §7/§8 的集中式拍卖里那个"中心拍卖商"去掉了，换成机器人之间的共识——这才让它真正分布式、可扩展、抗通信拓扑变化。Multi_03 给了你 CBBA 的算法流程，本章给了你它在整张方法地图上的来历：它站在"捆绑拍卖 × 分布式共识"的交汇点。

CBBA 在分类学里的精确坐标（兑现 §6.5）：

维度	CBBA 的取值	为什么
Gerkey-Matarić 格子	ST-SR-TA	单任务机器人、单机器人任务、要排未来任务序列（捆绑就是序列）
iTax 依赖级别	ID（捆绑内顺路）	边际出价捕捉同一机器人捆绑内的顺路依赖；不处理 XD（跨机器人避让）和 CD
集中/分布	分布式	共识替代中心拍卖商
解质量保证	收敛到无冲突解，有最坏性能界	Choi 2009 证明了在合理出价规则下收敛性与次优界

这也划清了 CBBA 的能力边界：它解决不了 MR（需要多机协作的单个任务）、解决不了 CD（任务本身可多种分解），更解决不了任务代价依赖其他机器人路线的 XD 强耦合（它只在冲突消解层面间接处理）。那些更难的情形，要靠 §7 的 MILP（小规模集中）或 §9 的联合方法。

8.6 代码：序贯单物品拍卖 (SSI) 实现¶

下面实现 SSI，让"边际出价 + 序贯定标"从描述变成可运行代码。场景：多台机器人给多个任务点送货，每台机器人维护一条路线，出价 = 把任务插入路线的边际行驶代价。

Step 1：为什么这样组织代码。

SSI 的核心是"边际代价出价"。机器人 r 对任务 t 的出价 =
  把 t 插入 r 当前路线后的最短路线长 - r 当前路线长。
所以每台机器人要维护:
  - 自己的位置 + 已分配任务的路线
  - 一个"插入边际代价"函数(给定新任务, 算最便宜的插入位置代价)

序贯定标: 每轮在所有(机器人,未分配任务)出价里挑全局最小, 分配, 更新, 重复。
注意: 出价要在"已有路线"基础上算 —— 这是 SSI 不同于朴素贪心的关键。

Step 2：正确写法。

import numpy as np
from itertools import permutations

def route_length(start, points):
    """给定起点和一组必访点, 返回最短访问路线长度(小规模用全排列精确解)。"""
    if not points:
        return 0.0
    best = float("inf")
    for perm in permutations(points):
        d = np.linalg.norm(np.array(perm[0]) - np.array(start))
        for a, b in zip(perm[:-1], perm[1:]):
            d += np.linalg.norm(np.array(a) - np.array(b))
        best = min(best, d)
    return best

def marginal_cost(robot_pos, current_tasks, new_task):
    """边际代价 = 加入 new_task 后的最短路线 - 当前最短路线。"""
    before = route_length(robot_pos, current_tasks)
    after  = route_length(robot_pos, current_tasks + [new_task])
    return after - before

def ssi_auction(robot_positions, task_positions):
    """序贯单物品拍卖。返回 {机器人索引: [分配到的任务索引...]}。"""
    n_robots = len(robot_positions)
    assignment = {i: [] for i in range(n_robots)}
    unassigned = set(range(len(task_positions)))

    while unassigned:
        best_bid = float("inf")
        best_r, best_t = None, None
        # 出价阶段: 每个机器人对每个未分配任务算边际代价
        for r in range(n_robots):
            current = [task_positions[t] for t in assignment[r]]
            for t in unassigned:
                bid = marginal_cost(robot_positions[r], current, task_positions[t])
                if bid < best_bid:        # 定标: 全局最小边际代价
                    best_bid, best_r, best_t = bid, r, t
        # 分配
        assignment[best_r].append(best_t)
        unassigned.remove(best_t)
        print(f"  分配任务 {best_t} -> 机器人 R{best_r} (边际代价 {best_bid:.2f})")
    return assignment

# ---- 仓库送货: 3 台机器人, 6 个任务点 ----
robots = [(0, 0), (10, 0), (5, 10)]
tasks  = [(1, 1), (2, 0), (9, 1), (8, 2), (5, 8), (6, 9)]
result = ssi_auction(robots, tasks)
for r, ts in result.items():
    rl = route_length(robots[r], [tasks[t] for t in ts])
    print(f"R{r} 任务 {ts}, 路线长 {rl:.2f}")
# 观察: 任务会按"顺路"聚到就近的机器人 —— 边际出价自动实现

Step 3：错误写法并解释为什么错。

# ❌ 错误 1: 出价用"机器人到任务的直线距离", 而非边际代价
def bid_wrong(robot_pos, current_tasks, new_task):
    return np.linalg.norm(np.array(robot_pos) - np.array(new_task))  # 只看起点到任务
# 问题: 忽略了机器人已分配的任务。一台已经要去远处的机器人, 顺路再拿一个几乎免费,
#      但这个出价会因为"起点离得远"而虚高, 导致任务被分给次优的机器人。
#      丢失了 ID(顺路)依赖 —— 这正是 SSI 边际出价的价值所在。

# ❌ 错误 2: 一轮把所有任务都按当前出价分配掉(并行而非序贯)
#   for t in tasks: assign t to argmin_r bid(r, t)   # 同时定标所有任务
# 问题: 多个任务可能都判给同一台机器人(它对每个都恰好最低), 而出价是基于
#      "空路线"算的, 没考虑"分了第一个任务后第二个任务的边际代价已变"。
#      SSI 必须序贯 —— 每分配一个就更新路线, 再算下一轮。

# ❌ 错误 3: 边际代价直接用"插到路线末尾", 不找最优插入位置
#   after = route_length_append_at_end(...)
# 问题: 把新任务硬接在路线末尾通常不是最便宜的。正确做法是尝试所有插入位置
#      (这里用全排列精确解; 大规模用便宜的"最便宜插入"启发式)取最小。

Step 4：SSI vs 集中式最优的对比。

# === SSI(分布式贪心) vs MILP/匈牙利(集中式最优) 的取舍 ===
# | 维度       | SSI 拍卖              | 集中式 MILP/匈牙利      |
# | 通信       | 分布式, 局部出价      | 需中心汇总全部代价      |
# | 规模       | 大规模可行            | 中小规模(NP-hard 墙)    |
# | 最优性     | 次优(贪心), 有界      | 最优                    |
# | 鲁棒性     | 中心失效不全瘫        | 中心失效则瘫            |
# | 顺路(ID)   | 边际出价自动捕捉      | 需在目标函数显式建模    |
#
# 选择: 规模大/要分布式/中心不可靠 -> SSI(或 CBBA); 规模中小/要最优 -> §7。
# 注意 SSI 是"序贯单物品", CBBA 是"分布式捆绑+共识", 后者是 SSI 思想的分布式升级。

⚠️ 常见陷阱¶

陷阱 8-1（概念误区）：拍卖出价用绝对代价而非边际代价。 - 错误描述：机器人对任务的出价用"自己到任务的距离"，不考虑已分配的任务（见 §8.6 Step 3 错误 1）。 - 现象/后果：丢失顺路（ID）依赖，任务分配得不偿失——本可顺路低价完成的任务被分给别人。 - 根本原因：绝对代价不反映"在已有承诺基础上再做这个任务的真实增量"。市场机制的效率来自边际定价。 - 正确做法：出价 = 把任务加入当前路线/计划的边际代价（增量），这样顺路自动得到奖励。

陷阱 8-2（思维陷阱）：把序贯拍卖做成并行一次性分配。 - 错误描述：一轮内对所有任务同时定标，不逐个更新（见 §8.6 Step 3 错误 2）。 - 现象/后果：多个任务挤给同一机器人，因为出价都基于未更新的初始路线。 - 根本原因：SSI 的正确性依赖"分配一个就更新路线、边际代价随之变化"。并行定标用的是过时的边际代价。 - 正确做法：严格序贯——每轮只定一个（最小边际或最大 regret），更新该机器人路线，再开下一轮。

陷阱 8-3（概念误区）：以为 CBBA 能解决所有多机分配。 - 错误描述：把 CBBA 当成多机任务分配的万能解。 - 现象/后果：在 MR（协作任务）、CD（任务可多种分解）、强 XD（跨机器人路线耦合）问题上用 CBBA，结果不可行或质量差。 - 根本原因：CBBA 精确地坐在 ST-SR-TA + ID 那一格（§8.5），它的捆绑+共识机制不覆盖协作、分解、强耦合。 - 正确做法：先用 §6 分类学定位问题。CBBA 适用 ST-SR-TA + ID；MR 要联盟形成，CD/强 XD 要 §9 联合方法或集中 MILP。

练习¶

（⭐⭐，实现） 给 §8.6 的 SSI 加入 regret clearing 定标规则：每轮不选边际代价最小的任务，而选"两个最小出价差距最大"的任务分配。对比两种定标规则在同一场景下的总路线代价。
（⭐⭐，分析） 构造一个场景，让 SSI 的边际出价明显优于"绝对距离出价"（陷阱 8-1）：放一台机器人远离所有任务但任务彼此聚集，说明边际出价如何让它顺路低价拿下整簇任务。
（⭐⭐⭐，设计扩展） SSI 的 route_length 用全排列精确解，$O(k!)$ 在任务多时爆炸。把它换成"最便宜插入"启发式（新任务只尝试插入现有路线的各个位置，不重排），分析复杂度从 $O(k!)$ 降到多少，以及质量损失。
（⭐⭐⭐⭐，跨节综合） 结合 §8.5 和 Multi_02（共识）：CBBA 用共识替代中心拍卖商。简述如果通信拓扑是动态变化的（机器人时连时断），CBBA 的共识阶段为什么仍能收敛到无冲突分配（提示：Choi 2009 的收敛性依赖什么假设）。

9. 规划与分配的耦合 ⭐⭐⭐⭐¶

9.1 衔接：两条伏笔在这里收束¶

本章开头埋了两条伏笔，现在收束。

伏笔一（§0 Q4 与 §2.4）：TAMP_T1 §2.4 演示过一个反面教材——"先做完整任务规划、再逐步检查运动可行性"会陷入指数级回溯，根源是两层解耦、信息单向流动。当时就预告：把"任务 vs 运动"换成"分配 vs 规划"，同样的陷阱会重现。

伏笔二（§7.5 练习 4 与 §6.4）：§7 的 MILP 假设代价 $c_{ij}$ 是已知常数，但 §6.4 的 ID/XD 依赖告诉我们，真实代价往往取决于机器人的路线安排——而路线又取决于它被分了哪些任务。§7.5 练习 4 就点破了这个矛盾。

这一节把两条伏笔合在一起回答一个根本问题：为什么不能"先分配、再让每台机器人各自规划"？为什么分配和规划必须一起想？ 这是本章难度最高（⭐⭐⭐⭐）、也是最能体现"任务层是一个整体"的一节。

9.2 解耦的诱惑与陷阱¶

最自然的工程直觉是两步解耦：

朴素两步法:
  第1步: 任务分配 —— 把任务分给机器人(假设每个任务有个固定代价)
  第2步: 单体规划 —— 每台机器人对自己的任务清单各自排序、规划路线

这很有吸引力：第 1 步用 §7 的匈牙利/MILP 或 §8 的拍卖，第 2 步每台机器人独立跑一个单体 TSP/规划。两步都是有成熟解法的子问题。问题出在第 1 步的那个假设——"每个任务有个固定代价"——是错的。

考虑仓库：把包裹 $p_1$ 分给机器人 $R_1$ 的"代价"是多少？它取决于 $R_1$ 还被分了哪些别的包裹：

如果 $R_1$ 只送 $p_1$，代价 = 往返 $p_1$ 的距离。
如果 $R_1$ 还要送顺路的 $p_4$，那 $p_1$ 的"边际代价"很小（顺路）。
如果 $R_1$ 被分了一堆分散各处的包裹，$p_1$ 可能要绕很大的路，边际代价很高。

也就是说，$p_1$ 的代价不是一个常数，而是依赖于整个分配方案 + 规划出的路线。这正是 §6.4 的 ID 依赖。两步法在第 1 步必须"猜"一个代价（通常用直线距离），但这个猜测在第 2 步规划出真实路线后往往被推翻——于是要么接受次优分配，要么回到第 1 步重分，陷入和 TAMP_T1 §2.4 同构的回溯。

本质洞察：分配-规划的耦合，与 TAMP 的任务-运动耦合，是同一个结构性难题的两个实例。两者都是"上层决策依赖下层结果、下层结果又由上层决策决定"的鸡生蛋循环。TAMP 里是"任务序列的可行性依赖运动规划、运动规划的起止又由任务序列定"；这里是"分配的代价依赖规划出的路线、路线又由分配的任务清单定"。认出这个同构，你就明白为什么整条 TAMP 线反复强调'不能解耦'——它不是某个具体算法的毛病，而是分层决策的内在张力。解耦带来模块化的工程便利，但当层间存在强依赖时，解耦就以最优性（甚至可行性）为代价。

9.3 耦合问题的真面目：联合分配 + 排序 + 路由¶

把"分配"和"规划"合起来看，多机器人任务分配的完整问题其实是一个经典的运筹学难题。多机器人任务分配 (MRTA) 常被表达为多旅行商问题 (mTSP)，已知是 NP-hard。更精确地说，当每台机器人有容量限制（一次只能装这么多）时，这个任务分配问题是带容量约束的车辆路径问题 (Capacity-constrained Vehicle Routing Problem, CVRP) 的一个实例，已知是 NP-hard。

这揭示了耦合问题的真面目——它同时包含三层决策，缠在一起：

决策层	决定什么	对应经典问题
分配 (assignment)	哪些任务归哪台机器人	集合划分
排序 (sequencing)	每台机器人按什么顺序做自己的任务	单体 TSP
路由 (routing)	任务之间走什么路径（含避障）	运动规划

两步法的错误，本质是把这三层强行切开：先定分配、再定排序+路由。但三者是耦合的——分配的好坏取决于排序后的真实路线长度，而最优排序又取决于分到了哪些任务。把任务分配、调度、路由决策显式协调，相比分别做选择和路由的分离方法，能带来可观的优化收益（某仓库研究中集成方法比传统分解方法提升约 30%）——这个数字量化了"解耦的代价"：分开做会丢掉约 30% 的优化空间。

9.4 三种应对策略¶

面对这个耦合的 NP-hard 问题，工程上有三档应对，从"假装没耦合"到"正面联合求解"：

策略一：解耦 + 迭代修正（最简单，可接受次优）。

先解耦两步法跑一遍，再用规划出的真实代价回去修正分配，迭代几轮。这类似 TAMP_T1 §2.4 的"加约束重规划"，但用在分配-规划之间。

解耦+迭代:
  1. 用直线距离做初始分配(§7/§8)
  2. 每台机器人规划真实路线, 得到真实代价
  3. 若真实代价与假设差距大, 用真实代价重新分配, 回到 2
  4. 收敛或达到轮数上限则停

优点：复用现成的分配和规划模块；缺点：不保证收敛到最优，可能在两步间振荡。

策略二：把规划嵌进分配的代价计算（中等，处理 ID 依赖）。

不再用直线距离当代价，而是在分配的出价/代价计算里直接调用规划器，算出真实的边际路线代价。§8 的 SSI 边际出价已经是这个思想的雏形（出价=插入路线的边际代价）。更进一步，可以把真实的避障路径规划嵌进去：把路径规划器集成进拍卖阶段的奖励计算，考虑实际的避障行驶距离而非理想直线距离，从而解决任务分配与路径规划之间的耦合。

本质洞察：策略二的精髓是让分配层"看得见"规划层的真实代价——这正是 §2.2 强调的"层间信息流动"。它没有消除分层（分配和规划仍是两个模块），但把规划的结果（真实路线代价）反馈进了分配的决策。这与 PDDLStream 让符号层"看得见"几何采样器的可行性是同一种思想（§3 的板块③）：不强行联立，而是建立有效的信息通道。代价是每次出价都要调用一次规划器，计算量大增——所以常配合"惰性 (lazy)"策略，只在必要时才精算路径。

策略三：联合优化（最彻底，规模受限）。

把分配、排序、路由写进一个优化问题（如一个大的 MILP 或约束规划 CP），让求解器同时决定三层。同时分配机器到操作、运输机器人到物料转移，这两个 NP-hard 组件的组合产生复杂的解空间——这是最彻底但也最贵的做法，只适合中小规模。大规模时退回滚动时域 (rolling horizon) 或启发式。

三种策略的取舍：

策略	耦合处理	最优性	计算	适用
一：解耦+迭代	弱（事后修正）	次优、可能振荡	低	快速原型、弱耦合
二：规划嵌入代价	中（ID 顺路）	较好	中（反复调规划器）	主流工程选择
三：联合优化	强（一体求解）	最优（小规模）	高（NP-hard）	中小规模、要最优

9.5 接口：分配层如何接到 TAMP¶

最后把本章（决策层）接回 TAMP_T1（任务-运动集成）。完整的多机器人系统是一个三层嵌套：

多机器人系统的三层嵌套(收尾本章, 接续 TAMP_T1):
┌────────────────────────────────────────────────────────┐
│ 任务分配层 (本章 §6-§8)                                  │
│   把任务分给 R1/R2/R3, 出价/代价需下层规划信息(§9.4策略二)│
└──────────────────────────┬─────────────────────────────┘
                          │ 每台机器人拿到任务清单
                          ▼
┌────────────────────────────────────────────────────────┐
│ 单体任务规划层 (本章 §3-§5)                              │
│   每台机器人把清单排成有序动作(HTN/时序), 验证逻辑可行    │
└──────────────────────────┬─────────────────────────────┘
                          │ 每个动作需几何可行的轨迹
                          ▼
┌────────────────────────────────────────────────────────┐
│ 任务-运动集成层 (TAMP_T1)                                │
│   为每个动作求几何参数与无碰撞轨迹(PDDLStream/LGP)        │
│   够不到→反馈回上层重排; 这是 TAMP_T1 的核心耦合          │
└────────────────────────────────────────────────────────┘
        失败反馈逐层上传: 运动不可行→重规划→重分配

这张图把本章和 TAMP_T1 拼成了完整的任务层。每一层都依赖下一层的可行性/代价信息，每一层的失败都要能反馈回上层——这就是 §2.2 那句"三层之间是双向耦合的"的最终兑现。一个工业级多机器人系统，本质上就是把这三层耦合处理好的系统。

本质洞察：读到这里，回看 §2.3 那个"项目负责人"的类比——分工（分配）的好坏取决于每个人能把活安排得多高效（规划），而每个人怎么安排又取决于被分到了哪些活。本章用九节走完了这个循环的完整论证：从 §2 提出三层栈、§3-§5 讲透"单体怎么规划"、§6-§8 讲透"多体怎么分配"，到 §9 证明二者必须耦合。任务层不是"规划"和"分配"两个独立工具的拼装，而是一个你中有我、必须协同求解的整体——这正是本章把它们合写、而非拆成两章的根本理由。

⚠️ 常见陷阱¶

陷阱 9-1（思维陷阱）：默认"先分配后规划"两步解耦总是对的。 - 错误描述：把多机任务分配当成"先分好、各自规划"的流水线，用直线距离做分配代价。 - 现象/后果：分配方案在规划出真实路线后被推翻，实际总代价远超预期，或陷入分配-规划振荡。 - 根本原因：任务代价不是常数，依赖分配方案和规划出的路线（ID/XD 依赖）。解耦的前提（代价独立）不成立。 - 正确做法：识别耦合强度。弱耦合可用策略一（迭代修正）；ID 顺路依赖用策略二（规划嵌入代价）；要最优且规模小用策略三（联合优化）。

陷阱 9-2（概念误区）：以为把代价从直线距离换成真实路径就"解决"了耦合。 - 错误描述：策略二里把规划器嵌进代价计算，就认为耦合彻底消除了。 - 现象/后果：忽略了 XD（跨机器人）耦合——一台机器人的真实路线还取决于其他机器人走哪条路（会不会堵），单纯算自己的避障路径仍不够。 - 根本原因：策略二处理了 ID（自己的顺路），但 XD（多机互相影响）需要机器人间协调，单体规划器算不出来。 - 正确做法：ID 用策略二足矣；XD 要么走联合优化（策略三），要么在执行层用多机路径协调（MAPF，见 Multi_03）化解冲突。

陷阱 9-3（思维陷阱）：把分配-规划耦合和 TAMP 任务-运动耦合当成两个无关的问题。 - 错误描述：分别学这两个耦合，没看出它们是同构的。 - 现象/后果：在一个上重复踩另一个已经讲过的坑，无法迁移经验。 - 根本原因：没抓住"上层决策依赖下层结果、下层又由上层决定"这个共同结构。 - 正确做法：把两者作为"分层决策的内在张力"的同一类问题理解（§9.2 本质洞察），解法思想也相通（建立层间信息通道 / 联立求解 / 迭代修正）。

练习¶

（⭐⭐，分析） 构造一个 2 机器人 4 任务的具体场景，使"直线距离分配 + 各自规划"的结果明显劣于联合最优。给出两种方案的总代价，量化解耦的损失。
（⭐⭐⭐，实现） 实现策略一（解耦+迭代）：先用 §7 匈牙利按直线距离分配，再用 §8 的 route_length 算真实路线代价，用真实代价更新代价矩阵重新分配，迭代到分配不再变化。观察它是否收敛、是否振荡。
（⭐⭐⭐，建模） 把 §7.5 的 MILP 扩展为"分配 + 排序"联合模型（mTSP 式）：引入变量 $x_{ijk}$ 表示机器人 $k$ 是否从任务 $i$ 直接去任务 $j$，加子环消除约束。讨论变量数如何随任务数增长、为什么这限制了它只能用于小规模。
（⭐⭐⭐⭐，综合） 结合 §9.5 和 TAMP_T1：画出一个"3 机器人收拾仓库"的完整失败反馈链——运动层报告"$R_1$ 够不到高架子上的物体"，这个失败应该如何逐层上传（运动→规划→分配），每一层分别做什么调整？给出每层的具体响应。

10. 工程实践：把规划与分配跑起来 ⭐⭐⭐¶

10.1 从教学代码到工程工具链¶

前面各节的代码都是为讲清原理而写的最小实现。真实工程里，你不会手写规划器和 MILP 求解器，而是用成熟工具。本节梳理任务规划与分配的工具链，并讲清各自的适用边界——这是从"理解原理"到"搭出系统"的关键一跳。

层次	教学实现（前文）	工程工具	何时用工程工具
符号规划	§3.6 手写松弛启发式	Fast Downward、pyperplan、ENHSP	任务规划稍复杂就该用，自己写启发式不现实
HTN	§4.5 手写递归分解	GTPyhop、SHOP3、PANDA	配方多、要偏序时
时序规划	§5.4 手写 STN	OPTIC、TFD、ENHSP	有 durative action、数值流
线性指派	§7.3 `linear_sum_assignment`	scipy（已是工程级）	直接用，无需自己实现匈牙利
MILP 分配	§7.5 PuLP	OR-Tools、Gurobi、CPLEX	规模大、要商用性能
拍卖	§8.6 手写 SSI	通常自研（按场景定制）	分布式、特定通信约束

本质洞察：工具链的选择本身就是一次 §6 式的"先定问题再选工具"。教学代码的价值是让你看懂工具内部在做什么——当 Fast Downward 跑不出解、当 Gurobi 报告 infeasible、当 SSI 不收敛时，只有理解了删除松弛、LP 松弛、边际出价的原理，你才知道是建模错了、规模超了、还是出价规则有问题。会用工具的人很多，能在工具失效时诊断原因的人，才是真正掌握了这一层。 这也是本章前面坚持手写最小实现的理由。

10.2 经典任务规划：Fast Downward 与 pyperplan¶

工程中最常用的经典规划器是 Fast Downward（基于 PDDL，含 LAMA 等强启发式配置，是国际规划竞赛的常胜框架）和轻量的 pyperplan（纯 Python，适合教学和小问题，TAMP_T1 §3.5 已用过）。

典型工作流（与 TAMP_T1 §3.5 衔接，那里用 pyperplan 跑过 pick-place）：

# 工程中调用 Fast Downward 的典型方式 (命令行)
# fast-downward.py domain.pddl problem.pddl --search "astar(lmcut())"
#                                                          ^^^^^^^
#   lmcut() = §3.7 讲的 LM-cut 可容许启发式, 配 A* 求最优
#   求快可换 "lazy_greedy([ff()])" —— §3.5 的 h^FF 配贪心

# pyperplan 的 Python API (轻量, 适合嵌入)
from pyperplan.planner import _parse, _ground, SEARCHES, HEURISTICS
problem = _parse("domain.pddl", "problem.pddl")
task = _ground(problem)
heuristic = HEURISTICS["hff"](task)        # h^FF 启发式(§3.5)
solution = SEARCHES["astar"](task, heuristic)

注意这里的 hff、lmcut 正是 §3 讲的启发式——工程工具把它们做成了开箱即用的选项，但选哪个、为什么，靠的是 §3 的理解。

10.3 分配求解：OR-Tools 的两副面孔¶

工程中分配问题的主力是 Google OR-Tools，它同时提供线性指派的快速专解和通用 MILP/CP 求解器——正好对应本章 §7 的两副面孔。

Step 1：为什么 OR-Tools 适合工程分配。

OR-Tools 同时覆盖本章两条分配主线:
  - LinearSumAssignment: 线性指派专解(ST-SR-IA), 比 scipy 更快, 工程级
  - CP-SAT / MIP 求解器: 通用约束/整数规划(带容量、协作等约束)
这避免了"小问题用 scipy、大问题换 Gurobi"的工具割裂 —— 一个库通吃。
工程上 CP-SAT 求解器在很多组合分配问题上甚至优于传统 MILP。

Step 2：正确写法（线性指派，对应 §7.3）。

from ortools.graph.python import linear_sum_assignment

# 仓库 ST-SR-IA: 3 机器人 × 3 任务, 代价矩阵
assignment = linear_sum_assignment.SimpleLinearSumAssignment()
costs = [[4, 2, 8], [4, 3, 7], [3, 1, 6]]
for r in range(len(costs)):
    for t in range(len(costs[r])):
        assignment.add_arc_with_cost(r, t, costs[r][t])

status = assignment.solve()
if status == assignment.OPTIMAL:
    print(f"总代价: {assignment.optimal_cost()}")
    for r in range(assignment.num_nodes()):
        t = assignment.right_mate(r)
        print(f"  R{r} -> 任务 {t} (代价 {assignment.assignment_cost(r)})")

Step 3：错误写法并解释为什么错。

# ❌ 错误 1: 用 LinearSumAssignment 解带容量约束的问题
#   LinearSumAssignment 只做一对一指派(ST-SR-IA), 无法表达"一台机器人多任务+容量"
# 问题: 带容量是 GAP/CVRP(§7.4), 必须用 CP-SAT/MIP, 不是线性指派。
#      用错求解器要么报错要么默默给出无意义结果。

# ❌ 错误 2: 不检查 solve() 的返回状态, 直接读结果
#   assignment.solve(); cost = assignment.optimal_cost()  # 没检查 status
# 问题: 若问题不可行(如任务数≠机器人数且未补齐), 状态不是 OPTIMAL,
#      此时读 optimal_cost() 是未定义行为。必须先判 status == OPTIMAL。

# ❌ 错误 3: 把浮点代价直接喂给整数求解器
#   add_arc_with_cost(r, t, 3.7)  # OR-Tools 整数图算法期望整数代价
# 问题: 线性指派的整数实现要求整数代价。浮点要先缩放取整(如 ×1000 转整数),
#      否则精度丢失或报错。

Step 4：何时从线性指派升级到 CP-SAT。

# === OR-Tools 分配求解器选择 ===
# | 问题类型                  | OR-Tools 求解器        | 对应本章          |
# | ST-SR-IA 一对一指派        | LinearSumAssignment    | §7.2-7.3 匈牙利    |
# | 带容量/预算/协作约束       | CP-SAT (CpModel)       | §7.4-7.5 MILP     |
# | 分配+排序+路由联合(VRP)    | Routing 库 (专门)      | §9.3 耦合问题      |
#
# 判断: 纯一对一 -> LinearSumAssignment; 有约束 -> CP-SAT;
#       含路由耦合 -> OR-Tools Routing 库(内置 VRP/TSP 求解器)。
# OR-Tools Routing 库正是 §9 耦合问题的工程答案 —— 它把分配+排序+路由一体求解。

10.4 集成进 ROS 2 的架构建议¶

把任务规划与分配接入真实机器人系统（ROS 2）时，一个清晰的架构是把三层做成独立节点，用明确的接口连接：

ROS 2 任务层架构(建议):
┌─────────────────┐   任务清单    ┌─────────────────┐  动作序列  ┌──────────────┐
│ 分配节点         │ ───(action)──>│ 规划节点         │──(action)─>│ 执行(Nav2/   │
│ allocator        │               │ task_planner     │            │ MoveIt2 BT)  │
│ (OR-Tools/拍卖)  │ <──代价查询────│ (Fast Downward)  │ <─失败反馈──│              │
└─────────────────┘   (service)   └─────────────────┘            └──────────────┘
       ▲                                                                  │
       └──────────────── 失败上传(重分配) ────────────────────────────────┘

关键设计点：

用 action 而非 service 连接：规划和分配都是耗时操作，action 支持进度反馈与取消（service 是阻塞的）。
代价查询接口：分配节点要算真实代价（§9.4 策略二），需向规划节点查询"这台机器人做这个任务的真实路线代价"——这是 §9 耦合在架构上的落地。
失败反馈通道：执行失败→规划重排→分配重分，逐层上传（§9.5 的反馈链），架构上必须预留。

本质洞察：这个架构图把本章和后续 T5（行为树执行）连了起来——最右边的"执行"节点正是 T5 要详讲的 Nav2/MoveIt2 行为树。本章产出"做什么、谁来做"，T5 负责"稳健地做下去"。整条任务层的工程落地，就是把分配、规划、执行三类节点用 action/service/反馈通道正确连接。理解了接口，你就理解了为什么任务层不是一个算法、而是一个需要架构设计的子系统。

⚠️ 常见陷阱¶

陷阱 10-1（编程陷阱）：分配求解器不检查返回状态。 - 错误描述：调用求解器后直接读结果，不判 OPTIMAL/INFEASIBLE（见 §10.3 Step 3 错误 2）。 - 现象/后果：问题不可行时读到未定义的"解"，系统据此行动导致错误。 - 根本原因：求解器在不可行/超时时不返回有效解，状态码是唯一可靠的成败信号。 - 正确做法：永远先检查 status，区分 OPTIMAL/FEASIBLE/INFEASIBLE/超时，分别处理。

陷阱 10-2（思维陷阱）：用错求解器层次（线性指派 vs CP-SAT vs Routing）。 - 错误描述：拿线性指派解带约束问题，或拿通用 MILP 硬解大规模路由。 - 现象/后果：前者建模失真或报错，后者跑不动。 - 根本原因：每个求解器对应特定问题类（§10.3 Step 4 表），用错层次必然低效或无解。 - 正确做法：纯指派→LinearSumAssignment；带约束→CP-SAT；含路由耦合→Routing 库。先用 §6 分类定位，再选求解器层次。

陷阱 10-3（概念误区）：把规划和分配做成阻塞式 service，不留反馈通道。 - 错误描述：ROS 2 里用阻塞 service 串联三层，失败时无反馈、无法取消。 - 现象/后果：耗时规划阻塞整个系统，执行失败无法触发重规划/重分配，系统卡死。 - 根本原因：忽略了任务层的耗时性与失败反馈需求（§9.5）。 - 正确做法：用 action（支持进度/取消）连接，显式设计失败上传通道（执行→规划→分配）。

练习¶

（⭐⭐，实现） 用 OR-Tools 的 LinearSumAssignment 重做 §7.3 的仓库指派，对比它与 scipy linear_sum_assignment 的结果是否一致、接口有何不同。
（⭐⭐⭐，建模） 用 OR-Tools 的 CP-SAT（CpModel）重新实现 §7.5 的带容量分配 MILP，体会 CP 建模与 MILP 建模在表达约束上的异同。
（⭐⭐⭐，设计） 为 §10.4 的 ROS 2 架构设计"代价查询" service 的消息接口：分配节点发什么（机器人 ID + 任务 ID + 已有清单），规划节点回什么（真实路线代价 + 是否可行）。这是 §9.4 策略二的架构接口。

11. 累积项目：给 Mini-TAMP 加上多机分配层 ⭐⭐⭐¶

11.1 项目衔接：从单机到多机¶

TAMP_T1 §11 构建了一个单机器人的 Mini-TAMP 系统（PyBullet 仿真 + pyperplan 任务规划 + 简单运动规划 + Plan-then-Check 协调器）。本章的累积项目在它之上加一层——多机器人任务分配层，让系统从"一台机器人执行一个计划"升级为"多台机器人分工协作"。

这正好把本章学的东西串起来：用 §7 的匈牙利做分配、用 §8 的边际出价处理顺路、用 §9 的反馈链处理"某台机器人完不成就重分配"。

11.2 项目结构¶

Mini-TAMP 多机版(本章新增层 + T1 已有层):
┌──────────────────────────────────────────────┐
│ 【本章新增】多机分配层 MultiRobotAllocator     │
│   输入: 任务集合 + 机器人集合                  │
│   方法: 匈牙利(§7) 或 SSI 边际出价(§8)         │
│   输出: 每台机器人的任务清单                   │
│   失败处理: 某机器人规划失败 → 重分配(§9)      │
└────────────────────┬─────────────────────────┘
                    │ 每台机器人一份清单
                    ▼
┌──────────────────────────────────────────────┐
│ 【T1 已有】单机 Mini-TAMP (每台机器人各跑一个) │
│   TaskPlanner(pyperplan) + MotionPlanner       │
│   + TAMPCoordinator (Plan-then-Check)          │
└──────────────────────────────────────────────┘

11.3 核心代码：多机分配层¶

下面实现新增的分配层，它包裹 T1 的单机 Mini-TAMP。为聚焦本章主题，单机部分用简化接口表示（完整实现见 TAMP_T1 §11）。

import numpy as np
from scipy.optimize import linear_sum_assignment

class MultiRobotAllocator:
    """多机任务分配层 —— 本章累积项目的核心新增组件。
    包裹 T1 的单机 Mini-TAMP, 把任务分给多台机器人。"""

    def __init__(self, robots, single_tamp_factory):
        """
        robots: [(robot_id, init_pose), ...]
        single_tamp_factory: 可调用对象, 给定机器人返回一个 T1 的单机 TAMP 协调器
        """
        self.robots = robots
        self.make_tamp = single_tamp_factory   # 复用 T1 的 TAMPCoordinator

    def compute_cost_matrix(self, tasks):
        """代价矩阵: C[i][j] = 机器人 i 做任务 j 的代价。
        §9 的关键: 这里用真实路线代价(调规划), 而非直线距离。"""
        n_r, n_t = len(self.robots), len(tasks)
        C = np.zeros((n_r, n_t))
        for i, (rid, pose) in enumerate(self.robots):
            for j, task in enumerate(tasks):
                # 简化: 用机器人位姿到任务位置的距离近似
                # 工程版应调用 T1 的 MotionPlanner 算真实无碰撞路线代价(§9.4策略二)
                C[i][j] = np.linalg.norm(np.array(pose[:2]) - np.array(task["pos"][:2]))
        return C

    def allocate(self, tasks):
        """用匈牙利算法做 ST-SR-IA 分配(§7)。返回 {robot_id: [task...]}。"""
        C = self.compute_cost_matrix(tasks)
        n_r, n_t = C.shape
        assignment = {rid: [] for rid, _ in self.robots}

        if n_t <= n_r:
            # 任务不多于机器人: 直接一对一指派(§7.2)
            row, col = linear_sum_assignment(C)
            for r, t in zip(row, col):
                assignment[self.robots[r][0]].append(tasks[t])
        else:
            # 任务多于机器人: 用 SSI 边际出价分配(§8), 一台机器人可多任务
            assignment = self._ssi_allocate(tasks, C)
        return assignment

    def _ssi_allocate(self, tasks, C):
        """序贯单物品拍卖(§8): 边际出价 + 序贯定标。"""
        assignment = {rid: [] for rid, _ in self.robots}
        unassigned = set(range(len(tasks)))
        robot_pos = {rid: np.array(pose[:2]) for rid, pose in self.robots}

        while unassigned:
            best = (float("inf"), None, None)   # (边际代价, robot_id, task_idx)
            for rid, _ in self.robots:
                # 简化的边际代价: 到任务的距离(工程版用真实路线增量)
                for t in unassigned:
                    tp = np.array(tasks[t]["pos"][:2])
                    marginal = np.linalg.norm(robot_pos[rid] - tp)
                    if marginal < best[0]:
                        best = (marginal, rid, t)
            _, rid, t = best
            assignment[rid].append(tasks[t])
            robot_pos[rid] = np.array(tasks[t]["pos"][:2])  # 更新位置(§8序贯关键)
            unassigned.remove(t)
        return assignment

    def solve_with_reallocation(self, tasks, max_rounds=3):
        """完整流程: 分配 → 各机器人规划 → 失败则重分配(§9 反馈链)。"""
        for round_i in range(max_rounds):
            assignment = self.allocate(tasks)
            failed_tasks = []
            results = {}
            for rid, task_list in assignment.items():
                tamp = self.make_tamp(rid)              # T1 的单机协调器
                for task in task_list:
                    plan = tamp.solve(task)             # T1 的 Plan-then-Check
                    if plan is None:                    # 单机规划失败
                        failed_tasks.append(task)       # §9: 收集失败任务
                    else:
                        results.setdefault(rid, []).append((task, plan))
            if not failed_tasks:
                print(f"第 {round_i+1} 轮: 全部成功")
                return results
            print(f"第 {round_i+1} 轮: {len(failed_tasks)} 个任务失败, 重分配")
            tasks = failed_tasks                        # §9: 失败任务进入下一轮重分配
        print("达到最大轮数, 仍有任务未完成")
        return results

11.4 项目里程碑与练习¶

阶段	章节	累积内容
阶段 0	TAMP_T1 §11	单机 Mini-TAMP（仿真+规划+协调器）
阶段 1（本章）	本章 §11	多机分配层（匈牙利/SSI + 重分配反馈）
阶段 2	T3	升级单机协调器为 PDDLStream 式
阶段 3	T5	用行为树替换 Plan-then-Check，加执行监控

项目练习：

（⭐⭐） 运行 MultiRobotAllocator，构造 3 机器人 5 任务的场景，观察 SSI 分配如何把任务按就近聚到机器人。修改任务位置，看分配如何变化。
（⭐⭐⭐） 把 compute_cost_matrix 里的"直线距离近似"替换为调用 T1 的 MotionPlanner 算真实路线代价（§9.4 策略二）。对比真实代价分配与直线距离分配的差异。
（⭐⭐⭐） 实现 solve_with_reallocation 的一个测试：人为让某台机器人"够不到"某个任务（规划返回 None），验证失败任务能被收集并在下一轮重分配给别的机器人（§9.5 反馈链）。
（⭐⭐⭐⭐） 给分配层加入容量约束（每台机器人最多 $k$ 个任务），把 allocate 从匈牙利/SSI 换成 §7.5 的 MILP（用 PuLP 或 OR-Tools）。讨论这如何改变分配结果。

本章常见误解汇总¶

误解	正确理解	对应节
任务分配就是多机路径规划 (MAPF)	MAPF 是"分配已定 + 任务独立"后的路径协调子问题；任务分配是更上游、更一般的问题	§2 陷阱 2-1
决策三层可严格自上而下、互不反馈	三层双向耦合，下层失败必须反馈回上层，否则指数回溯	§2.2, §9
$h^{\text{add}}$ 信息量强，可配 A* 求最优	$h^{\text{add}}$ 高估、不可容许，配 A* 不再保证最优；求最优用 $h^{\max}$/LM-cut	§3 陷阱 3-1
删除松弛"删掉负效果"会丢失正确性	松弛只用于估计代价（导航），不用于求解；真实解仍在完整问题上验证	§3 陷阱 3-3
HTN 只是 STRIPS 的加速版，解集合相同	HTN 表达力严格更强（不可判定），但解被配方约束，解集合不同	§4 陷阱 4-3
durative action 是瞬时动作加时间戳	时长引入"执行期间"，前提/效果在 start/end/over-all 语义不同，并发需 over-all 不变式	§5 陷阱 5-1
TA（时间扩展）就是做多次 IA	TA 需前瞻整个序列，是 NP-hard；朴素重复 IA 短视、质量差	§6 陷阱 6-2
ST-SR-IA 之外的格子也能多项式最优	只有 ST-SR-IA 多项式可解（=线性指派），其余全 NP-hard	§6.3
在 ST-SR-IA 上用贪心和匈牙利差不多	贪心不保证最优，匈牙利 $O(n^3)$ 保证最优，无理由用贪心	§7 陷阱 7-1
MILP 总能在合理时间解出最优	MILP 是 NP-hard，最坏指数；只适合中小规模	§7 陷阱 7-3
拍卖出价用绝对代价即可	必须用边际代价，才能捕捉顺路 (ID) 依赖	§8 陷阱 8-1
CBBA 能解决所有多机分配	CBBA 精确坐在 ST-SR-TA + ID + 分布式那一格，不覆盖 MR/CD/强 XD	§8 陷阱 8-3
先分配后规划两步解耦总是对的	任务代价依赖路线（ID/XD），解耦丢最优性（约 30%），可能振荡	§9 陷阱 9-1
分配-规划耦合与 TAMP 任务-运动耦合无关	两者同构——都是"上层依赖下层结果、下层由上层决定"的循环	§9 陷阱 9-3

本章小结¶

本章打开了任务层"决策"这一半的两根支柱——任务规划（一个执行者怎么独自把目标拆成有序动作）与任务分配（一群执行者怎么分工），并证明二者必须耦合。回顾全章逻辑链：

§2 决策层全景：任务分配 → 任务规划 → 运动规划构成三层决策栈，分配决定"谁做"、规划决定"做什么顺序"、运动决定"怎么动"，三层双向耦合。
§3 经典规划深化：打开 TAMP_T1 当黑盒用的规划引擎，讲清启发式的统一来源——删除松弛推出 $h^{\max}$/$h^{\text{add}}$/$h^{\text{FF}}$，外加地标与抽象两条造启发式的路；三种元策略（松弛/分解/投影）贯穿全书。
§4 HTN：长任务搜索爆炸时，用配方分层分解；HTN 用领域知识换搜索效率，表达力强于 STRIPS 但解被配方约束。
§5 时序与数值规划：给规划加时间、并发、资源；durative action 的三处时间锚点、STN 用负权环检测时序一致性。
§6 MRTA 分类学：Gerkey-Matarić 的 ST/MT×SR/MR×IA/TA 把分配问题归类，只有 ST-SR-IA 多项式可解；Korsah iTax 补上 ND/ID/XD/CD 依赖维度。
§7 优化式分配：ST-SR-IA = 线性指派，匈牙利 $O(n^3)$ 最优；带约束用 MILP 通用建模。
§8 拍卖式分配：分布式、可扩展的第二条主线；序贯单物品拍卖的边际出价捕捉顺路，CBBA = 捆绑拍卖 + 分布式共识，精确坐落 ST-SR-TA + ID。
§9 规划-分配耦合：两步解耦会因"代价非常数"陷入回溯（与 TAMP 任务-运动耦合同构）；完整问题是 mTSP/CVRP（NP-hard），三档应对策略从迭代修正到联合优化。
§10-§11 工程与项目：Fast Downward/OR-Tools 工具链 + ROS 2 架构；在 T1 的 Mini-TAMP 上加多机分配层。

一句话收束本章：任务规划与任务分配不是两个独立工具，而是任务层决策这枚硬币的两面——搜索与优化同源、规划与分配在耦合处合一。

术语速查表¶

术语	一句话定义
状态空间搜索	节点是世界状态、边是动作的规划搜索（现代主流）
规划空间 / 偏序规划 (POP)	节点是未完成的偏序计划，只约束必要的动作先后
删除松弛 (delete relaxation)	删掉动作负效果使问题单调，用于造启发式
$h^{\max}$ / $h^{\text{add}}$	删除松弛下取最贵子目标（可容许）/ 子目标代价相加（信息强不可容许）
$h^{\text{FF}}$	在松弛规划图上抽取一个松弛计划，用其长度作启发式
地标 (landmark)	任何解都绕不开的命题/动作；LM-cut 是其可容许变体
抽象启发式	投影到更小状态空间精确求解，作为下界（PDB、merge-and-shrink）
HTN	分层任务网络，用方法把复合任务分解为原子任务
原子/复合任务、方法	primitive（可执行）/ compound（待分解）/ method（分解配方）
durative action	PDDL 2.1 的有时长动作，前提/效果分 at-start/at-end/over-all
STN	简单时序网络，二元时序约束；一致性 = 距离图无负权环
MRTA	多机器人任务分配
ST/MT, SR/MR, IA/TA	单/多任务机器人、单/多机器人任务、瞬时/时间扩展分配
iTax (ND/ID/XD/CD)	任务依赖分类：无/同机器人内/跨机器人/复杂依赖
线性指派 (LAP)	一对一最小权匹配，匈牙利算法 $O(n^3)$ 最优
MILP	混合整数线性规划，分配的通用声明式建模工具
序贯单物品拍卖 (SSI)	每轮按边际代价出价、序贯定标的分布式分配
边际代价出价	出价 = 把任务加入当前路线/计划的增量代价，自动捕捉顺路
CBBA	基于共识的捆绑算法 = 捆绑拍卖 + 分布式共识
分配-规划耦合	分配代价依赖规划路线、路线依赖分配的鸡生蛋循环
mTSP / CVRP	多旅行商 / 带容量车辆路径问题，分配+排序+路由的完整形态

知识点总表¶

#	知识点	核心要点	对应节	难度
1	三层决策栈	分配→规划→运动，双向耦合	§2	⭐
2	状态空间 vs 规划空间	状态/动作 vs 未完成偏序计划	§3.2	⭐⭐
3	删除松弛	删负效果→单调→可贪心，造启发式之源	§3.3	⭐⭐
4	h^max/h^add/h^FF	取最大/求和/抽松弛计划	§3.4-3.5	⭐⭐
5	地标与抽象启发式	必经子目标 / 降维精确解	§3.7	⭐⭐⭐
6	HTN 分解	复合任务用方法拆为原子任务	§4.2-4.3	⭐⭐⭐
7	HTN vs STRIPS	表达力更强但解受配方约束	§4.4	⭐⭐⭐
8	durative action	三处时间锚点 + over-all 不变式	§5.2	⭐⭐⭐
9	STN 一致性	距离图无负权环，Floyd-Warshall 检测	§5.3	⭐⭐⭐
10	Gerkey-Matarić 分类	ST/MT×SR/MR×IA/TA，仅 ST-SR-IA 多项式	§6.2-6.3	⭐⭐
11	Korsah iTax	ND/ID/XD/CD 依赖维度	§6.4	⭐⭐
12	线性指派与匈牙利	减常数不改最优，O(n³)	§7.2	⭐⭐⭐
13	MILP 分配建模	声明式约束 + 二元变量	§7.4	⭐⭐⭐
14	序贯单物品拍卖	边际出价 + 序贯定标，捕捉顺路	§8.3	⭐⭐⭐
15	CBBA 定位	捆绑拍卖+共识，ST-SR-TA+ID+分布式	§8.5	⭐⭐⭐
16	分配-规划耦合	代价非常数，与 TAMP 耦合同构	§9.2	⭐⭐⭐⭐
17	mTSP/CVRP	分配+排序+路由的完整 NP-hard 形态	§9.3	⭐⭐⭐⭐
18	三档应对策略	迭代修正/规划嵌入代价/联合优化	§9.4	⭐⭐⭐⭐

延伸阅读¶

任务规划（板块①深化，§3-§5）： - Hoffmann & Nebel (2001), "The FF Planning System: Fast Plan Generation Through Heuristic Search," JAIR 14. ⭐⭐⭐ —— $h^{\text{FF}}$ 的原始论文，§3.5 的来源。 - Helmert & Domshlak (2009), "Landmarks, Critical Paths and Abstractions," ICAPS. ⭐⭐⭐⭐ —— LM-cut 启发式，§3.7。 - Nau et al. (2003), "SHOP2: An HTN Planning System," JAIR 20:379-404. ⭐⭐⭐ —— HTN 代表系统，§4.3。 - Fox & Long (2003), "PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains," JAIR 20:61-124. ⭐⭐⭐ —— durative action 的来源，§5.2。 - Dechter, Meiri & Pearl (1991), "Temporal Constraint Networks," Artificial Intelligence 49. ⭐⭐⭐ —— STN 的奠基，§5.3。

任务分配（板块⑥，§6-§8）： - Gerkey & Matarić (2004), "A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems," IJRR 23(9):939-954. ⭐⭐ —— MRTA 分类学奠基，§6.2。 - Korsah, Stentz & Dias (2013), "A Comprehensive Taxonomy for Multi-Robot Task Allocation," IJRR 32(12):1495-1512. ⭐⭐⭐ —— iTax 依赖维度，§6.4。 - Kuhn (1955), "The Hungarian Method for the Assignment Problem," Naval Research Logistics Quarterly 2. ⭐⭐ —— 匈牙利算法原始论文，§7.2。 - Koenig et al. (2006), "The Power of Sequential Single-Item Auctions for Agent Coordination," AAAI. ⭐⭐⭐ —— SSI 拍卖，§8.3。 - Choi, Brunet & How (2009), "Consensus-Based Decentralized Auctions for Robust Task Allocation," IEEE T-RO 25(4):912-926. ⭐⭐⭐ —— CBBA，§8.5（Multi_03 主参考）。

耦合与综述（§9）： - 经典运筹学教材中"车辆路径问题 (VRP)"章节（如 Toth & Vigo, The Vehicle Routing Problem）。⭐⭐⭐ —— §9.3 耦合问题的运筹学背景。

工具链（§10）： - Fast Downward 官方文档（启发式配置与搜索算法）。⭐⭐ —— §10.2。 - Google OR-Tools 文档（Assignment、CP-SAT、Routing 三个模块）。⭐⭐ —— §10.3。

本章与后续章节的关系¶

后续章节	本章哪部分为它铺垫	它如何深化本章
T3 PDDLStream	§9 的"规划嵌入代价"（策略二，让符号层看见几何可行性）	详解流式集成如何系统地缝合符号搜索与几何采样
T4 LGP	§9 的"联合优化"（策略三）与 §3.3 优化式目标表达	详解把任务选择与轨迹优化联立成混合优化
T5 行为树	§10.4 架构图最右"执行"节点、§2.2 失败反馈	精读 Nav2 行为树，讲清执行层如何监控、恢复、触发重规划
T6 不确定性 TAMP	§6 分类学（任务代价不确定时分配如何变）	信念空间下的规划与分配
T8 多机 TAMP	§9 整章（分配-规划耦合）、§11 多机项目	把分配-规划-运动的多机联合做深，接 Multi 线协同控制

🔧 故障排查手册¶

症状	可能原因	排查步骤	相关节
规划器跑很久不出解（任务长）	平铺状态空间搜索爆炸，未用层次结构	1. 确认启发式是否生效（打印 $h$ 值）2. 任务是否有标准流程→改用 HTN 3. 检查是否目标不可达	§3, §4
A* 返回的解不是最优	用了不可容许启发式（如 $h^{\text{add}}$）	1. 确认启发式类型 2. 求最优换 $h^{\max}$/LM-cut 3. 确认配的是 A* 而非贪心	§3.4 陷阱 3-1
删除松弛代价算成 ∞ 或偏大	单遍扫描未到不动点	1. 检查是否 `while changed` 循环 2. 确认每次降代价都标记 changed 3. 检查是否漏删 delete 列表	§3.6 陷阱 3-2
HTN 明明有解却返回失败	方法没覆盖该情况，或漏 base case	1. 检查复合任务是否有适用方法 2. 递归任务是否有终止方法 3. operator 是否就地改了状态	§4.5 陷阱 4-1/4-2
并发计划执行时冲突	缺 over-all 不变式	1. 检查 durative action 的保护条件 2. 用 over-all 声明执行期不变式 3. 检查时间区间是否真不冲突	§5.2 陷阱 5-1
STN 一致性检测漏报矛盾	双边约束只加单边，或用了 Dijkstra	1. 确认每条 a≤Δ≤b 加两条边 2. 用 Floyd-Warshall/Bellman-Ford（非 Dijkstra）3. 检查所有 d[i][i]	§5.4 陷阱 5-2
分配结果总代价远超预期	贪心代替匈牙利，或用直线距离忽略顺路	1. ST-SR-IA 是否用了匈牙利 2. 代价是否应含真实路线（ID 依赖）3. 是否该联合分配+排序	§7.1, §9
MILP 跑数小时不收敛	规模超出 MILP 能力	1. 统计变量/约束数 2. 设求解时间上限和 gap 容差 3. 规模大改拍卖/启发式	§7.4 陷阱 7-3
拍卖分配得不偿失	出价用绝对代价非边际代价	1. 确认出价=插入路线的边际增量 2. 确认序贯（每轮更新路线）3. 检查定标规则	§8.6 陷阱 8-1
分配-规划在两步间振荡	解耦+迭代不收敛	1. 确认是否强耦合（XD）2. 弱耦合可加阻尼/锁定 3. 强耦合改联合优化	§9.4
多机系统某机器人卡死，整体停摆	失败无反馈通道，或用阻塞 service	1. 检查失败是否上传重分配 2. ROS 2 用 action 非 service 3. 确认反馈链完整	§10.4 陷阱 10-3

API 速查表¶

API / 工具	签名 / 用法	说明	对应节
`scipy.optimize.linear_sum_assignment`	`row_ind, col_ind = linear_sum_assignment(C)`	线性指派最优解，最小化 `C[row_ind,col_ind]`；最大化取负	§7.3
`pulp.LpProblem`	`prob = LpProblem(name, LpMinimize)`	MILP 问题容器	§7.5
`pulp.LpVariable.dicts`	`x = LpVariable.dicts("x", idx, cat="Binary")`	批量二元决策变量；分配必须 Binary	§7.5
`pulp.lpSum`	`prob += lpSum(c[i,j]*x[i,j] for ...)`	线性目标/约束求和	§7.5
`prob.solve`	`prob.solve(PULP_CBC_CMD(msg=0))`	调用 CBC 求解；检查 `LpStatus[prob.status]`	§7.5
`ortools ... LinearSumAssignment`	`add_arc_with_cost(r,t,cost)` → `solve()`	OR-Tools 线性指派；代价须整数；检查 status==OPTIMAL	§10.3
`ortools ... CpModel`	`CpModel()` + `CpSolver()`	通用约束/整数规划，带约束分配	§10.3
`pyperplan ... SEARCHES/HEURISTICS`	`SEARCHES["astar"](task, HEURISTICS["hff"](task))`	经典规划求解，hff=$h^{\text{FF}}$	§10.2
Fast Downward (CLI)	`fast-downward.py d.pddl p.pddl --search "astar(lmcut())"`	工程级规划器；lmcut=LM-cut 可容许启发式	§10.2
`route_length`（自定义，§8.6）	`route_length(start, points)`	最短访问路线长（小规模全排列精确）	§8.6
`marginal_cost`（自定义，§8.6）	`marginal_cost(pos, current, new)`	边际代价出价的核心	§8.6

研究实践建议¶

入门（建立可运行系统）：先把 §7.3 匈牙利、§7.5 MILP、§8.6 SSI 三段代码跑通，再做 §11 累积项目的阶段 1（多机分配层）。目标是能把"分配 + 各自规划"端到端跑起来，哪怕用直线距离近似。

进阶（处理耦合）：实现 §9.4 的策略二——把真实路线代价（调 §8.6 的 route_length 或 T1 的运动规划器）嵌入分配的代价计算。这是从"玩具系统"到"像样系统"的关键一跳，亲手体会解耦的损失。

研究（前沿方向）：分配-规划-运动的联合优化在大规模下仍是开放问题。可关注的方向：把规划器嵌入拍卖奖励的惰性策略（减少调用次数）、学习型分配（用神经网络预测边际代价以加速）、以及与 T6 不确定性、T8 多机的结合。这些都建立在本章的耦合理解之上。

下一章预告：TAMP_T3《PDDLStream 与流式集成》将深入 §9 提到的"让符号层看见几何可行性"这条路——详解 PDDLStream 如何用 Stream（条件化的几何采样器）把连续参数采样融入符号搜索，系统地缝合 TAMP_T1 §2.5 那道符号-几何鸿沟。本章 §9 的"规划嵌入代价"在那里会上升为一套完整的集成范式。

层次	这一层要回答的问题	在仓库场景里的具体形态
谁来做	5 个包裹分给 3 台机器人，怎么分？	\(R_1\) 负责 \(\{p_1,p_4\}\)、\(R_2\) 负责 \(\{p_2,p_5\}\)、\(R_3\) 负责 \(\{p_3\}\)？还是别的分法？
做什么、什么顺序	单台机器人拿到自己的包裹清单后，动作怎么排？	\(R_1\) 先去取 \(p_1\) 还是 \(p_4\)？取完一个就送、还是两个都抓在手上一起送？
怎么动过去	每个"去取 \(p_1\)"具体怎么走、怎么抓？	从当前位姿到 \(p_1\) 货架的无碰撞路径、抓取姿态、电机指令

	\(h^{\max}\)	\(h^{\text{add}}\)
聚合前提/目标	取最大 \(\max\)	求和 \(\sum\)
隐含假设	子目标可完全共享子计划（最乐观）	子目标完全独立、零共享（最悲观）
可容许？	是（永不高估）	否（会高估）
通常信息量	弱（太乐观，常严重低估）	强（更接近真实，导向性好）
典型用途	需要最优性保证时（配 A*）	只求快速找到解时（配贪心，FF 的基础）

启发式	一句话本质	可容许	信息量	计算	常见搭配
\(h^{\max}\)	删负效果后取最贵子目标	是	弱	多项式	A*（求最优）
\(h^{\text{add}}\)	删负效果后子目标代价相加	否	中	多项式	贪心（求快）
\(h^{\text{FF}}\)	删负效果后真抽一个计划数长度	否	强	多项式	加权 A*/贪心（FF、LAMA）

类别	等价的经典问题	复杂度	仓库场景例子	本章对应解法
ST-SR-IA	线性指派问题 (LAP) / 最优二部匹配	多项式可解 \(O(n^3)\)	此刻把每个空闲机器人配一个最近包裹	§7 匈牙利算法
ST-SR-TA	调度 / 多旅行商 (mTSP) 类	NP-hard	给每台机器人排一串包裹，最小化总时间	§7 MILP；§8 拍卖近似
ST-MR-IA	集合划分 (set partitioning) / 联盟形成	NP-hard	此刻把机器人分组，每组合搬一个超重包裹	§7 MILP（小规模）；近似
MT-SR-IA	一台机器人可领多任务的指派	NP-hard	每台机器人同时处理多个包裹的指派	§7 MILP
MT-MR-TA	最一般，含上述所有困难	NP-hard（最难）	多臂机器人、合作任务、未来排程全有	分解 + 启发式

症状	可能原因	排查步骤	相关节
规划器跑很久不出解（任务长）	平铺状态空间搜索爆炸，未用层次结构	1. 确认启发式是否生效（打印 \(h\) 值）2. 任务是否有标准流程→改用 HTN 3. 检查是否目标不可达	§3, §4
A* 返回的解不是最优	用了不可容许启发式（如 \(h^{\text{add}}\)）	1. 确认启发式类型 2. 求最优换 \(h^{\max}\)/LM-cut 3. 确认配的是 A* 而非贪心	§3.4 陷阱 3-1
删除松弛代价算成 ∞ 或偏大	单遍扫描未到不动点	1. 检查是否 `while changed` 循环 2. 确认每次降代价都标记 changed 3. 检查是否漏删 delete 列表	§3.6 陷阱 3-2
HTN 明明有解却返回失败	方法没覆盖该情况，或漏 base case	1. 检查复合任务是否有适用方法 2. 递归任务是否有终止方法 3. operator 是否就地改了状态	§4.5 陷阱 4-1/4-2
并发计划执行时冲突	缺 over-all 不变式	1. 检查 durative action 的保护条件 2. 用 over-all 声明执行期不变式 3. 检查时间区间是否真不冲突	§5.2 陷阱 5-1
STN 一致性检测漏报矛盾	双边约束只加单边，或用了 Dijkstra	1. 确认每条 a≤Δ≤b 加两条边 2. 用 Floyd-Warshall/Bellman-Ford（非 Dijkstra）3. 检查所有 d[i][i]	§5.4 陷阱 5-2
分配结果总代价远超预期	贪心代替匈牙利，或用直线距离忽略顺路	1. ST-SR-IA 是否用了匈牙利 2. 代价是否应含真实路线（ID 依赖）3. 是否该联合分配+排序	§7.1, §9
MILP 跑数小时不收敛	规模超出 MILP 能力	1. 统计变量/约束数 2. 设求解时间上限和 gap 容差 3. 规模大改拍卖/启发式	§7.4 陷阱 7-3
拍卖分配得不偿失	出价用绝对代价非边际代价	1. 确认出价=插入路线的边际增量 2. 确认序贯（每轮更新路线）3. 检查定标规则	§8.6 陷阱 8-1
分配-规划在两步间振荡	解耦+迭代不收敛	1. 确认是否强耦合（XD）2. 弱耦合可加阻尼/锁定 3. 强耦合改联合优化	§9.4
多机系统某机器人卡死，整体停摆	失败无反馈通道，或用阻塞 service	1. 检查失败是否上传重分配 2. ROS 2 用 action 非 service 3. 确认反馈链完整	§10.4 陷阱 10-3