跳转至

POMDP 与信念空间规划:当你看不清世界时如何决策

不确定性规划方向(Part-U)第 4 章。上承 U0 总论的"五安全谱",本章处理**感知端的认知不确定性**——"我看不清世界"。这与 U2(鲁棒,动力学端有界扰动)、U3(机会约束,动力学端概率扰动)、U1(分支,交互端离散意图)正交:那几章假设状态可观测、只是演化不确定;本章连**状态本身**都看不清,只能通过带噪观测推断。对 SLAM 工程师而言这是最自然的延伸——SLAM 的状态估计就是 belief update 的工程实现,POMDP 只是在它之上加"如何用 belief 做决策"。


前置自测

开始前先自测。以下问题答不出 2 道及以上,建议先回到对应前置章节。

  1. 写出马尔可夫决策过程(MDP)的五元组 \(\langle S,A,T,R,\gamma\rangle\),并说明值函数 \(V^*(s)\) 满足的 Bellman 最优方程。(→ 若答不出,回 U0 §3 或 MDP/DP 基础)
  2. EKF / 粒子滤波在做什么?给定上一时刻的状态分布、一个控制、一个观测,它如何更新状态分布?(→ 回 SLAM 状态估计 / 贝叶斯滤波)
  3. 什么是充分统计量(sufficient statistic)?为什么有了它就可以"扔掉"原始数据?
  4. U1 的分支规划用"共享干 + 分支"处理离散意图不确定性。它对"他车意图"维护了什么?为什么说它是 POMDP 的一种近似?(→ 回 U1 §U1.3/§U1.4)
  5. 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)。


本章目标

学完本章,你应该能够:

  1. 写出 POMDP 的七元组形式化,推导 belief update(贝叶斯滤波),并说清 **belief 是充分统计量**的意义——为什么它把整段历史压缩成当前的一个分布。
  2. 解释 POMDP 如何转化为 belief 空间上的 MDP,以及为什么这个转化既是出路(可用 MDP 工具)又是难点(状态空间变成连续高维单纯形)。
  3. 理解 α-vector 与 PWLC 值函数(Sondik 定理)——POMDP 精确求解的数学基础,以及为什么精确解随视界指数爆炸。
  4. 说清从精确到近似的路线:QMDP(最廉价近似)→ 点基方法(SARSOP,离线、在可达 belief 上备份)→ 在线树搜索(POMCP/DESPOT)。
  5. 掌握 DESPOT 的确定化稀疏 belief 树:K 个确定化场景如何把随机 belief 树固化为稀疏树、output-sensitive 性能界、R-DESPOT 正则化。
  6. 梳理 DESPOT 家族演化:DESPOT → HyP-DESPOT(GPU)→ Context-POMDP(自驾)→ DESPOT-α / MAGIC / LeTS-Drive(学习辅助)。
  7. 理解 belief-space motion planning(LQG-MP / ML 观测假设 / RRBT / FIRM / BSP-iSAM)是 POMDP 在"高斯 belief + 连续空间"下的特化,并说清 Active SLAM = POMDP 实例(信息增益 = 奖励)。
  8. 建立 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 按**贝叶斯滤波**更新:

\[b'(s') = \eta\, \underbrace{O(o\mid s',a)}_{\text{观测校正}}\, \underbrace{\sum_{s} T(s'\mid s,a)\, b(s)}_{\text{运动预测}},\]

其中 \(\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 最优方程照搬:

\[V^*(b)=\max_{a}\Big[\rho(b,a)+\gamma\sum_{o}\Pr(o\mid b,a)\,V^*\big(\tau(b,a,o)\big)\Big].\]

本质洞察: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)。

练习

  1. [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。
  2. [A 型·感知混淆] 构造一个 4 状态走廊,其中状态 1 和状态 3 的观测模型完全相同(感知混淆)。从在 1、3 上各半的 belief 出发,反复"原地观测",验证 belief 不收敛(保持双峰);再加一个"前进"动作让机器人离开混淆区,验证 belief 这时才收敛。
  3. [思考题] 为什么说 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)**。它可以写成有限个线性函数取上包络:

