分支 / 场景规划：为多个离散未来同时准备策略¶
不确定性规划方向（Part-U）第 1 章。上承 U0 总论的"五安全谱"，本章对应谱上的**分支 / contingency 端**——专门处理"他人意图"这类**离散、多模态**的不确定性。与 U2（鲁棒，连续有界扰动）、U3（机会约束，连续概率扰动）互补：那两章处理"扰动有多大"，本章处理"未来是哪一种"。
前置自测¶
开始前先自测。如果以下问题答不出 2 道及以上，建议先回到对应前置章节。
- 写出一个标准 MPC 的优化问题（决策变量、代价、动力学约束、状态/控制约束）。它对"未来"做了什么假设？（→ 若答不出，回 U0 §1 或任一方向的 MPC 基础）
- 什么是非预期约束（non-anticipativity constraint）？U2 的场景树 MPC 里它长什么样？（→ 回 U2 "场景树 MPC 的最小骨架"）
- 一辆自动驾驶车在路口看到一辆横向来车，它"可能让行也可能抢行"。如果你的规划器只赌"最可能"的那个，会有什么风险？
- POMDP 的状态、观测、信念（belief）各是什么？为什么直接精确求解 POMDP 通常不可行？（→ 回 U0 §3 / §6，U4 会展开）
- CVaR\(_\alpha\) 和期望、最坏情况分别是什么关系？（→ 回 U0 §3，U5 会展开）
这 5 题分别对应本章要用的五块前置：MPC 优化结构（全章地基）、非预期约束（§U1.1/§U1.6 的核心）、意图不确定性的危害（§U1.1 动机）、POMDP（§U1.4 EPSILON 的形式化背景）、CVaR（§U1.5 MARC 的风险度量）。
本章目标¶
学完本章，你应该能够：
- 说清"分支规划 vs 单轨迹规划"的本质区别：单轨迹规划假设未来唯一确定；分支规划显式枚举多个离散未来，并在当前决策中保留对所有分支的兼容性（"共享干 + 分支"）。
- 推导分支规划的基本形式化：场景加权代价 + 共享干（非预期）约束 + 各分支独立优化，并说明三个关键设计旋钮（分支点 \(t_{\text{branch}}\)、分支数 \(K\)、场景概率 \(P(\omega_k)\)）。
- 实现 MPDM 的策略枚举 + 闭环前向仿真：写出 IDM 跟车模型与 MOBIL 换道模型，理解代价评估与 \(O(|\Pi|^{n})\) 复杂度瓶颈。
- 解释 EUDM 如何把组合爆炸压回可实时：DCP-Tree（策略序列而非组合）+ CFB（只在危险交互处分支）。
- 说清 EPSILON = EUDM + SSC 的分层架构：行为决策层（POMDP + 引导分支）→ 运动规划层（时空语义走廊 QP）。
- 理解 MARC 的两项关键进化：场景级 divergence 动态决定分支点（而非固定时刻）+ CVaR 风险感知双层优化。
- 建立 Multi-stage NMPC 与分支规划的数学同构：scenario tree = contingency tree，并解释二者社区为何几乎不互引。
- 对比分支规划与 MCTS 的结构差异：领域先验固定宽度树 vs UCB 自适应探索；无反向传播 vs 累积统计量。
本章知识导航 ⭐¶
本章沿一条主线展开：当未来有 \(K\) 种离散可能时，不要只赌一个，而要"用一段共享的当前动作对所有可能都安全，再在未来分叉时分别优化"——即"共享干 + 加权分支"。
单轨迹 MPC（赌一个最可能的未来，U0/U2/U3 已掌握）
│ 未来其实是"离散多模态"的（他车让/不让、左转/右转）
▼
┌──────────────────────────────────────────────┐
│ 分支 / 场景规划（本章主线） │
│ min Σ_k P(ω_k)·J(u, ω_k) │
│ s.t. 共享干 u(t0:t_branch) 对所有 ω_k 相同 │
│ 分支 u(t_branch:T, ω_k) 各自独立 │
└──────────────────────────────────────────────┘
│ │ │
如何枚举场景 如何压缩搜索 如何定分支点 + 风险
§U1.2 MPDM §U1.3 EUDM §U1.5 MARC
(策略×前向仿真) (DCP-Tree+CFB) (divergence+CVaR)
│
▼
§U1.4 EPSILON（EUDM + SSC 完整系统）
§U1.6 Multi-stage NMPC（化工社区的同构形式）
§U1.7 vs MCTS（与搜索式规划的结构对比）
本章方法谱系（这条线怎么来的）：分支规划由 Hardy 与 Campbell 在 2013 年系统提出（在概率障碍预测上同时优化多条 contingency 路径）；2015 年 Cunningham 等的 MPDM 把他车建模为离散语义策略集、枚举评估；2020 年 HKUST 的 EUDM 用 DCP-Tree + CFB 把组合爆炸压回实时；2021 年 EPSILON 把 EUDM 与时空语义走廊拼成完整开源系统；2023 年 MARC 引入场景级动态分支点与 CVaR 风险度量。与此平行，化工过程控制社区的 Lucia–Engell 在 2013 年独立发展出 multi-stage NMPC（scenario tree），数学上与 contingency planning 严格同构却几乎不互引。各方法的精确出处在文末"延伸阅读"给出并已逐一核实。
阅读路径：想快速建立直觉 → §U1.1（形式化 + frozen robot 问题）+ §U1.2 的"本质洞察"；想动手 → §U1.2（MPDM）+ 完整实现精读 + 累积项目；想理解工业系统 → §U1.3/§U1.4（EUDM/EPSILON）；想做研究 → §U1.5（MARC）+ §U1.6（同构）+ 前沿。§U1.7（vs MCTS）是连接经典规划与搜索/RL 的桥，按兴趣选读。
前置知识桥接¶
本章建立在以下前置之上，这里用 2–3 行重新激活，便于不翻回去也能跟上。
- MPC 的优化结构（U0 / 任一方向 MPC）：MPC 在每个控制周期解一个有限时域最优控制问题（OCP）——决策一条控制序列，最小化预测时域上的代价，满足动力学、状态、控制约束，施加首控制后滚动重解。本章把"一条轨迹"升级成"一棵轨迹树"。
- 非预期约束（U2 场景树 MPC）：回顾 U2 末尾的场景树 MPC——在不确定性揭示之前，各场景必须共用同一个控制（你此刻还分不清是哪种情况），写成 \(u_j^{(0)}=u_{j'}^{(0)}\ \forall j,j'\)。本章把这个"共享当前动作"的思想做成主角，称为"共享干"。
- 机会约束收紧（U3）：回顾 U3——线性约束 \(a^\top x\le b\) 在高斯不确定下收紧为 \(a^\top\bar x\le b-\Phi^{-1}(1-\delta)\sqrt{a^\top\Sigma a}\)。本章每条分支内部仍可用这套收紧处理连续扰动——分支处理"离散意图"、收紧处理"连续噪声"，两者正交、可叠加。
- CVaR（U0 §3，U5 详解）：回顾 U0——CVaR\(_\alpha\) 是"最坏 \((1-\alpha)\) 尾部的平均损失"，介于期望与最坏情况之间的连续旋钮。§U1.5 的 MARC 用它给场景代价做风险加权。
- POMDP（U0 §3/§6，U4 详解）：回顾 U0——POMDP 在部分可观测下规划，状态不可直接测，只能维护信念 \(b(x)\)；精确求解一般不可行。§U1.4 的 EPSILON 把决策形式化为 POMDP，但用"引导分支"避开了直接求解的爆炸。
如果跳过本章会怎样¶
- 场景一（frozen robot，僵住的机器人）：你的机器人在人群 / 车流中导航，预测每个动态障碍的未来轨迹后发现"几乎所有方向都可能撞"，于是单轨迹规划器找不到可行解、机器人停在原地不动（frozen robot problem）。根因是它假设了"未来唯一确定"并对最坏预测买单。分支规划通过"对多个离散未来分别留一条出路、当前只走它们的公共安全动作"化解僵局。
- 场景二（决策振荡）：路口对向来车意图不明，你的规划器这一帧赌"它会让"、下一帧赌"它不让"，于是 ego 在加速与刹车之间反复横跳（决策振荡 / policy oscillation），既不舒适也不安全。分支规划用"共享干"保证短期一致性——当前这一段动作对所有意图都成立，不会因为预测翻转就突变。
预计阅读时间¶
- 精读（推导 + 代码 + 手算走查 + 自己实现 MPDM）：约 8–11 小时。
- 速读（抓主线 + 看本质洞察 + 跳过部分源码精读）：约 3–4 小时。
- 速查（已学过，回来查 DCP-Tree / 非预期约束 / 选型）：用"实践索引"与"本章符号速查"直接定位，约 20 分钟。
§U1.1 分支规划的基本形式化 ⭐⭐¶
动机：未来不是"一条"，而是"几种"¶
前面三章（U0/U2/U3）的规划器，骨子里都假设**未来是一条确定的轨迹**——哪怕带不确定性，也是"一条名义轨迹 + 一圈误差管道"（U2）或"一条名义轨迹 + 概率收紧"（U3）。这对"扰动是连续小抖动"的执行端不确定性很合适。
但有一类不确定性根本不是"小抖动"，而是**离散的、分叉的**：
- 路口的对向来车，要么让行、要么抢行——这是两种定性不同的未来，不是"让行程度的连续抖动"。
- 你要并线，旁边车道的后车**要么减速放你进、要么加速堵你**。
- 前车**要么直行、要么右转下匝道**。
这些是**他人意图（intent）的不确定性**。它的特点是：可能的未来是**少数几个离散模态**，每个模态对应一条定性不同的演化；而且**哪个模态会发生，往往要再过一会儿才能从观测中看清**（车开始减速了，你才知道它要让你）。
多视角理解：连续扰动 vs 离散意图，两种不确定性 - 物理视角：连续扰动像"风把车吹偏一点点"（U2/U3 处理）——围绕名义轨迹的小邻域抖动；离散意图像"岔路口往左还是往右"——几条分开的路。像 / 不像：两者都让未来不确定，但前者是单峰分布的方差，后者是多峰分布的"哪个峰"。 - 分布视角：连续扰动 → 单峰（近似高斯）分布，用方差刻画；离散意图 → 多峰（混合）分布，用"模态 + 权重"刻画。U3 进阶专题里的 GMM-CC 已经碰到多峰，但那里是把多峰拆成多个高斯各自收紧；本章是为每个模态**准备一条独立的未来策略**。 - 决策视角：面对方差，你留一圈安全裕度就够（一个动作应对所有抖动）；面对多峰，单一动作往往**无法同时对所有峰最优**——抢行就该刹车、让行就该通过，你得"先走一个对两者都不坏的动作，等看清了再分别应对"。这就是分支规划。
把"赌最可能的单一未来"换成"为多个离散未来分别准备"，正是本章的全部出发点。
反面：只赌最可能的未来会怎样¶
设想最朴素的做法：用一个预测器给出每个他车**最可能**的未来轨迹，然后当成确定的障碍，做一次普通单轨迹 MPC。两个典型失败：
失败一：frozen robot（僵住）。如果预测器给的是"覆盖所有可能性"的悲观预测（他车的可达集很大），单轨迹规划器会发现整条路都被"可能占用"的区域堵死，找不到可行轨迹，于是机器人停下不动。这在密集人群导航里极其常见——预测越保守，机器人越容易僵住。
失败二：决策振荡。如果预测器给的是"当前最可能"的单一模态，那么当观测把"最可能"从模态 A 翻到模态 B 时（他车的细微动作让概率反转），规划器的最优解会**突变**——上一帧还在加速通过、这一帧就猛刹让行。反复翻转就是决策振荡，乘客体验极差且不安全。
本质洞察：单轨迹规划的两难，根源是"过早承诺"。frozen robot 是"对所有可能都承诺避让"（太保守、无解），决策振荡是"对当前最可能完全承诺"（太激进、易翻转）。两者都错在**在信息还不够时就把当前动作完全绑定到某个未来假设上**。分支规划的解法是"延迟承诺"（commitment deferral）：当前只走一段对所有候选未来都安全的"共享干"，把"到底按哪个未来走"的承诺**推迟到分支点之后**——那时观测多半已经把真实意图揭示出来了。这正是 U0 §1 "保守度应由信息推导"在时间维度上的体现：信息不足时不承诺，信息到位了再分叉。
延伸：延迟承诺（commitment deferral）作为统一原理¶
把"frozen / 振荡"的诊断再推一层，会得到一个可迁移的设计原理：延迟承诺。
任何在不确定下做序贯决策的系统，都面临一个张力：现在就承诺一个未来假设（决断但可能错）vs 等信息更全再决定（稳妥但可能太晚）。单轨迹规划把这个张力推到极端——它每一帧都对"某个单一未来"完全承诺当前动作。frozen 是"承诺避让所有可能"（保守端的承诺），振荡是"承诺当前最可能"（激进端的承诺，且随预测翻转而反复重新承诺）。
延迟承诺的解法：把"承诺哪个未来"推迟到信息能支撑这个承诺的时刻，在此之前只做"对所有候选未来都不坏"的动作（共享干）。形式上，承诺时刻 = 分支点 \(t_{\text{branch}}\)，理想值是"信息揭示时刻"（各未来的最优当前动作开始分歧之时）。
这个原理不止用于驾驶： - 机器人导航：人群里不急着决定"从左绕还是右绕",先减速直行（对两者都不坏），等人的走向明朗再绕。 - 投资 / 期权：不确定时持有现金 / 期权（保留选择权），信息到位再下注——金融里这叫"实物期权（real option）"，与延迟承诺同构。 - 多阶段随机规划：here-and-now 决策 + recourse（进阶专题一）——recourse 就是"等不确定性揭示后的延迟承诺"。
本质洞察：分支规划是"延迟承诺"在轨迹空间的实现。共享干 = 推迟承诺期间的稳健动作，分支 = 承诺后对各未来的最优反应，分支点 = 承诺时刻。一旦你用"何时承诺、承诺前做什么稳健动作"这套语言来想，frozen / 振荡 / 保守度 / 一致性就都统一了——它们都是"承诺时机选错"的不同表现。这也是为什么 MARC 把"分支点"做成自适应（在信息真正揭示处承诺）是质的进步：它把承诺时机对齐到了信息节奏上。
理论：分支规划的基本形式化¶
把上面的直觉写成优化问题。在当前时刻 \(t_0\)，ego 面对 \(K\) 个可能的离散未来情景 \(\{\omega_1,\dots,\omega_K\}\)（例如他车的 \(K\) 种意图），每个情景有概率 \(P(\omega_k)\)（\(\sum_k P(\omega_k)=1\)，来自预测器或先验）。我们要决策一棵**轨迹树**：一段所有情景共用的"共享干" + 每个情景一条独立的"分支"。
逐项解读：
- 场景加权代价 \(\sum_k P(\omega_k) J(\cdot;\omega_k)\)：不是只优化某一个未来，而是优化所有未来的**期望代价**。注意代价 \(J\) 同时依赖共享干和该情景的分支。
- 共享干约束（核心）：\(t_0\) 到 \(t_{\text{branch}}\) 之间的控制 \(u_{\text{trunk}}\) 对所有情景**必须相同**。这正是 U2 见过的**非预期约束（non-anticipativity）**——在不确定性揭示之前（\(t<t_{\text{branch}}\)），你还分不清是哪个 \(\omega_k\)，所以此刻只能下一个对所有情景一致的动作。它保证了短期决策的一致性（消除振荡）。
- 分支约束：\(t_{\text{branch}}\) 之后，每个情景 \(\omega_k\) 用各自独立的控制 \(u_k\)、在各自的动力学 / 约束 \(f(\cdot,\omega_k)\)、\(\mathcal{X}(\omega_k)\) 下优化。这保证了对每个未来都留了一条专门的出路（化解 frozen robot）。
- 约束随情景变：\(\mathcal{X}(\omega_k)\) 强调障碍 / 可行域本身依赖情景——他车让行时它占的空间，和抢行时不同。
执行时只施加**共享干的第一个控制** \(u_{\text{trunk}}^{(0)}\)，然后滚动重规划——和标准 MPC 的滚动时域一致。下一周期观测更新，\(K\) 个情景的概率 \(P(\omega_k)\) 也更新，分支树重新展开。
多视角理解：分支规划的轨迹树的三种看法 - 决策树视角：根是当前状态，从根伸出一段共享干，到分支点后分叉成 \(K\) 条枝，每条枝对应一个未来情景。这棵树深度浅（通常一层分叉）、宽度固定（\(K\) 由领域先验定）。 - 优化视角：它是一个**带耦合约束的多场景优化**——\(K\) 个子问题（每个情景一条轨迹）通过"共享干相同"这条非预期约束耦合在一起。去掉耦合就退化成 \(K\) 个独立 MPC；耦合越长（\(t_{\text{branch}}\) 越晚），越保守也越一致。 - 博弈 / 信息视角：共享干是"在信息不足时的稳健动作"，分支是"信息到位后的最优反应"。\(t_{\text{branch}}\) 就是你**假设的"信息揭示时刻"**——你赌"到了 \(t_{\text{branch}}\) 就能看清他车意图"。这把规划和"何时能获得信息"显式联系起来（U4 的主动感知会把"何时获得信息"也变成决策）。
三个关键设计旋钮¶
形式化里有三个必须定的量，它们决定了一个分支规划器的全部行为：
| 旋钮 | 含义 | 各方法怎么定 |
|---|---|---|
| \(t_{\text{branch}}\) 分支点 | 共享干多长、何时分叉 | MPDM / EUDM：固定（如每个策略节点一段，EUDM 用 8s 时域、2s 一个策略节点、树深 4）；MARC：动态（按场景轨迹"开始显著分叉"处，用 Wasserstein 距离度量） |
| \(K\) 分支数 | 枚举几个未来 | MPDM：\(O(\|\Pi_{\text{ego}}\|\cdot\|\Pi_{\text{other}}\|^{n})\)（组合，易爆炸）；EUDM：CFB 裁到 3–8 个 |
| \(P(\omega_k)\) 场景概率 | 各未来的权重 | 来自预测器输出 / 领域先验 / 对他车意图的贝叶斯更新 |
为什么 \(t_{\text{branch}}\) 是最关键的旋钮：它太早（共享干太短）→ 退化成 \(K\) 个几乎独立的 MPC，短期一致性弱、易振荡；太晚（共享干太长）→ 所有情景被迫共用很长一段动作，过度保守（回到 frozen 的边缘）。"在信息真正揭示的时刻分叉"才最优——这正是 MARC 相对 MPDM/EUDM 的核心改进（§U1.5）。
与单轨迹 MPC 的对比¶
| 维度 | 单轨迹 MPC | 分支规划 |
|---|---|---|
| 决策变量 | 一条轨迹 \(u(t_0:T)\) | 一棵轨迹树 \(\{u_{\text{trunk}},u_1,\dots,u_K\}\) |
| 未来假设 | 最可能的单一未来 | \(K\) 个离散未来 + 概率权重 |
| 问题规模 | \(N\times(n_x{+}n_u)\) | 共享干 \(N_{\text{trunk}}\times(n_x{+}n_u)\) + 分支 \(\approx K\times N\times(n_x{+}n_u)\) |
| 计算代价 | \(1\times\) | \(\sim K\times\)（但共享干减少实际增量） |
| 对振荡的鲁棒性 | 差（最优策略随预测翻转而突变） | 好（共享干保证短期一致性） |
| frozen robot | 易发生（对悲观预测无解） | 缓解（每个未来各留一条出路） |
| 处理的不确定性 | 连续小扰动（配 U2/U3） | 离散多模态意图 |
问题规模走查：分支比单轨迹大多少¶
把"问题规模 \(\sim K\times\)（但共享干减少增量）"用具体数字坐实。设时域 \(N=30\) 步、状态 \(n_x=2\)（位置 \(s\)、速度 \(v\)）、控制 \(n_u=1\)（加速度 \(a\)）、分支数 \(K=2\)、共享干 \(N_{\text{trunk}}=10\)。
- 单轨迹 MPC：控制变量 \(N\cdot n_u=30\) 个，状态变量 \((N{+}1)\cdot n_x=62\) 个。
- 分支规划：控制变量 \(=\underbrace{N_{\text{trunk}}}_{\text{共享干}}+\underbrace{K\cdot(N-N_{\text{trunk}})}_{\text{各分支}}=10+2\times20=50\) 个（不是 \(K\cdot N=60\)——共享干那 10 步只算一次）；状态变量 \(K\cdot(N{+}1)\cdot n_x=2\times31\times2=124\) 个。
对比：控制变量 \(50\) vs 单轨迹 \(30\)（\(1.67\times\)，而非 \(K=2\) 倍）——差的那 \(0.33\times\) 正是共享干省下的（共享段不按分支翻倍）。共享干越长，增量越小：若 \(N_{\text{trunk}}=20\)（共享更长），控制变量 \(=20+2\times10=40\)（仅 \(1.33\times\)）；若 \(N_{\text{trunk}}=0\)（无共享），控制变量 \(=2\times30=60\)（满 \(2\times\)，且退化成独立两段）。
这给出一个清晰的工程图景：分支规划的规模增量由"\(K\) 和分支段长度"决定，共享干越长增量越小。所以控制 \(K\)（CFB）和合理设共享干长度（不必太短）既是质量旋钮、也是规模 / 实时旋钮。
本质洞察：分支规划的成本几乎全在"分支数 \(K\)"，而收益几乎全在"共享干"。问题规模随 \(K\) 近似线性增长（分支后每个情景一条轨迹），所以控制 \(K\)（EUDM 的 CFB 干这个）是工程可行性的关键；而真正解决 frozen / 振荡两难的，是共享干那条非预期约束——它让你"现在只下一个对所有未来都安全的动作"。记住这一点：分支是为了不漏掉任何未来，共享干是为了不过早承诺任何未来。后续所有方法（MPDM/EUDM/EPSILON/MARC/multi-stage NMPC）都只是在回答"\(K\) 个情景怎么选、怎么压、分支点放哪、代价怎么加权"——骨架就是上面这个"共享干 + 加权分支"。
⚠️ 本节常见陷阱¶
💡 概念误区：把"分支规划"和"为每个场景各跑一个独立 MPC"混为一谈 - 新手想法："不就是对 \(K\) 个未来各算一条最优轨迹吗？分别跑 \(K\) 次 MPC 就行。" - 现象 / 后果：\(K\) 条轨迹的"当前动作"互不相同，你不知道该执行哪一个；若按"最可能场景"那条执行，就退回了单轨迹规划的决策振荡。 - 根本原因：漏掉了**共享干（非预期约束）。分支规划的灵魂不是"分别优化",而是"分支前必须共用一个当前动作"——正是这条耦合约束让"当前该做什么"有唯一、稳健的答案。 - **正确做法：把 \(K\) 个场景作为**一个**带非预期约束的联合优化求解，输出唯一的共享干第一控制。检验方法：把分支点 \(t_{\text{branch}}\) 设到 0（无共享干），看决策是否开始随预测翻转而振荡——若是，说明你之前确实靠共享干在稳住。
🧠 思维陷阱：以为分支越多（\(K\) 越大）越安全 - 新手想法："多枚举几个未来总没坏处，\(K\) 大覆盖更全。" - 现象 / 后果：\(K\) 一大，问题规模线性膨胀、求解超时；且大量低概率冗余场景稀释了对真正危险场景的关注。 - 根本原因：\(K\) 是计算成本的主因，而安全主要由"是否覆盖了真正危险的那几个模态"决定，不由数量决定。EUDM 的 CFB 正是基于这一点——只在"危险交互"处分支，其余用最可能模态。 - 正确做法：用危险度 / 交互度筛选要分支的场景（CFB 思想），把 \(K\) 控制在 3–8；宁可多花在"分支点放得准"（MARC）也不要盲目加 \(K\)。
💡 编程陷阱：共享干约束只加在状态上、忘了加在控制上 - 现象 / 报错：把"共享干"实现成"各场景前 \(N_{\text{trunk}}\) 步状态相等"，但控制变量仍各自独立——结果分支前各场景的控制不同，等于没有非预期约束。 - 错误代码：
cons += [x[j][t] == x[0][t] for t in range(N_trunk)]（只约束状态）。 - 正确写法：非预期约束要加在**控制**上cons += [u[j][:, :N_trunk] == u[0][:, :N_trunk]]（分支前控制相同）；由于各场景初始状态相同、动力学在分支前也相同（共享干段尚未受情景影响），控制相同会自动让状态相同。 - 根本原因：你执行的是控制（首控制下发执行器），不是状态；非预期的本质是"此刻下的动作只能有一个"，所以约束的对象必须是控制。 - 检验方法：打印各场景分支前的控制序列，应逐元素相等。
练习¶
- [A 型·形式化] 把上面的分支规划形式化退化到 \(K=1\)（只有一个未来），证明它就是普通单轨迹 MPC。再退化到 \(t_{\text{branch}}=T\)（共享干贯穿全程），说明此时 \(K\) 个场景被迫共用整条轨迹——这对应什么经典方法的保守程度？（提示：对所有场景共用一条轨迹 \(\approx\) 对场景集做某种"最坏/期望"处理）
- [A 型·实现，累积项目 U1 起点] 用 cvxpy 实现一个最小两场景分支规划（1D 或 2D）：一个动态障碍有"减速 / 匀速"两种意图，ego 在共享干段下统一动作、分支段各自避让。可视化轨迹树（共享干 + 两条分支）。观察：把 \(t_{\text{branch}}\) 从早调到晚，共享干越长 ego 越保守。
- [思考题] frozen robot 和决策振荡是单轨迹规划的两个失败模式。请用"承诺时机"这一个概念统一解释它们，并说明共享干 + 分支如何同时治好这两个病。
§U1.2 MPDM：多策略决策 ⭐⭐⭐¶
动机：他车的未来不是任意轨迹，而是少数几种"语义策略"¶
§U1.1 的形式化里，\(K\) 个情景 \(\omega_k\) 是抽象的"离散未来"。MPDM（Multi-Policy Decision Making，多策略决策，Cunningham 等, ICRA 2015） 给了它一个极有用的具体化：把每辆车（包括 ego 和他车）的未来建模为从一个小的、语义明确的策略集合里选一个。
人开车不是在连续控制空间里任意游走，而是在执行少数几个**语义策略**：跟车、左变道、右变道、加速、减速。MPDM 的洞察是——既然如此，与其预测他车的连续轨迹，不如枚举它在执行哪个语义策略。这把"无穷维的轨迹预测"降成"有限个离散策略的概率分配"，正好对应 §U1.1 的 \(K\) 个情景。
多视角理解：从"预测轨迹"到"枚举策略"的转变 - 预测视角：传统做法预测他车未来位置序列（一条或多条轨迹），是连续空间的回归问题。 - 策略视角（MPDM）：MPDM 改问"他车在执行哪个语义策略（跟车/变道/...）"，是离散空间的分类 / 枚举问题。像 / 不像：两者都在回答"他车会怎么动"，但策略视角把问题离散化、语义化，可解释性强、天然对应分支。 - 闭环视角：关键是 MPDM 用**闭环前向仿真**评估——给定 ego 策略和他车策略，让双方都按各自策略（用 IDM/MOBIL 这类反应式模型）相互响应地推演一段时间，而不是把他车当成不随 ego 反应的"录像"。这抓住了**交互**：ego 减速，他车也会跟着调整。
算法：策略枚举 + 闭环前向仿真¶
MPDM 的核心循环：枚举 ego 的候选策略，对每个 ego 策略、在他车各候选策略下做闭环前向仿真，按他车策略概率加权得到该 ego 策略的期望代价，最后选代价最小的 ego 策略。
输入：ego 候选策略集 Π_ego = {跟车, 左变道, 右变道, 加速, 减速}
他车候选策略集 Π_other（同类）+ 各策略先验/预测概率 P(π_other)
for π_ego in Π_ego:
for π_other in Π_other: # 或只对 top-k 关键他车
# 闭环前向仿真 2–5s：ego 按 π_ego、他车按 π_other，用 IDM/MOBIL 互相反应
rollout = closed_loop_sim(π_ego, π_other, horizon=T_sim)
score(π_ego, π_other) = cost(rollout) # 安全 + 效率 + 舒适
J(π_ego) = Σ_{π_other} P(π_other) · score(π_ego, π_other)
π* = argmin_{π_ego} J(π_ego)
执行 π* 对应的轨迹的首段，滚动重规划
注意这正是 §U1.1 形式化的一个具体实例：\(\omega_k\) = 他车策略 \(\pi_{\text{other}}\)，\(P(\omega_k)=P(\pi_{\text{other}})\)，代价 \(J\) 来自闭环前向仿真。ego 选出的 \(\pi^*\) 就是"对所有他车策略加权最优"的那条共享策略——MPDM 的"共享"体现在它**选一个语义策略**（而非一条轨迹），这个策略本身在短期内对各种他车反应都给出一致的动作。
闭环前向仿真的两个反应式模型¶
MPDM 的前向仿真要让车"按策略自动驾驶"，靠两个经典的微观交通模型。
IDM（Intelligent Driver Model，智能驾驶员模型，Treiber–Hennecke–Helbing, 2000） 管纵向（跟车）。它给出加速度作为"自己想多快"和"前车有多近"的函数：
其中期望间距
五个参数：期望速度 \(v_0\)、最大加速度 \(a\)、舒适减速度 \(b\)、最小停车间距 \(s_0\)、期望车头时距 \(T\)；\(s\) 是与前车的实际间距、\(\Delta v=v-v_{\text{lead}}\) 是接近速度。直觉：括号里第一项 \((v/v_0)^4\) 是"自由驾驶"项（没车挡时趋向 \(v_0\)），第二项 \((s^*/s)^2\) 是"交互"项（前车越近、相对速度越大，\(s^*\) 越大、减速越狠）。\(s\to s^*\) 时两项平衡、加速度趋零（稳定跟车）。
MOBIL（Minimizing Overall Braking Induced by Lane changes，换道模型，Kesting–Treiber–Helbing, 2007） 管横向（换道决策）。它用 IDM 算"换道前后各车的加速度变化"，换道当且仅当满足：
- 安全准则：换道后，目标车道后车的 IDM 加速度 \(a^{\text{new}}_{\text{back}}\ge -b_{\text{safe}}\)（别逼得后车急刹）。
- 激励准则：\(\underbrace{(a^{\text{new}}_{\text{ego}}-a^{\text{old}}_{\text{ego}})}_{\text{自己的收益}}+p\cdot\underbrace{\big[(a^{\text{new}}_{\text{others}}-a^{\text{old}}_{\text{others}})\big]}_{\text{对相关邻车的影响}}>\Delta a_{\text{th}},\)
其中 \(p\in[0,1]\) 是**礼让系数（politeness）**——\(p=0\) 是只顾自己的自私司机，\(p=1\) 是完全考虑邻车感受；\(\Delta a_{\text{th}}\) 是换道阈值（避免频繁变道）。直觉：换道要让"自己加速度的提升，加上礼让加权的邻车加速度变化"超过一个阈值才值得。
IDM 行为深入：四个 regime、五参数与数值走查¶
IDM 之所以是前向仿真的好"演员",在于一条公式自然涵盖了驾驶的几个定性行为段（regime）。把加速度 \(\dot v=a[1-(v/v_0)^4-(s^*/s)^2]\) 的两项拆开看：
- 自由流（free flow）：前车很远（\(s\gg s^*\)），交互项 \((s^*/s)^2\to 0\)，加速度 \(\approx a[1-(v/v_0)^4]\)——趋向期望速度 \(v_0\)。\(v\ll v_0\) 时全力加速，\(v\to v_0\) 时加速度趋零。
- 接近（approaching）：前车较近且更慢（\(\Delta v>0\)），\(s^*\) 因相对速度项 \(\frac{v\Delta v}{2\sqrt{ab}}\) 增大，交互项变大，开始减速。这是 IDM 的**预判刹车**——不等贴近，凭相对速度就提前减速。
- 跟随（following）：\(s\approx s^*\)、\(\Delta v\approx 0\)，两项接近平衡，加速度小、稳定跟车。平衡间距由 \((v/v_0)^4=(s^*/s)^2\) 解出，略大于 \(s^*\)。
- 紧急（emergency）：间距骤小（\(s\ll s^*\)），交互项 \((s^*/s)^2\) 暴涨，加速度大幅为负——急刹。
五参数的物理意义（调它们就是调驾驶风格）：
| 参数 | 含义 | 调大效果 |
|---|---|---|
| \(v_0\) 期望速度 | 自由流目标速度 | 开得更快 |
| \(a\) 最大加速度 | 加速能力 | 起步 / 提速更猛 |
| \(b\) 舒适减速度 | 期望减速强度 | 刹车更果断（也影响 \(s^*\)） |
| \(s_0\) 最小停车间距 | 静止时的车距 | 停车留更大间隙 |
| \(T\) 期望车头时距 | 动态跟车的时间间距 | 跟车更松（间距随速度线性增大） |
跟车数值走查（本车初速 8、前车匀速 6、初始间距 20，\(dt=0.5\)，默认参数）：
| \(t\) | \(v_{\text{ego}}\) | gap | \(s^*\) | accel |
|---|---|---|---|---|
| 0.0 | 8.00 | 20.0 | 18.62 | \(-0.10\) |
| 1.0 | 7.86 | 18.10 | 17.99 | \(-0.26\) |
| 2.0 | 7.58 | 16.44 | 16.82 | \(-0.31\) |
| 3.0 | 7.27 | 15.10 | 15.57 | \(-0.30\) |
本车比前车快，IDM 凭相对速度提前温和减速（accel 始终小幅为负），速度从 8 渐降向 6（匹配前车）、间距从 20 收敛向平衡值。平衡间距：稳态时 \(v=v_{\text{lead}}=6\)、\(\Delta v=0\)，\(s^*=s_0+vT=2+6\times1.5=11\)；平衡需 \((v/v_0)^4=(s^*/s)^2\)，解出 \(s_{\text{eq}}=s^*/\sqrt{1-(6/12)^4}=11/\sqrt{0.9375}\approx 11.36\)。即本车最终以 6 m/s 跟在前车后约 11.4m——一个由参数完全决定的稳定跟随。
对比性思维：IDM 是"连续函数"而非"规则集"。朴素的跟车模型常写成 if-else 规则（"近了就刹、远了就加"）；IDM 用一条光滑函数同时涵盖自由流 / 接近 / 跟随 / 紧急四个 regime，regime 之间平滑过渡、无突变。这让前向仿真的轨迹连续可微、无规则边界处的抖动——也是它比规则式模型更适合做 MPDM 前向仿真"演员"的原因。
本质洞察：MPDM 的前向仿真用"行为模型"代替"轨迹预测"。IDM/MOBIL 不是预测某辆车的具体轨迹，而是给一个**策略**（如"跟车"）配一套反应式动力学，让车在仿真里自己跑出轨迹。这有两个好处：(1) 交互闭环——ego 和他车在仿真里相互反应，自动体现"ego 减速则他车跟进"；(2) 语义可解释——每条仿真轨迹对应一个明确的策略组合，便于调试和审计。代价是 IDM/MOBIL 是简化模型，真实司机未必严格遵守（EPSILON 后来加了"安全机制"来兜底这种模型失配，§U1.4）。
MOBIL 换道决策的数值走查¶
把实现三的 mobil_lane_change 跑三个典型情形（数值已核对），看清安全准则与激励准则怎么协同。礼让系数 \(p=0.3\)、安全阈值 \(b_{\text{safe}}=4\)、换道阈值 \(a_{\text{th}}=0.1\)。
| 情形 | 设定 | 激励值 | 安全 | 换道？ | 解读 |
|---|---|---|---|---|---|
| 该换 | 当前道有慢前车(gap10,lead 6)、目标道空、后车远(v8,gap40) | \(+12.2\) | 是 | 换 | 慢前车拖累 ego，旁道畅通、后车不受扰 → 激励大、安全满足 |
| 不该换 | 同上，但目标道后车很近(gap3)且快(v12) | \(-24.0\) | 否 | 不换 | 并入会逼后车急刹（\(a^{\text{new}}_{\text{back}}<-b_{\text{safe}}\)）→ 安全准则一票否决 |
| 不必换 | 当前道畅通(无前车)、目标道也空 | \(-0.02\) | 是 | 不换 | 本道已畅通、换道无收益 → 激励 \(<a_{\text{th}}\)，没必要折腾 |
三个情形覆盖 MOBIL 的全部判断逻辑：
- **激励准则**决定"想不想换"——情形一激励 \(+12.2\)（强烈想换，因前方被慢车堵），情形三激励 \(-0.02\approx0\)（本道畅通、无动机）。
- 安全准则**决定"能不能换"——情形二激励本可能为正（前方有慢车），但目标道后车太近，并入会逼它急刹（\(a^{\text{new}}_{\text{back}}\le-b_{\text{safe}}\)），安全准则**一票否决，无论激励多大都不换。
- 礼让系数 \(p\) 的作用：激励里的 \(p\cdot(a^{\text{new}}_{\text{back}}-a^{\text{old}}_{\text{back}})\) 项，让 ego 在算"换不换"时把"对目标道后车的影响"按 \(p\) 计入——\(p\) 大则更顾及后车（少做激进切入），\(p=0\) 则只顾自己。
对比性思维：MOBIL 的"安全准则一票否决" vs "激励准则加权权衡"。两个准则地位不对等——安全准则是**硬门槛**（不满足直接不换，类似 U2 的 CBF 硬安全约束），激励准则是**软权衡**（收益超阈值才换，类似代价函数里的偏好项）。这种"硬安全门槛 + 软收益权衡"的二层结构，在机器人决策里反复出现（CBF-QP 的硬约束 + 软目标、机会约束的硬违约上限 + 软效率代价）。MOBIL 把它用在换道上：先过安全关，再比收益——安全永远优先于效率。
闭环前向仿真为什么对 merge 场景是决定性的¶
§U1.2 的本质洞察强调"闭环 vs 开环"。用并线（merge）场景把这点讲透——它是分支规划文献的标志性场景，也是开环必败、闭环必需的最清楚例子。
场景：ego 在汇入车道，想并入主路；主路上 ego 目标间隙的后方有一辆车 B。ego 有 {加速并入, 减速等待} 两策略，B 有 {让行（减速给空间）, 不让（保持 / 加速）} 两意图。
开环仿真为什么必败：开环把 B 当成"按预测轨迹走的录像"——B 的轨迹固定、不随 ego 反应。于是： - 若预测 B"匀速不让",ego 算出"间隙不够、并不进去"→ 选"减速等待"→ 但如果 B 其实会让，ego 白白错过了并入机会（过保守 / frozen 边缘）。 - 开环永远看不到"ego 一压过去、B 就会松油门让行"这种**交互涌现**的间隙。
闭环仿真为什么必需：闭环让 ego 和 B 都按各自策略用 IDM 互相反应—— - ego 选"加速并入"+ B 是"让行"意图：ego 前压，B 的 IDM 检测到前方 ego 切入、自动减速让出空间 → 并入成功、代价低。 - ego 选"加速并入"+ B 是"不让"意图：ego 前压，B 不减速甚至加速 → 间隙不够、安全罚高 → 该组合代价高。
于是 MPDM 在闭环下能正确区分"B 让"和"B 不让"两个分支，并按概率加权选策略——B 大概率让则倾向并入，大概率不让则等待。这种"我压你让 / 我压你不让"的交互后果，只有闭环仿真才看得到。
本质洞察：merge 的本质是"间隙是协商出来的,不是观测到的"。开环假设间隙是外生固定的（B 的录像），所以 ego 只能被动接受；闭环承认间隙是 ego 与 B 交互**协商**的产物（ego 的动作改变 B 的反应）。分支规划 + 闭环仿真因此能表达"试探性前压 → 观察 B 反应 → 按反应分支"——这正是人类司机并线时做的事。这也再次说明 §U1.2 的核心：MPDM 的价值在闭环交互建模，开环仿真会丢掉分支规划最关键的能力。
复杂度：MPDM 为什么不可扩展¶
MPDM 的双重循环里，外层是 ego 策略（\(|\Pi_{\text{ego}}|\) 个），内层要枚举他车策略组合。如果场景里有 \(n\) 辆相关他车、每辆 \(|\Pi_{\text{other}}|\) 个策略，他车的联合策略组合数是 \(|\Pi_{\text{other}}|^{n}\)。于是总仿真次数：
举例：\(|\Pi_{\text{ego}}|=5\)、\(|\Pi_{\text{other}}|=3\)、\(n=3\) 辆车 → \(5\times3^3=135\) 次前向仿真；\(n=5\) 辆 → \(5\times3^5=1215\) 次。指数项 \(|\Pi_{\text{other}}|^{n}\) 是杀手——他车一多就炸。这正是 EUDM（§U1.3）要解决的问题：用 DCP-Tree 把"组合"换成"序列"、用 CFB 只在危险处分支，把指数压成多项式。
对比性思维：MPDM 的"组合"枚举 vs EUDM 的"序列 + 筛选"。MPDM 对他车策略做**笛卡尔积**（所有组合），复杂度 \(|\Pi_{\text{other}}|^n\) 随车数指数爆炸；EUDM 不枚举组合，而是展开 ego 自己的**策略序列**（一条时间轴上的策略链）并只在危险交互处分支，复杂度降到 \(O(\text{深度}\times\text{宽度})\)。一句话：MPDM 的代价在"他车组合"，EUDM 把注意力转回"ego 自己的决策序列 + 少数关键交互"。
语义策略集 \(\Pi\) 怎么设计¶
MPDM/EUDM 的可解释性与质量，很大程度取决于语义策略集 \(\Pi\) 设计得好不好。这是工程落地的关键一步，原则如下。
覆盖性 vs 紧凑性的权衡：\(\Pi\) 要**覆盖**场景里所有定性不同的合理行为（漏了某类行为，分支规划就永远做不出它——§专题八的"有限策略集"次优来源），又要**紧凑**（策略越多复杂度越高、\(O(|\Pi|^n)\) 越爆炸）。常见做法是按"横向 \(\times\) 纵向"组织：横向 {车道保持, 左变道, 右变道}、纵向 {加速, 匀速, 减速, 停车}，组合出一个不大不小的语义集。
与道路结构绑定：策略集应随场景结构变化——高速路用 {保持, 左变道, 右变道}；路口用 {直行, 左转, 右转, 让行, 抢行}；环岛用 {进入, 等待, 跟随}。把策略集设计成"场景类型 → 策略集"的查表，比一套策略走天下更贴合。
他车策略集 vs ego 策略集：ego 的 \(\Pi_{\text{ego}}\) 是"ego 能执行的动作"（受 ego 动力学约束）；他车的 \(\Pi_{\text{other}}\) 是"他车可能的意图"（用于分支与前向仿真）。两者可以不同——他车意图集常更粗（让 / 不让足矣），ego 动作集可更细（要落成轨迹）。
粒度的工程取舍：策略太粗（如只有"走 / 停"）→ 表达力不足、行为生硬；太细（如把加速度连续离散成 20 档）→ 失去"语义"意义、复杂度爆炸、且退化成连续优化（该用 multi-stage NMPC）。好的粒度是"每个策略对应一个人能命名的定性行为"。
对比性思维：策略集设计是"用领域知识换搜索空间"的具体操作。§U1.7 说分支规划"知识密集"——这个知识主要就注入在策略集里。策略集设计得好（覆盖关键行为、粒度恰当），分支规划就能用很小的 \(|\Pi|\) 实时给出可解释的好决策；设计得差（漏行为或过细），要么够不到最优、要么爆炸。这也是分支规划区别于 MCTS 的地方：MCTS 在原始动作空间里搜索（不需设计策略集，但要大量搜索），分支规划在人工设计的语义策略集里枚举（不搜索，但依赖策略集质量）。一句话：分支规划把"该考虑哪些行为"的知识前置进了策略集设计——这一步做好，是用好 MPDM/EUDM 的前提。
⚠️ 本节常见陷阱¶
💡 概念误区：以为 MPDM 在预测他车的精确轨迹 - 新手想法："MPDM 内部肯定有个轨迹预测器，预测他车未来位置。" - 现象 / 后果：试图给 MPDM 配一个高精度轨迹预测网络，发现接口对不上、且失去了可解释性。 - 根本原因：MPDM 预测的是**离散策略的概率**（他车在执行哪个语义策略），轨迹是用 IDM/MOBIL 在前向仿真里"跑"出来的，不是预测出来的。 - 正确做法：把预测器的输出对接成"他车各策略的概率 \(P(\pi_{\text{other}})\)"，而非位置序列。检验方法：确认你的 \(\sum_{\pi}P(\pi)=1\) 且策略集是离散语义集。
🧠 思维陷阱：用开环（非交互）仿真评估策略 - 新手想法："把他车当成按预测轨迹走的录像，ego 在上面避让就行，省得做闭环。" - 现象 / 后果：评估出的 ego 策略在真实交互中表现差——因为它没考虑"ego 的动作会改变他车的反应"。典型如并线：开环仿真里后车永远匀速，ego 以为挤不进去；闭环里后车会减速让行。 - 根本原因：开环仿真丢掉了**交互**，等于假设他车对 ego 毫无反应。MPDM 的价值恰恰在闭环前向仿真。 - 正确做法：前向仿真里让 ego 和他车都按各自策略用 IDM/MOBIL 相互响应。检验方法：在并线场景跑，开环会 frozen（挤不进），闭环应能在后车让行的场景下并入。
💡 编程陷阱：IDM 的期望间距 \(s^*\) 忘了取非负 / 漏了相对速度项 - 现象 / 后果：跟车仿真里出现负间距、车辆穿模，或前车减速时本车不减速、追尾。 - 错误代码：
s_star = s0 + v*T（漏了 \(\frac{v\Delta v}{2\sqrt{ab}}\) 相对速度项），或不做max(0, ...)。 - 正确写法：s_star = s0 + max(0.0, v*T + v*dv/(2*sqrt(a*b)))，其中dv = v - v_lead。 - 根本原因：相对速度项是 IDM 的"预判刹车"机制（前车更慢时提前拉大期望间距）；漏了它跟车会变得迟钝、易追尾。\(\max(0,\cdot)\) 防止接近速度为负（本车更慢）时期望间距被算成负数。 - 检验方法：让前车急刹，本车应平滑减速且间距始终 \(\ge s_0\)。
练习¶
- [A 型·实现 IDM] 实现 IDM 单车道跟车：一条直道、前车按给定速度曲线（含一次急刹）行驶，本车用 IDM 跟随。画速度 / 间距曲线，验证间距始终 \(\ge s_0\)、急刹时本车平滑减速。扫 \(T\)（车头时距）观察跟车松紧。
- [A 型·实现 MPDM] 在一个简化并线场景里实现最小 MPDM：ego 有 {加速并入, 减速等待} 两策略，主道后车有 {让行, 不让} 两策略，用 IDM 做 3s 闭环前向仿真，按后车策略概率加权选 ego 策略。验证：后车大概率让行时 ego 选并入，大概率不让时 ego 选等待。
- [B 型·复杂度] 给定 \(|\Pi_{\text{ego}}|=5\)、\(|\Pi_{\text{other}}|=4\)，分别算 \(n=2,4,6\) 辆他车时 MPDM 的前向仿真次数。若每次仿真 1ms，哪个 \(n\) 开始超过 100ms 的实时预算？这说明了什么工程约束？
- [思考题] MOBIL 的礼让系数 \(p\) 从 0 调到 1，换道行为会怎么变？把它和"博弈规划里对手是否合作"联系起来——\(p\) 在某种意义上编码了什么样的交互假设？
§U1.3 EUDM：引导分支 ⭐⭐⭐¶
动机：把 MPDM 的指数爆炸压回实时¶
§U1.2 末尾看到 MPDM 的复杂度 \(O(|\Pi_{\text{ego}}|\cdot|\Pi_{\text{other}}|^n)\) 随他车数 \(n\) 指数爆炸——3 辆车已上百次仿真、5 辆车上千次，跑不到几十毫秒的实时预算。EUDM（Efficient Uncertainty-aware Decision-making，高效不确定性感知决策，Lu Zhang*、Wenchao Ding* 等, HKUST, ICRA 2020） 用两个机制把它压回实时，同时保持 MPDM 的策略枚举思想。它把决策形式化为一个 POMDP（他车意图是隐变量），但**不直接求解** POMDP（那会爆炸），而是用领域知识"引导分支"。
两个核心机制：DCP-Tree（领域专属闭环策略树）解决"ego 策略空间怎么展开"，CFB（条件聚焦分支）解决"他车意图怎么有选择地枚举"。
反面：不引导分支会怎样¶
EUDM 把决策形式化为 POMDP（他车意图是隐状态），但**刻意不直接求解** POMDP。看看两条朴素路线各自怎么崩，就懂了"引导分支"的必要性。
朴素路线一：精确求解 POMDP。把它当标准 POMDP 用值迭代 / 点基方法（PBVI、SARSOP）求解——理论最优，但 POMDP 的求解复杂度随状态空间、观测空间、时域**指数爆炸**。自驾的状态（多车连续位姿）+ 观测（连续传感）+ 长时域，规模远超精确 POMDP 求解器能实时处理的量级。结果：跑不到实时，根本上车。
朴素路线二：MPDM 式全组合枚举。退而用 MPDM 的离散策略枚举——但 §U1.2 已算过，他车策略组合 \(|\Pi_{\text{other}}|^n\) 随车数指数爆炸，且若还要展开 ego 的多步策略序列，ego 侧也是 \(|\Pi_{\text{ego}}|^{d}\) 指数。两个指数相乘，几辆车 + 几步就超时。
EUDM 的"引导"出在哪：它在 action space（ego 动作）和 observation/intention space（他车意图）两个空间都用领域先验引导分支——DCP-Tree 引导 action 空间（一周期一次切换），CFB 引导 observation/intention 空间（只对危险交互分支）。"引导"二字的含义就是：不盲目展开两个空间的全部组合，而是用专家知识只展开"值得展开"的少数分支。这把"精确 POMDP 的指数"和"全组合枚举的指数"双双压回多项式——既保留 POMDP 的不确定性建模、又获得实时性。
对比性思维：EUDM 不是'更快的 POMDP 求解器',而是'用领域先验做了大幅剪枝的近似 POMDP'。它没有改进 POMDP 的通用求解算法（那是 U4 的方向），而是承认"通用求解必爆炸",转而用驾驶领域的强先验（语义策略、一周期一次切换、危险交互筛选）把问题裁剪到一个可实时的子集上。这是"用领域知识换通用性"的典型——放弃了对任意 POMDP 的最优性，换来了对驾驶这个特定 POMDP 的实时近似解。
机制一：DCP-Tree（Domain-specific Closed-loop Policy Tree）¶
MPDM 在**单个时刻**对 ego 选一个策略。但真实驾驶是**策略序列**——"先跟车 1.5s，再左变道"。如果在每个时间节点都允许 ego 切换到任意策略，策略序列数仍然指数爆炸（\(|\Pi_{\text{ego}}|^{\text{深度}}\)）。
DCP-Tree 用一条领域先验大幅剪枝：在一个规划周期内，ego 最多切换一次策略。理由很实在——如果真需要复杂的策略变化（如"跟车→变道→再跟车"），可以靠**高频重规划**分多个周期实现，单个周期内不必考虑多次切换。
于是 DCP-Tree 的结构是：从当前正在执行的策略出发，每个节点要么"保持当前策略"，要么"切换到另一个策略（且之后保持）"。EUDM 用 8s 的规划时域、每 2s 一个策略更新节点，于是树深 4。这把单周期的 ego 策略序列数从 \(|\Pi_{\text{ego}}|^4\) 压到线性级别（每条序列最多一次切换）。
本质洞察：DCP-Tree 用"一周期一次切换"把指数压成线性。关键观察是"决策频率"与"策略复杂度"可以解耦——你不需要在一个规划周期里规划出全部复杂机动，因为滚动重规划（每几十毫秒一次）会不断给你新机会切换。这是一个典型的"用时间换空间"的工程智慧：把"一次想清楚所有切换"换成"每周期只想一次切换 + 高频重规划"。它和 MPC 滚动时域的哲学一脉相承——不求一步到位，求每步够好且能滚动修正。
机制二：CFB（Conditional Focused Branching，条件聚焦分支）¶
DCP-Tree 解决了 ego 侧。他车侧呢？MPDM 对所有他车的所有策略组合枚举（那个 \(|\Pi_{\text{other}}|^n\) 爆炸项）。CFB 的洞察：绝大多数他车与 ego 的当前决策无关，不值得为它们分支。
CFB 对每条 ego 策略序列，只在"危险交互"处分支他车意图，其余他车一律用其**最可能**策略（不分支）。"危险交互"指：在这条 ego 策略下，某个他车的不同意图（让 / 不让）会显著改变 ego 的安全性或代价。CFB 通过一个初步的（用最可能意图的）前向仿真识别出哪些他车是"关键交互车"，只对这少数几辆分支。
于是分支数从"所有他车的组合"\(|\Pi_{\text{other}}|^n\) 压到"少数关键交互车的组合"，通常 3–8 个分支。
对比性思维：MPDM 的"无差别枚举" vs CFB 的"危险度筛选"。MPDM 平等对待每辆他车的每个策略（笛卡尔积）；CFB 先问"哪些他车的意图真的会影响我"，只为这些分支。这和 U3 的 IRA"把风险预算分给紧约束"、U2 故障排查"多障碍 CBF 只激活最近几个"是同一种工程思维——把有限的计算 / 预算花在真正关键的地方。CFB 之于分支数，正如 IRA 之于风险预算。
DCP-Tree × CFB：两个机制如何联合压复杂度¶
DCP-Tree 压 ego 侧、CFB 压他车侧，两者相乘才得到 EUDM 的最终复杂度。把账算清，能看到 EUDM 相对 MPDM 的指数级压缩到底来自哪。
MPDM 的基线：\(O(|\Pi_{\text{ego}}|\cdot|\Pi_{\text{other}}|^{n})\)——ego 单时刻一个策略（\(|\Pi_{\text{ego}}|\)）\(\times\) 全部他车意图组合（\(|\Pi_{\text{other}}|^{n}\)，\(n\) 是相关他车数，指数项）。
DCP-Tree 对 ego 侧的处理：把"单时刻选一个策略"升级为"策略序列"（看得更远），但用"一周期\(\le\)1次切换"把序列数从 \(|\Pi_{\text{ego}}|^{d}\)（\(d\) = 策略节点数 / 树深）压到**线性级**——序列要么全程不变、要么只在某处切一次。于是 ego 侧从"指数 \(|\Pi_{\text{ego}}|^{d}\)"降到"\(O(d\cdot|\Pi_{\text{ego}}|)\)"。
CFB 对他车侧的处理：把"全部他车的意图组合 \(|\Pi_{\text{other}}|^{n}\)"压到"只对关键交互车的组合 \(|\Pi_{\text{other}}|^{n_{\text{key}}}\)"（\(n_{\text{key}}=1\sim2\ll n\)），其余他车用最可能意图。指数的**指数从 \(n\) 降到 \(n_{\text{key}}\)**——这是最关键的一刀（因为 \(n\) 是真实场景里最大的爆炸源）。
联合：EUDM 总复杂度 \(\approx O\big(\underbrace{d\cdot|\Pi_{\text{ego}}|}_{\text{DCP-Tree}}\times\underbrace{|\Pi_{\text{other}}|^{n_{\text{key}}}}_{\text{CFB}}\big)\)。对比 MPDM 的 \(O(|\Pi_{\text{ego}}|\cdot|\Pi_{\text{other}}|^{n})\)： - ego 侧：从（潜在的）\(|\Pi_{\text{ego}}|^d\) 指数 → \(d\cdot|\Pi_{\text{ego}}|\) 线性（DCP-Tree 省）； - 他车侧：从 \(|\Pi_{\text{other}}|^{n}\) → \(|\Pi_{\text{other}}|^{n_{\text{key}}}\)（CFB 省，把指数的指数从 \(n\) 砍到 \(n_{\text{key}}\)）。
数量级体感：\(n=5\) 辆车、\(|\Pi_{\text{other}}|=3\) 时，MPDM 的他车组合是 \(3^5=243\)；CFB 取 \(n_{\text{key}}=2\) 则降到 \(3^2=9\)——27 倍压缩，且这个压缩比随 \(n\) 增大而急剧拉大。正是这两刀，让分支规划从"几辆车就超时"变成"50–100ms 内可解"。
对比性思维：DCP-Tree 砍"底数的幂"、CFB 砍"指数本身"。两个机制压的是复杂度公式的不同部位——DCP-Tree 把 ego 策略序列从幂次（\(|\Pi_{\text{ego}}|^d\)）压成线性（靠"一周期一次切换"这条结构约束）；CFB 把他车组合的指数 \(n\) 砍成 \(n_{\text{key}}\)（靠"只分支关键车"这条危险度筛选）。砍指数（CFB）比砍底数（DCP-Tree）收益更大，因为指数 \(n\) 是爆炸的主因——这也是为什么 CFB 是 EUDM 实时性的关键。记住这个"砍指数优先于砍底数"的直觉，你在任何组合优化里都知道该先攻哪里。
EUDM 的完整流程¶
把两个机制串起来，EUDM 一个规划周期做的事：
1. 展开 DCP-Tree：从当前策略出发，生成 ego 候选策略序列（每序列≤1次切换，树深4）
2. 对每条 ego 策略序列：
a. 用所有他车的"最可能意图"做一次前向仿真 → 识别关键交互车（CFB）
b. 只对关键交互车枚举意图（让/不让/...），生成少数分支场景
c. 每个分支场景做闭环前向仿真，算代价
d. 按场景概率加权 → 该策略序列的期望代价
3. 选期望代价最小的 ego 策略序列，输出其首段策略 + 粗轨迹参考
4. 滚动重规划
输出是**最优 ego 策略序列 + 对应的粗轨迹参考**——注意 EUDM 是**行为决策层**，它定"做什么策略"，具体的光滑轨迹由下游的运动规划层（SSC，§U1.4）生成。
多视角理解：EUDM 把 POMDP "引导"成可解问题的三种看法 - POMDP 视角：他车意图是隐状态，EUDM 是在 belief 上做决策。但它不解完整 POMDP，而是用领域先验把"动作空间"（DCP-Tree）和"观测 / 意图分支"（CFB）都裁剪到极小。 - 搜索视角：DCP-Tree 是一棵宽度固定、深度浅、靠领域规则（一周期一次切换）剪枝的策略树——和 MCTS 的自适应树形成鲜明对比（§U1.7）。 - 工程视角：EUDM 的全部努力是"在保持枚举式可解释性的前提下，把仿真次数从指数压到几十次"，从而在 50–100ms 内完成——这是它能上实车的关键。
⚠️ 本节常见陷阱¶
💡 概念误区：以为 DCP-Tree 是在枚举他车策略 - 新手想法："DCP-Tree 的分支应该是他车的不同意图吧？" - 现象 / 后果：把 DCP-Tree 和 CFB 的职责搞混，实现出一棵既展开 ego 策略又展开他车意图的混合树，结构混乱。 - 根本原因：DCP-Tree 展开的是 ego 自己的策略序列（时间轴上的策略链）；他车意图的分支是 CFB 干的事。两者职责分离：DCP-Tree 管"我怎么做"，CFB 管"他们可能怎么做"。 - 正确做法：DCP-Tree 的节点 = ego 策略切换点；CFB 的分支 = 关键交互车的意图。检验方法：画出树，纵向（深度）应是 ego 策略序列、横向（在危险点）才是他车意图分支。
🧠 思维陷阱：以为"一周期一次切换"会让 EUDM 错过复杂机动 - 新手想法："只允许一次切换，那'跟车→变道→回正'这种需要多次切换的机动不就做不出来了？" - 现象 / 后果：误以为 EUDM 表达能力受限，转而设计允许多次切换的树（复杂度又爆炸）。 - 根本原因：忽略了**滚动重规划**。单周期一次切换 + 每几十毫秒重规划 = 多个周期串起来可以实现任意复杂的策略序列。表达能力没丢，只是分摊到了时间轴上。 - 正确做法：相信滚动时域——单周期只规划到下一次切换，复杂机动由连续多个周期自然涌现。
练习¶
- [A 型·DCP-Tree] 给定 ego 策略集 {跟车, 左变道, 右变道}、时域 8s、每 2s 一节点（树深 4）、约束"一周期\(\le\)1次切换"。枚举所有合法的 ego 策略序列，数一数有多少条。对比"允许任意切换"时的 \(3^4=81\) 条，CFB/DCP 剪掉了多少？
- [B 型·EUDM 精读] 精读 EUDM/EPSILON 的
eudm_planner/核心代码，画出"DCP-Tree 展开 → CFB 识别关键车 → 前向仿真 → 代价加权 → 策略选择"的数据流图，标注每一步的输入输出。 - [思考题] CFB 靠"最可能意图的初步仿真"识别关键交互车。如果某个他车的真实意图恰好是小概率的危险意图（初步仿真没把它当关键车），会发生什么？这暴露了 CFB 的什么假设？（提示：联系 §U1.5 MARC 为何要改进分支策略）
§U1.4 EPSILON：从行为决策到完整系统 ⭐⭐⭐¶
动机：EUDM 只给"策略"，谁来给"轨迹"？¶
§U1.3 强调 EUDM 是**行为决策层**——它输出"最优 ego 策略序列 + 粗轨迹参考"，但不给可执行的光滑轨迹。一个能上车的系统还需要**运动规划层**把策略落成满足动力学、避障、舒适的轨迹。EPSILON（Efficient Planning System for Automated Vehicles in Highly Interactive Environments，Wenchao Ding*、Lu Zhang* 等, HKUST, IEEE T-RO 2021） 就是把 EUDM（行为层）与 SSC（运动层）拼成的完整、开源、实车验证的分层系统。
架构：行为决策层 + 运动规划层¶
EPSILON 是一个两层结构：
环境理解（感知/预测/定位）
│ 他车状态 + 意图先验
▼
┌─────────────────────────────────────┐
│ 行为决策层（EUDM） │
│ POMDP 形式化 + 引导分支(DCP-Tree+CFB) │
│ 输出：最优 ego 策略序列 + 粗轨迹参考 │
└─────────────────────────────────────┘
│ 选定策略下的语义意图
▼
┌─────────────────────────────────────┐
│ 运动规划层（SSC） │
│ 构造时空语义走廊（凸多面体序列） │
│ 走廊内 QP 求光滑轨迹 │
└─────────────────────────────────────┘
│ 光滑可执行轨迹
▼
控制 / 执行
为什么要分层：行为决策（离散、组合、博弈味重）和运动规划（连续、光滑、几何约束）是两类不同的问题，强行塞进一个优化里又非凸又难解。分层让行为层用枚举式策略树处理"离散意图"，运动层用凸优化处理"连续轨迹"——各用最适合的工具。这与 U2 §U2.5 "MPC 给方向、CBF 给护栏"、腿足栈"MPC 给质心轨迹、WBC 给关节力矩"是同一种分层哲学。
SSC：时空语义走廊（Spatio-temporal Semantic Corridor）¶
SSC（Ding 等, IEEE RA-L 2019）是 EPSILON 的运动规划层。在 EUDM 选定的策略下（比如"在他车后方并入"），SSC 把"该策略允许 ego 走的时空区域"编码成一串**凸多面体**（在位置-时间空间里），即"语义走廊"。然后在走廊内解一个 QP 求光滑轨迹（位置 / 速度 / 加速度连续、在走廊内、满足动力学）。
直觉：策略（"在 A 车后 B 车前并入"）唯一确定了一条时空"通道"，把这个通道用凸多面体表示，轨迹优化就变成一个凸 QP——快而可靠。这和你在其他方向见过的"safe flight corridor"（无人机）、"driving corridor"是同一类思想：先用离散决策框定一个凸的可行通道，再在通道内做凸优化。
本质洞察：EPSILON = "离散决策定通道 + 连续优化填轨迹"。分支规划（EUDM）在离散策略空间里选出"走哪个时空通道"，SSC 把这个通道凸化成走廊，QP 在凸走廊内求最优光滑轨迹。难的非凸部分（该走哪条通道、避哪辆车的哪一侧）交给离散的策略枚举；凸的部分（通道内怎么走最光滑）交给 QP。这是处理"组合 + 连续"混合问题的经典解耦套路——也解释了为什么纯连续优化做交互式驾驶会陷入局部最优（它无法跨越"绕左 vs 绕右"这种离散选择，而分支 / 拓扑天然能）。
为什么纯连续优化做交互式驾驶会陷入局部最优¶
EPSILON 的分层（离散选通道 + 连续填轨迹）不只是"工程方便",而是**绕开纯连续优化的根本困难**——理解这点，才懂分层 / 分支的必要性。
同伦类（homotopy class）的障碍：在有动态障碍的环境里，"从障碍左侧绕"和"从障碍右侧绕"是两条**拓扑上不连续**的轨迹——你无法在不穿过障碍的前提下，把"绕左"的轨迹连续形变成"绕右"。它们属于不同的**同伦类**。纯连续轨迹优化（一个 NLP / QP 从某初值出发做梯度下降）只能在**当前同伦类内**找局部最优——它跨不过"障碍"这道墙到另一类去。于是：若初值在"绕左"类、但全局最优在"绕右"类，纯连续优化会卡在"绕左"的局部最优，永远找不到更好的"绕右"。
这正是 frozen / 次优的一个深层来源：交互式驾驶的关键决策（绕障碍哪侧、在他车前还是后、让还是抢）本质是**离散的同伦 / 拓扑选择**，而纯连续优化对这种离散选择无能为力（它只会在初值所在的那一类里优化）。
分支 / 分层如何破解： - 分支规划：显式枚举不同的离散选择（绕左 / 绕右、前 / 后、让 / 抢）——每个选择对应一个同伦类，为每类各优化一条轨迹，再比较。这正是 §前沿 Topology-driven MPC 的核心（按拓扑等价类并行优化多条轨迹择优）。 - EPSILON 分层：行为层（离散策略枚举）负责选同伦类（哪个通道），运动层（SSC 凸走廊 + QP）在选定的**单一**同伦类内做连续优化——此时通道已凸、QP 无局部最优之虞。
本质洞察：交互式驾驶的难,一半在"离散的拓扑选择"、一半在"连续的轨迹优化",必须分开打。纯连续优化擅长后者（凸通道内找光滑轨迹）、却败于前者（跨不过障碍选同伦类）；纯离散枚举擅长前者、却给不出光滑可执行轨迹。EPSILON 的分层 = 离散枚举选同伦类（分支 / 行为层）+ 连续优化填类内轨迹（SSC / 运动层），各用所长。这也解释了为什么"端到端一个连续优化解决交互式驾驶"很难——它没有显式处理同伦类选择的机制，容易卡在初值所在类的局部最优。分支 / 分层不是可选的工程技巧，而是**应对离散拓扑选择的必需结构**。
SSC 走廊构造的三步（从语义策略到凸走廊）¶
SSC 把"选定策略"落成凸走廊，概念上分三步：
- 语义立方体（semantic cube）划分：在"位置 \(\times\) 时间"空间里，根据选定策略与各障碍的时空占据，把 ego 可走的区域切成一串**语义立方体**——每个立方体是一段时间内 ego 允许占据的位置区间，且明确"在哪辆车的前 / 后、哪条车道"。策略（如"在 A 车后、B 车前并入"）唯一确定了这串立方体的语义。
- 立方体扩张为凸走廊：把相邻语义立方体在时空上连成一条**凸多面体序列**（走廊）。凸性是关键——每段走廊是凸的，整条轨迹只要逐段落在对应走廊内，就自动满足该策略的时空约束。
- 走廊内 QP：在走廊约束下，最小化轨迹的光滑性代价（jerk / 加速度）+ 跟踪代价，解一个 QP。因约束（走廊是凸多面体）和代价（二次）都凸，QP 快而可靠。
直觉：策略把"非凸的避障问题"（绕 A 的左还是右、在 B 前还是后）切成了"一个确定的凸通道",剩下的"通道内怎么走最光滑"是凸 QP。这正是 §U1.4 本质洞察"离散决策定通道 + 连续优化填轨迹"的具体机制——SSC 是那个"定通道 + 填轨迹"的运动层实现。
对比性思维：SSC 的"语义走廊" vs 纯几何走廊。无人机的 safe-flight-corridor 是纯几何的（避开静态障碍的自由空间凸分解）；SSC 的走廊带**语义 + 时间**——它不只说"哪里是空的",而是说"按这个策略、在这辆车的前 / 后、这段时间该在哪"。多了语义和时间维，才能表达"在动态交互中按某策略通行"。这是把"静态几何避障"推广到"动态交互式通行"的关键一步。
ego-centric belief：只对关心的车维护信念¶
EPSILON 在 EUDM 基础上加了一个重要的工程优化：ego-centric belief update——不对场景里所有车维护完整的意图信念，只对**ego 当前决策真正关心的交互车**维护 belief。这和 CFB"只对关键交互车分支"一脉相承：信念维护也是有成本的，把它聚焦在关键车上。这进一步压低了在线计算，使系统能在实车的城市密集车流中实时运行。
EPSILON 还引入了一个**带安全机制的驾驶员模型**，来对冲 IDM/MOBIL 这类先验模型的不完美（真实他车未必严格按 IDM 跟车）——当先验模型与观测明显不符时，安全机制接管，避免因模型失配导致危险。
开源与工程意义¶
EPSILON 开源于 HKUST-Aerial-Robotics/EPSILON（C++/ROS，GPLv3），是少数把"行为决策 + 运动规划"完整闭环、且在真实城市车流验证过的开源交互式规划系统之一。它的价值不仅是算法，更是**一个可精读的完整工程参考**——从语义地图、意图先验、DCP-Tree/CFB、到 SSC 走廊 QP 的全链路。
对比性思维：EPSILON 的分层 vs 端到端学习的单体。近年也有端到端（一个网络直接出轨迹）的交互式规划。EPSILON 代表的分层枚举路线，强在可解释、可验证、可调试（每个决策都有语义、每条约束都看得见），弱在依赖手工设计的策略集与先验模型；端到端强在能从数据里学到复杂交互模式，弱在黑箱、难验证、长尾不可控。两条路线并非互斥——可以用学习改进 EPSILON 的意图预测 / 分支点选择（§U1.5 的 Neural 化方向、§前沿），同时保留分层的安全可控骨架。
⚠️ 本节常见陷阱¶
💡 概念误区：以为 EPSILON 是一个端到端的单一优化 - 新手想法："EPSILON 应该是把所有东西塞进一个大优化问题求解。" - 现象 / 后果：试图写一个"既选策略又出轨迹"的联合优化，发现又非凸又难解、跑不动。 - 根本原因：EPSILON 的关键正是**分层解耦**——行为层（离散枚举）和运动层（凸 QP）分开。把它们合并会丢掉解耦带来的可解性。 - 正确做法：理解两层的接口——行为层输出"语义策略 / 意图"，运动层据此构造凸走廊再 QP。检验方法：能清楚说出"哪一层处理离散、哪一层处理连续"。
🧠 思维陷阱：以为给所有他车都维护信念才"严谨" - 新手想法："只对部分车维护 belief 不够严谨，应该对全场景所有车都建信念。" - 现象 / 后果：信念维护与分支计算量随车数膨胀，实时性崩溃。 - 根本原因：忽略了**ego-centric** 的工程洞察——绝大多数车与 ego 当前决策无关，为它们维护信念是浪费。严谨性应服务于"对 ego 决策有影响的不确定性"，而非无差别覆盖。 - 正确做法：像 CFB 一样聚焦关键交互车。检验方法：去掉远处无关车的 belief，决策质量应几乎不变、计算量大降。
练习¶
- [A 型·EPSILON 运行] 按
HKUST-Aerial-Robotics/EPSILON的 README 搭建 ROS 环境，在提供的城市场景运行完整系统，用 rqt 观察 EUDM 的决策频率与 SSC 的走廊生成。逐步增加他车数量，记录计算时间增长曲线。 - [A 型·SSC 直觉] 在一个简单的"在前车后方并入"场景里，手工画出该策略对应的时空语义走廊（位置-时间空间的凸多面体序列），并说明为什么在走廊内做 QP 是凸的。
- [思考题] EPSILON 用"带安全机制的驾驶员模型"对冲 IDM/MOBIL 的失配。这本质上是在处理 §U0 的哪一类不确定性（认知 / 偶然 / 模型）？它和 U2 的"鲁棒对最坏扰动留余量"在思想上有什么相通？
§U1.5 MARC：动态分支点 + 风险感知 ⭐⭐⭐⭐¶
动机：固定分支点的两个毛病¶
MPDM/EUDM/EPSILON 都在**固定时刻**分支（如 EUDM 每 2s 一个策略节点）。§U1.1 已指出 \(t_{\text{branch}}\) 是最关键的旋钮，固定它有两个毛病：
- 分早了浪费 / 分晚了危险：真实场景里"意图何时揭示"是变化的——有时他车一秒内就表态（该早分支），有时要好几秒才看清（晚分支才合理）。固定分支点要么过早分叉（共享干太短、不够稳）、要么过晚（共享干太长、过保守）。
- 只看期望、不看尾部风险：MPDM/EUDM 按场景概率加权**期望**代价。但安全关键场景里，你往往更怕"小概率但灾难性"的尾部（他车突然抢行导致碰撞），期望代价会把这个尾部平均掉。
MARC（Multipolicy and Risk-aware Contingency Planning，Tong Li、Lu Zhang 等, HKUST, IEEE RA-L 2023） 针对这两点给出两项关键进化。
进化一：场景级 divergence 动态决定分支点¶
MARC 不在固定时刻分支，而是观察**多个场景的轨迹何时开始显著分叉**，在那里动态设分支点。度量"分叉程度"用 Wasserstein 距离——比较不同场景下 ego（或交互）轨迹分布的差异，当差异超过阈值（轨迹真的开始分开了），就在那一刻分支。
直觉：分支点应该放在"信息真正揭示、各场景不得不分开"的时刻，而不是人为固定的钟点。两个场景在前 3s 的最优轨迹几乎重合（无论他车让不让，ego 前 3s 都该这么走），那共享干就该到 3s；如果 1s 就分开了，共享干就只到 1s。让数据决定分支点，而非先验固定。
本质洞察：MARC 把分支点从"超参数"变成"由场景分叉自动涌现的量"。回顾 §U1.1——\(t_{\text{branch}}\) 是最关键旋钮，理想值是"信息揭示时刻"。MARC 的洞察是：信息揭示时刻**可观测**——它就是"各场景最优轨迹开始显著分叉"的时刻（在那之前，不同未来对应的最优当前动作是一样的，所以还不必分；之后才必须分）。用 Wasserstein 距离量化"分叉"，分支点就从手调超参变成了自适应量。这呼应 U3 进阶里"递归可行性 / 分布距离"的思想，也是"让结构由数据涌现而非人为设定"的一般工程审美。
动态分支点的数值示意¶
用一个 1D 示意把"轨迹分叉 → 动态分支点"做实。两意图下 ego 的最优位置轨迹：意图 A（让行）在 1.5s 后减速，意图 B（通过）在 1.5s 后加速；之前两者最优动作相同（意图不可区分），轨迹重合。对确定性轨迹，1D Wasserstein 距离就是位置差 \(W(t)=|s_A(t)-s_B(t)|\)：
| \(t\)(s) | \(s_A\)（让） | \(s_B\)（通） | \(W(t)=\lvert s_A-s_B\rvert\) |
|---|---|---|---|
| 0.0–1.5 | 重合 | 重合 | 0.000 |
| 2.0 | 15.50 | 16.38 | 0.875 |
| 2.5 | 18.50 | 21.12 | 2.625 |
| 3.0 | 21.00 | 26.25 | 5.250 |
| 3.5 | 23.00 | 31.75 | 8.750 |
前 1.5s 两意图轨迹完全重合（\(W=0\)）——此时无论让 / 通，ego 的最优动作都一样，共享干无损。1.5s 后开始分叉，\(W(t)\) 单调增长。取分叉阈值 \(\tau=1.0\)，\(W(t)\) 在 \(t=2.5\)s 首次超阈值——动态分支点 = 2.5s。
对比固定分支点（如 EUDM 每 2s 在 2.0s 处分叉）：固定分支在 2.0s 分，但此时 \(W=0.875<\tau\)，轨迹还没真正分开，分早了（共享干本可再长一点、更稳）；而若某场景 1s 就分叉，固定的 2s 又分晚了。动态分支让分支点**自适应**轨迹实际分叉的节奏——这正是进阶专题十四"\(t_{\text{branch}}^*=\tau^*\)（信息揭示时刻）"的可操作近似：用可观测的"轨迹分叉"代理不可观测的"信息揭示"。
本质洞察：动态分支点把"共享干长度"交给数据决定。这个 1D 示意里，\(W(t)=0\) 的区间（0–1.5s）就是"共享无损区"——延长共享干到此处末端不损失任何最优性；\(W(t)\) 一旦增长，继续共享就开始有损。MARC 用阈值 \(\tau\) 在"无损区结束、有损区开始"的交界处分叉。一句话：固定分支点是猜共享干该多长，动态分支点是测出来——测的依据就是"各意图最优轨迹何时开始分开"。
进化二：CVaR 风险感知的双层优化¶
MARC 把"期望代价"换成 CVaR 风险度量，并组织成**双层优化**：
- 上层：枚举 ego 策略（沿用 MPDM/EUDM 的策略枚举）。
- 下层：对每个 ego 策略，不是算场景概率加权的**期望**代价，而是算 CVaR\(_\alpha\)——最坏 \((1-\alpha)\) 尾部场景的平均代价。
回顾 U0 §3 / U3 进阶十：CVaR\(_\alpha\) 关注"违反 / 出事时有多糟"，而非"多大概率出事"。在分支规划里用 CVaR 意味着：选 ego 策略时，不仅看它在各场景的期望表现，更看它在**最坏那几个场景**下的表现。\(\alpha\) 是风险旋钮——\(\alpha\to 0\) 趋近期望（风险中性）、\(\alpha\to 1\) 趋近最坏情况（极度保守）。
这样选出的策略对"小概率灾难场景"更稳健——比如它会倾向于选"即使他车抢行也能安全"的策略，哪怕该策略在"他车让行"的大概率场景下效率略低。
多视角理解：MARC 的三层"为什么更好" - 分支点视角：动态分支（Wasserstein divergence）让共享干长度自适应信息揭示时刻——不再早分浪费、晚分危险。 - 风险视角：CVaR 替代期望，让策略选择对尾部灾难敏感——治好"期望把罕见碰撞平均掉"的毛病。 - 输出视角：MARC 的运动规划器输出"名义轨迹 + 多条延迟分支"（树形），而非传统的"选中某个场景的单一最优"——保留了对所有未来的兼容性直到执行。
CVaR 双层优化怎么解¶
MARC 的"上层枚举 ego 策略、下层 CVaR"双层结构，求解上有讲究。
下层（给定 ego 策略，算 CVaR）：对选定的 ego 策略，各场景 \(\omega_k\) 给出代价 \(L_k\)（来自该策略 + 场景下的轨迹评估）与概率 \(P(\omega_k)\)。CVaR\(_\alpha\) 用 Rockafellar–Uryasev 形式
$\(\mathrm{CVaR}_\alpha=\min_{t}\Big\{t+\tfrac{1}{1-\alpha}\sum_k P(\omega_k)\,(L_k-t)_+\Big\},\)$
对离散场景，最优 \(t\) 在某个 \(L_k\) 处取到，遍历即可（实现四的 cvar_discrete）。若下层还要优化每个场景内的轨迹（而非只评估固定轨迹），则 CVaR 可写成一个**凸**子问题（R-U 形式对 \(t\) 与轨迹联合凸），用 QP / 凸求解器解——这是 MARC"下层求解"比 MPDM"下层仿真"更重也更优的地方。
上层（选 ego 策略）：枚举 ego 候选策略（沿用 DCP-Tree 思想），对每个算下层 CVaR，取最小。上层是离散枚举，下层是连续凸优化——这正是"离散外层 + 连续内层"的双层结构，与 EPSILON 的"行为枚举 + 运动 QP"同构，只是把运动层的目标从"期望 / 名义"换成了"CVaR 风险"。
树形输出：MARC 的运动规划器输出"名义轨迹 + 多条延迟分支"——即不只给选中场景的单一最优轨迹，而是保留共享干 + 各场景分支的整棵树，直到执行（与 §U1.1 形式化的轨迹树一致）。这让 MARC 在执行层面也保持了对所有未来的兼容性。
本质洞察：MARC = EPSILON 的双层结构 + 把"期望"换"CVaR" + 把"固定分支"换"动态分支"。三处改动都不动 EPSILON 的"行为枚举 + 运动优化"骨架——它是在同一骨架上换了"代价度量"（期望→CVaR）和"分支点"（固定→Wasserstein 动态），并把运动层输出从单轨迹升级为轨迹树。理解这点，你就知道从 EPSILON 到 MARC 不是推倒重来，而是三个可插拔的升级——这也是工程演进的常见形态：保骨架、换组件。
为什么偏偏是 CVaR，而非别的风险度量¶
MARC 选 CVaR 不是随意的，有两个硬理由（也呼应 U0 §3 对风险度量的讨论、U5 会展开）。
理由一：CVaR 是凸的、可优化的。下层优化要把"风险"塞进一个能解的优化问题。CVaR 的 Rockafellar–Uryasev 形式 \(\min_t\{t+\frac{1}{1-\alpha}\mathbb{E}[(L-t)_+]\}\) 对决策变量**凸**（\((L-t)_+\) 是凸的、取期望与 \(\min_t\) 保凸），所以下层是凸优化、可高效求解。对比 VaR（分位数）——它**非凸**（分位数对决策变量不连续 / 非凸），直接优化 VaR 是难题。所以 CVaR 能进优化、VaR 不能，这是工程上的决定性差别。
理由二：CVaR 是一致性风险度量（coherent risk measure）。它满足次可加性、正齐次、单调、平移不变四条公理——直观说，它对"分散风险"友好（合并两个场景的 CVaR 不大于各自之和），不会出现 VaR 那种"分散反而显得更危险"的悖论。这让用 CVaR 选出的策略在数学上行为良好、可组合（多车 / 多场景时尤其重要）。
对比性思维：CVaR 兼得"看尾部"与"可优化"，这是它被选中的根本。期望（看不到尾部）、最坏情况（太保守且 \(\max\) 在很多场景下也难优化）、VaR（看尾部但非凸、不一致）各有硬伤；CVaR 同时满足"对尾部敏感（看最坏 \((1-\alpha)\)）+ 凸可优化（R-U 形式）+ 一致性（行为良好）"三条，正好卡在 MARC 需要的位置。这也是为什么 CVaR 几乎是风险敏感规划的默认选择（U5 会看到它在更广场景里的统治地位）——不是因为它最保守或最激进，而是因为它"既看得见尾部、又解得动"。
MARC 与 EPSILON 的三处关键差异¶
| 维度 | EPSILON | MARC |
|---|---|---|
| 分支点 | 固定（DCP-Tree 每 2s 节点） | 动态（场景级 Wasserstein divergence） |
| 代价度量 | 场景概率加权**期望** | CVaR\(_\alpha\) 尾部风险 |
| 运动规划输出 | 选定策略下的单一最优轨迹 | 名义轨迹 + 多条延迟分支（树形） |
对比性思维：从 EUDM/EPSILON 到 MARC，是"把固定旋钮变成自适应 + 把期望变成尾部"。EUDM 解决了"组合爆炸"（让分支规划可实时），MARC 解决了"分支点该放哪 + 怎么对罕见危险稳健"（让分支规划更聪明、更安全）。两步进化方向不同：前者是**效率**（压复杂度），后者是**质量**（分支点准 + 风险敏感）。这也提示研究的两个永恒维度——更快，或更好。
⚠️ 本节常见陷阱¶
💡 概念误区：把 CVaR 当成"最坏情况" - 新手想法："MARC 用 CVaR，那就是只看最坏那个场景呗。" - 现象 / 后果：把下层优化实现成 \(\max_k\)（最坏场景），过度保守、退回 frozen 的边缘。 - 根本原因：CVaR\(_\alpha\) 是最坏 \((1-\alpha)\) 尾部的平均，不是单个最坏点。\(\alpha\) 控制尾部多大——\(\alpha=0.9\) 只看最坏 10% 场景的平均，仍比纯最坏温和。 - 正确做法：用 Rockafellar–Uryasev 形式 \(\mathrm{CVaR}_\alpha=\min_t\{t+\frac{1}{1-\alpha}\mathbb{E}[(L-t)_+]\}\)（U3 进阶十）实现，\(\alpha\) 作可调旋钮。检验方法：\(\alpha\to 0\) 应退化为期望、\(\alpha\to 1\) 才趋近最坏。
🧠 思维陷阱：以为动态分支点一定比固定的好，无脑上 Wasserstein - 新手想法："MARC 的动态分支更先进，任何场景都该用。" - 现象 / 后果：在意图揭示时刻本就稳定的场景（如固定路口）上，动态分支带来的 Wasserstein 计算开销得不偿失。 - 根本原因：动态分支的收益在"意图揭示时刻变化大"的场景；揭示时刻稳定时，固定分支（EUDM）又快又够用。 - 正确做法：按场景特性选——揭示时刻多变（密集交互、博弈性强）用 MARC 动态分支；揭示时刻稳定用 EUDM 固定分支。这本身就是一次"方法选型"（见选型决策指南）。
练习¶
- [B 型·MARC 论文精读] 精读 MARC 论文（arXiv:2308.12021），标注：(1) 场景级 divergence 的 Wasserstein 距离怎么算、阈值怎么定；(2) CVaR 双层优化的上下层各优化什么；(3) 与 EPSILON 的三处关键差异在论文图表里的体现。
- [A 型·CVaR 选策略] 在累积项目的两场景分支里，把"期望代价选策略"换成"CVaR\(_\alpha\) 选策略"。构造一个"大概率省时但小概率碰撞"的策略和一个"稍慢但始终安全"的策略，扫 \(\alpha\) 观察 MARC 何时从前者切到后者。
- [思考题] MARC 用 Wasserstein 距离判断"场景何时分叉"。如果两个场景的轨迹均值相同但方差差异大，Wasserstein 距离能否捕捉到这种"分叉"？这对分支点选择意味着什么？
§U1.6 Multi-stage NMPC 与分支规划的数学同构 ⭐⭐⭐¶
动机：化工社区独立发明了同一个东西¶
分支规划起源于自动驾驶（Hardy 2013 → MPDM → EUDM）。但在**化工过程控制**社区，Lucia 与 Engell 等（TU Dortmund）在 2013 年独立发展出 multi-stage NMPC（多阶段非线性 MPC），用 scenario tree（场景树） 处理参数不确定性。惊人的是：multi-stage NMPC 的数学结构与 contingency planning 严格同构——同样的"共享干 + 分支 + 场景加权代价",只是换了套语言、应用在完全不同的领域，而且两个社区几乎不互相引用。
理解这个同构有双重价值：(1) 你能用化工社区成熟的 multi-stage NMPC 理论（递归可行性、鲁棒性证明）和工具（do-mpc、acados 多阶段）来做 contingency planning；(2) 它是"同一个数学骨架在不同领域反复出现"的绝佳教学案例。
Multi-stage NMPC 的 scenario tree¶
Lucia–Finkler–Engell（Journal of Process Control 2013）的设定：系统有**参数不确定性**（如反应速率常数、活化能未知，落在某个区间）。把不确定性离散化成几个代表值（如最大 / 最小 / 名义），在预测时域上展开成一棵**场景树**——每个采样步、对每个不确定性取值分叉：
t0 t_robust T
│ │ │
├──共享───┤ │ robust horizon 内分支
│ ├──ω1(高)─────│ robust horizon 后
│ ├──ω2(名义)───│ 每枝参数固定、不再分叉
│ └──ω3(低)─────│
关键结构与 contingency planning 一一对应：
- 场景 \(\omega_k\)：参数不确定性的离散实现（vs contingency 的"他车意图"）。
- 共享干 + 非预期约束：在不确定性揭示前，各场景共用控制（multi-stage NMPC 明确写出非预期约束 \(u\) 在分叉前相同）——和 §U1.1 的共享干**完全一样**。
- 场景加权代价：\(\sum_k \omega_k\)-概率加权的代价（vs contingency 的场景概率加权）。
- robust horizon（鲁棒时域）\(N_r\)：场景树只在前 \(N_r\) 步分叉，之后每枝参数固定、不再继续分叉——否则树随时域指数膨胀 \(d^{N_r}\)（\(d\) = 每步分支因子）。这对应 contingency 里"分支后各枝独立到底"的截断，是控制复杂度的关键旋钮。
本质洞察：contingency tree 与 scenario tree 是同一棵树。把"他车意图"换成"参数实现"、把"前向仿真评估"换成"NLP 联合优化"、把"离散策略选择"换成"连续控制输出",两者就完全重合。共享干 = 非预期约束，分支 = 场景枝，加权代价 = 期望代价，分支点 / robust horizon = 共享干长度。两个社区从不同问题（驾驶交互 vs 化工参数）出发，各自爬到了同一个数学结构的山顶却没看见对方——这告诉你，"在不确定性揭示前共享动作、揭示后分支优化"是一个领域无关的普适原理，值得你在任何"离散多模态不确定性"的问题上调用。
三处差异（同构之下的不同侧重）¶
| 维度 | Contingency（MPDM/EUDM/EPSILON） | Multi-stage NMPC（Lucia–Engell） |
|---|---|---|
| 场景 \(\omega_k\) | 他车语义意图（离散、领域先验） | 参数不确定性实现（连续集离散化） |
| 评估方式 | 闭环前向仿真（IDM/MOBIL） | NLP 联合优化（所有场景一起解） |
| 输出 | 离散策略选择 + 下游轨迹 | 连续控制输入序列 |
| 理论侧重 | 实时性、可解释、交互建模 | 递归可行性、鲁棒性证明、最优性 |
| 工具 | EPSILON（C++/ROS） | do-mpc（Python）、acados 多阶段 |
注意 multi-stage NMPC 对**离散值**不确定性给出该时域下的最优解，对**连续值**不确定性（离散化后）给出近似——这与 §U1.1 的形式化性质一致。
用 do-mpc 做 scenario tree NMPC¶
do-mpc（TU Dortmund，Python）是 multi-stage NMPC 的主要开源实现，内置场景树支持。它的 set_uncertainty_values() 接口让你声明不确定参数的若干取值，框架自动展开场景树、加非预期约束、调 NLP 求解器（IPOPT 等）。这意味着：你可以用 do-mpc 的工业级 NMPC 求解器做 contingency planning——把"他车意图"建模为离散参数取值即可。
对比性思维：前向仿真评估 vs NLP 联合优化，两种求解哲学。MPDM/EUDM 用**前向仿真 + 枚举**：每个策略组合跑一遍 IDM/MOBIL 仿真算代价，再选最优——简单、可解释、易并行，但"评估"和"优化"分离（先仿真出代价、再挑），且仿真模型简化。multi-stage NMPC 用 NLP 联合优化：所有场景的轨迹 + 非预期约束塞进一个大 NLP 一起解——理论完备（最优性、可行性可证）、能精确处理动力学约束，但非凸 NLP 难解、可解释性弱。一句话：自驾社区偏"枚举 + 仿真"（重交互与实时），过控社区偏"联合 NLP"（重最优与理论）。理解这点，你能在两边的工具箱里自由取用。
注：
acados2025 年的 Multi-Phase OCP 接口在数学上也等价于 scenario tree——意味着可以用 acados 的实时求解器（U2 §U2.6）做 contingency planning，把分支规划接到工业级 SQP-RTI 流水线上。这是把"自驾的分支思想"与"过控的实时求解器"打通的一条工程路径。
为什么两个社区没发现对方（一个文献调研的教训）¶
contingency planning（自驾）和 multi-stage NMPC（化工）数学同构却几乎不互引，原因值得剖析——它对你做跨领域调研有直接启发。
三道隔阂： 1. 问题表述语言不同：自驾说"他车意图、语义策略、交互",化工说"参数不确定性、scenario、recourse"。同一个"共享干 + 分支",一边叫"non-anticipativity 下的 ego 策略序列",一边叫"multi-stage 的 here-and-now + recourse"。关键词不重叠 → 检索不到对方。 2. 评价指标不同：自驾社区重实时性、可解释、交互真实感（能不能上车、能不能解释决策）；化工社区重最优性、递归可行性、鲁棒性证明（能不能证明约束满足）。在意的东西不同 → 各自的"好论文"标准不同 → 不在对方的视野里。 3. 发表场所不同：自驾发 ICRA / RA-L / T-RO（机器人会议期刊）；化工发 J. Process Control / Automatica / CDC（控制 / 过程工程期刊）。读的刊不同 → 物理上看不到对方。
这给你的启发： - 跨领域同构很常见：一个数学结构（这里是"非预期约束下的场景树优化"）常在多个领域被独立发现。做研究前，用"数学结构"而非"领域术语"去检索——搜 "scenario tree optimization""non-anticipativity""multi-stage stochastic programming",能挖到自驾术语检索不到的化工金矿。 - 借用成熟理论：化工社区为 multi-stage NMPC 积累了几十年的递归可行性、鲁棒性、对偶分解理论——做自驾 contingency 时直接借用，不必重新发明。反之，自驾的交互建模 / 实时引导分支也能反哺过控。
acados Multi-Phase OCP 的映射细节：acados 2025 的 Multi-Phase OCP 允许一个 OCP 分成多个"相位（phase）",每相位有自己的动力学 / 约束 / 时域。把场景树的每条分支映射成一个 phase、用非预期约束耦合各 phase 的共享干段，就能用 acados 的 SQP-RTI（U2 §U2.6）实时求解 contingency。这条路径把"自驾的分支思想"接到"过控 / 控制社区的工业级实时求解器",是跨社区借用的一个具体工程出口。
本质洞察：领域壁垒往往是"语言 + 指标 + 场所"的壁垒,而非"思想"的壁垒。两个社区爬到了同一个数学山顶却没看见对方，不是因为思想不通，而是因为说着不同的话、在意不同的事、在不同的地方发表。这是科研里反复上演的故事（卡尔曼滤波在控制与信号处理、EM 算法在统计与机器学习……）。教训很实在：遇到一个结构，先问"别的领域有没有同构的东西",用数学语言去检索——你常能省下重新发明的几年。
为什么 multi-stage 不保守：recourse（反馈在预测中）¶
multi-stage NMPC 被称为"非保守的鲁棒控制",关键在 recourse（追索 / 反馈在预测中，feedback-in-prediction）——这点也正是它与"开环 min-max 鲁棒"的本质区别，值得讲透（它直接对应本章共享干 + 分支的"分支"那一半）。
开环 min-max 鲁棒的保守：最朴素的鲁棒做法是找**一条**控制序列 \(u_{0:N}\)，使其对不确定性的**所有**实现都满足约束（\(\min_u\max_\omega J\)）。问题：它假设"我现在就要定死整条控制序列、之后不管观测到什么都照执行"——但现实是未来会观测到不确定性的实现、可以据此调整。开环 min-max 放弃了这个调整能力，于是被迫用一条对最坏情况都安全的保守序列，过度保守。
multi-stage 的 recourse：scenario tree 的分支结构显式编码了"未来控制可以随不确定性的揭示而调整"——树在每个（robust horizon 内的）节点分叉，意味着不同的不确定性实现走向不同的子树、用不同的后续控制。换言之，未来的控制不是一条定死的序列，而是"依分支而定的反馈策略"。这正是 recourse：先下共享的 here-and-now 控制，等不确定性揭示后，各分支用各自的 recourse 控制补救。
为什么 recourse 降低保守度：因为你不必用一条序列同时对所有实现安全——你只需共享干那段（信息揭示前）对所有实现安全，之后各分支各自应对。这把"对所有未来取交集"（开环 min-max，保守）松弛成"共享干取交 + 分支各管各"（multi-stage，非保守）——和 §U1.1、实现五说的"单轨迹取交 vs 分支共享干 + 分叉"是**同一个道理**。
本质洞察：recourse = 承认'未来能看到信息并据此调整',这正是分支规划的'分支'。开环 min-max 假设"决策一次定死",所以保守；multi-stage / contingency 承认"未来会揭示信息、控制可以反应",所以用分支表达这种反应能力，从而非保守。一句话：保守度来自'假装看不到未来信息',非保守来自'用分支为未来的信息留出反应'。这也解释了 §U1.1 为什么共享干只到分支点——分支点之后的"反应能力"（recourse / 分支）正是降低保守度的来源，过早或过度共享（共享干太长）就是在丢弃 recourse、退回开环 min-max 的保守。
⚠️ 本节常见陷阱¶
💡 概念误区：以为 scenario tree NMPC 和 contingency planning 是两回事 - 新手想法："一个是化工的、一个是自驾的，应该没关系。" - 现象 / 后果：在做自驾分支规划时重新发明 multi-stage NMPC 已经解决的问题（如非预期约束的写法、robust horizon 截断），走弯路。 - 根本原因：没看出二者的数学同构。共享干 = 非预期约束、分支 = 场景枝、加权代价 = 期望代价——是同一个优化结构。 - 正确做法：把它们当成同一个骨架的两个实例，跨社区借用理论与工具（如用 do-mpc / acados 多阶段做 contingency）。检验方法：能写出一个统一形式化，让 MPDM 和 multi-stage NMPC 都是它的特例（综合练习有此题）。
🧠 思维陷阱：以为 robust horizon 越长越鲁棒 - 新手想法："场景树分叉的步数（robust horizon \(N_r\)）越长，考虑的未来越全，越鲁棒。" - 现象 / 后果：\(N_r\) 一大，场景树规模 \(d^{N_r}\) 指数爆炸，NLP 解不动。 - 根本原因：\(N_r\) 是复杂度的指数因子。鲁棒性主要由"是否覆盖了关键的不确定性实现"决定，而非分叉步数。多数情况 \(N_r=1\sim2\) 已足够（之后参数固定）。 - 正确做法：取小 \(N_r\)（常 1–2）+ 滚动重规划，和 EUDM"一周期一次切换 + 高频重规划"是同一智慧。检验方法：增大 \(N_r\) 若性能几乎不变、求解却显著变慢，说明 \(N_r\) 已够。
练习¶
- [A 型·do-mpc 场景树] 用 do-mpc 的 Getting Started，在倒立摆上实现 2-scenario multi-stage NMPC（摩擦系数高 / 低两情景）。对比单场景 NMPC（赌名义摩擦）与多场景的跟踪鲁棒性——在真实摩擦偏离名义时谁更稳。
- [A 型·统一形式化] 写出一个同时涵盖 MPDM 和 multi-stage NMPC 的统一优化形式（共享干 / 非预期约束 + 分支 + 场景加权代价），并分别说明两者是它的哪种特例（场景含义、评估方式、输出类型的取值）。
- [思考题] 两个社区做着同构的工作却几乎不互引。从"问题表述语言"（语义策略 vs 参数实现）和"评价指标"（实时性 / 可解释 vs 最优性 / 可行性证明）两个角度，解释为什么他们没发现对方。这对你做跨领域文献调研有什么启发？
§U1.7 分支规划 vs MCTS：与搜索式规划的结构对比 ⭐⭐¶
动机：分支树和 MCTS 的树，是一回事吗？¶
分支规划展开一棵"策略树"，MCTS（蒙特卡洛树搜索，AlphaGo/MuZero 的核心）也展开一棵树。看起来都是"树搜索",但它们的结构、机制、保证截然不同。把差异讲清，能帮你判断一个"树状决策"问题该用哪种，也能理解二者正在如何收敛。
结构对比¶
| 维度 | 分支规划（MPDM/EUDM） | MCTS（AlphaGo/MuZero） |
|---|---|---|
| 树的展开 | 领域先验**固定宽度**策略树（宽度 = 策略数 / 关键交互，深度浅） | **UCB 自适应**探索-利用（按 \(Q+c\sqrt{\ln N/n}\) 选择性深入） |
| Rollout（推演） | 闭环仿真（IDM/MOBIL 等**确定性**反应模型） | 随机 rollout 或 value network 估值 |
| 反向传播 | 无——每个规划周期从零重新构造树 | 有——累积统计量 \(N(s,a)\)、\(Q(s,a)\) 反传回根 |
| 可解释性 | 高——每个节点是语义明确的策略 | 低——隐式策略 / 值网络 |
| 连续动作 | 天然支持（MPC 风格的连续控制） | 需离散化或 Progressive Widening |
| 收敛保证 | 无（启发式 + 领域先验） | 有（UCB → 渐近最优 / regret bound） |
| 实时性 | 强（固定小树，50–100ms） | 取决于模拟次数预算，可重 |
一个具体例子：无信号路口¶
把抽象对比落到一个场景。ego 接近一个无信号灯路口，对向有一辆车意图不明。
分支规划怎么展开：ego 策略集固定为 {通过, 让行, 停车}（领域先验给定，3 个）；对向车意图分支为 {抢行, 让行}（CFB 判定为关键交互，2 个）。于是树是"\(3 \times 2 = 6\) 个固定分支"，每个分支用 IDM 闭环仿真评估一次，按意图概率加权选 ego 策略。整棵树宽度固定（6）、深度浅（一层意图分叉）、50ms 内枚举完——你能清楚说出"我考虑了通过/让行/停车三种动作，对向抢行/让行两种意图，共 6 种组合"。
MCTS 怎么展开：MCTS 不预设策略集，从当前状态出发，用 UCB 在动作空间里自适应地选择性深入——它可能在"通过"这个有希望的动作上展开很深（多步推演通过后的演化），在"停车"上浅尝辄止；rollout 用随机模拟或价值网络估值，反向传播累积统计，模拟几百上千次后选访问最多 / 价值最高的动作。树是不规则的（有希望的分支深、无希望的浅）、靠大量模拟、决策依据是统计量而非语义。
差别一目了然：分支规划是"6 个语义明确的固定分支 + 一次性确定评估"；MCTS 是"自适应不规则树 + 大量随机模拟 + 统计累积"。前者快、可解释、依赖你把策略集设对（漏了"急加速抢过"这个动作就永远做不出）；后者通用、能发现你没预设的动作、但慢且黑箱。这正是上面结构对比表每一行的具体化。
本质洞察：分支规划用"领域先验"换"搜索",MCTS 用"搜索"换"通用性"。分支规划把"该考虑哪些未来"的知识硬编码进固定宽度的策略树（你告诉它：只有这几个语义策略、只在危险处分支），于是不需要大量搜索就能实时决策——代价是依赖人工设计的策略集、对先验外的情况无能为力。MCTS 不依赖领域先验，靠 UCB 在巨大搜索空间里自适应地探索-利用，理论上渐近最优、通用——代价是要大量模拟、黑箱、连续动作难处理。一句话：分支规划是"知识密集、搜索轻量"，MCTS 是"搜索密集、知识轻量"。选哪个取决于你的领域知识有多强、实时预算有多紧、动作空间是离散还是连续。
两者正在收敛¶
近年两条路线在互相靠近：
- 让分支规划获得 MCTS 的"自适应深度"：用学习的方法预测分支价值和分支点（神经化的分支选择），让 contingency planning 不再是固定宽度树，而能像 MCTS 那样自适应地决定"在哪深入"。
- 让 MCTS 获得 POMDP 式的不确定性处理：把 AlphaZero 思想搬进 belief-space MCTS（如 BetaZero, Moss 等 2024），让 MCTS 在信念空间上搜索，从而处理部分可观测——这正是 U4（POMDP）会展开的方向。
对比性思维：固定宽度树 vs 自适应树，背后是"先验 vs 数据"的老问题。这与 U2/U3 反复出现的主题一致——你对问题了解越多（强先验），就越能用轻量的结构（固定树、解析收紧）实时求解；了解越少，就越要靠搜索 / 数据（MCTS、采样、学习）来补。分支规划站在"强先验"一端，MCTS 站在"弱先验、重搜索"一端，中间地带（神经化分支、belief MCTS）正是当前研究最活跃的地方。
Rollout 的两种角色：确定性闭环仿真 vs 随机 / 价值网络¶
结构对比表里"Rollout"一行最容易被略过，但它体现了两种方法对"如何估一个决策的价值"的根本不同认识，值得展开。
分支规划的 rollout = 确定性闭环仿真：给定 ego 策略 + 场景，用 IDM/MOBIL 这类**确定性**反应模型推演**一条**轨迹，算其代价（实现二的 rollout_cost）。每个（策略, 场景）组合只需**一次**仿真——因为模型确定、结果唯一。代价是仿真模型简化（与真实有差），但好处是快、可复现、可解释（每条 rollout 对应明确的策略 + 场景语义）。
MCTS 的 rollout = 随机模拟或价值网络：MCTS 从一个节点出发，要么做**随机** rollout（随机策略走到底，结果有方差，需多次平均），要么用**价值网络**直接估值（AlphaZero 路线）。随机 rollout 需要大量采样来降低方差（这正是 MCTS"重搜索"的来源）；价值网络则把"估值"摊销进训练好的网络（快但黑箱）。
这个差别的后果： - 分支规划：少量确定性 rollout（每场景一次）→ 快、但受限于模型质量与策略集覆盖。 - MCTS：大量随机 rollout / 网络估值 → 慢（或需训练）、但能逼近真实价值、不依赖手工模型。
这也呼应了"无反向传播 vs 有反向传播"：分支规划每次重新构造、不累积统计（因为确定性 rollout 一次就够）；MCTS 累积 \(N/Q\) 统计（因为随机 rollout 需要多次累积才收敛）。两者是自洽的设计——确定性模型配一次性评估，随机模型配累积统计。
对比性思维：rollout 方式决定了"要不要累积统计"。分支规划用确定性模型，一次 rollout 就给出该场景的确定代价，无需重复，所以也不需要反向传播累积——每周期从零构造树即可。MCTS 用随机 / 网络估值，单次有方差，必须多次采样 + 反向传播累积 \(N/Q\) 才能收敛到可靠估值。所以"无反传"不是分支规划偷懒，而是"确定性 rollout"的自然结果；"有反传"也不是 MCTS 啰嗦，而是"随机 rollout"的必然要求。理解这条因果，你就明白两者的机制差异都源于同一个根：你用什么方式估一个决策的价值。
补充：MCTS 的收敛保证 vs 分支规划的"无保证"¶
§U1.7 的对比表里，MCTS"有收敛保证"、分支规划"无"。这点值得展开——它解释了两者适用边界的理论根源。
MCTS 的保证（直觉版）：MCTS 的选择规则 UCB（Upper Confidence Bound）\(Q(s,a)+c\sqrt{\ln N(s)/n(s,a)}\) 在"利用（选当前最优 \(Q\)）"和"探索（选访问少的 \(n\) 小动作）"间平衡。理论上，UCB 的累积遗憾（regret，与最优策略的差距）随模拟次数 \(N\) 以 \(O(\sqrt{N\ln N})\) 增长（即平均遗憾趋零）——模拟够多，MCTS 渐近收敛到最优。AlphaZero 用神经网络替代随机 rollout 估值，加速了这个收敛但保持了搜索的渐近性。
分支规划为什么"无保证"：分支规划（MPDM/EUDM）的"无收敛保证"有几个来源（呼应进阶专题八的次优性）： - 固定策略集：只在有限语义策略里选，最优动作可能不在集里——无论怎么搜都够不到。 - 无探索机制：每周期按领域先验展开固定宽度树，不像 UCB 那样自适应探索未访问的可能——它压根不"搜索",而是"枚举固定的几个"。 - 无累积统计：每周期从零构造树、不积累 \(Q/N\) 统计，所以没有"随模拟增多而收敛"的机制。
这不是缺陷,是取舍：分支规划用"放弃渐近最优"换"实时 + 可解释 + 强先验下够好"。在自驾这种"领域先验强（就那几个语义策略）、实时预算紧（几十毫秒）、要可解释（决策可审计）"的场景，渐近最优不如"50ms 内给个可解释的够好决策"重要。反之 MCTS 在"领域先验弱、搜索预算充足、容忍黑箱"的场景（如围棋）才发挥渐近最优的威力。
对比性思维：收敛保证的价值取决于"你有没有时间和理由去搜索"。围棋有近乎无限的思考时间 + 没有强先验 + 不需可解释 → MCTS 的渐近最优是宝;自驾有 50ms + 强语义先验 + 要可解释 → 分支规划的"快而够好"更实用。所以"有无收敛保证"不是判断方法优劣的唯一标准——要结合"你的问题给不给搜索的时间和理由"。神经化分支 / belief MCTS（§前沿）正是想在两端之间取一个平衡：用学习注入先验（减少所需搜索）+ 保留一定搜索 / 自适应（获得部分收敛性）。
⚠️ 本节常见陷阱¶
💡 概念误区：以为分支规划是"简化版 MCTS" - 新手想法："分支规划不就是没做反向传播、宽度固定的 MCTS 吗？" - 现象 / 后果：试图给分支规划加 UCB / 反向传播，把它"升级"成 MCTS，结果丢掉了实时性和可解释性、又没获得 MCTS 的理论保证。 - 根本原因：两者是**不同的设计取舍**，不是简繁关系。分支规划的固定宽度 + 无反传是**特意为之**（换实时性与可解释），不是 MCTS 的退化。 - 正确做法：按问题选——强领域先验 + 紧实时预算 + 需可解释 → 分支规划；弱先验 + 大搜索空间 + 容忍黑箱 → MCTS；想要两者之长 → 神经化分支 / belief MCTS（前沿）。
把分支规划放进规划方法谱系¶
收束本章对比，把分支规划摆进"规划方法谱系"的坐标里。沿"先验强度 / 搜索量"轴：
强先验、轻搜索 ─────────────────────────────► 弱先验、重搜索
单轨迹 MPC 分支规划(MPDM/EUDM) 神经化分支/belief MCTS MCTS/MuZero
(赌1个未来) (固定宽度策略树) (学习先验+部分搜索) (UCB自适应树)
│ │ │ │
假设未来唯一 领域先验定K个分支 学习何时/如何分支 纯搜索找最优
最快、最受限 快、可解释、需策略集 平衡快慢与通用 慢、通用、渐近最优
分支规划处在"强先验、轻搜索"一端偏中——比单轨迹 MPC 多了"显式枚举 K 个未来"（不再赌一个），但比 MCTS 少了"自适应搜索"（用固定宽度策略树代替 UCB）。它的甜点是**领域先验强 + 实时预算紧 + 要可解释**的场景（自驾、交互式机器人导航）。当先验变弱（没有现成语义策略集）、搜索预算变大、可容忍黑箱时，谱系向右滑向 MCTS / 学习。
本质洞察：选规划方法,本质是在"先验"和"搜索 / 数据"之间分配你的资源。你对问题了解越多（强先验：知道就那几个语义策略、知道安全约束），越能用轻量结构（固定树、解析约束）实时求解，分支规划就够；了解越少（弱先验），越要靠搜索（MCTS）或数据（学习）来补。这条"先验 ↔ 搜索 / 数据"的权衡贯穿全 Part-U——U2/U3 用强模型先验（动力学 + 不确定性界）做解析鲁棒 / 收紧，本章用强领域先验（语义策略）做枚举分支，而 RL / MCTS 在先验稀薄处用搜索 / 数据补。理解你的问题"先验有多强",就知道该往谱系的哪一端走。
练习¶
- [思考题] MPDM 的策略枚举与 MCTS 的树展开在数学上有何结构性差异？如果要让 MPDM 获得 MCTS 的"自适应深度",需要修改哪些组件？（提示：固定宽度 → 学习的分支价值 / 分支点）
- [B 型·对比实现] 在一个小的离散决策场景（如简化路口）里，分别用"固定宽度策略枚举"和"带 UCB 的 MCTS"求解，对比决策质量、计算时间、可解释性。
- [思考题] 为什么连续动作对 MCTS 是难点、对分支规划（MPC 风格）却天然？这和两者"如何表示动作空间"有关——展开说说。
进阶专题¶
正文给了主线与各方法思想，这里对几个值得深入的点展开——既是对主线的加深，也是研究 / 工程会真正碰到的细节。
进阶专题一：非预期约束与信息结构 ⭐⭐⭐⭐¶
§U1.1 把共享干写成 \(u_i(0{:}t_{\text{branch}})=u_j(0{:}t_{\text{branch}})\)，但它背后是**多阶段随机规划（multi-stage stochastic programming）** 的"信息结构"理论，值得讲透。
信息结构（information structure）：决策在时间上展开，每一步你只知道"到目前为止观测到的信息"。形式上，用一个**信息过滤流（filtration）** \(\mathcal{F}_0\subseteq\mathcal{F}_1\subseteq\cdots\) 描述信息随时间增长——\(\mathcal{F}_t\) 是 \(t\) 时刻"已知的事件"。非预期约束的本质：决策 \(u_t\) 必须是 \(\mathcal{F}_t\)-可测的，即 \(u_t\) 只能依赖 \(t\) 时刻已知的信息，不能"预知"未来才揭示的不确定性。
在场景树上，这翻译成：若两个场景 \(\omega_i,\omega_j\) 在节点 \(t\) 处尚未分开（共享同一历史），则它们在该节点的决策必须相同。共享干就是"所有场景尚未分开的那段公共历史"——分支点 \(t_{\text{branch}}\) 是信息揭示（场景可区分）的时刻，之后各场景进入各自的子树、决策可以不同。
两阶段 vs 多阶段：最简单的随机规划是**两阶段（two-stage）——先决策 here-and-now（不确定性揭示前），观测后再决策 recourse（补救）。contingency 规划本质是两阶段的（共享干 = here-and-now，分支 = recourse）。**多阶段（multi-stage） 则有多个揭示时刻、多层分支（场景树有多层）。EUDM 的 DCP-Tree（多个策略节点）是多阶段的，但用"一周期一次切换 + robust horizon"把层数压到很浅。
本质洞察：共享干 = "信息未到时的 here-and-now 决策",分支 = "信息到后的 recourse"。这把分支规划牢牢锚定在随机规划的经典理论上——非预期约束不是工程 trick，而是"决策不能预知未来"这一信息论铁律的直接编码。理解这点，你就能把分支规划、multi-stage NMPC、场景树优化、随机规划全部看成同一棵树上的果子，并复用随机规划几十年的理论（对偶、分解、可行性）。
进阶专题二：分支 × 机会约束的嵌套（离散 + 连续的统一）⭐⭐⭐⭐¶
正文反复说"分支管离散意图、U3 收紧管连续扰动，可嵌套"。这里把嵌套形式写出来。
设 \(K\) 个离散意图 \(\omega_k\)（他车让 / 不让），**每个意图内部**障碍位置还带连续高斯不确定 \(\Sigma_o^{(k)}\)（感知噪声）。联合形式：
外层是离散意图分支（本章），内层每条分支的避障约束用 U3 的解析高斯收紧处理该意图下的连续不确定（自身状态协方差 \(P_{k,t}\) + 障碍感知协方差 \(\Sigma_o^{(k)}\)）。
直觉：分支回答"哪个未来"，收紧回答"那个未来里多大扰动"。两者维度正交——意图是离散多模态，扰动是连续单峰，各管各的。这正是 U0 §3 "范式可叠加"的精确落地：一个安全系统常常是"分支（U1）处理意图离散多模态 + 每条分支内机会约束（U3）处理连续扰动 + CBF（U2）兜瞬时安全底线"。
对比性思维：嵌套 vs 混为一谈。错误做法是把"意图 + 扰动"都塞进一个大的连续不确定性（如把"让 / 不让"也当成连续分布的方差）——这会让单峰假设崩掉、收紧失效。正确做法是**分层**：离散意图用分支（多峰各留一条），每峰内的连续扰动用收紧（单峰方差）。这与 U3 进阶里 GMM-CC"把多峰拆成多个高斯各自收紧"异曲同工，只是这里多了"为每峰准备独立策略"的决策维度。
进阶专题三：Wasserstein divergence 与动态分支点 ⭐⭐⭐⭐¶
MARC（§U1.5）用场景级 Wasserstein 距离动态定分支点，这里讲清它怎么算、为什么合理。
Wasserstein 距离（直觉版）：度量两个概率分布 \(\mu,\nu\) 的差异，等于"把一个分布的质量搬成另一个分布所需的最小搬运代价"（earth mover's distance）。一维下，\(W_1(\mu,\nu)=\int|F_\mu^{-1}(q)-F_\nu^{-1}(q)|\,dq\)（分位数函数之差的积分）。
用在分支点选择：对每个时刻 \(t\)，比较"不同场景下 ego（或交互）轨迹分布"的 Wasserstein 距离 \(W(t)\)。\(W(t)\) 小 → 各场景的最优轨迹几乎重合（无论哪个未来，当前都该这么走）→ 还不必分支；\(W(t)\) 超过阈值 → 轨迹真的开始分开 → 在这里设分支点。
即"轨迹分布首次显著分叉"的时刻。\(\tau\) 是分叉阈值。
为什么比固定分支点好：固定分支点（EUDM 每 2s）不管场景实际何时分叉；动态分支点让共享干长度自适应——场景早分叉（1s 就分开）则共享干短、晚分叉（4s 才分开）则共享干长。这正好对齐 §U1.1 说的"理想分支点 = 信息揭示时刻"，而 Wasserstein 把"信息揭示"操作化成了"轨迹分布可测地分开"。
本质洞察：动态分支点把"何时分叉"从超参变成可观测量。\(W(t)\) 让"场景何时不得不分开"变得可度量——在 \(W(t)<\tau\) 期间，不同未来对应的最优当前动作几乎一样（所以共享无损），\(W(t)\) 越阈值才必须分。这是"让结构由数据涌现而非人为设定"的典范，也呼应 U3 进阶里用分布距离做自适应决策的思想。代价是要在线估计轨迹分布并算 Wasserstein，比固定分支点重——所以揭示时刻稳定的场景仍用固定分支（见 §U1.5 思维陷阱）。
进阶专题四：MPDM 数值走查（2×2 代价表）⭐⭐⭐¶
把实现二的 mpdm_select 跑一遍，看清"枚举 + 加权 + argmin"的机制。设 ego 初始 \((s,v)=(0,8)\)、他车 \((20,5)\)，ego 策略 \(\{\)go, yield\(\}\)、他车策略 \(\{\)keep, yield\(\}\)，他车策略概率 \((0.7,0.3)\)，闭环前向仿真 3s。
各 (ego, other) 组合的代价（效率 + 安全 + 舒适）构成 \(2\times2\) 表：
| other=keep | other=yield | |
|---|---|---|
| ego=go | 15.4 | 30.4 |
| ego=yield | 107.6 | 110.1 |
按他车策略概率加权： - \(J(\text{go})=0.7\times15.4+0.3\times30.4\approx 19.9\) - \(J(\text{yield})=0.7\times107.6+0.3\times110.1\approx 108.3\)
选 \(\arg\min\) → ego 选 "go"（\(J=19.9\) 远小于 yield 的 \(108.3\)）。
为什么 go 赢、这说明什么：这个场景里他车在 20m 外、gap 大，没有真实碰撞冲突；而 ego 的 IDM 本身就自带避撞（近了自动刹），所以无论 go 还是 yield，安全罚都几乎不触发。于是 yield（低期望速度 \(v_0=4\)）只是白白拖慢 ego、堆高效率罚。关键教训：在**纯纵向跟车**场景里，IDM 的内在避撞让"go/yield"主要只差效率——策略分化不明显。MPDM 真正发挥价值的是**横向冲突**（并线、路口）场景：那里"go（抢)"和"yield（让）"会因碰撞风险真正分化（抢错了会侧撞，IDM 的纵向避撞救不了横向冲突）。这也是文献里 MPDM/EUDM 的标志性场景都是 merge / 路口而非简单跟车的原因。
本质洞察：toy 模型的"反直觉"结果本身是教学点。这个 \(2\times2\) 表诚实地暴露了"用 \(v_0\) 编码策略 + 纯纵向 IDM"的局限——IDM 的避撞太强，洗掉了策略的安全差异。它提醒你：分支 / 多策略的价值取决于"不同策略是否导致定性不同的安全后果"。纵向跟车下后果差异小（IDM 兜底），横向博弈下后果差异大（抢 / 让定生死）。选场景时要让策略真正"分化",才看得出分支规划的价值。
进阶专题五：从 contingency 到博弈 ⭐⭐⭐⭐¶
本章把他车意图当**外生情景**——给定 \(\omega_k\) 与概率 \(P(\omega_k)\)，他车不随 ego 的策略改变其意图分布。但真实交互里，他车也在**对 ego 最优反应**（你让它就进、你抢它就退）。这就从"分支规划"过渡到"博弈规划"。
外生 vs 反应式： - Contingency（外生）：他车意图是给定的概率情景，ego 单方面对这些情景做最优。简单、可解释、适合"他车不太理会 ego"或"交互弱"的场景。 - 博弈（反应式）：ego 和他车互为对方策略的函数，求 Nash 均衡（都最优反应）或 Stackelberg 均衡（一方领导、另一方跟随）。能建模"你来我往"的强交互，但求解更难（耦合的不动点 / 双层优化）。
Contingency Games（Peters 等, 2024, §前沿）把两者结合：在博弈框架里做 contingency——既考虑他车的反应（博弈），又为他车的离散意图 / 类型分支（contingency）。它是"分支思想"在多智能体博弈里的推广。
对比性思维：外生情景 vs 理性玩家，是"预测" vs "博弈"的分界。Contingency 把他车当"带概率的自然现象"（像天气），ego 对它做鲁棒 / 期望最优；博弈把他车当"有目标的对手 / 伙伴",ego 要推理"它会怎么回应我的动作"。判断用哪个：他车对 ego 的反应**弱**（如 ego 是小车、他车是大流量主路）→ contingency 够用；反应**强**（势均力敌的博弈、谈判式交互）→ 需要博弈。这也是为什么密集交互 / 协商场景是博弈规划的主战场，而一般避让用 contingency 即可。
进阶专题六：递归可行性与共享干 ⭐⭐⭐⭐¶
U2 讲过 MPC 的**递归可行性**（这一步可行能否保证下一步仍可行）。分支规划作为滚动重规划的 MPC，也面临这个问题，且共享干带来新的考量。
问题：第 \(t\) 周期解出共享干 + 分支、下发共享干首控制；第 \(t{+}1\) 周期意图概率更新、场景集可能变化，重新展开分支树——新问题还可行吗？
共享干的双刃：共享干强制各场景共用一段动作，这**增强了短期一致性**（治振荡），但也**可能损害递归可行性**——如果共享干把 ego 带到一个"对某个新出现的危险场景无法补救"的状态，下一周期该场景的分支就可能 infeasible。
缓解手段（沿用 U2/multi-stage 思想）： - 终端约束 / 终端集：要求每条分支末端进入一个"安全可维持"的终端集（如能停下、能维持安全距离），保证后续可补救。 - 短共享干 + 高频重规划：共享干越短，被"锁死"在坏状态的风险越小；靠高频重规划不断修正（与 EUDM 一周期一次切换同理）。 - 软约束兜底：碰撞约束加松弛 + 重罚，保证 QP 永远有解（哪怕代价很高），避免硬 infeasible 导致控制器卡死（见故障排查）。
本质洞察：共享干长度是"一致性"与"可行性"的权衡旋钮。长共享干 → 强一致（不振荡）但弱可行性（可能被锁死）；短共享干 → 弱一致但强可行性（易补救）。这又一次回到 §U1.1 "\(t_{\text{branch}}\) 是最关键旋钮"——它不仅调保守度，还调递归可行性。MARC 的动态分支点在这里也有好处：在信息揭示时刻分叉，共享干不会被人为拉长到"锁死"的程度。
进阶专题七：多交互车 / 多分支的组合管理 ⭐⭐⭐¶
正文 MPDM 复杂度 \(O(|\Pi_{\text{ego}}|\cdot|\Pi_{\text{other}}|^n)\) 的指数项来自多车组合。实战里如何管理？
联合分支 vs 边缘分支： - 联合分支：枚举所有他车意图的笛卡尔积（车 A 让 \(\times\) 车 B 抢 \(\times\) …）——最全但 \(|\Pi_{\text{other}}|^n\) 爆炸。 - 边缘分支：只对**最关键的一两辆车**分支意图，其余车用其边缘最可能意图（不分支）——这正是 CFB（§U1.3）。把 \(K\) 从 \(|\Pi_{\text{other}}|^n\) 压到 \(|\Pi_{\text{other}}|^{n_{\text{key}}}\)（\(n_{\text{key}}=1\sim2\)）。
关键车识别：CFB 用"最可能意图的初步仿真"找出"哪些车的意图变化会显著改变 ego 安全 / 代价"。度量可以是：该车不同意图下 ego 最优代价的差异、或该车与 ego 轨迹的时空接近度。
剪枝策略： - 概率剪枝：丢弃联合概率极低的场景组合（如所有车都做小概率动作）。 - 危险剪枝：保留"高危险度"场景（即使概率不高，但后果严重——这与 CVaR 思想一致，§U1.5）。 - 去重 / 聚类：把导致 ego 相似反应的场景聚成一类（呼应 Hardy 2013 的"障碍轨迹聚类"）。
对比性思维：组合管理的核心是"把指数项的底数和指数都压小"。压指数（\(n\to n_{\text{key}}\)）靠 CFB 只分支关键车；压底数（\(|\Pi_{\text{other}}|\)）靠聚类 / 合并相似意图。两者叠加才能把"理论上 \(|\Pi|^n\)"压到"实际几十个分支"。这和 U3 的风险分配、U2 的多障碍 CBF 激活一样，都是"有限计算花在关键处"的工程铁律在分支数上的体现。
进阶专题八：分支规划的最优性与次优性来源 ⭐⭐⭐⭐¶
分支规划（尤其 MPDM/EUDM）是启发式，其次优性来自几个明确来源，理解它们有助于判断"何时该信任它、何时该换方法"。
次优性来源： 1. 有限策略集：ego / 他车只在少数语义策略里选，真实最优动作可能不在策略集里（如某个介于"跟车"和"变道"之间的动作）。策略集越粗，次优越大。 2. 简化前向模型：IDM/MOBIL 是简化反应模型，与真实驾驶有差（EPSILON 加"安全机制"对冲）。前向仿真不准 → 代价估计不准 → 选错策略。 3. 固定分支点：分支点没放在信息真正揭示处（MARC 改进这点）→ 共享干过早 / 过晚 → 次优。 4. 期望 vs 真实目标：用场景概率加权期望，但你真实想要的可能是风险敏感目标（MARC 用 CVaR 改进）。 5. 场景离散化：连续意图离散成几个模态，离散化误差。
对比 multi-stage NMPC 的最优性：multi-stage NMPC 对**离散值**不确定性给出该预测时域下的**最优**解（联合 NLP 精确求解、无策略集 / 前向模型的近似）；对**连续值**不确定性（离散化后）给近似。所以若你的不确定性本就是少数离散值、且能承受 NLP 求解，multi-stage NMPC 比 MPDM/EUDM 更优（无前1–4 项的次优）——代价是非凸 NLP 难解、可解释性弱、连续控制而非语义策略。
本质洞察：MPDM/EUDM 用"五重近似"换"实时 + 可解释",multi-stage NMPC 用"精确 NLP"换"难解 + 黑箱"。没有免费的最优——你要么接受启发式的次优（换实时与可解释），要么付 NLP 的计算与可解释代价（换最优性）。判断标准：实时预算紧 + 要可解释 + 策略集 / 前向模型够好 → MPDM/EUDM；离散值不确定 + 能承受 NLP + 要最优性保证 → multi-stage NMPC。这正是 §U1.6 两种求解哲学的最优性侧面。
进阶专题九：意图概率 \(P(\omega_k)\) 从哪来 ⭐⭐⭐¶
形式化里的 \(P(\omega_k)\)（各离散未来的概率）是分支规划的关键输入，但正文一直当它"给定"。它实际有三个来源，且会随时间更新。
来源一：预测器（learned predictor）。现代多模态轨迹预测器（如基于图神经网络的预测）直接输出"他车有哪几个意图模态 + 各模态概率"。这是 \(P(\omega_k)\) 最直接的来源——把预测器的模态概率接成分支权重即可（呼应 §U1.2 FAQ：分支规划消费预测的产物）。
来源二：领域先验（domain prior）。在没有 / 不信任学习预测器时，用规则给先验：路权规则（主路车更可能保持、支路车更可能让）、历史统计（该路口 80% 的车直行）、几何启发（朝匝道偏的车更可能下匝道）。先验简单、可解释，常作为预测器的兜底。
来源三：贝叶斯更新（Bayesian update）。意图不是一次定死的——随着观测积累，应在线更新意图信念：
观测似然 \(P(o_t\mid\omega_k)\) 来自"他车的实际运动与意图 \(\omega_k\) 的预测运动有多吻合"——他车开始减速了，"让行"意图的似然就升高、信念向让行倾斜。这正是 EPSILON 的 ego-centric belief update（§U1.4）在做的事：只对关键交互车维护并更新这个意图后验。
陷阱与平滑： - 过自信：预测器 / 更新给出的概率若过于尖锐（某模态接近 1），分支会退化成单轨迹（只剩一个有效分支）→ 又可能 frozen / 振荡。 - 抖动：观测噪声让 \(P(\omega_k)\) 每帧剧烈跳动 → 分支权重抖动 → 决策不稳。需对意图概率做时间平滑（如指数滑动平均），或靠共享干吸收短期抖动。 - 模态缺失：真实意图不在枚举的模态集里（如罕见的危险机动）→ 无论概率怎么更新都漏掉它。这是 CFB"靠最可能意图初步仿真识别关键车"的固有风险（§U1.3 练习 3）——小概率危险模态可能被忽略。
本质洞察：\(P(\omega_k)\) 是分支规划与"预测 / 感知"的接口，也是它的软肋。分支规划的决策质量上限，被意图概率的质量卡住——概率不准（过自信 / 抖动 / 漏模态），再好的分支优化也会选错。这解释了两件事：(1) 为什么 EPSILON 要加"带安全机制的驾驶员模型"对冲预测失配；(2) 为什么 MARC 用 CVaR——当概率不可靠时，对尾部加权（而非完全信任期望）是一种稳健兜底。一句话：分支规划把"该怎么决策"做得很好，但"未来有哪些可能、各多大概率"这个上游若不准，下游再优也白搭。
进阶专题十：分支规划怎么评测 ⭐⭐⭐¶
实现了分支规划，怎么定量说它"比单轨迹好"？需要一组针对性指标 + 控制变量对比。
核心指标：
| 指标 | 定义 | 衡量什么 |
|---|---|---|
| frozen rate | 机器人僵住（长时间零速 / 无可行解）的回合占比 | 是否治好 frozen |
| 振荡率 | 单位时间内决策切换 / 控制符号翻转次数 | 是否治好振荡（短期一致性） |
| 碰撞率 | 发生碰撞的回合占比 | 安全 |
| 最近距离 | 全程与障碍的最小间距分布 | 安全裕度 |
| 到达率 / 到达时间 | 成功到目标的占比 / 平均耗时 | 效率 |
| 平均速度 | 全程平均速度 | 效率（保守度的反面） |
| jerk / 加速度方差 | 控制平滑度 | 舒适 |
| 求解耗时（最坏） | 单周期规划耗时的最坏值 | 实时性 |
控制变量对比（在累积项目测试台上）： - 单轨迹 vs 分支：同测试台、同种子、同障碍意图分布，对比 frozen rate 与振荡率——分支应显著降低两者。 - 共享干长度扫描：扫 \(N_{\text{trunk}}\)，画"\(N_{\text{trunk}}\) ↔ 振荡率 ↔ 平均速度"——找"不振荡（共享干够长）也不过保守（共享干不太长）"的甜点。 - 期望 vs CVaR：在"小概率灾难"场景对比期望加权与 CVaR 选策略（实现四）——CVaR 应降低碰撞率（尤其尾部），代价是平均速度略降。 - 固定 vs 动态分支点：在"意图揭示时刻多变"的场景对比 EUDM（固定）与 MARC（动态）——动态分支应在保持安全的同时提高效率。
权衡前沿（trade-off frontier）：分支规划的几个指标互相拉扯——安全 ↔ 效率（更安全往往更慢）、一致性 ↔ 反应性（共享干越长越一致但反应越慢）。好的评测不是看单一指标，而是画**权衡前沿**（如"碰撞率 vs 到达时间"的 Pareto 曲线），看你的方法是否把前沿往"又安全又快"的方向推。
对比性思维：分支规划的评测重点是"frozen / 振荡",不只是"碰撞率"。单看碰撞率，单轨迹规划（对悲观预测避让）可能碰撞率也很低——但它是靠 frozen（僵住不动）换来的，毫无用处。分支规划的价值恰恰在"不靠僵住也能安全"——所以必须同时报告 frozen rate、振荡率、效率，才能体现它相对单轨迹的真正优势。这与 U2/U3 评测时"碰撞率 + 保守度一起看"是同一逻辑：安全不能靠牺牲可用性换取。
进阶专题十一：CFB 的危险度怎么度量 ⭐⭐⭐¶
§U1.3 说 CFB"只对危险交互的他车分支",但"危险度"怎么量化决定了 CFB 的成败。
CFB 的识别流程（更细）： 1. 初步仿真：对当前 ego 策略，让所有他车按其**最可能意图**做一次闭环前向仿真，得到一条名义演化。 2. 危险度打分：对每辆他车，评估"它的意图若不是最可能的那个，会多大程度改变 ego 的安全 / 代价"。常用度量： - 时空接近度：该车与 ego 轨迹在时空上的最近距离 / 最近时刻——越近越危险。 - 意图敏感度：该车不同意图下 ego 最优代价的差异 \(\max_{\text{intent}} J - \min_{\text{intent}} J\)——差异越大，该车意图越"关键"（值得分支）。 - 碰撞贡献：该车在多少个意图组合下会与 ego 产生潜在冲突。 3. 选关键车：按危险度排序，取 top \(n_{\text{key}}\)（通常 1–2 辆）作为分支对象，其余用最可能意图（不分支）。
为什么这样有效：绝大多数他车与 ego 的当前决策无关（远、不冲突、意图变化不影响 ego），为它们分支是浪费。CFB 用"危险度"把计算预算集中到真正影响 ego 的少数车上——把 \(|\Pi_{\text{other}}|^n\) 压到 \(|\Pi_{\text{other}}|^{n_{\text{key}}}\)。
固有风险：CFB 的危险度基于"最可能意图的初步仿真"——若某车真实意图是小概率的危险意图，初步仿真可能没把它判为关键车，于是漏掉了对它的分支。这是"用最可能意图筛选"的固有盲区（呼应 §U1.3 练习 3、专题九的模态缺失）。缓解：危险度里加入"最坏意图"的考量（不只看最可能），或对时空极近的车强制分支（无论意图概率）。
对比性思维：CFB 的危险度筛选 vs U3 的风险分配 vs U2 的 CBF 激活。三者是同一工程铁律的三个化身——有限计算 / 预算只花在关键处。CFB 把分支预算花在危险交互车（按危险度）；U3 IRA 把风险预算 \(\delta\) 分给紧约束（按紧度）；U2 多障碍 CBF 只激活最近几个障碍（按距离）。它们的"关键度量"不同（危险度 / 紧度 / 距离），但思想一致：识别瓶颈、集中资源。掌握这个元思想，你在任何"组合爆炸"的规划问题里都知道第一步该干什么——先找关键的那几个，别无差别枚举。
进阶专题十二：历史演进与实验室传承 ⭐⭐⭐¶
分支规划的发展史，是"概念 → 可实时 → 完整系统 → 更聪明"四步，且有清晰的实验室传承——理解这条线，能帮你把各方法摆到正确的历史位置。
四步演进： 1. 概念奠基（Hardy–Campbell, T-RO 2013）：首次系统提出在概率障碍预测上同时优化多条 contingency 路径——确立了"为多个可能未来分别规划、再耦合"的核心思想。但它是优化型规划器（样条轨迹 + 碰撞概率界 + 障碍轨迹聚类），未引入"语义策略"。 2. 离散策略枚举（MPDM, Cunningham 等, ICRA 2015）：把他车建模为离散语义策略集、用闭环前向仿真评估——把"无穷维轨迹预测"降成"有限策略枚举",可解释性大增。但 \(O(|\Pi|^n)\) 复杂度限制了可扩展性。 3. 引导分支压复杂度（EUDM, ICRA 2020）→ 完整系统（EPSILON, T-RO 2021）：DCP-Tree + CFB 把组合爆炸压回实时（50–100ms），EPSILON 再拼上 SSC 运动层成为完整开源系统、实车验证。这一步让分支规划"能上车"。 4. 更聪明（MARC, RA-L 2023）：动态分支点（Wasserstein）+ CVaR 风险——把固定旋钮变自适应、把期望变尾部。这一步让分支规划"更准、更稳"。
实验室传承： - UMich APRIL（MPDM 原创）：Cunningham、Galceran、Eustice、Olson——MPDM 的策略枚举 + 闭环仿真范式由此而来。 - HKUST Aerial Robotics（EUDM/EPSILON/MARC 黄金三部曲）：Shaojie Shen 组的 Lu Zhang、Wenchao Ding、Tong Li 等——把 MPDM 的思想做成可实时、完整、风险感知的系统，是分支规划工程化的核心推手。 - TU Dortmund DYN（scenario tree NMPC 独立演化）：Lucia、Engell 等——从化工过程控制独立发展出 multi-stage NMPC，数学同构却几乎不与自驾社区互引（§U1.6）。
本质洞察：分支规划的演进是"先把思想做对，再把它做快，再把它做全，最后把它做聪明"。Hardy 把思想做对（多 contingency）、MPDM 把它语义化（策略枚举）、EUDM/EPSILON 把它做快做全（引导分支 + 完整系统）、MARC 把它做聪明（动态分支 + 风险）。这条"对 → 快 → 全 → 聪明"的路径，是很多机器人算法成熟的通用轨迹——你做研究时可以对照：你的方法在哪一步？下一步该往哪走（更快 / 更全 / 更聪明 / 更鲁棒）？
进阶专题十三：分支规划与强化学习的关系 ⭐⭐⭐¶
U0 §6 埋了"经典规控与 RL 处处相通"的暗线。分支规划与 RL 的连接点值得单独讲清。
分支树 vs 策略 / 价值网络：分支规划显式展开"未来情景树"并在上面优化；RL（尤其 model-based）把"对未来的推理"隐式编码进策略 / 价值网络。两者求解的是同一类问题（不确定下的序贯决策），区别在"显式优化"还是"隐式学习"。
几个具体连接： - 与 model-based RL：分支规划的"闭环前向仿真"（IDM/MOBIL 推演）\(\approx\) model-based RL 的"在学到的动力学模型上 rollout"——区别只在前向模型是手工的（IDM）还是学到的（神经动力学）。Contingencies from Observations（§前沿）正是用学到的行为模型做 contingency，是两者的交汇。 - 与分层 / option RL：分支规划的"语义策略集 + 选一个策略"\(\approx\) 分层 RL 的"option / 子策略库 + 选一个 option"。DCP-Tree 的"策略序列"\(\approx\) option 的时序组合。两者都在"离散高层策略 + 连续低层执行"的分层结构上。 - 与 MCTS / AlphaZero：已在 §U1.7 详述——分支规划是固定宽度树（强先验），MCTS 是自适应树（弱先验 + 搜索）；belief MCTS（BetaZero）让搜索处理 POMDP，是两路线收敛点。 - 安全层接口：分支规划（尤其其共享干 + CBF 兜底）可作为 RL 策略的安全外壳——RL 出高层意图 / 偏好，分支规划 + 安全约束保证可执行且安全（呼应 U0 §6、U2 §U2.5 的"经典给 RL 兜底"）。
对比性思维：分支规划是"白盒的、一次性的"未来推理，RL 是"黑盒的、摊销的"未来推理。分支规划每个规划周期从零展开未来树、显式优化（白盒、可解释、但每次重算）；RL 把对未来的推理在训练时"摊销"进网络权重，部署时一次前向（黑盒、快、但难解释、难验证）。这正是 §U1.7 "知识密集 vs 搜索 / 数据密集"的另一面。实践中两者常组合：用 RL / 学习改进分支规划的预测 / 分支点 / 前向模型（注入数据），同时保留分支规划的可解释安全骨架（保住白盒）——这是当前自驾规划"既要学习能力又要可验证安全"的主流折中。
进阶专题十四：最优分支点的理论刻画 ⭐⭐⭐⭐¶
§U1.1 反复说"\(t_{\text{branch}}\) 是最关键旋钮、理想值是信息揭示时刻",§U1.5 说 MARC 用 Wasserstein 找它。这里把"最优分支点"的理论刻画讲清，并连到信息价值与主动感知。
信息揭示时刻 \(\tau^\*\)：定义为"观测足以把意图区分开"的时刻——在 \(t<\tau^\*\) 时，各意图的后验 \(P(\omega_k\mid o_{1:t})\) 仍接近先验（看不清是哪个）；在 \(t\ge\tau^\*\) 后，后验集中到某个意图（看清了）。\(\tau^\*\) 由"他车动作何时透露意图"决定：它一减速，让行意图就显形。
最优分支点 = 信息揭示时刻（理想情形）：考虑共享干带来的代价。在 \(t<\tau^\*\) 区间，由于意图不可区分，各意图下的**最优当前动作本就相同**——此时强制共享干**无损**（你本来也会对各意图下同一个动作）。在 \(t\ge\tau^\*\) 后，意图已可区分，各意图的最优动作开始分歧——此时还强制共享就**有损**（牺牲了对已知意图的最优反应）。所以：
两种偏离的代价： - 分早了（\(t_{\text{branch}}<\tau^\*\)）：在信息还没揭示时就让各分支独立——但此时你还分不清意图，"独立优化"等于对当前最可能意图承诺，丢了短期一致性（→ 振荡）。形式上，分支后各分支的首控制可能不同，而你只能执行一个，被迫选一个=过早承诺。 - 分晚了（\(t_{\text{branch}}>\tau^\*\)）：信息已揭示、各意图最优动作已分歧，却仍强制共享——被迫用一个对已区分意图都折中的动作，过度保守（→ 逼近 frozen）。损失 \(\approx\int_{\tau^\*}^{t_{\text{branch}}}(\text{折中动作代价}-\text{各意图最优动作代价})\,dt\)。
为什么 Wasserstein 能近似 \(\tau^\*\)：各意图下的**最优轨迹**在 \(t<\tau^\*\) 几乎重合（最优动作相同 → 轨迹相同），在 \(t\ge\tau^\*\) 开始分开。所以"轨迹分布的 Wasserstein 距离首次超阈值"的时刻，正是各意图最优轨迹开始分歧的时刻 \(\approx\tau^\*\)（§U1.5、进阶专题三）。MARC 用可观测的"轨迹分叉"代理了不可直接观测的"信息揭示"。
信息价值（Value of Information, VoI）与主动感知：延迟承诺到 \(\tau^\*\) 的收益，本质是"等到信息到位再决策"的信息价值。更进一步——如果 ego 能**主动做动作去加速信息揭示**（如轻轻前压试探他车是否让行，让 \(\tau^\*\) 提前），那么分支点 \(t_{\text{branch}}\) 就不再是被动等来的，而是 ego 可以**主动影响**的——这把"分支规划"推向"主动感知 / 信息收集",正是 U4（POMDP / 主动感知）的核心：把"何时 / 如何获得信息"也变成决策变量。
本质洞察：分支规划的最优性,等价于"把承诺时机对齐到信息节奏"。\(t_{\text{branch}}^\*=\tau^\*\) 这一条把全章的旋钮直觉升华成理论：共享干在信息揭示前无损（最优动作本就一致）、揭示后有损（牺牲已知意图的最优）——所以最优分支点恰是信息揭示时刻。MPDM/EUDM 用固定 \(t_{\text{branch}}\) 是对 \(\tau^\*\) 的粗略猜测（常猜偏）；MARC 用 Wasserstein 估计 \(\tau^\*\)（更准）；U4 的主动感知则让 ego 去**改变** \(\tau^\*\)（更主动）。这条"猜 \(\tau^\*\) → 估 \(\tau^\*\) → 改 \(\tau^\*\)"的线，串起了 §U1.1、§U1.5 与 U4——也是分支规划走向信息论最优的方向。
进阶专题十五：分支 × 机会约束嵌套的数值示意 ⭐⭐⭐⭐¶
进阶专题二给了"分支管离散意图、每条分支内用 U3 机会约束管连续扰动"的嵌套形式。这里用数值把它做实，展示 U0 §3"范式可叠加"的具体样子。
设定：两意图 \(\{\)让行, 通过\(\}\)（离散分支，本章），每条分支内障碍位置带高斯不确定 \(s_{\text{obs}}\sim\mathcal N(\bar s_{\text{obs}},\sigma_o^2)\)（连续扰动，U3）+ ego 自身状态协方差 \(P\)。每条分支的避障约束用 U3 解析收紧：
收紧量数值（\(d_{\text{safe}}=5\)，\(\Phi^{-1}(0.95)=1.645\)）：
| \(\delta\) | \(\Phi^{-1}(1{-}\delta)\) | \(\sigma_o{=}0.5,P{=}0\) | \(\sigma_o{=}1.0,P{=}0.25\) | \(\sigma_o{=}2.0,P{=}1.0\) |
|---|---|---|---|---|
| 0.10 | 1.282 | 0.641 | 1.433 | 2.866 |
| 0.05 | 1.645 | 0.822 | 1.839 | 3.678 |
| 0.01 | 2.326 | 1.163 | 2.601 | 5.202 |
读法：取 \(\delta=0.05\)、\(\sigma_o=1.0\)、\(P=0.25\)，收紧量 \(=1.645\sqrt{1.25}\approx1.84\) m——有效安全间距 \(=d_{\text{safe}}+1.84=6.84\) m（比名义 5m 多留 1.84m，以 95% 概率不违约）。\(\delta\) 越小（要求越严）、不确定越大（\(\sigma_o,P\) 越大），收紧越多。
嵌套的关键：两条分支的收紧量**可以不同**——"让行"分支里他车已开始减速、意图较明朗，感知 \(\sigma_o\) 可能较小（收紧少）；"通过"分支里他车仍在快速运动、预测 \(\sigma_o\) 较大（收紧多）。于是每条分支按**自己那个意图下的连续不确定**各自收紧。这正是嵌套的样子：
本质洞察：嵌套 = "分支选未来 + 每个未来内收紧扰动",两个旋钮各管一维。外层的 \(K\) 个分支处理"他车意图是让还是通"（离散多模态），内层的 \(\Phi^{-1}(1-\delta)\sqrt{\cdot}\) 处理"那个意图下障碍位置的连续不确定"（单峰方差），两维正交、各调各的。一个成熟的自驾规控栈往往是三层嵌套：分支（U1，离散意图）→ 每分支内机会约束（U3，连续概率扰动）→ CBF 兜瞬时安全底线（U2）。这就是 U0 §3 "范式可叠加"从口号变成可写出的联合公式——也是你把全 Part-U 的工具拼成一个系统的样板。
进阶专题十六：可解释性与安全验证 ⭐⭐⭐¶
§U1.4 提过分支规划"可解释、可验证"是相对端到端的核心优势。在安全关键部署里，这不是锦上添花，而是能否上路的硬门槛——值得单独讲清。
分支规划的可解释性来自哪： - 语义策略：每个分支对应一个有名字的策略（"在 A 车后并入""让行""绕障碍左侧"）——决策可以用人话解释（"我选了让行，因为对向车大概率抢行"），而非一串黑箱网络激活。 - 显式场景与概率：\(\{\omega_k, P(\omega_k)\}\) 明确列出"我考虑了哪些未来、各多大概率"——出了问题能复盘"是漏了某个场景，还是概率估错了"。 - 可见约束：碰撞 / 动力学 / 安全约束都是显式写出的（如 SSC 走廊、\(d_{\text{safe}}\)），能逐条审计"违反了哪条"。
为什么这对安全验证关键：安全关键系统（自驾、医疗机器人）通常要**可验证、可认证、可追责**。 - 可验证：能形式化地检查"在所有枚举场景下，约束是否满足"——分支规划的离散场景 + 显式约束让这种检查可做（multi-stage NMPC 甚至能给约束满足的证明，§U1.6）；端到端网络的"所有输入下安全"难以形式化验证。 - 可追责：事故后能回答"系统当时为什么这么决策"——分支规划有决策树、场景、概率可查；黑箱难追责。 - 可调试 / 可干预：发现某类场景处理不当，能定点修（加一个分支、调一个约束、改一个先验）；端到端要重训整个网络且可能引入新问题。
代价（诚实地说）：可解释性来自"手工设计的策略集 + 先验模型",这也是分支规划的软肋——策略集外的情况处理不了、先验模型与真实有差（§U1.4 EPSILON 的"安全机制"正是补这个）。端到端能从数据学到分支规划设计者没想到的复杂交互模式。所以前沿（§前沿）的方向多是"用学习增强分支规划的预测 / 分支点 / 前向模型（注入数据能力），同时保留分支 / 分层的可解释安全骨架（保住可验证）"。
本质洞察：在安全关键机器人里,"可验证安全"常压倒"平均性能最优"——这是分支 / 分层等经典方法长盛不衰的根本原因。一个平均表现更好但偶尔莫名失败、且无法验证 / 追责的黑箱，在自驾 / 医疗里可能根本无法部署；一个平均表现稍逊但每个决策可解释、约束可验证、失败可追责的分支规划器，反而能过认证、能上路。这呼应 U0 与全 Part-U 的一条暗线：不确定性下的规控，最终交付的不只是"性能",而是"有依据的安全"——分支规划把"为什么这么决策、考虑了哪些未来、约束是否满足"全部摆到台面上，这正是它在 2013–2024 十余年间从未被端到端取代、反而持续演进（EUDM→EPSILON→MARC）的深层原因。学习与经典不是替代关系，而是"学习提供能力、经典提供可验证骨架"的互补。
前沿与开放问题¶
分支规划近年的活跃方向，是把"固定策略集 + 固定分支"推向"学习 / 采样 / 博弈"，并向自驾以外的机器人场景迁移。
- 采样式分支（MPPI 路线）：把分支约束放进 MPPI 的采样框架，用 GPU 并行评估大量带分支的 rollout。相关工作如 Biased-MPPI（Trevisan, Alonso-Mora, IEEE RA-L 2024）把"辅助控制器"融进 MPPI 的采样分布以改善收敛，为采样式 contingency 提供了基础；也有工作在 MPPI 内部再嵌一层 MPPI 评估 contingency 的可达性约束。意义：把分支规划从"凸 QP / NLP"搬到"可大规模并行采样"的范式（呼应采样式 MPC 方向 D）。
- 博弈式分支（Contingency Games）：Peters 等的 Contingency Games（IEEE RA-L 2024）把 contingency planning 放进多智能体博弈框架——不只是"为他车意图分支",而是显式建模 ego 与他车的策略耦合。它把 §U1 的"他车意图作为外生情景"升级为"他车也在最优反应"，与博弈规划方向交界。
- 风险感知分支 + 多模态预测（RACP）：把多模态轨迹预测器的输出直接接入 risk-aware contingency（如 RACP, Mustafa 等 2024），用预测分布驱动分支与风险度量——是 MARC 思想与现代深度预测器的结合。
- 拓扑驱动分支（Topology-driven MPC）：de Groot 等的 T-MPC 在"拓扑等价类"层面分支——把"绕障碍左侧 / 右侧 / 不通过"作为离散拓扑选择，并行优化多条对应轨迹、择优执行。它和 contingency 的"为离散选择分支"同源，但分支维度是**轨迹拓扑**而非"他车意图"。意义：分支思想从"意图不确定"推广到"自身机动的多模态"。
- 学习驱动的分支选择：用神经网络预测"该不该分支、在哪分支、各分支概率"，让 contingency planning 获得 MCTS-like 的自适应深度（§U1.7）；以及从观测中学他车行为模型来做更可靠的前向仿真（如 Contingencies from Observations, Rhinehart 等, ICRA 2021）。
- belief-space MCTS（与 U4 交界）：BetaZero（Moss 等 2024）把 AlphaZero 搬进 belief-space MCTS，让搜索式规划获得 POMDP 式不确定性处理——是 §U1.7 "两路线收敛"的代表。
开放问题（尤其机器人侧）： - 机器人侧的分支规划：分支规划在自驾很成熟，但在无人机追逃（对手机动的离散模态）、多足地形分支（"踩这块石头 / 那块石头"）、人机协作（人的意图离散多模态）等机器人场景仍少见——把成熟的 contingency 框架迁移过去是明确的空白。 - 分支点的学习与保证：MARC 用 Wasserstein 动态定分支点是启发式，缺乏"何时分支才最优 / 才安全"的理论保证。 - 与连续不确定性的统一：分支处理离散意图、U2/U3 处理连续扰动，如何在一个框架里同时处理"该走哪个分支 + 每个分支内的连续鲁棒 / 机会约束"（嵌套），是一个工程上常见但理论上未完全打通的问题。
一个值得动手的迷你研究方向：把本章的 contingency MPC 接到一个机器人场景（如无人机躲避一个"可能左转可能右转"的动态障碍），用累积项目的测试台验证它相比单轨迹 MPC 在 frozen / 振荡上的改善。门槛适中（本章给了可运行骨架），且填补"机器人侧分支规划"的空白。
完整实现精读：从公式到可运行代码¶
前面给了形式化与各方法思想；这一节对最核心的两件事给出可独立运行的实现：(1) 场景树 contingency MPC（共享干 + 分支，凸 QP），把 §U1.1 的形式化逐行落地；(2) MPDM 风格的闭环前向仿真（IDM + 策略枚举），把 §U1.2 落地。读完你应能从零写出一个分支规划器。
两节实现的分工：实现一是"优化型"分支规划（一个带非预期约束的联合 QP 同时解所有分支，对应 multi-stage NMPC / SSC 风格）；实现二是"枚举 + 仿真型"分支规划（枚举策略、闭环前向仿真评估，对应 MPDM/EUDM 风格）。两者覆盖了 §U1.6 对比的两种求解哲学。
实现一：场景树 contingency MPC（共享干 + 分支）¶
最清晰的可运行设定是**纵向 yield-vs-go**：ego 沿一条直路行驶（状态 = 位置 \(s\)、速度 \(v\)，控制 = 加速度 \(a\)），前方有一个动态障碍，它有两种离散意图——"刹车"（减速，ego 必须保持跟车间距）或 "维持"（匀速，ego 可更快）。每个意图给出障碍的预测位置轨迹。ego 决策一棵轨迹树：共享干段（前 \(N_{\text{trunk}}\) 步）对两意图用**同一组加速度**，分支段各自优化。碰撞约束是"保持在障碍后方至少 \(d_{\text{safe}}\)"——它对决策变量**线性**，所以整个问题是**凸 QP**。
import numpy as np, cvxpy as cp
def contingency_mpc_long(s0, v0, v_des, obs_traj, probs, N=30, N_trunk=8,
dt=0.1, a_max=3.0, d_safe=5.0, w_v=1.0, w_a=0.1):
"""纵向 yield-vs-go 场景树 contingency MPC（凸 QP）。
s0,v0: ego 初始位置/速度; v_des: 期望速度。
obs_traj: 形如 (K, N+1) 的各意图下障碍位置预测; probs: (K,) 各意图概率。
共享干: 前 N_trunk 步控制对所有意图相同(非预期约束)。
碰撞约束: 每个意图、每步 ego 位置 <= 障碍位置 - d_safe (跟在后方)。"""
K = obs_traj.shape[0]
s = [cp.Variable(N + 1) for _ in range(K)] # 每意图一条位置轨迹
v = [cp.Variable(N + 1) for _ in range(K)] # 每意图一条速度轨迹
a = [cp.Variable(N) for _ in range(K)] # 每意图一条加速度轨迹
cost, cons = 0, []
for k in range(K):
cons += [s[k][0] == s0, v[k][0] == v0]
for t in range(N):
cons += [s[k][t+1] == s[k][t] + dt * v[k][t]] # 位置积分
cons += [v[k][t+1] == v[k][t] + dt * a[k][t]] # 速度积分
cons += [cp.abs(a[k][t]) <= a_max, v[k][t] >= 0] # 执行器 + 不倒车
cons += [s[k][t+1] <= obs_traj[k][t+1] - d_safe] # 跟在障碍后方(线性!)
# 场景加权代价: 跟踪期望速度 + 控制平滑
cost += probs[k] * (w_v * cp.sum_squares(v[k] - v_des) + w_a * cp.sum_squares(a[k]))
# 非预期约束: 共享干段(前 N_trunk 步)各意图加速度相同
for k in range(1, K):
cons += [a[k][:N_trunk] == a[0][:N_trunk]]
cp.Problem(cp.Minimize(cost), cons).solve(solver=cp.OSQP, warm_start=True)
a_shared = a[0][:N_trunk].value # 共享干: 对所有意图一致的当前动作序列
return float(a_shared[0]), a_shared, [s[k].value for k in range(K)]
# 用法:
# 障碍初始在 s=30, "维持"意图匀速 8 m/s, "刹车"意图减速到 0
# t = np.arange(N+1)*dt
# obs_go = 30 + 8.0*t # 匀速维持
# obs_stop = 30 + np.maximum(0, 8.0 - 4.0*t)*t # 减速(示意)
# obs_traj = np.vstack([obs_go, obs_stop]); probs = np.array([0.6, 0.4])
# a0, a_shared, ego_trajs = contingency_mpc_long(0.0, 8.0, 10.0, obs_traj, probs)
逐块对应 §U1.1 的形式化：s[k]/v[k]/a[k] 是每个意图（场景 \(\omega_k\)）一条独立轨迹；probs[k] 是 \(P(\omega_k)\)；cost += probs[k]*... 是场景加权代价 \(\sum_k P(\omega_k)J(\cdot;\omega_k)\)；a[k][:N_trunk] == a[0][:N_trunk] 是**共享干 / 非预期约束**（前 \(N_{\text{trunk}}\) 步控制对所有意图相同）；s[k][t+1] <= obs_traj[k][t+1] - d_safe 是随意图变化的碰撞约束 \(\mathcal{X}(\omega_k)\)。返回的 a_shared[0] 是唯一的、对所有意图一致的当前控制——这正是分支规划"当前该做什么"的稳健答案。注意碰撞约束对 s[k] 线性，整个问题是凸 QP，OSQP 微秒级可解。
实现一的数值走查：共享干长度如何调节保守度¶
用一个能定性手算的设定理解"共享干越长越保守"。设 ego 初速 \(v_0=8\)、期望速度 \(v_{\text{des}}=10\)，障碍初始在 \(s=30\)；意图"维持"下障碍匀速 8（ego 可逐渐加速逼近 \(v_{\text{des}}\)，间距够），意图"刹车"下障碍快速减速停在 \(s\approx 34\)（ego 必须减速以保持 \(d_{\text{safe}}=5\) 的间距，即 ego 最终不能超过 \(s\approx 29\)）。
- 共享干段（前 \(N_{\text{trunk}}\) 步）：加速度对两意图必须相同。要同时满足"维持"意图希望加速、"刹车"意图要求别冲太前，最优的共享动作是一个**折中**——温和加速甚至轻微减速，使得无论哪个意图揭示，ego 都还来得及反应。
- 共享干越长（\(N_{\text{trunk}}\) 越大）：折中动作要维持越久，ego 在共享段越不敢加速（因为要为"刹车"意图留余地），整体更**保守**（平均速度更低）。
- 共享干越短（\(N_{\text{trunk}}\) 越小）：ego 很快就能按各意图分别优化——"维持"分支大胆加速、"刹车"分支及时减速，整体效率更高，但短期一致性弱（接近独立两段）。
定性验证：把 N_trunk 从 4 调到 16，打印共享干首加速度 a0 与"维持"分支的平均速度。N_trunk 越大，a0 越小（越保守）、平均速度越低——与上面的推理一致。这就是 §U1.1 "\(t_{\text{branch}}\) 是最关键旋钮"的数字体感：分支点（共享干长度）直接换算成保守度。
把
N_trunk设为 0（无共享干）会怎样？两意图的轨迹完全独立优化，a[0][0]和"假如只优化刹车意图"得到的首控制可能不同——你将无法给出唯一的当前动作，回到 §U1.1 陷阱里说的"退化成独立 MPC + 决策振荡"。所以 \(N_{\text{trunk}}\ge 1\) 是分支规划有意义的前提。
实现二：MPDM 风格闭环前向仿真（IDM + 策略枚举）¶
实现一是"联合 QP"路线；实现二走"枚举 + 仿真"路线（MPDM/EUDM 风格）。核心是 IDM 反应模型 + 策略枚举 + 闭环前向仿真评估。
import numpy as np
def idm_accel(v, v_lead, gap, v0=12.0, a=1.5, b=2.0, s0=2.0, T=1.5):
"""IDM 纵向加速度。v: 本车速度, v_lead: 前车速度, gap: 与前车间距(>0)。
dot_v = a[1 - (v/v0)^4 - (s*/gap)^2], s* = s0 + max(0, vT + v·Δv/(2√(ab)))。"""
dv = v - v_lead # 接近速度 Δv
s_star = s0 + max(0.0, v * T + v * dv / (2.0 * np.sqrt(a * b))) # 期望间距(取非负)
gap = max(gap, 1e-3) # 防除零
return a * (1.0 - (v / v0) ** 4 - (s_star / gap) ** 2)
def rollout_cost(ego_policy, other_policy, ego0, other0, T_sim=3.0, dt=0.1):
"""闭环前向仿真: ego 按 ego_policy、他车按 other_policy, 用 IDM 互相反应。
ego0/other0 = (s, v)。策略用期望速度 v0 编码: 'go'->高 v0, 'yield'->低 v0。
返回该(ego,other)组合的代价: 效率(偏离期望) + 安全(间距过小重罚) + 舒适(加速度)。"""
v0_map = {"go": 12.0, "yield": 4.0, "keep": 8.0}
es, ev = ego0; os_, ov = other0 # ego/other 的(位置,速度)
cost = 0.0
for _ in range(int(T_sim / dt)):
gap = os_ - es # ego 在后, 他车在前
a_e = idm_accel(ev, ov, gap, v0=v0_map[ego_policy]) # ego 对他车反应
a_o = idm_accel(ov, ev, 1e6, v0=v0_map[other_policy])# 他车(前车无约束, gap=∞)
ev = max(0.0, ev + dt * a_e); es += dt * ev # 闭环推进
ov = max(0.0, ov + dt * a_o); os_ += dt * ov
cost += (ev - 10.0) ** 2 * dt # 效率: 偏离期望速度 10
cost += 1e3 * max(0.0, 3.0 - gap) ** 2 * dt # 安全: 间距<3 重罚
cost += 0.1 * a_e ** 2 * dt # 舒适: 控制平滑
return cost
def mpdm_select(ego0, other0, ego_policies, other_policies, other_probs):
"""MPDM: 枚举 ego 策略, 对他车策略闭环仿真, 按他车策略概率加权选最优 ego 策略。"""
best_pi, best_J = None, np.inf
table = {}
for pe in ego_policies:
J = 0.0
for po, p in zip(other_policies, other_probs):
c = rollout_cost(pe, po, ego0, other0)
table[(pe, po)] = c
J += p * c # 按他车策略概率加权
if J < best_J:
best_J, best_pi = J, pe
return best_pi, best_J, table
# 用法:
# best, J, table = mpdm_select((0.,8.), (20.,5.),
# ego_policies=["go","yield"], other_policies=["keep","yield"],
# other_probs=[0.7, 0.3])
# 注意: 纯纵向跟车下 IDM 已自带避撞(近了自动刹), 故 ego 多选 "go"(效率更高);
# "go/yield" 的真正分化在横向冲突(并线/路口)场景 —— 那里选错会真撞上(见进阶专题四)
逐块对应 §U1.2：idm_accel 是 IDM 公式（注意 s_star 的 max(0,·) 与相对速度项，正是 §U1.2 编程陷阱说的两个易错点）；rollout_cost 是**闭环**前向仿真（ego 和他车都用 IDM 互相反应，不是开环录像）；mpdm_select 是策略枚举 + 概率加权选择，对应 §U1.2 算法的双重循环。把策略用"期望速度 \(v_0\)"编码是一种最简的语义策略实现（go = 高 \(v_0\) 冲、yield = 低 \(v_0\) 让）。
两个实现的关系：实现一（联合 QP）给出唯一的共享干动作、理论上最优、处理连续控制；实现二（枚举仿真）给出语义策略选择、可解释、易并行，但评估靠简化仿真。真实系统常**两者结合**——用实现二（MPDM/EUDM 风格）在行为层选语义策略，再用实现一（QP / SSC 风格）在运动层把选定策略落成光滑轨迹。这正是 EPSILON 的分层架构（§U1.4）。
实现三：MOBIL 换道决策（横向策略的反应模型）¶
实现二给了 IDM（纵向）。换道（横向策略）用 MOBIL——它用 IDM 算"换道前后相关车的加速度变化"，按安全 + 激励两准则决定换不换。这补全了 MPDM 前向仿真里"变道"类策略的反应模型。
import numpy as np
def mobil_lane_change(ego, cur_lead, tgt_lead, tgt_back, p=0.3, b_safe=4.0, a_th=0.1):
"""MOBIL 换道决策。ego=(v, gap_to_cur_lead);
cur_lead/tgt_lead: 当前/目标车道前车速度(None=无前车);
tgt_back=(v, gap_to_ego_after): 目标车道后车(ego 并入后它的前车变成 ego)。
返回 (是否换道, 激励值, 安全是否满足)。"""
ve, gap_cur = ego
a_ego_old = idm_accel(ve, cur_lead if cur_lead else ve, gap_cur if cur_lead else 1e6)
a_ego_new = idm_accel(ve, tgt_lead if tgt_lead else ve, 30.0 if tgt_lead else 1e6)
if tgt_back: # 目标车道后车: 换道前后加速度变化
vb, gap_b = tgt_back
a_back_old = idm_accel(vb, tgt_lead if tgt_lead else vb, 1e6) # ego 来之前
a_back_new = idm_accel(vb, ve, gap_b) # ego 并入后跟 ego
else:
a_back_old = a_back_new = 0.0
safe = a_back_new >= -b_safe # 安全准则: 别逼后车急刹
incentive = (a_ego_new - a_ego_old) + p * (a_back_new - a_back_old) # 激励准则
return (safe and incentive > a_th), incentive, safe
# 验证(数值已核对):
# 当前车道慢前车(gap10,lead6)、目标车道空、后车远(8,40): (True, +12.2, safe) -> 换道
# 目标车道后车很近很快(12, gap3): (False,-24.0,unsafe) -> 不换(安全否决)
# 当前车道畅通(无前车): (False, -0.02,safe) -> 不换(无激励)
逐块对应 §U1.2 的 MOBIL：a_ego_new - a_ego_old 是 ego 换道的"自身收益"；p*(a_back_new - a_back_old) 是礼让加权的"对目标车道后车的影响"；safe = a_back_new >= -b_safe 是安全准则（别把后车逼到急刹）；incentive > a_th 是激励准则（收益超阈值才换）。三个验证用例分别覆盖"该换（前方慢车 + 旁道空）""不该换（后车近，安全否决）""不必换（本道畅通，无激励）"——这正是 MOBIL 的三类典型判断。
实现四：CVaR 风险感知的策略选择（MARC 思想）¶
实现二的 mpdm_select 按场景**期望**选策略；MARC（§U1.5）按 CVaR 选。这里给出离散场景的 CVaR 计算（Rockafellar–Uryasev 形式）与风险感知选择，并展示它如何在"小概率灾难"场景下做出与期望不同的选择。
import numpy as np
def cvar_discrete(costs, probs, alpha):
"""离散场景的 CVaR_alpha(Rockafellar-Uryasev): 最坏(1-alpha)尾部的平均代价。
CVaR_a = min_t { t + 1/(1-a) * Σ_k p_k * max(0, L_k - t) }。最优 t 在某个 L_k 取到。"""
costs, probs = np.asarray(costs, float), np.asarray(probs, float)
return min(t + 1.0/(1.0-alpha) * np.sum(probs * np.maximum(0.0, costs - t))
for t in costs)
def cvar_select(policy_scenarios, alpha=0.9):
"""风险感知策略选择(MARC 思想): 选 CVaR_alpha 最小的策略。
policy_scenarios: {policy: (costs[list], probs[list])}。alpha->0 退化为期望。"""
best, best_c = None, np.inf
for pol, (costs, probs) in policy_scenarios.items():
c = cvar_discrete(costs, probs, alpha)
if c < best_c:
best_c, best = c, pol
return best, best_c
# 验证(数值已核对): 策略A"大概率省时小概率灾难" vs 策略B"稳定中等"
# A: costs=[10,1000], probs=[0.9,0.1] (期望=109, 但有灾难尾部)
# B: costs=[120,130], probs=[0.9,0.1] (期望=121, 但无灾难)
# 期望(等价 alpha=0): 选 A(109<121) —— 风险中性会赌灾难策略
# CVaR_0.5: A=208,B=122 -> 选 B; CVaR_0.9: A=1000,B=130 -> 选 B
# 即 alpha 越大(越在意尾部), 越早从"省时但危险"切到"稳健安全"
逐块对应 §U1.5 的 MARC：cvar_discrete 是 CVaR 的 Rockafellar–Uryasev 形式（U3 进阶十的同一公式）；cvar_select 是 MARC 下层"按 CVaR 而非期望选策略"。验证里 A 是"大概率省时（10）、小概率灾难（1000）"的激进策略，B 是"稳定中等（120/130）"的稳健策略——期望选 A（109<121，被小概率灾难平均掉了），但 CVaR（\(\alpha\ge0.5\)）选 B（尾部把 A 的灾难暴露出来）。这正是 §U1.5 "期望把罕见碰撞平均掉、CVaR 对尾部敏感"的数字铁证，也验证了 §U1.5 陷阱所说"\(\alpha\to 0\) 退化为期望"。
三个实现 + 一个选择器的全景：实现一（contingency QP，共享干 + 分支）是运动层；实现二（MPDM 选策略）+ 实现三（MOBIL 换道）是行为层的枚举 + 反应模型；实现四（CVaR 选择）把行为层从风险中性升级为风险感知（MARC）。把它们拼起来——MPDM/MOBIL 选语义策略（可换成 CVaR 选），contingency QP 落成共享干 + 分支轨迹——就是一个"行为层 + 运动层 + 风险感知"的完整分支规划器骨架，对应 EPSILON（§U1.4）+ MARC（§U1.5）的集成形态。
实现五：单轨迹 vs 分支——frozen 的对比¶
本章开篇说分支治 frozen。这里用最小代码把"单轨迹必僵 / 分支能解"摆在一起。关键对比：**单轨迹**规划要求一条轨迹同时满足**所有意图**的避障约束（对所有意图的占据取并集 / 最严处），**分支**允许轨迹在分支点后按意图分开。
import numpy as np, cvxpy as cp
def single_traj_mpc(s0, v0, v_des, obs_traj, N=30, dt=0.1, a_max=3.0, d_safe=5.0):
"""单轨迹(无分支)鲁棒规划: 一条轨迹必须对所有意图都安全。
obs_traj: (K, N+1) 各意图障碍位置。约束 = 对每个意图都满足 -> 取最严(min)。"""
s, v, a = cp.Variable(N+1), cp.Variable(N+1), cp.Variable(N)
cost, cons = 0, [s[0]==s0, v[0]==v0]
for t in range(N):
cons += [s[t+1]==s[t]+dt*v[t], v[t+1]==v[t]+dt*a[t]]
cons += [cp.abs(a[t])<=a_max, v[t]>=0]
for k in range(obs_traj.shape[0]): # 对所有意图都要满足(无分支!)
cons += [s[t+1] <= obs_traj[k][t+1] - d_safe] # 等价于 <= 最严的那个意图
cost += cp.sum_squares(v[t]-v_des) + 0.1*cp.square(a[t])
prob = cp.Problem(cp.Minimize(cost), cons); prob.solve(solver=cp.OSQP)
return prob.status, (s.value if s.value is not None else None)
# 对比实验(伪代码描述, 结论由约束结构决定):
# 场景: 障碍"维持"意图匀速远离(给 ego 大空间), "刹车"意图急停在近处(逼 ego 停)。
# single_traj_mpc: 一条轨迹必须同时满足两意图 -> 被"刹车"意图(最严)逼停在近处,
# 即使"维持"意图本可大胆前进 -> 过度保守(平均速度极低, 接近 frozen);
# 若"刹车"意图的停车点 < d_safe, single 直接 infeasible(真 frozen)。
# contingency_mpc_long(实现一): 共享干段温和折中, 分支后"维持"分支加速、"刹车"分支停,
# -> 可行且不过度保守。
为什么单轨迹必僵：单轨迹要求**一条** \(s(t)\) 在每个时刻都满足所有意图的约束，等价于满足**最严**的那个——\(s(t)\le \min_k(\text{obs}_k(t)-d_{\text{safe}})\)。于是无论哪个意图实际发生，ego 都按"最坏意图"行动：要么过度保守（被最严意图逼得极慢），要么直接 infeasible（最严意图的可行域为空）。这正是 §U1.1 反面说的 frozen——对所有可能都悲观避让。
为什么分支能解：分支允许 \(s_k(t)\) 在分支点后各自满足**自己那个**意图的约束（\(s_k(t)\le \text{obs}_k(t)-d_{\text{safe}}\)，不取并集），于是"维持"分支不被"刹车"意图拖累。共享干段虽仍需折中（前 \(N_{\text{trunk}}\) 步对两意图一致），但折中只持续到分支点，之后松绑——保守度被限制在共享干长度内，而非贯穿全程。
本质洞察：单轨迹 = 对意图集取交（最严约束），分支 = 共享干后对意图各取各的。这是 frozen 的数学根源——单轨迹把"对所有未来安全"实现成"满足所有约束的交集",交集可能空（infeasible）或极小（过保守）；分支把这个交集只施加在共享干段，分支后各意图在自己的（更宽的）可行域里走。一句话：单轨迹对未来取交、分支对未来取共享干 + 分叉——这一个集合运算的差别，就是 frozen 与不 frozen 的差别。
累积项目：U1 模块（给统一测试台加分支决策层）¶
U0 §7 规划的累积项目里，U1 的任务是**给统一不确定性导航测试台加分支 / MPDM 决策层**——处理一个带离散意图的动态障碍。前几章（U2 鲁棒、U3 机会约束）处理的是连续扰动；U1 模块**只新增"动态障碍 + 分支决策"这一层，主干测试台不变**，体现累积项目"加一个范式只加一个模块"的精神。
import numpy as np, cvxpy as cp
class BranchNavModule:
"""U1 累积项目模块: 在 2D 导航测试台上加一个带离散意图的动态障碍 + 分支决策。
复用前几章的 2D 思路, 但聚焦'离散意图'这一新不确定性来源。
场景: ego 沿 +x 行驶到目标; 一个横穿障碍有'抢行(cross)'或'让行(yield)'两意图。
分支规划: 共享干段统一减速准备, 分支段按意图分别(抢行->等它过, 让行->通过)。"""
def __init__(self, dt=0.1, d_safe=4.0):
self.dt, self.d_safe = dt, d_safe
self.x_conflict = 15.0 # 冲突区 ego 的 x 坐标
self.goal_x = 30.0
def predict_obstacle(self, intent, N):
"""各意图下障碍占据冲突区的时间窗(简化为障碍到达/离开冲突区的时刻)。
返回 ego 在冲突区 x_conflict 处'必须避开'的时间步集合(占用窗)。"""
t = np.arange(N + 1) * self.dt
if intent == "cross": # 抢行: 障碍 1.0~2.5s 占据冲突区(ego 须等)
occupy = (t >= 1.0) & (t <= 2.5)
else: # 让行: 障碍很快离开/不进入, 几乎不占据
occupy = (t >= 0.0) & (t <= 0.4)
return occupy
def plan(self, s0, v0, intents, probs, N=40, N_trunk=10,
v_des=8.0, a_max=3.0):
"""两意图纵向 contingency: ego 决策共享干 + 分支, 避免在障碍占用窗内进入冲突区。
约束实现: 占用窗内, ego 位置 s <= x_conflict - d_safe (停在冲突区前)。"""
K = len(intents)
s = [cp.Variable(N + 1) for _ in range(K)]
v = [cp.Variable(N + 1) for _ in range(K)]
a = [cp.Variable(N) for _ in range(K)]
cost, cons = 0, []
for k, intent in enumerate(intents):
occupy = self.predict_obstacle(intent, N)
cons += [s[k][0] == s0, v[k][0] == v0]
for t in range(N):
cons += [s[k][t+1] == s[k][t] + self.dt * v[k][t]]
cons += [v[k][t+1] == v[k][t] + self.dt * a[k][t]]
cons += [cp.abs(a[k][t]) <= a_max, v[k][t] >= 0]
if occupy[t+1]: # 占用窗内: 停在冲突区前
cons += [s[k][t+1] <= self.x_conflict - self.d_safe]
cost += probs[k] * (cp.sum_squares(v[k] - v_des) + 0.1*cp.sum_squares(a[k])
+ 0.5*cp.sum_squares(s[k][-1] - self.goal_x))
for k in range(1, K): # 非预期约束: 共享干
cons += [a[k][:N_trunk] == a[0][:N_trunk]]
cp.Problem(cp.Minimize(cost), cons).solve(solver=cp.OSQP, warm_start=True)
return a[0][:N_trunk].value, [s[k].value for k in range(K)]
# ── 三档目标(呼应 U2/U3 累积项目) ──
# Bronze: 跑通两意图 contingency, 可视化共享干 + 两条分支轨迹
# Silver: 扫 N_trunk(共享干长度), 画"共享干长度 ↔ ego 平均速度(保守度)"曲线;
# 扫意图概率 probs, 观察 ego 倾向(抢行概率高 -> 更早减速准备)
# Gold: 把'期望加权'换成 CVaR(MARC 思想)选策略; 或把分支点从固定 N_trunk
# 换成'两分支轨迹开始分叉处'动态确定(Wasserstein divergence 的离散近似)
与前几章累积项目的关系：U2 的 NavTestbed 处理连续有界扰动（Tube + CBF）、U3 的 CCNavTestbed 处理连续概率扰动（机会约束）；U1 的 BranchNavModule 处理**离散意图**这一新维度。三者正交、可叠加——真实系统里，你可以在每条分支内部再用 U3 的机会约束处理该分支的连续扰动（U0 §3 "范式可叠加"的体现）。这也是累积项目的设计目的：在同一测试台上，让你亲手把"离散分支 + 连续鲁棒 / 机会约束"拼起来。
本质洞察：U1 模块把测试台的不确定性从"连续"扩到"离散多模态"。前几章的扰动都是"围绕名义的连续抖动"，加一种就是换一种收紧 / 滤波；U1 加的是"未来分叉成几种"这一**结构性**新维度，需要的是"树状决策"而非"单轨迹收紧"。把它和 U2/U3 拼起来，测试台就同时具备了"执行端连续扰动 + 交互端离散意图"——已经逼近真实自驾 / 机器人系统的不确定性结构。
方向落地案例¶
分支规划起源自驾，但"为离散多模态未来分别准备"的思想是跨方向的。各方向的落地形态：
- 自动驾驶（原生场景）：路口让行 / 抢行、并线博弈、前车直行 / 下匝道——他车意图的离散多模态。EPSILON / MARC 是代表，已在真实城市车流验证。这是分支规划最成熟的战场。
- 无人机追逃 / 避障：对手机动的离散模态（左规避 / 右规避 / 俯冲），或动态障碍"可能左转可能右转"。可把 ego 的 contingency tree 接到无人机 MPC（呼应无人机方向的 rpg_mpc）——共享干保证短期机动一致，分支为对手各模态各留一条规避。机器人侧分支规划仍是空白（§前沿开放问题）。
- 多足机器人地形分支：落足点选择的离散多模态（"踩这块石头 / 那块石头 / 绕过"），尤其在 stepping-stones、碎石地形。可与 U2 §U2.5 的 CBF 地形安全约束结合——分支选落足模态、CBF 保证每步落足安全。
- 人机协作 / 服务机器人：人的意图离散多模态（"要拿这个 / 那个"、"往左走 / 往右走"）。机器人用 contingency 为人的每个意图准备一条配合策略，共享干段做对所有意图都合理的预备动作，等人的意图明朗再分支。这与 U4（POMDP / 主动感知）天然结合——机器人甚至可以主动做动作去试探人的意图。
- 过程控制（同构场景）：化工 / 能源系统的参数不确定性（反应速率、负荷未知）。multi-stage NMPC（§U1.6）是这里的标准形态，do-mpc 是主力工具。
本质洞察：分支规划的迁移条件是"不确定性是离散多模态 + 揭示有延迟"。任何满足"未来分叉成几个离散可能、且要过一会儿才能看清是哪个"的问题，都可以套分支规划的"共享干 + 分支"骨架——无论对象是他车意图、对手机动、落足点、人的意图还是化工参数。反之，若不确定性是连续单峰抖动（用 U2/U3）、或离散但立刻可知（无需共享干），就不必用分支。判断"要不要分支规划",先问这两个条件。
方法选型决策指南¶
面对一个"未来不确定"的规划问题，按下面的逻辑选（先判断要不要分支，再选哪种分支方法）。
第一步：要不要用分支规划？
- 不确定性是**连续单峰**抖动（风、噪声、未建模残差）吗？→ 是则用 U2（鲁棒 / 有界）或 U3（机会约束 / 概率），不必分支。
- 不确定性是**离散多模态**（他车让 / 不让、左 / 右）吗？→ 是则继续。
- 多模态**立刻可知**（一观测就分清）吗？→ 是则无需共享干，直接按已知模态规划；否则（揭示有延迟）→ 用分支规划。
第二步：选哪种分支方法？
| 你的情况 | 推荐方法 | 本章位置 |
|---|---|---|
| 入门 / 想要可解释的策略枚举 | MPDM | §U1.2 |
| 他车多、需实时（50–100ms） | EUDM（DCP-Tree + CFB 压复杂度） | §U1.3 |
| 要完整系统（决策 + 轨迹）、要落地参考 | EPSILON（EUDM + SSC） | §U1.4 |
| 意图揭示时刻多变 / 在意尾部风险 | MARC（动态分支 + CVaR） | §U1.5 |
| 连续控制 + 要最优性 / 可行性保证 | Multi-stage NMPC（do-mpc / acados 多阶段） | §U1.6 |
| 弱领域先验 + 大搜索空间 + 容忍黑箱 | MCTS / belief MCTS | §U1.7 |
| 要大规模并行采样 | 采样式分支（Biased-MPPI 路线） | §前沿 |
| 自身机动的拓扑多模态（绕左 / 绕右） | Topology-driven MPC | §前沿 |
第三步：分支内部还有连续扰动吗？ → 在每条分支内部叠加 U3 的机会约束 / U2 的 Tube（嵌套）。分支管"哪个未来"、收紧管"该未来内的连续扰动"。
一句话选型：连续扰动找 U2/U3，离散意图找本章；本章内部——求快用 EUDM，求全用 EPSILON，求稳（风险 / 动态分支）用 MARC，求理论 / 连续控制用 multi-stage NMPC，弱先验用 MCTS。
理论补遗：非预期约束、robust horizon 与复杂度¶
正文用到几个理论点，这里补齐。
非预期约束（non-anticipativity）的本质。它来自多阶段随机规划（multi-stage stochastic programming）：决策必须是"到目前为止可观测信息"的函数，不能"预知"未来才揭示的不确定性。在分支规划里，\(t<t_{\text{branch}}\) 时你还分不清是哪个场景，所以这段的控制只能对所有场景相同——这就是共享干。形式上：若两个场景 \(\omega_i,\omega_j\) 在时刻 \(t\) 之前不可区分，则 \(u_i(0{:}t)=u_j(0{:}t)\)。它是分支规划 / multi-stage NMPC / 场景树优化的共同地基（U2 场景树 MPC 已用过）。
robust horizon（鲁棒时域）与复杂度。场景树若每步对 \(d\) 个不确定性取值都分叉，\(N\) 步后有 \(d^N\) 个叶子——指数爆炸。multi-stage NMPC 的对策是**只在前 \(N_r\) 步（robust horizon）分叉，之后每枝参数固定不再分叉**，叶子数降到 \(d^{N_r}\)。取小 \(N_r\)（常 1–2）+ 滚动重规划，是控制复杂度的关键（与 EUDM 的 DCP-Tree"一周期一次切换"同理）。
分支规划的复杂度谱： $\(\underbrace{\text{MPDM 组合}}_{O(|\Pi_{\text{ego}}||\Pi_{\text{other}}|^n)}\ \xrightarrow{\text{DCP-Tree+CFB}}\ \underbrace{\text{EUDM}}_{O(\text{深度}\times\text{宽度})}\ ,\qquad \underbrace{\text{场景树 NMPC}}_{O(d^{N_r}\cdot\text{单NLP})}.\)$ 关键洞察：MPDM 的爆炸在"他车组合数 \(n\) 的指数"，EUDM 用序列 + 危险筛选把它压成多项式；multi-stage NMPC 的爆炸在"robust horizon \(N_r\) 的指数",用小 \(N_r\) 截断。两条路线都靠"截断 + 高频重规划"控制复杂度。
最优性。multi-stage NMPC 对**离散值**不确定性给出该预测时域下的最优解；对**连续值**不确定性（离散化后）给出近似（离散化越细越准、越慢）。MPDM/EUDM 是启发式（依赖策略集与前向仿真模型的质量），无最优性保证——这是用"可解释 + 实时"换来的。
本质洞察：分支规划的所有复杂度控制，本质都是"截断未来 + 滚动修正"。无论是 EUDM 的"一周期一次切换"、CFB 的"只在危险处分支"、还是 multi-stage 的"只在 robust horizon 内分叉",都在做同一件事——不在单次规划里展开完整的未来树（那必然指数爆炸），而是浅浅展开 + 靠高频重规划不断修正。这与 MPC 滚动时域、与 U2/U3 的"离线重活 + 在线轻量"是同一种工程哲学：不求一次算尽，求每次够好且能滚动纠偏。
从 Python 原型到 C++ 部署¶
本章原型用 Python（cvxpy / numpy）。真实自驾 / 机器人系统的分支规划要落到 C++ 实时回路。
两段式工作流（沿用 U2/U3）：Python 原型验证算法 / 策略集 / 分支逻辑 → C++ 部署实时回路。分支规划的 C++ 落地有两条主路径，对应正文的两种求解哲学：
- 枚举 + 仿真路线（MPDM/EUDM/EPSILON 风格）：行为层是策略树展开 + 闭环前向仿真，计算密集但天然并行（各策略 / 各分支的仿真互相独立）。C++ 实现重点是：(1) 高效的前向仿真（IDM/MOBIL 的向量化 / 多线程）；(2) DCP-Tree / CFB 的剪枝逻辑；(3) 与运动层（SSC 的走廊 QP）的接口。EPSILON（C++/ROS）是现成的工业级参考——它在 50–100ms 内完成 EUDM 策略树展开，可直接精读其 C++ 实现。
- 联合 NLP / QP 路线（multi-stage NMPC 风格）：把场景树 + 非预期约束塞进一个 NLP / QP。C++ 落地可借 acados 的 Multi-Phase OCP（§U1.6）——它把场景树映射到工业级 SQP-RTI 求解器（U2 §U2.6），实时性强。或用 CasADi 手写场景树 NLP + IPOPT（do-mpc 的底层）。
部署阶段的专属坑： - 实时预算与分支数的权衡：分支数 \(K\)、DCP-Tree 深度、CFB 关键车数都直接影响耗时；C++ 里要把这些设成可配置，并监控最坏情况耗时（不是平均）。 - 前向仿真的确定性 / 可复现：闭环仿真涉及浮点累积，C++ 与 Python 结果可能有差异；逐模块对拍。 - 求解失败兜底：行为层选不出策略 / 运动层 QP infeasible 时，要有兜底（上一周期策略、紧急减速）——分支规划在真实长尾场景必然偶尔失败，兜底是安全底线。 - 意图概率的来源与时延：\(P(\omega_k)\) 来自预测器，预测器有时延 / 误差；C++ 集成时要处理预测的时间对齐与异常值。
部署总原则：分支规划在 Python 验证过（化解 frozen / 振荡）\(\ne\) 在 C++ 真车上达标。前向仿真模型与真实他车的失配、预测概率的误差、最坏情况耗时、长尾兜底——这四类只在部署暴露。EPSILON 的"带安全机制的驾驶员模型"正是为对冲模型失配而设（§U1.4）。
工具与源码精读拓展¶
分支规划用得好不好，一半在于读过真实系统的代码。按"先易后难"的精读清单：
| 项目 | 角色 | 精读重点 |
|---|---|---|
| highway-env（Python/Gym） | 轻量测试环境 | 不精读代码，用作分支规划的测试场景（merge / 路口 / 环岛）；在它上面跑你的 MPDM 实现，观察 frozen / 振荡 |
EPSILON（HKUST-Aerial-Robotics/EPSILON，C++/ROS，GPLv3） |
完整工业级参考 | semantic_map_manager/（他车状态 / 意图编码）、eudm_planner/（DCP-Tree + CFB 完整实现，约 2000 行）、ssc_planner/（时空语义走廊 QP）；重点理解 EUDM 如何在 50–100ms 内完成策略树展开 |
do-mpc（do-mpc/do-mpc，Python） |
multi-stage NMPC 实现 | controller.py 的 set_uncertainty_values()——场景树如何嵌入 NLP；对比 scenario tree NMPC 与 EPSILON 的 DCP-Tree 在代码层面的异同 |
Apollo Planning（ApolloAuto/apollo，planning 模块） |
工程质量最高的枚举 | modules/planning/scenarios/——EM Planner 的多候选枚举结构（与 MPDM 同构）；学工业级策略枚举的代码组织 |
精读路线建议：先用 highway-env 跑通自己的 MPDM（建立直觉）→ 精读 EPSILON 的 eudm_planner/（理解工业级 DCP-Tree + CFB）→ 用 do-mpc 跑 scenario tree NMPC（理解同构的另一面）→ 翻 Apollo 的 scenarios（看工程组织）。
避坑：EPSILON 是 ROS1 项目、依赖较多，搭环境前先读 README 的依赖清单；do-mpc 装好 CasADi + IPOPT 即可快速上手；highway-env 是 pip 一键装的轻量 Gym 环境，最适合快速实验。
本章代码索引与项目结构¶
| 代码 | 在哪 | 作用 |
|---|---|---|
contingency_mpc_long |
实现一 | 纵向 yield-vs-go 场景树 contingency MPC（凸 QP，共享干 + 分支） |
idm_accel |
实现二 | IDM 纵向加速度（跟车反应模型） |
rollout_cost |
实现二 | 闭环前向仿真 + 代价（MPDM 评估） |
mpdm_select |
实现二 | MPDM 策略枚举 + 概率加权选择 |
BranchNavModule |
累积项目 | 测试台分支决策模块（横穿障碍抢行 / 让行） |
建议的项目结构（Python 原型 + C++ 部署双包）：
branch_nav/
├── prototype_py/ # Python 原型(研究/验证)
│ ├── contingency_mpc.py # contingency_mpc_long(场景树 QP)
│ ├── mpdm.py # idm_accel, rollout_cost, mpdm_select
│ ├── idm_mobil.py # IDM/MOBIL 反应模型
│ ├── testbed.py # BranchNavModule(累积项目)
│ └── experiments.py # 扫 N_trunk / 意图概率 / frozen 对比
├── deploy_cpp/ # C++ 部署(实时上车)
│ ├── behavior/ # EUDM 风格: DCP-Tree + CFB + 前向仿真
│ ├── motion/ # SSC 风格: 走廊构造 + QP
│ └── config/params.yaml # K, 树深, CFB 关键车数, d_safe, 时域...
└── scenario_tree_nmpc/ # 联合 NLP 路线(可选)
└── dompc_model.py # do-mpc / acados 多阶段场景树
衔接工作流：prototype_py/ 跑通分支逻辑 / 策略集 / 参数（扫 \(N_{\text{trunk}}\)、对比 frozen）→ 行为层移到 deploy_cpp/behavior/（EUDM 风格）、运动层移到 deploy_cpp/motion/（SSC 风格），或走 scenario_tree_nmpc/（联合 NLP）→ 用 params.yaml 让 Python 调好的参数直接喂 C++。
综合实战清单：从零搭一个分支规划器¶
把全章串成一条可执行路径：
- 建测试环境：用 highway-env（merge / 路口）或累积项目的
BranchNavModule，先跑一个**单轨迹 MPC** baseline，复现 frozen / 振荡（亲眼看到问题）。 - 写反应模型：实现 IDM（注意
s*的max(0)与相对速度项）+ MOBIL，单车道跟车 / 换道验证。 - MPDM 行为层：策略枚举 + 闭环前向仿真（实现二），按意图概率加权选策略。在 merge 场景验证它化解 frozen。
- contingency 运动层：用场景树 QP（实现一）把选定意图落成共享干 + 分支轨迹。可视化轨迹树。
- 压复杂度：加 DCP-Tree（一周期一次切换）+ CFB（只对关键交互车分支），把仿真次数压到几十次。
- 调分支点：扫 \(N_{\text{trunk}}\)（共享干长度），画"保守度 ↔ 分支点"曲线，找到不 frozen 也不振荡的甜点。
- 升级风险 / 动态分支（进阶）：把期望加权换成 CVaR（MARC 思想）；把固定分支点换成场景分叉处动态确定。
- 上真机前检查：前向仿真模型与真实他车的失配如何兜底？意图概率的来源 / 时延？最坏情况耗时？长尾失败的兜底策略？
走完这八步，你就有了一个"行为层（MPDM/EUDM 选策略）+ 运动层（contingency QP 出轨迹）"的完整分支规划器——本章方法的集成形态。把它和累积项目测试台拼起来，就能做"单轨迹 vs 分支""期望 vs CVaR""固定 vs 动态分支点"的对比实验。
🔧 故障排查手册¶
分支规划的"故障"很少是代码崩溃，更多是"决策行为不对"。下表按症状定位。
| 症状 | 可能原因 | 排查 / 纠正步骤 | 相关节 |
|---|---|---|---|
| 机器人僵住不动（frozen） | 退回了单轨迹规划 / 共享干太长 / 对所有场景悲观避让 | 1. 确认是否真在解联合分支问题（非各场景独立）；2. 缩短 \(N_{\text{trunk}}\)；3. 检查是否对每个场景都留了可行分支（而非全场景共用一条最坏约束） | §U1.1 |
| 决策反复横跳（振荡） | 共享干太短 / 没加非预期约束 / 意图概率每帧剧变 | 1. 确认非预期约束加在**控制**上、覆盖前 \(N_{\text{trunk}}\) 步；2. 增大 \(N_{\text{trunk}}\)；3. 对意图概率做时间平滑 | §U1.1/§U1.2 |
| 联合 QP / NLP infeasible | 共享干 + 分支约束冲突（某场景在共享段就不可行）/ \(d_{\text{safe}}\) 过大 | 1. 打印各场景在共享段的约束余量；2. 给碰撞约束加松弛 + 重罚；3. 减小 \(d_{\text{safe}}\) 或缩短共享干 | §U1.1/实现一 |
| 前向仿真里车辆穿模 / 负间距 | IDM 的 \(s^*\) 漏 max(0) 或漏相对速度项 / 步长过大 |
1. 核对 s_star = s0 + max(0, vT + v·Δv/(2√(ab)))；2. 减小 dt；3. 检查 gap 防除零 |
§U1.2/实现二 |
| 实时超时（>预算） | 分支数 \(K\) 太大 / DCP-Tree 太深 / CFB 没生效（对所有车分支） | 1. 用 CFB 只对关键交互车分支；2. 限制树深 + 一周期一次切换；3. 监控最坏耗时（非平均），上限 \(K\) | §U1.3/理论补遗 |
| MPDM 选出的策略在真实交互中差 | 用了开环（非交互）前向仿真 | 1. 确认仿真里 ego 与他车都按各自策略**互相反应**；2. 在并线场景对拍开环 vs 闭环 | §U1.2 |
| 对小概率危险场景不设防 | 用期望代价、被罕见灾难平均掉 | 1. 换 CVaR\(_\alpha\) 选策略（MARC 思想）；2. 调 \(\alpha\) 增大尾部权重 | §U1.5 |
| 分支点总是不对（早 / 晚） | 用了固定分支点、但场景揭示时刻多变 | 1. 改用动态分支（场景轨迹分叉处）；2. 用 Wasserstein / 简单轨迹距离阈值定分支点 | §U1.5 |
API 速查表¶
本章涉及的核心函数 / 接口签名与一句话说明（原型用 numpy / cvxpy，工程用 EPSILON / do-mpc / acados）。
| 函数 / 接口 | 签名（简化） | 说明 |
|---|---|---|
contingency_mpc_long |
(s0,v0,v_des,obs_traj,probs,N,N_trunk,...) -> (a0, a_shared, ego_trajs) |
纵向场景树 contingency QP，返回共享干首控制 |
idm_accel |
(v,v_lead,gap,v0,a,b,s0,T) -> accel |
IDM 跟车加速度 |
rollout_cost |
(ego_policy,other_policy,ego0,other0,T_sim,dt) -> cost |
闭环前向仿真代价 |
mpdm_select |
(ego0,other0,ego_policies,other_policies,other_probs) -> (best_pi, J, table) |
MPDM 策略选择 |
cp.Variable / cp.Problem |
cvxpy | 场景树 QP 的决策变量与求解（OSQP 后端） |
do-mpc MPC.set_uncertainty_values |
(**{param: [v1,v2,...]}) |
声明不确定参数取值，自动展开场景树 NMPC |
| acados Multi-Phase OCP | AcadosMultiphaseOcp |
把场景树映射到 SQP-RTI 求解器（§U1.6） |
EPSILON eudm_planner |
C++ / ROS | DCP-Tree + CFB 行为决策（工业级参考） |
EPSILON ssc_planner |
C++ / ROS | 时空语义走廊 QP（运动规划） |
调参与诊断速查¶
| 参数 / 旋钮 | 作用 | 调大 | 调小 | 经验起点 |
|---|---|---|---|---|
| \(N_{\text{trunk}}\) 共享干长度 | 短期一致性 vs 保守度 | 更稳、更保守（易 frozen 边缘） | 更激进、易振荡 | 时域的 1/4 ~ 1/3，再按 frozen / 振荡微调 |
| \(K\) 分支数 | 覆盖未来 vs 计算量 | 覆盖更全、更慢 | 更快、可能漏危险模态 | 3–8（用 CFB 筛选关键交互） |
| DCP-Tree 深度 | 策略序列长度 | 看更远、指数膨胀 | 更快、看不远 | 时域 / 节点间隔（如 8s÷2s = 4） |
| CFB 关键车数 | 分支精度 vs 计算量 | 更准、更慢 | 更快、可能漏车 | 1–3 辆最危险交互车 |
| \(\alpha\)（CVaR，MARC） | 风险偏好 | 更保守（重尾部） | 趋近期望（风险中性） | 0.8–0.95，安全关键场景偏大 |
| robust horizon \(N_r\)（multi-stage） | 分叉步数 vs 复杂度 | 更鲁棒、指数膨胀 | 更快、欠鲁棒 | 1–2（之后参数固定） |
| \(d_{\text{safe}}\) 安全间距 | 安全 vs 通行 | 更安全、易 infeasible | 更激进、易擦碰 | 按速度 / 制动能力定，留制动距离 |
| IDM 车头时距 \(T\) | 跟车松紧 | 跟车更松（间距大） | 跟车更紧（间距小） | 1.0–1.6s |
| MOBIL 礼让 \(p\) | 换道激进度 | 更礼让（少变道） | 更自私（多变道） | 0.1–0.5 |
诊断口诀：frozen → 缩共享干 / 查分支可行性；振荡 → 增共享干 / 查非预期约束加在控制上 / 平滑意图概率；超时 → CFB 筛关键车 / 限树深；对罕见危险不设防 → 换 CVaR。
本章 FAQ：高频疑问速答¶
Q1：分支规划和"多假设跟踪 / 多模态预测"有什么区别？ 多模态预测只是给出"未来有哪几种可能 + 概率"（感知 / 预测的产物）；分支规划是在这些可能之上**做决策**（共享干 + 分支优化）。预测是输入、规划是输出。分支规划消费多模态预测的结果（\(\omega_k\) 与 \(P(\omega_k)\)）。
Q2：共享干第一控制下发后，下一周期场景概率变了，分支树要重建吗？ 是。和标准 MPC 滚动时域一样——每周期用最新观测更新场景集与概率、重新展开分支树、解、下发新的共享干首控制。分支规划是"每周期重规划",不是"规划一次执行到底"。
Q3：\(K\) 个场景必须穷举吗？能不能采样？ 两条路都有。MPDM/EUDM 是穷举（小 \(K\) + CFB 筛选）；采样式（Biased-MPPI 路线，§前沿）用采样近似大量分支，靠 GPU 并行。穷举可解释、适合小 \(K\)；采样适合大场景空间。
Q4：分支规划能处理"连续的"意图（如他车减速的程度连续可变）吗？ 直接处理连续意图就回到了 U2/U3（连续不确定性）。分支规划的设计前提是**离散少数模态**。若意图本质连续，可离散化成几个代表模态（如"急让 / 缓让 / 不让"）再分支——但离散化太细就失去分支的意义，该考虑 multi-stage NMPC 的连续值离散化或直接用 U3。
Q5：为什么不直接解完整 POMDP？ POMDP 理论上最优地处理意图不确定性（U4 详解），但精确求解随状态 / 观测 / 时域指数爆炸，跑不到实时。EUDM/EPSILON 把 POMDP 用"引导分支"（DCP-Tree + CFB）裁剪到可实时，是**近似但实用**的 POMDP 解法。要完整 POMDP 处理 → U4。
Q6：共享干越长越安全吗？ 不是。共享干太长 → 所有场景被迫共用很长一段动作 → 过度保守、逼近 frozen。共享干的"理想长度"是"信息揭示时刻"（MARC 用 Wasserstein 动态找它）。安全靠"覆盖危险模态 + 分支留出路",不靠共享干长度。
Q7：分支规划和博弈规划（Nash / Stackelberg）什么关系？ 分支规划把他车意图当**外生情景**（给定 \(\omega_k\) 与概率，他车不随 ego 策略改变其意图分布）；博弈规划把他车当**理性玩家**（他车也在最优反应 ego）。Contingency Games（§前沿）是两者的结合。一般：交互弱 / 他车不太反应 → 分支够用；交互强（你来我往的博弈）→ 需要博弈规划。
Q8：IDM/MOBIL 是必须的吗？能用学习的行为模型吗？ 不是必须。IDM/MOBIL 是闭环前向仿真的一种简单反应模型，可换成学习的行为模型（如 Contingencies from Observations 学到的模型，§前沿）。EPSILON 还加了"安全机制"对冲简单模型的失配。前向仿真的核心是"闭环交互",用什么模型是可替换的。
本章常见误解汇总¶
| 误解 | 正确理解 |
|---|---|
| 分支规划 = 为每个场景各跑一个独立 MPC | 必须有**共享干（非预期约束）**把各场景的当前动作绑成一个，否则退回振荡（§U1.1） |
| 分支越多（\(K\) 越大）越安全 | \(K\) 是计算成本主因；安全靠覆盖危险模态，用 CFB 筛选而非盲目加 \(K\)（§U1.1/§U1.3） |
| 共享干越长越安全 | 太长则过度保守、逼近 frozen；理想长度是信息揭示时刻（MARC 动态找，§U1.5） |
| MPDM 在预测他车精确轨迹 | MPDM 预测**离散策略概率**，轨迹由 IDM/MOBIL 在闭环仿真里跑出（§U1.2） |
| 用开环仿真评估策略就行 | 必须**闭环**（ego 与他车互相反应），否则漏掉交互、并线类场景评估失真（§U1.2） |
| DCP-Tree 枚举的是他车意图 | DCP-Tree 展开 ego 策略序列；他车意图分支是 CFB 的事（§U1.3） |
| 一周期一次切换会错过复杂机动 | 滚动重规划让复杂机动跨多个周期自然涌现，表达能力不丢（§U1.3） |
| CVaR 就是最坏情况 | CVaR\(_\alpha\) 是最坏 \((1-\alpha)\) 尾部的平均，\(\alpha\) 可调，比纯最坏温和（§U1.5） |
| scenario tree NMPC 与 contingency planning 是两回事 | 数学**严格同构**（共享干=非预期约束、分支=场景枝），只是社区与语言不同（§U1.6） |
| 分支规划是简化版 MCTS | 是不同设计取舍（固定宽度 + 无反传换实时 + 可解释），非 MCTS 的退化（§U1.7） |
| robust horizon 越长越鲁棒 | 它是复杂度的指数因子；常取 1–2 + 滚动重规划（理论补遗） |
本章小结¶
本章把"赌一个最可能的未来"升级成"为多个离散未来分别准备策略"。主线是 U0 安全谱思想：当不确定性是**离散多模态意图**（而非连续抖动）时，用"共享干 + 加权分支"——当前下一个对所有未来都安全的动作，等信息揭示后再分叉优化。
一条主线回顾：一个概念串起全章¶
如果只带走一个东西，应该是：分支规划 = 共享干 + 加权分支。
- 共享干（非预期约束）统一了全章：它是"在信息揭示前，当前动作对所有场景必须相同"——MPDM 选一个语义策略、EUDM 的 DCP-Tree 一周期一次切换、multi-stage NMPC 的非预期约束、MARC 的延迟分支，本质都是它。共享干治"决策振荡"（短期一致）。
- 分支治"frozen robot"：为每个离散未来各留一条独立出路，不必对所有可能都悲观避让。
- 三个旋钮贯穿全章：分支点 \(t_{\text{branch}}\)（最关键，MARC 用 Wasserstein 动态定）、分支数 \(K\)（EUDM 用 CFB 压）、场景概率 \(P(\omega_k)\)（预测器给）。
- 与 U2/U3 正交：分支处理"哪个未来"（离散意图），U2/U3 的收紧处理"该未来内多大扰动"（连续），可嵌套叠加。
所以这一章不是几个孤立算法，而是**"共享干 + 加权分支"这一思想在不同求解范式上的化身**：枚举 + 仿真（MPDM/EUDM/EPSILON）、联合 NLP（multi-stage NMPC）、风险感知（MARC）、搜索（MCTS 对比）。遇到一个新的分支方法，先问：场景怎么枚举 / 采样？分支点放哪？代价怎么加权（期望 / CVaR）？共享干怎么实现？
术语速查表¶
| 术语 | 一句话定义 |
|---|---|
| 分支 / contingency 规划 | 为多个离散未来情景分别准备策略，共享当前动作、未来分叉优化 |
| 共享干（shared trunk） | 分支点之前所有场景共用的那段控制 |
| 非预期约束（non-anticipativity） | 信息揭示前各场景控制必须相同的约束（共享干的形式化） |
| 分支点 \(t_{\text{branch}}\) | 共享干结束、各场景开始独立优化的时刻 |
| frozen robot | 单轨迹规划对悲观预测无解、机器人僵住的失败模式 |
| 决策振荡 | 单轨迹规划随预测翻转而反复横跳的失败模式 |
| MPDM | 多策略决策：枚举语义策略 + 闭环前向仿真评估选最优 |
| IDM | 智能驾驶员模型，纵向跟车的反应式加速度模型 |
| MOBIL | 换道决策模型（安全准则 + 激励准则 + 礼让系数） |
| DCP-Tree | 领域专属闭环策略树（展开 ego 策略序列，一周期\(\le\)1次切换） |
| CFB | 条件聚焦分支（只对危险交互的他车枚举意图） |
| EUDM | 高效不确定性感知决策（DCP-Tree + CFB，行为决策层） |
| SSC | 时空语义走廊（凸多面体序列 + 走廊内 QP，运动规划层） |
| EPSILON | EUDM + SSC 的完整分层系统（POMDP 形式化 + 引导分支） |
| ego-centric belief | 只对 ego 关心的交互车维护意图信念 |
| MARC | 多策略 + 风险感知 contingency（动态分支点 + CVaR） |
| 场景级 divergence | 用 Wasserstein 距离度量各场景轨迹"何时显著分叉",据此动态定分支点 |
| CVaR\(_\alpha\) | 最坏 \((1-\alpha)\) 尾部的平均损失（风险度量，\(\alpha\) 可调） |
| Multi-stage NMPC | 化工社区的场景树鲁棒 NMPC，与 contingency 数学同构 |
| scenario tree | 场景树：在 robust horizon 内对不确定性分叉的预测树 |
| robust horizon \(N_r\) | 场景树分叉的步数（之后参数固定），控制复杂度的旋钮 |
| MCTS | 蒙特卡洛树搜索：UCB 自适应展开 + rollout + 反向传播 |
知识点总表¶
| 方法 | 核心思想 | 分支点 | 代价 | 求解 | 工程定位 |
|---|---|---|---|---|---|
| 基本形式化（§U1.1） | 共享干 + 加权分支 | 旋钮 | 场景加权期望 | — | 全章地基 |
| MPDM（§U1.2） | 策略枚举 + 闭环前向仿真 | 固定 | 期望 | 枚举 + 仿真 | 入门、可解释 |
| EUDM（§U1.3） | DCP-Tree + CFB 压复杂度 | 固定（2s 节点） | 期望 | 引导分支 | 实时（50–100ms） |
| EPSILON（§U1.4） | EUDM + SSC 分层系统 | 固定 | 期望 | 行为 + 运动两层 | 完整开源系统 |
| MARC（§U1.5） | 动态分支 + CVaR | 动态（Wasserstein） | CVaR\(_\alpha\) | 双层优化 | 风险敏感、动态分支 |
| Multi-stage NMPC（§U1.6） | 场景树 + 非预期约束 | robust horizon | 期望 | 联合 NLP | 连续控制、理论完备 |
| vs MCTS（§U1.7） | 固定宽度树 vs UCB 自适应 | — | — | 枚举 vs 搜索 | 结构对比 |
本章核心公式速查¶
| 公式 | 表达式 | 出处 |
|---|---|---|
| 分支规划形式化 | \(\min \sum_k P(\omega_k)J(u_{\text{trunk}},u_k;\omega_k)\) s.t. 共享干 + 分支 + 非预期约束 | §U1.1 |
| 非预期约束 | \(u_i(0{:}t_{\text{branch}})=u_j(0{:}t_{\text{branch}})\ \forall i,j\) | §U1.1 |
| IDM 加速度 | \(\dot v=a\big[1-(v/v_0)^4-(s^*/s)^2\big]\) | §U1.2 |
| IDM 期望间距 | \(s^*=s_0+\max\!\big(0,\,vT+\tfrac{v\Delta v}{2\sqrt{ab}}\big)\) | §U1.2 |
| MOBIL 激励准则 | \((a^{\text{new}}_{\text{ego}}-a^{\text{old}}_{\text{ego}})+p\sum(a^{\text{new}}-a^{\text{old}})_{\text{others}}>\Delta a_{\text{th}}\) | §U1.2 |
| MOBIL 安全准则 | \(a^{\text{new}}_{\text{back}}\ge -b_{\text{safe}}\) | §U1.2 |
| MPDM 复杂度 | $O( | \Pi_{\text{ego}} |
| CVaR（Rockafellar–Uryasev） | \(\mathrm{CVaR}_\alpha=\min_t\{t+\tfrac{1}{1-\alpha}\mathbb{E}[(L-t)_+]\}\) | §U1.5 |
| 场景树叶子数 | \(d^{N_r}\)（\(d\) = 每步分支因子，\(N_r\) = robust horizon） | §U1.6 |
本章符号速查¶
| 符号 | 含义 | 备注 |
|---|---|---|
| \(\omega_k\) | 第 \(k\) 个离散未来情景（他车意图 / 参数实现） | \(k=1,\dots,K\) |
| \(P(\omega_k)\) | 情景 \(\omega_k\) 的概率 | \(\sum_k P(\omega_k)=1\) |
| \(K\) | 分支（情景）数 | EUDM 用 CFB 压到 3–8 |
| \(u_{\text{trunk}}\) | 共享干控制（分支前各场景共用） | 非预期约束的对象 |
| \(u_k\) | 第 \(k\) 个分支的控制 | 分支后各自独立 |
| \(t_{\text{branch}}\) / \(N_{\text{trunk}}\) | 分支点 / 共享干步数 | 最关键旋钮 |
| \(J(\cdot;\omega_k)\) | 情景 \(\omega_k\) 下的代价 | 含安全 / 效率 / 舒适 |
| \(\Pi_{\text{ego}},\Pi_{\text{other}}\) | ego / 他车候选语义策略集 | MPDM |
| \(v_0,a,b,s_0,T\) | IDM 五参数 | 期望速度 / 最大加速 / 舒适减速 / 最小间距 / 车头时距 |
| \(s,\Delta v,s^*\) | 实际间距 / 接近速度 / 期望间距 | IDM |
| \(p\) | MOBIL 礼让系数 | \(\in[0,1]\) |
| \(n\) | 相关他车数 | MPDM 复杂度指数 |
| \(\alpha\) | CVaR 置信水平 | \(\in[0,1]\)，与 U2 CBF 的 class-K 函数 \(\alpha(\cdot)\) 区分（见 U0 符号表） |
| \(N_r\) | robust horizon（场景树分叉步数） | multi-stage NMPC |
| \(d\) | 每步分支因子 | 场景树叶子数 \(d^{N_r}\) |
| \(d_{\text{safe}}\) | 安全间距 | 碰撞约束 |
与 U0 符号表的衔接：本章沿用 U0 的 \(x,u,\pi,J,\delta\) 等；新增 \(\omega_k\)（情景）、\(u_{\text{trunk}}\)（共享干）、\(t_{\text{branch}}\)（分支点）、IDM/MOBIL 参数。注意 \(\alpha\) 在本章是 CVaR 置信水平（标量），与 U2 CBF 的 class-K 函数 \(\alpha(\cdot)\) 严格区分。
实践索引与一页纸总览¶
我想……→ 看这里：
- 理解分支规划到底解决什么 → §U1.1 动机 + 反面（frozen / 振荡）
- 写出形式化（共享干 + 分支）→ §U1.1 理论 + 本章核心公式速查
- 实现 IDM 跟车 → §U1.2 + 实现二 idm_accel
- 实现 MPDM 选策略 → §U1.2 + 实现二 mpdm_select
- 实现 contingency QP（共享干 + 分支）→ 实现一 contingency_mpc_long
- 理解 EUDM 怎么压复杂度 → §U1.3（DCP-Tree + CFB）
- 理解完整系统怎么搭 → §U1.4（EPSILON = EUDM + SSC）
- 处理动态分支点 / 风险 → §U1.5（MARC）
- 用 do-mpc / acados 做场景树 → §U1.6 + API 速查
- 选哪种方法 → 方法选型决策指南
- 调 frozen / 振荡 / 超时 → 调参速查 + 故障排查手册
- 上车部署 → 从 Python 到 C++ 部署 + 综合实战清单
一页纸总览：
问题: 未来是离散多模态(他车意图/对手机动/落足点), 且揭示有延迟
│
├─ 不要赌一个 → frozen(全避让无解) 或 振荡(随预测翻转)
│
解法: 共享干 + 加权分支
min Σ_k P(ω_k)·J(u_trunk, u_k; ω_k)
s.t. 共享干 u(t0:t_branch) 对所有 ω_k 相同(非预期约束) ← 治振荡
分支 u(t_branch:T, ω_k) 各自优化 ← 治 frozen
│
三旋钮: t_branch(最关键,MARC动态) / K(EUDM用CFB压) / P(ω_k)(预测器)
│
方法谱:
枚举+仿真 ── MPDM(策略+IDM/MOBIL) → EUDM(DCP-Tree+CFB) → EPSILON(+SSC)
联合 NLP ── Multi-stage NMPC(场景树, 与上严格同构) [do-mpc/acados]
风险感知 ── MARC(动态分支 + CVaR)
搜索对比 ── MCTS(UCB自适应, 弱先验) ↔ 神经分支/belief MCTS(收敛中)
│
与 U2/U3 正交: 分支管"哪个未来", 收紧管"该未来内连续扰动"(可嵌套)
延伸阅读¶
出处已逐一核实。难度：⭐⭐ 入门精读，⭐⭐⭐ 需相应基础，⭐⭐⭐⭐ 研究级。
奠基与核心（分支 / contingency 规划） - J. Hardy, M. Campbell. "Contingency Planning Over Probabilistic Obstacle Predictions for Autonomous Road Vehicles." IEEE Transactions on Robotics, 29(4):913–929, 2013. DOI: 10.1109/TRO.2013.2254033. ⭐⭐⭐（分支规划奠基：优化型规划器同时优化多条 contingency 路径 + 碰撞概率界 + 障碍轨迹聚类） - A. G. Cunningham, E. Galceran, R. M. Eustice, E. Olson. "MPDM: Multipolicy Decision-Making in Dynamic, Uncertain Environments for Autonomous Driving." ICRA 2015. DOI: 10.1109/ICRA.2015.7139412. ⭐⭐⭐（MPDM：策略枚举 + 闭环前向仿真）
HKUST 三部曲（EUDM → EPSILON → MARC） - L. Zhang*, W. Ding*, J. Chen, S. Shen. "Efficient Uncertainty-aware Decision-making for Automated Driving Using Guided Branching." ICRA 2020. arXiv:2003.02746. ⭐⭐⭐（EUDM：DCP-Tree + CFB；code: HKUST-Aerial-Robotics/eudm_planner） - W. Ding*, L. Zhang*, J. Chen, S. Shen. "EPSILON: An Efficient Planning System for Automated Vehicles in Highly Interactive Environments." IEEE Transactions on Robotics, 38:1118–1138, 2021. DOI: 10.1109/TRO.2021.3104254, arXiv:2108.07993. ⭐⭐⭐⭐（EPSILON：EUDM + SSC 完整系统；code: HKUST-Aerial-Robotics/EPSILON, GPLv3） - W. Ding, L. Zhang, J. Chen, S. Shen. "Safe Trajectory Generation for Complex Urban Environments Using Spatio-temporal Semantic Corridor." IEEE Robotics and Automation Letters, 4(3):2997–3004, 2019. ⭐⭐⭐（SSC：时空语义走廊 QP） - T. Li, L. Zhang, S. Liu, S. Shen. "MARC: Multipolicy and Risk-aware Contingency Planning for Autonomous Driving." IEEE Robotics and Automation Letters, 2023. arXiv:2308.12021. ⭐⭐⭐⭐（MARC：场景级 Wasserstein 动态分支 + CVaR 双层）
Multi-stage NMPC（同构的过程控制视角）
- S. Lucia, T. Finkler, S. Engell. "Multi-stage Nonlinear Model Predictive Control Applied to a Semi-batch Polymerization Reactor under Uncertainty." Journal of Process Control, 23(9):1306–1319, 2013. ⭐⭐⭐⭐（multi-stage NMPC：scenario tree + 非预期约束 + robust horizon；与 contingency 数学同构）
- do-mpc 文档与教程（do-mpc/do-mpc，Python）。⭐⭐（multi-stage NMPC 实现，set_uncertainty_values 场景树）
反应式交通模型（前向仿真用） - M. Treiber, A. Hennecke, D. Helbing. "Congested Traffic States in Empirical Observations and Microscopic Simulations." Physical Review E, 62(2):1805–1824, 2000. ⭐⭐⭐（IDM 原始论文） - A. Kesting, M. Treiber, D. Helbing. "General Lane-Changing Model MOBIL for Car-Following Models." Transportation Research Record, 1999:86–94, 2007. ⭐⭐⭐（MOBIL 换道模型）
前沿（2021–2024，方向迁移与学习 / 博弈 / 采样化） - E. Trevisan, J. Alonso-Mora. "Biased-MPPI: Informing Sampling-Based Model Predictive Control by Fusing Ancillary Controllers." IEEE Robotics and Automation Letters, 9(6):5871–5878, 2024. DOI: 10.1109/LRA.2024.3397083. ⭐⭐⭐⭐（采样式 MPC 的分支 / 引导基础） - L. Peters, A. Bajcsy, C.-Y. Chiu, D. Fridovich-Keil, F. Laine, L. Ferranti, J. Alonso-Mora. "Contingency Games for Multi-Agent Interaction." IEEE Robotics and Automation Letters, 9(3):2208–2215, 2024. ⭐⭐⭐⭐（博弈式 contingency） - K. A. Mustafa, D. Jarne Ornia, J. Kober, J. Alonso-Mora. "RACP: Risk-Aware Contingency Planning with Multi-Modal Predictions." arXiv:2402.17387, 2024. ⭐⭐⭐⭐（风险感知 + 多模态预测驱动的 contingency） - N. Rhinehart, J. He, C. Packer, M. A. Wright, R. McAllister, J. E. Gonzalez, S. Levine. "Contingencies from Observations: Tractable Contingency Planning with Learned Behavior Models." ICRA 2021. ⭐⭐⭐⭐（从观测学行为模型做 contingency） - O. de Groot, L. Ferranti, D. Gavrila, J. Alonso-Mora. Topology-driven MPC（T-MPC，拓扑等价类并行轨迹分支）相关工作。⭐⭐⭐⭐（分支维度 = 轨迹拓扑）
教材 / 综述（建立体系）
- M. J. Kochenderfer 等. Algorithms for Decision Making（MDP/POMDP/不确定性决策统一教材，开放获取）。⭐⭐
- highway-env（eleurent/highway-env，Python/Gym）——分支规划的轻量测试环境。⭐⭐
注：本章不引用具体 star / 引用数（随时间变动、不可精确核实）。各 HKUST 工作的作者顺序以论文为准（EUDM 为 Zhang*/Ding* 等额贡献、EPSILON 为 Ding*/Zhang* 等额贡献）。
综合练习与项目挑战¶
跨章综合题（综合 U0–U3 与本章）：
- [跨章·分支 \(\times\) 机会约束] 在累积项目里，给
BranchNavModule的每条分支内部叠加 U3 的机会约束——障碍位置带高斯不确定 \(\Sigma_o\)，每条分支用 \(\Phi^{-1}(1-\delta)\sqrt{\cdot}\) 收紧。写出"离散意图分支 + 分支内连续机会约束"的联合形式，并说明这正是 U0 §3 "范式可叠加"的体现。 - [跨章·分支 vs 鲁棒] 同一个"动态障碍可能横穿"的场景，分别用 (a) U2 的鲁棒 Tube（把障碍可达集当有界扰动避让）和 (b) 本章的分支规划。对比两者的保守度与 frozen 倾向。说明何时该用哪个（提示：障碍意图离散且揭示有延迟时分支更优）。
- [跨章·安全谱定位] 把本章的分支规划放回 U0 的五安全谱，说明它处理的是哪一类不确定性（环境 / 交互端离散多模态），与 U2（执行端有界）、U3（执行端概率）、U4（感知端认知）、U5（尾部风险）的分工。画一张"不确定性来源 → 推荐范式"的对照图。
项目挑战：
- [项目·完整分支规划器] 按"综合实战清单"八步，在 highway-env 的 merge 场景搭一个完整分支规划器（MPDM 行为层 + contingency QP 运动层）。交付：(1) frozen / 振荡的 baseline 复现；(2) 分支规划的改善对比；(3) 扫 \(N_{\text{trunk}}\) 的保守度曲线。
- [项目·MARC 化] 在挑战 4 基础上，把期望加权换成 CVaR（扫 \(\alpha\)）、把固定分支点换成动态（轨迹分叉处）。对比 EPSILON 风格 vs MARC 风格在"罕见危险场景"下的表现。
- [项目·机器人侧迁移] 把 contingency MPC 迁移到一个机器人场景（无人机躲"可能左 / 右转"的障碍，或多足"踩 A / B 石头"）。验证相比单轨迹 MPC 在 frozen / 振荡上的改善——这填补 §前沿"机器人侧分支规划"的空白。
本章各节关系¶
| 小节 | 与本章其他节 / 其他章的关系 |
|---|---|
| §U1.1 基本形式化 | 全章地基；共享干 + 分支 + 非预期约束被后续所有方法复用；非预期约束续 U2 场景树 MPC |
| §U1.2 MPDM | 形式化的"枚举 + 仿真"实例；IDM/MOBIL 被 EUDM/EPSILON 的前向仿真复用；复杂度问题引出 §U1.3 |
| §U1.3 EUDM | 解决 §U1.2 的组合爆炸（DCP-Tree + CFB）；是 §U1.4 EPSILON 的行为层 |
| §U1.4 EPSILON | EUDM（§U1.3）+ SSC 的完整系统；分层思想呼应 U2 §U2.5（MPC + CBF 分层） |
| §U1.5 MARC | 改进 EUDM/EPSILON 的固定分支点（动态）与期望代价（CVaR）；CVaR 续 U0 §3 / U3 进阶十、接 U5 |
| §U1.6 Multi-stage NMPC | 揭示 §U1.1 形式化与化工场景树 NMPC 的同构；非预期约束 / robust horizon 续 U2 场景树 MPC |
| §U1.7 vs MCTS | 把分支规划放进"搜索式规划"谱系对比；belief MCTS 接 U4 |
| 全章 | 上承 U0（五安全谱的分支端、交互端离散多模态）；与 U2/U3 正交（分支管离散意图、收紧管连续扰动，可嵌套）；下接 U4（POMDP 完整处理意图、主动感知）、U5（CVaR 风险，MARC 已预览） |
本章与后续章节的关系¶
上一节的"本章各节关系"梳理章内脉络；这里专门列出本章如何为后续章节铺垫。
| 后续章节 | 关系 | 本章铺垫的知识点 |
|---|---|---|
| U4 POMDP / Belief 规划 | 本章把意图不确定性**形式化为 POMDP 但用引导分支近似求解**（EUDM/EPSILON）；U4 正面处理 POMDP（belief 更新、主动感知、POMCP/DESPOT）。本章的"ego-centric belief""引导分支"是 U4 的实用前奏 | POMDP 形式化、意图作隐变量、引导分支 vs 完整求解、belief MCTS（§U1.7） |
| U5 风险敏感 / CVaR | 本章 MARC 已用 CVaR 给场景代价做风险加权（§U1.5）；U5 系统展开 CVaR、风险度量、分布鲁棒。本章是 CVaR 的第一次"实战应用" | CVaR\(_\alpha\) 定义与 Rockafellar–Uryasev 形式、风险敏感 vs 风险中性、尾部 vs 期望 |
| 附录（基准与对照） | 把分支规划与 U2/U3/U4/U5 各范式放同一测试台横向 benchmark | 累积项目 BranchNavModule、单轨迹 vs 分支对比、安全谱定位 |
一句话：本章是不确定性规划"交互 / 环境端、离散多模态"这一极的支柱。它向 U4 输出"把意图不确定性当 POMDP 但用分支近似"的实用路线（U4 再给完整 POMDP 解法），向 U5 输出 CVaR 的首个实战（MARC），并与 U2/U3 的连续不确定性处理正交互补、可嵌套叠加——五条安全谱至此各就各位。
研究与实践建议¶
给工程师：先在累积项目（或 highway-env merge）把"单轨迹 baseline → 复现 frozen / 振荡 → MPDM 化解 → contingency QP 出轨迹"这条路走通——你会亲眼看到共享干怎么治振荡、分支怎么治 frozen。工程落地优先级：先 MPDM/EUDM 风格（可解释、易调试、有 EPSILON 现成参考），再按需上 SSC 运动层、CVaR 风险、动态分支。务必记住三句：非预期约束加在控制上、\(K\) 用 CFB 筛关键车、分支点是最关键旋钮。
给研究者：本章是 Part-U 里"自驾成熟、机器人侧空白"的一章，四个方向有明确可发表 / 可开源空间：(1) 机器人侧分支规划（无人机追逃 / 多足地形 / 人机协作的 contingency，几乎空白）；(2) 分支点的学习与保证（MARC 的 Wasserstein 是启发式，缺"何时分支才最优 / 才安全"的理论）；(3) 离散分支 + 连续鲁棒的统一框架（分支 \(\times\) 机会约束 / Tube 的嵌套，工程常见但理论未打通）；(4) 采样化 / 博弈化 / 神经化分支（Biased-MPPI / Contingency Games / 学习分支点）。其中机器人侧迁移门槛相对低（本章给了可运行骨架）、影响力大，最适合学生起步。
给初学者的学习路径：建议"先拿直觉、再补方法、最后上手"。第一步只读 §U1.1（形式化 + frozen / 振荡）+ 实现一的数值走查（共享干越长越保守），把"共享干 + 加权分支"主线建起来。第二步读 §U1.2（MPDM + IDM/MOBIL），把"枚举 + 闭环仿真"吃透——这是分支规划最直观的实例。第三步动手：先写 IDM 跟车，再写 MPDM 选策略（实现二），最后跑 contingency QP（实现一）。§U1.3–U1.6（EUDM/EPSILON/MARC/multi-stage）作为进阶，§U1.7（vs MCTS）按兴趣读。
学完本章你应当能：写出分支规划的形式化（共享干 + 加权分支 + 非预期约束）；实现 IDM 跟车与 MPDM 策略选择；用场景树 QP 输出共享干 + 分支轨迹；说清 EUDM 如何压复杂度、EPSILON 如何分层、MARC 如何动态分支 + 风险感知、multi-stage NMPC 为何与 contingency 同构、分支规划与 MCTS 的结构差异；并对一个新的"离散多模态不确定性"问题给出有理有据的方法选型。带着这些，你可以进入 U4（POMDP / 主动感知 / belief 空间）与 U5（CVaR / 风险敏感 / 分布鲁棒）。
版本信息速查¶
本章代码以 Python 原型为主。下表汇总所基于的主流库 / 框架版本（版本号为**建议最低值**，向后兼容多数更高版本；实际以你的环境为准）与各核心方法的出处年份。方法年份与出处已在"延伸阅读"逐一核实。
库 / 框架版本（指示性最低值）
| 库 / 框架 | 建议版本 | 本章用途 |
|---|---|---|
| Python | 3.10+ | 原型语言 |
| NumPy | 1.24+ | IDM/MOBIL 仿真、轨迹运算 |
| CVXPY | 1.4+ | 场景树 contingency QP 建模 |
| OSQP | 0.6+ | QP 后端（contingency MPC） |
| do-mpc | 4.5+ | multi-stage NMPC / 场景树（§U1.6） |
| CasADi | 3.6+ | do-mpc / acados 的符号建模后端 |
| acados | 0.3+ | Multi-Phase OCP 做场景树（§U1.6，可选） |
| highway-env | 1.8+ | 分支规划的轻量测试环境（merge / 路口） |
| EPSILON | — | 行为 + 运动完整系统（C++/ROS，源码精读，随仓库版本） |
核心方法出处年份（已核实）
| 方法 | 年份 | 出处 |
|---|---|---|
| Contingency planning（奠基） | 2013 | Hardy–Campbell, IEEE T-RO 29(4) |
| MPDM | 2015 | Cunningham–Galceran–Eustice–Olson, ICRA |
| IDM | 2000 | Treiber–Hennecke–Helbing, Phys. Rev. E 62(2) |
| MOBIL | 2007 | Kesting–Treiber–Helbing, Transp. Res. Rec. 1999 |
| EUDM | 2020 | Zhang–Ding–Chen–Shen, ICRA |
| SSC | 2019 | Ding et al., IEEE RA-L 4(3) |
| EPSILON | 2021 | Ding–Zhang–Chen–Shen, IEEE T-RO 38 |
| Multi-stage NMPC | 2013 | Lucia–Finkler–Engell, J. Process Control 23(9) |
| MARC | 2023 | Li–Zhang–Liu–Shen, IEEE RA-L |
| Biased-MPPI | 2024 | Trevisan–Alonso-Mora, IEEE RA-L 9(6) |
| Contingency Games | 2024 | Peters et al., IEEE RA-L 9(3) |
注：本章算法对库版本不敏感（核心是前向仿真、凸 QP、场景树结构）；真正影响结果的是**策略集 / 前向仿真模型是否贴合真实交互**、意图预测概率的质量、以及**分支点 / 共享干长度的整定**，而非具体版本号。
附录：前置自测参考答案¶
回到开头那 5 道自测题，读完全章再核对。
- MPC 优化结构：决策一条控制序列 \(u_{0:N-1}\)，最小化 \(\sum_k\ell(x_k,u_k)+\ell_f(x_N)\)，s.t. \(x_{k+1}=f(x_k,u_k)\)、\(x_k\in\mathcal{X}\)、\(u_k\in\mathcal{U}\)、\(x_0\) 给定，施加首控制后滚动重解。它假设**未来是一条确定轨迹**（沿名义动力学）——本章正是放松这一假设，把"一条轨迹"升级成"一棵分支轨迹树"。
- 非预期约束：在不确定性揭示前，各场景必须共用同一控制（你此刻分不清是哪个场景）。U2 场景树 MPC 里写成 \(u_j^{(0)}=u_{j'}^{(0)}\ \forall j,j'\)（第一步控制对所有场景相同）。本章把它做成"共享干",是分支规划的灵魂（§U1.1）。
- 只赌最可能的风险：若赌"它让行"而它实际抢行 → 可能碰撞；若每帧赌不同 → 决策振荡（加速 / 刹车横跳）；若对所有可能都悲观避让 → frozen（僵住）。分支规划用"共享干 + 分支"同时治这几个病（§U1.1）。
- POMDP：状态 \(x\) 不可直接观测，只能通过观测 \(o\) 维护信念 \(b(x)\)（状态后验分布），在 belief 上做决策。精确求解随状态 / 观测 / 时域指数爆炸，故一般不可行。本章 EUDM/EPSILON 把意图不确定性形式化为 POMDP，但用"引导分支"（DCP-Tree + CFB）近似求解避开爆炸（§U1.4）；U4 给完整解法。
- CVaR：CVaR\(_\alpha\) 是最坏 \((1-\alpha)\) 尾部的平均损失，介于期望（\(\alpha\to 0\)）与最坏情况（\(\alpha\to 1\)）之间的连续旋钮。本章 MARC 用它给场景代价做风险加权，对小概率灾难场景更稳健（§U1.5）；U5 系统展开。
如果这 5 题现在都能流畅作答，你已握住本章全部支柱：MPC 优化结构（升级为轨迹树）、非预期约束（共享干）、意图不确定性的危害（frozen / 振荡）、POMDP（引导分支近似）、CVaR（风险感知分支）。其余方法都是把"共享干 + 加权分支"按不同方式（枚举 / NLP / 风险 / 搜索）组装起来。
结语¶
本章把不确定性规划从"连续扰动"推进到"离散多模态意图"。核心只有一句：未来有 \(K\) 种离散可能时，不要只赌一个——用共享干对所有可能保持短期一致、用分支为每个可能各留一条出路，等信息揭示再承诺。从 Hardy 2013 的奠基、到 MPDM 的策略枚举、EUDM 的引导分支、EPSILON 的完整系统、MARC 的动态分支 + 风险、再到化工社区同构的 multi-stage NMPC——它们都是这一思想的不同化身。
至此，Part-U 的五安全谱已各就各位：U2 鲁棒（执行端有界 100%）、U3 机会约束（执行端概率 \(\delta\)）、U1 分支（交互端离散多模态）。接下来 U4 将正面处理**感知端的认知不确定性**——当状态本身不可直接观测、需要在信念空间规划并主动收集信息时，POMDP 登场（本章的"引导分支"是它的实用前奏）；U5 则深入**尾部风险**——把 MARC 预览的 CVaR 展开成完整的风险敏感与分布鲁棒规划。带着"共享干 + 加权分支"这把钥匙，你已能处理任何"离散多模态 + 揭示有延迟"的决策问题。