G2 实时博弈求解器：iLQGames / ALGAMES / SE-IBR¶
上一章 G1 把零和微分博弈的理论底座打透了——HJI 方程给出全局最优、可达性给出严格安全证书、耦合 Riccati 给出 LQ 博弈的闭式解。 但 G1 末尾也反复强调一件事：HJI 算不动。维度诅咒把网格法卡在约 6 维，而真实的交互场景——三车过路口、多机竞速、人车博弈——动辄十几维。 理论最优却跑不起来，这就是 G2 要解决的全部问题：如何在保留博弈交互结构的前提下，把求解时间压到毫秒级，让博弈规划真正跑在车上？
这一章给出三套主流答案，各有取舍： - iLQGames——把一般非线性博弈在每个时刻局部近似成 LQ 博弈，反复解 G1 那组耦合 Riccati，达到毫秒级实时（论文 14 状态场景滚动时域 <50 ms）；输出反馈 Nash（强），但硬约束处理弱。 - ALGAMES——把广义 Nash 的 KKT 条件当作根搜索问题，用增广拉格朗日严格处理硬约束；输出开环 GNE（约束严），但需高频 MPC 才有反馈效果。 - SE-IBR——在迭代最佳响应里加一个灵敏度项，让求解器主动选"让对手最受限"的均衡；真实四旋翼、Audi TTS 实车都用它落地。
一条贯穿全章的主线是 G1 的耦合 Riccati 如何变成工程：§2.3 的 iLQGames 每一步迭代解的，正是 G1 §1.6 那组方程；§2.4 我们会逐行精读它的 C++ 实现
lq_solver.cc。理解了这条线，你就能把"反馈 Nash"从黑板上的均衡概念，变成一个在 100 Hz MPC 循环里实时输出控制量的求解器。本章是算法工程教学：理论与代码并重，会有大量可运行的 Julia/C++/Python 代码。重心从 G1 的"为什么"转向"怎么实现、怎么调、怎么选型"。
前置自测¶
答不出 ≥ 2 题，建议先补相应前置再读本章。这 5 题对应本章反复用到的前置工具。
- （来自 G1） 写出 \(N\) 人 LQ 博弈的耦合 Riccati 方程，并说明它与单人 LQR 的 Riccati 差在哪一项。给定各 \(P_i\)，反馈增益 \(K_i\) 怎么算？（→ G1 §1.6）
- （来自 G1） 什么是反馈 Nash 均衡？它和开环 Nash 的本质区别是什么？为什么反馈策略在有扰动时更鲁棒？（→ G1 §1.2、§1.4）
- （iLQR / DDP） 单人 iLQR 每步迭代做哪几件事（线性化、二次化、反向 Riccati、前向 rollout）？为什么需要 line search 里的步长 \(\alpha\)？（→ Part 0）
- （优化基础） 写出带不等式约束 \(g(x)\le0\) 的优化问题的 KKT 条件（含互补松弛）。增广拉格朗日法如何处理不等式约束？（→ Part 0）
- （Eigen） Eigen 中固定大小矩阵（
Matrix3d）与动态大小矩阵（MatrixXd）在内存分配上有何区别？块操作.block<r,c>(i,j)做什么？（→ v8 Ch11）
本章目标¶
读完本章，你应当能够：
- 区分均衡概念：说清 Nash 均衡与 Stackelberg 均衡的数学定义、适用场景（对等交互 vs 层级交互），并解释为什么 Stackelberg leader 能"利用先手优势"做得比 Nash 好、代价是什么。
- 吃透 iLQGames：完整写出 iLQGames 的迭代算法，解释它每一步如何把非线性博弈局部化成 G1 的 LQ 博弈、解耦合 Riccati、再前向 rollout，并理解它为什么能达到毫秒级实时。
- 精读 C++ 实现：读懂
ilqgames的lq_solver.cc，指认耦合 Riccati 的反向递推循环、多人 Q/R 矩阵的组装、反馈增益 \(K\) 与前馈 \(k\) 的物理含义。 - 掌握 ALGAMES：说清 ALGAMES 如何把 GNEP 的 KKT 条件堆叠成非线性方程组、用拟牛顿 + 增广拉格朗日求解，并解释它与 iLQGames 在均衡类型、约束处理、信息结构上的根本差异。
- 理解 SE-IBR：解释标准 IBR 为什么没有均衡选择能力，SE-IBR 的灵敏度项 \(\partial u_{-i}^*/\partial u_i\)（KKT 隐函数）如何让它倾向"封堵"对手，以及它在实车竞速上的落地。
- 了解前沿：说清 GFNE 如何严格统一"反馈信息结构 + 约束"、DG-SQP 如何用 SQP 把博弈求解工业化，以及它们解决了前几代的什么遗留问题。
- 会选型：面对一个具体交互场景（路口、竞速、人车、merge），论证该用哪套求解器、为什么，并说清各自的工程代价。
知识导航¶
本章的知识可以挂在一棵以"求解器"为中心的树上。 树根是 G2 的核心问题——"如何把博弈求解实时化"； 树干是三套主流求解器（iLQGames / ALGAMES / SE-IBR）及其理论统一（GFNE / DG-SQP）； 树枝是均衡概念、信息结构、代码实现这些支撑性知识。
博弈求解实时化（保留交互结构 + 毫秒级）
│
┌───────────────────────┼───────────────────────┐
均衡是什么 求解器怎么做 怎么选/怎么落地
│ │ │
§2.1 Nash vs Stackelberg │ §2.8 综合对比与选型
§2.2 开环 vs 反馈 Nash │ ↑
（承 G1，定义解的"目标"） │ │
│ ┌─────────┼─────────┬──────────┐ │
└─────────────→│ │ │ │ │
§2.3 iLQGames §2.5 §2.6 §2.7 │
（反馈Nash· ALGAMES SE-IBR GFNE/ │
毫秒级·弱约束） （开环· （灵敏度· DG-SQP │
│ 硬约束） 封堵） （统一/ │
│ 工业SQP）│
§2.4 ilqgames C++ 源码精读 │
（lq_solver.cc：G1耦合Riccati的工程实现）─┘
一条最重要的线索：G1 §1.6 的耦合 Riccati 是本章的心脏。 §2.3 的 iLQGames 把它包进"线性化—二次化—解耦合 Riccati—rollout"的迭代外壳，§2.4 逐行看它的 C++ 实现。 其余求解器是这条主线的对照与补充：ALGAMES 换一条路（KKT 根搜索而非 Riccati），SE-IBR 换一种均衡选择（灵敏度增强），GFNE/DG-SQP 把理论与工程推到最新。
推荐阅读路径： §2.1→§2.2 先把"我们到底要求什么样的解"定清楚（均衡概念、信息结构），这是理解所有求解器的前提； §2.3→§2.4 是全章重心，iLQGames 算法 + C++ 精读必须吃透（它直接接 G1，也是项目甲本章模块）； §2.5→§2.6 是两条重要的替代/增强路线； §2.7 研究级，时间紧可先速读； §2.8 选型，把全章串成可操作的决策。
本章难度集中在 §2.3–§2.5。若时间紧张，§2.7（GFNE/DG-SQP 的理论细节）可先速读、回头精读。
前置知识桥接¶
本章重度依赖 G1，这里把会反复取用的几个 G1 结论激活一下，读者不必翻回上一章也能跟上。
耦合 Riccati（G1 §1.6，本章心脏）。 \(N\) 人 LQ 博弈——线性动力学 \(\dot x=Ax+\sum_j B_ju_j\)、每人二次代价 \(J_i=\frac12\int(x^\top Q_ix+u_i^\top R_{ii}u_i)\,dt\)——的反馈 Nash 均衡由一组**耦合**的 Riccati 方程给出：
反馈增益 \(K_i=R_{ii}^{-1}B_i^\top P_i\)，策略 \(u_i=-K_ix\)。 关键点：那个求和交叉项 \(-\sum_{j\ne i}(P_jS_jP_i+P_iS_jP_j)\) 把 \(N\) 条方程缠在一起，必须联立求解——这就是"博弈"相对"最优控制"的全部数学增量。 本章 §2.3 的 iLQGames 每一步迭代，解的就是这组方程（离散时间版）；§2.4 看它的 C++ 实现。
反馈 Nash vs 开环 Nash（G1 §1.2）。 开环策略是时间的函数 \(u_i(t)\)（开局算好一条控制序列，之后照着执行）；反馈策略是状态的函数 \(u_i(t,x)\)（每个时刻看当前状态再算控制）。 反馈策略有天然的扰动拒绝能力：状态被扰偏了，反馈律会"看到"并修正，开环律却照旧执行错误的计划。 本章 §2.2 会把这个区别讲深，并说明 iLQGames 输出反馈 Nash（强）、ALGAMES 输出开环 GNE（需高频 MPC 补偿）。
均衡选择是设计决策（G1 §1.1）。 博弈的纳什均衡可能不唯一——路口"你让我"和"我让你"都是合法 Nash，数学不告诉你选哪个。 G1 指出"均衡选择是设计决策"；本章 §2.6 的 SE-IBR 就是一种显式的均衡选择机制（用灵敏度项偏向"封堵"对手的均衡），而 §2.3 末尾会看到 iLQGames 靠初始化隐式地选均衡。
iLQR（Part 0）。 单人 iLQR 反复做四件事：沿名义轨迹把动力学线性化、把代价二次化、反向解 Riccati 得反馈增益、前向 rollout 更新轨迹（带步长 \(\alpha\) 做 line search 防发散）。 本章 §2.3 的 iLQGames 就是 iLQR 的博弈推广——四步骨架完全一样，只把第三步的单人 Riccati 换成 \(N\) 人耦合 Riccati。这个"换内核"的视角是理解 iLQGames 最快的入口。
如果跳过本章会怎样¶
两个具体场景，说明为什么这一章不能跳。
场景一：你想让自动驾驶车在无保护左转时不"僵住"。 G1 §1.1 讲过 frozen robot——把对向车当固定障碍，规划器会判定无安全间隙、原地干等。 要破解它，必须让车在规划时建模"我探一下、对方会让"的交互——这就是博弈规划。 但 G1 的 HJI 算不动（维度太高），你需要的是本章 §2.3 的 iLQGames 或 §2.5 的 ALGAMES：它们能在 10 ms 内解出一个考虑了交互的反馈策略，让车敢于试探、并对人类司机的反应做出实时调整。 跳过本章，你就只有"理论上正确但跑不起来"的 HJI，和"跑得起来但会僵住"的解耦预测-规划——两头不靠。
场景二：你要做多无人机竞速，想让自己的机封堵对手超车。 标准的"预测对手轨迹 + 自己避撞"管线做不出"封堵"这种博弈行为——因为它把对手当成不会对你反应的移动障碍。 要让无人机学会像人类赛车手那样卡位，你需要 §2.6 的 SE-IBR：它的灵敏度项显式地让你的策略偏向"让对手最受限"。 这正是 Spica/Wang 在真实四旋翼和 Audi TTS 上落地的方法。 跳过本章，你写不出有竞争性的对抗策略。
预计阅读时间¶
| 模式 | 时间 | 说明 |
|---|---|---|
| 精读（含跑通 iLQGames.jl + 精读 lq_solver.cc + 实现 SE-IBR） | 35–45 小时（约 3 周） | 完整训练本章目标列出的全部能力 |
| 速读（理解三套求解器脉络，跳过 C++ 精读与 SE-IBR 实现） | 8–10 小时 | 抓住 §2.1–§2.3 + §2.5 + §2.8 主线 |
| 速查（回头查某个算法/API/陷阱） | — | 用章末 API 速查表与故障排查手册定位 |
§2.1 Nash 均衡 vs Stackelberg 均衡 ⭐⭐¶
这一节解决什么问题：在动手写任何求解器之前，先把"我们到底要求什么样的解"定清楚。 博弈的解不是唯一概念——同时决策还是有先后？这个看似抽象的区分，直接决定你该用 iLQGames（Nash）还是 Stackelberg 式规划，也决定了求解器的结构。
动机：路口的两种"谁先谁后"¶
回到 G1 开篇那个无保护左转。 你的车要左转，对向有车直行。 现在问一个 G1 没细究的问题：你和对向车，是"同时"决策，还是有"先后"？
这个问题有两种合理答案，对应两种不同的博弈解：
- 同时决策：你们俩在同一瞬间各自选动作，谁也不先承诺、谁也不等谁。每个人只能基于"对方大概会怎么做"来选自己的最优。这导向 Nash 均衡。
- 有先后：假如你先把车头探进路口、明确公示了"我要左转"的意图，对向车看到后再决定让还是不让。你作为"先动的一方"，可以预判对方的反应、并利用这个预判选一个对自己最有利的公示动作。这导向 Stackelberg 均衡。
这两种建模不是谁对谁错，而是**对应不同的真实交互结构**。 竞速中两架无人机抢同一条线，没有谁天然先谁后——是 Nash。 自动驾驶车面对人类司机，AV 可以主动公示意图、人类被动响应——更像 Stackelberg。 选错了模型，求解器再精确也是答非所问。
反面案例：把"有先后"硬套成"同时"会怎样¶
设想你在做人车交互，真实结构是"AV 公示意图、人类响应"（Stackelberg），但你图省事用了 Nash 求解器。 会发生什么？ Nash 假设双方同时决策、互不让步，求出的均衡里 AV 不会"主动试探"——因为 Nash 框架下没有"我先动、对方会反应"这回事，AV 默认对方的策略是固定的、与自己无关。 结果就是 G1 那个 frozen robot 的变种：AV 不敢探、行为保守而晦涩，错失了"我探一下、人类自然会让"的协调机会。 反过来，竞速场景本是 Nash（对等），你却用 Stackelberg 把自己当 leader、假设对手会乖乖响应你的公示——对手其实根本不买账，你基于错误的"对手会让"预判做出激进抢线，directly 撞上去。 根子都是一样的：均衡概念必须匹配真实的决策时序结构。
历史：Sadigh 2016 的范式转变¶
把 Stackelberg 引入自动驾驶、并产生重大影响的，是 Sadigh、Sastry、Seshia、Dragan 在 RSS 2016（"Planning for Autonomous Cars that Leverage Effects on Human Actions"）的工作。 它的核心洞察，正是 G1 §1.1 三次认知跨越里的第一跨——承认对手是有目标的决策者——并往前推了一步： 传统自动驾驶把人类司机当移动障碍、预测其轨迹然后避让，导致防御性且晦涩的行为； Sadigh 等把人车交互建模成一个**欠驱动动力学系统**——机器人的动作不仅改变自己的状态，还会**改变人类的动作**——并用逆强化学习（IRL）从人类轨迹中学出人类的奖励函数，再让 AV 用 Stackelberg 式的规划**主动影响**人类。 他们的用户研究证实：机器人确实能通过这种规划，引导人类司机做出期望的反应（比如让 AV 先并线）。
这是一次范式转变：从"预测-避让"到"影响-引导"。 它也定义了 G2 的两条主线之一——Stackelberg 式的层级交互（人车），与之并列的是 Nash 式的对等交互（竞速、多车 merge），后者由 §2.3 的 iLQGames 等求解。
理论：两种均衡的数学定义¶
Nash 均衡。 \(N\) 个玩家同时决策，玩家 \(i\) 的策略 \(u_i\)、其余玩家记 \(u_{-i}\)。 一组策略 \((u_1^*,\dots,u_N^*)\) 是 Nash 均衡，当且仅当每个人在他人策略固定时都无法单方面改善自己的代价：
直觉：站在均衡点上，任何人单独偏离都只会让自己更差，所以没人有动机动——这是一个**不动点**。 注意 (2.1) 里每个人面对的 \(u_{-i}^*\) 是固定的：Nash 的精神是"在别人不变的前提下我最优"，所有人同时如此、彼此自洽。
Stackelberg 均衡。 现在引入先后：leader（领导者，记 L）先选策略 \(u_L\) 并公示，follower（跟随者，记 F）看到后做**理性响应**——针对 leader 的选择求自己的最优：
leader 知道 follower 会这样响应，于是它求解一个**双层优化（bilevel optimization）**：在"follower 会最优响应"的约束下，选对自己最有利的公示：
直觉：leader 把 follower 的最优响应 (2.2) 当成一个"函数"嵌进自己的优化 (2.3) 里——它不是在猜 follower 固定会怎么做（那是 Nash），而是在主动**塑造** follower 的反应。
本质洞察（先手优势 = 把对手的最优响应内化为约束）：Nash 和 Stackelberg 的根本差别，在于"对手的策略"在你眼里是什么。 Nash 里它是一个**固定的外生量** \(u_{-i}^*\)（你假设它不变、只优化自己）； Stackelberg 里它是一个**依赖你的内生函数** \(u_F^*(u_L)\)（你知道你一动、它就跟着变，于是主动利用这个反应）。 正是这个"把对手的最优响应内化进自己优化"的动作，给了 leader 先手优势——它能在所有"对手会怎么回应"的可能里，挑一个对自己最好的局面去引导。 但天下没有免费的午餐：这个优势**完全建立在"能准确预测 follower 响应"之上**。预测错了（比如把激进司机当成会让的），先手优势瞬间变成自负的灾难。
两者的数学关系。 Stackelberg 解一般**不在** Nash 均衡集合里——它是一个不同的解概念。 leader 利用先手优势，通常能得到比任何 Nash 均衡**对自己更好**的结果（因为 Nash 是"对手固定"下的最优，而 Stackelberg 是"主动塑造对手"下的最优，后者的可行空间更大）。 代价前面已说：需要准确预测 follower 的响应函数 \(u_F^*(u_L)\)，这在实践中要么靠 IRL 学（Sadigh 2016 的路子），要么靠对 follower 代价的假设——任何偏差都会侵蚀这个优势。
一个算到底的例子：先手优势值多少。 抽象定义之后，用一个最小标量博弈把 Nash 和 Stackelberg 都算到底，看"先手优势"具体值多少。 设两人代价
leader 想让 \(u_L\) 接近 1、且希望 \(u_F\) 小；follower 想让 \(u_F\) 跟住 \(u_L\)。
先算 Nash（同时决策）。 各自对自己的控制求最优，解 (2.1)：
联立得 Nash 均衡 \((u_L^*,u_F^*)=(1,1)\)，此时 leader 的代价 \(J_L=(1-1)^2+1^2=1\)。 注意 Nash 里 leader 只顾把 \(u_L\) 推到 1（让第一项归零），却没考虑这会逼 follower 也跟到 1、害得自己第二项 \(u_F^2=1\) 变大——因为 Nash 框架下 leader 把 \(u_F\) 当外生固定，看不到"我动 \(u_F\) 会跟"。
再算 Stackelberg（leader 先动）。 leader 先求 follower 的响应函数：固定 \(u_L\)，follower 最优是 \(u_F^*(u_L)=u_L\)（从 \(\partial J_F/\partial u_F=0\)）。 leader 把这个响应**代入**自己的代价 (2.3)：
对 \(u_L\) 求最优：\(\frac{d}{du_L}(2u_L^2-2u_L+1)=4u_L-2=0\Rightarrow u_L=0.5\)，于是 \(u_F^*=0.5\)，leader 代价 \(J_L=(0.5-1)^2+0.5^2=0.25+0.25=0.5\)。
对比。 Stackelberg leader 的代价 \(J_L=0.5\)，比 Nash 的 \(J_L=1\) 降低了一半。 这就是先手优势的具体值——leader 因为知道"我把 \(u_L\) 压低一点，follower 会跟着压低、我的第二项 \(u_F^2\) 就小了"，主动选了一个折中的 \(u_L=0.5\)，牺牲第一项一点（\((0.5-1)^2=0.25\)）换第二项大降（\(1\to0.25\)），总代价反而更优。 Nash 看不到这步，因为它把 follower 当固定。 这个算例把本质洞察具体化了：先手优势 = 把 follower 的响应 \(u_F^*(u_L)=u_L\) 内化进自己的优化，于是能主动塑造对自己有利的局面。 这也是规格练习 2 的解答模板。 但别忘了这个 0.5 的优势是有前提的——它假设 follower 真的会按 \(u_F^*(u_L)=u_L\) 理性响应。 如果真实的 follower（人类司机）偏离这个响应（比如根本不让），leader 基于 \(J_L=0.5\) 的乐观预期做出的决策反而可能比保守的 Nash 更糟。 这正是下面陷阱 2 的核心，也是为什么 Sadigh 2016 要用 IRL 去**学**真实的 follower 响应、而非假设它。 换句话说，先手优势的大小，等于你对对手响应模型的准确程度——模型越准，优势越实；模型越虚，优势越可能反噬。
系统性分类：什么场景用哪种均衡¶
系统性分类（按交互的时序结构选均衡概念）：
| 交互结构 | 典型场景 | 该用的均衡 | 本章对应求解器 |
|---|---|---|---|
| 对等、同时（无明确先后） | 无人机竞速、多车 merge、多机协调 | Nash | §2.3 iLQGames、§2.5 ALGAMES、§2.6 SE-IBR |
| 层级、有先后（一方公示、一方响应） | 人车协作、AV 与人类司机、领航-跟随 | Stackelberg | Sadigh 2016 式双层规划；§2.7 部分扩展 |
| 对等但想"软性引导" | 竞速中想封堵对手、但仍是同时决策 | Nash + 均衡选择 | §2.6 SE-IBR（在 Nash 框架内偏向"封堵"） |
注意第三行很微妙——它揭示了一条中间道路： 有时交互结构是对等的（Nash），但你仍想获得类似 leader 的"引导"效果。 SE-IBR（§2.6）正是干这个的：它不改变 Nash 的同时决策结构，而是在均衡选择上做文章，用灵敏度项让求解器偏向"让对手最受限"的那个 Nash——在 Nash 框架内，实现近似 Stackelberg 的封堵行为。 这条中间道路在竞速里特别有用，§2.6 会详谈。
⚠️ 常见陷阱¶
陷阱 1（概念误区）：以为 Stackelberg 解就是"更好的 Nash 解" - 错误描述：觉得既然 leader 能做得比 Nash 好，那 Stackelberg 解一定也是个 Nash 解、只是更优的那个。 - 现象/后果：在 Nash 求解器里找"最优的那个 Nash"，以为能复现 Stackelberg 的引导行为，结果完全做不出主动塑造对手的效果。 - 根本原因：Stackelberg 解一般不在 Nash 集合内——它是不同的解概念。Nash 假设对手策略固定（外生），Stackelberg 把对手响应当成自己可塑造的函数（内生），二者的最优性条件不同。 - 正确做法：先判断交互的时序结构。真有先后（一方能先公示、另一方再响应）才用 Stackelberg 的双层优化 (2.3)；对等同时决策就用 Nash。想在 Nash 框架内要引导效果，用 §2.6 的 SE-IBR，而非"挑个好 Nash"。
陷阱 2（思维陷阱）：无条件相信"先手优势"，忽略对 follower 响应的预测误差 - 错误描述：认为当 leader 总是有利的，公示意图就能引导对方，不去验证对 follower 响应模型的准确性。 - 现象/后果：把不让行的激进司机当成会让的，AV 基于错误预判做出危险抢行；或在对手并不理性响应时，Stackelberg 策略反而比保守的 Nash 更危险。 - 根本原因：Stackelberg 的先手优势完全依赖"准确预测 follower 的最优响应 \(u_F^*(u_L)\)"。这个预测来自对 follower 代价的假设或 IRL 学习，任何偏差都会让 (2.3) 的内层 (2.2) 失真，引导变误导。 - 正确做法：把 follower 响应模型的不确定性显式纳入考量（如对响应做鲁棒化、或在线辨识 follower 代价）。Sadigh 2016 用 IRL 学人类奖励正是为降低这个偏差；不确定性大时，宁可退回更保守的 Nash 或加安全滤波（G4）。
练习¶
- （概念辨析） 对下面四个场景，分别判断该用 Nash 还是 Stackelberg 建模，并说明"谁先谁后"的依据：(i) 两架无人机竞速抢同一弯道；(ii) 高速公路上 AV 想并入人类司机车流；(iii) 十字路口两辆完全对等的自动驾驶车；(iv) 领航车带一队跟随车编队行驶。
- （数学） 设一个标量双人博弈：\(J_L=(u_L-u_F)^2+u_L^2\)、\(J_F=(u_F-u_L/2)^2\)，\(u_L,u_F\in\mathbb{R}\)。（a）求 Nash 均衡（两人同时最优，解 (2.1)）；（b）求以 L 为 leader 的 Stackelberg 解（先求 follower 响应 \(u_F^*(u_L)\)，代入 (2.3) 再对 \(u_L\) 最优）；（c）比较两者下 leader 的代价 \(J_L\)，验证 Stackelberg leader 是否确实不差于 Nash。
- （开放思考） Sadigh 2016 用 IRL 从人类轨迹学出奖励函数，再用 Stackelberg 规划影响人类。如果人类司机其实是"有界理性"的（不完全最优、带随机性），用确定性的 Stackelberg 双层优化会有什么问题？你会怎么改进？（提示：可参考 §2.7 的 MaxEnt Games 思路。）
§2.2 开环 Nash vs 反馈 Nash ⭐⭐⭐¶
这一节解决什么问题：上一节定了"同时还是先后"（Nash vs Stackelberg）。这一节定另一个正交的维度——策略是时间的函数还是状态的函数。 这个区分决定了 iLQGames（反馈）和 ALGAMES（开环）的根本差异，也直接关系到"求出来的解扔到有扰动的真实车上还管不管用"。
动机：算好的控制序列，中途被风吹偏了怎么办¶
设想 iLQGames 或 ALGAMES 替你的车算出了一条与对向车博弈后的最优计划。 这条计划长什么样，有两种本质不同的形态：
- 一串控制量 \(u_i^*(t_0),u_i^*(t_1),\dots,u_i^*(t_{T-1})\)——开局一次性算好、之后逐拍照着执行。这叫**开环（open-loop）**策略。
- 一族反馈律 \(u_i^*(t_k,x)=\bar u_{i,k}+K_{i,k}(x-\bar x_k)\)——每个时刻看**当前实际状态** \(x\) 再算控制。这叫**反馈（feedback）**策略。
两者在**没有扰动、模型完美**时给出完全相同的轨迹。 但真实世界有风、有建模误差、有传感器噪声。 现在问关键问题：执行到一半，一阵侧风把你的车吹偏了 0.5 米，偏离了名义轨迹 \(\bar x_k\)。这两种策略会怎么反应？
- 开环策略：照旧输出 \(u_i^*(t_k)\)——它根本不知道你偏了，因为它只看时间、不看状态。于是误差不被纠正，甚至越积越大。
- 反馈策略：它看到当前状态 \(x\) 比名义 \(\bar x_k\) 偏了 \(\delta x=0.5\) 米，于是输出 \(\bar u_{i,k}+K_{i,k}\cdot\delta x\)——那个 \(K_{i,k}\delta x\) 项就是针对偏差的修正，把车往回拉。
这就是反馈策略"天然抗扰"的来历，也是 G1 §1.2 反复强调过的事，现在我们把它在博弈语境里讲透。
反面案例：用开环 Nash 跑真实车会怎样¶
把一个纯开环 Nash 解直接部署到真实车上，典型故障是这样的： 开环解在仿真里（无扰动）完美——两车流畅地完成 merge，零碰撞。 一上实车，轮胎打滑、风扰、定位漂移让真实状态持续偏离名义轨迹。 开环控制序列对此一无所知，仍按"理想世界"的计划走，于是真实轨迹慢慢偏离、安全间隙被吃掉，原本算好的"零碰撞"变成实际的危险接近甚至剐蹭。 更糟的是博弈耦合放大了这个问题：你偏了、对方的开环计划也没考虑你偏了，两个都不纠偏的计划叠加，误差是相互放大的。
这正是为什么 ALGAMES（输出开环 GNE）必须配高频 MPC 才能上车——下面会解释这个补救机制。
理论：两种信息结构的精确定义¶
信息结构（information structure） 指的是"做决策时能用到什么信息"。这是博弈论里一个精确概念，开环和反馈是它的两种典型。
开环 Nash 均衡（Open-Loop Nash Equilibrium, OLNE）。 每个玩家的策略是**时间的函数**，且只依赖**初始状态** \(x_0\)：
也就是说，玩家在 \(t_0\) 时刻基于 \(x_0\) 把整条控制序列算好，承诺执行、中途不再依据实际状态调整。 满足 Nash 条件 (2.1)：每个人的控制序列在他人序列固定时最优。
反馈 Nash 均衡（Feedback Nash Equilibrium, FBNE）。 每个玩家的策略是**当前时刻状态的函数**：
在 LQ 博弈里（G1 §1.6），这个反馈律有闭式形式 \(u_i^*(t_k,x)=-K_{i,k}\,x\)（或仿射形式 \(\bar u_{i,k}+K_{i,k}(x-\bar x_k)+\alpha k_{i,k}\)，§2.3 会用到）。 满足的是一个更强的条件——子博弈完美（subgame perfect）：不仅在初始时刻是 Nash，从任何中途状态出发的剩余博弈也都是 Nash。
本质洞察（开环承诺一条路，反馈承诺一个规则）：开环与反馈的差别，是"承诺一条轨迹"与"承诺一套应变规则"的差别。 开环玩家说："我会走这条线，不管发生什么。" 反馈玩家说："我会按这个规则应对——你在哪，我就相应地在哪。" 在确定性世界里两者走出的线一样；在有扰动的世界里，反馈的"应变规则"能持续把系统拉回，开环的"固定轨迹"却会放任偏差累积。 这就是为什么 G1 §1.2 说反馈 Nash 在有扰动时严格优于开环——不是它算得更准，而是它**带了纠偏机制**。
把"信息结构"这个抽象概念用一张表钉清楚——它指的是"每个玩家在每个决策时刻能用到什么信息"，开环和反馈是它的两个极端：
| 维度 | 开环 (OLNE) | 反馈 (FBNE) |
|---|---|---|
| 策略形式 | \(u_i(t_k)\)，时间的函数 | \(u_i(t_k, x_k)\)，当前状态的函数 |
| 决策时用到的信息 | 只用初始状态 \(x_0\) + 当前时刻 | 用运行时实际状态 \(x_k\) |
| 何时算好 | \(t_0\) 一次性算好整条序列 | 每个时刻看状态实时算 |
| 对扰动的反应 | 无（照旧执行既定序列） | 有（\(K\delta x\) 项纠偏） |
| 最优性强度 | 仅初始时刻 Nash | 子博弈完美（任意中途状态都 Nash） |
| 对手偏离的预期 | 假设对手雷打不动执行序列 | 预期对手也会随状态调整反馈 |
| 求解结构 | 耦合两点边值问题（PMP 协态） | 耦合 Riccati（值函数对状态求导） |
| 本章对应 | ALGAMES、DG-SQP | iLQGames、GFNE |
这张表把后面所有求解器的"信息结构"那一栏的来源讲清了：iLQGames 解耦合 Riccati（值函数 \(V_i(x)\) 对状态求导，天然得状态反馈）→ 反馈；ALGAMES 解 KKT（控制序列满足一阶最优性）→ 开环。求解结构决定了信息结构，而非反过来。
用数据说话：反馈到底强多少。 这个"反馈抗扰"不是定性的口号，可以量化。 拿 §2.3 那个收敛后的 2 车 iLQGames 解，在前向执行的每一步注入幅值 0.05 的随机扰动（模拟风/打滑/定位漂移），对比两种执行方式 30 次取平均：反馈（用 \(u_{i,k}=\bar u_{i,k}-K_{i,k}\delta x_k-k_{i,k}\)，含 \(K\delta x\) 纠偏项）vs 伪开环（去掉 \(K\delta x\) 项，只用名义控制 \(\bar u_{i,k}-k_{i,k}\)，模拟开环执行）：
| 执行方式 | 平均终点误差 | 平均最小间距 | 最坏情况最小间距 |
|---|---|---|---|
| 反馈 Nash（用 \(K\delta x\) 纠偏） | 1.275 | 0.846 | 0.615 |
| 伪开环（不纠偏） | 2.280 | 0.983 | 0.423 |
反馈把扰动下的平均终点误差从 2.280 降到 1.275——降低了 44%。 更关键的是最坏情况：反馈的最坏最小间距 0.615 比伪开环的 0.423 更安全（伪开环在某些扰动序列下两车危险地靠近）。 这组数字把 §2.2 的核心论点钉死了：反馈那个 \(K\delta x\) 项是真金白银的抗扰能力，不是理论摆设——同一条名义轨迹，带不带反馈纠偏，扰动下的表现差近一半。 这也正是 §2.5 会强调"ALGAMES 开环解必须配高频 MPC"的实证理由：没有反馈纠偏的开环执行，在真实扰动下会显著劣化。
为什么 FBNE 一般不等于 OLNE。 这是个容易被忽略的微妙点：同一个博弈，开环 Nash 和反馈 Nash 的解**一般不同**（即便在 LQ 情形）。 原因在于"对手会不会对我的偏离做出反应"这个预期，被编进了均衡： 反馈博弈里，玩家 \(i\) 知道"如果状态偏了，对手 \(j\) 的反馈律也会相应调整"——这个对手的应变能力，改变了 \(i\) 的最优策略； 开环博弈里，玩家 \(i\) 假设对手会雷打不动执行既定序列，无论状态怎么变。 两种对"对手如何应对未来状态"的预期不同，导致两种均衡不同。 G1 §1.6 那组耦合 Riccati 解的是**反馈** Nash（因为值函数 \(V_i(x,t)\) 是状态的函数，求导得到的是状态反馈）；开环 Nash 则要解一组耦合的两点边值问题（PMP 协态方程联立），结构不同。
对比：信息结构这一维度上的 iLQGames vs ALGAMES¶
把这一节和 §2.1 合起来，能看清两个**正交**的分类维度——"同时/先后"（Nash/Stackelberg）和"反馈/开环"（信息结构）。本章的两大主力求解器在第二个维度上正好分居两端：
对比性思维（反馈 Nash vs 开环 GNE 的工程后果）：
| 维度 | iLQGames（反馈 Nash） | ALGAMES（开环 GNE） |
|---|---|---|
| 策略形式 | \(u_i(t_k,x)\) 状态的函数 | \(u_i(t_k)\) 时间的函数 |
| 抗扰能力 | 强：反馈增益 \(K\) 自动纠偏 | 弱：固定序列不纠偏 |
| 子博弈完美 | 是（任意中途状态都 Nash） | 否（只在初始状态 Nash） |
| 每步子问题 | 耦合 Riccati（解析，§2.3） | KKT 牛顿步（线性系统，§2.5） |
| 上车方式 | 天然反馈，可直接闭环 | 必须配高频 MPC 补偿 |
| 硬约束处理 | 弱（penalty） | 强（AL + 互补，§2.5） |
最后两行揭示了一个深刻的工程权衡，值得单独说： ALGAMES 输出开环解、抗扰弱，但它能**严格处理硬约束**（碰撞、道路边界）；iLQGames 输出反馈解、抗扰强，但**硬约束只能软惩罚**。 两边都有短板，工程上怎么补？
MPC 把开环变"准反馈"。 ALGAMES 的补救是**滚动时域（receding horizon / MPC）：每隔很短的时间（如 16 ms，对应 60+ Hz），用**当前实际状态**重新解一次开环博弈，只执行解出来的第一个控制量，下一拍再用新状态重解。 这样虽然每次解的是开环序列，但因为每拍都用最新真实状态重启，**高频重规划在效果上逼近了反馈——状态偏了，下一拍立刻基于偏后的状态重算。 所以 ALGAMES 上车的标准姿势是"开环求解器 + 60 Hz MPC"，用计算频率换反馈效果。 iLQGames 则因为本身输出反馈律，单次求解就自带纠偏，MPC 频率可以更低（甚至单次规划配反馈跟踪即可）。
多视角理解（MPC ↔ 把开环解"反馈化"）：MPC 在这里扮演的角色，和它在单人最优控制里完全一致——用"高频重规划"把一个开环最优解变成事实上的闭环策略。 相似之处：单人 MPC 也是每拍解一个开环 OCP、只执行第一步、滚动前进，用频率换闭环鲁棒性。 不同之处：博弈 MPC 每拍重解的是一个**多人博弈**（ALGAMES 的 GNEP），计算量比单人 OCP 大得多，所以"能不能在一个控制周期内解完"成了 ALGAMES 能否上车的硬指标——这也是 §2.5 会强调 ALGAMES 做到 60+ Hz 的意义。 一句话：反馈是"解一次、自带纠偏"，MPC 是"频繁重解、逼出纠偏"，两条路殊途同归，但代价结构不同。
代码：MPC 循环把单次求解变闭环¶
前面反复说"开环 + 高频 MPC ≈ 反馈"，落成代码就一目了然。 MPC 循环的骨架极简——每拍用**当前真实状态**重新求解整个博弈、只执行解出来的**第一个**控制量、下一拍再用新状态重解：
# 假设 solve_ilqgames(x0, H) 返回从 x0 出发、时域 H 的整条控制序列（开环计划）
# MPC: 每拍重解、只取第一步、滚动前进
x = x0_init.copy(); traj = [x.copy()]
for k in range(sim_steps):
u_plan = solve_ilqgames(x, H_mpc) # ① 用当前真实状态 x 重新规划
u_now = [u_plan[0][i] for i in range(N)] # ② 只取第一个控制量
x = step(x, u_now) + noise * np.random.randn(nx) # ③ 执行 + 真实扰动
traj.append(x.copy()) # ④ 下一拍用偏移后的新状态重解
关键就在 solve_ilqgames(x, ...) 每拍都吃**最新的 x**——状态被扰动偏了，下一拍的规划立刻基于偏后的状态重启，这就是"高频重规划逼出反馈效果"。
拿它和"单次开环"（开局解一次、之后照着既定序列执行、不重规划）在相同扰动下对比：
| 执行方式 | 两车最小间距 | car1 终点（目标 (0,4)） |
|---|---|---|
| MPC 闭环（每拍重解 + 扰动） | 0.900 | (−0.04, 3.68) ✓ |
| 单次开环（不重规划 + 同扰动） | 0.305 | (−1.07, 4.07) ✗ 明显偏离 |
数字说话：MPC 闭环把最小间距维持在 0.900（接近无扰动时的 0.871），终点也准；单次开环在同样扰动下最小间距骤降到 0.305（危险接近），car1 终点横向偏到 −1.07（跑偏了一米多）。
这就是 §2.5 反复强调"ALGAMES 开环解必须配高频 MPC"的实证——没有重规划，开环计划在扰动下会迅速劣化甚至危险；有了 MPC 每拍重解，开环求解器也能获得接近反馈的鲁棒性。
代价是计算：MPC 闭环跑了 sim_steps 次完整博弈求解，而单次开环只解一次——这正是 §2.2 说的"用计算频率换反馈效果"。
⚠️ 常见陷阱¶
陷阱 1（概念误区）：以为开环 Nash 和反馈 Nash 在 LQ 情形下相同 - 错误描述：觉得既然都是 LQ 博弈、都满足 Nash 条件，开环解和反馈解应该一样。 - 现象/后果：用开环求解器算出的解，去对照反馈求解器的轨迹，发现对不上，误以为某个求解器有 bug，浪费大量时间查错。 - 根本原因：两者的信息结构不同——反馈博弈里玩家预期"对手会对未来状态变化做反应"，开环博弈里玩家假设"对手雷打不动执行既定序列"。这个对对手应变能力的不同预期，使两种均衡一般不同，即便在 LQ 情形。 - 正确做法：明确你要的是哪种均衡再选求解器。要反馈 Nash（抗扰、子博弈完美）用 iLQGames（解耦合 Riccati）；要开环 GNE（约束严格）用 ALGAMES（解 KKT）。不要拿两者的轨迹直接对照期望它们相等。
陷阱 2（思维陷阱）：把开环 GNE 解直接部署到真实系统，不配 MPC - 错误描述：在仿真里 ALGAMES 的开环解完美，就直接把这条控制序列烧进真实车，期望同样表现。 - 现象/后果：实车上扰动、打滑、定位漂移让真实状态偏离名义轨迹，开环序列不纠偏，误差累积，安全间隙被吃掉，仿真里的"零碰撞"变成实车的危险接近。 - 根本原因：开环策略只依赖初始状态和时间、不看运行时状态，没有任何纠偏机制；博弈耦合还会放大误差（双方计划都没考虑对方偏离）。 - 正确做法：开环求解器必须配滚动时域 MPC——每拍用当前实际状态重解、只执行第一步。确保单次求解时间短于控制周期（ALGAMES 做到 60+ Hz 正是为此）。或改用 iLQGames 的反馈解，单次求解即自带纠偏。
练习¶
- （概念） 用自己的话解释，为什么反馈 Nash 满足"子博弈完美"而开环 Nash 不满足。举一个两步博弈的例子：在第一步后状态被扰动偏离，说明反馈策略和开环策略各自如何（不）响应。
- （推导联系 G1） G1 §1.6 的耦合 Riccati 解的是反馈 Nash。请说明：为什么从值函数 \(V_i(x,t)=\frac12 x^\top P_i x\) 出发、对状态求导得到的策略 \(u_i=-K_i x\) 天然是状态反馈而非时间函数？如果改求开环 Nash，方程结构会变成什么（提示：PMP 协态）？
- （工程设计） 你要在一辆真实自动驾驶车上部署 ALGAMES（开环 GNE，严格处理碰撞约束）。请设计完整的上车方案：(a) MPC 频率怎么定（与单次求解时间的关系）；(b) 如果某一拍求解超时没解完，控制器应该怎么办（fallback 策略）；(c) 如何兼顾 ALGAMES 的硬约束优势和反馈的抗扰需求。
§2.3 iLQGames 算法 ⭐⭐⭐ ★ 本章重心¶
这一节解决什么问题：把 G1 的耦合 Riccati 从"黑板上的闭式解"变成"能毫秒级实时跑的求解器"。 iLQGames 是整章的心脏，也是项目甲本章模块的内核——它每一步迭代解的，正是 G1 §1.6 那组方程。 全章若只精读一节，就是这一节。
动机：一般博弈不可解，但 LQ 博弈可解——那就反复 LQ¶
G1 讲清了两件看似矛盾的事： 一般非线性微分博弈没有闭式解、HJI 网格法被维度诅咒卡死（§1.7）； 但 LQ 博弈（线性动力学 + 二次代价）有**闭式**的反馈 Nash 解——那组耦合 Riccati（§1.6）。 矛盾怎么调和？ 答案和单人最优控制里 iLQR 调和"非线性 OCP 难解、LQR 易解"的方式一模一样：反复地把难问题局部近似成易问题。
具体说，iLQGames 的思路是： 在当前猜测的名义轨迹附近，把非线性动力学**一阶 Taylor 展开**成线性、把代价**二阶展开**成二次，得到一个**局部 LQ 博弈**； 解这个 LQ 博弈（耦合 Riccati，G1 §1.6）得到每人的反馈律； 用新策略前向 rollout 出一条更好的轨迹，作为下一轮的名义轨迹； 重复，直到收敛。 这就是 iLQGames——iLQR 的博弈推广。
反面案例：为什么不能"预测对手 + 自己 iLQR"¶
一个看似省事的替代方案：既然 iLQR 能解单人非线性最优控制，那我先用个预测器预测对手轨迹、把它当移动障碍，再对自己跑标准 iLQR——不就把博弈问题"降维"成了单人问题？ 这正是 iLQGames 论文要反对的做法。 它的问题和 G1 §1.1 的 frozen robot 同源：把对手当成不对你反应的固定障碍，切断了交互反馈环。 iLQR 求出的"最优"是针对"对手轨迹固定"的最优——可对手轨迹其实依赖你的策略。 你避让对手算出的轨迹，反过来又会改变对手的最优响应，而你的 iLQR 对此一无所知。 结果是预测与实际脱节：要么过度保守（预测对手不让，frozen），要么过度乐观（预测对手会让，实际抢行撞上）。 iLQGames 的关键改进，就是把"对手也在同时优化"编进求解器——它每步解的是**耦合**的多人 LQ 博弈，所有玩家的反馈增益同时求出、相互依赖，而非各自为政的单人 iLQR。
历史：iLQR → iLQGames¶
iLQGames 由 Fridovich-Keil、Ratner、Peters、Dragan、Tomlin 在 ICRA 2020（"Efficient Iterative Linear-Quadratic Approximations for Nonlinear Multi-Player General-Sum Differential Games"，pp.1475–1481）提出。 它的思想谱系很清晰：单人最优控制里，Mayne 等的 DDP（1960s）与其简化版 iLQR（Li-Todorov 2004、Tassa 等）用"反复 LQ 近似"高效求解非线性 OCP； Fridovich-Keil 等把这一思想搬到博弈——既然 LQ 博弈也有闭式解（G1 §1.6 的耦合 Riccati），那就反复求解局部 LQ 博弈近似。 他们的标志性 demo 是一个三人一般和博弈：两车过十字路口、一行人走人行横道，求解器自动让两车轻微转向互相避让、并给行人留出额外间隙——全程毫秒级实时求解（滚动时域 <50 ms）。 这一工作把博弈规划从"理论可行"推到了"实时可用"，也直接催生了后续的 GFNE（§2.7，把它的反馈结构 + 约束严格化）。
理论：iLQGames 的完整算法¶
把思路落成精确的算法。设 \(N\) 人一般和离散时间博弈：
其中 \(x_k\in\mathbb{R}^{n_x}\) 是所有玩家拼接的状态、\(u_{i,k}\in\mathbb{R}^{n_{u_i}}\) 是玩家 \(i\) 的控制。 iLQGames 迭代如下：
输入：初始名义轨迹 (x̄, ū₁,...,ūN)
重复直到收敛：
① 线性化动力学（沿名义轨迹）：
A_k = ∂f/∂x |_(x̄_k,ū_k), B_{i,k} = ∂f/∂u_i |_(x̄_k,ū_k)
② 二次化代价（沿名义轨迹）：
Q_{i,k}, q_{i,k} = ∇²/∇ ℓ_i 对 x 的二阶/一阶； R_{ii,k}, r_{i,k} 对 u_i
③ 反向递推解耦合 Riccati（G1 §1.6 的离散版）：
从 k=T-1 倒推到 0，每步解一个 N×N 块线性系统，
得到每人的反馈增益 K_{i,k} 和前馈 k_{i,k}
④ 前向 rollout（带步长 α 做 line search）：
从 x₀ 出发，u_{i,k} = ū_{i,k} - K_{i,k}(x_k - x̄_k) - α·k_{i,k}
逐步用 f 推出新轨迹
⑤ 检查收敛（总代价变化 < ε），更新名义轨迹
与 iLQR 的唯一本质区别在步骤 ③。 单人 iLQR 这一步解的是单人 Riccati（一条方程，标量化的反向递推）； iLQGames 解的是 \(N\) 人耦合 Riccati——所有玩家的反馈增益 \(K_{i,k}\) 在每个时间步**同时**求出、相互耦合，对应 G1 §1.6 那个交叉项。 其余四步（线性化、二次化、rollout、收敛检查）与 iLQR 的骨架完全一致。 这就是为什么说"iLQGames = 把 iLQR 的单人 Riccati 换成多人耦合 Riccati"。
步骤 ③ 的离散耦合 Riccati 长什么样。 G1 §1.6 给的是连续时间微分形式 \(-\dot P_i=\dots\)；iLQGames 在离散时间下做反向递推。 设玩家 \(i\) 的值函数（cost-to-go）为 \(V_{i,k}(x)=\frac12 x^\top Z_{i,k}x+\zeta_{i,k}^\top x\)，从终端 \(Z_{i,T}=Q_{i,T}\) 倒推。 在每个时间步 \(k\)，所有玩家的反馈增益由一个**耦合的块线性系统**同时解出（这正是 G1 交叉项在离散时间的体现）：把每个玩家的一阶最优性条件
对 \(i=1,\dots,N\) 堆叠成一个 \(\big(\sum_i n_{u_i}\big)\times\big(\sum_i n_{u_i}\big)\) 的线性系统 \(M\,\mathbf{u}=-(N_x\,x+n)\)，解出 \(\mathbf{u}=-K_k x-k_k\) 中的 \(K_k,k_k\)。 那个矩阵 \(M\) 的非对角块 \(B_i^\top Z_{i,k+1}B_j\,(i\ne j)\) 就是耦合的来源——去掉它，\(N\) 个玩家就退化成各自独立的 LQR 反向递推（即 §2.3 末尾会强调的"独立 iLQR"错误）。 解出 \(K_{i,k},k_{i,k}\) 后，用闭环转移 \(F_k=A_k-\sum_j B_{j,k}K_{j,k}\) 更新每人的 \(Z_{i,k},\zeta_{i,k}\)，继续往前倒推。
本质洞察（iLQGames = iLQR 换内核）：理解 iLQGames 最快的方式，是把它看成 iLQR 做了一处"换心手术"——把反向 pass 里的单人 Riccati 摘掉，换上 G1 的多人耦合 Riccati，其余器官（前向 rollout、line search、收敛判据）原样保留。 这个视角的力量在于：你对 iLQR 的所有工程经验（怎么做 line search、怎么正则化防发散、怎么暖启动）几乎都能直接迁移到 iLQGames。 它也解释了 iLQGames 为什么快——耦合 Riccati 虽然比单人 Riccati 多了块耦合，但仍是**解析**的反向递推（每步只解一个小线性系统），没有外层迭代，所以单次 LQ 博弈求解和单次 iLQR 反向 pass 一个量级，毫秒级即可完成。
复杂度与实时性¶
每步迭代的主要开销在反向递推：\(T\) 个时间步，每步解一个 \((\sum_i n_{u_i})\times(\sum_i n_{u_i})\) 线性系统并更新 \(N\) 个 \(n_x\times n_x\) 的 \(Z\) 矩阵，量级约 \(O\big(T\cdot n_x^2\cdot\sum_i n_{u_i}\big)\)。 iLQGames 论文给出的实测数字是权威参考：三人 14 状态的交叉路口场景，初次求解 < 0.25 秒；而在硬件避撞测试中，滚动时域（MPC）问题收敛在 < 50 ms。 后者才是实时上车的关键指标——50 ms 对应 20 Hz 的重规划频率，足以放进车载 MPC 循环。 （"kHz 级"是更小规模或更优实现下的量级说法；论文 14 状态场景的硬件实测是 50 ms 级，二者不矛盾——规模越小、实现越优化，单次求解越快。） 单次迭代的主要开销在反向递推 \(O\big(T\cdot n_x^2\cdot\sum_i n_{u_i}\big)\)，数次迭代即收敛，这是它能达到上述速度的原因。 这个速度让 iLQGames 能直接放进实时 MPC 循环，是它相对 HJI（§1.7，秒级甚至更慢）的决定性优势。 一个对比能体现量级差异：HJI 可达性算一个 3–6 维问题的值函数动辄几秒到几分钟（网格规模 \(N^d\)，§1.7），而 iLQGames 解一个十余维的多车博弈在数十毫秒内（论文 14 状态场景滚动时域 <50 ms）——快了几个数量级。 代价是 iLQGames 只给局部反馈 Nash（非全局最优、非严格安全），但对实时上车这是值得的取舍，也正是 G1→G2 那条"从理论最优到可算近似"主线的体现。
实现：一个能跑的 iLQGames（2 车交叉路口）¶
理论讲完，落到能跑的代码。 下面给一个**自包含、纯 NumPy** 的最小 iLQGames，求解 2 车交叉路口的反馈 Nash：car0 沿 +x 穿过原点、car1 沿 +y 穿过原点，两车都想到达各自目标、又都要避免相撞。 这是项目甲本章模块的核心骨架（项目甲要 Eigen/C++ 版，逻辑一致，C++ 移植见练习）。
Step 1：先讲为什么这样组织代码。 iLQGames 的代码结构直接镜像它的算法五步。 有三个设计决定值得先说清楚，否则容易写错：
其一，多车状态拼接成单一向量。
两车各 4 维状态 \([p_x,p_y,\theta,v]\)，拼成 8 维 \(x\)。
为什么拼接？因为耦合 Riccati 是在"全局状态"上做反向递推的——博弈耦合（碰撞）体现在不同车的状态之间，必须放在同一个状态向量里才能让 \(Z_{i}\) 矩阵的非对角块捕捉到这种耦合。
这对应 ilqgames C++ 里的 ConcatenatedDynamicalSystem（§2.4 会看到）。
其二，线性化是块对角的、耦合只来自代价。 每辆车的动力学只依赖自己的状态和控制（车 0 怎么开不直接出现在车 1 的运动方程里），所以拼接后的 \(A_k\) 是块对角的、\(B_{i,k}\) 只在第 \(i\) 块非零。 真正把两车"耦合"起来的是**碰撞 penalty**——它是两车位置之差的函数，于是 \(Q_{i,k}\) 在两车位置的交叉块上非零。 记住这点能帮你 debug：如果你的求解器算出两车互不避让，多半是碰撞 penalty 的 Hessian/梯度没正确写进 \(Q_i/q_i\)。
其三，前向 rollout 必须带 line search 步长 \(\alpha\)。 和 iLQR 一样，线性化只在名义轨迹附近有效，整步（\(\alpha=1\)）更新可能跨出近似有效域导致代价不降甚至发散。 所以前向 pass 要试几个 \(\alpha\in\{1,0.5,0.25,\dots\}\)，取让总代价最小的那个——这是防发散的关键。
Step 2：核心实现（正确写法）。 下面是反向递推解耦合 Riccati 的核心函数，每行注明对应算法哪一步、G1 哪个量：
import numpy as np
dt, T, N, nx_i, nu_i = 0.1, 40, 2, 4, 2
nx = N * nx_i # 拼接状态维 = 8
idx = [slice(0,4), slice(4,8)] # 两车状态在拼接向量中的位置
uidx = [slice(0,2), slice(2,4)]
def lq_game_solve(As, Bs_list, Qs_t, qs_t, Rs_t, rs_t):
"""离散时间耦合 Riccati 反向递推（算法步骤 ③；G1 §1.6 的离散版）。
返回反馈增益 K[i][k] 与前馈 k[i][k]，策略 u_i = -K_i·x - k_i。"""
Z = [[None]*T for _ in range(N)] # Z[i][k] = 玩家i的cost-to-go二次项（G1的P_i）
zeta = [[None]*T for _ in range(N)] # 一次项（仿射博弈才非零）
K = [[None]*T for _ in range(N)]
kff = [[None]*T for _ in range(N)]
for i in range(N): # 终端条件 Z_{i,T}=Q_{i,T}
Z[i][T-1] = Qs_t[T-1][i].copy(); zeta[i][T-1] = qs_t[T-1][i].copy()
for t in range(T-2, -1, -1): # 从倒数第二步往回递推
A, Bs = As[t], Bs_list[t]
# —— 把 N 个玩家的一阶最优性堆叠成块线性系统 M·u = -(Nmat·x + nvec) ——
M = np.zeros((N*nu_i, N*nu_i))
Nmat = np.zeros((N*nu_i, nx))
nvec = np.zeros(N*nu_i)
for i in range(N):
ri = slice(i*nu_i, (i+1)*nu_i)
for j in range(N):
rj = slice(j*nu_i, (j+1)*nu_i)
blk = Bs[i].T @ Z[i][t+1] @ Bs[j] # 非对角块 = 耦合来源！
if i == j: blk = blk + Rs_t[t][i] # 对角块加自己的 R_ii
M[ri, rj] = blk
Nmat[ri, :] = Bs[i].T @ Z[i][t+1] @ A
nvec[ri] = Bs[i].T @ zeta[i][t+1] + rs_t[t][i]
sol = np.linalg.solve(M, np.hstack([Nmat, nvec.reshape(-1,1)]))
Kbig, kbig = sol[:, :nx], sol[:, nx] # 一次解出所有玩家的 K、k
for i in range(N):
ri = slice(i*nu_i, (i+1)*nu_i)
K[i][t], kff[i][t] = Kbig[ri, :], kbig[ri]
# —— 闭环转移 F = A - Σ_j B_j K_j，更新每人的 Z、zeta ——
F, beta = A.copy(), np.zeros(nx)
for j in range(N):
F = F - Bs[j] @ K[j][t]
beta = beta - Bs[j] @ kff[j][t]
for i in range(N):
Z[i][t] = Qs_t[t][i] + K[i][t].T @ Rs_t[t][i] @ K[i][t] + F.T @ Z[i][t+1] @ F
zeta[i][t] = qs_t[t][i] + K[i][t].T @ (Rs_t[t][i] @ kff[i][t] - rs_t[t][i]) \
+ F.T @ (Z[i][t+1] @ beta + zeta[i][t+1])
return K, kff
lq_game_solve 是反向 pass，但它吃的 \(A_k,B_{i,k},Q_{i,k},q_{i,k},R_{ii,k},r_{i,k}\) 从哪来？
这是 iLQGames 的"前半"——线性化与二次化（算法步骤 ① ②），同样要写对，否则反向 pass 再正确也是垃圾进垃圾出。
先看动力学线性化：每辆 unicycle 的连续动力学 \(\dot{[p_x,p_y,\theta,v]}=[v\cos\theta,\,v\sin\theta,\,\omega,\,a]\)，对状态/控制求雅可比再离散化：
def jac_i(xi, ui):
"""单车 unicycle 的离散线性化：返回 A_i = I+dt·∂f/∂x, B_i = dt·∂f/∂u。"""
px, py, th, v = xi
Ac = np.array([[0, 0, -v*np.sin(th), np.cos(th)], # ∂(v·cosθ)/∂θ, ∂/∂v
[0, 0, v*np.cos(th), np.sin(th)],
[0, 0, 0, 0],
[0, 0, 0, 0]])
Bc = np.array([[0, 0], [0, 0], [1, 0], [0, 1]]) # ω 进 θ̇, a 进 v̇
return np.eye(4) + dt*Ac, dt*Bc # 前向欧拉离散
拼接时，每辆车的 \(A_i\) 放进全局 \(A_k\) 的对角块、\(B_i\) 放进 \(B_{i,k}\) 的第 \(i\) 块——这就是前面"线性化是块对角的"那句话的代码体现：
A_cat = np.eye(nx)
Bs = [np.zeros((nx, nu_i)) for _ in range(N)]
for i in range(N):
Ai, Bi = jac_i(xbar_k[idx[i]], ubar_k[i])
A_cat[idx[i], idx[i]] = Ai # 块对角：car_i 的动力学只动 car_i 的状态
Bs[i][idx[i], :] = Bi # car_i 的控制只进 car_i 的状态块
代价二次化是博弈耦合真正进入的地方。 每车的"到目标"代价是自身状态的二次型（只进对角块），而碰撞 penalty 是两车位置之差的函数，求导后**同时**落到两车的状态块上——这段代码必须对所有玩家对称地累加（对应陷阱 3）：
def costs_and_derivs(x, us):
"""返回每车的 Q_i(nx×nx), q_i(nx), R_ii, r_i。碰撞项对双方对称计入。"""
Qs = [np.zeros((nx, nx)) for _ in range(N)]
qs = [np.zeros(nx) for _ in range(N)]
Rs = [w_u.copy() for _ in range(N)]
rs = [w_u @ us[i] for i in range(N)]
for i in range(N): # 各车"到目标"代价（自身块）
e = x[idx[i]] - goal[i]
Qs[i][idx[i], idx[i]] += w_goal
qs[i][idx[i]] += w_goal @ e
p0, p1 = x[idx[0]][:2], x[idx[1]][:2] # 碰撞 penalty（耦合来源）
dvec = p0 - p1; dist = np.linalg.norm(dvec) + 1e-6
if dist < d_safe:
g = dist - d_safe # 违反量 <0
dgdp0, dgdp1 = dvec/dist, -dvec/dist
for i in range(N): # 对双方对称累加！（陷阱3）
qs[i][idx[0].start:idx[0].start+2] += w_coll*2*g*dgdp0
qs[i][idx[1].start:idx[1].start+2] += w_coll*2*g*dgdp1
Qs[i][idx[0].start:idx[0].start+2,
idx[0].start:idx[0].start+2] += w_coll*2*np.outer(dgdp0, dgdp0)
Qs[i][idx[1].start:idx[1].start+2,
idx[1].start:idx[1].start+2] += w_coll*2*np.outer(dgdp1, dgdp1)
return Qs, qs, Rs, rs
有了这三块（线性化 jac_i、拼接、二次化 costs_and_derivs）加上反向 pass lq_game_solve，还差三个辅助函数就能跑通：状态推进 step、前向 rollout、总代价评估。先把它们补全（都是直白的工具函数，但缺了就跑不起来）：
dt = 0.1; w_u = np.diag([0.1, 0.1]); w_goal = np.diag([1.0, 1.0, 0.1, 0.5])
w_coll = 50.0; d_safe = 1.0
goal = [np.array([4,0,0,1.0]), np.array([0,4,np.pi/2,1.0])] # 两车目标
def dyn_i(xi, ui):
px, py, th, v = xi; om, a = ui
return np.array([v*np.cos(th), v*np.sin(th), om, a]) # 连续 unicycle
def step(x, us):
xn = x.copy()
for i in range(N):
xn[idx[i]] = x[idx[i]] + dt*dyn_i(x[idx[i]], us[i]) # 前向欧拉，逐车推进
return xn
def build_lq_along_trajectory(xbar, ubar):
"""步骤 ①②：沿名义轨迹逐步线性化 + 二次化，收集每步的 A,B,Q,q,R,r。"""
As, Bs_list, Qs_t, qs_t, Rs_t, rs_t = [], [], [], [], [], []
for t in range(T):
A_cat = np.eye(nx); Bs = [np.zeros((nx, nu_i)) for _ in range(N)]
for i in range(N):
Ai, Bi = jac_i(xbar[t][idx[i]], ubar[t][i])
A_cat[idx[i], idx[i]] = Ai; Bs[i][idx[i], :] = Bi # 块对角拼接
As.append(A_cat); Bs_list.append(Bs)
Qs, qs, Rs, rs = costs_and_derivs(xbar[t], [ubar[t][i] for i in range(N)])
Qs_t.append(Qs); qs_t.append(qs); Rs_t.append(Rs); rs_t.append(rs)
return As, Bs_list, Qs_t, qs_t, Rs_t, rs_t
def forward_rollout(x0, xbar, ubar, K, kff, alpha):
"""步骤 ④：用反馈律前向推进。u_i = ū_i - K_i·(x-x̄) - α·k_i。"""
xs = [x0.copy()]; us_new = [[None]*N for _ in range(T)]
for t in range(T-1):
dx = xs[t] - xbar[t]
for i in range(N):
us_new[t][i] = ubar[t][i] - K[i][t] @ dx - alpha*kff[i][t] # 含反馈纠偏 K·dx
xs.append(step(xs[t], [us_new[t][i] for i in range(N)]))
for i in range(N): us_new[T-1][i] = ubar[T-1][i].copy()
return xs, us_new
def total_costs(xbar, ubar):
"""评估每车总代价（到目标 + 控制能耗 + 碰撞 penalty）。"""
Js = [0.0]*N
for t in range(T):
for i in range(N):
e = xbar[t][idx[i]] - goal[i]
Js[i] += 0.5*e@w_goal@e + 0.5*ubar[t][i]@w_u@ubar[t][i]
p0, p1 = xbar[t][idx[0]][:2], xbar[t][idx[1]][:2]
dist = np.linalg.norm(p0 - p1)
if dist < d_safe:
for i in range(N): Js[i] += w_coll*(dist - d_safe)**2 # 碰撞软惩罚
return Js
有了这些，外层迭代就是把五步串起来：
# 初始化：名义控制全 0、名义轨迹由初始 rollout 得到
x0 = np.array([-3,0,0,1.0, 0,-3,np.pi/2,1.0])
ubar = [[np.zeros(nu_i) for _ in range(N)] for _ in range(T)]
xbar = [x0.copy()]
for t in range(T-1): xbar.append(step(xbar[t], [ubar[t][i] for i in range(N)]))
prev = sum(total_costs(xbar, ubar))
for it in range(50):
# ①② 沿名义轨迹线性化 + 二次化
As, Bs_list, Qs_t, qs_t, Rs_t, rs_t = build_lq_along_trajectory(xbar, ubar)
# ③ 反向 pass 解耦合 Riccati
K, kff = lq_game_solve(As, Bs_list, Qs_t, qs_t, Rs_t, rs_t)
# ④ 前向 rollout + line search（试递减步长，取代价最小者）
best = None
for alpha in [1.0, 0.5, 0.25, 0.1, 0.05]:
xs, us_new = forward_rollout(x0, xbar, ubar, K, kff, alpha)
J = sum(total_costs(xs, us_new))
if best is None or J < best[0]: best = (J, xs, us_new)
Jnew, xbar, ubar = best
# ⑤ 收敛检查
if abs(prev - Jnew) < 1e-4: break
prev = Jnew
这就是完整的 iLQGames——前向 rollout 用反馈律 \(u_{i,k}=\bar u_{i,k}-K_{i,k}(x_k-\bar x_k)-\alpha k_{i,k}\) 推进（注意那个 \(K_{i,k}(x_k-\bar x_k)\) 项，正是 §2.2 反复强调的反馈纠偏项）。
五步里只有步骤 ③ 是博弈特有的，其余四步与单人 iLQR 逐字对应——再次印证"iLQGames = iLQR 换内核"。
上面的代码连同前面的 jac_i、costs_and_derivs、lq_game_solve 是完整自包含的，复制到一起即可运行复现下面的结果。
Step 3：把它跑起来，看真实结果。 对初始位形 car0 在 \((-3,0)\) 朝 +x、car1 在 \((0,-3)\) 朝 +y，碰撞 penalty 权重 \(w_{\text{coll}}=50\)、安全距离 \(d_{\text{safe}}=1.0\)，跑出来：
| 指标 | 数值结果 | 含义 |
|---|---|---|
| 收敛迭代数 | 29 次 | 总代价变化 < 1e-4 即停 |
| 两车最小间距 | 0.871 | 安全距离 \(d_{\text{safe}}=1.0\) |
| car0 终点 | (4.62, −0.03) | 目标 (4, 0) ✓ |
| car1 终点 | (0.03, 4.61) | 目标 (0, 4) ✓ |
| 纳什自检 | 20/20 | car0 随机单边扰动均不优于均衡策略 |
求解器自动学会了避让——两车都微微偏离直线、错开通过路口，各自抵达目标。 纳什自检证实这是个真均衡：固定 car1 策略，对 car0 的控制序列做 20 次随机单边扰动，**没有一次**能降低 car0 的代价（全部 20/20 不优于均衡），符合 Nash 定义 (2.1)。 这两个验证（纳什自检 + 抗扰对比）的代码如下，是检验任何博弈求解器实现是否正确的标准工具：
def rollout(x0, ubar): # 纯名义 rollout（无反馈）
xs = [x0.copy()]
for t in range(T-1): xs.append(step(xs[t], [ubar[t][i] for i in range(N)]))
return xs
# —— 验证一：纳什自检（固定 car1，扰动 car0，不应改善 car0 代价）——
J0 = total_costs(xbar, ubar)[0]
np.random.seed(0); worse = 0; trials = 20
for _ in range(trials):
ub2 = [[ubar[t][i].copy() for i in range(N)] for t in range(T)]
for t in range(T): ub2[t][0] = ub2[t][0] + 0.05*np.random.randn(nu_i) # 仅扰动 car0
if total_costs(rollout(x0, ub2), ub2)[0] >= J0 - 1e-6: worse += 1
print(f"纳什自检: car0 单边扰动 {worse}/{trials} 次不优于均衡") # 实跑: 20/20
# —— 验证二：反馈 vs 伪开环抗扰（注入扰动，对比纠偏能力，§2.2）——
def rollout_disturbed(x0, xbar, ubar, K, kff, use_feedback, noise=0.05, trials=30):
np.random.seed(42); errs, gaps = [], []
for _ in range(trials):
xs = [x0.copy()]
for t in range(T-1):
dx = xs[t] - xbar[t]
us = [(ubar[t][i] - K[i][t]@dx - kff[i][t]) if use_feedback # 反馈纠偏
else (ubar[t][i] - kff[i][t]) for i in range(N)] # 伪开环不纠偏
xs.append(step(xs[t], us) + noise*np.random.randn(nx)) # 注入扰动
errs.append(sum(np.linalg.norm(xs[-1][idx[i]][:2]-goal[i][:2]) for i in range(N)))
gaps.append(min(np.linalg.norm(xs[t][idx[0]][:2]-xs[t][idx[1]][:2]) for t in range(T)))
return np.mean(errs), np.min(gaps)
ef, gf = rollout_disturbed(x0, xbar, ubar, K, kff, True)
eo, go = rollout_disturbed(x0, xbar, ubar, K, kff, False)
print(f"反馈: 终点误差={ef:.3f} 最坏间距={gf:.3f} | 伪开环: 误差={eo:.3f} 间距={go:.3f}")
# 实跑: 反馈 误差1.275 间距0.615 | 伪开环 误差2.280 间距0.423 —— 反馈降误差44%
这两段验证代码值得收进工具箱：纳什自检是判断"求出来的到底是不是 Nash"的金标准（漏了耦合块就会失败，见陷阱 1），抗扰对比则量化了 §2.2 反复强调的反馈优势（实跑数据见 §2.2 的表）。
Step 4：调权重看均衡变化——并暴露软约束的本质局限。 规格里有个经典实验：改变碰撞 penalty 权重，观察均衡行为如何变。 把 \(w_{\text{coll}}\) 从 50 提到 300，重跑：
| 碰撞权重 \(w_{\text{coll}}\) | 两车最小间距 | 是否满足 \(d_{\text{safe}}=1.0\) |
|---|---|---|
| 50 | 0.871 | 否（侵入 0.129） |
| 300 | 0.978 | 否（侵入 0.022） |
权重越大，两车越"小心"、间距越接近安全距离——均衡行为确实随权重连续变化（这就是规格说的"从让行到抢行"的连续谱）。 但请注意一个要命的事实：哪怕权重提到 300，最小间距 0.978 仍 < 1.0——两车仍轻微侵入了安全区。 这不是 bug，而是 penalty 软约束的本质局限：penalty 只是在违反约束时加大代价，它让违反"变贵"，却**永远不能保证违反不发生**。 再加大权重只能把间距推得更接近 1.0，但要么永远差一点、要么权重大到让数值病态（\(Q\) 矩阵条件数爆炸、迭代发散）。
本质洞察（软约束逼近、硬约束保证——这是 ALGAMES 存在的理由）：iLQGames 用 penalty 处理碰撞，本质是把"硬约束"软化成"代价项"。 软约束的好处是简单——直接进二次代价、不破坏耦合 Riccati 的解析结构，所以 iLQGames 能保持毫秒级实时。 软约束的代价是**没有保证**——上面的实验白纸黑字显示，再大的权重也只能逼近 \(d_{\text{safe}}\)、无法真正满足它。 安全关键场景里，"逼近不碰"和"保证不碰"是天壤之别。 这正是 §2.5 的 ALGAMES 存在的全部理由：它用增广拉格朗日 + 互补条件**严格**处理硬约束，能真正保证 \(d_{\text{safe}}\) 不被侵犯——代价是放弃了解析的 Riccati、换成迭代的 KKT 根搜索。 记住这个 0.978 < 1.0 的数字，§2.5 你会看到 ALGAMES 如何把它变成"恰好 1.0、一步不越界"。
这个实验还顺带印证了 §2.2 的伏笔——iLQGames（反馈 Nash、软约束）与 ALGAMES（开环 GNE、硬约束）的互补，不是纸上谈兵，而是一个具体的 0.978 vs 1.0 的差距。
均衡选择：初始化决定停在哪个 Nash¶
G1 §1.1 强调过博弈均衡可能不唯一——路口"你让我"和"我让你"都是合法 Nash。 iLQGames 作为一个**局部**方法（基于局部 LQ 近似 + 梯度式迭代），它会收敛到**离初始名义轨迹最近的那个**局部 Nash。 换句话说，iLQGames 靠初始化隐式地选均衡：
- 用"car0 先行"的名义轨迹初始化，多半收敛到 car0 抢行、car1 让的均衡；
- 用"car1 先行"初始化，则收敛到对称的另一个均衡。
这是 iLQGames 的一个重要特性（也是局限）：它不保证找到全局最优或某个"社会最优"的均衡，只保证找到初始化附近的一个局部 Nash。 工程上这既是负担也是抓手——负担是结果依赖初始化、需要小心暖启动；抓手是你可以**用初始化来引导均衡选择**（想让车谦让，就用谦让的轨迹初始化）。 §2.6 的 SE-IBR 提供了另一种更主动的均衡选择机制（灵敏度项），而本节这个"初始化选均衡"是 iLQGames 最朴素的办法。这也是规格思考题"初始化如何影响均衡选择"的答案。
⚠️ 常见陷阱¶
陷阱 1（编程陷阱）：把耦合 Riccati 写成 N 个独立的单人 Riccati - 错误描述：图省事，在反向递推里对每个玩家单独解一个标准 LQR Riccati，跳过那个 \(N\times N\) 块线性系统，相当于把
lq_game_solve里M矩阵的非对角块 \(B_i^\top Z_iB_j\,(i\ne j)\) 直接置零。 - 现象/后果：求解器跑得通、也"收敛"，但算出的策略不是 Nash 均衡——两车互不避让、或避让行为诡异；纳什自检会失败（单边扰动能改善代价）。 - 根本原因：去掉非对角块 = 假设"每个玩家当其他玩家不存在"，这正是 G1 §1.6 反复警告的、丢掉了博弈耦合。耦合恰恰来自那些非对角块——它们编码了"玩家 \(i\) 的最优依赖玩家 \(j\) 的反馈"。 - 正确做法：必须组装完整的块线性系统M（含非对角块）并一次性np.linalg.solve解出所有玩家的 \(K\)。自检方法：跑纳什自检（固定他人、单边扰动自己），若有扰动能改善代价，几乎一定是漏了耦合块。陷阱 2（编程陷阱）：前向 rollout 不带 line search，直接整步更新 - 错误描述：前向 pass 直接用 \(\alpha=1\) 更新所有控制 \(u_{i,k}=\bar u_{i,k}-K_{i,k}\delta x_k-k_{i,k}\)，不试更小的步长。 - 现象/后果：迭代代价不降反升、甚至发散（NaN）；尤其在碰撞 penalty 权重大、非线性强时极易出现。 - 根本原因：线性化与二次化只在名义轨迹的小邻域内有效，整步更新可能跨出近似有效域，使新轨迹比旧的更差。 - 正确做法：前向 pass 试一组递减步长 \(\alpha\in\{1,0.5,0.25,0.1,\dots\}\)，取使总代价最小的那个（armijo 式回溯）。和单人 iLQR 完全一样——这是从 iLQR 迁移过来的工程经验之一。自检方法：若迭代代价出现上升或 NaN，先检查是否做了 line search。
陷阱 3（编程陷阱）：碰撞 penalty 的梯度/Hessian 没正确写进所有玩家的代价 - 错误描述：碰撞 penalty 是两车位置之差的函数，求导后既影响 car0 的状态块、也影响 car1 的状态块；新手常只把它写进"肇事车"一方的 \(q_i/Q_i\)，漏掉对方。 - 现象/后果：一方避让、另一方无动于衷（因为它的代价里没有碰撞项的梯度），博弈退化成单边避让，不对称且不合理。 - 根本原因：一般和博弈里碰撞代价对双方都计入（都不想撞），所以 penalty 对 \(p_0\) 和 \(p_1\) 的导数要分别加到**每个**玩家的 \(q_i\) 的对应状态块上（见前面
costs_and_derivs里对i in range(N)的循环）。 - 正确做法：碰撞 penalty 的一阶/二阶导对所有相关玩家的状态块都要正确累加。自检方法：可视化轨迹，若只有一方避让、另一方直行穿过，检查 penalty 是否对称地进了双方代价。陷阱 4（概念误区）：以为加大碰撞 penalty 权重就能保证不碰撞 - 错误描述：看到最小间距侵入安全区，就不断调大 \(w_{\text{coll}}\)，以为权重够大就能严格满足 \(d_{\text{safe}}\)。 - 现象/后果：间距确实越来越接近 \(d_{\text{safe}}\)（如实验里 0.871→0.978），但**永远差一点**；权重过大时 \(Q\) 矩阵条件数爆炸、迭代发散。 - 根本原因：penalty 是软约束——它让违反"变贵"而非"禁止"。最优解总是在"违反一点点换取其他代价降低"和"penalty 惩罚"之间权衡，于是总会侵入一点。这是软约束的数学本质，与权重大小无关。 - 正确做法：需要严格保证不碰撞时，用硬约束方法——ALGAMES 的增广拉格朗日 + 互补（§2.5），或 CBF 安全滤波（G4）。iLQGames 的 penalty 适合"尽量避免"而非"保证避免"的场景。
陷阱 5（思维陷阱）：以为 iLQGames 收敛到的就是"那个"正确均衡 - 错误描述：把 iLQGames 输出的 Nash 当成唯一/最优解，不意识到它依赖初始化。 - 现象/后果：换个初始名义轨迹，求解器收敛到不同的均衡（car0 让 vs car1 让），结果"不稳定"，却找不到原因；在需要特定礼让行为的场景里行为不可控。 - 根本原因：iLQGames 是局部方法，收敛到离初始化最近的局部 Nash。博弈均衡本就可能多个（G1 §1.1），iLQGames 不保证选到哪个。 - 正确做法：把初始化当成均衡选择的抓手——想要某种礼让行为，就用体现该行为的轨迹暖启动。需要更主动的均衡选择时用 SE-IBR（§2.6）。多均衡场景下，跑多个初始化、比较收敛到的均衡，是标准的稳健性检查。
练习¶
- （累积项目·甲，本章核心模块） 把本节的 NumPy
lq_game_solve用 Eigen/C++ 重写，并补全外层迭代（线性化、二次化、带 line search 的前向 rollout、收敛检查），构成一个完整的 2 车 iLQGames 求解器。这是项目甲（自动驾驶交互博弈规划器）在本章的核心模块——它直接以 G1 模块的耦合 Riccati 求解器为内核，把它从"求一次 LQ 博弈"升级为"迭代求解非线性博弈"。验收标准：(a) 复现本节的避让行为；(b) 纳什自检通过；(c) 改变碰撞权重，复现间距随权重变化的现象。 - （调试挑战） 给你一个 iLQGames 实现，它跑出来两车直接对穿、完全不避让。已知动力学和 line search 都正确。请列出**至少三个**可能的 bug 来源（提示：回顾陷阱 1、3），并说明各自如何用纳什自检或可视化定位。
- （设计扩展 + 连接 §2.2） 本节求解器输出反馈律 \(u_i=-K_i\delta x-\alpha k_i\)。请设计一个实验验证它的"反馈抗扰"能力（§2.2）：在前向 rollout 的每一步注入一个小随机扰动（模拟风/打滑），对比"用反馈律 \(K_i\delta x\) 纠偏"和"只用名义控制 \(\bar u_i\) 不纠偏（伪开环）"两种执行方式下的终点误差与最小间距。说明结果如何印证反馈 Nash 优于开环。
§2.4 ilqgames C++ 源码精读：lq_solver.cc ⭐⭐⭐¶
这一节解决什么问题：§2.3 的 NumPy 实现讲清了 iLQGames 的算法骨架，但真实工程代码长什么样、概念如何映射到 C++ 类、性能关键处怎么写？ 这一节精读
HJReachability/ilqgames的核心——把"耦合 Riccati 反向递推"从教学代码对照到工业级 C++ 实现。
动机：从"能跑的 NumPy"到"能上车的 C++"¶
§2.3 的 NumPy 求解器能复现避让行为、能通过纳什自检——但它跑一次要几十毫秒（Python 解释器 + 逐元素操作），离实时（<50 ms）还差得远。
真要把 iLQGames 放进车载 MPC 循环，需要 C++ + Eigen 的实现。
ilqgames（Fridovich-Keil 等维护，论文同款代码，188★，BSD-3，C++ 为主）就是这样一个参考实现。
精读它有两重价值：一是看 §2.3 的每个概念（拼接状态、耦合 Riccati、反馈增益 \(K\) 与前馈 \(k\)）如何落成工程化的类与数据结构；二是学到一批可迁移的 C++ 数值计算工程手法（Eigen 块操作、内存预分配、避免重复 malloc）。
说明：以下类名、文件结构依据 ilqgames 项目文档与规格（截至本资料编写）。开源项目持续演进，精读时请以仓库当前
master分支为准，重点理解数据流而非死记某个签名。
反面案例：直接把 NumPy 逐行翻译成 C++ 会怎样¶
一个常见的弯路：拿着 §2.3 的 NumPy 代码逐行直译成 C++，每个时间步 new 一批 MatrixXd、用动态大小矩阵存所有量。
这样写**能编译、能跑、结果也对**，但性能惨不忍睹——
博弈 MPC 每个控制周期要解一次完整 iLQGames（几十次反向递推 × 上百个时间步），如果每步都在堆上 malloc/free 一堆动态矩阵，内存分配开销会吞掉大部分时间预算，根本到不了 60 Hz。
这正是 G1 §1.5 之外、算法工程层面的"维度诅咒"——不是状态维度，而是**实时预算**的诅咒。
ilqgames 的工程价值，很大程度就在于它怎么把这些分配开销压下去：固定大小矩阵栈分配、容器预分配、跨迭代复用缓冲区。下面边读边指出来。
核心类结构：概念到 C++ 的映射¶
ilqgames 的类设计直接镜像 §2.3 的算法概念。先建立映射，精读才有方向：
| ilqgames C++ 类 | 对应 §2.3 的什么 | 职责 |
|---|---|---|
MultiPlayerDynamicalSystem |
多人耦合动力学 \(f\) | 定义 \(\dot x=f(x,u_1,\dots,u_N)\) 及其线性化 |
ConcatenatedDynamicalSystem |
状态拼接（§2.3 的 8 维 x） |
把各玩家子系统拼成单一大状态向量 |
PlayerCost |
每人代价 \(\ell_i\)（含碰撞 penalty） | 提供代价的一阶 \(q_i,r_i\)、二阶 \(Q_i,R_i\) |
Strategy |
反馈律 \(u_i=-K_i\delta x-k_i\) | 存每个时间步的增益 \(K_{i,k}\) 与前馈 \(k_{i,k}\) |
OperatingPoint |
名义轨迹 \((\bar x,\bar u)\) | 存当前迭代的参考状态/控制序列 |
LQSolver |
§2.3 的 lq_game_solve |
耦合 Riccati 反向递推（本节主角，约 200 行 Eigen） |
ILQSolver |
§2.3 的外层循环 | 线性化→二次化→调 LQSolver→前向 rollout→收敛 |
Problem |
整个问题封装 | 动力学 + 代价 + 初始条件 + 时域，并提供暖启动 |
这套结构和 §2.3 的对应关系几乎一一对上——LQSolver 是 lq_game_solve、ILQSolver 是外层循环、OperatingPoint 是名义轨迹、Strategy 是输出的反馈律。
理解了 §2.3，读这些类就是"换一种语言看同一个算法"。
多视角理解（C++ 类设计 ↔ 算法步骤的对象化）：
ilqgames的类划分，本质是把 §2.3 算法的每个"名词"对象化、每个"动词"方法化。 相似之处：和任何一个把数学算法工程化的库一样（比如 SLAM 里把因子图拆成Factor/Variable/Optimizer），它把数据（名义轨迹、策略、代价）和操作（线性化、求解、rollout）分离成职责单一的类。 不同之处：博弈特有的是MultiPlayerDynamicalSystem与ConcatenatedDynamicalSystem这对——它们显式地把"多个玩家"这件事编码进类型系统，而单人最优控制的库里没有"玩家"这个维度。 一句话：读懂这套类，关键是抓住"哪个类持有玩家间的耦合"——答案是ConcatenatedDynamicalSystem（状态拼接）和PlayerCost（碰撞耦合进代价），这与 §2.3 "耦合只来自拼接状态和碰撞代价"完全一致。
lq_solver.cc 精读：耦合 Riccati 的工程实现¶
src/solver/lq_solver.cc（约 200 行）是整个库的心脏，对应 §2.3 的 lq_game_solve。
它做的事一字不差：从终端往初始反向递推，每个时间步组装并求解一个耦合的块线性系统，输出每人的 \(K_{i,k}\) 和 \(k_{i,k}\)。
下面分三个关键片段对照讲解（C++ 代码按 ilqgames 的实现风格示意，重在数据流，非逐字复制）。
片段一：反向递推主循环的骨架。
和 §2.3 一样，从 \(k=T-1\) 倒推，维护每个玩家的 cost-to-go 二次型矩阵（C++ 里记为 Z 或 S，对应 §2.3 的 Z[i]、G1 的 \(P_i\)）：
// 反向递推：从终端时间步 horizon-1 倒推到 0
//（对应 §2.3 lq_game_solve 的 for t in range(T-2,-1,-1) 循环）
for (int kk = horizon - 1; kk >= 0; kk--) {
// 1) 组装本时间步的耦合块线性系统（见片段二）
// 2) 求解得到每个玩家的反馈增益 Ks[kk] 和前馈 ks[kk]
// 3) 用闭环转移更新每个玩家的 cost-to-go 矩阵 Z（见片段三）
}
C++ 工程化的关键在于：Z、Ks、ks 这些容器在求解前**预先 resize 好**（按玩家数 × 时域），循环里只往里写、不重新分配——这就是把 malloc 开销压到零的核心手法，也是它能实时的前提之一。
片段二：组装耦合块线性系统。
这是博弈耦合真正落地的地方，对应 §2.3 里组装 M 矩阵那段。
每个玩家 \(i\) 的一阶最优性条件，贡献块线性系统的一组行；非对角块 \(B_i^\top Z_i B_j\,(i\ne j)\) 就是耦合：
// 对每个玩家 i，填充块线性系统的第 i 组行
// （对应 §2.3 的 M[ri,rj] = Bs[i].T @ Z[i] @ Bs[j]）
for (PlayerIndex ii = 0; ii < num_players; ii++) {
for (PlayerIndex jj = 0; jj < num_players; jj++) {
// 非对角块（ii != jj）= 玩家间耦合的来源；对角块额外加上 R_ii
Eigen::Ref<MatrixXd> block = M.block(/* 行块 ii */, /* 列块 jj */, ...);
block = Bs[ii].transpose() * Z[ii] * Bs[jj];
if (ii == jj) block += Rs[ii]; // 对角块加自己的控制代价 R_ii
}
// 右端项：B_i^T (Z_i A) 进入 x 的系数，B_i^T zeta_i + r_i 进入常数项
}
// 求解 M * [K | k] = -[N | n]，一次解出所有玩家的增益与前馈
注意 M.block(...) ——这是 Eigen 的**块操作**，让你在一个大矩阵里直接读写子块而不拷贝（返回的是引用视图）。
这正是 §2.3 NumPy 里 M[ri,rj] 切片赋值的 C++ 对应，但 Eigen 的 .block 是零拷贝的，性能更好。
组装好后调用 Eigen 的稠密分解（如 M.lu().solve(...) 或 householderQr）一次解出所有玩家的反馈增益——和 §2.3 的 np.linalg.solve(M, ...) 一一对应。
片段三：用闭环转移更新 cost-to-go。
解出 \(K_{i,k}\) 后，构造闭环转移 \(F=A-\sum_j B_jK_j\)，更新每个玩家的 \(Z_i\)，继续倒推。对应 §2.3 末尾那段更新 Z[i][t]：
// 闭环系统矩阵 F = A - Σ_j B_j K_j（对应 §2.3 的 F = A - Σ Bs[j] @ K[j])
MatrixXd F = A;
for (PlayerIndex jj = 0; jj < num_players; jj++)
F -= Bs[jj] * Ks[kk][jj];
// 更新每个玩家的 cost-to-go：Z_i ← Q_i + K_i^T R_i K_i + F^T Z_i F
for (PlayerIndex ii = 0; ii < num_players; ii++)
Z[ii] = Qs[ii] + Ks[kk][ii].transpose() * Rs[ii] * Ks[kk][ii]
+ F.transpose() * Z[ii] * F;
这三段合起来，就是 §2.3 lq_game_solve 的完整 C++ 化身——逻辑一字不差，区别只在 Eigen 的零拷贝块操作、预分配容器、固定大小矩阵这些性能手法。
错误 vs 正确：Eigen 别名（aliasing）对照。 算法工程教学强调"看正确写法、也看错误写法、再对比"——上面那段 cost-to-go 更新藏着一个真实的 C++ 坑，单看正确代码看不出危险，对照错误写法才能记牢：
// ❌ 错误：自引用赋值踩 Eigen 别名 bug
// Z[i] 同时出现在左边和右边，且表达式含乘积；Eigen 默认假设无别名，
// 惰性求值时可能在算 F^T*Z[i]*F 的过程中就开始覆盖 Z[i]，污染还要用的数据。
Z[ii] = Qs[ii] + Ks[kk][ii].transpose() * Rs[ii] * Ks[kk][ii]
+ F.transpose() * Z[ii] * F; // ← Z[ii] 自引用，危险！结果可能错且不报错
// ✓ 正确写法一：用 .eval() 强制先算出临时结果，再赋值
Z[ii] = (Qs[ii] + Ks[kk][ii].transpose() * Rs[ii] * Ks[kk][ii]
+ F.transpose() * Z[ii] * F).eval(); // .eval() 切断别名
// ✓ 正确写法二：显式临时矩阵 + swap（更稳妥，意图清晰）
MatrixXd Z_next = Qs[ii] + Ks[kk][ii].transpose() * Rs[ii] * Ks[kk][ii]
+ F.transpose() * Z[ii] * F;
Z[ii].swap(Z_next); // 写到临时再交换，绝不别名
为什么这个 bug 特别阴险？因为它**不报错、结果"看着差不多"**——别名污染往往只让 Riccati 递推悄悄偏离，数值上不发散、不崩溃，但算出的反馈增益是错的，最终表现为"求解器跑通了、博弈行为却莫名其妙"。
对照着记：凡是 A = ...A... 形式（左右都有 A、中间含乘积/转置）的 Eigen 赋值，都要警惕别名，加 .eval() 或用临时矩阵。
这与 §2.3 NumPy 版形成鲜明对比——NumPy 的 @ 总是返回新数组，没有别名问题；这正是"C++ 直译 NumPy 会踩坑"的典型（陷阱 2）。
反馈增益 K 与前馈 k 的物理含义¶
精读时最容易"看懂代码却不懂意义"的，是输出的 Strategy 里那对 \(K_{i,k}\) 和 \(k_{i,k}\)。它们的物理含义必须讲清（这也是规格 B 型精读任务的要求）：
- 反馈增益 \(K_{i,k}\)（矩阵，\(n_{u_i}\times n_x\)）：它乘的是状态偏差 \(\delta x_k=x_k-\bar x_k\)。物理上，它回答"如果当前实际状态偏离了名义轨迹，玩家 \(i\) 该如何调整控制来纠偏"。这就是 §2.2 反复强调的**反馈纠偏项**——它让 iLQGames 输出的是反馈 Nash（抗扰），而非开环。\(K\) 越大，对偏差的修正越激进。
- 前馈项 \(k_{i,k}\)（向量，\(n_{u_i}\)）：它不依赖状态偏差，是"即便完全在名义轨迹上（\(\delta x=0\)），相对当前名义控制 \(\bar u_{i,k}\) 还要施加的修正量"。它驱动迭代**改进**名义轨迹本身——前向 rollout 里那个 \(-\alpha k_{i,k}\) 项（\(\alpha\) 是 line search 步长）正是用它把轨迹往更优处推。收敛时 \(k_{i,k}\to0\)（名义轨迹已是局部最优，无需再改），只剩 \(K_{i,k}\) 做运行时纠偏。
本质洞察（K 管"应变"、k 管"改进"）：理解这对量的最好方式，是分清它们服务于两个不同的目的。 \(k_{i,k}\) 是**离线**的——它在迭代中驱动名义轨迹收敛到局部 Nash，收敛后归零、功成身退。 \(K_{i,k}\) 是**在线**的——它在执行时持续工作，把实际状态拉回名义轨迹，是部署后真正起抗扰作用的部分。 这解释了一个常见困惑："收敛后 \(k\) 都快是 0 了，那 Strategy 还有什么用？"——用的是 \(K\)：哪怕名义轨迹完美，真实世界的扰动仍需要 \(K\) 来实时纠偏。 这也再次呼应 §2.2：正是这个收敛后仍非零的 \(K\)，让 iLQGames 的解是"自带纠偏规则"的反馈策略，而非一条会被扰动带偏的开环序列。
三车交叉路口 demo¶
exec/three_player_intersection/（对应论文 Fig.1）是 ilqgames 的标志性示例，也是上手的最佳入口。
它建模两辆车过十字路口、一个行人走人行横道的三人一般和博弈：每辆车想沿各自路线快速通过、避免与另一辆车及行人相撞，行人想安全过街。
跑 ./three_player_intersection 会弹出内置 GUI（基于 DearImGui），实时显示三个智能体的博弈轨迹——你能看到论文里描述的行为：两车都轻微转向互相避让、并给行人留出额外间隙。
这正是 §2.3 那个 2 车 demo 的三人加强版，也是验证你对前向-反向数据流理解的最佳实验：改一辆车的代价权重（比如调高它的"激进度"——降低碰撞 penalty 或提高进展奖励），重跑，观察其余智能体如何响应这个更激进的对手。
数据流串联：ILQSolver 与 LQSolver 怎么配合¶
精读时最容易"见树不见林"——读懂了 LQSolver（反向 pass）却不清楚它在整个求解里的位置。把两个核心类的数据交接画清楚，对应 §2.3 的算法五步：
ILQSolver::Solve() 外层循环（对应 §2.3 算法五步）:
┌─ 输入: OperatingPoint（名义轨迹 x̄, ū）
│
├─ ① 沿名义轨迹线性化 → 每步的 LinearDynamicsApproximation (A_k, B_{i,k})
├─ ② 二次化代价 → 每步的 QuadraticCostApproximation (Q_{i,k}, R_{i,k}, ...)
│
├─ ③ 调 LQSolver::Solve(线性化, 二次化) ← 反向 pass 在这里
│ └─ 内部: 耦合 Riccati 反向递推 → 返回 Strategy（每步 K_{i,k}, k_{i,k}）
│
├─ ④ 前向 rollout（用 Strategy + line search 步长 α）→ 新 OperatingPoint
│ u_{i,k} = ū_{i,k} - K_{i,k}(x_k - x̄_k) - α·k_{i,k}
│
└─ ⑤ 收敛检查（代价变化 < ε）→ 否则用新 OperatingPoint 回到 ①
看清这个数据流，三件事就明白了：
其一，LQSolver 只是步骤 ③，它**吃**线性化/二次化的结果、吐 Strategy——它不做线性化、不做 rollout，那些是 ILQSolver 的活。
其二，Strategy（含 \(K_{i,k},k_{i,k}\)）是两个类之间的"接口对象"——LQSolver 生产它、ILQSolver 在步骤 ④ 消费它。
其三，OperatingPoint（名义轨迹）是迭代的"状态"——每轮被步骤 ④ 更新、喂回步骤 ①，直到收敛。
这正是陷阱 3 要强调的：精读 lq_solver.cc 只看懂了步骤 ③，必须连 ILQSolver 的外层循环（尤其步骤 ④ 的 line search）一起读，才算掌握整个 iLQGames——这与 §2.3 NumPy 版"lq_game_solve + 外层循环"的分工完全对应。
⚠️ 常见陷阱¶
陷阱 1（编程陷阱）：反向递推里用动态大小矩阵 + 每步重新分配 - 错误描述：把 §2.3 NumPy 直译为 C++ 时，每个时间步
MatrixXd Z(nx, nx)重新声明、new一批临时矩阵。 - 现象/后果：能跑、结果对，但每个控制周期成百上千次 malloc/free，实时性垮掉——到不了 60 Hz，更别说毫秒级。 - 根本原因：博弈 MPC 每周期解一次完整 iLQGames（几十次反向递推 × 上百时间步），动态分配的累计开销吞掉时间预算。这和 G1 §1.5 的算法工程教训同源：实时系统里堆分配是大忌。 - 正确做法：维度编译期已知时用固定大小矩阵（如玩家状态维固定则用Matrix<double, nx_i, nx_i>）栈分配；容器（Z、Ks、ks）求解前一次性resize/reserve，循环里只写不分配；跨 MPC 周期复用 solver 对象的缓冲区。自检方法：用 profiler 看 malloc 占比，或开 Eigen 的EIGEN_RUNTIME_NO_MALLOC在热路径里断言无动态分配。陷阱 2（编程陷阱）：误用 Eigen 块操作的别名（aliasing） - 错误描述：在更新 cost-to-go 时写
Z[i] = F.transpose() * Z[i] * F，源和目标是同一块内存，且中间结果被逐步写回。 - 现象/后果：Eigen 默认假设表达式无别名，原地读写同一矩阵可能在求值中途覆盖还要用的数据，结果错乱——且不报错，数值"看着差不多"但 Riccati 递推悄悄发散。 - 根本原因：Eigen 的惰性求值 + 默认无别名假设，遇到A = f(A)这种自引用表达式（尤其涉及转置、乘积）可能踩别名 bug。 - 正确做法：对可能别名的赋值用.eval()强制先算出临时结果，或用Z[i].noalias()仅在确认无别名时优化。涉及自引用的 Riccati 更新，稳妥做法是写到临时矩阵再 swap。自检方法：结果可疑时，把热路径里所有A = ...A...形式加.eval()看结果是否改变——变了就是别名 bug。陷阱 3（概念误区）：以为读懂 LQSolver 就读懂了 iLQGames - 错误描述：精读完
lq_solver.cc（耦合 Riccati）就以为掌握了整个算法，忽略ILQSolver的外层循环。 - 现象/后果：理解了"解一次 LQ 博弈"，但不清楚线性化、二次化、line search、收敛判据如何串起来，自己实现时漏掉 line search 导致发散（§2.3 陷阱 2）。 - 根本原因：LQSolver只是 §2.3 算法五步里的第 ③ 步；真正让 iLQGames 工作的是ILQSolver把五步组织起来的外层循环，尤其前向 rollout 的 line search。 - 正确做法：精读时LQSolver（反向）和ILQSolver（外层）一起读，重点理解二者的数据交接——ILQSolver喂给LQSolver线性化/二次化的结果，LQSolver返回Strategy，ILQSolver再用它做 rollout。两者缺一不可。
练习¶
- （B 型·源码精读） 克隆
HJReachability/ilqgames，精读src/solver/lq_solver.cc（约 200 行）。标注并用自己的话写出：(a) 耦合 Riccati 反向递推的主循环在哪几行、对应 §2.3 的哪段；(b) 每个时间步如何组装多人 \(Q\)/\(R\) 矩阵与块线性系统；(c) 输出的Strategy里 \(K_i\) 和 \(k_i\) 分别存什么、物理含义是什么。 - （A 型·编译运行） 按 README 用 cmake 编译 ilqgames，运行
./three_player_intersection，用 GUI 观察三智能体博弈。然后修改其中一辆车的PlayerCost（提高其"激进度"），重新编译运行，记录并解释：其余两个智能体（另一辆车、行人）的轨迹如何响应这个更激进的对手？这印证了博弈求解器的什么特性？ - （调试挑战 + 连接 §2.3） 你把 §2.3 的 NumPy 求解器移植到 C++，结果在大碰撞权重下 Riccati 反向递推发散（出现 inf/NaN），但同样参数下 NumPy 版正常。已知算法逻辑正确。请列出至少两个 C++ 特有的可能原因（提示：回顾陷阱 2 的 Eigen 别名、以及未初始化矩阵），并说明如何用 Eigen 的调试宏定位。
§2.5 ALGAMES：硬约束的博弈求解器 ⭐⭐⭐¶
这一节解决什么问题：兑现 §2.3 末尾埋下的伏笔——iLQGames 的 penalty 软约束把两车最小间距停在 0.978 < 1.0，永远差一点。 ALGAMES 用增广拉格朗日**严格**处理硬约束，能把这个 0.978 变成**恰好 1.0、一步不越界**。代价是放弃解析的 Riccati，换成迭代的 KKT 根搜索。
动机：0.978 还不够——安全约束必须"保证"而非"逼近"¶
回到 §2.3 那个实验。 iLQGames 把碰撞当 penalty 软约束，加大权重只能把两车最小间距从 0.871 推到 0.978——仍侵入了 1.0 的安全区，且再加权重要么差一点、要么数值病态。 对很多场景这够用（"尽量别撞"），但对安全关键应用（自动驾驶的碰撞、机械臂的关节限位、无人机的禁飞区），"逼近不违反"和"保证不违反"是天壤之别——你不能对监管机构说"我的车有 97.8% 不撞墙"。 要的是**硬约束**：\(\text{dist}\ge d_{\text{safe}}\) 必须严格成立，一步不让。 这就是 ALGAMES 要解决的问题，也是它与 iLQGames 最根本的分工。
反面案例：继续加大 penalty 权重会怎样¶
假设你固执地用 iLQGames，靠不断调大碰撞 penalty 权重逼近硬约束。 两条死路： 其一，永远差一口气。penalty 的最优解总在"违反一点点换取代价降低"和"惩罚"之间权衡，于是总侵入一点——这是软约束的数学本质（§2.3 陷阱 4），与权重多大无关。 其二，数值病态。权重大到一定程度，二次化代价的 \(Q\) 矩阵条件数爆炸，反向 Riccati 递推变得极度敏感，迭代开始振荡甚至发散。 ALGAMES 论文恰好实测了这点：他们对比 ALGAMES 和 iLQGames，发现 iLQGames 的解会振荡、无法收敛，即便实现了自适应正则化方案去正则化它的 Riccati 反向 pass 也依然如此。 换句话说，软约束逼硬约束这条路，在数值上是走不通的。必须换方法——用拉格朗日乘子显式处理约束。
历史：从 ALTRO 到 ALGAMES¶
ALGAMES（Augmented Lagrangian GAME-theoretic Solver）由 Le Cleac'h、Schwager、Manchester 在 RSS 2020（arXiv:1910.09713）提出，扩展版发表于 Autonomous Robots 46:201–215, 2022（DOI 10.1007/s10514-021-10024-7）。 它的思想根植于单人轨迹优化里成熟的增广拉格朗日方法（如同组的 ALTRO 求解器）——把增广拉格朗日处理约束的能力，从单人最优控制推广到多人博弈。 论文的标志性结果有三个，都值得记住： 它用拟牛顿根搜索满足一阶最优性条件、用增广拉格朗日严格处理一般非线性状态/输入约束；在三车 ramp merging 场景上比当时最先进的 DDP 方法快三倍；其 MPC 实现跑在 60+ Hz，能缓解 frozen robot 问题。 这三点正好对应它的三大卖点：严格约束（AL）、快（拟牛顿 + 比 DDP 快 3 倍）、能上车（60+ Hz MPC 破解 frozen robot）。
理论：把 GNEP 的 KKT 条件当作根搜索¶
ALGAMES 与 iLQGames 的本质区别，是**求解对象**不同： iLQGames 做 DDP 风格的 Riccati 反向递推（得反馈 Nash，约束只能 penalty）； ALGAMES 直接求**广义 Nash 均衡问题（GNEP）的 KKT 条件的根**（得开环 GNE，约束严格）。
每个玩家的约束优化问题。 玩家 \(i\) 在共享约束 \(g(x,u)\le0\)（如碰撞、道路边界）下最小化自己的代价：
这是个**广义** Nash 问题——"广义"指约束 \(g\) 是所有玩家**共享**的（碰撞约束同时约束双方），玩家的可行域相互依赖，比标准 Nash 更难。
KKT 条件。 玩家 \(i\) 的一阶最优性（拉格朗日驻点）+ 原始可行 + 对偶可行 + 互补松弛：
最后那个 \(\lambda_i^\top g=0\) 是**互补松弛**：约束不起作用（\(g<0\)）时乘子为零（\(\lambda_i=0\)），约束起作用（\(g=0\)，恰好贴着安全边界）时乘子可正。这正是"硬约束"的数学刻画——它精确地区分"没碰边界"和"贴着边界"，而 penalty 做不到这个区分。
慢动作：互补松弛为什么能做到 penalty 做不到的事。 互补松弛 \(\lambda_i^\top g=0\) 是 KKT 里最反直觉的一条，但它正是硬约束的灵魂，值得逐步想清楚。 先看它在说什么：\(\lambda_i\ge0\) 且 \(g\le0\)，两者乘积为零，意味着**对每个约束分量，\(\lambda\) 和 \(g\) 不能同时非零**——要么 \(g<0\)（约束有余量）配 \(\lambda=0\)，要么 \(\lambda>0\) 配 \(g=0\)（约束贴边）。 这就把约束分成了泾渭分明的两类：不起作用的（inactive，离边界还远，乘子为零、对最优解无影响）和**起作用的**（active，恰好贴在边界上，乘子顶住它）。
现在对比 penalty 怎么处理同一件事。 penalty 把约束软化成 \(\frac{\rho}{2}\max(0,g)^2\) 这样的代价项——它对"离边界多远"是连续响应的：违反越多罚越多，但**永远没有"贴边界"这个精确状态**。 最优解总停在"罚款的边际 = 收益的边际"那一点，而这一点几乎总在 \(g>0\) 一侧一点点（侵入），因为只要还能通过轻微违反换取主代价下降，penalty 就会允许。 这就是 §2.3 那个 0.978 的来历——penalty 没有"贴边界"的概念，只有"违反到罚款和收益平衡为止"。
互补松弛则不同：它通过乘子 \(\lambda\) 提供了一个**精确顶在边界上的力**。 当约束该起作用时，\(\lambda\) 取一个恰好的正值，使一阶条件 \(\nabla_{u_i}J_i+\nabla_{u_i}g^\top\lambda_i=0\) 成立——这个 \(\lambda\) 就是约束的"影子价格"，它精确抵消了 ego 想越过边界的"动力"，让最优解**恰好落在 \(g=0\) 上**而非内部。 增广拉格朗日的外层迭代干的就是把这个 \(\lambda\) 迭代出来：从一个猜测的 \(\lambda\) 出发，每轮根据约束违反量更新 \(\lambda\leftarrow\max(0,\lambda+\rho g)\)、并增大 \(\rho\)，\(\lambda\) 逐步收敛到那个"恰好顶住边界"的影子价格。
读到这里你可能会问：既然 penalty 加大 \(\rho\) 也能逼近边界，和 AL 迭代 \(\lambda\) 有何本质不同？ 关键区别在**收敛的目标**：纯 penalty 的最优解随 \(\rho\to\infty\) 才趋于边界（且 \(\rho\to\infty\) 时数值病态），它逼近的是一个极限； AL 在**有限**的 \(\rho\) 下，靠 \(\lambda\) 收敛到影子价格就能让解恰好落在边界上——\(\lambda\) 项承担了"精确定位"，\(\rho\) 项只需保证迭代稳定，不必趋于无穷。 这就是为什么 AL 能在 §2.5 的实验里做到"恰好 1.0"而 penalty 永远 0.978：不是 AL 的 \(\rho\) 更大，而是它多了一个 \(\lambda\) 在精确顶住边界。
ALGAMES 的求解策略。 把**所有**玩家的 KKT 条件 (2.4) 堆叠成一个大的非线性方程组 \(G(z)=0\)（\(z\) 含所有玩家的控制、状态、乘子），然后： - 用**拟牛顿法**（quasi-Newton root-finding）求这个方程组的根——每步解一个线性系统（牛顿步），比 iLQGames 的 Riccati 多了外层迭代，但能处理一般约束； - 用**增广拉格朗日（AL）**处理不等式约束——外层迭代更新乘子 \(\lambda\) 和惩罚系数 \(\rho\)，把不等式约束逐步收紧到严格满足。
本质洞察（penalty 软化约束，AL 用乘子"精确定位"约束边界）：penalty 和增广拉格朗日的差别，是"罚款"和"罚款 + 影子价格"的差别。 纯 penalty 只有 \(\frac{\rho}{2}g^2\) 一项——它让违反变贵，但最优解总停在"罚款边际 = 收益边际"的内部，于是总侵入一点（§2.3 的 0.978）。 增广拉格朗日多了乘子项 \(\lambda^\top g\)——这个 \(\lambda\) 在迭代中收敛到约束的**影子价格**，它精确地"顶"住约束边界，使最优解恰好落在 \(g=0\) 上而非内部。 直觉上：penalty 是"墙软软的、撞上去会痛但能进去一点"；AL 是"墙 + 一只手，手的力道（乘子）刚好抵消你往里挤的力，让你停在墙面上"。 这就是为什么 AL 能做到 §2.3 做不到的"恰好 1.0"——乘子收敛后，约束被精确定位在边界上。
实现：增广拉格朗日硬约束求解器¶
把上面的 KKT + AL 思想落成能跑的代码。 对同一个 2 车场景，决策变量改成两车的控制序列（开环表述，符合 ALGAMES 输出开环 GNE 的定位），碰撞约束 \(c_k=d_{\text{safe}}-\text{dist}_k\le0\) 由增广拉格朗日处理（而非 §2.3 的 penalty）：
import numpy as np
from scipy.optimize import minimize
dt, T, N = 0.2, 20, 2
d_safe = 1.0
goal = [np.array([4,0]), np.array([0,4])]
x0_list = [np.array([-3.,0,0,1.0]), np.array([0,-3.,np.pi/2,1.0])]
vmax = None
def rollout_i(x0i, ui_seq):
xs = [x0i.copy()]
for k in range(T):
px, py, th, v = xs[-1]; om, a = ui_seq[k]
xs.append(xs[-1] + dt*np.array([v*np.cos(th), v*np.sin(th), om, a]))
return np.array(xs)
def unpack(z): return z[:2*T].reshape(T,2), z[2*T:].reshape(T,2)
def constraints_vec(z):
"""所有时间步的约束 c_k = d_safe - dist_k（≤0 即满足）。"""
u0, u1 = unpack(z)
X0, X1 = rollout_i(x0_list[0], u0), rollout_i(x0_list[1], u1)
return np.array([d_safe - np.linalg.norm(X0[k][:2]-X1[k][:2]) for k in range(T+1)])
def player_costs(z):
"""两玩家代价：到目标 + 控制能耗（碰撞由 AL 约束处理，不进代价）。"""
u0, u1 = unpack(z)
X0, X1 = rollout_i(x0_list[0], u0), rollout_i(x0_list[1], u1)
J0 = np.sum((X0[-1][:2]-goal[0])**2) + 0.05*np.sum(u0**2) + 0.02*np.sum((X0[:,:2]-goal[0])**2)
J1 = np.sum((X1[-1][:2]-goal[1])**2) + 0.05*np.sum(u1**2) + 0.02*np.sum((X1[:,:2]-goal[1])**2)
return J0, J1
def al_solve():
"""增广拉格朗日外层：交替'内层最小化 AL'与'更新乘子λ、惩罚ρ'。"""
z = np.zeros(4*T); lam = np.zeros(T+1); rho = 1.0
for outer in range(12): # 外层乘子迭代
def auglag(z):
J0, J1 = player_costs(z); c = constraints_vec(z)
al = 0.0
for k in range(T+1): # 不等式约束的 AL（Hestenes-Powell）
if lam[k] + rho*c[k] > 0:
al += lam[k]*c[k] + 0.5*rho*c[k]**2
else:
al += -0.5*lam[k]**2/rho
return J0 + J1 + al # 联合目标（简化对称 GNE）
z = minimize(auglag, z, method='L-BFGS-B', options={'maxiter':200}).x
c = constraints_vec(z)
lam = np.maximum(0, lam + rho*c) # 乘子更新 ← 关键：λ 收敛到影子价格
rho *= 2.0 # 惩罚递增
return z
z = al_solve()
c = constraints_vec(z); max_viol = np.max(c) # >0 表示侵入
u0, u1 = unpack(z)
X0, X1 = rollout_i(x0_list[0], u0), rollout_i(x0_list[1], u1)
min_gap = min(np.linalg.norm(X0[k][:2]-X1[k][:2]) for k in range(T+1))
print(f"ALGAMES(AL硬约束): 最小间距={min_gap:.4f} (d_safe={d_safe})")
print(f"最大约束违反={max_viol:.6f} (<=0 即严格满足)")
# 实跑输出: 最小间距=1.0000 最大约束违反=0.000004
关键就在 lam = np.maximum(0, lam + rho*c) 这行——它是前面"慢动作"讲的乘子更新，让 \(\lambda\) 逐步收敛到精确顶住边界的影子价格。
把它和 §2.3 的 penalty 代码对比：§2.3 把碰撞写进 costs_and_derivs 的二次代价（软惩罚），这里把碰撞从代价里拿出来、交给 constraints_vec + AL 外层严格处理——这一处代码差异，就是 0.978 和 1.0000 的全部来源。
实现验证：ALGAMES 把 0.978 变成 1.0000¶
兑现伏笔的时候到了。 对**完全相同**的 2 车交叉路口场景（car0 沿 +x、car1 沿 +y，安全距离 \(d_{\text{safe}}=1.0\)），把碰撞从 iLQGames 的 penalty 改成 ALGAMES 的增广拉格朗日硬约束（\(c=d_{\text{safe}}-\text{dist}\le0\)，外层迭代乘子 \(\lambda\) 与惩罚 \(\rho\)），跑出来：
| 求解器 | 约束处理 | 两车最小间距 | 最大约束违反 | 是否严格满足 \(d_{\text{safe}}=1.0\) |
|---|---|---|---|---|
| iLQGames（§2.3） | penalty 软约束（\(w=300\)） | 0.978 | +0.022 | 否（侵入 0.022） |
| ALGAMES（本节） | 增广拉格朗日硬约束 | 1.0000 | +0.000004 | 是（机器精度级满足） |
白纸黑字——ALGAMES 把最小间距从 0.978 推到 1.0000，最大约束违反仅 \(4\times10^{-6}\)（机器精度，等价于严格满足），两车仍都抵达各自目标。 这就是 §2.3 埋的那句"ALGAMES 会把它变成恰好 1.0"的实证。 软约束逼近、硬约束保证——一个 0.978 vs 1.0000 的数字，把两种方法的本质差异钉死了。
实现说明：上面用的是简化的对称 GNE 表述（联合目标 + Hestenes-Powell 形式的不等式 AL，外层 12 次乘子更新、\(\rho\) 翻倍）。真实的 Algames.jl 对每个玩家的 KKT 分别处理、用拟牛顿求根，但"AL 把约束逼到严格满足"的核心机制一致。这段代码可独立运行，重在演示硬约束的效果。
iLQGames vs ALGAMES：完整对比¶
把 §2.2、§2.3 和本节的所有维度汇总成一张决策表——这是规格 B 型论文对比任务的核心，也是 §2.8 选型的基础：
系统性分类（iLQGames vs ALGAMES 的六维对比）：
| 维度 | iLQGames | ALGAMES |
|---|---|---|
| 均衡类型 | 反馈 Nash | 开环 GNE（广义 Nash） |
| 信息结构 | 反馈（策略依赖当前状态 \(x\)） | 开环（策略仅依赖初始状态） |
| 抗扰能力 | 强（\(K\) 自动纠偏） | 弱（需高频 MPC 补偿） |
| 约束处理 | 弱（penalty 软约束，0.978<1.0） | 强（AL + 互补，严格满足 1.0） |
| 每步子问题 | 耦合 Riccati（解析，一次反向 pass） | 拟牛顿根搜索（迭代解 KKT 线性系统） |
| 求解速度 | 毫秒级（滚动时域<50ms） | 60+ Hz（比 DDP 快 3×，但慢于 iLQGames） |
| 上车方式 | 天然反馈，可直接闭环 | 必须配高频 MPC 获反馈效果 |
| 参考实现 | C++（ilqgames） | Julia（Algames.jl） |
这张表揭示的核心权衡：iLQGames 强在"反馈 + 快"、弱在"约束"；ALGAMES 强在"约束严格"、弱在"开环（需 MPC 补偿）+ 相对慢"。 两者不是谁取代谁，而是互补——§2.8 会给出"什么场景选哪个"的决策树。
多视角理解（两条路 ↔ 优化里的两大约束处理范式）：iLQGames 和 ALGAMES 的分野，其实是数值优化里两大约束处理范式在博弈语境的投影。 相似之处：单人最优控制里也有这对——DDP/iLQR（把约束 penalty 进代价、做 Riccati）vs 直接法 + SQP/内点（把约束显式交给 NLP 求解器）。iLQGames 继承前者、ALGAMES 继承后者。 不同之处：博弈把"一个优化"变成"耦合的多个优化求不动点"，于是 iLQGames 的 Riccati 变成耦合 Riccati、ALGAMES 的 KKT 变成 GNEP 的堆叠 KKT——复杂度都因玩家耦合而上升。 一句话：如果你熟悉单人轨迹优化里 "DDP vs 直接法+SQP" 的取舍，就已经理解了 iLQGames vs ALGAMES 的取舍——博弈只是给两者各加了一层玩家耦合。 这也预告了 §2.7 的 DG-SQP——它正是把"直接法 + SQP"这一支在博弈里推到工业级。
⚠️ 常见陷阱¶
陷阱 1（概念误区）：以为 ALGAMES 的开环 GNE 不需要 MPC 就能上车 - 错误描述：看到 ALGAMES 严格满足约束，就以为它的开环解可以直接部署、不用像 §2.2 说的那样配 MPC。 - 现象/后果：开环解在仿真完美（严格满足约束），上实车后扰动让状态偏离名义轨迹，开环序列不纠偏，约束在实际执行中被违反——"严格满足"只在名义轨迹上成立。 - 根本原因：ALGAMES 的约束严格性是针对**名义轨迹**的；它输出的是开环策略（§2.2），本身不含反馈纠偏。实际状态一偏，名义轨迹上的约束保证就不再适用。 - 正确做法：ALGAMES 必须配高频 MPC（论文的 60+ Hz 正是为此）——每拍用当前实际状态重解，让"高频重规划"逼近反馈、并在新状态上重新保证约束。这恰是 §2.2 讲的"开环 + MPC = 准反馈"。
陷阱 2（思维陷阱）：在不需要硬约束的场景盲目上 ALGAMES - 错误描述：觉得 ALGAMES "约束更严格、更高级"，所有场景都用它，弃用 iLQGames。 - 现象/后果：在"尽量避免碰撞"就够用的场景（如开阔区域多车协调），付出了 ALGAMES 更慢、需配 MPC、实现更复杂的代价，却没用上硬约束的好处；还丢了 iLQGames 反馈解的抗扰优势。 - 根本原因：硬约束不是免费的——AL 的外层乘子迭代比一次 Riccati 慢，开环解还需 MPC 补偿抗扰。只有当"必须严格满足约束"时，这些代价才值得。 - 正确做法：按需选型（§2.8）。安全关键、约束必须严格满足 → ALGAMES；要反馈抗扰、约束"尽量满足"即可、要极致速度 → iLQGames。很多实际系统甚至两者结合：iLQGames 出反馈策略 + CBF/可达性（G1、G4）兜底硬安全约束。
练习¶
- （A 型·对比实验） 用 Algames.jl 复现一个 3 车 ramp merging 场景，并用 §2.3 的 iLQGames（或 iLQGames.jl）求解同一场景。定量对比三项：(a) 约束满足精度（最小车间距 vs 安全距离，验证 ALGAMES 严格、iLQGames 侵入）；(b) 单次求解时间；(c) 轨迹差异（开环 GNE vs 反馈 Nash）。把结果填进本节的对比表，验证"ALGAMES 严格满足、iLQGames 逼近但侵入"。
- （概念推导） 写出本节 2 车碰撞约束 \(\text{dist}\ge d_{\text{safe}}\) 的 KKT 条件 (2.4) 的具体形式（含互补松弛）。解释：当两车相距很远（约束不起作用）时，乘子 \(\lambda\) 是多少？当两车恰好贴着安全距离时呢？这个互补关系如何让 ALGAMES 做到"恰好 1.0"而 penalty 做不到？
- （设计 + 连接 §2.2、§2.8） 你要为一辆真实自动驾驶车设计博弈规划模块，要求：(a) 与人类车交互时不僵住（frozen robot）；(b) 严格不违反碰撞约束；(c) 对扰动鲁棒。单用 iLQGames 或单用 ALGAMES 各自缺什么？设计一个结合两者优点的方案（提示：可考虑 iLQGames 反馈 + 硬约束兜底，或 ALGAMES + 高频 MPC，论证你的选择）。
§2.6 SE-IBR：灵敏度增强的迭代最佳响应 ⭐⭐⭐¶
这一节解决什么问题：§2.3 的 iLQGames 靠初始化隐式选均衡，§2.5 的 ALGAMES 也不主动选均衡。但竞速里你想**主动封堵**对手——这是一种特定的均衡选择。 SE-IBR 在迭代最佳响应里加一个灵敏度项，让求解器倾向于"让对手最受限"的那个 Nash，从而在 Nash 框架内做出近似 Stackelberg 的封堵行为。真实四旋翼、Audi TTS 实车都用它落地。
动机：竞速要的不只是"避撞"，而是"封堵"¶
回到 §2.1 系统性分类表的第三行那个"中间道路"——交互是对等的（Nash），但你想要类似 leader 的引导效果。 竞速是最典型的场景。 要赢得多机竞速，光会沿赛道最优行驶、避免碰撞还不够；你得像人类赛车手那样**策略性封堵**（blocking，卡住对手的超车线）、佯动（faking）、伺机超车。 这些都不是单纯的避撞能产生的行为——避撞是"别撞上"，封堵是"主动占住对手想去的位置"。 标准的博弈求解器（iLQGames、纯 IBR）会算出一个 Nash，但当存在多个 Nash 时，它们不会刻意选"封堵对手"的那个。 SE-IBR 要补的就是这个能力：在 Nash 框架内，主动选择倾向于封堵对手的均衡。
反面案例：标准 IBR 为什么封堵不了¶
先看标准 IBR（Iterated Best Response，迭代最佳响应）——一个朴素的求 Nash 的方法： 固定其他玩家的策略，求自己的最优响应；更新；轮到下一个玩家固定别人求自己最优；如此交替，直到没人想改变——收敛到一个 Nash。
标准 IBR 的问题在于它**没有均衡选择能力**。 当博弈有多个 Nash（竞速中"我封堵你"和"你封堵我"可能都是 Nash），IBR 会收敛到哪个，完全取决于初始化和迭代顺序——它随机停在某个 Nash 上，不会刻意挑对自己最有利（封堵对手）的那个。 更本质的是，标准 IBR 在求自己最优响应时，把对手的策略当**完全固定**——它没有建模"我这么走，会逼得对手不得不让"。 这正是 §2.1 Nash 的局限：对手策略是外生固定的，你无法主动塑造它。 结果就是：标准 IBR 求出的 ego 轨迹是"在对手固定轨迹下避撞 + 最优进展"，但不会主动卡位——它把竞争对手当成了一个会避让的移动障碍，而非一个可以被你的走位逼退的对手。
历史：Spica 的无人机竞速¶
SE-IBR（Sensitivity-Enhanced Iterated Best Response）由 Spica、Falanga、Cristofalo、Montijano、Scaramuzza、Schwager 在 RSS 2018（"A Real-Time Game Theoretic Planner for Autonomous Two-Player Drone Racing"，DOI 10.15607/RSS.2018.XIV.040，arXiv:1801.02302）提出。 论文开宗明义点出竞速的本质：要成功，玩家必须不仅最优地沿赛道行驶，还要通过策略性封堵、佯动、伺机超车来与对手竞争，同时避免碰撞；且因为不愿向对手暴露自己的策略，每个玩家必须独立预测对手的未来动作。 他们的关键创新，是在迭代最佳响应中引入**灵敏度分析**——用一个灵敏度项近似"对手会为避免碰撞而对 ego 让步多少"，从而实时逼近 Nash 并产生封堵行为。 后续 Wang、Taubner、Schwager 把它扩展到多智能体 3D 环境（Multi-Agent SE-IBR，Robotics and Autonomous Systems 125:103410, 2020），Wang 等进一步在 **Stanford 的 Audi TTS 实车**上用自行车模型 + 微分平坦做多车竞速验证（T-RO 2021）。 这条线把博弈竞速从仿真一路推到了真实赛车，是 SE-IBR 工程价值的最佳背书。
理论：灵敏度项如何制造封堵¶
标准 IBR 的代价。 玩家 \(i\) 在对手策略 \(u_{-i}\) 固定时，最小化自己的代价：
注意 \(u_{-i}\) 被当成常量——这就是标准 IBR 不会封堵的根源。
SE-IBR 的灵敏度增强。 SE-IBR 的核心思想：ego 不再把对手当固定的，而是建模"对手的最优响应会随 ego 的策略而变"——即把对手的响应 \(u_{-i}^*(u_i)\) 看成 ego 策略的函数（这正是 §2.1 Stackelberg 的精神！但放在 IBR 的迭代里近似实现）。 于是在 ego 的代价里加一个**灵敏度项**，刻画"ego 改变策略时，对手会如何让步"：
第一项是常规代价（但对手响应已是 \(u_i\) 的函数）；第二项是灵敏度项——\(\alpha\) 是权重，\(\partial u_{-i}^*/\partial u_i\) 是**对手最优响应对 ego 策略的灵敏度**，刻画"ego 动一点，对手会让多少"。 直觉：这一项鼓励 ego 选那些能**最大程度逼对手让步**的走位——也就是封堵。
灵敏度 \(\partial u_{-i}^*/\partial u_i\) 怎么算：KKT 隐函数定理。 关键技术难点是计算 \(\partial u_{-i}^*/\partial u_i\)——对手的最优响应对 ego 策略的导数。 对手的最优响应 \(u_{-i}^*\) 是它自己优化问题的解，满足它的 KKT 条件 \(G(u_{-i}^*,\,u_i)=0\)（\(G\) 是对手的一阶最优性条件，依赖 ego 的 \(u_i\) 作为参数）。 对这个隐式方程用**隐函数定理**求导：
也就是说，灵敏度由对手 KKT 系统的雅可比（\(\partial G/\partial u_{-i}\)，即对手最优性条件的 Hessian）和它对 ego 参数的偏导算出。 这个隐函数求导技巧，和 §2.7 的可微博弈、G3 逆博弈里"对均衡求导"是同一套数学——记住它，后面会反复出现。
算法对照：SE-IBR 只比标准 IBR 多一步。 把两套迭代并排写出来，能看清 SE-IBR 的"增量"到底在哪——它不是另起炉灶的新算法，而是在标准 IBR 的最优响应里插了一个灵敏度修正：
标准 IBR（每轮）: SE-IBR（每轮）:
for each player i: for each player i:
固定对手 u_{-i}（视为常量） ① 算对手响应 u*_{-i}(u_i)
u_i ← argmin J_i(u_i, u_{-i}) ② 算灵敏度 ∂u*_{-i}/∂u_i（KKT 隐函数）
③ u_i ← argmin [J_i + α·灵敏度项] ← 唯一增量
直到收敛（无人想改） 直到收敛
左边标准 IBR 求最优响应时把对手当**死的**（常量）；右边 SE-IBR 多了步骤 ①②③——它把对手当**活的**（会随 \(u_i\) 变），并在代价里加灵敏度项 (2.5)。
除了这一处，两者的迭代骨架（轮流更新各玩家、迭代到收敛）完全一样。
所以工程上，把一个已有的标准 IBR 求解器升级成 SE-IBR，只需加灵敏度项的计算与代价修正，不必重写迭代框架——这也是 §2.6 代码骨架里 seibr_ego_cost 在 α=0 时自动退回标准 IBR 的原因。
本质洞察（SE-IBR = 在 Nash 框架内借一点 Stackelberg）：SE-IBR 处在 Nash 和 Stackelberg 之间一个巧妙的位置。 纯 Nash（标准 IBR）把对手当固定——不封堵；纯 Stackelberg 把对手当完全可塑造的 follower——但要求 ego 真的是 leader（有先手、对手乖乖响应）。 竞速里没有明确的 leader（双方对等、同时决策），用不了纯 Stackelberg；但你又想要封堵这种"塑造对手"的效果。 SE-IBR 的解法：保持 IBR 的对等迭代结构（仍在求 Nash），但通过灵敏度项 \(\partial u_{-i}^*/\partial u_i\) 局部地建模"对手会让步"——相当于在每步最优响应里偷偷用了一点 Stackelberg 的"我动你让"。 权重 \(\alpha\) 是旋钮：\(\alpha=0\) 退回标准 IBR（纯 Nash、不封堵），\(\alpha\) 越大越激进地封堵（越像 leader）。 一句话：SE-IBR 用一个灵敏度项，在对等的 Nash 框架里挤出了近似 Stackelberg 的封堵能力——这正是 §2.1 表格第三行那条"中间道路"的数学实现。
灵敏度项的计算结构¶
把灵敏度的计算落成代码结构（封堵行为的完整复现需要真实赛道模型 + 车辆动力学，见下方说明；这里聚焦灵敏度项本身的计算骨架）：
import numpy as np
def opponent_kkt_residual(u_opp, u_ego, params):
"""对手的一阶最优性条件 G(u_opp; u_ego)=0。
u_ego 作为参数进入——对手要避开 ego，所以它的最优性依赖 ego 策略。"""
# ∇_{u_opp} J_opp + 约束项；J_opp 含与 ego 的避撞代价，故依赖 u_ego
return grad_opp_cost(u_opp, u_ego, params)
def sensitivity_dopp_dego(u_opp_star, u_ego, params, eps=1e-6):
"""用 KKT 隐函数定理算 ∂u_opp*/∂u_ego = -(∂G/∂u_opp)^{-1} (∂G/∂u_ego)。
∂G/∂u_opp 是对手最优性条件的雅可比（Hessian），∂G/∂u_ego 是对 ego 的偏导。"""
n_opp, n_ego = len(u_opp_star), len(u_ego)
# 数值雅可比（实际可用自动微分，如 JAX/CasADi，更快更准）
dG_dopp = np.zeros((n_opp, n_opp)) # ∂G/∂u_opp
dG_dego = np.zeros((n_opp, n_ego)) # ∂G/∂u_ego
G0 = opponent_kkt_residual(u_opp_star, u_ego, params)
for j in range(n_opp):
up = u_opp_star.copy(); up[j] += eps
dG_dopp[:, j] = (opponent_kkt_residual(up, u_ego, params) - G0) / eps
for j in range(n_ego):
ue = u_ego.copy(); ue[j] += eps
dG_dego[:, j] = (opponent_kkt_residual(u_opp_star, ue, params) - G0) / eps
return -np.linalg.solve(dG_dopp, dG_dego) # 隐函数定理
def seibr_ego_cost(u_ego, u_opp_star, params, alpha):
"""SE-IBR 的 ego 代价 (2.5)：常规代价 + α·灵敏度项。"""
base = ego_cost(u_ego, u_opp_star, params)
dJ_dopp = grad_ego_cost_wrt_opp(u_ego, u_opp_star, params) # ∂J_i/∂u_{-i}
dopp_dego = sensitivity_dopp_dego(u_opp_star, u_ego, params) # ∂u_{-i}*/∂u_i
sensitivity_term = alpha * dJ_dopp @ dopp_dego @ np.ones_like(u_ego)
return base + sensitivity_term # α=0 退回标准 IBR
核心是 sensitivity_dopp_dego——它用隐函数定理把"对手会让多少"算出来。
实际工程实现（Spica/Wang）用自动微分（而非上面的数值差分）算这些雅可比，更快更准；且在完整的赛道 + 自行车模型 + 微分平坦框架下，灵敏度项才能产生论文中那种显著的封堵行为。
上面的骨架重在展示**灵敏度项的数学结构如何落成代码**——它是 SE-IBR 区别于标准 IBR 的唯一增量，其余迭代结构与标准 IBR 一致。
一个能跑且效果可见的最小例子。 赛道封堵在玩具模型上看不出（见下方说明），但**灵敏度项如何改变 ego 行为**可以在一个单步标量博弈上清晰展示。 设 ego 和 opp 的控制共同影响一个标量状态 \(x=u_e+u_o\)，ego 想让 \(x\to1\)、opp 想让 \(x\to0\)，各自带控制能耗：
import numpy as np
from scipy.optimize import minimize
# ego 代价 Je=(x-1)²+0.1·ue², opp 代价 Jo=(x-0)²+0.1·uo², x=ue+uo
def opp_best_response(ue): return -ue/1.1 # opp 最优响应（解析: dJo/duo=0）
def opp_kkt(uo, ue): return 2*(ue+uo) + 0.2*uo # opp 一阶最优性 G(uo;ue)
def sensitivity(ue, eps=1e-6): # ∂uo*/∂ue 隐函数定理
uo = opp_best_response(ue)
dG_duo = (opp_kkt(uo+eps, ue) - opp_kkt(uo, ue))/eps
dG_due = (opp_kkt(uo, ue+eps) - opp_kkt(uo, ue))/eps
return -dG_due/dG_duo # -(∂G/∂uo)⁻¹(∂G/∂ue)
def ego_cost(ue, alpha):
uo = opp_best_response(ue); x = ue + uo
Je = (x-1)**2 + 0.1*ue**2
if alpha > 0: # 灵敏度增强项
Je += alpha * (2*(ue+uo-1)) * sensitivity(ue) # α·(∂Je/∂uo)·(∂uo*/∂ue)
return Je
for alpha in [0.0, 0.5, 1.0]:
ue = minimize(lambda u: ego_cost(u[0], alpha), [0.5], method='Nelder-Mead').x[0]
print(f"alpha={alpha}: ego控制={ue:.3f}, opp响应={opp_best_response(ue):.3f}")
# 实跑: α=0 → ego=0.840; α=0.5 → ego=1.221; α=1.0 → ego=1.603
# 灵敏度 ∂uo*/∂ue = -0.9091（解析 -1/1.1，数值验证一致）
跑出来：\(\alpha=0\)（标准 IBR）时 ego 控制 0.840；\(\alpha\) 增大到 1.0 时 ego 控制增到 1.603——灵敏度项让 ego 更激进地施加控制去克服对手的对抗（因为它"看到"自己每加一分力、对手会按 \(\partial u_o^*/\partial u_e=-0.909\) 让步）。 这个最小例子虽不含赛道几何，但干净地展示了 SE-IBR 的核心机制：\(\alpha\) 这个旋钮如何通过灵敏度项把 ego 从"被动最优"推向"主动塑造对手"。 灵敏度的数值 \(-0.9091\) 与解析值 \(-1/1.1\) 吻合，验证了隐函数定理实现的正确性。
关于赛道封堵的复现：blocking、faking 这类行为对赛道几何、车辆模型、灵敏度权重 \(\alpha\) 的调校都很敏感，简单的对称玩具模型（如 2D 单积分器直线赛道）往往观察不到明显封堵——这是真实的工程经验。上面的单步标量例子能展示灵敏度项的作用机制，但要复现论文中的封堵/佯动，需用 Spica/Wang 提供的完整赛道竞速框架（含弯道、自行车模型）。本节因此聚焦灵敏度项的原理、计算结构与作用机制，而非给一个简化到失真的"封堵 demo"。
⚠️ 常见陷阱¶
陷阱 1（概念误区）：以为标准 IBR 收敛到的 Nash 就是"会封堵"的均衡 - 错误描述：觉得 IBR 既然在博弈里求 Nash，求出来的 ego 策略自然会包含封堵、卡位等竞争行为。 - 现象/后果：用标准 IBR 做竞速，ego 只会避撞和最优行驶，从不主动卡住对手的超车线，竞速表现像"礼让的陪练"而非"有竞争力的对手"。 - 根本原因：标准 IBR 求最优响应时把对手策略当固定常量——它没建模"我封堵，对手会被迫让"，所以不会主动封堵。多个 Nash 时它还随机停在某个、不挑封堵的那个。 - 正确做法：用 SE-IBR——加灵敏度项 (2.5) 显式建模对手让步，主动选倾向封堵的均衡。检验方法：把 \(\alpha\) 从 0 调大，观察 ego 是否越来越倾向占据对手前方的封堵位（在完整赛道模型下）。
陷阱 2（编程陷阱）：灵敏度项里 KKT 雅可比奇异/病态时直接求逆 - 错误描述：算 \(\partial u_{-i}^*/\partial u_i=-(\partial G/\partial u_{-i})^{-1}\partial G/\partial u_i\) 时，直接对 \(\partial G/\partial u_{-i}\) 求逆，不检查它是否奇异或病态。 - 现象/后果：当对手的最优性条件 Hessian 接近奇异（如约束退化、对手问题非严格凸），求逆得到爆炸的灵敏度，ego 策略剧烈震荡甚至发散。 - 根本原因：隐函数定理要求 \(\partial G/\partial u_{-i}\) 可逆；对手优化问题病态时这个雅可比奇异，求逆数值上不可靠。 - 正确做法：用
np.linalg.solve而非显式求逆；对病态情形加正则化（如 \(\partial G/\partial u_{-i}+\epsilon I\)）或用伪逆；并对灵敏度项做幅值裁剪防止单步过大。检验方法：监控 \(\partial G/\partial u_{-i}\) 的条件数，过大时触发正则化。陷阱 3（思维陷阱）：把灵敏度权重 \(\alpha\) 调得越大越好 - 错误描述：认为 \(\alpha\) 越大封堵越强、竞速越有利，于是把它调到很大。 - 现象/后果：\(\alpha\) 过大时 ego 过度激进地封堵，忽视自身进展和避撞，要么被对手绕过、要么逼出危险接近；灵敏度项主导代价后，求解也容易不收敛。 - 根本原因：灵敏度项是"塑造对手"的奖励，但它与"自身最优进展""避撞"是竞争关系。\(\alpha\) 过大破坏了这个平衡，且灵敏度本身是局部线性近似，大 \(\alpha\) 放大了近似误差。 - 正确做法：把 \(\alpha\) 当需要调校的超参数，在"封堵强度"和"自身进展/安全/收敛性"间折中。从小值起步逐步增大，观察竞速胜率与安全性的折中曲线，取拐点附近的值。
练习¶
- （A 型·实现对比） 对 2 机无人机竞速（可用 2D 单积分器 + 一段有弯道的赛道），实现标准 IBR 和 SE-IBR。对比：(a) SE-IBR 是否更倾向 blocking 行为（ego 是否更多占据对手前方）；(b) 灵敏度权重 \(\alpha\) 从 0 增大时，ego 的封堵强度和竞速胜率如何变化；(c) \(\alpha\) 过大时是否出现震荡或过度激进。注意：需用带弯道的赛道才易观察到封堵（直线对称赛道往往看不出差异）。
- （推导·连接 G3） 推导灵敏度 \(\partial u_{-i}^*/\partial u_i\) 的隐函数定理表达式。从对手的 KKT 条件 \(G(u_{-i}^*,u_i)=0\) 出发，对 \(u_i\) 求全导，解出 \(\partial u_{-i}^*/\partial u_i\)。说明这个"对均衡/最优解求导"的技巧与 §2.7 可微博弈、G3 逆博弈的联系。
- （概念·连接 §2.1） SE-IBR 被描述为"在 Nash 框架内实现近似 Stackelberg 的封堵"。请对照 §2.1 的 Nash (2.1) 和 Stackelberg (2.3) 定义，论证：(a) 为什么竞速用不了纯 Stackelberg（提示：谁是 leader？）；(b) SE-IBR 的灵敏度项 (2.5) 在数学上如何"借用"了 Stackelberg 的 \(u_F^*(u_L)\) 思想；(c) \(\alpha=0\) 时为什么 SE-IBR 退回纯 Nash。
§2.7 GFNE 与 DG-SQP：理论统一与工业级求解 ⭐⭐⭐⭐¶
这一节解决什么问题：前面三套求解器各有短板——iLQGames 反馈但约束弱、ALGAMES 约束严但开环、SE-IBR 能封堵但仍是局部 IBR。 能不能既要反馈、又要严格约束？能不能把博弈求解做到工业级 SQP 那样稳健？这一节讲两个最新进展：GFNE（理论统一反馈 + 约束）和 DG-SQP（工业级 SQP 求解），并展望 2024–2026 前沿。 本节偏研究级，时间紧可先速读，掌握"它们各补了前几代什么短板"即可。
动机：前几代求解器的短板拼图¶
把 §2.3–§2.6 的四套方法摆在一起，会发现一块缺失的拼图。 回顾 §2.5 的对比表：iLQGames 给反馈 Nash（抗扰强），但约束只能 penalty（§2.3 的 0.978<1.0）；ALGAMES 给严格约束，但输出开环 GNE（需 MPC 补偿抗扰）。 两个最想要的性质——反馈信息结构（抗扰）和**严格约束满足**（安全）——分别被两套方法各占一半，没有一套同时拥有。 这不是偶然，而是因为"反馈 + 约束"的数学本身就难：反馈策略是状态的函数，约束又依赖状态和所有玩家的控制，把两者严格地统一在一个框架里，需要处理一层套一层的隐式依赖。 GFNE 正是来填这块拼图的——它把 iLQGames 的反馈结构和 ALGAMES 的严格约束在理论上统一起来。 而另一条线上，DG-SQP 解决的是另一个工程痛点：让博弈求解像成熟的 SQP 优化器那样**稳健可靠**（从更大范围的初始条件收敛），把它从"学术原型"推向"工业级工具"。
GFNE：把反馈 Nash 推广到带约束的博弈¶
GFNE 是什么。 广义反馈 Nash 均衡（Generalized Feedback Nash Equilibrium, GFNE）由 Laine、Fridovich-Keil、Chiu、Tomlin 在 SIAM Journal on Optimization 33(1):294–318, 2023（DOI 10.1137/21M142530X, arXiv:2101.02900）提出。 名字拆开看就懂它的定位： "Feedback Nash"——它要的是反馈均衡（像 iLQGames，策略依赖状态、抗扰）； "Generalized"——它要处理状态和输入**约束**（像 ALGAMES 的"广义" Nash，约束共享）； 合起来：GFNE = 反馈 Nash + 严格约束，正好是前面那块缺失的拼图。 论文把反馈 Nash 均衡的概念推广到玩家受状态/输入约束的博弈，在轨迹层面形式化了（局部）GFNE 解的必要与充分条件。
核心难点：嵌套的隐式导数。 为什么"反馈 + 约束"这么难？论文点出了关键：求解 GFNE 的必要条件，一般需要计算**一系列嵌套的、隐式定义的导数**，这很快变得难以处理（intractable）。 直觉上：反馈博弈里，玩家 \(i\) 在每个时刻的最优反馈，依赖于"未来所有时刻其他玩家的反馈如何随状态变化"——这本身又依赖更未来的反馈……一层套一层。 加上约束后，每一层还要处理约束的隐式依赖（约束起作用时乘子如何随状态变），嵌套求导迅速爆炸。 这正是 §2.6 SE-IBR 那个 \(\partial u_{-i}^*/\partial u_i\) 隐函数求导的"多时刻、带约束"加强版——单步的灵敏度求导已经不简单，GFNE 要在整条轨迹上、带约束地做，难度陡增。
慢动作：用两步博弈看"嵌套"从哪来。 "嵌套的隐式导数"听起来抽象，用一个两时刻的反馈博弈就能看清它怎么层层套起来。 设博弈只有两步 \(k=0,1\)，玩家 \(i\) 在每步用反馈律 \(u_{i,k}(x_k)\)。 反馈 Nash 要求**子博弈完美**（§2.2）——不仅 \(k=0\) 是 Nash，从 \(k=1\) 任意状态出发的剩余博弈也是 Nash。 于是求 \(k=0\) 的最优反馈时，玩家 \(i\) 必须知道"\(k=1\) 时所有玩家的反馈如何随 \(x_1\) 变化"——因为它在 \(k=0\) 选的 \(u_{i,0}\) 会影响 \(x_1\)，而 \(x_1\) 又决定 \(k=1\) 大家怎么反应、进而决定 \(i\) 在 \(k=1\) 的剩余代价。
把这个依赖链拆开看： \(i\) 在 \(k=0\) 的最优性，依赖 \(\partial u_{j,1}^*/\partial x_1\)（对手在 \(k=1\) 的反馈对状态的灵敏度）——这是**第一层**隐式导数； 而 \(u_{j,1}^*\) 本身是 \(j\) 在 \(k=1\) 的 KKT 解，求 \(\partial u_{j,1}^*/\partial x_1\) 又要对 \(j\) 的 KKT 条件用隐函数定理——这里面还嵌着所有**其他**玩家在 \(k=1\) 的反馈（因为 \(j\) 的最优依赖别人的反馈），于是又冒出 \(\partial u_{l,1}^*/\partial x_1\)…… 两步博弈就已经是"我对你的反应求导、而你的反应里又含着对他的反应"。 真实问题有上百个时间步，这个链从 \(k=T\) 一路嵌套回 \(k=0\)，每往前一步、每多一个玩家、每多一个起作用的约束，嵌套就深一层——这就是论文说的"嵌套隐式导数迅速变得难解"。 一句话：嵌套来自反馈博弈的子博弈完美性 × 玩家间耦合 × 时间维度的三重叠加——任何一维单拎出来都不难，三者相乘就爆炸。
解法：近似 + 牛顿式求解（SLQG）。 GFNE 的破解之道是"近似"——这也是论文标题里"Approximate"的来历。 他们引入一个对必要条件的**近似**，使其便于高效求值，进而能数值求解； 然后用**牛顿式方法**求满足（近似）必要条件的博弈轨迹，再对照充分条件检验。 具体算法是 SLQG（Sequential Linear-Quadratic Games）——每步解一个**约束 LQ 博弈**（一次 LCP / 混合互补问题），思想上是 iLQGames"反复解 LQ 博弈"的带约束版本：iLQGames 每步解无约束耦合 Riccati，GFNE 的 SLQG 每步解带约束的 LQ 博弈（多了互补条件）。
本质洞察（GFNE = iLQGames 的骨架 + ALGAMES 的约束处理）：理解 GFNE 最快的方式，是看它如何缝合前两套方法。 它保留 iLQGames 的"反复解 LQ 博弈"骨架（所以输出反馈、保留抗扰）； 又把 ALGAMES 的"严格约束 + 互补条件"塞进每步的 LQ 博弈（所以约束严格）； 代价是每步子问题从"解析的耦合 Riccati"升级成"带约束的 LQ 博弈（LCP）"——比 Riccati 贵，且必要条件要用近似才算得动。 一句话：GFNE 用"每步解约束 LQ 博弈 + 必要条件近似"，换来了 iLQGames 和 ALGAMES 都没有的'反馈 + 严格约束'组合——这是博弈求解理论统一方向的里程碑，但计算代价和实现复杂度也最高。 这也回答了规格里那个开放问题"如何在 iLQGames 中正式处理状态约束"——GFNE 给出了理论答案，尽管尚未像 iLQGames 那样有广泛部署的实时实现。
DG-SQP：把博弈求解做成工业级 SQP¶
DG-SQP 是什么。 DG-SQP（Dynamic Game SQP）由 Zhu 与 Borrelli 提出（arXiv:2404.00186, 2024；前身 arXiv:2203.16478, 2022），是 UC Berkeley MPC Lab 的工作。 它求解开环一般和动态博弈的局部 GNE（和 ALGAMES 同属开环 GNE 阵营），但走的是经典数值优化里最成熟的一条路——序贯二次规划（SQP）： 每次迭代只需求解**一个凸二次规划（QP）**。 这与 iLQGames（解析 Riccati）、ALGAMES（拟牛顿 + AL）都不同——DG-SQP 把博弈的 KKT 系统当成一个非线性方程组，用 SQP 迭代逼近，每步线性化成一个 QP 子问题。
三个让它稳健的关键设计。 DG-SQP 的贡献不在"用 SQP"这个想法本身（直接法 + SQP 是成熟优化技术），而在三个让它在博弈语境下稳健收敛的工程设计： 其一，非单调线搜索（non-monotonic line search）——求解 KKT 方程时，不强求每步 merit 函数单调下降（博弈的 KKT 残差不像单人优化那样有良好的下降性质），允许暂时上升以跳出局部停滞； 其二，处理零和代价的 merit 函数——博弈里玩家代价可能此消彼长（零和分量），普通 merit 函数会失效，需专门设计； 其三，衰减正则化（decaying regularization）——SQP 步选择时加正则化保证 QP 子问题良态，并随迭代衰减以不损害最终精度。 论文证明该方法在局部 GNE 邻域达到**线性收敛**。
为什么重要：成功率而非速度。 DG-SQP 的卖点不是"更快"，而是"更可靠"。 在 head-to-head（一对一）赛车场景下，论文把 DG-SQP 与当时最先进的、基于混合互补问题（MCP）的 PATH 求解器做了细致对比：在用**精确** Frenet 运动学表述的博弈上，两者成功率**相当**；而当用一种**近似** Frenet 表述（论文的第二个贡献，借 MPCC 思想改善数值鲁棒性）时，DG-SQP 相比 PATH 成功率显著提升、最多达 32%。 这个区分很重要——DG-SQP 不是全面碾压 PATH，而是在它配套的近似表述下展现出鲁棒性优势；如实理解这一点，才不会夸大它的能力。 这个指标很关键——前几代求解器（包括 iLQGames、ALGAMES）的一个共同痛点是**对初始化敏感、容易不收敛**（§2.3 陷阱 5、§2.5 都提过）。 DG-SQP 通过借鉴成熟 SQP 的稳健化技术（非单调线搜索、merit 函数、正则化），把"能从多大范围的初始条件收敛"这件事显著改善了。 对工程部署而言，"95% 的情况能解出来"和"60% 的情况能解出来"是天壤之别——这正是 DG-SQP 把博弈求解推向工业级的意义。
多视角理解（三套开环求解器 ↔ 数值优化的演进史）：把 ALGAMES、GFNE、DG-SQP 放进数值优化的历史脉络，它们的关系就清晰了。 相似之处：三者都在求"满足 KKT 的博弈轨迹"，都是把单人约束优化的成熟技术搬到博弈——ALGAMES 搬的是增广拉格朗日、GFNE 搬的是带约束的牛顿法、DG-SQP 搬的是 SQP。 不同之处：它们对应单人优化里不同的约束处理流派，各有稳健性/速度/约束严格性的权衡；DG-SQP 尤其继承了 SQP 几十年积累的稳健化技巧（线搜索、merit 函数、正则化），所以收敛性最好。 一句话：博弈求解器的演进，很大程度是在重走单人数值优化走过的路——把 AL、牛顿法、SQP 这些经典武器逐一武装到博弈上。 这条类比的价值：你对单人优化求解器的所有认识（SQP 为什么稳、AL 怎么调 \(\rho\)）几乎都能迁移过来。
一个统一视角：开环 GNE = 混合互补问题（MCP）¶
把 ALGAMES、DG-SQP、PATH 这几套开环求解器真正统一起来的，是一个深刻的观察：开环动态博弈求 GNE，可以表述成一个混合互补问题（Mixed Complementarity Problem, MCP）。 这值得单独点出，因为它解释了为什么这些看似不同的方法能互相比较、甚至互换。
回顾 §2.5 的 KKT 条件 (2.4)：每个玩家的一阶最优性 + 互补松弛 \(\lambda_i^\top g=0\)。 把所有玩家的 KKT 堆叠起来，那些等式（一阶最优性）和互补不等式（\(\lambda\ge0,\ g\le0,\ \lambda^\top g=0\)）合在一起，正好是 MCP 的标准形式——一组变量，部分满足等式、部分满足互补关系。 于是"求开环 GNE"就等价于"解这个 MCP"，而 MCP 是运筹学/变分不等式领域研究了几十年的成熟问题（Facchinei-Pang 的经典理论）。
这个统一视角立刻带来三个洞察： 其一，PATH 求解器（Dirkse-Ferris 1995，"求解 MCP 的非单调稳定化方案"）本是运筹学里求解 MCP 的通用工具，可以**直接拿来**解博弈的 GNE——这就是为什么 DG-SQP 拿 PATH 当对比基线：它们解的是同一个 MCP，只是算法不同。 其二，ALGAMES 的"AL 处理互补约束"、DG-SQP 的"SQP 逼近 KKT"、PATH 的"MCP 稳定化"，本质都是**求解同一个 MCP 的不同数值策略**——这呼应了上面"重走单人优化老路"的多视角。 其三，MCP 视角也揭示了开环 GNE 求解的**固有难点**：MCP 一般非凸、可能多解（对应多个 GNE）、可能无解，这正是这些求解器都面临收敛性挑战的根源（DG-SQP 的稳健化、ALGAMES 的正则化都是在和 MCP 的这些病态作斗争）。
本质洞察（KKT 堆叠 → MCP → 通用求解器）：从单个玩家的优化，到博弈的 GNE，再到 MCP，是一条逐步"通用化"的抽象阶梯。 每上一级，问题就接入一套更成熟的数学机器：玩家优化接 KKT、博弈 GNE 接 MCP、MCP 接 PATH 这类通用求解器。 这条阶梯的工程价值在于：你不必为博弈从零造求解器——把它化成 MCP，几十年的互补问题理论和现成求解器（PATH）就都能用上。 这也是为什么 §2.7 的前沿工作（如把 GNE 当 MCP 用 PATH 解）和 DG-SQP 能站在同一个擂台上比较——它们共享 MCP 这个底层语言。 （注：这条 MCP 视角主要适用于**开环** GNE；反馈 GFNE 因嵌套隐式导数，结构比 MCP 更复杂，不能简单归约。）
2024–2026 前沿¶
博弈求解仍在快速演进，几个值得关注的方向（部分工作较新、临近本资料知识边界，细节以原文为准）：
- Contingency Games（应急博弈）（Peters 等，2024）：把博弈与分支规划融合——在博弈均衡中加入 contingency 约束（一段共享的"干"轨迹 + 针对对手不同意图的"分支"），处理"对手意图不确定"的场景。这是博弈 + 分支规划（U 线的分支场景规划）的交叉，回应了"对手意图不确定怎么办"这个 Nash/Stackelberg 都回避的问题。
值得展开一下，因为它补的是本章所有方法的一个共同盲区。 §2.1–§2.7 的求解器都默认**对手的代价/意图已知**（iLQGames 要写出对手的代价、SE-IBR 要知道对手的优化问题才能算灵敏度）。 但真实交互里对手意图常常是**不确定**的——路口那辆车到底是要直行还是右转？ Contingency Games 的解法借自鲁棒/分支规划：规划一段两种意图都安全的"共享干轨迹"（在意图揭晓前执行），再为每种可能意图各备一条"分支轨迹"（意图明确后切换）。 这样既不必在意图揭晓前就赌一个猜测（避免抢行），又不会像最坏情况规划那样过度保守（frozen）。
多视角理解（Contingency Games 与 U 线分支场景规划）：这正是 U 线"分支场景规划"思想在博弈语境的投影。 相似之处：两者都用"共享干 + 多分支"结构处理未来的不确定分叉，都在"过早承诺"和"过度保守"之间找平衡。 不同之处：U 线的分支规划处理的是**环境/对手轨迹**的不确定（对手被当作随机或最坏情况的外生量）；Contingency Games 把对手升级为**博弈玩家**（对手也在优化、也会对 ego 反应），于是每条分支内部还要解一个博弈。 一句话：Contingency Games = 分支场景规划 乘以 博弈——把"对手意图不确定"和"对手是决策者"两件事同时处理，是 G2 求解器与 U 线不确定性规划的交汇点。（U 线会从分支规划那一侧再讲这个结构。） - MaxEnt Multi-Agent Dynamic Games（最大熵多智能体动态博弈）（Mehr、Schwager 等，T-RO 2023）：用 softmax Bellman 处理**有界理性**——真实的人/对手不是完美最优的，带随机性。最大熵框架让正向求解（算均衡）和逆向求解（从行为反推代价，G3）统一起来，也呼应了 §2.1 陷阱 2 提的"对手有界理性"问题。 - Implicit GT-MPC（隐式博弈论 MPC）：把离线训练的 GNE 数据用来学一个值函数，当作 MPC 的终端代价——用离线学习换在线计算，思想上类似 §1.7 的 DeepReach（神经近似换可扩展）在博弈语境的投影。
开放问题（规格列出、至今仍开放）：如何在 iLQGames 中正式处理状态约束（GFNE 给了理论答案但实时实现仍难）？如何保证多 Nash 中选到"好"的那个（SE-IBR 的封堵、初始化引导都只是部分答案）？iLQGames 的局部收敛如何获得全局初始化（DG-SQP 改善了收敛域但未根治）？这些问题串起了本章所有方法的共同局限——它们都是**局部**方法，全局性和均衡选择仍是博弈规划的根本挑战。
把这些开放问题归纳成三个根本挑战，它们贯穿本章所有方法、也指向未来：全局性（所有方法都是基于梯度/牛顿的局部方法，依赖好的初始化，无全局最优保证）、均衡选择（多 Nash 时选哪个仍是设计决策，SE-IBR/初始化引导只是局部抓手）、模型不确定（对手代价/意图未知或有界理性，Contingency/MaxEnt Games 刚开始触及）。 本章的演进可以看成对这三者的逐步进攻：iLQGames→ALGAMES→GFNE 主攻"约束 + 信息结构"、DG-SQP 主攻"收敛域（全局性的一部分）"、SE-IBR 主攻"均衡选择"、前沿的 Contingency/MaxEnt 主攻"模型不确定"。 没有一个方法同时解决三者——这既是博弈规划尚未成熟的标志，也是它仍是活跃研究领域的原因。
⚠️ 常见陷阱¶
陷阱 1（概念误区）：以为 GFNE 已经是可以替代 iLQGames 的实时方案 - 错误描述：看到 GFNE "反馈 + 严格约束"两全其美，就以为它能直接替代 iLQGames 上车。 - 现象/后果：试图把 GFNE 用在需要毫秒级实时的场景，发现它的每步子问题（带约束 LQ 博弈 / LCP）+ 必要条件近似的计算远比 iLQGames 的解析 Riccati 重，达不到同等实时性。 - 根本原因：GFNE 的理论统一是有代价的——嵌套隐式导数即便用了近似仍比 Riccati 贵，且实现复杂度高。它是理论里程碑，尚无 iLQGames 那样成熟的高频实时部署。 - 正确做法：按需求选——要极致实时 + 反馈、约束"尽量满足"即可，用 iLQGames；要严格约束，看是否能接受开环 + MPC（ALGAMES）或承担 GFNE 的计算代价。GFNE 目前更多是研究工具和理论参考。
陷阱 2（思维陷阱）：用"求解速度"评判 DG-SQP，得出它不如 iLQGames 的结论 - 错误描述：拿单次求解时间比较，发现 DG-SQP（每步解 QP + SQP 迭代）比 iLQGames（解析 Riccati）慢，就判定 DG-SQP "不行"。 - 现象/后果：错过 DG-SQP 真正的价值，在需要高可靠收敛的场景仍用易发散的方法，遇到求解失败束手无策。 - 根本原因：DG-SQP 的设计目标是**成功率/稳健性**（从大范围初始条件收敛），不是单次速度。它用 SQP 的稳健化技术换收敛可靠性——成功率比 PATH 提升 32% 才是它的核心指标。 - 正确做法：按场景的核心需求选指标。对收敛可靠性要求高（如多变的赛车超车、初始化难暖启动）的场景，DG-SQP 的"高成功率"比 iLQGames 的"快但可能不收敛"更有价值；反之要极致速度则选 iLQGames。速度和成功率是两个维度，别用一个否定另一个。
练习¶
- （概念对比·B 型论文阅读） 精读 GFNE（Laine et al. SIOPT 2023）的摘要与算法部分。回答：(a) GFNE 相比 iLQGames 多处理了什么、相比 ALGAMES 多保留了什么？(b) "嵌套的隐式导数"难在哪里，为什么需要近似？(c) SLQG 每步解的"约束 LQ 博弈"与 iLQGames 每步的"无约束耦合 Riccati"差在哪？把三套方法（iLQGames/ALGAMES/GFNE）的每步子问题并排列出。
- （A 型·DG-SQP 运行） 克隆
zhu-edward/DGSQP，运行其 head-to-head 赛车示例。观察并记录：(a) SQP 每步的 QP 子问题如何用 CasADi 构造；(b) 非单调线搜索在哪里、它允许 merit 函数暂时上升的效果；(c) 从不同初始条件出发，DG-SQP 的收敛成功率（与是否易发散对比）。 - （综合思考·连接全章） 本章五套方法（iLQGames、ALGAMES、SE-IBR、GFNE、DG-SQP）都是**局部**方法，都面临"全局初始化"和"多 Nash 选择"的根本挑战。请论证：(a) 为什么局部性是这些基于梯度/牛顿的方法的固有限制；(b) §2.7 的前沿工作（Contingency Games、MaxEnt Games）各从什么角度部分缓解了这些挑战；(c) 如果让你设计下一代求解器，你会优先攻克全局性还是均衡选择？为什么？
§2.8 综合对比与选型 ⭐⭐¶
这一节解决什么问题：前面讲了五套求解器（iLQGames、ALGAMES、SE-IBR、GFNE、DG-SQP）+ 两种均衡概念（Nash、Stackelberg）。 面对一个真实交互场景，到底该用哪个？这一节把全章串成一棵可操作的选型决策树，并给出工程落地的组合策略。
动机：纸上谈兵 vs 工程决策¶
学完五套方法，真正的考验是落地：给你一个具体场景——城市自动驾驶的无保护左转、F1 级别的无人机竞速、仓库里多机器人协调、人车混行的路口——你该选哪套求解器？ 这不是"哪个最先进"的问题（GFNE/DG-SQP 最新不代表最该用），而是"哪个最匹配你的需求约束"的问题。 选型要同时权衡四个维度：均衡概念（对等还是层级）、信息结构（要不要反馈抗扰）、约束严格性（安全约束是"尽量"还是"必须"）、计算预算（毫秒级单次还是 60 Hz 重规划够用、单次速度还是收敛成功率优先）。 本节给一棵决策树，把这四个维度的权衡落成可执行的选择。
全景对比表¶
先把全章方法的所有维度汇总成一张总表（这是 §2.2、§2.5、§2.7 各对比表的合并升级版）：
| 方法 | 均衡类型 | 信息结构 | 约束处理 | 速度/特点 | 参考实现 | 最适场景 |
|---|---|---|---|---|---|---|
| iLQGames | 反馈 Nash | 反馈（抗扰强） | 弱（penalty，逼近） | 毫秒级（解析 Riccati，<50ms） | C++ ilqgames | 极致实时、对等交互、约束"尽量满足" |
| ALGAMES | 开环 GNE | 开环（需 MPC） | 强（AL，严格） | 60+ Hz（比 DDP 快 3×） | Julia Algames.jl | 安全关键、约束必须严格、可配 MPC |
| SE-IBR | Nash（偏封堵） | 反馈/滚动 | 中（penalty + 灵敏度） | 实时（IBR 迭代） | 论文/实车 | 竞速、需主动封堵对手 |
| GFNE | 广义反馈 Nash | 反馈 + 约束 | 强（互补） | 慢（约束 LQ 博弈 + 近似） | 研究原型 | 理论需"反馈 + 严格约束"两全 |
| DG-SQP | 开环 GNE | 开环（需 MPC） | 强（SQP + 约束） | 中（高成功率） | Python DGSQP | 收敛可靠性优先、初始化难的赛车超车 |
| Stackelberg（Sadigh） | Stackelberg | 层级 | 视实现 | 双层优化 | 论文 | 人车交互、AV 主动引导人类 |
这张表是选型的"参数手册"。下面把它转成决策流程。
选型决策树¶
系统性分类（博弈求解器选型决策树）：按四个问题依次决策——
Q1: 交互是对等的，还是有明确先后（一方公示、另一方响应）？
├─ 有明确先后（人车、AV引导人类）
│ → Stackelberg 式规划（Sadigh 2016）；需准确预测 follower 响应（IRL 学）
│ 若 follower 有界理性 → 考虑 MaxEnt Games（§2.7）
└─ 对等（竞速、多车 merge、多机协调）→ 进入 Q2
Q2: 安全约束是"尽量满足"，还是"必须严格满足"？
├─ 尽量满足即可（开阔区域协调、约束不紧）→ 进入 Q3
└─ 必须严格满足（碰撞、关节限位、禁飞区）
→ ALGAMES（开环 GNE + AL，配高频 MPC 补抗扰）
或 GFNE（若必须同时要反馈，且能承担计算代价）
或 iLQGames + CBF/可达性兜底（G1/G4，见下方组合策略）
Q3: 你需要的核心能力是什么？
├─ 极致实时 + 反馈抗扰 → iLQGames（毫秒级、解析 Riccati、天然反馈）
├─ 主动封堵对手（竞速博弈行为）→ SE-IBR（灵敏度项偏向封堵）
└─ 收敛可靠性优先（初始化难、易发散）→ DG-SQP（SQP 稳健化、成功率高 32%）
这棵树的四层正好对应四个权衡维度：Q1 选均衡概念、Q2 选约束严格性、Q3 选核心能力。 注意 Q2 的"必须严格满足"分支给了三个选项——这反映了一个现实：严格约束 + 反馈 + 实时这三者目前没有单一方法全占，要么牺牲一个（ALGAMES 牺牲反馈、GFNE 牺牲速度），要么用组合策略。
工程落地的组合策略¶
实际系统很少只用一套方法，而是组合。最常见的两种：
组合一：iLQGames（反馈 + 实时）+ CBF/可达性安全层（硬约束兜底）。 这是最实用的组合，融合 G1、G2、G4。 用 iLQGames 求反馈 Nash（拿到毫秒级实时 + 抗扰的交互策略），但它的 penalty 软约束保证不了硬安全（§2.3 的 0.978<1.0）； 于是在它输出的控制上串一个安全滤波器——CBF（G4）或 HJI 可达性的最小限制控制器（G1 §1.4）——作为最后一道防线，把任何会违反硬安全约束的控制投影到安全集内。 这样既有 iLQGames 的实时反馈交互，又有可证明的硬安全保证。 这正是 G1 §1.4 那条"HJI 安全值函数 ↔ CBF"伏笔在工程上的兑现：博弈求解器管"怎么交互得好"，安全层管"绝不越界"。
组合二：ALGAMES/DG-SQP（开环 GNE + 严格约束）+ 高频 MPC（补反馈）。 这是 §2.2 反复讲的标准姿势。 用 ALGAMES 或 DG-SQP 求严格满足约束的开环 GNE，但开环不抗扰（§2.2）； 于是套一个高频 MPC 循环（60+ Hz），每拍用当前实际状态重解、只执行第一步——用"高频重规划"逼出反馈效果。 ALGAMES 论文的 60+ Hz MPC 实现、DG-SQP 的赛车部署都是这个模式。 适合约束必须严格、且能负担高频重规划计算预算的场景。
本质洞察（没有银弹，组合是常态）：本章五套方法没有一个是"最优解"——每个都在"反馈 / 约束严格 / 实时 / 收敛可靠 / 均衡选择"这五个维度上有取舍。 工程落地的智慧不在于挑一个"最强"的，而在于**根据场景的核心约束选主求解器、再用辅助层补短板**。 想要反馈 + 硬安全 → iLQGames + CBF；想要严格约束 + 抗扰 → ALGAMES + MPC；想要封堵 → SE-IBR；想要收敛可靠 → DG-SQP。 一句话：选型的本质是"识别你的场景里哪个维度不可妥协，把它作为主轴选求解器，其余维度用组合策略补齐"——这比追逐"最先进的单一方法"重要得多。 这也呼应 G1 的主线：从 HJI 的"理论最优但算不动"，到 G2 的"局部近似但实时"，再到这里的"组合策略补短板"——博弈规划的工程化，始终是在理想性质和可实现性之间做精明的取舍。
决策树实战：三个案例走查¶
把决策树用在三个真实场景上走一遍，演示它怎么落地（这也是练习 1 的解题示范）。
案例一：L4 城市自动驾驶的无保护左转（人车混行）。 走决策树：Q1——交互有先后吗？AV 可以主动探头公示左转意图、人类司机再反应，偏 Stackelberg（但人类未必严格理性响应）。 Q2——安全约束必须严格吗？必须，绝不能撞。 综合：主求解器用 Stackelberg 式规划（Sadigh 2016，配 IRL 学人类奖励）处理"引导人类让行"，但因为人类有界理性 + 安全是硬约束，叠加 CBF 安全层（G4）兜底碰撞约束，并对人类响应做鲁棒化（响应预测不确定时退保守）。 一句话方案：Stackelberg 引导 + IRL 学人类模型 + CBF 硬安全兜底。
案例二：一对一无人机竞速（要赢、要封堵）。 走决策树：Q1——对等（双方同时决策、无明确先后），Nash。 Q2——安全约束（不相撞）需要满足，但竞速中"贴身"是常态，属于"尽量 + 关键处硬约束"。 Q3——核心能力是什么？主动封堵对手。 综合：主求解器用 SE-IBR（§2.6，灵敏度项制造封堵），它在 Nash 框架内实现近似 Stackelberg 的卡位；避撞用 SE-IBR 自带的 penalty + 必要时 CBF 兜底。 若发现求解器在贴身缠斗的初始条件下常不收敛，换用或叠加 DG-SQP（§2.7，收敛域更大）。 一句话方案：SE-IBR 封堵为主 + DG-SQP 保收敛（贴身缠斗时）+ CBF 防撞。
案例三：高速 ramp merging，三车（必须严格不撞 + 要抗扰）。 走决策树：Q1——对等（三车同时决策），Nash。 Q2——安全约束必须严格满足（高速碰撞致命），进入硬约束分支。 此时要同时满足"严格约束 + 抗扰"——单套方法都不全占（§2.5）。 综合：两条路线择一。路线 A：ALGAMES（严格约束的开环 GNE）+ 高频 MPC（60+ Hz，补开环的抗扰短板，每拍用实际状态重解）——这正是 ALGAMES 论文缓解 frozen robot 的标准姿势。路线 B：iLQGames（反馈、抗扰、毫秒级）+ CBF 安全层（兜底硬约束）——用 iLQGames 的反馈拿抗扰、CBF 拿硬安全。 两条路线的取舍：路线 A 约束处理更原生（AL 直接处理 merge 的几何约束），路线 B 抗扰更原生（反馈律自带）且更快。ramp merging 约束几何复杂，路线 A（ALGAMES + MPC）通常更稳妥。 一句话方案：ALGAMES 严格约束 + 60 Hz MPC 补抗扰（或 iLQGames + CBF 作为更快的备选）。
这三个案例覆盖了决策树的主要分支（Stackelberg / Nash+封堵 / Nash+硬约束），也演示了"主求解器 + 辅助层"组合的实际拼法——真实工程几乎总是组合，而非单一方法。
⚠️ 常见陷阱¶
陷阱 1（思维陷阱）：选型时追逐"最先进"而非"最匹配" - 错误描述：看到 GFNE/DG-SQP 是最新的（2023/2024），就默认它们比 iLQGames（2020）更该用。 - 现象/后果：在只需极致实时 + 反馈的场景上了 GFNE，达不到毫秒级；或在简单对等协调场景上了 DG-SQP，付出收敛稳健化的复杂度却用不上。 - 根本原因：方法的"新"不等于"适合你的场景"。每套方法是为特定需求设计的——GFNE 为"反馈+约束"、DG-SQP 为"收敛可靠性"，不是全面替代。 - 正确做法：从场景需求出发走决策树，而非从"哪个最新"出发。识别你的核心约束（实时性？约束严格性？收敛可靠性？），选最匹配的主求解器。 - 自检方法：问自己"这个场景里，哪个维度是绝对不能妥协的？"——答案决定主求解器，而非论文发表年份。
陷阱 2（概念误区）：以为选了一套求解器就解决了所有问题 - 错误描述：选定 iLQGames（或任一单套方法）后，期望它同时满足实时、反馈、硬安全、收敛可靠所有需求。 - 现象/后果：iLQGames 在安全关键场景下因 penalty 软约束发生碰撞；或 ALGAMES 开环解上车后因不抗扰偏离——单套方法的短板在部署后暴露成事故。 - 根本原因：没有单套方法五个维度全占（本节本质洞察）。每套都有短板：iLQGames 弱约束、ALGAMES 开环、GFNE 慢、DG-SQP 也需 MPC。 - 正确做法：用组合策略补短板——iLQGames + CBF 兜底硬安全、ALGAMES + MPC 补反馈。把主求解器的短板用辅助层显式补齐，而非指望单套全能。 - 自检方法：选定主求解器后，对照全景表逐列检查它的短板列（如 iLQGames 的"约束处理：弱"），问"这个短板在我的场景会出事吗？会就加辅助层"。
练习¶
- （综合选型） 对下面四个真实场景，走一遍选型决策树，给出主求解器 + 必要的辅助层，并说明每步决策依据：(a) L4 城市自动驾驶的无保护左转（人车混行、必须严格不撞）；(b) 一对一无人机竞速（对等、要封堵、要赢）；(c) 仓库 20 台 AGV 的开阔区域协调（对等、约束不紧、要实时）；(d) 高速 ramp merging（对等、必须严格不撞、要抗扰）。
- （组合策略设计） 详细设计"iLQGames + CBF 安全层"的组合（连接 G1 §1.4、G4）：(a) iLQGames 输出什么、CBF 层接收什么；(b) CBF 如何把不安全控制投影到安全集（最小限制 QP）；(c) 两层的频率如何配合；(d) 这个组合相比"单用 ALGAMES + MPC"各有什么优劣？
- （批判性思考·连接全章主线） 本章从 G1 的"HJI 理论最优但算不动"出发，发展出五套"局部近似但实时"的求解器。请论证这条主线背后的根本权衡：(a) 为什么"全局最优 + 严格保证 + 实时"三者不可兼得（联系 G1 §1.7 维度诅咒）；(b) 五套方法各自在这个"不可能三角"里牺牲了什么、换来了什么；(c) 组合策略（求解器 + 安全层）是否真的绕过了这个权衡，还是只是把它转移到了别处？
本章常见误解汇总¶
把全章八节的陷阱与易错点收口成一张表，按"误解 → 正解"对照，便于回头自查。
| 误解 | 正解 | 出处 |
|---|---|---|
| Stackelberg 解就是"更好的 Nash 解" | Stackelberg 解一般不在 Nash 集合内，是不同的解概念（对手响应内生 vs 外生） | §2.1 |
| 先手优势总成立，无需验证 follower 响应预测 | 先手优势完全依赖准确预测 follower 响应，预测错则引导变误导 | §2.1 |
| 开环 Nash 与反馈 Nash 在 LQ 情形相同 | 一般不同——对"对手是否对未来状态反应"的预期不同 | §2.2 |
| 开环 GNE 解可直接上车 | 开环不抗扰，必须配高频 MPC 用频率换反馈效果 | §2.2、§2.5 |
| iLQGames 与 iLQR 是不同算法 | iLQGames = iLQR 换内核（单人 Riccati → 多人耦合 Riccati），其余四步一致 | §2.3 |
| 把耦合 Riccati 写成 N 个独立 LQR | 必须组装含非对角块的耦合系统，否则不是 Nash（纳什自检会失败） | §2.3 |
| 加大碰撞 penalty 权重就能保证不碰撞 | penalty 软约束永远逼近不保证（0.978<1.0），权重过大还数值病态 | §2.3、§2.5 |
| iLQGames 收敛到的就是"那个"正确均衡 | 局部方法，收敛到初始化附近的 Nash；多 Nash 时靠初始化选 | §2.3 |
| 读懂 LQSolver 就读懂了 iLQGames | LQSolver 只是反向 pass；还需 ILQSolver 外层循环（尤其 line search） | §2.4 |
| C++ 直译 NumPy 即可，无需管内存 | 每步 malloc 动态矩阵会垮掉实时性；需固定大小 + 预分配 | §2.4 |
| ALGAMES 的开环 GNE 不需 MPC | 约束严格性只在名义轨迹成立，实际状态偏离需 MPC 重解 | §2.5 |
| 所有场景都该用"更高级"的 ALGAMES | 硬约束有代价（慢、需 MPC）；不需严格约束时 iLQGames 更优 | §2.5 |
| 标准 IBR 收敛的 Nash 会自动封堵 | 标准 IBR 把对手当固定、不封堵；需 SE-IBR 的灵敏度项 | §2.6 |
| 灵敏度权重 α 越大越好 | α 过大过度激进、忽视进展与避撞、易不收敛 | §2.6 |
| GFNE 可替代 iLQGames 实时上车 | GFNE 计算重（约束 LQ 博弈 + 近似），是理论里程碑非实时方案 | §2.7 |
| 用速度评判 DG-SQP 得出它不行 | DG-SQP 的价值是成功率（比 PATH 高 32%），不是单次速度 | §2.7 |
| 选最先进的方法就对了 | 选最匹配场景的，而非最新的；识别不可妥协的维度 | §2.8 |
| 一套求解器解决所有问题 | 没有方法五维全占；用组合策略（求解器 + 安全层）补短板 | §2.8 |
本章小结¶
本章回答了开篇的问题——如何把博弈求解实时化，让博弈规划跑在车上。
主线是 G1 的耦合 Riccati 如何变成工程：
§2.1–§2.2 先定清"要求什么样的解"——Nash（对等）vs Stackelberg（层级）、反馈（抗扰）vs 开环（需 MPC）两个正交维度；
§2.3 的 iLQGames 是全章心脏——它 = iLQR 换内核，每步把非线性博弈局部化成 G1 的 LQ 博弈、解耦合 Riccati、前向 rollout，达到毫秒级实时，但 penalty 软约束只能逼近安全（实测 0.978<1.0）；
§2.4 逐行精读了它的 C++ 实现 lq_solver.cc；
§2.5 的 ALGAMES 用增广拉格朗日严格处理硬约束，把那个 0.978 变成恰好 1.0，但输出开环 GNE、需高频 MPC；
§2.6 的 SE-IBR 用灵敏度项在 Nash 框架内挤出封堵能力；
§2.7 的 GFNE（反馈 + 约束）和 DG-SQP（工业级 SQP、成功率高 32%）代表理论统一与工程稳健的最新进展；
§2.8 把五套方法串成选型决策树，并给出"求解器 + 安全层"的组合策略。
贯穿全章的权衡：全局最优、严格保证、实时三者不可兼得（G1 §1.7 维度诅咒的延续）。 五套方法各在这个"不可能三角"里做取舍，工程落地靠组合策略补短板——这与 G1 从"理论最优"到"可算近似"的退让一脉相承。
还有一个本章自始至终的隐含前提，值得在收尾时点破：所有这些求解器都假设对手的代价函数已知——iLQGames 要写出对手的 \(\ell_j\)、ALGAMES 要知道对手的约束、SE-IBR 要对对手的优化问题求灵敏度。 可现实里，对手（人类司机、竞争对手）的真实意图和偏好往往是**未知的**，需要从观测到的行为中反推。 这正是 G1 §1.1 那第三次认知跨越——"从代价已知到代价需推断"——尚未兑现的部分，也是下一章 G3 逆博弈的主题。 本章打磨的求解器（尤其 iLQGames 的反馈策略、SE-IBR 的 KKT 灵敏度）会成为 G3 的"前向模型"：逆博弈在外层推断对手代价、在内层调用本章的求解器算均衡，两者嵌套。 所以本章不是终点，而是 G3 的引擎室。
术语速查表¶
| 术语 | 一句话定义 |
|---|---|
| Nash 均衡 | 同时决策，每人在他人策略固定时不能单方面改善（不动点） |
| Stackelberg 均衡 | leader 先公示、follower 响应；leader 解双层优化利用先手优势 |
| 开环 Nash (OLNE) | 策略是时间的函数，只依赖初始状态；不抗扰 |
| 反馈 Nash (FBNE) | 策略是当前状态的函数；子博弈完美、天然抗扰 |
| iLQGames | iLQR 的博弈推广，反复解局部 LQ 博弈（耦合 Riccati），输出反馈 Nash |
| 耦合 Riccati | N 人 LQ 博弈的反馈 Nash 条件，交叉项使 N 条方程相互耦合（G1 §1.6） |
| ALGAMES | 用增广拉格朗日 + 拟牛顿求 GNEP 的 KKT 根，严格处理硬约束，输出开环 GNE |
| GNEP | 广义 Nash 均衡问题——约束被所有玩家共享，可行域相互依赖 |
| KKT 条件 | 一阶最优性 + 原始/对偶可行 + 互补松弛，约束优化的最优性刻画 |
| 增广拉格朗日 (AL) | penalty + 乘子项；乘子收敛到影子价格，精确定位约束边界 |
| SE-IBR | 灵敏度增强 IBR，加 ∂u*₋ᵢ/∂uᵢ 项偏向封堵对手 |
| 灵敏度项 | 对手最优响应对 ego 策略的导数，由 KKT 隐函数定理算 |
| GFNE | 广义反馈 Nash 均衡 = 反馈 Nash + 严格约束，每步解约束 LQ 博弈 |
| DG-SQP | 用 SQP 求开环 GNE，每步解一个 QP，非单调线搜索 + merit 函数 + 衰减正则化 |
| frozen robot | 把对手当固定障碍导致的僵死/过保守行为（G1 §1.1） |
| 反馈增益 K / 前馈 k | K 管在线纠偏（抗扰）、k 管离线改进名义轨迹（收敛后归零） |
知识点总表¶
| 节 | 知识点 | 难度 | 一句话 |
|---|---|---|---|
| §2.1 | Nash vs Stackelberg | ⭐⭐ | 对等用 Nash、层级用 Stackelberg；先手优势靠预测对手响应 |
| §2.2 | 开环 vs 反馈 Nash | ⭐⭐⭐ | 反馈抗扰、开环需 MPC；二者一般不等 |
| §2.3 | iLQGames | ⭐⭐⭐ ★ | iLQR 换内核，反复解耦合 Riccati，毫秒级实时；软约束只能逼近 |
| §2.4 | ilqgames C++ 精读 | ⭐⭐⭐ | lq_solver.cc 是耦合 Riccati 工程实现；K 纠偏、k 改进 |
| §2.5 | ALGAMES | ⭐⭐⭐ | AL + KKT 根搜索，严格约束（0.978→1.0），开环需 MPC |
| §2.6 | SE-IBR | ⭐⭐⭐ | 灵敏度项偏向封堵；KKT 隐函数算 ∂u*₋ᵢ/∂uᵢ |
| §2.7 | GFNE / DG-SQP | ⭐⭐⭐⭐ | GFNE 统一反馈+约束；DG-SQP 工业级 SQP，成功率高 32% |
| §2.8 | 综合选型 | ⭐⭐ | 决策树选主求解器，组合策略（求解器+安全层）补短板 |
累积项目：本章新增模块¶
| 项目 | 本章新增模块 | 内容 | 后续如何复用 |
|---|---|---|---|
| 甲（自动驾驶交互博弈规划器） | 完整 iLQGames 求解器 | 以 G1 的耦合 Riccati 求解器为内核，扩成完整 iLQGames（线性化 + 二次化 + 反向 Riccati + line search rollout），2 车交叉路口验证避让与纳什 | G3 在其上加逆博弈层（从观测推断对手代价）；G4 串 CBF 安全层兜底硬约束 |
本章项目甲的核心模块（§2.3 练习 1）直接把 G1 §1.6 的"求一次 LQ 博弈"升级为"迭代求解非线性博弈"——这是从"理论内核"到"可用求解器"的关键一跃。 配套的 ALGAMES 对比实现（§2.5 练习 1）和 SE-IBR 灵敏度项（§2.6 练习 1）作为可选扩展，帮助理解不同求解路线。
延伸阅读¶
按主题与难度标注，括号内为定位。
均衡概念与人车交互（核心入门） - Sadigh, Sastry, Seshia, Dragan, "Planning for Autonomous Cars that Leverage Effects on Human Actions," RSS 2016（⭐⭐⭐ Stackelberg + IRL 影响人类，范式转变，DOI 10.15607/RSS.2016.XII.029） - Başar & Olsder, Dynamic Noncooperative Game Theory, SIAM 1999（⭐⭐⭐⭐ 均衡概念、信息结构的理论圣经，Ch3、Ch6）
iLQGames（本章重心，必读）
- Fridovich-Keil, Ratner, Peters, Dragan, Tomlin, "Efficient Iterative Linear-Quadratic Approximations for Nonlinear Multi-Player General-Sum Differential Games," ICRA 2020（⭐⭐⭐ 主论文，pp.1475–1481, arXiv:1909.04694）
- Fridovich-Keil, Rubies-Royo, Tomlin, "An Iterative Quadratic Method for General-Sum Differential Games with Feedback Linearizable Dynamics," ICRA 2020（⭐⭐⭐ 反馈线性化版，pp.2216–2222, arXiv:1910.00681）
- HJReachability/ilqgames 代码（⭐⭐⭐ C++ 参考实现，188★，BSD-3；精读 src/solver/lq_solver.cc）
- JuliaGameTheoreticPlanning/iLQGames.jl（原 lassepe/iLQGames.jl，⭐⭐ Julia 版，用自动微分做 LQ 近似，几行即可定义并求解一个 2-player unicycle 博弈，教学入门首选）
ALGAMES 与硬约束（进阶）
- Le Cleac'h, Schwager, Manchester, "ALGAMES: A Fast Solver for Constrained Dynamic Games," RSS 2020 / Autonomous Robots 46:201–215, 2022（⭐⭐⭐⭐ AL + 拟牛顿，硬约束，arXiv:1910.09713 / 2104.08452）
- RoboticExplorationLab/Algames.jl（⭐⭐⭐ Julia 实现，119★；含 AlgamesDriving.jl 自驾场景）
SE-IBR 与竞速（进阶） - Spica, Falanga, Cristofalo, Montijano, Scaramuzza, Schwager, "A Real-Time Game Theoretic Planner for Autonomous Two-Player Drone Racing," RSS 2018（⭐⭐⭐ 灵敏度增强 IBR，DOI 10.15607/RSS.2018.XIV.040, arXiv:1801.02302） - Wang, Wang, Talbot, Gerdes, Schwager, "Game-Theoretic Planning for Self-Driving Cars in Multivehicle Competitive Scenarios," T-RO 2021（⭐⭐⭐⭐ Audi TTS 实车，DOI 10.1109/TRO.2020.3047521）
理论统一与工业级求解（研究级）
- Laine, Fridovich-Keil, Chiu, Tomlin, "The Computation of Approximate Generalized Feedback Nash Equilibria," SIAM J. Optim. 33(1):294–318, 2023（⭐⭐⭐⭐ GFNE，反馈+约束统一，DOI 10.1137/21M142530X, arXiv:2101.02900）
- Zhu, Borrelli, "A Sequential Quadratic Programming Approach to ... Open-Loop Generalized Nash Equilibria for Autonomous Racing," arXiv:2404.00186, 2024（⭐⭐⭐⭐ DG-SQP，工业级 SQP，zhu-edward/DGSQP）
2024–2026 前沿（选读） - Peters et al., Contingency Games, 2024（⭐⭐⭐⭐ 博弈 + 分支，处理对手意图不确定） - Mehr, Schwager et al., MaxEnt Multi-Agent Dynamic Games, T-RO 2023（⭐⭐⭐⭐ softmax Bellman，有界理性，正逆统一）
本章与后续章节的关系¶
| 关系 | 章节 | 衔接点 |
|---|---|---|
| 直接前置（被本章用） | G1 微分博弈理论 | §1.6 耦合 Riccati = iLQGames 每步子问题；反馈 Nash（§1.2）是 iLQGames 输出形式 |
| 直接后续 | G3 逆博弈与预测规划 | SE-IBR 的灵敏度（§2.6 KKT 隐函数）= 逆博弈"对均衡求导"的前身；iLQGames 反馈策略是逆博弈的前向模型 |
| 直接后续 | G4 安全证书与 MARL | §2.8 的"iLQGames + CBF 安全层"组合；硬约束博弈的安全保证 |
| 跨专题对照 | U2 鲁棒规划 / MPC | §2.2 的"开环 + 高频 MPC = 准反馈"；博弈 MPC = 多人 MPC |
| 跨专题对照 | U1 分支场景规划 | §2.7 Contingency Games = 博弈 + 分支融合 |
| 工具复用 | Part 0 / iLQR | iLQGames = iLQR 换内核；DG-SQP = SQP 在博弈的推广 |
| 工具复用 | v8 Eigen | §2.4 ilqgames C++ 大量用 Eigen 块操作、固定大小矩阵 |
🔧 故障排查手册¶
把本章实践中最常撞的坑整理成"症状 → 可能原因 → 排查步骤 → 相关节"。
| 症状 | 可能原因 | 排查步骤 | 节 |
|---|---|---|---|
| iLQGames 迭代代价不降反升 / 出现 NaN | 前向 rollout 没做 line search，整步更新跨出近似有效域 | 1. 加 line search 试递减 α∈{1,0.5,...} 2. 检查碰撞 penalty 权重是否过大致病态 | §2.3 |
| 两车互不避让 / 避让不对称 | 耦合 Riccati 漏了非对角块（退化成独立 LQR）；或碰撞 penalty 没对称进双方代价 | 1. 检查块线性系统是否含 BᵢᵀZᵢBⱼ(i≠j) 2. 检查 penalty 梯度是否加到所有玩家 3. 跑纳什自检 | §2.3 |
| 加大碰撞权重仍侵入安全区 | penalty 软约束的本质局限，无法严格满足 | 1. 接受软约束逼近的事实 2. 改用 ALGAMES 硬约束或串 CBF 安全层 | §2.3、§2.5、§2.8 |
| C++ 移植后 Riccati 发散，NumPy 版正常 | Eigen 别名（A=f(A) 自引用）；或固定大小矩阵未初始化 | 1. 自引用赋值加 .eval() 2. 用 EIGEN_INITIALIZE_MATRICES_BY_NAN 查未初始化 | §2.4 |
| C++ 实现达不到实时（>控制周期） | 每步 malloc 动态矩阵 | 1. profiler 看 malloc 占比 2. 改固定大小矩阵 + 容器预分配 3. 跨周期复用缓冲 | §2.4 |
| ALGAMES 仿真完美、上车违反约束 | 开环解不抗扰，实际状态偏离名义轨迹 | 1. 配高频 MPC 每拍用实际状态重解 2. 确认单次求解 < 控制周期 | §2.2、§2.5 |
| SE-IBR 策略剧烈震荡 | 灵敏度项的 KKT 雅可比奇异/病态直接求逆；或 α 过大 | 1. 用 solve 不求逆 + 正则化 2. 监控雅可比条件数 3. 减小 α | §2.6 |
| 博弈求解从某些初始条件不收敛 | 局部方法对初始化敏感 | 1. 多初始化暖启动 2. 考虑 DG-SQP（收敛域更大，成功率高 32%） | §2.3、§2.7 |
API 速查表¶
本章涉及的核心求解器接口与关键函数签名（按参考实现，具体以各仓库当前版本为准）。
iLQGames 核心（§2.3 NumPy / §2.4 C++）
| 接口 | 签名 / 说明 |
|---|---|
lq_game_solve(As, Bs_list, Qs_t, qs_t, Rs_t, rs_t) |
离散耦合 Riccati 反向递推，返回 K[i][k], kff[i][k]（§2.3） |
jac_i(xi, ui) |
单车线性化，返回 A_i=I+dt·∂f/∂x, B_i=dt·∂f/∂u（§2.3） |
costs_and_derivs(x, us) |
二次化代价，返回 Qs, qs, Rs, rs（碰撞项对双方对称计入） |
ILQSolver (C++) |
iLQGames 外层循环：线性化→二次化→LQSolver→rollout→收敛 |
LQSolver (C++) |
耦合 Riccati 反向递推（src/solver/lq_solver.cc，~200 行 Eigen） |
ConcatenatedDynamicalSystem |
多人状态拼接成单一向量 |
Strategy |
反馈策略容器：Ks（增益 K）+ ks（前馈 k） |
OperatingPoint |
名义轨迹 |
ALGAMES（§2.5）
| 接口 | 签名 / 说明 |
|---|---|
constraints_vec(z) |
返回所有约束 c_k = d_safe − dist_k（≤0 即满足） |
| 增广拉格朗日外层 | 迭代更新乘子 λ = max(0, λ+ρc)、惩罚 ρ *= γ |
| 拟牛顿根搜索 | 求堆叠 KKT 方程组 G(z)=0 的根 |
Algames.jl |
Julia 实现入口（RoboticExplorationLab） |
SE-IBR（§2.6）
| 接口 | 签名 / 说明 |
|---|---|
sensitivity_dopp_dego(u_opp_star, u_ego, params) |
KKT 隐函数定理算 ∂u*₋ᵢ/∂uᵢ = −(∂G/∂u₋ᵢ)⁻¹(∂G/∂uᵢ) |
seibr_ego_cost(u_ego, u_opp_star, params, α) |
SE-IBR 代价 (2.5)：常规代价 + α·灵敏度项 |
best_response(...) |
标准 IBR 的最优响应（α=0 时） |
DG-SQP（§2.7）
| 接口 | 签名 / 说明 |
|---|---|
zhu-edward/DGSQP |
Python/CasADi 实现；每步解一个凸 QP |
| 关键组件 | 非单调线搜索 + merit 函数 + 衰减正则化 |
研究实践建议¶
给新手（从能跑的最小例子建立直觉）。
最快上手路径：先用 iLQGames.jl（Julia，~70 行核心，10 行跑起 2-player）跑通一个 2 车交叉路口，可视化反馈 Nash 轨迹，改碰撞权重看均衡从"让行"到"抢行"的变化；
再回头读 §2.3 的 NumPy 实现，对照理解线性化→二次化→耦合 Riccati→rollout 的数据流；
最后编译 ilqgames C++ 跑 three_player_intersection，精读 lq_solver.cc 把概念落到工程。
"先跑通最小例子、再读代码、再啃理论"这个顺序，比一上来读 ICRA 论文高效得多。
论文从 iLQGames（Fridovich-Keil 2020）入手——它是本章方法里最直观、代码最友好的。
给有经验者（往前沿与工程落地走）。 本章方法的共同软肋是**局部性**和**均衡选择**，前沿在三处： 其一，全局性——所有方法都是局部的，如何获得好的全局初始化（DG-SQP 改善了收敛域但未根治）是活跃方向； 其二，反馈 + 严格约束 + 实时三全——GFNE 在理论上统一了反馈和约束，但实时实现仍难，是值得攻坚的工程硬骨头； 其三，有界理性与意图不确定——真实对手不完美最优（MaxEnt Games）、意图不确定（Contingency Games），把这些融进实时求解器是 2024+ 的热点。 工程落地上，"iLQGames + CBF 安全层"是目前最实用的组合（实时反馈 + 硬安全兜底），值得吃透其两层接口与频率配合（连接 G1、G4）。
版本信息速查¶
本章涉及的开源实现与论文版本（截至本资料编写，仅供参考，请以各仓库/出版方最新为准）：
| 项目 / 论文 | 版本信息 | 出处 |
|---|---|---|
| ilqgames（C++） | ~188★，BSD-3-Clause，C++ 为主 | github.com/HJReachability/ilqgames |
| iLQGames.jl | ~41★，Julia（用自动微分） | github.com/JuliaGameTheoreticPlanning/iLQGames.jl（原 lassepe/） |
| Algames.jl | ~119★，MIT，Julia | github.com/RoboticExplorationLab/Algames.jl |
| DGSQP | Python / CasADi / OSQP | github.com/zhu-edward/DGSQP |
| iLQGames 论文 | ICRA 2020, pp.1475–1481 | arXiv:1909.04694 |
| ALGAMES 论文 | RSS 2020 / AuRo 46:201–215 (2022) | arXiv:1910.09713 / 2104.08452 |
| SE-IBR 论文 | RSS 2018 | arXiv:1801.02302 |
| GFNE 论文 | SIAM J. Optim. 33(1):294–318 (2023) | arXiv:2101.02900 |
| DG-SQP 论文 | 2024（赛车版） | arXiv:2404.00186 |
| Eigen | 3.x（ilqgames 依赖） | eigen.tuxfamily.org |
G2 完结。 从 G1 的耦合 Riccati 出发，我们走过了 iLQGames（反馈、毫秒级）、ALGAMES（硬约束、0.978→1.0）、SE-IBR（封堵）、GFNE（理论统一）、DG-SQP（工业级稳健），最后用选型决策树和组合策略把它们落地。博弈规划至此从"理论最优但算不动"（G1）真正变成了"实时跑在车上"。下一章 G3 将带着这些求解器进入**逆博弈**——不再假设对手代价已知，而是从观测中把它推断出来，完成 G1 §1.1 那第三次认知跨越。