\[V^*(b) = \max_{\alpha \in \Gamma}\ \sum_{s} \alpha(s)\, b(s) = \max_{\alpha\in\Gamma}\ \alpha\cdot b,\]

其中 \(\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_H| \sim |A|^{?}\times|\Gamma_{H-1}|^{|\Omega|},\]

每多一步视界,规模以 \(|\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)。精确求解只用于很小的问题或理论分析。

练习

  1. [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 的近似本质:它用"下一步全可观测"的假设给动作估值,因此**系统性低估"持续消歧"的长期价值**——在需要长时间消歧的更难问题上会过早行动。
  2. [A 型·PWLC 可视化] 取一个 2 状态 POMDP(belief 是 \([0,1]\) 上的一个数 \(p=b(s_1)\)),给定 3 个 α-vector(各是一条直线 \(\alpha\cdot b\)),画出它们的上包络 \(V^*(p)=\max_\alpha\alpha\cdot b\)。标出每段由哪个 α 主导、对应哪个动作。验证上包络是凸的分段线性曲线。
  3. [思考题] 为什么 \(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:

\[\alpha_b=\arg\max_{\alpha\in\text{backup}(b)}\ \alpha\cdot b,\qquad \text{backup}(b)\ \text{枚举}\ \big(a,\ \{o\mapsto\text{选哪个旧}\alpha\}\big).\]

直觉:对每个动作 \(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\)-最优解;它常被当作"准最优"基准来校准在线方法。

练习

  1. [A 型·朴素点基备份] 在 Tiger 问题上实现最简点基价值迭代:固定一组 belief 点(如 \(\{0,0.1,\dots,1\}\) 上的 11 个点),迭代做点基 Bellman 备份,画出值函数下界随迭代的上升。对比 QMDP(§U4.2 练习),验证点基解会选 listen(看得见信息价值)而 QMDP 不会。
  2. [A 型·上下界 gap] 给 Tiger 维护一个简单上界(如 \(V_{\text{MDP}}\),假设全可观测的值)和点基下界,画出两者的 gap 随迭代收窄。理解 HSVI/SARSOP 为什么用 gap 引导采样。
  3. [思考题] 为什么 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 时优化一个**正则化目标**

\[\max_{\pi}\ \Big[\underbrace{\hat V_\pi(b_0)}_{\text{$K$ 场景平均回报}}\ -\ \underbrace{\lambda\,|\pi|}_{\text{策略大小惩罚}}\Big],\]

其中 \(|\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)。

练习

  1. [A 型·确定化场景] 实现"场景 = 起始状态 + 随机数串":写一个 step(state, action, rand_seq) 用预定随机数序列做确定性转移 + 观测。验证:同一随机数串 + 不同动作序列 → 不同确定轨迹;不同随机数串 + 同动作序列 → 不同轨迹。理解场景为何能"确定化"随机执行。
  2. [A 型·K 的影响] 在 Tiger(或 RockSample)上跑一个 DESPOT 式在线规划器(可用 §完整实现精读的简化版),分别用 \(K=10,50,200\) 场景,记录策略质量(平均回报)与单步规划耗时。验证 \(K\) 越大越好但越慢——理解"为什么 \(K=500\)\(K=50\) 更好但更慢"。
  3. [B 型·稀疏树画图] 给一个 \(|A|=2,|Z|=2,D=3\) 的小 POMDP,分别画出(a)完整 belief 树(\(O(|A|^D|Z|^D)\) 节点)和(b)\(K=3\) 个场景下的 DESPOT(只留场景经历的观测分支)。数一数两者节点数,直观感受"稀疏"省了多少。
  4. [思考题] 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_DSPOMDPDvc_ = 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 学习"二选一,而是"学习引导搜索"——既要学习的样本效率,又要搜索的可验证性。

练习

  1. [A 型·宏动作] 在一个格子世界 POMDP 上,对比"单步动作"和"宏动作(如'向北走 3 格')"两种动作空间下的规划树深度与节点数。验证宏动作如何把有效视界缩短、树变小——理解 MAGIC 的动机。
  2. [B 型·HyP-DESPOT 接口精读] 阅读 AdaCompNUS/hyp-despotDvc_DSPOMDP GPU 接口,对比 CPU 端 DSPOMDP,找出哪些函数被移到 GPU(设备端)执行、为什么是这几个(提示:并行 rollout 里被 \(K\) 个场景反复调用的那些)。
  3. [思考题] 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)。

练习

  1. [A 型·协方差传播评估路径] 实现 LQG-MP 的核心:给两条候选路径(一条短但靠近障碍、一条长但远离障碍),用 LQG 沿路径传播协方差,算各自的碰撞概率,选更可靠的。验证"短路径不一定更优"(不确定性可能让它碰撞概率更高)。
  2. [A 型·ML 观测假设] 在一个 1D 定位问题上,对比"真实随机观测"和"ML 观测假设(观测=期望值)"下 belief 的演化。验证:信息量高(观测准)时两者接近;信息量低 / 歧义大时 ML 假设失真。理解 Platt 等方法的适用边界。
  3. [B 型·BSP-iSAM 与因子图] 精读 Indelman–Carlone–Dellaert 2015,理解(a)如何在 iSAM2 因子图里计算"未来信息增益"、(b)它与你在 SLAM 里用的 GTSAM 因子图是什么关系。写出"未来信息增益"作为一个可加因子的形式。
  4. [思考题] 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\) 的原因。

