POMDP 与信念空间规划:当你看不清世界时如何决策¶
不确定性规划方向(Part-U)第 4 章。上承 U0 总论的"五安全谱",本章处理**感知端的认知不确定性**——"我看不清世界"。这与 U2(鲁棒,动力学端有界扰动)、U3(机会约束,动力学端概率扰动)、U1(分支,交互端离散意图)正交:那几章假设状态可观测、只是演化不确定;本章连**状态本身**都看不清,只能通过带噪观测推断。对 SLAM 工程师而言这是最自然的延伸——SLAM 的状态估计就是 belief update 的工程实现,POMDP 只是在它之上加"如何用 belief 做决策"。
前置自测¶
开始前先自测。以下问题答不出 2 道及以上,建议先回到对应前置章节。
- 写出马尔可夫决策过程(MDP)的五元组 \(\langle S,A,T,R,\gamma\rangle\),并说明值函数 \(V^*(s)\) 满足的 Bellman 最优方程。(→ 若答不出,回 U0 §3 或 MDP/DP 基础)
- EKF / 粒子滤波在做什么?给定上一时刻的状态分布、一个控制、一个观测,它如何更新状态分布?(→ 回 SLAM 状态估计 / 贝叶斯滤波)
- 什么是充分统计量(sufficient statistic)?为什么有了它就可以"扔掉"原始数据?
- U1 的分支规划用"共享干 + 分支"处理离散意图不确定性。它对"他车意图"维护了什么?为什么说它是 POMDP 的一种近似?(→ 回 U1 §U1.3/§U1.4)
- MCTS(蒙特卡洛树搜索)的四步是什么(选择 / 扩展 / 模拟 / 反向传播)?UCB 如何平衡探索与利用?(→ 回 U1 §U1.7)
这 5 题对应本章五块前置:MDP/Bellman(§U4.2 值函数的地基)、贝叶斯滤波(§U4.1 belief update 就是它)、充分统计量(§U4.1 belief 的核心性质)、U1 分支规划(§U4.4 belief 树与 contingency 树同源)、MCTS(§U4.4 DESPOT/POMCP 是 belief 空间的 MCTS)。
本章目标¶
学完本章,你应该能够:
- 写出 POMDP 的七元组形式化,推导 belief update(贝叶斯滤波),并说清 **belief 是充分统计量**的意义——为什么它把整段历史压缩成当前的一个分布。
- 解释 POMDP 如何转化为 belief 空间上的 MDP,以及为什么这个转化既是出路(可用 MDP 工具)又是难点(状态空间变成连续高维单纯形)。
- 理解 α-vector 与 PWLC 值函数(Sondik 定理)——POMDP 精确求解的数学基础,以及为什么精确解随视界指数爆炸。
- 说清从精确到近似的路线:QMDP(最廉价近似)→ 点基方法(SARSOP,离线、在可达 belief 上备份)→ 在线树搜索(POMCP/DESPOT)。
- 掌握 DESPOT 的确定化稀疏 belief 树:K 个确定化场景如何把随机 belief 树固化为稀疏树、output-sensitive 性能界、R-DESPOT 正则化。
- 梳理 DESPOT 家族演化:DESPOT → HyP-DESPOT(GPU)→ Context-POMDP(自驾)→ DESPOT-α / MAGIC / LeTS-Drive(学习辅助)。
- 理解 belief-space motion planning(LQG-MP / ML 观测假设 / RRBT / FIRM / BSP-iSAM)是 POMDP 在"高斯 belief + 连续空间"下的特化,并说清 Active SLAM = POMDP 实例(信息增益 = 奖励)。
- 建立 DreamerV3 的 RSSM = 摊销 belief 的等价认识,看清"神经世界模型派"与"DESPOT 树搜索派"如何在 Neural-guided 树搜索(BetaZero)处合流;并能读懂 DESPOT 的 C++
DSPOMDP接口。
本章知识导航 ⭐¶
本章沿一条主线展开:状态看不清,就维护一个状态的概率分布(belief),把它当作充分统计量,在 belief 空间上做决策。
状态可观测(U0/U1/U2/U3 默认)
│ 现实:状态看不清(传感器噪声 / 遮挡 / 部分可观测)
▼
┌─────────────────────────────────────────────┐
│ POMDP:在信念空间(belief)上决策(本章主线) │
│ belief b(s) = 状态后验; b'=贝叶斯滤波更新 │
│ belief 是充分统计量 → POMDP = belief 空间 MDP │
└─────────────────────────────────────────────┘
│ │ │
值函数长什么样 怎么近似求解 连续 / 高维特化
§U4.2 α-vector §U4.3 点基(SARSOP) §U4.6 belief-space
PWLC(Sondik) §U4.4 DESPOT(在线) motion planning
§U4.5 DESPOT 家族 §U4.7 Active SLAM
│
▼
§U4.8 DreamerV3 = 摊销 belief(神经世界模型)
本章方法谱系(这条线怎么来的):POMDP 由 Sondik 在 1971 年的博士论文奠基(证明有限视界最优值函数在 belief 空间分段线性且凸);1998 年 Kaelbling–Littman–Cassandra 用机器人感知语言把它标准化为七元组;2003–2008 年点基方法(PBVI→HSVI→SARSOP)只在"可达 belief"上备份,从"不可算"走到"离线可算中等规模";2010–2013 年在线树搜索(POMCP→DESPOT)把 MCTS 搬进 belief 树、用粒子隐式表示 belief,做到大规模实时;2018 年 HyP-DESPOT 用 GPU 并行再快百倍;2021 年起学习辅助(MAGIC 学宏动作、LeTS-Drive 学引导);2023 年起神经世界模型(DreamerV3 的 RSSM)作为"摊销 belief"与树搜索(BetaZero)合流。各方法的精确出处在文末"延伸阅读"给出并已逐一核实。
关键实验室:MIT CSAIL(Kaelbling/Lozano-Pérez,POMDP 标准化 + 抓取 POMDP)、NUS AdaComp(Hsu/Lee,DESPOT 全家族、事实标准)、Stanford SISL(Kochenderfer,POMDPs.jl 生态、POMCPOW、BetaZero)、CMU(Pineau 的 PBVI、Smith/Simmons 的 HSVI)、Technion/MIT(Indelman/Carlone,BSP-iSAM、Active SLAM 综述)。
阅读路径:想建立直觉 → §U4.1(belief + 充分统计量)+ §U4.2 的本质洞察;想动手 → §U4.1/§U4.3 的实现 + 完整实现精读(Tiger + QMDP + 在线规划器);想上工程 → §U4.4/§U4.5(DESPOT 全家族 + C++ 接口);想接 SLAM → §U4.6/§U4.7(belief-space planning + Active SLAM);想接学习 / 世界模型 → §U4.8(RSSM = 摊销 belief)。
前置知识桥接¶
本章建立在以下前置之上,这里用 2–3 行重新激活。
- MDP 与 Bellman(U0 §3 / DP 基础):MDP 是 \(\langle S,A,T,R,\gamma\rangle\),最优值函数满足 \(V^*(s)=\max_a[R(s,a)+\gamma\sum_{s'}T(s'|s,a)V^*(s')]\)。POMDP 是 MDP 的"看不清状态"版——本章会把它转成"状态是 belief"的 MDP,于是这套 Bellman 机器仍然适用,只是状态空间变了。
- 贝叶斯滤波 / EKF / 粒子滤波(SLAM 状态估计):给定先验 \(b(s)\)、控制 \(a\)、观测 \(o\),贝叶斯滤波先用运动模型预测、再用观测模型校正,得到后验 \(b'(s')\)。本章的 belief update 就是贝叶斯滤波——SLAM 工程师已经天天在做,只是没在 belief 之上做决策。
- U1 分支规划(§U1.3/§U1.4):回顾 U1——分支规划对"他车意图"维护一个离散分布、在共享干 + 分支树上决策;EUDM 还显式说它是"POMDP + 引导分支"。本章给出 POMDP 的完整处理,U1 的"引导分支"是它的一种领域剪枝近似(§U4.4 会接上)。
- MCTS(U1 §U1.7):回顾 U1——MCTS 用 UCB 自适应展开 + rollout + 反向传播。本章的 POMCP/DESPOT 就是把 MCTS 搬到 **belief 树**上(节点是 belief、用粒子表示,边是动作-观测)。
- CVaR(U0 §3,U3 进阶十,U5 详解):回顾——CVaR\(_\alpha\) 是最坏 \((1-\alpha)\) 尾部的平均损失。本章末尾会提到风险敏感 POMDP(把期望奖励换成 CVaR),是 U5 的方向。
如果跳过本章会怎样¶
- 场景一(在错误的状态上自信决策):你的机器人用 EKF 估计自己在走廊的位置,但走廊两端长得一样(感知混淆),EKF 的协方差其实很大、甚至是双峰的。如果你无视这个不确定性、把均值当真实状态做 MDP 决策,机器人会"自信地"走错方向。POMDP 强迫你在**整个 belief**(而非一个点估计)上决策——不确定大时它会倾向于先去"看清楚"(主动消歧),而非贸然行动。
- 场景二(不会主动获取信息):探索一个未知环境时,"下一步该去哪里看"才能最快把地图建准?这本质是"用动作降低 belief 的不确定性"——是一个以**信息增益为奖励**的 POMDP(Active SLAM)。不学 POMDP,你只会被动跟着给定路径走,不会让机器人主动规划"去哪测量最划算"。
预计阅读时间¶
- 精读(推导 + 代码 + 手算走查 + 自己实现 Tiger/QMDP/在线规划器):约 10–14 小时。
- 速读(抓主线 + 看本质洞察 + 跳过部分源码精读):约 4–5 小时。
- 速查(已学过,回来查 belief update / α-vector / DESPOT 接口 / 选型):用"实践索引"与"本章符号速查"直接定位,约 25 分钟。
§U4.1 POMDP 形式化与 belief ⭐⭐¶
动机:状态看不清,怎么办¶
前面三章(U2/U3/U1)都默认一件事:当前状态 \(x\) 是可观测的。鲁棒 MPC 知道自己在哪、只是不知道风会怎么吹;机会约束知道障碍在哪、只是位置带高斯噪声;分支规划知道自己的状态、只是不知道他车的离散意图。但有一类不确定性更根本——连你自己的状态都看不清:
- 机器人在长得一样的走廊里定位,传感器读数无法区分"在 A 段"还是"在 B 段"——位置本身是不确定的。
- 抓取时手指挡住了物体,你不知道物体的确切位姿。
- 经典的 Tiger 问题(Kaelbling–Littman–Cassandra 1998):你面前两扇门,一扇后面是老虎、一扇后面是奖励,但你不知道哪扇。你可以"听"来获取信息,但听不准(有概率听错),且听也有代价。该开哪扇门?要不要先多听几次?
这些问题的共同点:状态不可直接观测,只能通过带噪声的观测去推断。这正是 POMDP(Partially Observable Markov Decision Process,部分可观测马尔可夫决策过程)要处理的。
多视角理解:POMDP 相对 MDP 多了什么 - MDP 视角:MDP 假设你每一步都知道当前状态 \(s\),决策只依赖 \(s\)。POMDP 去掉这个假设——你不知道 \(s\),只拿到一个观测 \(o\)。像 / 不像:两者都是"在动态环境里序贯决策、最大化累积奖励",但 MDP 的决策依据是**状态**,POMDP 的决策依据是**对状态的信念**。 - 估计 + 决策视角:POMDP = 状态估计(从观测推断状态分布)+ 决策(在状态分布上选动作)。SLAM 做的是前半(估计),POMDP 把后半(在估计结果上决策)也纳进来。 - 信息视角:MDP 里"信息"是完备的(你看得见 \(s\));POMDP 里信息是**部分的、带噪的**,所以"获取信息"本身成了一种有价值的动作(Tiger 里的"听"、SLAM 里的"去某处测量")——这是 POMDP 独有的、MDP 里不存在的决策维度。
反面:把 POMDP 当 MDP 做会怎样¶
最朴素的偷懒:用滤波器(EKF / 粒子滤波)估一个状态点估计 \(\hat s\)(如均值或最大后验),然后假装 \(\hat s\) 就是真实状态、套 MDP 的最优策略。两个典型失败:
失败一:在多模态 / 高方差 belief 上自信决策。走廊两端长得一样时,belief 可能是**双峰**的("在 A 段"和"在 B 段"概率各半)。点估计(均值)会落在两峰中间——一个**根本不可能的位置**(走廊正中的墙里)。在这个虚假的"均值状态"上决策,结果荒谬。即便 belief 是单峰但方差很大,把均值当真值也会忽略"我其实很不确定"这一关键信息。
失败二:永远不会主动消歧。MDP 策略只会根据"当前以为的状态"选最优动作,它**没有"为了看得更清而行动"的概念**——因为 MDP 假设状态本就可观测、无需获取信息。于是 Tiger 问题里,当 MDP 策略不确定时,它要么瞎猜开门(高风险),要么陷入僵局,而不会"先多听几次再决定"。"听"在 MDP 框架里是一个看似无收益的动作(不改变物理状态、只改变信息),MDP 看不到它的价值。
本质洞察:POMDP 的关键是"在分布上决策",而非"在点估计上决策"。把 belief 塌缩成一个点(均值 / MAP)再做 MDP,丢掉的恰恰是"我有多不确定"这个信息——而这个信息正是 POMDP 决策的核心依据。不确定性大时,最优 POMDP 策略会倾向于**先降低不确定性**(获取信息)再行动;不确定性小时才直接追求奖励。这种"该探索还是该利用、由当前 belief 的形状决定"的行为,是 MDP 永远学不会的,因为 MDP 的世界里没有"不确定的状态"这回事。后面会看到,正是这一点让 POMDP 能自然导出主动感知 / Active SLAM。
理论:POMDP 七元组¶
POMDP 在 MDP 的五元组上加两项(观测空间和观测模型),成为七元组 \(\langle S, A, T, R, \Omega, O, \gamma\rangle\)(本章 \(\Omega\) 表示观测空间,不同于 U2 鲁棒规划章的 RPI 集 \(\Omega\)。):
| 元素 | 含义 | 与 MDP 的关系 |
|---|---|---|
| \(S\) | 状态空间(往往不可直接观测) | MDP 也有,但 MDP 里可观测 |
| \(A\) | 动作空间 | 同 MDP |
| \(T(s'\mid s,a)\) | 状态转移概率 | 同 MDP |
| \(R(s,a)\) | 奖励函数 | 同 MDP |
| \(\Omega\) | 观测空间(你能看到的东西) | MDP 没有 |
| \(O(o\mid s',a)\) | 观测模型:在 \(a\) 后到达 \(s'\) 时观测到 \(o\) 的概率 | MDP 没有 |
| \(\gamma\) | 折扣因子 \(\in[0,1)\) | 同 MDP |
与 MDP 唯一的结构差别就是 \(\Omega\) 和 \(O\):你不再直接看到 \(s'\),而是看到一个由 \(s'\) 概率性生成的观测 \(o\)。\(O(o\mid s',a)\) 编码了传感器的不完美——理想传感器 \(O\) 是确定性的(\(o\) 唯一确定 \(s'\)),现实传感器 \(O\) 是弥散的(同一个 \(s'\) 可能给出不同 \(o\),不同 \(s'\) 可能给出相同 \(o\),即感知混淆)。
理论:belief 与贝叶斯滤波更新¶
既然看不到状态,就维护一个**对状态的概率分布**——信念(belief) \(b\),其中 \(b(s)\) 是"当前处于状态 \(s\) 的概率",\(\sum_s b(s)=1\)(离散状态)。belief 就是状态的后验分布,浓缩了到目前为止所有观测和动作的信息。
每走一步(执行动作 \(a\)、收到观测 \(o\)),belief 按**贝叶斯滤波**更新:
其中 \(\eta=1/\Pr(o\mid b,a)\) 是归一化常数,保证 \(\sum_{s'}b'(s')=1\)。逐项解读:
- 运动预测 \(\sum_s T(s'\mid s,a)b(s)\):把旧 belief 通过转移模型推一步,得到"动作后、看观测前"的预测 belief \(\bar b(s')\)。这一步**增大不确定性**(运动有噪声,分布被抹平)。
- 观测校正 \(O(o\mid s',a)\cdot\):用刚收到的观测 \(o\) 给预测 belief 重新加权——与 \(o\) 更吻合的状态 \(s'\) 概率被抬高。这一步**减小不确定性**(观测带来信息,分布被锐化)。
- 归一化 \(\eta\):让结果重新成为概率分布。
多视角理解:belief update 的三种身份 - 贝叶斯视角:它就是贝叶斯定理 \(\text{后验} \propto \text{似然} \times \text{先验}\) 的序贯版——预测 belief 是先验,\(O(o\mid s',a)\) 是似然,\(b'\) 是后验。 - SLAM 视角:它**就是 EKF / UKF / 粒子滤波做的事**。EKF 的"预测步"= 运动预测、"更新步"= 观测校正;粒子滤波的"重要性重采样"= 用观测似然给粒子重新加权。如果你写过 EKF-SLAM,你已经实现过 belief update——区别只在 SLAM 到此为止(估完就用均值),POMDP 还要在 \(b'\) 之上做规划。 - 信息状态视角:belief 是把"原始历史 \((a_1,o_1,\dots,a_t,o_t)\)"压缩后的**信息状态**——它"记住"了历史里所有与决策相关的东西。
本质:belief 是充分统计量,POMDP = belief 空间的 MDP¶
这是 POMDP 理论的枢纽。belief 是历史的充分统计量(sufficient statistic):给定当前 belief \(b\),过去的整段动作-观测历史 \((a_1,o_1,\dots,a_t,o_t)\) 可以被**完全遗忘**——未来的最优决策只依赖 \(b\),不依赖你是经过怎样的历史才到达这个 \(b\) 的。
为什么?因为 \(b\) 已经把历史里所有"与未来相关"的信息都编码进去了(它是状态的完整后验分布)。两段不同的历史,只要导出相同的 belief,之后的最优策略就完全一样。
这个事实有一个深远推论:POMDP 可以转化为 belief 空间上的一个(完全可观测的)MDP——称为 belief-MDP:
- 状态 = belief \(b\)(完全可观测!你总是知道自己当前的 belief,因为它是你自己算出来的);
- 动作 = 原 POMDP 的动作 \(a\);
- 转移 = belief update(给定 \(b,a\),收到 \(o\) 后转到 \(b'=\tau(b,a,o)\),转移概率 \(=\Pr(o\mid b,a)\));
- 奖励 = belief 上的期望奖励 \(\rho(b,a)=\sum_s b(s)R(s,a)\)。
于是 POMDP 的求解原则上化归 MDP 的求解,Bellman 最优方程照搬:
本质洞察:POMDP→belief-MDP 是"用状态空间的复杂度换可观测性"。原 POMDP 的麻烦是"状态不可观测";转成 belief-MDP 后状态(belief)完全可观测了——天大的好消息。但代价是状态空间从原来的**离散有限**集合 \(S\)(\(|S|\) 个状态),变成了 belief 所在的**连续高维单纯形** \(\Delta^{|S|-1}\)(\(|S|\) 维概率向量、维度 \(|S|-1\))。你把"看不清"的难题,转化成了"在一个连续高维空间上做 MDP"的难题。POMDP 的全部求解技术(§U4.2–U4.5)都是在跟这个连续高维 belief 空间搏斗——精确解(α-vector)、点基近似(只管可达的那部分 belief)、在线树搜索(只管从当前 belief 出发能到的那部分)。记住这一句,后面所有方法都是它的注脚。
POMDP 与 HMM、卡尔曼滤波的关系¶
belief update 不是新东西——它统一了你可能已经熟悉的几个滤波 / 推断框架,看清这层关系能消除"又一个新模型"的负担。
- 隐马尔可夫模型(HMM):HMM 是"有隐状态 + 观测、但**没有动作**"的模型——它只做推断(前向算法估隐状态后验),不做决策。POMDP = HMM + 动作 + 奖励。HMM 的前向递归 \(\alpha_t(s)\propto O(o_t\mid s)\sum_{s'}T(s\mid s')\alpha_{t-1}(s')\) 和 POMDP 的 belief update 结构一模一样(少了动作条件)。所以会 HMM 前向算法,就会 belief update。
- 卡尔曼滤波:是 belief update 在"线性高斯"下的解析特例——belief 是高斯 \((\mu,\Sigma)\),预测步和更新步有闭式解(§U4.6 的 Riccati 递归)。粒子滤波则是 belief update 的非参数蒙特卡洛实现(用粒子近似任意分布)。
- 贝叶斯滤波:是上述所有的统一抽象——预测(用转移)+ 校正(用观测似然)+ 归一化。卡尔曼是它的高斯特例、粒子滤波是它的采样实现、HMM 前向是它的离散无动作版。
所以 POMDP 的"估计"那一半,是你在 SLAM / 信号处理里见过的滤波器的统一体;POMDP 真正新增的,只有"在这个 belief 之上做带动作 + 奖励的决策"。
多视角理解:belief update 是"一族滤波器的共同骨架",POMDP 给它加了决策。HMM 前向、卡尔曼、粒子滤波看似三个东西,其实是同一个贝叶斯滤波(预测 + 校正)在"离散无动作 / 线性高斯 / 非参数采样"下的三个面孔。POMDP 在这个共同骨架上加动作(转移依赖 \(a\))、加观测模型依赖 \(a\)、加奖励——于是从"被动推断隐状态"升级成"主动决策"。这就是为什么 SLAM / 滤波背景的人学 POMDP 增量小:估计内核你早就有了,只是没在它上面挂决策。
SLAM 工程师的直觉:你已经会一半了¶
如果你做过 SLAM,本章的"估计"那一半你已经精通:
| SLAM 概念 | POMDP 对应 | 说明 |
|---|---|---|
| 状态(位姿 + 地图) | POMDP 状态 \(s\) | SLAM 的状态往往连续高维 |
| 运动模型 | 转移 \(T(s'\mid s,a)\) | 同一套东西 |
| 传感器模型 | 观测模型 \(O(o\mid s',a)\) | 同一套东西 |
| EKF / 粒子滤波 | belief update | 一模一样的操作 |
| 估计出的位姿分布 | belief \(b\) | SLAM 算到这就停,POMDP 继续 |
| —(SLAM 没有) | 在 belief 上做 planning | 这是 POMDP 多出来的 |
所以对 SLAM 工程师,学 POMDP 的增量很小:你已经会维护 belief,只需再学"如何在 belief 上做决策"。§U4.7 会看到,Active SLAM 就是"在你的 SLAM 之上加一个 POMDP 规划器,决定下一步去哪里看"——你的 SLAM 技能直接成为 POMDP 的一个子模块(belief update 模块)。
⚠️ 本节常见陷阱¶
💡 概念误区:把 belief 当成一个点估计(均值 / MAP) - 新手想法:"belief 不就是滤波器估出来的那个状态嘛,取均值用就行。" - 现象 / 后果:在双峰 / 高方差 belief 上,均值落在不可能的位置(如两个模态中间);决策无视不确定性,该消歧时不消歧。 - 根本原因:belief 是**整个分布**,不是一个点。POMDP 决策依赖分布的形状(尤其不确定性大小),塌缩成点就丢了这个信息。 - 正确做法:在整个 belief 上决策(α-vector 内积、或在粒子集上仿真)。检验方法:构造一个双峰 belief,看你的决策是否会"先消歧再行动"——若它直接按均值冲,说明你塌缩了 belief。
💡 编程陷阱:belief update 忘了归一化,或归一化在校正前 - 现象 / 后果:belief 不再是概率分布(和不为 1),多步后数值漂移甚至全为 0(下溢)。 - 错误代码:
b_new[s2] = O[o][s2] * sum(T[s][s2]*b[s] for s in S)后直接用(没除以 \(\eta^{-1}=\sum_{s'}\cdot\));或在乘 \(O\) 之前就归一化。 - 正确写法:先算未归一化的 \(\tilde b(s')=O(o\mid s',a)\sum_s T(s'\mid s,a)b(s)\),全部算完后**再统一除以 \(\sum_{s'}\tilde b(s')\)。 - **根本原因:归一化常数 \(\eta=1/\sum_{s'}\tilde b(s')\) 依赖所有 \(s'\) 的未归一化值,必须等它们都算出来才能除。 - 检验方法:每步 update 后assert abs(sum(b)-1) < 1e-9;大状态空间用对数域防下溢。🧠 思维陷阱:以为"观测越多 belief 一定越确定" - 新手想法:"多观测几次,不确定性总会下降吧。" - 现象 / 后果:在感知混淆的环境(走廊两端一样)里反复观测,belief 始终双峰、不收敛——多观测没用,因为观测本身无法区分这两个状态。 - 根本原因:观测能降低不确定性的前提是它对不同状态**有区分力**(\(O(o\mid s_1)\ne O(o\mid s_2)\))。在感知混淆区,观测对两个状态似然相同,再多也不消歧——必须靠**动作**(移动到能区分的地方)才能消歧。 - 正确做法:当 belief 卡在多模态不收敛时,规划一个"去能区分的地方"的动作序列(主动消歧)——这正是 POMDP / Active SLAM 要解决的(§U4.7)。
练习¶
- [A 型·实现 belief update] 在 Tiger 问题上实现 belief update:状态 \(\{\)tiger-left, tiger-right\(\}\),动作 \(\{\)listen, open-left, open-right\(\}\),听的观测模型 \(O(\text{hear-left}\mid\text{tiger-left},\text{listen})=0.85\)。从均匀 belief \((0.5,0.5)\) 出发,连续"听"到 3 次 hear-left,打印每步 belief。验证 belief 向 tiger-left 收敛但不会到 1。
- [A 型·感知混淆] 构造一个 4 状态走廊,其中状态 1 和状态 3 的观测模型完全相同(感知混淆)。从在 1、3 上各半的 belief 出发,反复"原地观测",验证 belief 不收敛(保持双峰);再加一个"前进"动作让机器人离开混淆区,验证 belief 这时才收敛。
- [思考题] 为什么说 belief 是充分统计量?请论证:"两段不同历史若导出相同 belief,则之后的最优策略相同"。这个性质为什么是"POMDP 可转化为 belief-MDP"的前提?
§U4.2 α-vector 与 PWLC 值函数 ⭐⭐⭐¶
动机:belief 空间上的值函数长什么样¶
§U4.1 把 POMDP 化成了 belief 空间上的 MDP,Bellman 方程也照搬了。但 belief 空间是**连续高维**的(\(|S|\) 维单纯形),值函数 \(V^*(b)\) 是定义在这个连续空间上的函数——它长什么样?能不能用有限的东西表示?如果不能,POMDP 就根本无从求解(你没法存一个连续空间上的任意函数)。
Sondik 在 1971 年的博士论文回答了这个问题,给出了 POMDP 求解的数学基石。
理论:Sondik 定理与 PWLC¶
Sondik 1971 核心定理:有限视界 POMDP 的最优值函数 \(V^*(b)\) 在 belief 空间上是**分段线性且凸的(Piecewise-Linear and Convex, PWLC)**。它可以写成有限个线性函数取上包络:
其中 \(\Gamma = \{\alpha_1,\dots,\alpha_m\}\) 是有限个 α-vector 的集合,每个 \(\alpha\) 是一个 \(|S|\) 维向量(和状态空间同维)。
逐项理解:
- 每个 α-vector \(\alpha\) 是 belief 空间上的一个**线性函数** \(b\mapsto\alpha\cdot b\)(在单纯形上是一张超平面)。
- \(V^*(b)\) 取所有这些线性函数的**逐点最大**(上包络)——有限个线性函数取 max,结果就是分段线性且凸的。
- 在 belief 空间的每个区域,某一个 α-vector 占主导(它的 \(\alpha\cdot b\) 最大);区域之间的边界是相邻两张超平面相交处。
为什么是凸的(直觉):值函数凸意味着"belief 越不确定(越靠近单纯形中心),价值越低"——因为不确定时你更可能选错动作。在单纯形的顶点(belief 集中在某个确定状态),价值最高(你确切知道自己在哪);越往中间(越不确定),价值越低。有限个线性下界取上包络,自然形成这个凸形状。
含义:每个 α-vector 是一个"条件计划"¶
α-vector 不只是数学对象,它有清晰的语义:每个 α-vector 对应一个条件计划(conditional plan)——即"从某个动作开始、之后根据观测如何分支"的一整套策略。\(\alpha(s)\) 的值 = "如果真实状态是 \(s\),执行这个条件计划能拿到的期望累积奖励"。
于是最优策略变得极简:在当前 belief \(b\) 下,选使 \(\alpha\cdot b\) 最大的那个 α-vector,执行它对应的动作。换言之,α-vector 集合 \(\Gamma\) 同时编码了值函数(取上包络)和策略(取 argmax 的那个 α 对应的动作)。
多视角理解:α-vector 的三种看法 - 几何视角:每个 α 是 belief 单纯形上方的一张超平面;\(V^*\) 是这些超平面的上包络(一个凸的分段线性"穹顶")。belief 空间被划分成若干区域,每个区域由一张主导超平面"罩着"。 - 策略视角:每个 α 是一个条件计划(含起始动作 + 后续依观测的分支);\(\alpha(s)\) 是该计划在真实状态 \(s\) 下的价值。最优策略 = 在当前 belief 选价值上包络最高的那个计划。 - 回归视角:\(V^*(b)=\max_\alpha\alpha\cdot b\) 像是"用有限个线性专家、每个专家在自己擅长的 belief 区域给出价值,取最强专家"——belief 落在哪个区域,就由哪个条件计划当家。
一个 2 状态的 PWLC 走查¶
把 PWLC 落到 Tiger(2 状态)上看清楚。belief 是一个数 \(p=b(\text{TL})\in[0,1]\)(另一维 \(1-p\)),所以每个 α-vector 是 \([0,1]\) 上的一条**直线** \(\alpha\cdot b=\alpha(\text{TL})\,p+\alpha(\text{TR})(1-p)\)。设值函数有三个 α-vector(对应三个条件计划):
- \(\alpha_A=(10,-100)\):条件计划"开右门"(虎在左则 +10、虎在右则 −100),对应直线 \(10p-100(1-p)\);
- \(\alpha_B=(-100,10)\):条件计划"开左门",对应 \(-100p+10(1-p)\);
- \(\alpha_C=(8.5,8.5)\):条件计划"先听再说"(两状态价值都约 8.5,近水平线)。
\(V^*(p)=\max(\alpha_A\cdot b,\ \alpha_B\cdot b,\ \alpha_C\cdot b)\) 是这三条直线的**上包络**。逐点看谁主导:
| belief \(p=b(\text{TL})\) | \(\alpha_A\)(开右) | \(\alpha_B\)(开左) | \(\alpha_C\)(听) | 主导 → 最优动作 |
|---|---|---|---|---|
| 0.5(最不确定) | −45 | −45 | 8.5 | \(\alpha_C\) → 听 |
| 0.9 | −1 | −89 | 8.5 | \(\alpha_C\) → 听 |
| 0.99 | 8.9 | −98.9 | 8.5 | \(\alpha_A\) → 开右门 |
交点(策略切换处):\(\alpha_A\) 与 \(\alpha_C\) 相交于 \(10p-100(1-p)=8.5\Rightarrow p\approx0.986\)。于是上包络分三段:\(p<0.014\) 开左门(\(\alpha_B\))、\(0.014<p<0.986\) 听(\(\alpha_C\))、\(p>0.986\) 开右门(\(\alpha_A\))。这就是一条**分段线性、凸**的曲线(三段直线、向上凸),每段由一个 α-vector(条件计划)主导——和 §U4.4/实现三 DESPOT 式规划器"\(p=0.99\) 才开门、否则听"的行为一致。
多视角理解:PWLC 上包络 = "belief 空间被切成几块,每块归一个条件计划管"。三条直线把 \([0,1]\) 切成三段,每段的最优动作不同(开左 / 听 / 开右)。belief 落在哪段,就执行那段主导 α 对应的条件计划。这就是"最优策略 = 选 \(\arg\max_\alpha\alpha\cdot b\) 的动作"的几何意义——α-vector 集合同时是值函数(取上包络)和策略(取 argmax)。精确求解就是要算出这些直线(哪些 α、各管哪段);状态多时直线变超平面、数量指数爆炸,于是要近似。
反面:精确求解为什么不可扩展¶
既然 \(V^*\) 能用有限个 α-vector 精确表示,为什么 POMDP 还是出了名地难?因为 α-vector 的数量随视界指数爆炸。
做一步 Bellman 备份(value iteration 的一轮)时,新的 α-vector 集合要枚举"当前动作 × 每个观测分别接哪个旧 α-vector"的所有组合。粗略地,视界 \(H\) 步时 α-vector 数量
每多一步视界,规模以 \(|\Gamma|^{|\Omega|}\) 的方式膨胀——这是观测分支带来的**历史灾难(curse of history)。再加上 belief 本身是 \(|S|\) 维(**维数灾难,curse of dimensionality),精确 POMDP 求解被证明是计算上极难的(PSPACE-hard 量级)。
实践中,绝大多数新生成的 α-vector 是**冗余的**(它们在任何 belief 上都不是上包络的一部分,被其他 α 支配)。精确算法(如 Sondik 的 one-pass、Witness、Incremental Pruning)大量时间花在"剪掉被支配的 α-vector"上,但即便如此也扛不住指数增长——几十个状态、十几步视界就难以为继。
本质洞察:POMDP 的难,难在"两类 curse 叠加"。维数灾难(curse of dimensionality):belief 是 \(|S|\) 维连续向量,状态一多 belief 空间就爆炸。历史灾难(curse of history):值函数的 α-vector 数随视界以 \(|\Gamma|^{|\Omega|}\) 膨胀,观测一多、视界一长就爆炸。精确求解同时撞上这两堵墙。后续所有近似方法本质都是在"绕开其中一堵或两堵墙":点基方法(§U4.3)绕维数灾难(只在少数可达 belief 点上备份,不管整个单纯形);在线树搜索 DESPOT(§U4.4)同时绕两堵(采样状态绕维数灾难、采样观测绕历史灾难)。记住"两个 curse",你就有了理解所有 POMDP 近似算法的统一框架。
QMDP:最廉价的近似(理解 α-vector 的副产品)¶
理解了 α-vector,一个极廉价的近似立刻浮现:QMDP。它假设"再走一步后世界就完全可观测了"——于是用底层 MDP 的 Q 函数 \(Q_{\text{MDP}}(s,a)\)(假装状态可观测算出来的,便宜)当作 α-vector:每个动作 \(a\) 配一个 α-vector \(\alpha_a(s)=Q_{\text{MDP}}(s,a)\),决策时 \(a^*=\arg\max_a\sum_s b(s)Q_{\text{MDP}}(s,a)\)。
QMDP 极快(只需解一个 MDP),但有个系统性短板:它低估"持续获取信息"的长期价值。因为它假设"再走一步世界就全可观测",它认为"不确定性下一步就会自己消失"——于是**消歧不足、倾向过早行动**:在需要持续多步消歧才该出手的问题上,QMDP 往往在 belief 还不够确定时就贸然决策。需要澄清一个常见误传:QMDP 并非"从不获取信息"——在某些不确定的 belief 上它仍会选信息动作(如 Tiger 里听几次),因为该动作的 \(Q_{\text{MDP}}\) 值被"下一步就全可观测、之后能拿满分"的高续值抬高了。它真正的毛病是**系统性低估"消歧要做多久"**,把多步信息收集压缩成"一步就够"。结论:QMDP 适合"信息会自然到来、只需少量消歧"的问题(快且够用),不适合需要大量主动消歧的问题(会过早行动)。
对比性思维:QMDP vs 完整 POMDP,差在"信息的长期价值"。QMDP 把"未来不确定性"当成"下一步就消失",于是它**系统性低估**了"多步消歧"的价值——它能看到信息动作的一步收益(因为续值高),却看不到"需要连续消歧很多步"这件事。完整 POMDP(及下面的点基 / 在线方法)正确评估"持续获取信息→未来 belief 更确定→未来决策更好"的多步长期价值,所以在该消歧时会消歧够、不过早行动。一句话:QMDP 便宜但低估了消歧要做多久,完整 POMDP 贵但算得准。选 QMDP 还是完整方法,先问"我的问题需要多少主动消歧"——只需少量消歧(很多导航任务)QMDP 够用且快;需要大量持续消歧(强歧义任务)则要完整方法。
精确求解算法做了什么(为什么连它们也扛不住)¶
既然 \(V^*\) 能用有限个 α-vector 精确表示,历史上有一批精确算法去算这个集合:最朴素的 Monahan 枚举——一步备份枚举"每个动作 × 每个观测接哪个旧 α"的所有组合,生成指数多个候选 α,再剪掉被支配的;Sondik / Cheng 的 one-pass 方法、Witness 算法(逐个 belief 区域"找证人"确认缺哪个 α)、Incremental Pruning(增量地做交集 + 剪枝,是这类算法里较高效的)。
它们的共同结构是"生成候选 α → 剪掉被支配的 α",差别只在如何更聪明地生成 / 剪枝以少枚举。但无论多聪明,新生成的候选数随视界指数增长(\(|\Gamma|^{|\Omega|}\) 量级),剪枝只能延缓不能消除——几十个状态、十几步视界就跑不动。这正是 §U4.2 思维陷阱"换算法救不了"的具体印证:精确算法的瓶颈是问题固有的(PSPACE-hard),不是剪枝不够好。这也是为什么实践必须转向点基(§U4.3)与在线(§U4.4)近似。
⚠️ 本节常见陷阱¶
💡 概念误区:以为 α-vector 是 belief(也是 \(|S|\) 维向量,容易混) - 新手想法:"α-vector 和 belief 都是 \(|S|\) 维向量,是一回事吧?" - 现象 / 后果:把 α 归一化成概率分布(错误),或把 belief 当 α 去取 max。 - 根本原因:belief \(b\) 是**概率分布**(非负、和为 1),表示"我在哪";α-vector 是**价值向量**(可正可负、不归一化),\(\alpha(s)\) 表示"若真在 \(s\)、执行某计划的价值"。两者维度相同但语义完全不同,通过内积 \(\alpha\cdot b\) 配对。 - 正确做法:分清角色——belief 是输入(你的信念),α 是值函数的分片(候选计划的价值)。检验:α 的分量出现负数是正常的(奖励可负),belief 出现负数是 bug。
🧠 思维陷阱:以为 α-vector 数量爆炸是"实现不好",换个算法就行 - 新手想法:"精确求解慢是因为算法没优化,用更好的剪枝就能扩展。" - 现象 / 后果:在中等规模 POMDP 上死磕精确求解 + 剪枝,仍然超时——因为这是**问题固有的复杂度**(PSPACE-hard),不是实现问题。 - 根本原因:α-vector 随视界指数增长是 POMDP 的本质难度(两个 curse),再好的剪枝也只能延缓、不能消除指数。 - 正确做法:中等规模就上点基近似(SARSOP,§U4.3);大规模 / 实时就上在线树搜索(DESPOT,§U4.4)。精确求解只用于很小的问题或理论分析。
练习¶
- [A 型·QMDP] 在 Tiger 问题上实现 QMDP:先解全可观测 MDP 得到 \(Q_{\text{MDP}}(s,a)\),再用 \(a^*=\arg\max_a\sum_s b(s)Q_{\text{MDP}}(s,a)\) 决策。观察 QMDP 在不同 belief 下何时 listen、何时开门(你会发现它在不确定时确实会 listen,但只 listen 很少几次就开门)。理解 QMDP 的近似本质:它用"下一步全可观测"的假设给动作估值,因此**系统性低估"持续消歧"的长期价值**——在需要长时间消歧的更难问题上会过早行动。
- [A 型·PWLC 可视化] 取一个 2 状态 POMDP(belief 是 \([0,1]\) 上的一个数 \(p=b(s_1)\)),给定 3 个 α-vector(各是一条直线 \(\alpha\cdot b\)),画出它们的上包络 \(V^*(p)=\max_\alpha\alpha\cdot b\)。标出每段由哪个 α 主导、对应哪个动作。验证上包络是凸的分段线性曲线。
- [思考题] 为什么 \(V^*(b)\) 是**凸**的而不是凹的?请从"belief 越不确定、价值越低"的直觉和"有限个线性函数取 max"的代数两方面论证。如果某问题的值函数看起来是凹的,说明你哪里弄反了?
§U4.3 点基方法:只在可达 belief 上备份(SARSOP)⭐⭐⭐¶
动机:不必在整个单纯形上求解¶
§U4.2 说精确求解的死穴是"在整个 belief 单纯形上维护 α-vector,数量指数爆炸"。但有一个关键观察能救命:从一个固定的初始 belief \(b_0\) 出发,实际可达的 belief 只是单纯形里的一小块——不是整个 \(|S|-1\) 维单纯形,而是由"从 \(b_0\) 出发、各种动作-观测序列能到达的 belief"构成的一个低维子集。
直觉:你的 belief 不会乱跑到单纯形任意位置。它从 \(b_0\) 出发,每步按 belief update 转移,能到的地方有限。既然如此,为什么要在永远到不了的 belief 上精确求解? 点基方法(point-based methods)正是抓住这一点:只在一组**代表性的可达 belief 点**上做 Bellman 备份,每个点维护一个 α-vector,用这些 α-vector 近似整个值函数。
理论:点基价值迭代三代演进¶
PBVI(Pineau–Gordon–Thrun, IJCAI 2003,CMU)——开创点基。选一组 belief 点 \(B=\{b_1,\dots,b_n\}\)(从 \(b_0\) 出发探索得到),只在这些点上做备份:每个 \(b_i\) 备份出一个 α-vector \(\alpha_i\)(让 \(\alpha_i\cdot b_i\) 最大的那个条件计划)。值函数近似为 \(\tilde V(b)=\max_i\alpha_i\cdot b\)。关键:α-vector 的数量被**点的数量** \(n\) 限制(每点一个),不再随视界指数膨胀——维数灾难被绕开。PBVI 是 anytime 的(点越多越准),并随用随加点。
HSVI(Smith–Simmons, UAI 2004/2005,CMU)——上下界引导。PBVI 的问题是"该选哪些 belief 点备份"没有明确指引。HSVI 同时维护值函数的**上界**(一组点的凸包,给 \(V^*\) 上界)和**下界**(一组 α-vector,给 \(V^*\) 下界),用"上下界的间隙(gap)"作为启发式:哪个可达 belief 点的上下界间隙大(最不确定它的真实价值),就优先沿着到它的路径下探、在那里备份。这给出**有界次优**保证——上下界夹逼,gap 收窄到阈值就停。
SARSOP(Kurniawati–Hsu–Lee, RSS 2008,NUS)——只盯最优可达 belief。SARSOP 把 HSVI 再推进一步:它只在**最优可达 belief 空间(optimally reachable belief space)上采样备份——即"沿着最优策略"能到达的 belief,而不是所有可达 belief。直觉:连最优策略都到不了的 belief,更不值得花力气。SARSOP 用上下界 + α-vector 剪枝 + 对可达空间形状的估计来聚焦采样,成为**事实标准的离线 \(\epsilon\)-最优 POMDP 求解器(常被用来校准其他在线方法)。代码:AdaCompNUS/sarsop。
三代点基方法怎么选 belief 点¶
PBVI、HSVI、SARSOP 的核心差别,正在于"往哪放 belief 点 / 往哪备份"——这决定了用同样的预算能逼近多准。
- PBVI:从 \(b_0\) 出发,用"扩展 belief 集"启发式逐步加点——挑那些能扩大 belief 集覆盖范围的新可达点(让点尽量散开、覆盖可达区域)。简单,但不区分点的重要性。
- HSVI:用**上下界 gap** 引导——沿"当前上下界间隙最大"的动作-观测路径下探、在路径末端备份。直觉:哪里最"不确定它的真实价值"(gap 大),就优先去那里搞清楚。这让备份集中在"还没想明白"的 belief 上。
- SARSOP:在 HSVI 基础上再加一层聚焦——只在**最优可达(optimally reachable)**belief 上备份,即"沿最优策略会走到"的 belief。它用对可达空间形状的采样估计 + α-vector 剪枝,避免在"虽可达但最优策略不会去"的 belief 上浪费。
三者是层层聚焦:PBVI"覆盖可达"→ HSVI"优先 gap 大的可达"→ SARSOP"只盯最优策略会去的可达"。越往后,同样预算花在越值得的地方,逼近越快——这也是 SARSOP 成为离线事实标准的原因。
对比性思维:点基三代的进步 = "把有限的备份预算花得越来越准"。POMDP 求解的预算(时间 / 内存)有限,关键是花在哪些 belief 上。PBVI 撒胡椒面(覆盖可达)、HSVI 盯不确定(gap 大处)、SARSOP 盯最优路径(最优可达)。这条"越来越聚焦"的演进,和 §U4.4 DESPOT 的 output-sensitive(只为简洁好策略花力气)、§U4.3 思考题里"只盯最优策略会去的地方"是同一审美——好的近似不是均匀逼近,而是把精度集中在最优解附近。
α-vector 的管理:备份、剪枝、下界¶
点基方法的工程核心是管理一个 α-vector 集合 \(\Gamma\):
- 备份(backup):在一个 belief 点 \(b\) 上做一次 Bellman 备份,生成一个新 α-vector(对应"在 \(b\) 上的最优条件计划")。
- 剪枝(prune):新 α 加入后,删掉被支配的 α-vector——若某个 \(\alpha\) 在所有可达 belief 上都不是上包络的一部分(总有别的 α 比它大),它就是冗余的,删掉。剪枝是控制 \(|\Gamma|\) 规模的关键。
- 下界性质:点基方法维护的 α-vector 集合给出 \(V^*\) 的一个**下界** \(\tilde V(b)=\max_\alpha\alpha\cdot b\le V^*(b)\)——因为每个 α 对应一个**真实可执行**的条件计划,其价值不会超过最优值。这个下界性质让点基解"安全"(不会高估价值)。
一次点基备份长什么样(Tiger 走查)¶
把"只在可达 belief 上备份"具体化。从 \(b_0=(0.5,0.5)\) 出发,Tiger 的可达 belief 很少:听一次到 \((0.85,0.15)\) 或 \((0.15,0.85)\),再听到 \((0.97,0.03)\) 等——它们沿对数 odds 等距排开,是单纯形(这里是线段 \([0,1]\))里一串离散点,远非整条线段。点基方法就在这串可达点上放 belief 点、各备份一个 α-vector。
一次备份(backup at \(b\))做什么:在 belief 点 \(b\) 上做一步 Bellman,挑出在 \(b\) 上价值最高的条件计划,生成它的 α-vector:
直觉:对每个动作 \(a\)、每个观测 \(o\),从上一轮的 α 集合里挑"接哪个旧条件计划"最好,组合出新 α;在 \(b\) 上取最优的那个。关键:每个 belief 点只产出一个 α-vector——所以 α 数量 = 点数(线性),不随视界指数膨胀(对比精确求解枚举所有组合)。
为什么给下界:\(\alpha_b\) 对应一个**真实可执行**的条件计划,其在任意 belief 上的价值 \(\le V^*\)。所以 \(\tilde V(b)=\max_b\alpha_b\cdot b\le V^*(b)\)——点基解是 \(V^*\) 的下界,且随备份单调上升、逼近 \(V^*\)。SARSOP 在此基础上只把点放在"最优策略会去"的可达 belief 上,进一步省力。
对比性思维:点基备份 vs 精确备份,差在"在几个点上挑 vs 在整个单纯形上保完整"。精确备份要保证新 α 集合在**整个单纯形**上都是正确上包络——于是要枚举所有 \((a,o\mapsto\alpha)\) 组合、再剪掉被支配的,组合数指数爆炸。点基备份只要求在**手里这几个可达 belief 点**上挑出最优 α——每点一个、数量受控。代价是点之间的 belief 近似可能不准(但 SARSOP 把点放在最该准的地方)。一句话:精确求解"处处正确但指数贵",点基"在可达点上够好且线性省"。
离线 vs 在线:点基方法的定位¶
点基方法是**离线(offline)** 的:花时间预先算出整个策略(一个 α-vector 集合),在线执行时只需查表——维护 belief,每步 \(a^*=\arg\max\)(取使 \(\alpha\cdot b\) 最大的 α 对应的动作)。这让在线执行极快(一次内积)。
它的适用边界: - 适合:状态空间中等(\(|S|\) 几十到几千)、模型固定、需要反复快速决策的问题。一次离线求解,反复在线查表。 - 不适合:状态空间巨大(如连续状态用粒子表示,α-vector 难定义);模型在线变化(如自驾每帧场景不同,离线算的策略用不上);初始 belief 经常变(SARSOP 的可达空间是针对特定 \(b_0\) 的,\(b_0\) 大变就要重算)。这些情况要用**在线方法**(§U4.4 DESPOT)。
多视角理解:点基方法在"求解谱"上的位置 - 相对精确求解:精确求解在整个单纯形上维护所有非支配 α-vector(指数爆炸);点基只在有限个可达 belief 点上各留一个 α-vector(数量受控)。像 / 不像:都用 α-vector 表示值函数,但精确求解要"处处正确",点基只要"在可达点上够好"。 - 相对 QMDP:QMDP 是点基的极端退化(每个动作一个 α-vector、且假设一步后全可观测,系统性低估多步消歧价值);点基方法(SARSOP)做真正的多步备份,能算准"持续获取信息"的长期价值。 - 相对在线树搜索:点基离线算好整个策略(覆盖所有可达 belief),在线只查表;DESPOT 在线只为"当前这个 belief"现算一棵树。点基是"一次算好、反复查",在线是"每次现算、用完就扔"。
本质洞察:点基方法用"可达性"砍掉了维数灾难的大头。精确求解的浪费在于"为永远到不了的 belief 也求解"。点基方法只在从 \(b_0\) 可达(SARSOP 更进一步:最优可达)的 belief 上备份——可达 belief 集通常是单纯形里一个极低维的子集,于是 α-vector 数量从"随视界指数"降到"随采样点数线性"。但它没解决历史灾难的全部(备份本身仍要枚举观测),且依赖"\(b_0\) 固定、模型固定"——一旦 belief 起点或模型在线变化,离线算的就作废。这两条局限正是在线树搜索(DESPOT)登场的理由:DESPOT 只关心"从当前 belief 出发、有限步内",把可达性聚焦到极致,且每周期重算以应对变化的模型。
离线点基与在线搜索的合作:α-vector 当下界¶
离线和在线不是非此即彼——它们常**合作**。点基方法离线算出的 α-vector 集合给出 \(V^*\) 的一个下界(每个 α 是可执行策略,§U4.3),这个下界正好能当**在线搜索的初始下界 / rollout 策略**。
具体地,DESPOT(§U4.4)和 HSVI 都需要一个下界来引导探索、给叶子估值。一个常见做法:先用一个廉价的离线方法(甚至就是 QMDP,或一个粗的点基解)算出 α-vector 作为 DESPOT 的 ScenarioLowerBound——在线搜索时,叶子的下界用 \(\max_\alpha\alpha\cdot b\) 而非从零 rollout,既快又稳。反过来,在线搜索访问到的新 belief 也可以反馈给离线求解器去补点。
对比性思维:离线"算好一张地图",在线"现场找路",两者拼起来最强。离线点基(SARSOP)算出覆盖可达 belief 的 α-vector——像一张粗略地图(哪里大概多值钱);在线 DESPOT 在当前 belief 现场精搜——像在地图上找当下最优路。把离线 α-vector 当在线搜索的下界 / 启发,就是"用粗地图加速精搜"。这也是 POMDPs.jl 等生态里"先 QMDP/FIB 算界、再 DESPOT 在线"的常见组合——离线管全局粗解、在线管局部精解,各取所长。
⚠️ 本节常见陷阱¶
💡 概念误区:以为点基方法给出的是 \(V^*\) 的上界 - 现象 / 后果:用 α-vector 解 \(\max_\alpha\alpha\cdot b\) 当成"价值上限"来做某些剪枝判断,逻辑反了。 - 根本原因:每个 α-vector 对应一个**真实可执行**的条件计划,其价值 \(\le\) 最优值,所以 \(\max_\alpha\alpha\cdot b\) 是 \(V^*(b)\) 的**下界**。(上界由另一套机制维护,如 HSVI 的点凸包或 fast informed bound。) - 正确做法:记住 α-vector 集合 = 值函数下界(也是可执行策略);上界是单独维护的另一套对象。检验:下界应随备份单调上升、逼近 \(V^*\)。
💡 概念误区:SARSOP 算好的策略换个初始 belief 还能用 - 现象 / 后果:在 \(b_0\) 上算好的 SARSOP 策略,换一个差异很大的 \(b_0'\) 直接用,性能变差。 - 根本原因:SARSOP 只在"从 \(b_0\) 最优可达"的 belief 上备份——\(b_0'\) 可达的区域可能没被覆盖,那里 α-vector 稀疏、近似差。 - 正确做法:\(b_0\) 大变就重算(或离线对一族 \(b_0\) 求解)。若 \(b_0\) 频繁变(如每帧不同),考虑在线方法。
🧠 思维陷阱:以为"点基方法是近似的,所以一定比精确求解差很多" - 现象 / 后果:因为是近似就不信任,宁可死磕精确求解。 - 根本原因:在可达 belief 集上,点基方法(尤其 SARSOP 带上下界)可以做到 \(\epsilon\)-最优——它"近似"的只是不可达区域(那里本就无所谓)。 - 正确做法:中等规模问题信任 SARSOP 的 \(\epsilon\)-最优解;它常被当作"准最优"基准来校准在线方法。
练习¶
- [A 型·朴素点基备份] 在 Tiger 问题上实现最简点基价值迭代:固定一组 belief 点(如 \(\{0,0.1,\dots,1\}\) 上的 11 个点),迭代做点基 Bellman 备份,画出值函数下界随迭代的上升。对比 QMDP(§U4.2 练习),验证点基解会选 listen(看得见信息价值)而 QMDP 不会。
- [A 型·上下界 gap] 给 Tiger 维护一个简单上界(如 \(V_{\text{MDP}}\),假设全可观测的值)和点基下界,画出两者的 gap 随迭代收窄。理解 HSVI/SARSOP 为什么用 gap 引导采样。
- [思考题] 为什么 SARSOP 只在"最优可达"belief 上备份,比 PBVI 在"所有可达"belief 上备份更高效?这个"只盯最优策略会去的地方"的思想,和 §U4.4 DESPOT 的"output-sensitive(复杂度依最优策略大小)"有什么共通之处?
§U4.4 DESPOT:在线 POMDP 规划 ⭐⭐⭐⭐¶
动机:当离线行不通¶
点基方法(§U4.3)离线算好整个策略,前提是"状态空间中等、模型固定、\(b_0\) 不常变"。但很多真实问题违反这些前提:
- 状态空间巨大:自驾里"每辆周围车的位置 + 速度 + 隐藏意图"的联合状态空间天文数字,连续状态用粒子表示——α-vector 根本没法在这么大的空间上离线管理。
- 模型在线变化:自驾每一帧的场景(哪些车、在哪、什么布局)都不同,离线对某个固定场景算好的策略,下一帧就用不上。
- 只需"此刻"的决策:实时系统每个控制周期(如 100ms)只需要回答"现在该做什么动作",不需要一张覆盖所有 belief 的完整策略表。
在线(online)POMDP 规划**正是为此:不预先算整个策略,而是在**每个决策周期,只为当前 belief \(b_0\) 现场规划——从 \(b_0\) 出发构造一棵有限深度的搜索树、找出当前最优动作、执行一步,然后下一周期用更新后的 belief 重新规划。DESPOT 是其中的标杆。
前奏:POMCP——belief 树上的 MCTS¶
在 DESPOT 之前,POMCP(Silver–Veness, NeurIPS 2010) 把 MCTS(U1 §U1.7)搬到了 belief 树上,是在线 POMDP 的奠基。它的要点:
- 粒子表示 belief:不显式存 \(b(s)\),而是用一组状态粒子近似 belief——这让它能处理巨大 / 连续状态空间(粒子数与 \(|S|\) 无关)。
- MCTS 四步:从根 belief 出发,用 UCT/UCB 选动作(平衡探索-利用)、采样观测下探、随机 rollout 估叶子价值、反向传播更新节点统计。
- 理论与短板:POMCP 在极限下收敛到最优,简单且在大 POMDP 上实践性能优秀;但它的**最坏情况很差**——UCB 启发式可能被误导、过度贪心(被少数高方差 rollout 带偏)。
DESPOT 保留了 POMCP "用采样破两个 curse"的优点,但用一组**固定的采样场景**来评估策略,避免 POMCP 的极端最坏行为。
理论:确定化稀疏 belief 树(DESPOT 的核心)¶
标准 belief 树的爆炸。从 \(b_0\) 出发、深度 \(D\) 的完整 belief 树包含所有动作-观测历史,节点数 \(O(|A|^D|Z|^D)\)——动作分支(\(|A|\) 路)× 观测分支(\(|Z|\) 路)逐层相乘,双指数。这正是历史灾难。
确定化场景(determinized scenario)。DESPOT 的关键构造:一个**场景** \(\phi=(s_0,\phi_1,\phi_2,\dots)\) 是"一个起始状态 + 一串预先采样好的随机数"。给定场景 \(\phi\) 和一个动作序列,状态和观测的演化就**完全确定**了——随机数 \(\phi_t\) 把"本来随机的转移和观测"在这次模拟里钉死成确定的结果。直觉:场景 = 把随机性"预先掷好骰子",于是同一动作序列在同一场景下走出唯一一条确定轨迹。
DESPOT = 标准 belief 树在 \(K\) 个采样场景下的稀疏子树。从 \(b_0\) 采样 \(K\) 个起始状态(按 \(b_0\) 加权)、配上 \(K\) 串随机数,得到 \(K\) 个场景 \(\{\phi_1,\dots,\phi_K\}\)。DESPOT 这棵树:
- 保留所有动作分支(每个节点仍可选任意动作);
- 只保留 \(K\) 个场景实际经历的观测分支(而非所有 \(|Z|\) 种观测)。
于是节点数从 \(O(|A|^D|Z|^D)\) 降到 \(O(|A|^D K)\)——观测分支被场景数 \(K\) 限制住,不再是 \(|Z|^D\)。这就是"稀疏(sparse)"的含义:一棵只长出 \(K\) 个场景走过的那些观测分支的瘦树。
破两个 curse 的方式: - 采样状态(从 belief 采 \(K\) 个起始状态)→ 破**维数灾难**(不枚举所有状态,只用 \(K\) 个代表,与 \(|S|\) 脱钩); - 采样观测(只保留场景经历的观测分支)→ 破**历史灾难**(不枚举所有观测序列,只用 \(K\) 个场景的,与 \(|Z|^D\) 脱钩)。
一棵 DESPOT 紧凑地编码了"所有策略在这 \(K\) 个场景下的执行"——评估一个策略 \(\pi\),就是看它在 \(K\) 个场景上跑出的平均折扣回报 \(\hat V_\pi(b)=\frac1K\sum_k V_{\pi,\phi_k}\)。
理论:output-sensitive 界与 R-DESPOT 正则化¶
output-sensitive regret 界。DESPOT 最深刻的理论结果:从 DESPOT 得到的最优策略是**近最优**的,其 regret(与真最优的差距)界**依赖于"最优策略的表示大小",而非状态空间大小**。直白说:只要存在一个简洁(表示小)的好策略,DESPOT 用不多的场景 \(K\) 就能找到它——哪怕状态空间天文数字。这就是"output-sensitive"(复杂度随输出/解的大小而定,不随输入/状态空间大小而定),是 DESPOT 能在巨大状态空间里实时工作的理论根基。
过拟合风险与 R-DESPOT。但只看"在 \(K\) 个场景上的平均回报"有个陷阱:一个**复杂**策略可能在这 \(K\) 个特定场景上表现完美(过拟合了这几个采样场景),却在真实分布上泛化很差。R-DESPOT(Regularized DESPOT) 的对策:搜索 DESPOT 时优化一个**正则化目标**
其中 \(|\pi|\) 是策略(子树)的大小,\(\lambda\) 是正则化系数。它在"策略在采样场景上的价值"和"策略的复杂度"之间权衡——惩罚过大的策略,逼它简洁、从而泛化好。R-DESPOT 的理论保证:当存在一个小的最优策略时,R-DESPOT 计算出近最优策略。不加正则化的版本叫 B-DESPOT(Basic DESPOT),在场景少时易过拟合。
对比性思维:R-DESPOT 的正则化 = 机器学习的"奥卡姆剃刀"搬到规划里。在监督学习里,模型在训练集上完美但测试差,是过拟合,对策是正则化(惩罚模型复杂度)。R-DESPOT 一模一样:\(K\) 个场景是"训练集",策略是"模型",在 \(K\) 个场景上完美但真实分布差就是过拟合,\(\lambda|\pi|\) 就是复杂度惩罚。这不是巧合——"用有限样本估计、防过拟合要正则化"是统计学习的普适原理,DESPOT 把它用在了"用 \(K\) 个采样场景估计策略价值"上。理解这个类比,你就懂了为什么 \(K\) 太小时一定要正则化(样本少、过拟合风险高),以及 \(\lambda\) 怎么调(样本越少、\(\lambda\) 越大)。
算法框架:Explore–Expand–Backup(anytime)¶
DESPOT 像 HSVI 一样维护每个节点的**上界**和**下界**,用它们引导搜索(anytime,时间耗尽就停):
输入: 当前 belief b0, 场景数 K, 最大深度 D, 时间预算
1. 采样 K 个场景 {φ_1,...,φ_K}(起始状态 ~ b0 + 随机数串), 建根节点
2. while 还有时间:
a. Explore: 从根沿"上下界 gap 最大"的动作-观测分支下探,
直到一个叶子(gap 足够小 或 到最大深度 D)
b. Expand: 扩展该叶子——对每个动作 a, 用 K 个场景前向仿真一步,
按场景经历的观测建子节点(只长场景走过的观测分支)
c. Backup: 自底向上更新沿途节点的上界/下界
(R-DESPOT: 用正则化目标 V̂ - λ|π| 选最优子策略)
3. 返回根节点的最优动作 a*; 执行一步, 收到真实观测 o
4. 用 (a*, o) 做 belief update 得 b0', 下一周期回到 1(重新采样场景重新规划)
每个决策周期都从零构造一棵新的 DESPOT(用当前 belief、重新采样场景)——这正是"在线、每周期重规划",天然适应模型 / 场景的逐帧变化。
多视角理解:DESPOT 树的三种看法 - 稀疏化视角:它是完整 belief 树被 \(K\) 个场景"稀疏化"后的瘦树——保留全部动作分支、只留场景经历的观测分支。 - 场景集成视角:它同时模拟 \(K\) 个"平行世界"(每个场景一个确定化世界),一个策略的价值 = 它在 \(K\) 个平行世界里的平均表现——和 U1 的场景树、机会约束的场景法同一血脉(用有限采样场景近似随机性)。 - MCTS 变体视角:它是 POMCP(belief 树 MCTS)的"低方差版"——用 \(K\) 个固定场景评估策略,代替 POMCP 的随机 rollout,避免被高方差 rollout 带偏。
本质洞察:DESPOT = "用 \(K\) 个确定化场景,把双指数的随机 belief 树压成线性于 \(K\) 的稀疏确定树"。完整 belief 树的爆炸来自两处:状态多(维数灾难)、观测序列多(历史灾难)。DESPOT 用同一招"采样"同时治两病——采 \(K\) 个起始状态治前者、只留这 \(K\) 个场景经历的观测分支治后者。再用 output-sensitive 界保证"只要好策略简洁,少量场景就够",用 R-DESPOT 正则化防止过拟合这 \(K\) 个场景。这三件事(确定化稀疏树 + output-sensitive + 正则化)合起来,让 POMDP 第一次在"\(10^5\) 量级状态 + 实时"的真实机器人问题上跑通。这也是为什么 DESPOT 成了在线 POMDP 的事实标准、并被搬上自驾车。
与 U1 的连接:belief 树就是被引导的 contingency 树¶
回顾 U1:EUDM/EPSILON 把"他车意图"当隐状态、形式化为 POMDP,但用"引导分支(DCP-Tree + CFB)"做领域剪枝近似求解。现在可以看清两者的关系:
- U1 的 contingency 树对**离散意图**分支;DESPOT 的 belief 树对**观测**分支(\(K\) 个场景经历的观测)。
- U1 用领域知识(一周期一次切换、只对危险车分支)做剪枝;DESPOT 用通用的"采样 \(K\) 个场景"做稀疏化。
- U1 的"引导分支"是 POMDP 的一种**领域专属、强剪枝**的近似解法(牺牲通用性换实时与可解释);DESPOT 是 POMDP 的**通用、采样**近似解法(保通用性,用 output-sensitive 界换实时)。
一句话:U1 的分支规划与 DESPOT 是同一个 POMDP 的两种近似——一个用领域引导剪枝,一个用场景采样稀疏化。
⚠️ 本节常见陷阱¶
💡 概念误区:以为"场景"是采样的状态序列 - 新手想法:"\(K\) 个场景就是 \(K\) 条采样出来的状态轨迹吧。" - 现象 / 后果:把场景理解成轨迹,搞不懂"为什么同一场景下不同动作序列走出不同轨迹"。 - 根本原因:场景 \(\phi=(s_0,\phi_1,\phi_2,\dots)\) 是"起始状态 + 一串**随机数**",不是轨迹。随机数把随机性钉死,但走出什么轨迹仍取决于你**选什么动作**——同一场景 + 不同动作序列 = 不同确定轨迹。这正是"一棵 DESPOT 编码所有策略在 \(K\) 场景下的执行"的关键。 - 正确做法:把场景想成"预先掷好的骰子序列"——决策(动作)还是你做的,骰子只是不再随机。
💡 编程陷阱:\(K\) 选得太小,过拟合采样场景 - 现象 / 后果:\(K\) 很小时,B-DESPOT 找到的策略在这几个场景上完美、实跑很差(决策抖动、对未采样到的观测毫无准备)。 - 根本原因:用太少场景估计策略价值,方差大、易过拟合(同监督学习样本太少)。 - 正确做法:用足够的 \(K\)(典型几十到几百,按问题调),并用 R-DESPOT 正则化(\(\lambda|\pi|\))防过拟合;\(K\) 越小 \(\lambda\) 应越大。检验:增大 \(K\) 看策略是否稳定、实跑性能是否提升(练习里会做 \(K=50\) vs \(K=500\))。
🧠 思维陷阱:把 DESPOT 当离线求解器用(算一次想反复用) - 现象 / 后果:跑一次 DESPOT 存下"策略",之后每帧直接用——但场景变了、belief 变了,旧树的动作不再合适。 - 根本原因:DESPOT 是**在线**方法,每棵树只为"当下这个 belief、这次采样的场景"服务,用完即弃。它的价值正在于每周期重算、适应变化。 - 正确做法:每个决策周期用当前 belief 重新采样场景、重建 DESPOT。要"算一次反复用"的离线策略,用点基方法(SARSOP)。
练习¶
- [A 型·确定化场景] 实现"场景 = 起始状态 + 随机数串":写一个
step(state, action, rand_seq)用预定随机数序列做确定性转移 + 观测。验证:同一随机数串 + 不同动作序列 → 不同确定轨迹;不同随机数串 + 同动作序列 → 不同轨迹。理解场景为何能"确定化"随机执行。 - [A 型·K 的影响] 在 Tiger(或 RockSample)上跑一个 DESPOT 式在线规划器(可用 §完整实现精读的简化版),分别用 \(K=10,50,200\) 场景,记录策略质量(平均回报)与单步规划耗时。验证 \(K\) 越大越好但越慢——理解"为什么 \(K=500\) 比 \(K=50\) 更好但更慢"。
- [B 型·稀疏树画图] 给一个 \(|A|=2,|Z|=2,D=3\) 的小 POMDP,分别画出(a)完整 belief 树(\(O(|A|^D|Z|^D)\) 节点)和(b)\(K=3\) 个场景下的 DESPOT(只留场景经历的观测分支)。数一数两者节点数,直观感受"稀疏"省了多少。
- [思考题] R-DESPOT 的正则项 \(\lambda|\pi|\) 和监督学习的 L2 正则、U3 进阶里的保守度权衡有何共通?为什么"在 \(K\) 个采样场景上估计策略价值"必然面临过拟合、必须正则化?
§U4.5 DESPOT 家族演化 ⭐⭐⭐¶
动机:从能跑通到上车¶
DESPOT(§U4.4)让在线 POMDP 在大状态空间实时跑通,但要真正上自动驾驶车,还差几步:算得更快(GPU)、处理大观测空间不过度乐观、规划视界更长、把"历史灾难"交给学习。NUS AdaComp 组(Hsu/Lee)围绕 DESPOT 做了一条清晰的演化链,是"一个算法如何被打磨到工业落地"的范本。
血缘表:五代演进¶
| 算法 | 年份/出处 | 核心创新 | 相对前身的增量 |
|---|---|---|---|
| DESPOT | NeurIPS 2013 / JAIR 2017 | 确定化稀疏 belief 树 + K 场景 + R-DESPOT 正则化 | 取代 POMCP 随机 rollout,方差更低、最坏情况好 |
| HyP-DESPOT | RSS 2018 | CPU 多线程 + GPU CUDA 并行 rollout;GPU 端 Dvc_DSPOMDP 接口 |
加速 100–500×,让 DESPOT 进实时控制回路 |
| DESPOT-α | RSS 2019 | α-vector 粒子近似 + 子策略共享 | 解决大观测空间下的过度乐观(观测多时方差爆) |
| Context-POMDP | ICRA 2020 | 道路上下文 + 行人隐藏意图建模;集成 SUMMIT 模拟器 | HyP-DESPOT 的城市驾驶实例化 |
| MAGIC | RSS 2021 | Generator-Critic 端到端**学宏动作(macro-action)** | 砍掉有效规划视界的指数因子 |
| LeTS-Drive | RSS 2019 / T-RO 2023 | 离线模仿树搜索训练网络 → 在线**引导** HyP-DESPOT | 把"历史灾难"部分交给学习 |
主干:DESPOT → HyP-DESPOT → Context-POMDP → (LeTS-Drive, MAGIC)。正交分支:DESPOT → DESPOT-α(处理大观测空间)。
逐个看:每一步解决什么(按三轴展开)¶
HyP-DESPOT(硬件轴:GPU 并行)。DESPOT 的瓶颈在"对 \(K\) 个场景做前向仿真 + rollout 估值"——而 \(K\) 个场景**彼此独立**(各持一串随机数、各走各的轨迹),这是教科书式的"易并行(embarrassingly parallel)"。HyP-DESPOT 据此做两级并行:CPU 多线程并行探索树的不同子树(共享上下界),GPU 用 CUDA 并行场景 rollout(每个线程跑一个场景,\(K\) 取几百时几百个 rollout 同时算——正是 GPU 擅长的同构独立小计算)。加速 100–500 倍,让 DESPOT 进几十毫秒的控制周期。代价:用户要额外提供 GPU 端的 Dvc_DSPOMDP(Dvc_ = device),把 Step 等写成 CUDA 核函数。算法与理论界没变,纯靠硬件落地。
DESPOT-α(正交分支:治大观测空间)。当观测空间很大时,\(K\) 个场景各自经历的观测几乎都不同——于是每个观测分支只有极少(甚至一个)场景支撑,子树之间无法共享信息,价值估计偏**乐观**(少数样本容易碰巧给出高估)。这是 §U4.4"\(K\) 太小过拟合"在大观测空间的极端形式。DESPOT-α 用 α-vector 的粒子近似让"相似观测下的子策略共享价值估计"——把原本割裂、各自乐观的观测分支信息打通,缓解高估。它不在主干上,是专治观测维度的正交改进。
Context-POMDP(领域轴:自驾实例化)。把 HyP-DESPOT 用到城市驾驶:周围车 / 行人的意图(要不要变道 / 过马路)作为隐状态 \(y\)(自车状态可观测、他人意图不可观测——正是 MOMDP 结构,进阶九);用**道路上下文**(车道几何、人行道、信号灯)约束意图的先验与转移(如"行人在斑马线前更可能过街");观测是带噪的位置 / 朝向,经观测模型反推意图 belief;再由 HyP-DESPOT 在"自车状态 + 他人意图 belief"上在线规划。配套 SUMMIT 模拟器生成密集城市交通。这是"通用 POMDP 求解器 + 领域模型 = 落地系统"的样板——与 U1 的 EPSILON 处理同一意图问题,区别在 Context-POMDP 用通用 DESPOT 树搜索、EPSILON 用领域引导分支。
MAGIC(学习轴:学宏动作砍视界)。POMDP 的有效规划视界长时,树深 \(D\) 大、\(|A|^D\) 爆炸。MAGIC 用 Generator-Critic 架构**学习一组宏动作(macro-action,多步动作的封装)**——规划时在宏动作(而非原始单步动作)上搜索,等效地把视界缩短一个指数因子。这是"用学习压缩动作空间 / 视界"。
LeTS-Drive(学习轴:学引导树搜索)。历史灾难的根在"树要探很多分支"。LeTS-Drive 先**离线模仿树搜索的结果训练一个网络**(学"好的搜索该往哪走"),在线时用它**引导** HyP-DESPOT 的探索(优先展开网络看好的分支)——把"该探哪里"这件耗时的事部分交给学到的先验。这与 §U4.8 的 BetaZero(学价值/策略网引导 belief MCTS)、U1 §U1.7 的"神经化分支"是同一潮流。
本质洞察:DESPOT 能 GPU 加速百倍,根本原因是"采样场景"这一设计本身就并行友好。DESPOT 用 \(K\) 个独立场景估策略价值(§U4.4)——这个"独立"不只带来低方差,还带来天然并行性:\(K\) 个场景无依赖、可同时算。所以 HyP-DESPOT 不是改了算法,而是兑现了 DESPOT 结构里本就存在的并行潜力。这给算法设计一个启示:一个方法能否被硬件加速,往往在它的数学结构里就决定了——蒙特卡洛 / 采样类方法(DESPOT、粒子滤波、MPPI)大多天然并行、适合 GPU,而强顺序依赖的方法(如某些图搜索)则难。
多视角理解:DESPOT 家族的演化轴 - 硬件轴:DESPOT(CPU)→ HyP-DESPOT(GPU 并行,快 100×)——同算法、换算力。 - 领域轴:DESPOT(通用)→ Context-POMDP(注入道路 / 行人领域模型)——通用求解器 + 领域知识 = 落地。 - 学习轴:DESPOT(纯搜索)→ MAGIC(学宏动作压视界)/ LeTS-Drive(学引导压历史灾难)——把搜索里最耗时的部分交给学习。 三条轴正交,可叠加:Context-POMDP 本身就是"GPU(HyP)+ 领域(道路)",再叠 LeTS-Drive 的学习引导,就是当前自驾 POMDP 的形态。
本质洞察:DESPOT 家族的演化 = "保住采样稀疏树的骨架,逐个攻克落地障碍"。骨架(确定化稀疏 belief 树 + output-sensitive + 正则化)从未变;变的是周边——HyP 用 GPU 攻速度、DESPOT-α 攻大观测空间的乐观偏差、Context 注入领域模型、MAGIC/LeTS 用学习攻视界与历史灾难。这与 U1 的 EUDM→EPSILON→MARC 演化同构(保骨架、换组件),也是成熟算法的通用成长路径:先把核心思想做对,再逐个补齐"快、准、专、聪明"的工程短板。对你的启示:遇到一个能跑通但上不了线的算法,别推倒重来,沿"它落地缺什么(速度?精度?领域适配?视界?)"逐个攻。
横向对比:四个在线 POMDP 求解器¶
DESPOT 不是唯一的在线 POMDP 求解器。把同库 / 同生态里的几个主力放一起对比,便于选型(AdaCompNUS/despot 库里就含 DESPOT/POMCP/AEMS 三个,可一键切换对比)。
| 求解器 | 核心机制 | 优 | 劣 |
|---|---|---|---|
| POMCP | belief 树 MCTS + UCT + 随机 rollout | 简单、大 POMDP 实践好 | 最坏情况差(UCB 可被误导、过度贪心) |
| DESPOT | K 确定化场景稀疏树 + 上下界 + 正则化 | 方差低、output-sensitive、最坏情况好 | 需调 K/λ;离散观测为主 |
| AEMS | 启发式搜索 belief 树(用上下界 gap 选下探) | 有界次优、收敛快 | 显式 belief(中等状态)、大状态吃力 |
| POMCPOW | POMCP + Progressive Widening | 处理连续动作 / 观测 | 连续空间调参更敏感 |
它们共享"在线、从当前 belief 现算、anytime"的框架,分野在"怎么控制采样 / 分支":POMCP 随机 rollout、DESPOT 固定 K 场景、AEMS 上下界启发式、POMCPOW 渐进加宽。文献常用 SARSOP(离线 \(\epsilon\)-最优)当基准来校准这些在线方法。
对比性思维:在线 POMDP 求解器的差别,全在"如何花有限的仿真预算"。预算(时间)有限,仿真次数有限——关键是把仿真花在哪。POMCP 用 UCB 自适应但可能被高方差 rollout 带偏;DESPOT 用固定 K 场景换低方差 + output-sensitive 保证;AEMS 用上下界 gap 精准下探但要显式 belief;POMCPOW 用渐进加宽防连续观测退化。没有普遍最优——离散中等用 AEMS/DESPOT、大状态用 POMCP/DESPOT、连续用 POMCPOW。DESPOT 之所以成主力,是它在"低方差 + 大状态 + 有保证"上的综合最均衡。
一个真实自驾 POMDP 栈:三轴如何叠在一起¶
家族成员不是互斥的选项,而是**可叠加的层**。一个落地的城市自驾 POMDP 决策栈,往往把三轴同时用上:
- 底座(领域轴):Context-POMDP 提供问题定义——周围车 / 行人意图作隐状态、道路上下文约束意图先验、SUMMIT 生成交通。这决定了"在解什么 POMDP"。
- 求解器(硬件轴):HyP-DESPOT 做在线求解——GPU 并行 rollout 让它在几十毫秒控制周期内搜完一棵 DESPOT。这决定了"能不能实时解"。
- 加速(学习轴):LeTS-Drive 用离线学到的网络引导 HyP-DESPOT 的探索(优先展开网络看好的分支),把"历史灾难"里"该探哪"的耗时部分压下来。这决定了"在有限预算内能搜多好"。
于是一帧的决策流程是:用当前传感更新意图 belief(Context 的观测模型)→ HyP-DESPOT 在 GPU 上搜一棵 DESPOT(LeTS 网络引导探索)→ anytime 时间到、返回最优动作 → 执行一步 → 下一帧重来。MAGIC 的宏动作可进一步嵌入,缩短有效视界。
本质洞察:DESPOT 家族的"可叠加性"源于骨架不变、改动正交。HyP 改实现(不碰算法)、Context 改问题定义(不碰求解器)、LeTS/MAGIC 改探索 / 动作空间(不碰稀疏树骨架)——三者作用在系统的不同层,互不冲突,所以能叠成一个栈。这正是 §U4.5 主线"保骨架、换组件"的工程红利:因为每代改动都正交,它们能组合而非互斥。对你的启示:设计算法演化时,让每次改动作用在正交的层(实现 / 问题 / 策略),未来才能自由组合。
把抽象落地:宏动作长什么样,家族在更大谱系里的位置¶
宏动作具象(MAGIC)。抽象地说"宏动作压缩视界"不够直观。具体到驾驶:原始单步动作是"这一帧的加速度 / 转向",规划 10 步要搜 \(|A|^{10}\);而宏动作是"保持车道 2 秒""向左变道""在斑马线前减速让行"这类多步封装——在宏动作上搜,等效视界从"几十帧"压到"几个宏动作",指数因子被砍掉。MAGIC 学的就是"在当前 belief 下,哪几个宏动作值得展开"。
家族在更大谱系里的位置。DESPOT 全家族(NUS)是在线 POMDP 的一支主线,但不是全部。同期还有 AEMS(启发式搜索 belief 树,常被放进 despot 库做对比,但它属于另一条"启发式搜索"血缘,非 DESPOT 家族)、POMCPOW(Stanford,连续空间,进阶三)、以及后续的 AdaOPS 等。它们共享"在线、anytime、采样 / 搜索"的大框架,DESPOT 家族的特色是"确定化场景 + output-sensitive + 一条清晰的工程演化链"。把 DESPOT 家族放在这个谱系里看:它不是孤立的算法,而是"在线 POMDP"这棵大树上被打磨得最适合机器人落地的一支。
⚠️ 本节常见陷阱¶
💡 概念误区:以为 HyP-DESPOT 改进了 DESPOT 的算法/理论 - 现象 / 后果:以为 HyP-DESPOT 有更好的近似界或搜索策略。 - 根本原因:HyP-DESPOT 的贡献是**并行实现**(CPU 多线程 + GPU rollout),算法与理论界和 DESPOT 一致——它解决的是"算得够不够快",不是"算得对不对"。 - 正确做法:分清"算法创新"(DESPOT-α 治乐观、MAGIC 压视界)与"工程加速"(HyP 的并行)。两类改进都重要,但性质不同。
🧠 思维陷阱:以为"学习辅助(LeTS/MAGIC)"意味着抛弃了树搜索 - 现象 / 后果:以为这些方法是端到端神经网络,不再有 POMDP 树搜索。 - 根本原因:LeTS-Drive / MAGIC 是**学习 + 搜索的混合**——学习负责"引导 / 压缩"(该探哪、用什么宏动作),底层仍是 HyP-DESPOT 的树搜索(保留可解释、近最优保证)。这正是"学习提供先验、搜索提供保证"的混合范式(同 BetaZero、U1 神经化分支)。 - 正确做法:理解主流不是"搜索 vs 学习"二选一,而是"学习引导搜索"——既要学习的样本效率,又要搜索的可验证性。
练习¶
- [A 型·宏动作] 在一个格子世界 POMDP 上,对比"单步动作"和"宏动作(如'向北走 3 格')"两种动作空间下的规划树深度与节点数。验证宏动作如何把有效视界缩短、树变小——理解 MAGIC 的动机。
- [B 型·HyP-DESPOT 接口精读] 阅读
AdaCompNUS/hyp-despot的Dvc_DSPOMDPGPU 接口,对比 CPU 端DSPOMDP,找出哪些函数被移到 GPU(设备端)执行、为什么是这几个(提示:并行 rollout 里被 \(K\) 个场景反复调用的那些)。 - [思考题] Context-POMDP(把意图当隐状态在线 POMDP 规划)和 U1 的 EPSILON(把意图当隐状态、引导分支近似 POMDP)解决同一类自驾意图问题。对比两者:DESPOT 路线和 EUDM 引导分支路线各自的优劣(提示:通用性 vs 可解释性、采样稀疏化 vs 领域剪枝)?
§U4.6 Belief-space motion planning:高斯 belief 的连续空间特化 ⭐⭐⭐¶
动机:连续高维状态怎么办¶
§U4.2–U4.5 的 POMDP 方法(α-vector、点基、DESPOT)主要面向**离散**状态 / 观测,或用粒子处理连续状态。但机器人有一大类问题是**连续高维**的:机械臂的关节位形、移动机器人的连续位姿。在这些问题上,机器人规划界**独立**发展出一条支线——belief-space motion planning(BSP,信念空间运动规划),核心假设是 belief 为高斯分布(用均值 + 协方差刻画,而非任意分布)。
高斯假设的代价与收益:收益是 belief 用 \((\mu,\Sigma)\) 紧凑表示、可微、能用卡尔曼系机器解析处理高 DoF;代价是**只能表示单峰**——处理不了多模态 belief(如走廊两端的双峰歧义,§U4.1)。所以 BSP 是 POMDP 在"高斯 belief + 连续空间"下的**特化**:擅长高 DoF,不擅长多模态。
脉络:从评估路径到 belief 空间图¶
LQG-MP(van den Berg, Abbeel, Goldberg, RSS 2010 / IJRR 30(7):895–913, 2011)——执行前评估路径质量。LQG-MP(Linear-Quadratic Gaussian Motion Planning)的思想:对一条候选路径(常由 RRT 生成),假设执行时用 LQG 控制器(LQR + 卡尔曼滤波)、用高斯模型刻画运动与观测噪声,于是可以**在执行之前**解析地算出机器人沿这条路径的**先验状态分布**(每个路点的协方差)。有了沿途协方差,就能评估路径质量——比如算"碰撞概率",从一堆候选路径里选最可靠的。关键贡献:让"路径的不确定性"在执行前可量化、可比较。
ML 观测假设(Platt, Tedrake, Kaelbling, Lozano-Pérez, RSS 2010)——化归确定性优化。这是与 LQG-MP 不同的另一篇 RSS 2010 工作(两者常被混淆,需分清)。它的核心技巧:规划时**假设未来的观测都等于其最大似然(期望)值**——这样 belief 的演化就不再随机(观测被钉死成 ML 值),belief 空间规划**化归为确定性轨迹优化**,可用高效的轨迹优化(如 DDP/iLQG)求解。这让 belief 规划首次能在高维问题上实时。代价:ML 观测假设在歧义大、观测信息量低时会失真(实际观测可能远离 ML 值)。
RRBT(Bry, Roy, ICRA 2011)——RRT* 进 belief 空间。把 RRT*(渐近最优采样规划)搬进 belief 空间:树的每个节点不只携带位置,还携带**协方差**(高斯 belief 的不确定性)。扩展时同时传播均值和协方差,并按"代价 + 不确定性"剪枝。这让采样式规划能在 belief 空间里找"既短又确定"的路径。
FIRM(Agha-mohammadi, Chakravorty, Amato, IJRR 33(2):268–304, 2014)——破历史灾难的 belief 图。前身是 Belief Roadmap(Prentice–Roy, IJRR 2009,PRM 式 belief 图 + 协方差因子分解)。FIRM 的关键创新:在 belief 图的每个节点放一个 stationary LQG 节点控制器,把机器人"稳定到该节点对应的一个固定 belief"——于是节点的 belief 变得**与到达历史无关**(belief-invariant)。这一招**打破了历史灾难**:因为每个节点的 belief 被控制器钉成固定值,不同路径到同一节点后 belief 相同,图上的规划就退化成普通的图搜索(节点间转移代价可预先算好、可组合)。这是 BSP 里最巧妙的结构设计之一。
BSP-iSAM / 广义信念空间(Indelman, Carlone, Dellaert, IJRR 34(7):849–882, 2015)——接 SLAM 的增量平滑。把 BSP 接入 iSAM2 增量平滑(因子图 SLAM 的主流后端):在因子图框架里**可微地计算"未来信息增益"——即"如果我走到某处测量,未来地图 / 位姿的不确定性会降多少"。这直接贯通了 **Active SLAM(§U4.7):你的 GTSAM / iSAM2 因子图后端,加上"未来信息增益"的可微计算,就能规划"下一步去哪测最划算"。对 SLAM 工程师,这是 BSP 与你已有工具(因子图)最直接的接口。
与 POMDP 的关系¶
| 维度 | 通用 POMDP(§U4.2–U4.5) | Belief-space planning(本节) |
|---|---|---|
| belief 表示 | 任意分布(α-vector / 粒子) | 高斯(均值 + 协方差) |
| 状态空间 | 离散,或粒子化的连续 | 连续高维(位形 / 位姿) |
| 擅长 | 多模态、感知混淆、信息获取 | 高 DoF、解析、可微 |
| 不擅长 | 高 DoF 连续(粒子维数灾难) | 多模态(高斯只能单峰) |
| 代表 | SARSOP, DESPOT | LQG-MP, RRBT, FIRM, BSP-iSAM |
多视角理解:BSP 是 POMDP 的"高斯特例",像卡尔曼滤波是贝叶斯滤波的高斯特例。贝叶斯滤波对任意分布成立,卡尔曼滤波是它在"线性高斯"下的解析特例(快、可微、但只能单峰)。BSP 与通用 POMDP 的关系完全平行:通用 POMDP 对任意 belief 成立(α-vector / 粒子,能处理多模态但贵),BSP 是它在"高斯 belief"下的特例(用 \((\mu,\Sigma)\) 解析处理高 DoF,但只能单峰)。像 / 不像:都在 belief 上规划,但 BSP 用高斯换来了连续高维的可解析性、丢掉了多模态表达力。理解这个平行,你就知道 BSP 和 DESPOT 不是竞争而是互补——高 DoF 连续问题用 BSP,多模态 / 感知混淆问题用 DESPOT。
本质洞察:BSP 用"高斯 belief"把 POMDP 的连续高维难题变可解析。通用 POMDP 在连续高维状态上会撞粒子维数灾难(高维空间需要指数级粒子)。BSP 的破局是限定 belief 为高斯——于是 belief 演化变成协方差的传播(Riccati 方程那一套),可解析、可微、与状态维度多项式相关。FIRM 更进一步用 stationary 控制器把节点 belief 钉成固定值,连历史灾难也破了。代价是单峰假设——遇到真正的多模态歧义(双峰 belief),BSP 无能为力,得回到粒子 / DESPOT。一句话:BSP 用单峰假设换连续高维的可解性,是 POMDP 在机器人运动规划里的"卡尔曼式"特化。
协方差怎么沿路径传播(LQG-MP 与 FIRM 的机制)¶
把 BSP 的"高斯 belief 演化"具体化,就是协方差矩阵 \(\Sigma\) 沿路径的传播——卡尔曼那一套:
- 预测步:\(\Sigma^- = A\Sigma A^\top + W\)(\(A\) 是线性化动力学、\(W\) 是过程噪声)——不确定性**增大**。
- 更新步:\(\Sigma^+ = (I-KH)\Sigma^-\)(\(K\) 是卡尔曼增益、\(H\) 是观测线性化)——观测带来信息、不确定性**减小**。
LQG-MP 就是沿一条候选路径反复跑这个递归,预先算出每个路点的 \(\Sigma\);有了 \(\Sigma\),路点处的**碰撞概率**可由"障碍方向上的位置方差"经高斯尾概率估出(距离障碍 \(d\)、投影到障碍方向的标准差 \(\sigma\),碰撞概率 \(\approx\Phi(-d/\sigma)\))。于是不同候选路径可按碰撞概率排序——这就是 §U4.6 说的"执行前评估路径质量"。
FIRM 的 stationary 招数:注意上面的 \(\Sigma\) 依赖"怎么走到这"(历史),这就是历史灾难在 BSP 里的化身。FIRM 在每个图节点放一个 LQG 控制器,让机器人在该节点处**稳定到一个固定的协方差** \(\Sigma_\infty\)——它是离散代数 Riccati 方程的不动点解(控制器一直作用,\(\Sigma\) 收敛到 \(\Sigma_\infty\),与初始无关)。于是"到达节点后的 belief"被钉成 \(\Sigma_\infty\),与到达路径无关(belief-invariant)。这把"带历史的 belief 传播"退化成"节点间转移代价可预先算、可组合"的普通图搜索——历史灾难被破。
对比性思维:LQG-MP 评估给定路径,FIRM 在图上搜索路径,差在"要不要消除历史依赖"。LQG-MP 对**一条**给定路径传播协方差、算质量——它不消除历史依赖(每条路径的 \(\Sigma\) 都依赖该路径),所以只能逐条评估、不能在图上自由组合。FIRM 用 stationary 控制器把节点 belief 钉死,消除了历史依赖,于是节点间的代价可预先算、像普通图一样组合搜索——代价是要在每个节点稳定(多花控制步)。这正对应 §U4.4 DESPOT 用采样限制历史分支——两者都在破历史灾难,FIRM 用"控制器钉死 belief"、DESPOT 用"采样限制观测分支"。
迭代 belief 空间优化:从评估到优化的桥¶
LQG-MP(§U4.6)只**评估**给定路径的协方差质量,不**优化**路径本身。一条自然的延伸是把整条 belief 轨迹当决策变量、直接做轨迹优化——这就是 van den Berg 等的迭代 belief 空间优化(如 belief 空间里的 iLQG / DDP,IJRR 2012 等)。
做法:把"belief 的均值 + 协方差随时间的演化"写成一个增广的确定性系统(高斯 belief 用 \((\mu,\Sigma)\) 参数化、配 ML 观测假设让演化确定),代价函数含到达项 + 控制项 + 不确定性项(如终端 \(\mathrm{tr}\,\Sigma\)),然后用 iLQG / DDP 这类局部轨迹优化器迭代求局部最优的 belief 轨迹。直觉:不是"先生成一堆路径再挑"(LQG-MP),而是"从一条初始路径出发、沿降低代价 + 不确定性的方向迭代改进"。
这条线正是 §U4.6(BSP,评估 / 采样)通向进阶专题十的 belief-space MPC(滚动时域优化)的桥:迭代 belief 优化求一整条最优 belief 轨迹,belief-MPC 则把它放进滚动时域、每步重优化。两者都属"连续优化派"——把 belief 当连续状态、用梯度 / DDP 优化,与 DESPOT 的"采样树搜索派"分庭抗礼。
对比性思维:BSP 内部也分"挑现成的 vs 优化出来的"两路。LQG-MP / RRBT 是"生成候选(RRT / RRT*)再按不确定性挑 / 剪"——离散候选里选最好。迭代 belief 优化 / belief-MPC 是"把 belief 轨迹当连续变量直接优化"——连续空间里求局部最优。前者覆盖广、能跳出局部(采样的好处),后者收敛快、精度高(梯度的好处)——和 U0 讲的"采样规划 vs 优化规划"的取舍在 belief 空间里重演。工程上常组合:采样给初值、优化做精修。
为什么"belief 空间的 RRT*"不等于普通 RRT*¶
RRBT 把 RRT* 搬进 belief 空间,但**不是简单地给节点贴个协方差**——它改变了"什么是更优路径"的定义。普通 RRT* 比较节点只看路径代价(长度 / 时间);RRBT 比较节点要看**代价 + 不确定性**两个维度——一个节点可能路径更短但协方差更大(更不确定 / 更易碰),另一个更长但更确定。
这带来一个关键后果:RRBT 的节点支配关系是偏序而非全序。普通 RRT* 里"代价小者支配代价大者"(全序,可直接剪);RRBT 里"代价**且**协方差都不差者才支配"(偏序)——一个节点只有在"既不更长、协方差也不更大"时才被剪。于是同一位置可能要保留**多个**节点(不同的代价-不确定性权衡),树更胖。这正是"在 belief 空间规划"比"在状态空间规划"贵的具体体现——你多了一个要权衡的维度(不确定性)。
本质洞察:把规划搬进 belief 空间,本质是"给每条路径多记一个不确定性维度,于是最优变成多目标权衡"。状态空间规划里,路径只有一个标量代价,最优是全序、易剪。belief 空间规划里,每条路径还带一个不确定性(协方差),"最优"成了"代价-不确定性"的 Pareto 权衡——短而险 vs 长而稳,谁更优取决于你多怕碰撞。RRBT 用偏序支配保留 Pareto 前沿上的多个候选、FIRM 用 stationary 控制器把不确定性钉成常数从而恢复全序(§U4.6)——两种应对"多出来的不确定性维度"的不同策略。这也解释了为什么 belief 空间规划普遍比状态空间规划贵:你在跟一个多目标问题搏斗。
Belief Roadmap 的"协方差因子分解"为什么省¶
FIRM 的前身 Belief Roadmap(BRM, Prentice–Roy, IJRR 2009) 解决的是一个很实际的效率问题:在 PRM 式的 belief 图上,每查询一次(换个起点 / 终点)都要沿边重新传播协方差,很慢。BRM 的关键招数是**协方差的因子分解(factoring the covariance)——它把"沿一条边的协方差传播"预计算成一个**与具体协方差值无关的线性传递函数(一个一次性可算、可组合的矩阵对),于是查询时不必逐步跑 Riccati 递归,只需把这些传递函数串起来(矩阵乘)即可得到终点协方差。
直觉:协方差沿边的演化(预测 + 更新)在合适的参数化下是一个**线性分式 / 线性传递**,可以"打包"成边的固有属性、离线算一次、在线复用。这把"每次查询都重算协方差"降到"一次预计算 + 在线矩阵组合"——和 FIRM 用 stationary 控制器钉死节点 belief 是两种不同的"让协方差可组合"的思路(BRM 用传递函数预计算、FIRM 用控制器钉死节点)。
对比性思维:BRM 和 FIRM 都在让"协方差传播可复用",一个靠预计算传递函数、一个靠控制器钉死节点。belief 图规划的痛点是协方差依赖历史、不能直接在图上组合。BRM 的解法:"把每条边的协方差传播预计算成传递函数,查询时组合"——边可复用、但节点 belief 仍依赖路径。FIRM 更进一步:"在节点用控制器把 belief 钉成固定值"——节点也 belief-invariant、彻底退化成普通图搜索。两者是同一目标(让 belief 图可高效组合搜索)下的递进,FIRM 的代价是要在节点稳定(多花控制步),收益是更彻底的历史无关性。
⚠️ 本节常见陷阱¶
💡 概念误区:把 LQG-MP 和"ML 观测假设"当成同一篇工作 - 现象 / 后果:引用混乱,把"假设未来观测=期望观测"安到 LQG-MP 头上。 - 根本原因:这是**两篇不同的 RSS 2010 论文**——LQG-MP(van den Berg–Abbeel–Goldberg)是"沿候选路径传播 LQG 协方差、执行前评估碰撞概率";ML 观测假设(Platt–Tedrake–Kaelbling–Lozano-Pérez)是"假设未来观测=最大似然值、化归确定性优化"。两者思路不同。 - 正确做法:分清归属——LQG-MP = 协方差传播评估路径;ML 观测假设 = 钉死观测做确定性优化。
🧠 思维陷阱:以为高斯 belief 适用于所有 SLAM / 定位问题 - 现象 / 后果:在感知混淆(走廊两端一样、对称环境)里用高斯 BSP,结果均值落在不可能位置(两峰中间)、规划失效。 - 根本原因:高斯只能表示单峰;感知混淆 / 全局定位歧义本质是**多模态** belief,高斯表示不了。 - 正确做法:单峰 / 局部不确定(已大致知道在哪、只是有噪声)用高斯 BSP;多模态 / 全局歧义(不知道在哪、有多个候选)用粒子滤波 + 粒子 POMDP(DESPOT)。
练习¶
- [A 型·协方差传播评估路径] 实现 LQG-MP 的核心:给两条候选路径(一条短但靠近障碍、一条长但远离障碍),用 LQG 沿路径传播协方差,算各自的碰撞概率,选更可靠的。验证"短路径不一定更优"(不确定性可能让它碰撞概率更高)。
- [A 型·ML 观测假设] 在一个 1D 定位问题上,对比"真实随机观测"和"ML 观测假设(观测=期望值)"下 belief 的演化。验证:信息量高(观测准)时两者接近;信息量低 / 歧义大时 ML 假设失真。理解 Platt 等方法的适用边界。
- [B 型·BSP-iSAM 与因子图] 精读 Indelman–Carlone–Dellaert 2015,理解(a)如何在 iSAM2 因子图里计算"未来信息增益"、(b)它与你在 SLAM 里用的 GTSAM 因子图是什么关系。写出"未来信息增益"作为一个可加因子的形式。
- [思考题] FIRM 用 stationary LQG 节点控制器把节点 belief 钉成固定值,从而"破历史灾难"。这个"用控制器消除历史依赖"的思想,和 §U4.4 DESPOT"用采样场景限制历史分支"在破历史灾难上有何异同?
§U4.7 Active SLAM 与主动感知 = POMDP 实例 ⭐⭐⭐¶
动机:从"被动建图"到"主动去看"¶
经典 SLAM 是**被动**的:机器人沿给定路径走,顺便把地图建出来。但有个更主动的问题:"下一步该去哪里看,才能最快把地图建准、把自己定准?" 这就是 Active SLAM(主动 SLAM)。它本质是一个决策问题——而且是一个我们已经会的决策问题:POMDP。
对 SLAM 工程师,这是 POMDP 价值的最直接体现:你已经会 belief update(SLAM 的状态估计);Active SLAM 就是在你的 SLAM 之上加一个 POMDP 规划器,决定下一步动作——你的 SLAM 技能直接成为 POMDP 的 belief update 子模块。
理论:Active SLAM 的 POMDP 形式化¶
把 Active SLAM 套进 §U4.1 的七元组:
- 状态 \(s\):机器人位姿 + 地图特征(路标位置等)——和 SLAM 的状态一样,连续高维。
- 动作 \(a\):去哪里(运动指令 / 下一个观测视角)。
- 观测 \(o\):传感器读数(激光 / 视觉特征)——和 SLAM 一样。
- 转移 \(T\)、观测 \(O\):运动模型、传感器模型——和 SLAM 一样。
- belief \(b\):位姿 + 地图的联合后验(SLAM 估出来的那个分布)——就是 SLAM 的输出。
- 奖励 \(R\):信息增益(让 belief 更确定)+ 覆盖(探索新区域)− 碰撞 − 运动代价。
唯一新的东西是**奖励 = 信息增益**——其余全是 SLAM 已有的。
信息增益作为奖励:POMDP 独有的能力¶
"用动作降低 belief 的不确定性"——这是 POMDP 独有、MDP 没有的概念(MDP 假设状态可观测,无所谓"降低不确定性")。怎么量化"belief 更确定"?用协方差矩阵 \(\Sigma\)(或信息矩阵 \(\Sigma^{-1}\))的**标量化**,即最优实验设计(optimal experimental design)的几个准则:
| 准则 | 定义(作用于协方差 \(\Sigma\)) | 几何含义 |
|---|---|---|
| D-optimality | \(\det(\Sigma)\)(或 \(\log\det\)) | 不确定性椭球的**体积** |
| A-optimality | \(\mathrm{tr}(\Sigma)\) | 各方向方差之**和**(椭球半轴平方和) |
| E-optimality | \(\lambda_{\max}(\Sigma)\) | 椭球**最长轴**(最坏方向的不确定性) |
信息增益 = 行动前后这个标量的下降(如 \(\det\Sigma\) 减小)。也可用 Shannon 熵的下降(\(H(b)-\mathbb{E}_o[H(b')]\),即互信息)来度量。Active SLAM 综述(Placed, Strader, Carrillo, Atanasov, Indelman, Carlone, Castellanos, IEEE T-RO 39(3):1686–1705, 2023) 系统梳理了这些度量与方法,是该领域的权威入口。
直觉:机器人选动作时,不只看"到目标多近",还看"去那里能把地图 / 位姿的不确定性降多少"——于是它会主动绕去看一眼信息量大的地方(如未探索区域、能形成回环的地标),而不是闷头直奔目标。
多视角理解:Active SLAM 的三种等价描述 - POMDP 视角:状态不可全观测(位姿 + 地图有不确定),奖励含信息增益——一个标准 POMDP(§U4.1)。 - 最优实验设计视角:每个动作是一次"实验",目标是选实验序列使后验最确定(D/A/E-optimality)——这是统计学的最优实验设计搬到序贯决策上。 - 探索-利用视角:信息增益奖励驱动"探索"(去不确定的地方看),到达 / 覆盖奖励驱动"利用"(完成任务)——POMDP 自动平衡两者(不像 MDP 需要手工加探索噪声)。
本质洞察:Active SLAM 让"SLAM 技能"长出"决策能力",几乎零额外成本。SLAM 工程师已经有了 POMDP 七元组的六个元素(状态、动作、转移、观测、belief update),唯一缺的是"奖励 = 信息增益"和"在 belief 上规划"。一旦补上这两块,被动 SLAM 就升级成主动 SLAM——机器人自己决定"去哪看最划算"。更深一层:这揭示了 SLAM 与 POMDP 本是一体两面——SLAM 是 POMDP 的 belief update 模块(估计),Active SLAM 是把 POMDP 的 planning 模块(决策)也接上。BSP-iSAM(§U4.6)的"在因子图里可微算未来信息增益"正是把这两块无缝缝合的工程实现。
信息增益的次模性:为什么贪心没那么糟¶
§U4.7 思维陷阱说"贪心选单步信息增益最大"会近视。但要给贪心一个公道——信息增益常具**次模性(submodularity)**,这让贪心有理论保证。
次模性(边际递减):信息增益作为"已选测量集合"的函数 \(f\) 常满足 \(f(A\cup\{e\})-f(A)\ge f(B\cup\{e\})-f(B)\)(对 \(A\subseteq B\))——即一次测量的边际信息,随你已测得越多而**递减**。直觉:你已经看清了大半,再看一眼带来的新信息就少了。互信息在很多观测模型下确有此性质。
贪心的近似保证:对**单调 + 次模**的目标,贪心选择(每步挑边际增益最大的)能达到最优的 \((1-1/e)\approx0.63\)(Nemhauser–Wolsey–Fisher 界)。所以"选哪些测量点"这个**集合选择**问题上,贪心不是瞎搞——有可证的近似保证。
但 Active SLAM 不止是集合选择:完整的 Active SLAM 还含**运动代价**和**序贯性**(去某处要走过去、走的路又影响后续能测什么)。这部分不是纯次模集合优化,贪心的 \((1-1/e)\) 保证不直接覆盖——所以仍需 POMDP 多步前瞻来处理"现在收益小、但解锁未来大回环"的情况。
对比性思维:贪心信息增益"在选测量集合上有保证、在序贯路由上会近视"。把 Active SLAM 拆成两层:内层"该测哪些点"(集合选择)——次模性让贪心拿 \((1-1/e)\),够用;外层"该怎么走过去"(序贯路由 + 运动代价)——非次模,贪心会近视、需 POMDP 前瞻。所以"贪心 vs POMDP"不是非黑即白:测量集合选择用贪心(有保证、快),整体路由用 POMDP(处理序贯 + 运动代价)。这也解释了为什么很多 Active SLAM 系统是"贪心选下一最佳观测(next-best-view)+ 有限前瞻"的混合。
Active SLAM 的实用面孔:next-best-view 与 frontier 探索¶
完整 POMDP 求解 Active SLAM 太贵,真实系统多用两类轻量近似,它们都是 Active SLAM 的"短视但实用"版:
- next-best-view(NBV,下一最佳视角):贪心地选"下一个能看到最多新信息的视角 / 位置"——对候选视角各算预期信息增益(如能新观测到多少未知体素 / 能降多少位姿协方差),选最大的去。
ethz-asl/mav_active_3d_planning(无人机主动三维建图)是其干净实现,用 Factory/Strategy 模式把"信息增益度量"和"视角采样"解耦。 - frontier-based exploration(前沿探索):选"已知与未知的边界(frontier)"作为目标去探——简单、鲁棒,是占据栅格建图的经典探索策略。它是 NBV 的特例(信息增益≈前沿大小)。
两者都用贪心 + 有限前瞻而非完整 POMDP——因为完整 POMDP 太贵,而信息增益的次模性(本节)让贪心有可接受的保证。它们是"把 Active SLAM 的 POMDP 理想,工程化成实时可跑"的折中。
对比性思维:NBV/frontier 是 Active SLAM 的"贪心实用版",完整 POMDP 是"理论最优版"。理论上 Active SLAM 是 POMDP,该用多步前瞻最优解;但实时机器人用不起,于是退到 NBV(贪心选最佳视角)/ frontier(去边界)。代价是近视(§U4.7 思维陷阱)——错过"现在收益小、走过去解锁大回环"的机会;收益是实时 + 简单 + 鲁棒,且次模性给贪心兜底。这与 §U4.4 的"完整 POMDP vs DESPOT 采样近似"、U1 的"完整博弈 vs 引导分支"是同一折中模式——理论最优太贵,工程退到有保证的贪心 / 采样近似。选哪个看你的实时预算与对最优性的需求。
算"期望信息增益"为什么贵¶
信息增益 \(\mathrm{IG}(b,a)=H(b)-\mathbb{E}_o[H(\tau(b,a,o))]\) 里有一个对**未来观测求期望**的 \(\mathbb{E}_o\)——这正是它贵的根源。要算这个期望,你得:枚举(或采样)动作 \(a\) 后可能收到的每个观测 \(o\)、对每个 \(o\) 做一次 belief update 得 \(\tau(b,a,o)\)、算其熵、再按 \(\Pr(o\mid b,a)\) 加权。观测空间大 / 连续时,这个期望本身就要采样近似(蒙特卡洛),而每个样本又要一次 belief update(高维 belief 上不便宜)。
多步前瞻更糟:要算"未来两步的信息增益",得对两层观测求期望(嵌套),代价指数上升——这正是 Active SLAM 作为 POMDP 难算的具体来源(信息增益奖励让 belief-MDP 的 rollout 每步都要做这个昂贵的期望)。这也解释了 NBV / frontier(本节)为什么用**单步贪心**:单步信息增益只需一层观测期望,可负担;多步前瞻的嵌套期望则要么近似、要么放弃。
对比性思维:信息增益的"期望未来观测"既是它的威力也是它的负担。普通奖励 \(R(s,a)\) 是即时的、便宜的;信息增益奖励要"预演未来会看到什么、那会让 belief 多确定"——这个前瞻正是它能驱动主动消歧的威力来源,但也让每次评估都要对未来观测求期望(贵)。所以"信息增益奖励"和"实时性"天然矛盾,工程上要么单步贪心(NBV)、要么粗采样近似期望。这是 Active SLAM 区别于普通导航的根本计算负担。
⚠️ 本节常见陷阱¶
💡 概念误区:以为信息增益是唯一奖励 - 现象 / 后果:只用信息增益当奖励,机器人无限探索、永不完成任务(或不回家、不到目标)。 - 根本原因:Active SLAM 的奖励是**多项加权**——信息增益 + 覆盖 − 碰撞 − 运动代价(− 到目标距离,若有任务目标)。只留信息增益就丢了任务性。 - 正确做法:按任务配权重(纯探索可重信息增益;带目标的导航要加到达项)。检验:纯信息增益策略会不会"乐不思蜀"地一直探索?
🧠 思维陷阱:贪心选"单步信息增益最大"就够了 - 现象 / 后果:每步选当前信息增益最大的方向(贪心),结果常陷入近视——错过"现在收益小、但走过去能解锁大回环"的路径。 - 根本原因:信息增益是**序贯**的,贪心忽略了"为未来更大信息增益铺路"。(不过信息增益常有**次模性 submodularity**——边际增益递减,这让贪心有 \((1-1/e)\) 近似保证,所以贪心不是毫无道理,但非最优。) - 正确做法:用 POMDP 规划(多步前瞻)而非单步贪心;若用贪心,知道它靠次模性有近似保证、但会近视。检验:对比贪心 vs 多步规划的探索效率(练习里做)。
💡 概念误区:直接对协方差求 \(\det\) 在高维数值上没问题 - 现象 / 后果:高维协方差 \(\det\) 极小或极大,浮点下溢 / 溢出。 - 根本原因:\(\det\) 是所有特征值之积,高维时数值范围爆炸。 - 正确做法:用 \(\log\det\Sigma=\sum\log\lambda_i\)(对数域,数值稳定),或用信息矩阵的 \(\log\det\)。这也是 D-optimality 实践中常用 \(\log\det\) 的原因。
练习¶
- [A 型·2D 格子 Active SLAM] 在 2D 占据栅格世界实现最简 Active SLAM:(1)占据栅格 + 位姿不确定作为 belief;(2)信息增益(如未知格子的熵减)作为奖励;(3)贪心选信息增益最大的方向。对比贪心 Active 探索 vs 随机游走的地图覆盖速度,验证主动探索更快。
- [A 型·D/A/E 对比] 给一个 2×2 协方差矩阵,分别算 D-(\(\log\det\))、A-(trace)、E-(\(\lambda_{\max}\))optimality,构造一个例子让三者给出不同的"哪个动作信息增益大"的判断。理解三准则各偏好降低哪种不确定性(体积 / 总和 / 最坏方向)。
- [思考题] 为什么信息增益奖励是 POMDP 独有、MDP 里不存在的?请从"MDP 假设状态可观测"出发论证。这也解释了为什么 QMDP(§U4.2,假设一步后全可观测)在 Active SLAM 上会失败——它看不见信息的价值。
§U4.8 DreamerV3 = 摊销 belief:神经世界模型与树搜索的合流 ⭐⭐⭐⭐¶
动机:图像 / 高维连续观测怎么办¶
DESPOT 等(§U4.4/U4.5)是**符号 / 粒子 POMDP 的在线树搜索**——适合状态 / 观测能用符号或粒子表示的问题。但当观测是**图像、点云这类高维连续信号**时,粒子滤波在高维状态上撞维数灾难、符号模型也写不出来。这时另一条路线登场:神经世界模型(neural world model)——用神经网络从高维观测里学一个**紧凑的隐空间 belief 表示 + 隐空间动力学**,在隐空间里"想象"未来、做决策。DreamerV3 是其代表。
理论:RSSM = 摊销 belief¶
DreamerV3 的核心是 RSSM(Recurrent State-Space Model,循环状态空间模型)。它的隐状态分两部分:
- 确定性部分 \(h_t\):一个 GRU(循环网络)的隐状态,携带历史的确定性"记忆"。
- 随机部分 \(z_t\):一个随机隐变量,捕捉当前的不确定性 / 随机性。
合起来 \((h_t, z_t)\) 就是 RSSM 的"隐状态"。关键认识:\((h_t, z_t)\) 就是一个摊销的 belief(amortized belief)——它是神经网络压缩出来的"对世界状态的信念表示"。具体的等价对应:
| RSSM 组件 | POMDP 对应 | 说明 |
|---|---|---|
| 后验 encoder \(q(z_t\mid h_t,x_t)\) | belief update(观测校正) | 从当前观测 \(x_t\) 推断隐状态后验——就是贝叶斯滤波的校正步 |
| 动力学 predictor \(p(z_t\mid h_t)\) | prior predict(运动预测) | 不看观测、只靠历史预测隐状态——就是贝叶斯滤波的预测步 |
| latent imagination rollout | belief 空间策略评估 | 在学到的世界模型里想象未来轨迹、估累积回报 |
| latent 空间的 actor-critic | belief 空间策略优化 | 在隐 belief 上学策略 / 价值——就是在 belief-MDP 上做 RL |
"摊销(amortized)"是关键词:DESPOT 每个决策周期**现场**算一棵树(贵但精确、可解释);RSSM 把"belief update + 规划"摊销进神经网络权重——训练时学好,部署时一次前向就出 belief 和动作(快但黑箱、受训练分布限制)。这正是 §U4.1"belief 是充分统计量"的神经版:RSSM 学了一个**压缩的充分统计量** \((h_t,z_t)\),而非显式维护 \(b(s)\)。
DreamerV3(Hafner et al., 2023, arXiv:2301.04104) 的工程贡献是 robust:用一套固定超参跨上百个差异巨大的任务(从 Atari 到机器人到 Minecraft)都能学好,靠 symlog 变换、free bits、KL 平衡等技巧稳住训练。它证明了"神经世界模型 = 摊销 POMDP 解"这条路线的通用性。
两派合流:DESPOT 树搜索 vs Dreamer 摊销¶
至此,POMDP 的求解出现了两大流派,正在合流:
- DESPOT 派(符号 / 粒子 POMDP 的在线树搜索):每周期现算 belief 树,可解释、有近最优保证,但状态 / 观测要能符号 / 粒子化。
- 神经世界模型派(连续 / 图像 POMDP 的摊销解):学隐空间 belief + 动力学,处理高维连续观测,快,但黑箱、受训练分布限制。
合流点是 Neural-guided 树搜索——BetaZero(Moss, Corso, Caldwell, Kochenderfer, RLC 2024) 是代表:用 AlphaZero 式的**学到的价值 / 策略网络** + belief-state MCTS——学习提供 belief 的价值估计与动作先验(摊销、快),树搜索提供前瞻与保证(可解释、近最优)。这与 §U4.5 的 LeTS-Drive / MAGIC(学引导 DESPOT)、U1 §U1.7 的"神经化分支 / belief MCTS"是同一潮流的不同分支:学习注入先验(减少所需搜索),搜索保留前瞻与可验证性。
多视角理解:RSSM 与 DESPOT 粒子 belief 的对比 - 表示视角:DESPOT 用**粒子**(一组状态样本)显式表示 belief;RSSM 用**神经隐向量** \((h_t,z_t)\) 隐式表示 belief。像 / 不像:都是 belief 的表示,但粒子是 nonparametric(样本多则准、可处理多模态、但高维贵),隐向量是 parametric(紧凑、处理高维图像、但表达力受网络与训练限制)。 - 计算视角:DESPOT 在线现算(用完即弃);RSSM 离线训练 + 在线摊销前向(一次出结果)。 - 适用视角:符号 / 中等状态、要可解释 / 保证 → DESPOT;高维图像 / 像素观测、要端到端 → Dreamer;要兼得 → BetaZero(学习引导树搜索)。
本质洞察:RSSM 是"把 belief update 和 belief 空间规划一起摊销进神经网络"的产物——它和 DESPOT 是同一个 POMDP 的两种解法。回到 §U4.1:POMDP = belief 空间 MDP,求解 = 维护 belief(update)+ 在 belief 上决策(planning)。DESPOT 显式做这两件事(粒子 belief + 树搜索);RSSM 把这两件事都用神经网络学了——encoder/predictor 摊销了 belief update,latent actor-critic 摊销了 belief 空间规划。所以"神经世界模型"不是 POMDP 的替代品,而是 POMDP 的摊销实现。这一认识把 RL/世界模型(Dreamer)与经典 POMDP(DESPOT)统一在同一框架下——它们求解同一个问题(belief 空间 MDP),只是一个现算、一个摊销。BetaZero 的合流正是因为这个底层统一:既然是同一个问题,自然可以"学一部分、搜一部分"。这也是 U0 §6 "经典规控与 RL 处处相通"暗线在 POMDP 上的兑现。
RSSM 怎么训练:KL 就是"惊讶"(= belief 校正的幅度)¶
把"RSSM = 摊销 belief"再钉实一层——看它的训练目标,会发现它字面上在学 belief update。RSSM 训练时优化三件事(变分下界 ELBO 的组成):
- 重构观测:从 \((h_t,z_t)\) 解码回观测 \(x_t\)(保证隐状态编码了观测信息)。
- 预测奖励(及连续性):从隐状态预测奖励(保证隐状态对决策有用)。
- KL 对齐先验与后验:\(D_{\mathrm{KL}}\big[q(z_t\mid h_t,x_t)\,\|\,p(z_t\mid h_t)\big]\)——让"看了观测的后验 \(q\)"与"没看观测的预测先验 \(p\)"尽量接近。
第 3 项是关键。\(p(z_t\mid h_t)\) 是**预测步**(不看观测、只靠历史 \(h_t\) 预测),\(q(z_t\mid h_t,x_t)\) 是**校正步**(看了观测 \(x_t\) 校正)——这正是贝叶斯滤波的预测 + 校正(§U4.1)。而它们之间的 KL 散度就是"惊讶(surprise)":观测把 belief 改动了多少(超出动力学预测的部分)。最小化这个 KL(配 free bits / KL 平衡防塌缩),等于训练动力学 \(p(z\mid h)\) 预测得准——让"没看观测的预测"尽量接近"看了观测的真相"。
latent imagination 为什么只用先验:规划(想象未来)时,未来观测**还没发生**,所以只能用 \(p(z_t\mid h_t)\)(预测步、不校正)滚动——这正是 §U4.4 说的"规划时你不知道未来观测"。Dreamer 在这些想象的隐轨迹上训 actor-critic,就是 belief 空间的策略优化。
本质洞察:RSSM 的 KL 项 = belief update 的"校正幅度",这把世界模型训练和贝叶斯滤波钉成了同一件事。很多人把 RSSM 当成黑箱 RL 组件,但它的训练目标字面上就是贝叶斯滤波:预测先验 \(p(z\mid h)\)、观测后验 \(q(z\mid h,x)\)、KL 度量校正幅度。最小化 KL = 让动力学预测准 = 让"预测的 belief"接近"校正后的 belief"。而想象 rollout 只用先验(无观测可校正),正是"规划时不知道未来观测"的诚实体现。看懂这一层,你就明白 §U4.8 标题"RSSM = 摊销 belief"不是类比而是**字面等式**——Dreamer 在用神经网络学贝叶斯滤波(编码器)+ 学 belief 空间的动态规划(latent actor-critic)。
另一条神经路线:model-free RNN 策略¶
Dreamer 是 model-based(学世界模型 + 在模型里想象规划)。但处理部分可观测还有一条更直接的 model-free 路线:用带记忆的策略网络(RNN / LSTM / Transformer)直接从历史观测映射到动作,不显式学世界模型。
两条路线都在解 POMDP,分野在"要不要显式 belief / 模型": - model-free RNN 策略:RNN 的隐状态**隐式**编码了 belief(它必须记住历史才能在部分可观测下决策)——但这个 belief 是隐式的、为最大化回报而生、不显式重构观测。简单、端到端,但样本效率低、隐 belief 不可解释。 - Dreamer(model-based):显式学 belief(RSSM)+ 世界模型,在想象里规划——样本效率高(可在模型里大量想象)、隐状态有明确语义(重构观测 + 预测),但要学好模型(model bias 风险)。
所以"RNN 策略的隐状态"和"RSSM 的 \((h_t,z_t)\)"都是学到的 belief 表示,区别在前者隐式(只为回报)、后者显式(要重构 + 预测)。
对比性思维:处理部分可观测,神经路线分"隐式记忆(RNN 策略)vs 显式 belief(Dreamer)"。两者都承认"部分可观测需要记忆 / belief",但 RNN 策略让记忆**隐式涌现**(网络自己学着记该记的)、Dreamer 让 belief 显式建模(RSSM 明确重构 + 预测)。隐式的简单端到端但样本贵、不可解释;显式的样本省(想象里训练)、可解释(隐状态有语义)但要学好模型。这又是一组"端到端 vs 结构化"的经典取舍(呼应 U0)——和"DESPOT 树搜索 vs RNN 策略"、"经典 SLAM vs 端到端定位"同源。理解这点,你看任何"部分可观测 + 神经网络"的工作,都能问:它的 belief 是隐式涌现还是显式建模?
两个工程关键:离散隐变量与世界模型精度¶
离散隐变量。DreamerV3 的随机隐变量 \(z_t\) 用的是**分类(categorical)分布**而非高斯——一组离散 one-hot 向量。这不是细节:离散隐变量更适合表示多模态 belief(高斯单峰,分类可多峰),且配合 straight-through 梯度训练更稳。这呼应 §U4.6——高斯 belief 只能单峰,而 RSSM 用离散隐变量绕开了这个限制,能在隐空间表示"世界可能是 A 也可能是 B"的多模态信念。
世界模型精度是命门。摊销 belief 的整条链(encoder + dynamics + 想象规划)都建立在"世界模型预测得准"之上。模型有偏(model bias)时,想象 rollout 会累积误差、把策略带到模型乐观但现实糟糕的地方——这是 model-based 方法的经典风险。DreamerV3 用 symlog 变换、KL 平衡、percentile 回报归一化等一堆技巧稳住模型,才做到跨域鲁棒。
本质洞察:神经摊销 POMDP 的可靠性,最终取决于"学到的世界模型有多准"。DESPOT 用真实模型在线搜索(模型给定、搜索可信);Dreamer 用**学到的**模型在隐空间想象(模型是学的、可能偏)。所以两派的可靠性瓶颈不同——DESPOT 卡在"搜得够不够"(算力),Dreamer 卡在"模型学得准不准"(数据 + 归纳偏置)。这也是为什么安全关键场景偏爱 DESPOT(用真模型、可验证),而数据丰富 + 高维观测场景偏爱 Dreamer(学模型、端到端)。选型时除了 belief 形状,还要问"我信得过学到的模型吗"。
⚠️ 本节常见陷阱¶
💡 概念误区:把 RSSM 的隐状态 \((h_t,z_t)\) 当成"真实状态" - 现象 / 后果:以为 Dreamer 在估计物理状态,试图把 \(z_t\) 解释成具体物理量。 - 根本原因:\((h_t,z_t)\) 是**摊销的 belief 表示**(对状态的信念的神经编码),不是物理状态本身——它编码的是"对状态的信念",且是为预测 / 决策优化的、未必对应可解释物理量。 - 正确做法:把 RSSM 隐状态理解为"belief 的神经压缩"(充分统计量的学习版),而非状态估计。检验:它的维度、含义由网络与任务决定,不对应固定物理量。
🧠 思维陷阱:以为摊销(神经世界模型)一定优于在线搜索(DESPOT) - 现象 / 后果:因为 Dreamer 快、端到端,就认为它全面碾压 DESPOT。 - 根本原因:摊销的代价是**受训练分布限制 + 黑箱 + model bias**——训练分布外性能骤降、决策不可解释 / 难验证、世界模型的偏差会误导规划。安全关键场景往往更看重 DESPOT 的可解释与近最优保证。 - 正确做法:高维图像 + 容忍黑箱 + 有大量训练数据 → Dreamer;符号 / 中等状态 + 要可解释 / 可验证 → DESPOT;想兼得 → BetaZero。没有普遍更优,看场景。
💡 概念误区:以为"世界模型"和"POMDP"是两个不相干的领域 - 现象 / 后果:把 RL 的世界模型和经典 POMDP 当成割裂的两套理论分别学。 - 根本原因:世界模型**就是** POMDP 的摊销解——RSSM 的 encoder = belief update、latent imagination = belief 空间策略评估。它们是同一框架。 - 正确做法:用"belief 空间 MDP"这个统一视角看待两者——这也是 BetaZero 能把它们接起来的根本原因。
练习¶
- [A 型·摊销 vs 现算] 概念对比实验:在一个小 POMDP 上,(a)用 DESPOT 式在线规划(每步现算);(b)训练一个小网络模仿 DESPOT 的输出(摊销)。对比在训练分布内 / 外的性能与单步耗时。验证摊销快但训练分布外退化。
- [B 型·RSSM 结构精读] 阅读 DreamerV3 的 RSSM 实现,标出哪部分对应 belief update 的"预测步"(dynamics predictor \(p(z_t\mid h_t)\))、哪部分对应"校正步"(encoder \(q(z_t\mid h_t,x_t)\))。理解 \((h_t,z_t)\) 为什么是"摊销 belief"。
- [思考题] RSSM 的 \((h_t,z_t)\) 和 DESPOT 的粒子 belief 都是 belief 的表示。请对比两者优劣:RSSM 在什么场景胜出(提示:高维图像观测)?DESPOT 在什么场景胜出(提示:可解释 / 保证 / 多模态)?BetaZero 如何取两者之长设计混合架构?
完整实现精读:从公式到可运行代码¶
前面的算法都用 Tiger 问题作例子。这里给出可运行、已数值核对的 Python 实现,把 §U4.1–U4.4 的核心(belief update、QMDP、在线 DESPOT 式规划、粒子 belief、信息增益)落成代码。所有数值都实跑核对过。
实现一:Tiger POMDP 与 belief update¶
先把 Tiger 问题定义清楚,再实现 §U4.1 的 belief update(贝叶斯滤波)。
import numpy as np
# 状态: 0=TL(虎在左), 1=TR(虎在右); 动作: 0=listen, 1=open-left, 2=open-right
# 观测: 0=hear-left, 1=hear-right
LISTEN, OL, OR = 0, 1, 2
TL, TR = 0, 1
ACC = 0.85 # listen 的准确率 O(听对|listen)
GAMMA = 0.95
def reward(s, a):
if a == LISTEN: return -1.0
if a == OL: return -100.0 if s == TL else 10.0 # 开左门: 虎在左=被吃
return -100.0 if s == TR else 10.0 # 开右门: 虎在右=被吃
def obs_prob(o, s2, a):
"""O(o | s', a): 仅 listen 有信息; open 后观测无信息(0.5)。"""
if a == LISTEN:
if s2 == TL: return ACC if o == 0 else 1 - ACC
else: return (1 - ACC) if o == 0 else ACC
return 0.5
def belief_update(b, a, o):
"""§U4.1 的贝叶斯滤波: b'(s') = η O(o|s',a) Σ_s T(s'|s,a) b(s)。
Tiger: listen 不改状态(T=I); open 重置为均匀。"""
nb = np.zeros(2)
for s2 in range(2):
pred = b[s2] if a == LISTEN else 0.5 # 运动预测(listen=恒等; open=重置)
nb[s2] = obs_prob(o, s2, a) * pred # 观测校正
nb /= nb.sum() # 归一化(必须全部算完再除!)
return nb
# 验证(数值已核对): 从均匀 belief 连听 3 次 hear-left
b = np.array([0.5, 0.5])
for i in range(3):
b = belief_update(b, LISTEN, 0)
print(f"听{i+1}次 hear-left: b(TL)={b[0]:.4f}")
# 输出: 0.8500 -> 0.9698 -> 0.9945 (向 TL 收敛, 但永不到 1)
逐块对应 §U4.1:pred 是运动预测(listen 状态不变所以 pred=b[s2],open 重置所以 pred=0.5);obs_prob(o,s2,a)*pred 是观测校正;最后 nb /= nb.sum() 是归一化 \(\eta\)——注意必须等所有 \(s'\) 的未归一化值都算完再统一除(陷阱见 §U4.1)。验证输出 \(0.85\to0.97\to0.9945\) 印证了"观测越多越确定、但因观测不完美永不到 1"。
实现二:QMDP(看清它的近似本质)¶
QMDP 用全可观测 MDP 的 Q 值当 α-vector。实现它并观察其真实行为(§U4.2 已澄清:它会 listen,但低估持续消歧的价值)。
def solve_mdp_values(n_iter=2000):
"""解全可观测 Tiger MDP 的 V_MDP(s)。listen 不改状态; open 重置(下个状态均匀)。"""
V = np.zeros(2)
for _ in range(n_iter):
Vn = np.zeros(2)
for s in range(2):
q_listen = reward(s, LISTEN) + GAMMA * V[s]
q_open = reward(s, OL) + GAMMA * 0.5 * (V[0] + V[1]) # 开门后重置
q_open2 = reward(s, OR) + GAMMA * 0.5 * (V[0] + V[1])
Vn[s] = max(q_listen, q_open, q_open2)
if np.max(np.abs(Vn - V)) < 1e-10:
return Vn
V = Vn
return V
def qmdp_action(b, V):
"""Q_MDP(s,a) 当 α-vector, 决策 a* = argmax_a Σ_s b(s) Q_MDP(s,a)。"""
def Q(s, a):
if a == LISTEN: return reward(s, LISTEN) + GAMMA * V[s]
return reward(s, a) + GAMMA * 0.5 * (V[0] + V[1])
qa = [sum(b[s] * Q(s, a) for s in range(2)) for a in range(3)]
return int(np.argmax(qa)), qa
# 验证(数值已核对):
V = solve_mdp_values() # V_MDP(TL)=V_MDP(TR)=200.0
# Q_MDP: listen=189, open-safe=200, open-tiger=90
for p in [0.5, 0.85, 0.97, 0.99]:
a, _ = qmdp_action(np.array([p, 1 - p]), V)
print(f"b(TL)={p}: QMDP 选 {['listen','open-L','open-R'][a]}")
# 输出: 0.5->listen, 0.85->listen, 0.97->open-R, 0.99->open-R
# 即 QMDP 从均匀听约 2 次(0.5->0.85->0.97)就开门 —— 它确实会 listen,
# 但因"假设一步后全可观测", 系统性低估了"该多听几次"(消歧不足)。
💡 概念误区(实现层面):以为 QMDP 在 Tiger 上从不 listen。许多二手资料这么说,但实跑可见 QMDP 在不确定 belief 上**会 listen**(因为 \(Q_{\text{MDP}}(s,\text{listen})=189\) 被"下一步全可观测后拿满分 200"的高续值抬高了)。它真正的短板是**低估消歧要做多久**——把多步信息收集当成"一步就够",于是在更强歧义的问题上过早行动。写教学代码时务必实跑验证、不要照搬"QMDP 不 listen"的说法。
实现三:DESPOT 式在线前向搜索¶
实现 §U4.4 的核心思想:从当前 belief 采样 \(K\) 个起始状态(场景),对每个动作做前向仿真 + rollout,选平均回报最高的动作。这是 DESPOT 思想的极简版(省略了 anytime 上下界与正则化)。
rng = np.random.default_rng(0)
def step(s, a, r):
"""确定化一步: 给定随机数 r∈[0,1), 返回 (下个状态, 观测, 奖励)。
这就是 §U4.4 '场景=起始状态+随机数串' 里单步的确定化模拟。"""
if a == LISTEN:
o = s if r < ACC else (1 - s) # 以 ACC 概率听对
return s, o, reward(s, a) # listen 不改状态
ns = 0 if r < 0.5 else 1 # open 重置
return ns, -1, reward(s, a)
def rollout(s, depth):
"""简单 rollout 策略(估叶子价值): 还有深度就 listen, 否则开门(知道 s 则拿+10)。"""
if depth <= 0:
return 10.0 # 知道状态时开安全门的即时回报
r = rng.random()
_, _, rew = step(s, LISTEN, r)
return rew + GAMMA * rollout(s, depth - 1)
def despot_plan(b, K=200, depth=4):
"""DESPOT 式: 采 K 个场景起始状态, 每个动作前向仿真+rollout, 选最优首动作。"""
starts = rng.choice(2, size=K, p=b) # 从 belief 采 K 个起始状态(破维数灾难)
best_a, best_v = None, -1e18
for a in range(3):
tot = 0.0
for s0 in starts: # K 个场景平均(蒙特卡洛估策略价值)
r = rng.random()
ns, o, rew = step(s0, a, r)
cont = GAMMA * rollout(ns, depth - 1) if a == LISTEN else 0.0
tot += rew + cont
v = tot / K
if v > best_v:
best_v, best_a = v, a
return best_a, best_v
# 验证(数值已核对):
for p in [0.5, 0.85, 0.99]:
a, v = despot_plan(np.array([p, 1 - p]))
print(f"b(TL)={p}: DESPOT式 选 {['listen','open-L','open-R'][a]} (val={v:.1f})")
# 输出: 0.5->listen, 0.85->listen, 0.99->open-R (不确定时消歧, 确定后行动)
逐块对应 §U4.4:starts = rng.choice(2, size=K, p=b) 是"从 belief 采 \(K\) 个起始状态"(破维数灾难);step(s,a,r) 用随机数 r 做确定化一步(场景的核心);对每个动作在 \(K\) 个场景上平均回报,是"用 \(K\) 个采样场景估策略价值"。这个极简版没有 DESPOT 的 anytime 上下界引导与 R-DESPOT 正则化,但抓住了"采样场景 + 前向仿真选动作"的骨架。验证显示它在 belief 不确定时选 listen(消歧)、确定后(\(p=0.99\))开门——正确的 POMDP 行为。
实现四:粒子 belief(处理大 / 连续状态)¶
DESPOT/POMCP 用粒子隐式表示 belief(§U4.4)。实现粒子滤波式的 belief 更新(SIR:重要性加权 + 重采样)。
def particle_update(particles, a, o, n_out=None):
"""粒子 belief 更新(SIR): 按观测似然加权, 重采样。
particles: 状态样本数组; 返回更新后的粒子集。"""
n_out = n_out or len(particles)
if a == LISTEN:
w = np.array([obs_prob(o, int(s), a) for s in particles]) # 观测似然加权
else:
w = np.ones(len(particles)) # open 后无信息
w = w / w.sum()
idx = rng.choice(len(particles), size=n_out, p=w) # 按权重重采样
return particles[idx]
# 验证(数值已核对): 1000 粒子从均匀, 听 3 次 hear-left
particles = rng.choice(2, size=1000, p=[0.5, 0.5])
for i in range(3):
particles = particle_update(particles, LISTEN, TL)
print(f"听{i+1}次: P(TL)≈{np.mean(particles == TL):.3f}")
# 输出: ≈0.845 -> ≈0.968 -> ≈0.994 (与实现一的解析值 0.85/0.97/0.994 吻合)
💡 编程陷阱:粒子滤波每步都重采样,或从不监控有效粒子数 - 现象 / 后果:每步无条件重采样会过早损失粒子多样性(许多粒子变成同一个值),belief 近似退化;反之从不重采样,则少数粒子很快占据几乎全部权重(权重退化),同样失真。 - 错误代码:
particles = particle_update(particles, a, o)里每步都rng.choice(...)重采样,且不检查权重是否已经很集中。 - 正确写法:先算**有效粒子数** \(\mathrm{ESS}=1/\sum_i w_i^2\),仅当 \(\mathrm{ESS}\) 低于阈值(如 \(N/2\))时才重采样;重采样后若粒子塌缩,加 roughening(给粒子注入小噪声)恢复多样性。 - 根本原因:重采样是把"权重不均"换成"样本不均"——用早了损失多样性、用晚了权重退化,须用 ESS 触发、在两者间平衡。 - 检验方法:打印每步 ESS 曲线;ESS 持续接近 1(只剩一个有效粒子)说明退化,需增加粒子数或加 roughening。注意感知混淆区粒子天然分成多簇是多峰、不是退化(§U4.1)。对比性思维:粒子 belief vs 解析 belief。实现一显式存 \(b=(b(\text{TL}),b(\text{TR}))\)(解析、精确,但只适合小离散状态);实现四用 1000 个粒子近似同一个 belief(近似、有采样噪声,但**与状态空间大小脱钩**——百万状态也是这套代码)。验证显示粒子估计(0.845/0.968/0.994)与解析值(0.85/0.97/0.994)吻合到采样精度。这正是 DESPOT/POMCP 能处理大状态空间的原因:用粒子代替显式分布。代价是粒子贫化(少数粒子占大权重时需重采样)与采样噪声。
实现五:信息增益(Active SLAM 的奖励)¶
§U4.7 的核心是"信息增益作为奖励"。实现熵减形式的信息增益。
def entropy(b):
"""belief 的 Shannon 熵(bit)。"""
b = np.clip(b, 1e-12, 1.0)
return -np.sum(b * np.log2(b))
def expected_info_gain(b, a):
"""执行动作 a 的期望信息增益 = H(b) - E_o[H(b')](即互信息)。"""
H_prior = entropy(b)
H_post = 0.0
for o in range(2):
p_o = sum(obs_prob(o, s, a) * b[s] for s in range(2)) # P(o|b,a)
if p_o < 1e-12:
continue
nb = belief_update(b, a, o)
H_post += p_o * entropy(nb)
return H_prior - H_post
# 验证(数值已核对): 均匀 belief 下 listen 的信息增益
b = np.array([0.5, 0.5])
print(f"listen 信息增益 = {expected_info_gain(b, LISTEN):.3f} bit")
# 输出: 0.390 bit (H=1.0 bit -> E[H']=0.610 bit, listen 降低 0.39 bit 不确定性)
print(f"open-left 信息增益 = {expected_info_gain(b, OL):.3f} bit")
# 输出: 0.000 bit (开门后 belief 重置为均匀, 无信息增益 —— 开门不消歧)
逐块对应 §U4.7:entropy(b) 是 belief 的不确定性度量;expected_info_gain 是"行动前熵 − 行动后期望熵"(互信息)。验证显示 listen 的信息增益 0.39 bit(消歧),open 的信息增益 0(开门重置、不消歧)——这正是 Active SLAM 里"信息增益奖励驱动机器人去消歧"的微观机制。把这个信息增益加进奖励,就把被动滤波升级成了主动感知。
实现六:格子世界主动定位(感知混淆 → 移动消歧)¶
把"belief 多峰、原地观测不消歧、必须移动消歧"(§U4.1 思维陷阱、§U4.7)落成一个完整可跑的小例子。环形走廊 6 格,其中**格 0 与格 3 特征相同**(感知混淆),机器人初始不知在哪。
import numpy as np
N = 6
feat = np.array([0, 1, 2, 0, 4, 5]) # 格0与格3特征都是0 -> 感知混淆
def obs_model(o, s): # P(o|s): 准确率0.8, 错时均匀到其他特征
return 0.8 if o == feat[s] else (1 - 0.8) / (len(set(feat)) - 1)
def bel_update(b, a, o): # 环形移动 a(+1/-1) + 观测校正
nb = np.zeros(N)
for s2 in range(N):
nb[s2] = obs_model(o, s2) * b[(s2 - a) % N] # 预测(移动)+校正(观测)
return nb / nb.sum()
def entropy(b):
b = np.clip(b, 1e-12, 1.0)
return -np.sum(b * np.log2(b))
true_s = 3
b = np.ones(N) / N # 初始均匀, 熵=2.585 bit(全不确定)
# (1) 原地观测: 看到格3的特征0, 但格0也是特征0 -> belief 双峰, 不消歧
o = feat[true_s]
b = bel_update(b, 0, o)
print("原地观测后:", np.round(b, 3), "熵=%.3f" % entropy(b))
# -> [0.444 0.028 0.028 0.444 ...] P(0)=P(3)=0.444 双峰! 熵=1.614 (观测无法消歧)
# (2) 移动一步再观测: 格3->格4(特征4 唯一), 而"假设在格0"会到格1(特征1) -> 可区分
true_s = (true_s + 1) % N # 真值到格4
o = feat[true_s]
b = bel_update(b, 1, o)
print("前进+观测后:", np.round(b, 3), "熵=%.3f" % entropy(b))
# -> [... 0.928 ...] P(4)=0.928 单峰! 熵=0.456 (移动消歧成功)
逐块对应 §U4.1/U4.7:第(1)步原地观测后 belief 双峰**于 \(\{0,3\}\)(熵 1.614)——因为格 0 和格 3 特征相同,观测对它俩**无区分力,再多原地观测也消不了歧(§U4.1 思维陷阱"观测越多不一定越确定"的活例)。第(2)步**移动**到一个能区分的位置(格 4 特征唯一),belief 立刻收敛到单峰(熵降到 0.456)——这正是 §U4.7 说的"感知混淆区必须靠动作(移动到可区分处)消歧"。把"选能最大降熵的移动"作为策略,就是最简的主动定位 / Active SLAM。
对比性思维:这个例子把"原地观测 vs 移动消歧"的差别量化了。原地观测:熵 \(2.585\to1.614\)(降了,但卡在双峰,因为观测对混淆格无区分力);移动一步再观测:熵 \(1.614\to0.456\)(一举消歧)。数字铁证:在感知混淆下,降低不确定性的关键不是"多观测"而是"移动到能区分的地方"——这是被动滤波(只更新 belief)与主动感知(规划动作来降不确定性)的分水岭,也是 Active SLAM(§U4.7)存在的理由。
本质洞察:六个实现串起了 POMDP 的完整骨架。实现一(belief update)= SLAM 工程师已会的估计;实现二(QMDP)= 最廉价的 belief 上决策(信息盲的极限);实现三(DESPOT 式)= 在 belief 上做前向搜索决策(看得见信息价值);实现四(粒子 belief)= 让前三者能扩展到大状态空间;实现五(信息增益)= 把"获取信息"变成可优化的奖励;实现六(格子主动定位)= 把前几块拼成"感知混淆到移动消歧"的完整主动感知小例(Active SLAM 雏形)。把它们拼起来——粒子 belief(实现四)+ DESPOT 式规划(实现三)+ 信息增益奖励(实现五)——就是一个能在大状态空间做主动感知的 POMDP 规划器骨架,对应 §U4.4/§U4.7 的工程形态。
进阶专题¶
正文给了主线与各方法思想,这里对几个值得深入的点展开——既加深主线理解,也是研究 / 工程会真正碰到的细节。
进阶专题一:belief 空间的几何 ⭐⭐⭐¶
§U4.1 说 belief 活在 \(|S|-1\) 维单纯形 \(\Delta^{|S|-1}\) 上,§U4.2 说值函数在其上 PWLC。把这个几何看清,对理解所有 POMDP 方法都有帮助。
单纯形(simplex):\(|S|\) 个状态的 belief 是一个非负、和为 1 的向量,所有这样的向量构成单纯形。2 状态时是一条线段(\(b(s_1)\in[0,1]\));3 状态时是一个三角形;\(n\) 状态时是 \(n-1\) 维单纯形。顶点**是确定 belief(某状态概率为 1)——最确定;**中心(均匀分布)——最不确定。
值函数的几何:\(V^*(b)=\max_\alpha\alpha\cdot b\) 是单纯形上方一族超平面的上包络——一个凸的分段线性"穹顶"。顶点处穹顶最高(确定时价值最高),中心处最低(不确定时价值最低)。每个 α-vector 罩住单纯形的一块区域;区域边界是相邻超平面的交线。求解 POMDP = 找出这个穹顶(哪些 α-vector、各罩哪块)。
可达 belief 子流形:从 \(b_0\) 出发,belief update 把 belief 映到新点。所有可达 belief 构成单纯形里的一个**子集**——通常是极低维的(远小于 \(|S|-1\) 维)。这是点基方法(§U4.3)的命根:只在这个低维可达子集上备份,而非整个单纯形。
本质洞察:POMDP 的所有近似方法都是"如何不在整个单纯形上较劲"。精确求解要刻画整个单纯形上的穹顶(指数多 α-vector);点基方法只刻画可达子流形上的穹顶(点数线性);DESPOT 只刻画"从 \(b_0\) 出发有限步可达"的更小局部;BSP 假设 belief 是高斯、把单纯形换成低维参数空间 \((\mu,\Sigma)\)。看懂单纯形几何,你就看懂了所有方法都在回答同一个问题——"belief 空间这么大,我到底要在哪一小块上求解?"
进阶专题二:两个 curse 的精确刻画 ⭐⭐⭐¶
§U4.2/§U4.4 反复提"维数灾难"和"历史灾难",这里精确刻画并对照各方法如何破解。
维数灾难(curse of dimensionality):belief 是 \(|S|\) 维连续向量。状态空间越大,belief 空间维度越高,覆盖它所需的资源(α-vector 数、点数、粒子数)随维度增长。根源:状态多。
历史灾难(curse of history):深度 \(D\) 的完整 belief 树有 \(O(|A|^D|Z|^D)\) 个节点——动作-观测历史随深度指数膨胀。值函数的 α-vector 数也随视界以 \(|\Gamma|^{|\Omega|}\) 膨胀。根源:历史(动作-观测序列)多。
各方法的破解对照:
| 方法 | 破维数灾难 | 破历史灾难 |
|---|---|---|
| 精确求解 | ✗(整个单纯形) | ✗(所有历史) |
| 点基(SARSOP) | ✓(只在可达 belief 点) | 部分(仍枚举观测备份) |
| POMCP | ✓(粒子,与 $ | S |
| DESPOT | ✓(采样 \(K\) 个起始状态) | ✓(只留 \(K\) 场景的观测分支) |
| BSP(高斯) | ✓(高斯参数 \((\mu,\Sigma)\),维度多项式) | ✓(FIRM 用 stationary 控制器钉死节点 belief) |
| Dreamer/RSSM | ✓(神经隐向量压缩) | ✓(摊销进网络,不显式展开历史) |
对比性思维:两个 curse 要分开打、且常用同一招(采样)打两个。很多人把 POMDP 的难笼统归为"状态空间大",但**历史灾难(观测序列多)往往比维数灾难更致命**——即使状态不多,长视界 + 多观测也会让 belief 树爆炸。DESPOT 的精妙在于用"采样"一招同时打两个:采样起始状态破维数灾难、采样观测(只留场景经历的)破历史灾难。记住"两个 curse 分开看、采样可同治",你评估任何 POMDP 方法时就知道该问"它怎么破维数、怎么破历史"。
进阶专题三:连续 POMDP 与 POMCPOW 的 Progressive Widening ⭐⭐⭐⭐¶
正文的方法多针对离散动作 / 观测。但很多机器人问题动作和观测都**连续**(连续控制量、连续传感读数)。连续观测尤其麻烦:每个观测几乎都不同,belief 树的观测分支无限多、每个分支只有一个粒子——树退化、无法估值。
POMCPOW(Sunberg–Kochenderfer, ICAPS 2018,Stanford SISL) 用 Progressive Widening(渐进加宽,PW) 解决:限制每个节点的子节点数随访问次数缓慢增长(\(\#\text{children}\le k\cdot N^\beta\))——而非为每个新观测都建新分支。直觉:访问少时只展开少数动作 / 观测,访问多了才逐渐加宽。这让连续空间的树保持"每个分支有足够样本支撑",避免退化。配套的 PFT-DPW(particle filter tree with double PW)同时对动作和观测加宽。
本质洞察:连续观测的难,难在"每个观测都不同→分支无限→树退化",PW 用"加宽速度受控"治它。离散观测时,\(|Z|\) 个观测分支各自被多个场景 / 粒子支撑,能估值;连续观测时,每个观测唯一、分支无限、每分支一个粒子,估值方差无穷大。Progressive Widening 的核心思想是"不要急着加宽——访问次数不够就不开新分支",让有限的样本集中在少数分支上、每个分支有统计意义。这与 DESPOT 用 \(K\) 个固定场景限制观测分支是同一目标(控制观测分支数)的不同手段——DESPOT 用固定场景集、POMCPOW 用受控加宽。
进阶专题四:近似谱与上下界 ⭐⭐⭐¶
POMDP 的近似方法形成一个"快—准"谱,且很多方法成对维护值函数的上下界。把这个谱理清,便于选型。
近似谱(从快糙到慢准): - QMDP:最快最糙。假设一步后全可观测,系统性低估持续消歧价值(§U4.2)。 - FIB(Fast Informed Bound):比 QMDP 略好的上界——它部分考虑观测,给出比 QMDP 更紧的上界。 - 点基(SARSOP):离线、中等规模、\(\epsilon\)-最优。在可达 belief 上备份。 - 在线树搜索(DESPOT/POMCP):大规模、实时、output-sensitive。每周期现算。
上下界配对:很多算法同时维护 \(V^*\) 的上界和下界,用 gap 引导搜索、判停: - 下界:一组 α-vector(每个对应真实可执行计划)给 \(V^*\) 下界(§U4.3)。或一个简单 rollout 策略的价值。 - 上界:QMDP / FIB 给 \(V^*\) 上界(它们高估,因为假设了更多可观测性)。HSVI/SARSOP 用点凸包做上界。 - 用法:gap = 上界 − 下界。gap 大的 belief 优先备份(HSVI/SARSOP)或探索(DESPOT);gap 收窄到阈值就停(有界次优保证)。
对比性思维:QMDP 既是"廉价策略"又是"上界"——一身两用。同一个 \(Q_{\text{MDP}}\),当策略用(取 argmax)是个信息盲的廉价控制器;当界用(\(\max_a\sum b(s)Q_{\text{MDP}}(s,a)\))是 \(V^*\) 的一个上界(因为全可观测假设只会高估价值)。这个"上界"身份在 DESPOT/HSVI 里很有用——它给搜索提供乐观估计、引导探索。理解"同一个近似既能当策略又能当界",是读懂 POMDP 求解器(上下界引导搜索)的关键。
进阶专题五:Tiger 数值走查(belief 演化 + QMDP 值)⭐⭐¶
把 Tiger 的关键数值摆出来,对照前面代码,建立量化直觉(数值均已核对)。
belief 演化(从均匀连听 hear-left,准确率 0.85):
| 听的次数 | \(b(\text{TL})\) | 解读 |
|---|---|---|
| 0(均匀) | 0.5000 | 完全不确定 |
| 1 | 0.8500 | 一次观测,odds 变 \(0.85/0.15\approx5.67\) |
| 2 | 0.9698 | odds 累乘 \(5.67^2\approx32\) |
| 3 | 0.9945 | odds \(5.67^3\approx182\),趋近但永不到 1 |
每听一次,对数 odds 加 \(\log(0.85/0.15)\)——belief 沿单纯形向 TL 顶点指数逼近、但因观测不完美(0.85<1)永不到达顶点。
QMDP 关键值(\(\gamma=0.95\),奖励 listen \(-1\) / 开对 \(+10\) / 开错 \(-100\)):全可观测 MDP 值 \(V_{\text{MDP}}=200\)(\(=10/(1-0.95)\),反复开安全门)。\(Q_{\text{MDP}}\):listen \(=-1+0.95\times200=189\);开安全门 \(=10+0.95\times200=200\);开虎门 \(=-100+0.95\times200=90\)。QMDP 在均匀 belief 选 listen(\(189>\) 开门的 \(0.5\times200+0.5\times90=145\) 但 listen 189 更高),听约 2 次到 \(b(\text{TL})\approx0.97\) 后开门(\(0.97\times200+0.03\times90\approx196.7>189\))。
本质洞察:Tiger 的数值揭示"belief 沿对数 odds 线性移动、值函数沿 belief 凸变化"。belief 更新在对数 odds 域是线性的(每次观测加固定增量),所以在概率域看是向顶点指数逼近。而价值随 belief 凸变化(顶点高、中心低)。POMDP 决策的本质就是这两件事的相互作用:观测把 belief 推向某顶点(更确定→价值更高),但推动需要代价(listen 的 \(-1\))和时间(多步)——何时停止推动转而行动,由"再推一步的信息价值"vs"现在行动的期望收益"权衡决定。
进阶专题六:POMDP 与强化学习的关系 ⭐⭐⭐¶
U0 §6 埋了"经典规控与 RL 处处相通"的暗线。POMDP 与 RL 的连接点尤其深。
POMDP = 带 belief 状态的 MDP,RL = 不知道模型的 MDP。两者正交又互补: - POMDP(本章):知道模型(\(T,O,R\) 已知),但**状态不可观测**——难在"在 belief 上规划"。 - RL:状态可观测(标准 RL),但**不知道模型**——难在"从交互学策略 / 价值"。 - POMDP-RL(部分可观测 RL):两难叠加——状态不可观测 + 模型未知。这是最难也最现实的设定。
连接点: - belief 状态 = RL 的"记忆":部分可观测 RL 里,策略需要记忆(用 RNN/Transformer 编码历史)——这个记忆**就是学到的 belief 表示**。DreamerV3 的 RSSM(§U4.8)正是把 belief 显式学出来。 - POMCP/DESPOT 的 rollout = RL 的 Monte Carlo 估值:树搜索的 rollout 估叶子价值,和 RL 的蒙特卡洛回报估计是同一件事。 - BetaZero/MAGIC/LeTS-Drive = POMDP × RL 的混合:用 RL/学习提供 belief 的价值 / 策略先验,用 POMDP 树搜索提供前瞻——同 §U4.8 的合流。
对比性思维:POMDP 和 RL 的"未知"在不同地方。新手常混淆 POMDP 和 RL。区分关键:POMDP 的未知是"状态"(模型已知、状态看不清),RL 的未知是"模型"(状态看得见、转移 / 奖励不知道)。POMDP 用贝叶斯滤波处理状态未知(要模型),RL 用试错处理模型未知(不要模型)。现实机器人常两者都未知(部分可观测 + 模型不准)——这时要么"学一个模型再做 POMDP 规划"(model-based,如 Dreamer),要么"用带记忆的策略直接学"(model-free RNN policy)。理解这个区分,你就不会把"POMDP"和"RL"当对立选项,而看到它们处理的是不确定性的不同侧面。
进阶专题七:Dec-POMDP 与多机器人 ⭐⭐⭐⭐¶
单机器人 POMDP 已经很难,多机器人协作在部分可观测下更难——这是 Dec-POMDP(Decentralized POMDP,去中心化 POMDP)。
难在哪:每个机器人只有自己的局部观测,无法共享 belief(通信受限),却要协同决策。每个 agent 维护自己的局部信息、推断他人可能的观测和行动。Dec-POMDP 的有限视界求解是 NEXP-complete——比单 POMDP 的 PSPACE 还高一个量级,极难。
实用路线: - 集中训练、分散执行(CTDE):训练时假设能看到全局(算 belief),执行时各 agent 只用局部观测——多智能体 RL 的主流范式。 - 显式通信:用通信动作共享部分信息,把 Dec-POMDP 拉近单 POMDP(通信充分时退化为集中式)。 - 结构假设:假设 agent 间弱耦合 / 可分解,降低复杂度。
本质洞察:Dec-POMDP 的爆炸来自"对他人信念的信念"(高阶信念)。单 POMDP 你维护"对状态的信念";Dec-POMDP 你还要维护"对队友观测 / 信念的信念"——而队友也在维护"对你的信念",形成无穷递归的高阶信念。NEXP 的复杂度正源于此。实用方法都在回避高阶信念:CTDE 训练时用全局信息绕开(执行时各管各)、通信用共享信息压平递归。这也是为什么多机器人 SLAM / 协作至今仍是开放难题——一旦通信受限、不能共享 belief,高阶信念的递归就无法回避。
进阶专题八:风险敏感 POMDP(接 U5)⭐⭐⭐⭐¶
本章的 POMDP 默认最大化**期望**累积奖励。但和 U1/U3 一样,期望会被罕见灾难平均掉——在安全关键场景,你可能更在乎"最坏情况下 belief 演化有多糟"。这就是**风险敏感 POMDP**,是 U5 的方向。
两种风险来源在 POMDP 里叠加: - 状态不确定(aleatoric + epistemic,本章核心):你不知道真实状态,belief 是分布。 - 回报的尾部风险(U5 核心):即使给定 belief,未来回报也有分布,你可能在乎其尾部(CVaR)。
做法:把 belief-MDP 的目标从"期望回报"换成"CVaR 回报"或其他风险度量。Rockafellar–Uryasev 形式(U3 进阶十)\(\mathrm{CVaR}_\alpha=\min_t\{t+\frac1{1-\alpha}\mathbb{E}[(L-t)_+]\}\) 仍可用,只是期望现在是"对 belief + 未来随机性"取的。难点:风险度量破坏了 belief 作为充分统计量的某些性质(CVaR 不满足 belief 上的动态规划可分解性,需要增广状态)。
对比性思维:POMDP 的"不确定"和 U5 的"风险"是两件事,可叠加。POMDP 处理"我不知道当前状态"(认知不确定),U5/CVaR 处理"未来回报的尾部有多糟"(风险态度)。一个风险敏感 POMDP 同时面对两者:在不确定的 belief 上、用风险敏感目标决策。这也呼应 U0 五安全谱——U4(感知端认知不确定)与 U5(尾部风险)正交,可组合成"风险敏感的 belief 空间规划"。这是当前 POMDP 研究的活跃方向,也是 Part-U 收官(U5)要展开的。
进阶专题九:MOMDP——混合可观测降维 ⭐⭐⭐¶
很多机器人问题里,状态的**一部分可观测、一部分不可观测**——比如机器人自己的位姿可观测(有里程计),但环境里某物体的类别 / 意图不可观测。把整个状态都当 belief 浪费:可观测部分的"belief"是个 delta 分布(就是它本身),维护它纯属冗余。
MOMDP(Mixed-Observability MDP,混合可观测 MDP) 用 factored 模型把状态拆成可观测分量 \(x\) 和不可观测分量 \(y\):\(s=(x,y)\)。于是 belief 只需对 \(y\) 维护(\(x\) 已知),belief 空间从对整个 \(s\) 的单纯形,降到"\(x\) 已知条件下对 \(y\) 的单纯形"——维度大降。SARSOP 的一个重要扩展就是利用 mixed observability(Ong-Png-Hsu-Lee 等),在很多机器人任务上把可解规模提了一大截。
本质洞察:MOMDP 是"只对真正看不清的部分维护 belief"——把维数灾难砍到不可观测子空间。维数灾难来自 belief 空间维度 = 状态数。但如果一半状态可观测,对它们维护 belief 是浪费(delta 分布)。MOMDP 把 belief 限制在不可观测子空间上——可观测部分当普通 MDP 状态、只对不可观测部分做 POMDP。这是"别为已知的东西付不确定性的代价"的工程智慧,也是把 POMDP 用上真实机器人(位姿常可观测、只有语义 / 意图不可观测)的关键降维手段。自驾里"自车状态可观测、他车意图不可观测"正是 MOMDP 结构(呼应 U1)。
进阶专题十:belief-space MPC——把 belief 纳入 MPC 状态 ⭐⭐⭐¶
U2/U3 的 MPC 在**状态**上滚动优化。当状态不可观测时,一个自然想法:把 belief 当作 MPC 的状态,在 belief 上做滚动时域优化——这就是 belief-space MPC(与 §U4.6 的 BSP 紧密相关)。
做法:MPC 的预测模型用 belief 动态(belief update + 预测观测,常假设高斯 belief 或 ML 观测以保可解),代价函数含"belief 不确定性"项(如 \(\mathrm{tr}\,\Sigma\)),约束施加在 belief 上(如 chance constraint)。于是 MPC 不仅规划"去哪",还规划"如何让 belief 保持确定 / 主动获取信息"。Platt 等的 ML 观测假设(§U4.6)正是让 belief-space MPC 可解的常用技巧(钉死观测 → 确定性轨迹优化 → 可用 DDP/iLQG/SQP)。
对比性思维:belief-space MPC 与 DESPOT 都在 belief 上规划,差在"连续优化 vs 树搜索"。belief-space MPC 把 belief 当连续状态、用梯度 / SQP 做滚动优化(适合连续高维、高斯 belief,续 U2/U3 的 MPC 机器);DESPOT 在离散 / 粒子 belief 上做树搜索(适合多模态、离散观测)。两者是 §U4.6 vs §U4.4 在"规划范式"上的体现——连续优化派(BSP / belief-MPC)vs 采样树搜索派(DESPOT)。选哪个仍回到那个老问题:belief 单峰高斯连续 → belief-MPC;多峰离散 → DESPOT。这也让 U4 与 U2/U3 接上了——belief-space MPC 就是"把 U2/U3 的 MPC 从状态空间搬到 belief 空间"。
进阶专题十一:belief 的表示方法谱 ⭐⭐⭐¶
贯穿本章的一条暗线是"belief 怎么表示"——它决定了能用什么算法、能处理什么问题。系统梳理一下:
| 表示 | 形式 | 优 | 劣 | 代表方法 |
|---|---|---|---|---|
| 精确分布 | \(b(s)\) 离散向量 | 精确、可算 α-vector | 仅小离散状态 | 精确求解、点基 SARSOP |
| 高斯 | \((\mu,\Sigma)\) | 紧凑、可解析、可微、高 DoF | 仅单峰 | BSP(LQG-MP/RRBT/FIRM) |
| 高斯混合 | \(\sum w_i\mathcal N(\mu_i,\Sigma_i)\) | 多峰 + 连续 | 分量数管理难 | 多假设跟踪、GMM 滤波 |
| 粒子 | 状态样本集 | 任意分布、多峰、与 $ | S | $ 脱钩 |
| 神经隐向量 | \((h_t,z_t)\) | 处理图像 / 高维观测、摊销 | 黑箱、受训练分布限制 | DreamerV3 RSSM |
选表示的主线:状态小离散 → 精确;连续单峰 → 高斯;连续多峰 → 高斯混合 / 粒子;图像 / 高维 → 神经。这张表其实就是本章所有方法的"底层数据结构"视角。
本质洞察:选 POMDP 方法,本质是先选 belief 的表示,算法随之而定。本章看似有一堆并列方法(SARSOP/DESPOT/BSP/Dreamer),但它们的根本分野在"用什么表示 belief"——精确分布配 α-vector、高斯配 Riccati、粒子配树搜索、神经向量配摊销 RL。一旦 belief 表示定了,能用的算法就基本定了。所以遇到新问题,先问"我的 belief 是什么形状(离散 / 单峰 / 多峰 / 图像)",再问"哪种表示装得下它"——表示选对,方法自然浮现。这也是为什么 §U4.6 的 BSP 和 §U4.4 的 DESPOT 不是竞争而是面向不同 belief 形状的互补工具。
进阶专题十二:信息论度量的统一(熵 / 互信息 / Fisher / D-A-E)⭐⭐⭐¶
§U4.7 出现了好几种"信息"度量(Shannon 熵、互信息、D/A/E-optimality、Fisher 信息),它们其实是同一件事的不同切面,理清能避免选错。
- Shannon 熵 \(H(b)\):belief 的不确定性(混乱程度)。
- 互信息 \(I(s;o\mid a)=H(b)-\mathbb E_o[H(b')]\):一个动作 / 观测带来的期望信息量——正是 §U4.7 的信息增益。它 \(\ge0\),观测越有区分力越大。
- Fisher 信息矩阵 \(\mathcal I\):局部地刻画"观测对参数估计的信息量";其逆是估计协方差的下界(Cramér–Rao)。在高斯 / 线性化下,\(\mathcal I\approx\Sigma^{-1}\)(信息矩阵 = 协方差的逆),这把"信息"和"协方差"接上了。
- D/A/E-optimality:对协方差 \(\Sigma\)(或信息矩阵 \(\mathcal I=\Sigma^{-1}\))的标量化——D(行列式 / 体积)、A(迹 / 总和)、E(最大特征值 / 最坏方向)。它们是"把矩阵不确定性压成一个可优化标量"的不同方式。
关系:高斯 belief 下,熵 \(H\propto\log\det\Sigma\)——所以"最小化熵"≈"D-optimality(最小化 \(\log\det\Sigma\))"≈"最大化 \(\log\det\mathcal I\)"。于是 §U4.7 的"信息增益 = 熵减"和"D-optimality"在高斯下是一回事。非高斯时用互信息更一般,但难算(要积分)。
本质洞察:这些"信息"度量在高斯下殊途同归,差别在非高斯与"你在乎哪种不确定"。Shannon 熵、互信息、\(\log\det\Sigma\)(D-opt)在高斯 belief 下基本等价(都正比于 \(\log\det\Sigma\))——所以别被术语吓到,它们大多在度量同一个"椭球体积"。真正的选择在两处:(1)belief 非高斯时,互信息最一般但难算,实践常退回高斯近似用 \(\log\det\);(2)你在乎哪种不确定——总体积(D)、各方向总和(A)、还是最坏方向(E)。Active SLAM 选度量,本质是回答这两个问题,而非纠结术语差异。
进阶专题十三:标准 POMDP benchmark 一览 ⭐⭐¶
DESPOT 的 examples/cpp_models/ 和文献里反复出现几个标准 benchmark。认识它们各测什么,便于读论文、跑实验、设计自己的问题。
| benchmark | 规模 | 测什么 | 特点 |
|---|---|---|---|
| Tiger | 2 状态、3 动作、2 观测 | 信息获取 vs 行动的权衡 | 最小 POMDP,教学 / 调试首选(本章全程用它) |
| RockSample(n,k) | \(\sim n^2\cdot 2^k\) 状态 | 大状态空间 + 信息获取(哪些石头是好的) | 机器人在网格采样石头,远程传感器越远越不准;可调规模 |
| Tag | \(\sim870\) 状态 | 部分可观测追逃 | 追一个看不见的目标(只有同格才观测到) |
| LaserTag | 更大 | 带激光传感的 Tag | 观测更丰富但仍部分可观测 |
| Pocman | \(\sim10^{56}\) 状态 | 巨大状态空间的可扩展性 | 部分可观测吃豆人;DESPOT/POMCP 展示大规模实时的招牌 |
这些 benchmark 的难度沿"状态空间 + 观测信息量"两轴铺开:Tiger 测核心权衡、RockSample 测可调规模 + 信息获取、Tag/LaserTag 测部分可观测追逃、Pocman 测极大状态空间。论文报告性能通常在这组上对比 SARSOP(小 / 中)、DESPOT/POMCP(大)。
本质洞察:benchmark 的演进映射 POMDP 方法的能力边界。Tiger(2 状态)SARSOP 秒解、Pocman(\(10^{56}\) 状态)只有在线采样方法(DESPOT/POMCP)能碰——一个 benchmark 跑得动跑不动,直接暴露方法的可扩展性。设计自己的 POMDP 时,先想清楚"它更像 Tiger(小、重权衡)还是 Pocman(大、重可扩展)",就知道该用 SARSOP 还是 DESPOT。这也是为什么本章用 Tiger 讲透原理(小到能手算)、用 DESPOT 讲可扩展(能上 Pocman 量级)。
进阶专题十四:POMDP 的复杂度与可解性全景 ⭐⭐⭐⭐¶
把散落各处的复杂度结论汇成一张全景图,理解"POMDP 到底有多难、哪些可解"。
| 问题 | 复杂度 / 可解性 | 含义 |
|---|---|---|
| MDP(全可观测) | P(多项式) | 容易,值迭代 / 线性规划可解 |
| POMDP 有限视界精确解 | PSPACE-hard | 比 MDP 难得多;只小问题可精确 |
| POMDP 无限视界最优策略 | 一般**不可计算**(undecidable) | 理论上无算法保证找到最优;只能近似 |
| POMDP \(\epsilon\)-近似(可达 belief) | 可工程化(SARSOP) | 中等规模离线 \(\epsilon\)-最优可达 |
| POMDP 在线规划(当前 belief) | output-sensitive(DESPOT) | 好策略简洁则少量场景可达近最优 |
| Dec-POMDP 有限视界 | NEXP-complete | 多智能体更难一个量级(进阶七) |
为什么这些复杂度结论重要:它们告诉你"哪些努力方向是死路"。比如想为一般 POMDP 找精确高效算法是徒劳(PSPACE-hard,§U4.2 思维陷阱);想为无限视界 POMDP 保证最优解也不可能(undecidable)。可行的方向都是"放松要求":放松到 \(\epsilon\)-近似(SARSOP)、放松到当前 belief 的在线解(DESPOT)、放松到高斯 belief(BSP)、放松到摊销(Dreamer)。每个实用方法都对应一种"放松"。
本质洞察:POMDP 研究史就是"在不可解的精确解 vs 可用的近似解之间,找各种聪明的放松"。精确 POMDP 撞 PSPACE / undecidable 这堵墙是铁的事实。所以整个领域的进展不是"攻破这堵墙",而是"绕过它"——每一种主流方法都是一种放松:可达性放松(点基)、视界放松(在线有限深度)、分布放松(高斯 BSP)、表示放松(神经摊销)、最优性放松(output-sensitive 近最优)。理解这一点,你读任何 POMDP 论文都能一眼看出它"放松了什么、换来了什么"——这是穿透 POMDP 方法丛林的指南针,也呼应 §U4.2"两个 curse"与进阶二"各方法如何绕 curse"的统一视角。
进阶专题十五:anytime 性质与实时部署 ⭐⭐⭐¶
要把 POMDP 放进机器人的控制回路(每周期固定毫秒预算),**anytime(随时可停)**性质是关键——这是 DESPOT/POMCP/HSVI 能上车而精确求解不能的工程原因。
什么是 anytime:算法在任意时刻被打断都能返回一个**当前最优可行解**,且解质量随计算时间单调提升。DESPOT 通过维护上下界 + 每轮 Explore-Expand-Backup 增量改进树来实现:时间一到就停、返回根节点当前最优动作。给的时间越多,树越深越宽、解越好(呼应 §U4.4 练习 \(K=50\) vs \(K=500\))。
实时部署的几个要点: - 时间预算分配:每个控制周期(如 100ms)扣掉感知 / belief update / 通信开销,剩下的才给规划。规划器用这个预算 anytime 搜索。 - belief update 与规划的节奏:高频做 belief update(跟上传感器),较低频做 POMDP 规划(计算贵)——或规划一次、执行多步(开环 / 半开环),下次再规划。 - 解质量 vs 实时性的权衡:预算紧就减小 \(K\) / 深度 \(D\) / 用更糙的 rollout,接受次优换实时;GPU(HyP-DESPOT)则在同预算下做更多场景、提质量。 - 最坏情况兜底:anytime 保证"有解可用",但极端紧预算下解可能很糙——安全关键系统要配一个保守的兜底策略(如紧急减速),规划失败 / 超时就退回兜底(呼应 U2 的安全滤波思想)。
本质洞察:anytime 是"用可中断的增量改进,把'算到最优'换成'在预算内尽量好'"——这是 POMDP 上实时机器人的通行证。精确求解是"要么算完要么没用"(不可中断),所以上不了实时回路。DESPOT/POMCP 把求解组织成"一轮一轮增量改进 + 随时可停返回当前最优"——于是它能塞进任意时间预算,预算多就好、少就糙,但总有解可用。这与 MPC 的"有限时域 + 滚动重规划"是同一种实时哲学(U2/U3):不追求一次算到全局最优,而是"在每个周期的预算内给出当前最优、然后滚动"。理解 anytime,你就懂了为什么"POMDP 难(PSPACE)"和"POMDP 能实时上车"并不矛盾——上车的从来不是精确解,而是 anytime 近似解。
进阶专题十六:分离原理为何在一般 POMDP 失效 ⭐⭐⭐⭐¶
一个贯穿估计与控制的深层问题:能不能把"状态估计"和"决策"**分开**做——先估出状态、再当它是真值做控制?答案揭示了 POMDP 的本质。
线性高斯下成立(LQG 分离原理):在线性动力学 + 高斯噪声 + 二次代价下,最优控制器**可以**分两步——卡尔曼滤波估出状态均值 \(\hat x\),再把 \(\hat x\) 当真值套 LQR。这就是 LQG 的分离原理 / 确定性等价(certainty equivalence):估计与控制解耦,且"按均值控制"恰好最优。这也是为什么 §U4.6 的 BSP(高斯 belief)能用"卡尔曼 + LQR"这套解析机器。
一般 POMDP 下失效:但分离原理是线性高斯的**特例**,一般 POMDP 不成立。原因正是 §U4.1 反复强调的——最优决策依赖**整个 belief 的形状**(尤其不确定性大小、是否多峰),而非仅均值。"按均值控制"会丢掉"我有多不确定"这一关键信息,于是次优甚至灾难(双峰 belief 的均值落在不可能处)。更关键:一般 POMDP 里,控制动作会影响未来能获得的信息(主动感知),所以估计与控制**耦合**——你选的动作既为了完成任务、又为了把状态看清,二者无法分开优化。
本质洞察:POMDP 的核心难度,正是"分离原理失效"——估计与控制不可解耦。线性高斯的世界很仁慈:估计(卡尔曼)和控制(LQR)可以各做各的,按均值行动即最优(确定性等价)。但这是特例。一般 POMDP 里,三件事缠在一起:决策依赖整个 belief(不只均值)、动作影响未来信息(主动感知)、不确定性影响最优动作(不确定时先消歧)。这三点让"先估计再控制"的朴素两段式失效——你必须在 belief 上**联合**优化估计与决策,这正是 POMDP(belief-MDP)比"滤波 + MDP 控制"难的根本。反过来看,§U4.1 的"把 POMDP 当 MDP 做"为什么失败、§U4.8 的"RSSM 把估计与控制一起摊销"为什么是对的,都是这条洞察的推论:当分离原理失效,估计与决策就必须在 belief 上合二为一。这也是整章最深的一句话。
前沿与开放问题¶
POMDP 仍是活跃研究领域,几条值得关注的前沿(截至本文知识范围):
- 神经引导树搜索:BetaZero(Moss et al., RLC 2024)把 AlphaZero 式价值 / 策略网络 + belief-state MCTS 用于长视界 POMDP;这一路线(学习提供先验、搜索提供保证)正成为主流,与 §U4.5 的 LeTS-Drive / MAGIC 同源。
- 离线 POMDP 图搜索:POMCGS(Partially Observable Monte-Carlo Graph Search, ICAPS 2025)等把在线树搜索的思想用于离线构造紧凑的有限状态控制器,兼顾离线策略的可复用与采样方法的可扩展。
- 世界模型导航:DreamerV3 之后,显式带 POMDP 目标的导航世界模型(如 2025 年前后的若干工作)把"摊销 belief + latent 规划"用到机器人导航,处理图像观测下的部分可观测。
- 开放问题:
- 3DGS / NeRF 作为观测模型:如何把 3D Gaussian Splatting / 神经辐射场这类高保真场景表示,接进 POMDP 的观测模型 \(O(o\mid s',a)\)?这关系到"用学到的场景表示做 belief 空间规划"。
- Dec-POMDP 的可扩展实现(进阶专题七):多机器人在通信受限下协作,NEXP 复杂度如何工程化逼近?
- DESPOT C++ 骨架 × PyTorch 学习组件的优雅桥接:如何让 DESPOT 的高效 C++ 树搜索与 PyTorch 的学习模块(学引导 / 学价值)干净地协同?这是 §U4.5 学习辅助路线落地的工程瓶颈。
这些问题没有定论,适合作为研究切入点。共同主题是"**学习 × 搜索 × 表示**的融合":用学到的表示(世界模型 / 3DGS)刻画 belief 与观测,用学到的先验引导搜索,用搜索保证前瞻与可验证性。
累积项目:为统一不确定性导航测试台加装"感知不确定性 + 主动感知"¶
回顾 Part-U 的累积项目(U0 §7 定义):一个 2D 双积分器导航测试台,逐章加装一种不确定性范式,主干不动。
- U2(鲁棒) 加了:有界扰动 + tube / CBF 安全滤波(动力学端,硬保证)。
- U3(机会约束) 加了:高斯扰动 + 概率约束 \(\delta\)(动力学端,概率保证)。
- U1(分支) 加了:他车离散意图 + 共享干 + 加权分支(交互端,多模态)。
- U4(本章)加:不可观测状态 + belief 维护 + 主动感知(感知端,认知不确定)。
本章模块设计(与前几章正交叠加,主干不动):
| 组件 | U4 之前 | U4 加装后 |
|---|---|---|
| 状态可观测性 | 状态 \(x\) 完全可观测 | 部分可观测:障碍的**位置 / 意图**只能通过带噪传感器观测 |
| 状态表示 | 点状态 \(x\) | belief \(b(x)\)(粒子集,复用实现四) |
| 估计模块 | 无(或假设已知) | belief update(粒子滤波,实现一 / 四)——SLAM 工程师已会 |
| 决策模块 | MPC / 分支规划(在 \(x\) 上) | 在 belief 上规划(DESPOT 式前向搜索,实现三) |
| 奖励 | 到达 − 碰撞 − 控制 | 加 **信息增益**项(实现五)——驱动主动消歧 |
| 主动感知 | 无 | 不确定大时**先去看清**(主动降低 belief 不确定性)再行动 |
与前几章的叠加:U4 的 belief 空间规划与 U2/U3 的动力学不确定性**正交可叠**——可以在 belief 空间里做带 chance constraint 的规划(每个 belief 样本上施加 U3 的概率约束);与 U1 的意图分支可统一——U1 的意图分支正是对"离散不可观测意图"的 belief 树近似(§U4.4)。
项目落地步骤(建议实现顺序):
1. 把测试台的障碍位置 / 意图设为不可观测,加一个带噪传感器(观测模型 \(O\))。
2. 用粒子集维护 belief(实现四的 particle_update)。
3. 在 belief 上做 DESPOT 式前向搜索选动作(实现三的 despot_plan,把 rollout 换成测试台的代价)。
4. 给奖励加信息增益项(实现五),对比"有 / 无主动感知"的导航成功率(在强歧义场景下,主动感知应显著提升成功率)。
5.(进阶)在 belief 样本上叠加 U3 的 chance constraint,做"感知不确定 + 概率安全"的规划。
该测什么(评估指标):跑这个 U4 测试台时,建议记录以下指标来量化"主动感知"的价值——(1)导航成功率(到达目标且不碰撞的比例),分"有 / 无信息增益奖励"两组对比,强歧义场景下前者应明显更高;(2)belief 熵随时间的曲线,看主动感知是否更快把不确定性压下来(对比被动跟随);(3)消歧前的多余移动(为看清而绕的路),它是"主动感知的代价"——好的策略应在"消歧收益"与"绕路代价"间平衡;(4)QMDP vs DESPOT 式的成功率差,验证 QMDP 因低估持续消歧而在强歧义场景吃亏。这组指标把 §U4.1(belief 熵)、§U4.2(QMDP 局限)、§U4.7(信息增益价值)都变成了可观测的数字。
本质洞察:U4 模块把测试台的不确定性从"动力学 / 交互端"扩到"感知端",补齐了五安全谱的最后一块拼图。U2/U3 假设你看得清世界、只是世界会变(动力学扰动);U1 假设你看得清自己、只是猜不透别人(交互意图);U4 让你连"世界当前什么样"都看不清(感知不确定)。四者正交叠加后,测试台覆盖了不确定性的四个来源——这正是 U0 五安全谱的工程化身(U5 再加尾部风险)。一个能在"动力学扰动 + 概率安全 + 多模态意图 + 感知不确定"下导航的测试台,就是不确定性规划的完整练兵场。
方向落地案例¶
POMDP / belief 空间规划在真实机器人方向的落地:
- 自动驾驶(意图感知):Context-POMDP(§U4.5)把周围车 / 行人的隐藏意图当 belief,在线 DESPOT 规划——城市密集交通的意图感知决策。与 U1 的 EPSILON 同处一个问题(意图不确定),DESPOT 路线 vs 引导分支路线各有取舍。
- 移动机器人探索 / Active SLAM(§U4.7):未知环境建图,用信息增益奖励驱动"去哪测最划算"。
ethz-asl/mav_active_3d_planning是无人机主动三维建图的干净实现(Factory/Strategy 设计模式 + POMDP 实例)。 - 机械臂抓取(部分可观测位姿):抓取时物体位姿被遮挡,用 belief 空间规划决定"先怎么动以看清 / 触清物体"——MIT CSAIL 的抓取 POMDP 路线。
-
水下 / 太空等强不确定环境:传感受限、模型不准,POMDP 的"在不确定上决策 + 主动获取信息"价值最大。
-
医疗 / 手术机器人(可操控针):可操控针(steerable needle)在软组织里穿刺到目标,组织变形 + 针尖位姿带噪 + 不能反复试探——这是 belief-space planning 的经典战场(van den Berg、Patil 等),用高斯 belief + 协方差传播规划"既准又稳"的穿刺路径,执行前评估偏离 / 损伤风险。
- 水下 / 太空 / 地下(强不确定环境):GPS 失效、传感受限、模型不准、回环稀少——belief 的不确定性大且难压。POMDP 的"在不确定上决策 + 主动获取信息"价值最大;Active SLAM(§U4.7)在这类环境(如 DARPA SubT 地下挑战)尤其关键。
共同模式:凡是"状态看不清、且获取信息有代价"的机器人任务,都是 POMDP。落地时的工程主力是 DESPOT 全家族(C++、实时、可上车)或 BSP(高 DoF 连续、高斯 belief)。哪个为主,仍回到那条主线:belief 多峰 / 离散观测 → DESPOT;高 DoF 连续 + 单峰高斯 → BSP——选型指南给了完整决策表。
方法选型决策指南¶
面对一个部分可观测问题,怎么选方法?按"状态空间 + belief 形状 + 实时性 + 是否需主动感知"决策:
| 你的情况 | 推荐方法 | 理由 |
|---|---|---|
| 状态小(几十)、模型固定、要可复用策略 | SARSOP(点基,离线) | 离线 \(\epsilon\)-最优,在线只查表 |
| 状态大 / 连续、模型每帧变、要实时 | DESPOT / HyP-DESPOT(在线) | output-sensitive、采样稀疏树、GPU 可百倍加速 |
| 只需快速粗解、消歧需求少 | QMDP(最廉价) | 极快,但系统性低估持续消歧(§U4.2) |
| 连续动作 / 观测 | POMCPOW(Progressive Widening) | 治连续观测分支退化(进阶三) |
| 高 DoF 连续状态、belief 单峰(高斯) | BSP(LQG-MP/RRBT/FIRM) | 高斯参数化、可解析、可微(§U4.6) |
| 多模态 belief(感知混淆 / 全局歧义) | 粒子 POMDP(DESPOT/POMCP) | 粒子能表示多峰,BSP 高斯不行 |
| 图像 / 像素观测、有大量数据、容忍黑箱 | DreamerV3(RSSM) | 摊销 belief、处理高维观测(§U4.8) |
| 要兼顾学习样本效率 + 搜索保证 | BetaZero(学引导 belief MCTS) | 学习提供先验、搜索提供前瞻(§U4.8) |
| 接 SLAM 因子图、要算未来信息增益 | BSP-iSAM(§U4.6) | 在 iSAM2 框架可微算信息增益,直通 Active SLAM |
决策主线三问:(1)belief 是单峰还是多峰?单峰高斯 → BSP;多峰 → 粒子 POMDP。(2)模型固定还是每帧变?固定小规模 → SARSOP 离线;变 / 大 → DESPOT 在线。(3)观测是符号还是图像?符号 → DESPOT;图像 → Dreamer,或两者杂交(BetaZero)。
对比性思维:选 POMDP 方法的本质是"在 belief 表示和求解方式上各做一次取舍"。belief 表示:解析(小离散,α-vector)vs 粒子(大 / 连续多峰)vs 高斯(高 DoF 单峰)vs 神经(图像)。求解方式:离线(SARSOP,算一次反复用)vs 在线(DESPOT,每帧现算)vs 摊销(Dreamer,训练好一次前向)。把这两个维度的取舍想清楚,选型就清楚了——没有万能方法,只有"匹配你的 belief 形状 + 实时预算 + 观测类型"的方法。
理论补遗¶
几个值得明确的理论点:
1. POMDP 求解的复杂度。有限视界 POMDP 的精确求解是 PSPACE-hard(比 MDP 的 P 难得多);无限视界 POMDP 的最优策略一般**不可计算**(undecidable)。这是为什么实践中只能近似。Dec-POMDP(进阶七)有限视界更是 NEXP-complete。这些复杂度结果说明"POMDP 难"是本质的、非实现问题(§U4.2 思维陷阱)。
2. belief 是充分统计量的证明要点。要证"给定 \(b_t\),最优动作不依赖历史"。归纳:未来回报只依赖未来状态-动作序列的分布,而该分布完全由当前状态分布(即 \(b_t\))和未来策略决定,与"如何到达 \(b_t\)"无关。所以两段导出相同 \(b_t\) 的历史,其最优续策略相同。这正是 POMDP→belief-MDP 转化的合法性根据(§U4.1)。
3. PWLC 的归纳证明骨架。\(V_0\)(零视界)是常数(PWLC 的平凡情形)。归纳假设 \(V_{H-1}\) PWLC(有限 α-vector)。一步 Bellman 备份:\(V_H(b)=\max_a[\rho(b,a)+\gamma\sum_o\Pr(o\mid b,a)V_{H-1}(\tau(b,a,o))]\)。代入 \(V_{H-1}\) 的 PWLC 形式,经代数整理,\(V_H\) 仍是有限个线性函数取 max——即 PWLC。归纳完成。α-vector 数随视界指数增长正来自这一步的组合(每个 \(a\) × 每个 \(o\) 接哪个旧 α)。
4. output-sensitive 界的意义。DESPOT 的 regret 界形如 \(O(\text{(最优策略表示大小)} \times \text{(采样误差)})\)——不含 \(|S|\)。这意味着"问题难度由最优策略的复杂度决定,而非状态空间大小"。直觉:如果好策略简单(如"先听到足够确定再开门"),少量场景就能找到它,哪怕状态空间巨大。这是 DESPOT 处理大状态空间的理论根基(§U4.4)。
从 Python 原型到 C++ 部署:DESPOT 的 DSPOMDP 接口¶
教学用 Python 讲清算法,但要上实时机器人(自驾、无人机),主力是 C++ 的 DESPOT(AdaCompNUS/despot,GPL-3.0)。它是 POMDP C++ 教学的最佳载体——因为它把"定义一个 POMDP"的门槛压到极低:你只需继承 DSPOMDP 基类、实现 6–8 个虚函数,求解器(DESPOT/POMCP/AEMS)全自动接管。
为什么是这套接口¶
DESPOT 的设计哲学:把"问题定义"和"求解算法"彻底解耦。你(用户)只负责描述 POMDP 的动态(怎么转移、怎么观测、奖励多少);求解器负责所有难的事(建确定化稀疏树、上下界引导搜索、正则化)。这种"实现几个回调、框架接管"的模式,和你在 SLAM 里用 GTSAM(你定义因子、框架做优化)、在 MPC 里用 acados(你定义模型 / 代价、框架求解 OCP)是同一种工程审美——用户只填领域特定的部分,通用算法复用。
核心类层次¶
World(真实/仿真环境) ── Planner ── Solver(DESPOT / POMCP / AEMS)
│
DSPOMDP(你的 POMDP 定义) ── Belief
│
ScenarioLowerBound / ScenarioUpperBound(上下界)
用户需实现的 6–8 个虚函数¶
继承 DSPOMDP,实现以下虚函数(这就是定义一个 POMDP 的全部工作):
class TigerPOMDP : public DSPOMDP {
public:
// 1) Step: 确定化一步——给定状态/动作/随机数, 返回奖励+观测, 原地改状态。
// 这是 §U4.4 "场景=随机数确定化执行" 的 C++ 落点; 求解器用它在 K 个场景上仿真。
bool Step(State& state, double random_num, ACT_TYPE action,
double& reward, OBS_TYPE& obs) const override;
// 2) NumActions: 动作个数 |A|。
int NumActions() const override;
// 3) ObsProb: 观测模型 O(obs | state', action), 用于 belief 更新与加权。
double ObsProb(OBS_TYPE obs, const State& state, ACT_TYPE action) const override;
// 4) CreateStartState: 采一个起始状态(按问题的初始分布)。
State* CreateStartState(string type = "DEFAULT") const override;
// 5) InitialBelief: 构造初始 belief b0(常是粒子集)。
Belief* InitialBelief(const State* start, string type = "DEFAULT") const override;
// 6) GetMaxReward: 单步最大奖励(供上界用)。
double GetMaxReward() const override;
// 7) CreateScenarioUpperBound: 上界(乐观估计, 引导搜索; 可用默认或自定义)。
ScenarioUpperBound* CreateScenarioUpperBound(string name = "DEFAULT",
string particle_bound = "DEFAULT") const override;
// 8) CreateScenarioLowerBound: 下界(一个可执行的简单策略, 如总是 listen)。
ScenarioLowerBound* CreateScenarioLowerBound(string name = "DEFAULT",
string particle_bound = "DEFAULT") const override;
};
Step 的实现(最关键,对应实现三的 step)¶
Step 是核心——它就是 Python 实现三里 step(s,a,r) 的 C++ 版:用随机数 random_num 把随机转移 / 观测**确定化**(这正是 DESPOT "场景"的机制)。
bool TigerPOMDP::Step(State& state, double random_num, ACT_TYPE action,
double& reward, OBS_TYPE& obs) const {
TigerState& s = static_cast<TigerState&>(state);
if (action == LISTEN) {
reward = -1.0;
// 用 random_num 确定化观测: 以 0.85 概率听对
bool correct = (random_num < 0.85);
obs = correct ? s.tiger_pos : (1 - s.tiger_pos);
return false; // 未终止
} else { // 开门
reward = (action - 1 == s.tiger_pos) ? -100.0 : 10.0; // 开到虎=-100
obs = 2; // 开门后观测无信息
return true; // 终止(本回合结束)
}
}
注意 random_num 的角色:它是场景预先掷好的"骰子",让这一步的随机性确定化——同一状态 + 同一动作 + 同一 random_num 永远走出同一结果。求解器对 \(K\) 个场景各持一串随机数,于是整棵 DESPOT 确定化(§U4.4)。
对比:C++ DESPOT 与 Python 原型¶
| 维度 | Python 原型(实现三) | C++ DESPOT(AdaCompNUS/despot) |
|------------|------------------------|--------------------------------|
| 用途 | 教学/理解/快速验证 | 实时部署(自驾/无人机) |
| 你写的 | 整个前向搜索循环 | 只写 DSPOMDP 的 6-8 个虚函数 |
| 求解器 | 自己写的简化版 | 工业级 DESPOT(anytime+正则化) |
| 上下界 | 简单 rollout | 可自定义 Scenario Upper/LowerBound|
| 速度 | 慢(纯 Python) | 快(C++; HyP-DESPOT 还有 GPU) |
| 多算法对比 | 无 | 同库含 DESPOT/POMCP/AEMS 可切换 |
工程上推荐路线:先用 Python 把 POMDP 建模 + 算法理解透(本章实现),再把 Step/ObsProb/InitialBelief 翻成 C++ DSPOMDP,让 DESPOT 求解器接管。Tiger 的完整 C++ 例子 <100 行(在 examples/cpp_models/tiger/),是上手 DESPOT 的最佳起点。
本质洞察:DESPOT 的
DSPOMDP接口把"POMDP 工程化"降到了"填几个回调"。POMDP 听起来高深,但 DESPOT 让你只需回答四个具体问题——怎么转移 + 观测(Step)、观测多大可能(ObsProb)、初始信念是什么(InitialBelief)、最多能拿多少奖励(GetMaxReward)——剩下的两个 curse、稀疏树、正则化全由求解器处理。这种"用户填领域回调、框架做通用算法"的解耦,是 DESPOT 成为事实标准的工程原因,也和 GTSAM(填因子)、acados(填模型)一脉相承。对你的启示:评估一个 POMDP 库,先看"我要定义一个新问题需要写多少、写什么"——DSPOMDP的 6–8 个虚函数是一个很低的门槛标杆。
工具与源码精读清单¶
POMDP 的主要开源生态,按"学习成本 / 用途"排序。精读重点已标出。
| 项目 | 语言 / 许可 | 定位 | 精读重点 |
|---|---|---|---|
| AdaCompNUS/despot | C++ / GPL-3.0 | 在线 POMDP 事实标准 | examples/cpp_models/(Tiger/RockSample/LaserTag/Pocman/Tag 五基准);src/solver/despot.cpp 核心循环;DSPOMDP 接口如何把建模门槛压到 6–8 个虚函数 |
| AdaCompNUS/hyp-despot | C++/CUDA / GPL-3.0 | GPU 并行 DESPOT | Dvc_DSPOMDP GPU 接口如何并行化 rollout;哪些函数移到设备端、为什么 |
| AdaCompNUS/sarsop | C++ / GPL | 离线点基求解器 | α-vector 的管理(备份 / 剪枝);最优可达 belief 的采样 |
| JuliaPOMDP/POMDPs.jl | Julia / MIT | 可组合 POMDP 生态 | 换求解器只改一个构造函数;配套 ARDESPOT.jl / POMCPOW.jl / SARSOP.jl / BetaZero.jl |
| h2r/pomdp-py | Python·Cython / MIT | Python 快速原型 | POMCP/POUCT 实现;适合教学与原型(与本章 Python 实现风格接近) |
| RDLLab/oppt | C++ / MIT | 在线 POMDP 工具箱 | 与 Gazebo 集成;连续状态 POMDP |
| ethz-asl/mav_active_3d_planning | C++·ROS / BSD | 无人机主动三维建图 | 最干净的 Factory/Strategy 设计模式;Active SLAM 的 POMDP 实例(§U4.7) |
精读路线建议:想理解算法 → 先读 pomdp-py(Python,POMCP 清晰)或本章 Python 实现;想上工程 → 读 despot 的 Tiger 例子 + despot.cpp 主循环;想做 Active SLAM → 读 mav_active_3d_planning;想用 Julia 快速对比多求解器 → POMDPs.jl。
对比性思维:选 POMDP 库看"建模门槛 + 求解器丰富度 + 生态"。
despot(C++)建模门槛极低(6–8 虚函数)、求解器工业级、但 C++ 上手有成本;pomdp-py(Python)原型快、读代码清晰、但性能有限;POMDPs.jl(Julia)可组合性最佳(换求解器改一行)、生态全(DESPOT/SARSOP/POMCPOW/BetaZero 都有)、但要学 Julia。学习选 Python / Julia,部署选 C++(despot/hyp-despot)。
代码索引¶
本章可运行实现速查(均在"完整实现精读",数值已核对):
| 实现 | 函数 | 对应正文 | 验证数值 |
|---|---|---|---|
| 实现一 | belief_update(b,a,o) |
§U4.1 贝叶斯滤波 | 听 3 次 hear-left → 0.85/0.97/0.9945 |
| 实现二 | solve_mdp_values, qmdp_action |
§U4.2 QMDP | \(V_{\text{MDP}}=200\);Q:listen 189 / 开安全 200 / 开虎 90;听约 2 次开门 |
| 实现三 | step, rollout, despot_plan |
§U4.4 DESPOT 式前向搜索 | 不确定 listen、\(p=0.99\) 开门 |
| 实现四 | particle_update |
§U4.4 粒子 belief | 1000 粒子 → 0.845/0.968/0.994(吻合解析) |
| 实现五 | entropy, expected_info_gain |
§U4.7 信息增益 | listen 增益 0.39 bit、open 增益 0 |
| C++ | TigerPOMDP::Step 等 |
§Python→C++ | DSPOMDP 6–8 虚函数 |
综合实战¶
把本章拼成一个端到端任务,巩固全章。
任务:2D 格子世界的主动定位 + 导航。机器人在一个有对称走廊的格子世界里,初始不知道自己在哪(全局歧义,belief 多峰),要导航到目标。
1. 建模为 POMDP(§U4.1):状态 = 格子位置;动作 = 上下左右;观测 = 周围墙的布局(对称处会混淆);奖励 = 到达目标 + 信息增益 − 步数。
2. 维护 belief(实现一 / 四):用粒子集表示位置 belief;每步用 particle_update 更新。验证在对称走廊里 belief 保持多峰、不收敛(§U4.1 思维陷阱)。
3. 在 belief 上规划(实现三):用 DESPOT 式前向搜索选动作;在 belief 多峰时,规划器应选"去能区分的地方"(主动消歧),而非直奔目标。
4. 加信息增益奖励(实现五):对比"有 / 无信息增益项"——无信息增益时机器人在歧义未消时就冲向目标(常走错峰对应的方向)、有信息增益时先消歧再走,成功率更高。
5. 对比 QMDP vs DESPOT 式(实现二 vs 三):QMDP 在多峰 belief 上消歧不足、过早行动;DESPOT 式看得见持续消歧的价值。
预期结论:(a)多峰 belief 必须靠"移动到可区分处"消歧,原地观测无用;(b)信息增益奖励让机器人主动消歧,显著提升强歧义场景的成功率;(c)QMDP 因低估持续消歧而表现差于完整在线规划。这串起了 §U4.1(belief / 多峰)、§U4.2(QMDP 局限)、§U4.4(在线规划)、§U4.7(信息增益)。
🔧 故障排查手册¶
POMDP / belief 空间规划实现与调试的高频故障:
| 症状 | 可能原因 | 排查步骤 | 相关节 |
|---|---|---|---|
| belief 多步后和不为 1 / 全为 0 | 未归一化,或在乘观测似然前归一化,或数值下溢 | 1. 每步 assert abs(sum(b)-1)<1e-9 2. 检查归一化在校正之后 3. 大状态空间转对数域 |
§U4.1 |
| belief 在对称环境里不收敛(一直多峰) | 不是 bug——感知混淆,观测对这些状态无区分力 | 1. 检查 \(O(o\mid s_1)\) 与 \(O(o\mid s_2)\) 是否相同 2. 需靠"移动到可区分处"消歧而非原地观测 | §U4.1 思维陷阱、§U4.7 |
| QMDP 在需要消歧的任务上表现差 / 过早行动 | QMDP 假设一步后全可观测,系统性低估持续消歧 | 1. 确认任务是否需要多步消歧 2. 换点基(SARSOP)或在线(DESPOT)3. 别照搬"QMDP 不 listen"的说法、实跑看 | §U4.2 |
| DESPOT 策略抖动 / 实跑差(场景少时) | \(K\) 太小,过拟合采样场景(B-DESPOT) | 1. 增大 \(K\)(几十→几百)2. 用 R-DESPOT 正则化(加 \(\lambda\|\pi\|\))3. \(K\) 越小 \(\lambda\) 越大 | §U4.4 |
| 连续观测下树退化(每分支一个粒子、估值方差爆) | 每个观测唯一,观测分支无限 | 1. 用 POMCPOW 的 Progressive Widening 2. 或离散化观测 3. 或用 DESPOT 的固定 \(K\) 场景限制分支 | 进阶三 |
| 粒子滤波 belief 退化(少数粒子占全部权重) | 粒子贫化(particle depletion) | 1. 增加粒子数 2. 重采样(SIR)3. 加 roughening / 注入噪声 | 实现四 |
| 高斯 BSP 在全局定位 / 对称环境失效(均值落在不可能处) | belief 实为多峰,高斯只能单峰 | 1. 确认 belief 是否多峰 2. 多峰换粒子 POMDP(DESPOT/POMCP)3. 单峰才用 BSP | §U4.6 思维陷阱 |
| Active SLAM 机器人无限探索、不完成任务 | 奖励只有信息增益、缺到达 / 任务项 | 1. 检查奖励是否多项加权 2. 加到达 / 覆盖项并配权重 | §U4.7 |
API 速查表¶
本章涉及的核心接口 / 函数签名(DESPOT C++ 与 Python 原型):
# === DESPOT C++ (AdaCompNUS/despot) DSPOMDP 用户接口 ===
bool Step(State&, double rand, ACT_TYPE a, double& reward, OBS_TYPE& obs) const # 确定化一步
int NumActions() const # |A|
double ObsProb(OBS_TYPE o, const State& s2, ACT_TYPE a) const # O(o|s',a)
State* CreateStartState(string type) const # 采起始状态
Belief* InitialBelief(const State* s, string type) const # 初始 belief b0
double GetMaxReward() const # 单步最大奖励(上界用)
ScenarioUpperBound* CreateScenarioUpperBound(...) const # 上界(乐观估计)
ScenarioLowerBound* CreateScenarioLowerBound(...) const # 下界(可执行策略)
# === 本章 Python 原型 ===
belief_update(b, a, o) -> b' # 贝叶斯滤波(§U4.1)
solve_mdp_values() -> V # 全可观测 MDP 值(QMDP 用)
qmdp_action(b, V) -> (a, q_values) # QMDP 决策(§U4.2)
despot_plan(b, K, depth) -> (a, value) # DESPOT 式前向搜索(§U4.4)
particle_update(particles, a, o) -> particles' # 粒子 belief(SIR, §U4.4)
expected_info_gain(b, a) -> bits # 信息增益(熵减, §U4.7)
# === POMDPs.jl (Julia) 典型用法 ===
pomdp = TigerPOMDP() # 定义问题
solver = SARSOPSolver() # 换求解器只改这一行(DESPOTSolver/POMCPOWSolver/...)
policy = solve(solver, pomdp) # 求解
a = action(policy, b) # 用策略决策
调参与诊断¶
POMDP 方法的关键超参与调法:
| 超参 | 出现在 | 作用 | 调参建议 |
|---|---|---|---|
| 场景数 \(K\) | DESPOT | 估策略价值的样本数 | 太小过拟合 / 抖动,太大慢;典型几十到几百,从小到大看性能拐点 |
| 搜索深度 \(D\) | DESPOT/POMCP | 前瞻步数 | 太浅近视、太深爆炸 + 浪费;按问题有效视界设,配宏动作(MAGIC)压缩 |
| 正则系数 \(\lambda\) | R-DESPOT | 惩罚策略复杂度 | \(K\) 越小 \(\lambda\) 越大;从小调大直到实跑稳定 |
| 粒子数 \(N\) | 粒子 belief | belief 近似精度 | 多峰 / 高维要更多;监控粒子贫化(有效粒子数 ESS)决定重采样时机 |
| UCB 系数 \(c\) | POMCP | 探索-利用平衡 | 太大瞎探、太小过贪;按回报量级调 |
| PW 系数 \(k,\beta\) | POMCPOW | 加宽速度 | 连续空间防退化;\(\beta\) 小则加宽慢(每分支样本多) |
| 折扣 \(\gamma\) | 全部 | 有效视界 \(\sim 1/(1-\gamma)\) | 越接近 1 有效视界越长、越难;按任务时间尺度设 |
| 信息增益权重 | Active SLAM | 探索 vs 任务 | 纯探索重信息增益;带目标要平衡到达项(否则乐不思蜀) |
诊断流程:策略差 → 先分清是"belief 估计错"(查滤波 / 归一化 / 粒子贫化)还是"规划错"(查 \(K/D/\lambda\))。belief 对但决策蠢 → 多半 \(K\) 太小或 \(D\) 太浅或 QMDP 信息盲。belief 都不对 → 查观测模型 \(O\) 是否正确、归一化是否对。
常见问题(FAQ)¶
Q1:POMDP 和 SLAM 到底什么关系? SLAM 是 POMDP 的 belief update 模块(状态估计);POMDP 在 SLAM 之上加"在 belief 上决策"。会 SLAM 就会 POMDP 的一半,Active SLAM 就是把另一半(planning)接上(§U4.1/§U4.7)。
Q2:belief 和点估计(均值 / MAP)有什么区别,为什么不能只用均值? belief 是整个分布,点估计丢了"不确定性大小 + 多峰"信息。在多峰 / 高方差 belief 上,均值可能落在不可能的位置,且无法触发主动消歧(§U4.1 陷阱)。
Q3:QMDP 到底 listen 不 listen? 会 listen(在不确定 belief 上),但系统性低估"该 listen 多久"——它假设一步后全可观测,于是消歧不足、过早行动。别照搬"QMDP 不 listen"的二手说法,实跑验证(§U4.2、实现二)。
Q4:DESPOT 的"场景"是什么?是采样的轨迹吗? 不是轨迹,是"起始状态 + 一串随机数"。随机数把随机性确定化,但走出什么轨迹仍取决于你选的动作。一棵 DESPOT 编码所有策略在 \(K\) 个场景下的执行(§U4.4 陷阱)。
Q5:什么时候用 BSP(高斯),什么时候用 DESPOT(粒子)? belief 单峰、状态高 DoF 连续 → BSP(高斯参数化、可解析);belief 多峰 / 感知混淆 → 粒子 POMDP(DESPOT/POMCP,高斯表示不了多峰)(§U4.6、选型指南)。
Q6:DreamerV3(世界模型)和经典 POMDP(DESPOT)是竞争关系吗? 不是。RSSM 是 POMDP 的摊销解(encoder = belief update、latent 规划 = belief 空间规划)。它们求解同一个问题(belief-MDP),一个现算、一个摊销,正在 BetaZero 处合流(§U4.8)。
Q7:POMDP 这么难(PSPACE-hard),实际机器人怎么用? 靠近似 + 在线 + 采样。DESPOT 的 output-sensitive 界保证"好策略简洁时少量场景就够",加 GPU(HyP-DESPOT)做到实时;或用 BSP 在高斯假设下解析求解(§U4.4/U4.6)。
Q8:U1 的分支规划和 POMDP 是什么关系? U1 的意图分支是对"离散不可观测意图"的 belief 树近似——EUDM 显式说自己是"POMDP + 引导分支"。U1 用领域剪枝近似 POMDP,DESPOT 用采样稀疏化近似 POMDP,是同一问题的两种近似(§U4.4)。
Q9:能不能"先估计再控制"——先用滤波器估出状态、再当真值做 MDP 控制? 线性高斯下可以(LQG 分离原理 / 确定性等价,按均值控制即最优);但一般 POMDP 不行——决策依赖整个 belief、且动作影响未来信息(主动感知),估计与控制耦合,必须在 belief 上联合决策(进阶十六、§U4.1 反面)。
Q10:POMDP 难在 PSPACE / undecidable,那实际怎么"绕过"这堵墙? 每个实用方法都对应一种"放松":可达性放松(点基只管可达 belief)、视界放松(在线只看有限深度)、分布放松(高斯 BSP)、表示放松(神经摊销 Dreamer)、最优性放松(output-sensitive 近最优)。读任何 POMDP 方法,问它"放松了什么、换来什么"(进阶十四)。
Q11:粒子滤波 belief 里粒子越来越集中(贫化)怎么办? 监控有效粒子数(ESS),低于阈值就重采样;重采样后粒子塌缩到少数几个值时,加 roughening(给粒子注入小噪声)或增加粒子数。感知混淆区粒子天然分裂成多簇是正常的(多峰),不是贫化——别误把多峰当 bug 去"修"(§U4.1、故障排查)。
本章常见误解汇总¶
| 误解 | 正确理解 | 出处 |
|---|---|---|
| belief 就是滤波器估的那个状态,取均值用即可 | belief 是整个分布;均值丢了不确定性 + 多峰信息,在多峰上甚至落在不可能位置 | §U4.1 |
| 观测越多 belief 一定越确定 | 仅当观测对状态有区分力;感知混淆区再多观测也不消歧,须靠移动 | §U4.1、§U4.7 |
| α-vector 是 belief(都是 $ | S | $ 维) |
| QMDP 在 Tiger 上从不 listen | QMDP 会 listen,但系统性低估持续消歧、过早行动(实跑验证) | §U4.2、实现二 |
| α-vector 数爆炸是实现不好、换算法就行 | 是 POMDP 固有复杂度(PSPACE-hard、两个 curse),非实现问题 | §U4.2、理论补遗 |
| 点基方法给的是 \(V^*\) 上界 | 是**下界**(每个 α 对应可执行计划);上界另行维护 | §U4.3 |
| DESPOT 的"场景"是采样轨迹 | 是"起始状态 + 随机数串";同场景 + 不同动作 = 不同轨迹 | §U4.4 |
| DESPOT 可以算一次反复用 | 它是在线方法,每周期现算、用完即弃;要复用用 SARSOP | §U4.4 |
| HyP-DESPOT 改进了 DESPOT 的算法 / 理论 | 它是并行实现(GPU),算法与界同 DESPOT | §U4.5 |
| LQG-MP = "假设未来观测为最大似然" | 两篇不同 RSS 2010:LQG-MP 是协方差传播评估路径;ML 观测假设是 Platt 等 | §U4.6 |
| 高斯 belief(BSP)适用所有定位 | 高斯只能单峰;全局歧义 / 对称环境是多峰,须用粒子 | §U4.6 |
| 信息增益是唯一奖励 | 是多项加权(信息增益 + 覆盖 − 碰撞 − 代价);只留信息增益会乐不思蜀 | §U4.7 |
| RSSM 的隐状态是真实状态 | 是摊销 belief(对状态的信念的神经编码),非物理状态 | §U4.8 |
| 世界模型和 POMDP 不相干 | 世界模型是 POMDP 的摊销解;同一框架(belief-MDP) | §U4.8 |
| 先估计再控制(按均值)总能行 | 仅线性高斯成立(LQG 分离原理);一般 POMDP 估计与控制耦合,须在 belief 上联合决策 | 进阶十六 |
| POMDP 难(PSPACE)所以上不了实时 | 上车的是 anytime 近似解(DESPOT),不是精确解;anytime 让它塞进任意时间预算 | 进阶十五 |
本章小结¶
本章沿一条主线走完:状态看不清,就维护一个状态的概率分布(belief),把它当充分统计量,在 belief 空间上决策。POMDP 把"部分可观测"难题转成"在连续高维 belief 空间上做 MDP"——出路是用上 MDP 的全套机器(Bellman、值函数),难点是 belief 空间的两个 curse(维数 + 历史)。值函数 PWLC(α-vector)给出精确解的结构,但指数爆炸;于是一条近似谱展开:QMDP(最廉价、低估持续消歧)→ 点基 SARSOP(离线、可达 belief 上 \(\epsilon\)-最优)→ 在线树搜索 DESPOT(采样确定化稀疏树、output-sensitive、实时)→ GPU 加速(HyP-DESPOT)→ 学习辅助(MAGIC/LeTS-Drive/BetaZero)。连续高维 + 单峰场景有 belief-space planning(LQG-MP/RRBT/FIRM/BSP-iSAM)这条高斯特化支线;Active SLAM 是 POMDP 的实例(信息增益 = 奖励);DreamerV3 的 RSSM 是摊销 belief,与树搜索在 BetaZero 处合流。对 SLAM 工程师,belief update 就是你已会的滤波,POMDP 只是再加"在 belief 上 planning"。
术语速查表¶
| 术语(中 / 英) | 一句话定义 |
|---|---|
| POMDP(部分可观测马尔可夫决策过程) | 状态不可直接观测、只能通过带噪观测推断的序贯决策问题;七元组 \(\langle S,A,T,R,\Omega,O,\gamma\rangle\) |
| belief(信念) | 对状态的概率后验分布 \(b(s)\);POMDP 决策的依据 |
| belief update(信念更新 / 贝叶斯滤波) | \(b'(s')=\eta O(o\mid s',a)\sum_s T(s'\mid s,a)b(s)\),预测 + 校正 + 归一化 |
| 充分统计量(sufficient statistic) | 给定 belief,历史可遗忘——未来最优决策只依赖当前 belief |
| belief-MDP(信念空间 MDP) | 以 belief 为状态的完全可观测 MDP;POMDP 化归于此 |
| 观测模型(observation model) | \(O(o\mid s',a)\),到达 \(s'\) 时观测到 \(o\) 的概率;编码传感器不完美 |
| α-vector(α 向量) | 值函数的线性分片;\(\alpha(s)\) = 某条件计划在状态 \(s\) 的价值 |
| PWLC(分段线性且凸) | 有限视界 POMDP 最优值函数的形状(Sondik 1971):\(V^*(b)=\max_\alpha\alpha\cdot b\) |
| 条件计划(conditional plan) | 一个 α-vector 对应的"起始动作 + 依观测分支"的策略 |
| 维数灾难(curse of dimensionality) | belief 是 $ |
| 历史灾难(curse of history) | belief 树节点 $O( |
| QMDP | 假设一步后全可观测,用 MDP 的 Q 当 α;快但低估持续消歧 |
| FIB(Fast Informed Bound) | 比 QMDP 略紧的值函数上界(部分考虑观测) |
| 点基方法(point-based) | 只在可达 belief 点上备份,α-vector 数受点数限制 |
| PBVI / HSVI / SARSOP | 点基三代:开创 / 上下界引导 / 只盯最优可达 belief(事实标准离线求解器) |
| 可达 belief(reachable belief) | 从 \(b_0\) 出发能到达的 belief 子集(通常低维) |
| POMCP | belief 树上的 MCTS;粒子表示 belief、UCT、随机 rollout |
| MCTS / UCT | 蒙特卡洛树搜索 / 上置信界树搜索(探索-利用平衡) |
| DESPOT | 确定化稀疏 belief 树 + K 场景;在线 POMDP 事实标准 |
| 确定化场景(determinized scenario) | 起始状态 + 一串随机数,把随机执行确定化 |
| 稀疏 belief 树(sparse belief tree) | 保留全部动作分支、只留 K 场景经历的观测分支 |
| output-sensitive(输出敏感) | regret 界依最优策略表示大小、不依状态空间大小 |
| R-DESPOT / B-DESPOT | 正则化 / 基础版 DESPOT;前者加 \(\lambda\|\pi\|\) 防过拟合场景 |
| regret 界(后悔界) | 与真最优的差距上界;DESPOT 的界 output-sensitive |
| HyP-DESPOT | CPU 多线程 + GPU CUDA 并行的 DESPOT,加速 100–500× |
| DESPOT-α | α-vector 粒子近似 + 子策略共享,治大观测空间过度乐观 |
| Context-POMDP | HyP-DESPOT 的自驾实例(道路上下文 + 行人隐意图) |
| MAGIC | Generator-Critic 学宏动作,砍有效视界指数因子 |
| 宏动作(macro-action) | 多步动作的封装,缩短规划视界 |
| LeTS-Drive | 离线模仿树搜索 → 在线引导 HyP-DESPOT |
| POMCPOW | 连续空间在线 POMDP,用 Progressive Widening |
| Progressive Widening(渐进加宽) | 限制子节点数随访问缓增,防连续观测树退化 |
| belief-space motion planning(BSP,信念空间运动规划) | 假设高斯 belief 的连续空间规划支线 |
| LQG-MP | 沿候选路径传播 LQG 协方差、执行前评估碰撞概率 |
| ML 观测假设 | 假设未来观测 = 最大似然值,化归确定性优化(Platt 等) |
| RRBT / BRM | RRT* / PRM 进 belief 空间,节点带协方差 |
| FIRM | PRM 式 belief 图 + stationary LQG 节点控制器(破历史灾难) |
| BSP-iSAM | BSP 接 iSAM2 增量平滑,可微算未来信息增益(通 Active SLAM) |
| Active SLAM(主动 SLAM) | 决定"下一步去哪测最划算"的 POMDP;奖励含信息增益 |
| 信息增益(information gain) | 行动前后 belief 不确定性的下降(熵减 / 互信息) |
| D / A / E-optimality | 协方差标量化:行列式(体积)/ 迹(总和)/ 最大特征值(最坏方向) |
| Shannon 熵 / 互信息 | belief 不确定性 / 行动带来的期望信息量 |
| DreamerV3 | 神经世界模型;RSSM + latent imagination,跨域鲁棒 |
| RSSM(循环状态空间模型) | 确定性 \(h_t\)(GRU)+ 随机 \(z_t\);摊销 belief 表示 |
| 摊销 belief(amortized belief) | 把 belief update + 规划摊销进神经网络权重 |
| latent imagination(隐空间想象) | 在学到的世界模型里想象未来 = belief 空间策略评估 |
| BetaZero | AlphaZero 式价值 / 策略网 + belief-state MCTS(学搜合流) |
| Dec-POMDP(去中心化 POMDP) | 多智能体局部观测协作;有限视界 NEXP-complete |
| 高阶信念(higher-order belief) | 对他人信念的信念;Dec-POMDP 爆炸之源 |
| 风险敏感 POMDP | 把期望目标换成 CVaR 等风险度量(接 U5) |
| 粒子滤波 / SIR | 用状态样本近似 belief;重要性加权 + 重采样 |
| 粒子贫化(particle depletion) | 少数粒子占全部权重,belief 近似退化 |
知识点总表¶
| 编号 | 知识点 | 核心要点 | 对应节 | 难度 |
|---|---|---|---|---|
| K1 | POMDP 七元组 | MDP 加观测空间 \(\Omega\) + 观测模型 \(O\) | §U4.1 | ⭐⭐ |
| K2 | belief update | 贝叶斯滤波:预测 + 校正 + 归一化;= EKF / 粒子滤波 | §U4.1 | ⭐⭐ |
| K3 | belief 是充分统计量 | 给定 belief 历史可遗忘 → POMDP = belief-MDP | §U4.1 | ⭐⭐⭐ |
| K4 | belief 不是点估计 | 整个分布;均值丢不确定性 + 多峰 | §U4.1 | ⭐⭐ |
| K5 | PWLC 与 α-vector | \(V^*(b)=\max_\alpha\alpha\cdot b\)(Sondik 1971);每 α 是条件计划 | §U4.2 | ⭐⭐⭐ |
| K6 | 两个 curse | 维数(状态多)+ 历史(观测序列多);近似方法都在绕 | §U4.2、进阶二 | ⭐⭐⭐ |
| K7 | QMDP | 假设一步后全可观测;快但系统性低估持续消歧 | §U4.2 | ⭐⭐⭐ |
| K8 | 点基方法 | 只在可达 belief 上备份;α 数受点数限制;给下界 | §U4.3 | ⭐⭐⭐ |
| K9 | SARSOP | 只盯最优可达 belief;离线 \(\epsilon\)-最优事实标准 | §U4.3 | ⭐⭐⭐ |
| K10 | POMCP | belief 树 MCTS;粒子 belief;极限最优但最坏差 | §U4.4 | ⭐⭐⭐ |
| K11 | DESPOT 确定化稀疏树 | K 场景固化随机树;采状态破维数、采观测破历史 | §U4.4 | ⭐⭐⭐⭐ |
| K12 | output-sensitive 界 | regret 依最优策略大小、不依 $ | S | $ |
| K13 | R-DESPOT 正则化 | \(\lambda\|\pi\|\) 防过拟合场景(= ML 奥卡姆剃刀) | §U4.4 | ⭐⭐⭐ |
| K14 | DESPOT 家族演化 | 硬件(HyP)/ 领域(Context)/ 学习(MAGIC/LeTS)三轴 | §U4.5 | ⭐⭐⭐ |
| K15 | belief-space planning | 高斯 belief 的连续空间特化;高 DoF 但单峰 | §U4.6 | ⭐⭐⭐ |
| K16 | LQG-MP vs ML 观测 | 两篇不同 RSS 2010:协方差传播 vs 钉死观测 | §U4.6 | ⭐⭐⭐ |
| K17 | FIRM 破历史灾难 | stationary 控制器把节点 belief 钉成固定值 | §U4.6 | ⭐⭐⭐ |
| K18 | Active SLAM = POMDP | 信息增益 = 奖励;SLAM 技能成 belief update 子模块 | §U4.7 | ⭐⭐⭐ |
| K19 | D/A/E-optimality | 协方差标量化(体积 / 总和 / 最坏方向) | §U4.7 | ⭐⭐⭐ |
| K20 | RSSM = 摊销 belief | encoder = belief update、latent 规划 = belief 空间规划 | §U4.8 | ⭐⭐⭐⭐ |
| K21 | 两派合流 BetaZero | 学习提供先验 + 树搜索提供保证 | §U4.8 | ⭐⭐⭐⭐ |
| K22 | POMDP vs RL | POMDP 未知状态(要模型)、RL 未知模型(不要) | 进阶六 | ⭐⭐⭐ |
| K23 | Dec-POMDP | 多智能体局部观测;高阶信念;NEXP | 进阶七 | ⭐⭐⭐⭐ |
| K24 | 风险敏感 POMDP | 期望换 CVaR;与认知不确定正交叠加(接 U5) | 进阶八 | ⭐⭐⭐⭐ |
核心公式速查¶
| 公式 | 表达式 | 含义 / 出处 |
|---|---|---|
| belief update | \(b'(s')=\eta\,O(o\mid s',a)\sum_s T(s'\mid s,a)b(s)\) | 贝叶斯滤波(§U4.1);\(\eta\) 归一化 |
| belief-MDP 奖励 | \(\rho(b,a)=\sum_s b(s)R(s,a)\) | belief 上的期望奖励(§U4.1) |
| belief-MDP Bellman | \(V^*(b)=\max_a[\rho(b,a)+\gamma\sum_o\Pr(o\mid b,a)V^*(\tau(b,a,o))]\) | POMDP 化归 MDP(§U4.1) |
| PWLC 值函数 | \(V^*(b)=\max_{\alpha\in\Gamma}\alpha\cdot b\) | Sondik 1971(§U4.2) |
| QMDP 决策 | \(a^*=\arg\max_a\sum_s b(s)Q_{\text{MDP}}(s,a)\) | 信息盲极限(§U4.2) |
| 标准 belief 树规模 | $O( | A |
| DESPOT 树规模 | $O( | A |
| DESPOT 策略价值 | \(\hat V_\pi(b)=\frac1K\sum_k V_{\pi,\phi_k}\) | K 场景平均(§U4.4) |
| R-DESPOT 目标 | $\max_\pi[\hat V_\pi(b_0)-\lambda | \pi |
| 信息增益(熵减) | \(\mathrm{IG}(b,a)=H(b)-\mathbb{E}_o[H(\tau(b,a,o))]\) | = 互信息(§U4.7) |
| Shannon 熵 | \(H(b)=-\sum_s b(s)\log b(s)\) | belief 不确定性(§U4.7) |
| D-optimality | \(\det\Sigma\) 或 \(\log\det\Sigma\) | 不确定椭球体积(§U4.7) |
| CVaR(R-U 形式) | \(\mathrm{CVaR}_\alpha(L)=\min_t\{t+\frac1{1-\alpha}\mathbb{E}[(L-t)_+]\}\) | 风险敏感 POMDP(进阶八,接 U5) |
符号速查¶
| 符号 | 含义 |
|---|---|
| \(S,A,\Omega\) | 状态空间、动作空间、观测空间 |
| \(T(s'\mid s,a)\) | 状态转移概率 |
| \(O(o\mid s',a)\) | 观测模型 |
| \(R(s,a)\) | 奖励函数 |
| \(\gamma\) | 折扣因子 |
| \(b,b'\) | 当前 / 更新后的 belief |
| \(b(s)\) | belief 在状态 \(s\) 的概率 |
| \(\eta\) | belief update 归一化常数 \(1/\Pr(o\mid b,a)\) |
| \(\tau(b,a,o)\) | belief 转移算子(= belief update) |
| \(\rho(b,a)\) | belief 上的期望奖励 |
| \(\alpha\) | α-vector(值函数线性分片) |
| \(\Gamma\) | α-vector 集合 |
| \(V^*(b)\) | 最优值函数 |
| \(Q_{\text{MDP}}(s,a)\) | 全可观测 MDP 的 Q 值(QMDP 用) |
| \(\phi=(s_0,\phi_1,\dots)\) | 确定化场景(起始状态 + 随机数串) |
| \(K\) | DESPOT 场景数 |
| \(D\) | 搜索 / 树深度 |
| \(\lambda\) | R-DESPOT 正则系数 |
| $ | \pi |
| \(\Sigma\) | 协方差矩阵(BSP / Active SLAM) |
| \(H(b)\) | belief 的 Shannon 熵 |
| \(h_t,z_t\) | RSSM 的确定性 / 随机隐状态 |
| $ | S |
实践索引(一页纸)¶
需要做什么 → 去哪:
- 实现 belief update → 实现一(
belief_update);陷阱:归一化在校正后、assert sum=1(§U4.1)。 - 快速粗解 / 基准 → 实现二(QMDP);记住它低估持续消歧(§U4.2)。
- 在线规划(大 / 变模型) → 实现三(
despot_plan)+ 工程上用 C++ DESPOT;调 \(K/D/\lambda\)(§U4.4、调参)。 - 大 / 连续状态的 belief → 实现四(粒子 belief);监控粒子贫化、重采样(§U4.4、故障排查)。
- 主动感知 / Active SLAM → 实现五(信息增益)+ 加进奖励;别只留信息增益(§U4.7)。
- 高 DoF 连续 + 单峰 → BSP(LQG-MP/RRBT/FIRM);多峰别用(§U4.6、选型)。
- 图像 / 像素观测 → DreamerV3(RSSM);或 BetaZero 杂交(§U4.8)。
- 上车部署 → C++
despot,写DSPOMDP6–8 虚函数(§Python→C++)。 - 选方法 → 选型决策指南(单峰 / 多峰?固定 / 变模型?符号 / 图像?)。
- 调不出来 → 故障排查手册 + 调参诊断(先分清 belief 估计错还是规划错)。
延伸阅读¶
按难度与主题分类,均已核实。
教材 / 综述(入门 → 核心) - Kochenderfer, Wheeler, Wray, Algorithms for Decision Making, MIT Press, 2022(免费在线)——MDP/POMDP 决策算法的现代权威教材,POMDPs.jl 的理论底座。⭐⭐ - Thrun, Burgard, Fox, Probabilistic Robotics, MIT Press, 2005——贝叶斯滤波 / belief 的机器人经典,belief update 的源头。⭐⭐ - Lauri, Hsu, Pajarinen, "Partially Observable Markov Decision Processes in Robotics: A Survey", IEEE T-RO 39(1):21–40, 2023——机器人 POMDP 的最新综述,全景入口。⭐⭐⭐ - Placed, Strader, Carrillo, Atanasov, Indelman, Carlone, Castellanos, "A Survey on Active SLAM: State of the Art and New Frontiers", IEEE T-RO 39(3):1686–1705, 2023(arXiv:2207.00254)——Active SLAM 权威综述(§U4.7)。⭐⭐⭐
奠基论文(核心) - Sondik, The Optimal Control of Partially Observable Markov Processes, PhD thesis, Stanford, 1971——PWLC 定理的源头(§U4.2)。⭐⭐⭐⭐ - Kaelbling, Littman, Cassandra, "Planning and acting in partially observable stochastic domains", Artificial Intelligence 101:99–134, 1998(DOI 10.1016/S0004-3702(98)00023-X)——POMDP 标准化 + Tiger 问题出处(§U4.1)。⭐⭐⭐
求解器:点基与在线(核心 → 进阶) - Pineau, Gordon, Thrun, "Point-based value iteration: An anytime algorithm for POMDPs", IJCAI 2003——PBVI 开创点基(§U4.3)。⭐⭐⭐ - Smith, Simmons, "Heuristic search value iteration for POMDPs", UAI 2004(及 HSVI2, UAI 2005)——上下界引导(§U4.3)。⭐⭐⭐ - Kurniawati, Hsu, Lee, "SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces", RSS 2008(DOI 10.15607/RSS.2008.IV.009)——离线事实标准(§U4.3)。⭐⭐⭐ - Silver, Veness, "Monte-Carlo planning in large POMDPs", NeurIPS 2010——POMCP,belief 树 MCTS(§U4.4)。⭐⭐⭐ - Ye, Somani, Hsu, Lee, "DESPOT: Online POMDP Planning with Regularization", JAIR 58:231–266, 2017(arXiv:1609.03250;会议版 Somani-Ye-Hsu-Lee, NeurIPS 2013)——在线事实标准(§U4.4)。⭐⭐⭐⭐ - Sunberg, Kochenderfer, "Online algorithms for POMDPs with continuous state, action, and observation spaces", ICAPS 2018——POMCPOW,连续空间(进阶三)。⭐⭐⭐⭐
GPU / 学习辅助(进阶 → 研究级) - Cai, Luo, Hsu, Lee, "HyP-DESPOT: A hybrid parallel algorithm for online planning under uncertainty", RSS 2018——GPU 并行(§U4.5)。⭐⭐⭐⭐ - Cai, Hsu, Lee, "Context-POMDP" 系列 / SUMMIT 模拟器, ICRA 2020——自驾意图感知(§U4.5)。⭐⭐⭐⭐ - Lee, Cai, Hsu, Lee, "MAGIC: Learning Macro-Actions for Online POMDP Planning", RSS 2021——学宏动作(§U4.5)。⭐⭐⭐⭐ - Cai, Hsu, et al., "LeTS-Drive" / 引导 HyP-DESPOT, RSS 2019 / T-RO 2023——学引导树搜索(§U4.5)。⭐⭐⭐⭐ - Moss, Corso, Caldwell, Kochenderfer, "BetaZero: Belief-State Planning for Long-Horizon POMDPs using Learned Approximations", RLC 2024(arXiv:2306.00249)——学搜合流(§U4.8)。⭐⭐⭐⭐ - Hafner, Pasukonis, Ba, Lillicrap, "Mastering Diverse Domains through World Models"(DreamerV3), 2023(arXiv:2301.04104)——RSSM = 摊销 belief(§U4.8)。⭐⭐⭐⭐
Belief-space motion planning(进阶) - van den Berg, Abbeel, Goldberg, "LQG-MP: Optimized path planning for robots with motion uncertainty and imperfect state information", RSS 2010 / IJRR 30(7):895–913, 2011(§U4.6)。⭐⭐⭐ - Platt, Tedrake, Kaelbling, Lozano-Pérez, "Belief space planning assuming maximum likelihood observations", RSS 2010——与 LQG-MP 不同的工作(§U4.6)。⭐⭐⭐ - Prentice, Roy, "The belief roadmap: Efficient planning in belief space by factoring the covariance", IJRR 28(11–12):1448–1465, 2009——BRM(§U4.6)。⭐⭐⭐ - Bry, Roy, "Rapidly-exploring random belief trees for motion planning under uncertainty", ICRA 2011——RRBT(§U4.6)。⭐⭐⭐ - Agha-mohammadi, Chakravorty, Amato, "FIRM: Sampling-based feedback motion-planning under motion uncertainty and imperfect measurements", IJRR 33(2):268–304, 2014(§U4.6)。⭐⭐⭐⭐ - Indelman, Carlone, Dellaert, "Planning in the continuous domain: A generalized belief space approach for autonomous navigation in unknown environments", IJRR 34(7):849–882, 2015——BSP-iSAM(§U4.6/U4.7)。⭐⭐⭐⭐
开源代码:AdaCompNUS/despot、AdaCompNUS/hyp-despot、AdaCompNUS/sarsop、JuliaPOMDP/POMDPs.jl、h2r/pomdp-py、RDLLab/oppt、ethz-asl/mav_active_3d_planning(详见"工具与源码精读清单")。
综合练习¶
跨节 / 跨章的综合题,检验是否把 POMDP 织进了整张知识网。
-
[跨节·端到端 POMDP] 用本章实现拼一个 2D 主动定位导航器(综合实战):粒子 belief(实现四)+ DESPOT 式规划(实现三)+ 信息增益奖励(实现五)。在对称走廊里验证:belief 多峰、主动消歧、信息增益提升成功率。串起 §U4.1/U4.4/U4.7。
-
[跨章·U4 × U1] U1 的分支规划把"他车意图"当离散隐状态、用引导分支近似 POMDP;§U4.4 说 belief 树 = 被引导的 contingency 树。请:(a)把 U1 的 EUDM 意图分支重新表述为一个 POMDP(写出 \(S,A,\Omega,O\),意图是隐状态);(b)对比 EUDM 的"引导分支剪枝"与 DESPOT 的"K 场景稀疏化"在破历史灾难上的异同;(c)讨论何时用 U1 引导分支、何时用 DESPOT。
-
[跨章·U4 × U3] U4 处理感知端不确定(belief),U3 处理动力学端概率约束(chance constraint)。设计一个"感知不确定 + 概率安全"的规划:在 belief 的每个粒子上施加 U3 的 \(\Pr(\text{碰撞})\le\delta\) 约束。请写出这个联合问题的形式,并讨论:belief 的不确定性如何影响可行的 \(\delta\)(提示:belief 越散,满足同样 \(\delta\) 越难)。
-
[跨章·五安全谱] 回顾 U0 五安全谱:U2(鲁棒 100%)、U3(机会约束 \(\delta\))、U5(CVaR 尾部)、U4(POMDP 信念 / 感知端)、U1(分支 / 交互端)。请画一张表,对每条谱列出:它处理哪类不确定性(动力学 / 交互 / 感知 / 尾部)、用什么数学对象(tube / \(\delta\) / CVaR / belief / 分支树)、何时该用。然后论证:为什么 U4 与 U2/U3 正交、可叠加(提示:一个管"状态看不清"、一个管"状态会变")。
-
[思考题·QMDP 的真相] §U4.2 澄清了"QMDP 不 listen"是误传。请:(a)实跑实现二,记录 QMDP 在 Tiger 上从均匀 belief 听几次后开门;(b)解释为什么 \(Q_{\text{MDP}}(s,\text{listen})=189\) 这么高(提示:全可观测续值 200);(c)构造 / 描述一个 QMDP 会明显失败(消歧严重不足)的问题——它需要满足什么特征?
-
[思考题·摊销 vs 现算] RSSM(Dreamer)摊销 belief、DESPOT 现算树。请论证:"它们求解同一个问题(belief-MDP),只是一个把 belief update + 规划摊销进网络权重、一个每周期现算"。然后讨论 BetaZero 如何取两者之长,以及这与 U1 §U1.7"神经化分支"、§U4.5"LeTS-Drive 学引导"是不是同一潮流。
-
[跨节·分离原理] 用一个线性高斯 1D 定位 + 调节任务,验证 LQG 分离原理(卡尔曼估均值 + LQR 控制 = 最优、按均值控制即可);再把它改成一个**双峰**初始 belief 的非线性版,验证"按均值控制"失效(均值落在两峰中间、决策荒谬)。结合进阶十六论证:为什么前者可解耦、后者必须在 belief 上联合决策。
-
[B 型·读 DESPOT 源码] 精读
AdaCompNUS/despot的src/solver/despot.cpp(约 500 行),画出 Explore → Expand → Backup → Prune 的完整循环,并标注:(a)确定化场景在哪里采样(起始状态 + 随机数);(b)上下界在哪里更新、如何引导 Explore;(c)R-DESPOT 的正则化(\(\lambda|\pi|\))在哪一步生效。对照本章实现三的简化版,说清工业级 DESPOT 比它多了哪些机制(anytime 上下界、正则化、剪枝)。
本章各节关系¶
各节如何环环相扣:
| 节 | 解决什么 | 依赖 | 为后文铺垫 |
|---|---|---|---|
| §U4.1 形式化与 belief | POMDP 是什么、belief 怎么更新、为什么是充分统计量 | MDP、贝叶斯滤波 | 全章地基(belief-MDP) |
| §U4.2 α-vector / PWLC | 值函数长什么样、为什么精确求解爆炸 | §U4.1 belief-MDP | 近似方法的动机(两个 curse) |
| §U4.3 点基 / SARSOP | 离线近似:只在可达 belief 上备份 | §U4.2 α-vector | 在线方法的对照(离线 vs 在线) |
| §U4.4 DESPOT | 在线近似:采样确定化稀疏树 | §U4.2 两个 curse、§U4.3 上下界、U1 MCTS | §U4.5 家族的骨架 |
| §U4.5 DESPOT 家族 | 从能跑到上车(GPU / 领域 / 学习) | §U4.4 DESPOT | §U4.8 学习辅助合流 |
| §U4.6 belief-space planning | 连续高维 + 单峰的高斯特化 | §U4.1 belief、卡尔曼 | §U4.7 BSP-iSAM 通 Active SLAM |
| §U4.7 Active SLAM | POMDP 实例:信息增益 = 奖励 | §U4.1 belief、§U4.6 BSP-iSAM | 累积项目主动感知模块 |
| §U4.8 DreamerV3 | 摊销 belief、两派合流 | §U4.1 充分统计量、§U4.4 树搜索 | 接 RL / 世界模型方向 |
主线串联:§U4.1 立地基(belief = 充分统计量 → belief-MDP)→ §U4.2 看值函数(PWLC + 两个 curse)→ §U4.3/U4.4/U4.5 近似求解谱(点基离线 → 在线树搜索 → 家族演化)→ §U4.6/U4.7 连续 / 主动支线 → §U4.8 神经摊销与合流。
本章与后续章节的关系¶
| 后续章节 | 关系 | 本章铺垫的知识点 |
|---|---|---|
| U5 风险敏感规划(CVaR) | U4 默认最大化期望;U5 把目标换成 CVaR 等风险度量。风险敏感 POMDP(进阶八)是两者的交点——在不确定 belief 上用风险敏感目标决策 | belief-MDP(§U4.1)、CVaR 的 R-U 形式(进阶八)、期望 vs 尾部的辨析 |
| U5 / 五安全谱收官 | U4(感知端认知不确定)与 U2/U3(动力学端)、U1(交互端)、U5(尾部风险)正交,合成完整五安全谱 | belief 与动力学不确定的正交性(§U4.1、进阶八) |
| Part-U 附录 | 附录汇总 Part-U 的统一测试台、跨章对照、选型总表 | 累积项目 U4 模块、方法选型决策指南 |
| RL / 世界模型方向 | RSSM = 摊销 POMDP(§U4.8)、POMDP vs RL(进阶六)为"部分可观测 RL / 世界模型"打底 | RSSM、latent imagination、POMDP-RL 关系 |
| 多机器人方向 | Dec-POMDP(进阶七)是多机器人协作在部分可观测下的形式化 | 高阶信念、CTDE、通信 |
衔接 U5:本章把"状态看不清"讲透了(认知不确定),但通篇最大化**期望**回报。U5 要问的是另一个正交问题——即使给定 belief,未来回报也有分布,你在乎它的**尾部**(最坏情况)吗?把 §U4 的 belief 空间规划和 U5 的 CVaR 目标结合,就是"风险敏感的信念空间规划",也是 Part-U 五安全谱的收官。
研究实践建议¶
分层次的上手 / 深入建议:
- 入门(建立直觉 + 跑通):读 §U4.1/U4.2 + 跑本章五个实现;用
pomdp-py(Python)跑 Tiger 的 POMCP;理解 belief = 充分统计量、两个 curse。 - 工程(上手主力工具):编译运行
AdaCompNUS/despot的 Tiger / RockSample;改写DSPOMDP定义自己的小 POMDP;用不同 \(K\)/depth 观察策略-时间权衡;想要 GPU 上hyp-despot。 - 接 SLAM(发挥已有技能):把你的 SLAM belief update 接成 POMDP 子模块;读 BSP-iSAM(在 iSAM2 因子图里算未来信息增益);跑
mav_active_3d_planning做主动建图。 - 接学习 / 世界模型:读 DreamerV3 的 RSSM(标出 encoder = belief update、predictor = 预测);读 BetaZero(学引导 belief MCTS);理解"学习提供先验、搜索提供保证"的混合范式。
- 研究切入:从"前沿与开放问题"挑——3DGS/NeRF 作观测模型、Dec-POMDP 可扩展、DESPOT × PyTorch 桥接;或风险敏感 POMDP(接 U5)。
- 避坑:别照搬"QMDP 不 listen"(实跑验证,§U4.2);分清 LQG-MP 与 ML 观测假设(§U4.6);多峰别用高斯 BSP(§U4.6);belief 调不出来先分清估计错还是规划错(故障排查)。
版本信息速查¶
本章引用的关键工作与版本(便于查证):
| 对象 | 版本 / 年份 / 出处 |
|---|---|
| POMDP 标准化 | Kaelbling-Littman-Cassandra, AIJ 101:99–134, 1998 |
| PWLC 定理 | Sondik PhD thesis, Stanford, 1971 |
| SARSOP | Kurniawati-Hsu-Lee, RSS 2008, DOI 10.15607/RSS.2008.IV.009 |
| POMCP | Silver-Veness, NeurIPS 2010 |
| DESPOT | NeurIPS 2013(会议)/ JAIR 58, 2017(期刊, arXiv:1609.03250) |
| HyP-DESPOT | Cai-Luo-Hsu-Lee, RSS 2018 |
| DESPOT-α | RSS 2019 |
| MAGIC | Lee-Cai-Hsu, RSS 2021 |
| POMCPOW | Sunberg-Kochenderfer, ICAPS 2018 |
| BetaZero | Moss et al., RLC 2024, arXiv:2306.00249 |
| DreamerV3 | Hafner et al., 2023, arXiv:2301.04104 |
| LQG-MP | van den Berg-Abbeel-Goldberg, RSS 2010 / IJRR 30(7):895–913, 2011 |
| ML 观测假设 | Platt-Tedrake-Kaelbling-Lozano-Pérez, RSS 2010 |
| FIRM | Agha-mohammadi-Chakravorty-Amato, IJRR 33(2):268–304, 2014 |
| BSP-iSAM | Indelman-Carlone-Dellaert, IJRR 34(7):849–882, 2015 |
| Active SLAM 综述 | Placed et al., IEEE T-RO 39(3):1686–1705, 2023, DOI 10.1109/TRO.2023.3248510 |
| despot 代码库 | AdaCompNUS/despot, GPL-3.0, C++ |
| POMDPs.jl | JuliaPOMDP/POMDPs.jl, MIT, Julia |
附录:前置自测参考答案¶
- MDP 五元组与 Bellman:\(\langle S,A,T,R,\gamma\rangle\);最优值 \(V^*(s)=\max_a[R(s,a)+\gamma\sum_{s'}T(s'\mid s,a)V^*(s')]\)。POMDP 在此之上加观测空间 \(\Omega\) + 观测模型 \(O\),并把"状态"换成"belief"(§U4.1)。
- 贝叶斯滤波:给定先验 \(b(s)\)、控制 \(a\)、观测 \(o\),先用运动模型预测(\(\sum_s T(s'\mid s,a)b(s)\),不确定性增大),再用观测似然校正(乘 \(O(o\mid s',a)\),不确定性减小),归一化。这就是 belief update(§U4.1)。
- 充分统计量:包含了原始数据中所有与目标相关信息的统计量——有了它,原始数据可丢弃而不损失推断 / 决策能力。belief 是 POMDP 历史的充分统计量(§U4.1 本质洞察)。
- U1 分支规划维护意图分布:U1 对他车意图维护一个离散概率分布、在共享干 + 加权分支树上决策;它是对"离散不可观测意图"的 belief 树近似(EUDM 显式称"POMDP + 引导分支")——本章 §U4.4 接上这条线。
- MCTS 四步 + UCB:选择(按 UCB 下探)→ 扩展(加新节点)→ 模拟(rollout 估值)→ 反向传播(更新 \(N/Q\));UCB \(=\bar Q+c\sqrt{\ln N/n}\) 平衡利用(\(\bar Q\))与探索(访问少的项加成)。POMCP/DESPOT 把它搬到 belief 树(§U4.4)。
结语¶
POMDP 给了不确定性规划一块此前缺失的拼图:当你连自己处在什么状态都看不清时,如何理性决策。它的答案优雅而统一——维护一个状态的概率分布(belief),证明它是充分统计量,于是"部分可观测"化归"在 belief 空间上做 MDP"。这一化归既是出路(MDP 全套机器可用),也定义了全部难度(belief 空间连续高维、两个 curse)。本章的近似谱——QMDP、点基 SARSOP、在线 DESPOT 全家族、belief-space planning、神经摊销 RSSM——本质都是在回答同一个问题:belief 空间这么大,到底在哪一小块上、用什么方式求解。
对 SLAM 工程师,本章最该带走的是:你已经会 belief update(那就是你的滤波器),POMDP 只是教你在 belief 上做决策;Active SLAM 就是把这两半缝起来,让机器人自己决定"下一步去哪里看最划算"。对做学习 / 世界模型的读者,最该带走的是:RSSM 是 POMDP 的摊销解,世界模型与经典 POMDP 求解同一个 belief-MDP——这把两个看似无关的领域统一了,也是 BetaZero 能学搜合流的根由。
回到 U0 的五安全谱:U4 占据"感知端认知不确定"这一维——它与 U2/U3 的动力学端、U1 的交互端正交,可层层叠加。但本章通篇最大化期望回报,回避了一个正交问题:即使给定 belief,未来回报也有分布,你在乎它的尾部吗?这正是 U5(风险敏感规划,CVaR) 要展开的——把本章的信念空间规划与 CVaR 目标结合,就是"风险敏感的信念空间规划",也是 Part-U 五安全谱的收官。状态看不清已经处理了;接下来,处理"看清了也可能很糟"的尾部风险。