练习

  1. [A 型·2D 格子 Active SLAM] 在 2D 占据栅格世界实现最简 Active SLAM:(1)占据栅格 + 位姿不确定作为 belief;(2)信息增益(如未知格子的熵减)作为奖励;(3)贪心选信息增益最大的方向。对比贪心 Active 探索 vs 随机游走的地图覆盖速度,验证主动探索更快。
  2. [A 型·D/A/E 对比] 给一个 2×2 协方差矩阵,分别算 D-(\(\log\det\))、A-(trace)、E-(\(\lambda_{\max}\))optimality,构造一个例子让三者给出不同的"哪个动作信息增益大"的判断。理解三准则各偏好降低哪种不确定性(体积 / 总和 / 最坏方向)。
  3. [思考题] 为什么信息增益奖励是 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 的组成):

  1. 重构观测:从 \((h_t,z_t)\) 解码回观测 \(x_t\)(保证隐状态编码了观测信息)。
  2. 预测奖励(及连续性):从隐状态预测奖励(保证隐状态对决策有用)。
  3. 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 能把它们接起来的根本原因。

练习

  1. [A 型·摊销 vs 现算] 概念对比实验:在一个小 POMDP 上,(a)用 DESPOT 式在线规划(每步现算);(b)训练一个小网络模仿 DESPOT 的输出(摊销)。对比在训练分布内 / 外的性能与单步耗时。验证摊销快但训练分布外退化。
  2. [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"。
  3. [思考题] 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.1pred 是运动预测(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.4starts = 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.7entropy(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,写 DSPOMDP 6–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/despotAdaCompNUS/hyp-despotAdaCompNUS/sarsopJuliaPOMDP/POMDPs.jlh2r/pomdp-pyRDLLab/opptethz-asl/mav_active_3d_planning(详见"工具与源码精读清单")。


综合练习

跨节 / 跨章的综合题,检验是否把 POMDP 织进了整张知识网。

  1. [跨节·端到端 POMDP] 用本章实现拼一个 2D 主动定位导航器(综合实战):粒子 belief(实现四)+ DESPOT 式规划(实现三)+ 信息增益奖励(实现五)。在对称走廊里验证:belief 多峰、主动消歧、信息增益提升成功率。串起 §U4.1/U4.4/U4.7。

  2. [跨章·U4 × U1] U1 的分支规划把"他车意图"当离散隐状态、用引导分支近似 POMDP;§U4.4 说 belief 树 = 被引导的 contingency 树。请:(a)把 U1 的 EUDM 意图分支重新表述为一个 POMDP(写出 \(S,A,\Omega,O\),意图是隐状态);(b)对比 EUDM 的"引导分支剪枝"与 DESPOT 的"K 场景稀疏化"在破历史灾难上的异同;(c)讨论何时用 U1 引导分支、何时用 DESPOT。

  3. [跨章·U4 × U3] U4 处理感知端不确定(belief),U3 处理动力学端概率约束(chance constraint)。设计一个"感知不确定 + 概率安全"的规划:在 belief 的每个粒子上施加 U3 的 \(\Pr(\text{碰撞})\le\delta\) 约束。请写出这个联合问题的形式,并讨论:belief 的不确定性如何影响可行的 \(\delta\)(提示:belief 越散,满足同样 \(\delta\) 越难)。

  4. [跨章·五安全谱] 回顾 U0 五安全谱:U2(鲁棒 100%)、U3(机会约束 \(\delta\))、U5(CVaR 尾部)、U4(POMDP 信念 / 感知端)、U1(分支 / 交互端)。请画一张表,对每条谱列出:它处理哪类不确定性(动力学 / 交互 / 感知 / 尾部)、用什么数学对象(tube / \(\delta\) / CVaR / belief / 分支树)、何时该用。然后论证:为什么 U4 与 U2/U3 正交、可叠加(提示:一个管"状态看不清"、一个管"状态会变")。

  5. [思考题·QMDP 的真相] §U4.2 澄清了"QMDP 不 listen"是误传。请:(a)实跑实现二,记录 QMDP 在 Tiger 上从均匀 belief 听几次后开门;(b)解释为什么 \(Q_{\text{MDP}}(s,\text{listen})=189\) 这么高(提示:全可观测续值 200);(c)构造 / 描述一个 QMDP 会明显失败(消歧严重不足)的问题——它需要满足什么特征?

  6. [思考题·摊销 vs 现算] RSSM(Dreamer)摊销 belief、DESPOT 现算树。请论证:"它们求解同一个问题(belief-MDP),只是一个把 belief update + 规划摊销进网络权重、一个每周期现算"。然后讨论 BetaZero 如何取两者之长,以及这与 U1 §U1.7"神经化分支"、§U4.5"LeTS-Drive 学引导"是不是同一潮流。


  1. [跨节·分离原理] 用一个线性高斯 1D 定位 + 调节任务,验证 LQG 分离原理(卡尔曼估均值 + LQR 控制 = 最优、按均值控制即可);再把它改成一个**双峰**初始 belief 的非线性版,验证"按均值控制"失效(均值落在两峰中间、决策荒谬)。结合进阶十六论证:为什么前者可解耦、后者必须在 belief 上联合决策。

  2. [B 型·读 DESPOT 源码] 精读 AdaCompNUS/despotsrc/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

附录:前置自测参考答案

  1. 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)。
  2. 贝叶斯滤波:给定先验 \(b(s)\)、控制 \(a\)、观测 \(o\),先用运动模型预测(\(\sum_s T(s'\mid s,a)b(s)\),不确定性增大),再用观测似然校正(乘 \(O(o\mid s',a)\),不确定性减小),归一化。这就是 belief update(§U4.1)。
  3. 充分统计量:包含了原始数据中所有与目标相关信息的统计量——有了它,原始数据可丢弃而不损失推断 / 决策能力。belief 是 POMDP 历史的充分统计量(§U4.1 本质洞察)。
  4. U1 分支规划维护意图分布:U1 对他车意图维护一个离散概率分布、在共享干 + 加权分支树上决策;它是对"离散不可观测意图"的 belief 树近似(EUDM 显式称"POMDP + 引导分支")——本章 §U4.4 接上这条线。
  5. 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 五安全谱的收官。状态看不清已经处理了;接下来,处理"看清了也可能很糟"的尾部风险。