第十六章：POMDP的近似技术

16.1 动机

在之前的章节中，我们已经研究了两种在不确定性场景下主要的动作选择框架: MDPs和POMDPs。这两种框架都处理非确定性的动作结果，他们的不同之处在于对处理传感器限制的兼容性上。只有POMDP算法可以处理感知中的不确定性，而MDP算法假设状态是完全可观测的。但是，POMDP的计算开销使得准确的算法几乎不能解决任何实际的机器人问题。

本章讨论POMDP算法的这些问题。我们将会看到，MDP和POMDP是可能的概率学规划和控制算法谱系中的两个极端。本章综述了一些近似POMDP技术，它们介于MDP和POMDP之间。这里讨论的算法与POMDP一样使用置信度空间的值迭代。他们以很多种形式对值函数近似。这样，他们大大的加速了POMDP的方案。

本章中研究的技术代表了不同类型的近似方法。具体的，我们将讨论如下的三种算法:

QMDP是一种MDPs和POMDPs的混合方法。该算法将定义在状态上的MDP最优值函数，扩展到了在置信度上的POMDP类型的值函数。QMDP建立在一个常常不成立的假设上(usually false-assumption)，在完成一步控制之后，状态就变成可观测的了。在QMDPs中的值迭代具有与MDPs的一样的复杂度。
扩展的MDP，简称AMDP。这种算法将置信度状态映射到一个低维的充分统计量上，并在这个低维空间中进行值迭代。最基本的实现涉及到一个组合表示形式，将最可能的状态与不确定度组合起来，通过熵来测量。因此其规划比在MDPs中规划的效率略差一点，但是结果可以得到显著的提高。
蒙特卡洛POMDP(MC-POMDP)。这是一种粒子滤波器版本的POMDP算法，它使用粒子来近似表达置信度。通过动态的构建一个置信度点集合，就像上一章中最后提到的PBVI算法中描述的那样， MC-POMDPs可以维护一个相对较小的置信度集合。MC-POMDPs可以用于连续的值状态、动作和测量值上，但是他们受限于我们在粒子滤波器应用中提到的相同的限制，以及一些MC-POMDPs特有的限制。

这些算法覆盖了一些在概率学规划和控制中的主要的值函数近似技术。

16.2 QMDPs

QMDPs是一种将MDPs和POMDPs的优点的组合的尝试。MDPs的值函数相比于POMDPs更容易计算，但是MDPs依赖于状态时完全可观测的假设。QMDP在计算上具有与MDP一样的效率，但是它返回的策略是定义在置信度状态上的。

其所用的数学技巧是比较直接的。在第十四章中讨论的MDP算法为我们提供了一个基于状态的值函数，它在状态是完全可观测的假设下是最优的。如此得到的值函数$\hat{V}$就是定义在世界状态上的。QMDP通过如下的数学扩展，将其值扩展到了置信度空间下: $$ \begin{equation}\label{f1} \hat{V}(b) = E_x\left[ \hat{V}(x) \right] = \sum_{i = 1}^N p_i \hat{V}(x_i) \end{equation} $$ 这里，我们使用了熟悉的符号$p_i = b(x_i)$。因此，这个值函数是线性的，其参数为: $$ \begin{equation}\label{f2} u_i = \hat{V}(x_i) \end{equation} $$ 这个线性函数完全是POMDP值迭代算法中所用的形式。因此在置信度空间上的值函数通过如下的线性等式得到: $$ \begin{equation}\label{f3} \hat{V}(b) = \sum_{i = 1}^N p_i u_i \end{equation} $$ MDP的值函数提供了一个单一的置信度空间的线性约束。这使得我们可以在一个单一线性约束上应用算法policy_POMDP。

这一思想的最基础版本产生了算法16.1中描述的QMDP算法。这里我们使用一个与算法15.2略微不同的符号。与其为每个动作$u$准备一个线性函数，并使用policy_POMDP确定动作，我们的QMDP算法直接通过一个函数$Q$计算了最优的值函数。在算法16.1的第四行中计算的值$Q(x_i, u)$，是控制$u$在$x_i$上的MPU值。接着在第6行中扩展了置信度状态，在置信度状态上考虑期望。第6行还最大化所有的动作，并返回了具有最高期望值的控制动作。

算法 16.1. QMDP算法为每个控制动作$u$计算期望结果，并选择具有最大值的动作$u$。这里使用的值函数是MDP最优的，驱散了POMDP中的状态不确定性。

MDP最优的值函数可以扩展到置信度空间中，这一内涵使得我们能够随意组合MDP和POMDP支撑。具体的， MDP最优的值函数$\hat{V}$可以用作算法POMDP的输入。借助$T$周期的POMDP支撑，只要信息能够在接下来的$T$时间步里可用，那么得到的策略就可以主动地应用于信息收集。即使对于非常小的$T$，我们通常也可以得到一个鲁棒的概率学控制算法，其计算效率也远远由于完全POMDP方案。

16.3 扩展的马尔可夫决策过程

16.3.1 扩展的状态空间

扩展的MDP，或者说是AMDP，是QMDP算法的一种替代方案。它也是对完全POMDP值函数的近似。只是，它没有忽略超过小时间周期$T$的状态不确定性，而是将置信度状态压缩到一个更紧致的表达形式中，并实现完全POMDP类型的概率学支撑。

在AMDP中的基本假设就是置信度空间可以归结为一个低纬的充分统计量$f$，它将置信度分布映射到了一个低维的空间中。通过这个统计量$f(b)$替代原始的置信度$b$来计算值和动作。统计量越紧致，所得到的值迭代算法就越高效。

在很多场景中统计量的一个较好的选择就是一个元组 $$ \begin{equation}\label{f4} \bar{b} = \begin{pmatrix} \arg \max_x b(x) \\ H_b(x) \end{pmatrix} \end{equation} $$ 其中$\arg\max_x b(x)$是在置信度分布$b$下的最可能的状态，并且 $$ \begin{equation}\label{f5} H_b(x) = - \int b(x) \log b(x) dx \end{equation} $$ 是置信度的熵。这个空间将被称为扩展的状态空间，因为它使用一个单一值扩展了状态空间，这个值就是置信度分布的熵。在扩展状态空间中计算值函数而不是置信度空间，在复杂度上可以改进很多。扩展的状态避免了高维度的置信度空间，这节约了带量的计算值函数的时间，复杂度从指数级降到了地界的多项式级。

如果$f(b)$是$b$的充分统计量，那么数学上对于机器人可能面临的所有置信度$b$，都可以用扩展的状态表示估计值: $$ \begin{equation}\label{f6} V(b) = V(f(b)) \end{equation} $$ 实际上，这个假设很少成立。但是，得到的值函数质量仍然能够用于合理的控制选择。

此外，我们还可以考虑其它不同的统计量，比如置信度分布的矩(均值，方差等)，协方差矩阵的特征值和特征向量等等。

16.3.2 AMDP算法

AMDP算法在扩展状态空间中进行值迭代。为了做到这一点，我们必须克服两个障碍。首先，对于我们的扩展状态表示准确的值更新是非线性的。这是因为熵是一个置信度参数的非线性函数。因此就必须对值支撑近似。AMDPs将扩展状态离散化，使用一个查找表来表示值函数$\hat{V}$。在讨论MDP的时候，我们已经考虑了这样的一个近似。在AMDPs中，这个表比在MDP中使用的状态空间大一个维度。

第二个障碍在于转移函数和扩展状态空间的回报函数。一般我们都会有一个概率，比如说运动方程$p(x' | u, x)$，测量方程$p(z | x)$，和回报函数$r(x, u)$。但是对于在扩展状态空间中的值迭代，我们需要定义扩展状态空间的相似函数。

AMDPs使用了一个技巧来计算必要的函数。该技巧从仿真中学习转移概率和回报函数。学习算法是建立在一个频率统计量上的，它记录了扩展置信度$\bar{b}$在控制$u$的作用下变换到另一个置信度$\bar{b}'$的频率，以及该变换带来的平均回报。

算法16.2描述了AMDP_value_iteration的基本算法。这个算法分为两个阶段。在第一阶段(行2–19)，它从一个扩展的状态$\bar{b}$和控制动作$u$到可能的后续扩展状态$\bar{b}'$，构建了一个转移概率表$\hat{\mathcal{P}}$。他还构建了一个回报函数$\hat{\mathcal{R}}$，测量了在扩展状态$\bar{b}$上选择$u$，所预期的立即回报$r$。

算法 16.2. 上部:扩展的MDP的值迭代算法。底部: 用于选择控制动作的算法。

这些函数都是通过一个采样过程来估计的，我们对于$\bar{b}$和$u$的每个组合生成$n$个样本(行8)。对于每个蒙特卡洛仿真，该算法首先生成一个置信度$b$，有$f(b) = \bar{b}$。这一步是很狡猾的，实际上它在定义上是病态的。在原始的AMDP模型中，构造器简单的选择设置$b$为一个对称的高斯，其参数与$\hat{b}$匹配。接下来，AMDP算法采样一个位姿$x$，一个后继位姿$x'$，和一个测量值$z$。接着，它应用贝叶斯滤波器来生成一个后验置信度$B(b, u, z)$，对于此它计算扩展的统计量(行14)。表$\hat{\mathcal{P}}$和$\hat{\mathcal{R}}$接着在第15和16行得到更新，使用简单的频率计数以及实际的回报为这个蒙特卡洛样本赋予一个权重。

一旦学习结束，AMDP继续值迭代。这在第20到26行中实现。和以往一样，值函数初始化为一个很大的负值。在第25行中的支撑等式迭代导致一个定义在扩展状态空间中的值函数。

当使用AMDP时，状态跟踪通常替换了原始的置信度空间。比如说，将AMDP应用于机器人运动，我们可以使用MCL来跟踪机器人位姿的置信度。算法16.2中的policy_AMDP显式了如何从AMDP值函数中提取控制策略。它在第2行中从完全置信度中提取扩展的状态表示，接着在第3行中简单选择最大化期望值的控制动作。

16.3.3 AMDP的数学推导

暂略。

16.3.4 应用于移动机器人导航

AMDP算法是很实用的。在移动机器人导航的上下文中，AMDPs使得机器人能够在选择动作的时候考虑它的"困惑"等级。这不仅包括当前的不确定性，还有机器人选择它的动作时，未来可能面临的不确定性。

我们介绍一个在已知环境中导航的机器人。在本书中我们已经介绍过这个例子了，如图1.2所示。显然，困惑的等级依赖于机器人的导航位置。在一个空旷的区域运动的机器人很可能逐渐地丢失其位置信息。这反映在其条件概率$p(\bar{b}' | u, \bar{b})$上，在这个区域中很容易就会增加置信度的熵。在一个满是位置特征的场景中，比如墙边的不同特征，其不确定度更可能降低。AMDP期待着这样的情形，并生成策略在最小化到达时间的同时最大化到达目标位置时的确定度。因为不确定度是真实位置误差的估计，所以它是一个很好的指标，用来衡量实际到达期望位置的几率。

图16.1中显示了两个不同的轨迹，它们由不同的起始和目标点。图(a)(c)中是一个MDP规划器，它们没有考虑机器人的不确定性。扩展的MDP规划器生成了如图(b)(d)所示的轨迹。在图(a)(b)中机器人需要穿过一个大型的开放区域，差不多有40米宽。MDP算法并没有意识到在开放区域中运动会增加丢失位置的风险，生成的控制策略是最短的路径直接从起始点连接到了目标点。相比之下，AMDP规划器生成的策略紧贴着障碍物运动，在运动过程中机器人有更多的几率获得传感器测量信息。类似的，图(c)(d)考虑了目标位置接近于没有特征的开阔区域中心的情况。这里的AMDP规划器知道，从已知障碍物旁边经过，可以降低位姿不确定性，增加到达目标位置的机会。


(a)	(b)	(c)	(d)
图 16.1. 大型开放环境下的机器人路径示例。图(a)和(c)显示了由一个传统的动态规划路径规划器生成的路径，它忽略了机器人感知的不确定性。图(b)和(d)是通过扩展MDP规划器获得的路径，它预估了不确定性并且规避了机器人可能丢失位置的区域。Courtesy of Nicholas Roy, MIT

图16.2对比了AMDP导航策略与MDP方法的效果，描述了目标位置熵机器人的置信度$b$的熵，它是一个关于传感器特征的函数。在这个图中，为了研究传感器缺乏的效果，最大的感知距离是变化的。正如图中建议的那样，AMDP有更大的可能成功。当传感器数据尤其稀少的时候，它们的差距最大。对于具有长距离测量能力的传感器，这种差距最终会消失。这一点也不奇怪，因为合适的距离传感器所能采集的信息数量对于机器人位置的依赖较小。

预测和规避不确定性的特征被称为沿边导航coastal navigation，这是在机器人导航上应用AMDP的特征。这是一个类似于在基于卫星的全球定位技术发明之前的航海方法，通常会尽量贴近海岸线航行，这样才不至于迷失。

图 16.2. MDP规划和扩展的MDP规划的效果对比。这里显示的是在目标位置熵不确定性(熵)关于传感器测量距离的函数。Courtesy of Nicholas Roy, MIT.

最后我们探讨一下统计量$f$的选择，来结束对AMDP的讨论。只要需要我们都可以添加更多的特征，但是这样会明显地增加计算复杂度。近期有工作研究学习统计量$f$的算法，使了非线性的降维技术。图16.3显示了这样一种学习算法的结果，将之应用在一个建筑中搜索入侵者的问题。这里的学习算法确定一个六维的状态表示，它为任意合理的追踪策略捕获机器人的置信度。灰色的例子表示机器人关于入侵者位置的置信度。正如这个例子所示，具有学习状态表示的AMDPs成功的生成了一个有效的策略，机器人首先清除部分走廊，但总是尽量的贴近上部的房间，防止入侵者从那里逃跑。接着它清除房间，这个时间足够短防止入侵者从走廊通过。最后机器人在走廊中继续它的追踪。


(a)	(b)	(c)	(d)	(e)	(f)
图 16.3. 一个改进版本的AMDP计算的策略，使用了一个学习的状态表示。任务就是找到一个入侵者。灰色的粒子表示入侵者位置的概率分布，一开始是均匀分布的，如(a)所示。黑色的圆点是入侵者的真实位置，机器人还没有感测到它。圆圈是机器人的位置。这个策略具有很高的成功概率。Courtesy of Nicholas Roy, MIT, and Geoffrey Gordon, CMU.

16.4 蒙特卡洛POMDPs

16.4.1 粒子集合的使用

本章中讨论的最后一个算法是POMDPs的粒子滤波器解决方案，称为MC-POMDP，是蒙特卡洛POMDP的简称。MC-POMDPs需要一个定义在粒子集合上的值函数。令$\mathcal{X}$为一个表示置信度$b$的粒子集合。那么值函数就表示为一个函数

$$ \begin{equation}\label{f10} V : \mathcal{X} \rightarrow \Re \end{equation} $$

这个表示方式有很多优点，但它也创造很多困难。一个关键的优势是我们可以在任意状态空间上表示值函数。实际上，在目前讨论的所有算法中，MC-POMDPs是唯一一个不需要有限状态空间的算法。此外，MC-POMDPs使用粒子滤波器跟踪置信度。我们已经看到了很多成功的粒子滤波器应用，MC-POMDPs将之用于规划和控制问题。

在POMDP中使用粒子集合的主要难点在于值函数的表示上。对于给定大小$M$的所有粒子集合，其空间都是$M$维的。此外，任何粒子集合被两次观测到的概率为0。这是粒子生成过程的随机特性导致的。因此，我们需要一个对$V$的表示，能够使用一些粒子集合更新，但是使用其它的粒子集合来提供值，这在MC-POMDP算法之前是没有见过的。换句话说，我们需要一个学习算法。 MC-POMDP通过一个使用局部加权插值的最近邻算法，在不同置信度之间插值。

16.4.2 MC-POMDP算法

算法16.3中列举了基本的MC-POMDP算法。该算法需要一系列的嵌套循环。其最内层的循环，在第6到16行，为一个特定的置信度$\mathcal{X}$更新了值函数$V$。它通过模拟每个可用的控制动作$u$，获得可能的后继置信度集合，来做到这点。这个模拟在第9到12行实现。基于此，它收集了每个可行的动作的局部值(第13行)。值函数的更新在第16行进行， $V$被简单的设定为所有$Q_u$中的最大值。

在这个局部支撑之后，就是MC-POMDP模拟物理系统，生成新粒子集合$\mathcal{X}$的过程。这个模拟过程在第17到21行中实现。在我们的例子中，这个更新总是贪婪的选择动作(第17行)。但是，实际的实现中常常会偶尔选择一个随机动作。通过转换到一个新的置信度$\mathcal{X}$，MC-POMDP值迭代在不同的置信度状态上进行更新。通过在整个片段上迭代(第2到第5行的外层循环)，最后值函数完全得到了更新。

关键的开放问题就是函数$V$的表示方式。MC-POMDP使用一个局部的学习算法追踪最近邻。该算法对应着值$V_i$扩展关联的置信度$\mathcal{X}_i$。当一个请求到来会伴随着一个之前没有观测到的粒子集合$\mathcal{X}_{query}$，MC-POMDP从它的记忆中确定$K$个最近的粒子集合。为了定义粒子集合的紧邻度，需要一些额外的假设。在初始的实现中，MC-POMDP为每个粒子卷积一个高斯函数，该高斯函数具有小的、固定的协方差，然后测量混合的高斯分布之间的KL散度。除去一些细节，这个步骤使得我们可以确定$K$个最近邻的粒子集合$\mathcal{X}_1, \cdots, \mathcal{X}_K$，及其相关的距离记为$d_1, \cdots, d_K$，需要注意KL散度不是技术意义上的距离，因为它是非对称的。请求集合的值$\mathcal{X}_{query}$可以通过如下的公式得到: $$ \begin{equation}\label{f11} V(\mathcal{X}_{query}) = \eta \sum_{k=1}^K \frac{1}{d_k}V_k \end{equation} $$ 其中，$\eta = \left[ \sum_k \frac{1}{d_k} \right]^{-1}$。$\mathcal{X}_k$是$K$近邻的集合中的第$k$个关联置信度。这个插值公式就是Shepard's interpolation，在算法16.3中的第13行中解释如何计算$V(\mathcal{X}')$。

在16行中的更新涉及到一个隐函数微分。如果关联集合已经包含了$K$个粒子集合，它的距离低于一个用户定义的阈值，对应的$V$值在传播其在插值的贡献过程中得到了更新: $$ \begin{equation}\label{f12} V_k \longleftarrow V_k + \alpha \eta \frac{1}{d_k}\left(\max_u Q(u) - V_k \right) \end{equation} $$ 其中$\alpha$是学习速率。表达式$\max_u Q(u)$是函数$V$的目标值，$\eta \frac{1}{d_k}$是第$k$个关联粒子集合在Shepard's插值公式中的贡献度。

如果有少于$K$个粒子集合的距离低于阈值，那么请求的粒子集合就简单的添加到相关的集合中，关联的值为$V = \max_u Q(u)$。在这种方式下，关联粒子集的集合随着时间逐渐增长。 $K$的取值以及用户定义的距离阈值决定了MC-POMDP值函数的平滑度。实际上，选择合适的值需要花些心思，因为如果阈值选择的太紧，它很容易超出一般电脑的内存空间。

16.4.3 MC-POMDPs的数学推导

暂略。

16.4.4 实际考量

再本章介绍的额这三种POMDP近似方法中，MC-POMDP是应用最少可能也是影响最小的一个。它的近似依赖于表示值函数的学习算法上。实现一个MC-POMDP算法需要很多技巧，需要对值函数的连续特性有很好的理解，因为它影响了实际使用的粒子数量。

MC-POMDP算法的原始实现可以得到图16.4中的结果。在图16.4a中显示了一个机器人，在它旁边有一个可抓取的物体在地板上，可以通过摄像头来探测到。一开始物体在机器人的视野之外。一个成功的策略有三个阶段。首先是一个搜索阶段，机器人将一直转圈直到找到了目标。接着就是一个动作阶段，机器人对准物体的中心以方便的抓取物体。最后就是一个抓取动作。主动感知和目标探测动作的组合让这个问题成为了一个相对有挑战的概率学控制问题。


(a)	(b)	(c)
图 16.4. 机器人寻找和抓取任务。(a) 一个装备有夹具和摄像头的机器人，握着目标物体。(b) 三个成功执行策略的2维轨迹，机器人一直在转圈，直到它看到了目标，然后初始化了一个成功的抓取动作。(c) 通过仿真计算得到的成功率，它是规划步骤数量的一个函数。

图16.4b中显示了示例剧情，机器人转动、移动、最后成功的抓取。图中显示的曲线就被投影到了二维的运动字典中了。图16.4c中显示了结果的质量，它是成功率关于MC-POMDP值迭代的迭代次数的函数。 4000次的迭代得到的值支撑，在一个低端的PC机上需要接近两个小时的计算时间，此时平均性能达到了80%。剩下的20%的失效主要是因为机器人不能定位自己的位置，并抓取目标，这在一定程度上是MC-POMDPs的近似的结果。

16.5 总结

在本章中，我们介绍了三种近似的概率规划和控制算法，它们具有不同的实际应用能力。所有的三种算法都依赖于对POMDP值函数的近似。但是其近似方法上有着本质的区别。

QMDP框架只考虑单一动作选择的不确定性。它建立在一个假设上，执行了下一个控制动作之后，世界的状态会立即变得可观测。完全的可观性使得它可以使用MDP最优值函数。 QMDP使用数学的期望算子将MDP的值函数扩展到了置信度空间中。因此，QMDP的规划效率于MDP一样，但是其值函数通常过多的估计了置信度状态的真实值。
QMDP算法的扩展组合了MDP最优值函数和一个POMDP支撑序列。当于$T$-POMDP支撑步骤组合的时候，所得到的策略考虑了动作对于周期$T$的信息收集能力，接着依赖于QMDP的完全客观状态假设。周期$T$越大，所得到的结果就越接近完全POMDP解决方案。
AMDP算法追求一个不同的近似方法。它将置信度映射到了一个低维的表示形式中，在这个形式上进行准确的值迭代。传统的表示形式由在一个置信度下的最可能状态，和置信度熵构成。在这种表达形式下， AMDPs就像MDP一样，在状态表示上有一个附加的维度，用于测量机器人的全局不确定性。
为了实现一个AMDP，有必要学习状态转移矩阵以及在低维置信度空间下的回报函数。AMDPs通过一个初始阶段来获得这些，将统计量缓存到一个查找表中，表示状态转移和回报函数。因此，AMDP就在这个学习的模型上操作，只有当学习的模型是准确的情况下它的结果才是准取得。
应用在已知环境中移动机器人导航的AMDPs被称为是coastal navigation。这种导航技术预测不确定度，并牺牲路径长度来获取路径上的确定度。如此得到的轨迹于任何非概率学的方案有着显著的不同。一个"coastally"导航机器人回避了那些增加迷失风险的区域。如果机器人可以以一个足够高的概率重定位，那么短暂的迷失是可以接受的。
MC-POMDP算法是一种粒子滤波器版本的POMDP方法。它计算了一个定义在粒子集合上的值函数。为了实现这样的一个值函数，MC-POMDPs必须使用一个局部学习技术，用一个局部加权规则来组合基于KL散度的近似测试。 MC-POMDPs就可以使用蒙特卡吕采样来实现一个近似的值支撑。这样的算法结果就是一个完全可行的POMDP算法，它的计算复杂度和准确性都是学习算法参数的函数。

本章主要是想说有很多近似方法，它们的计算复杂度很接近MDPs，而且还考虑了状态的不确定性。无论近似是多么粗糙，考虑了状态不确定性的算法，都倾向于提供比完全忽略不确定性的算法，鲁棒的多的结果。即使是在状态向量中添加一个新元素，它以一种一维的形式测量了全局的不确定性，都使得机器人的表现由很大的差别。

16.6 参考文献

在上一章中介绍了很多使用近似方法解决POMDP问题的方法。本章中介绍的QMDP算法归功于Littman et al.(1995)。针对扩展的状态表示方法的AMDP算法是由Roy et al. (1999)开发的。后来Roy et al. (2004)将之扩展到了一个学习的状态表示方法上了。Thrun (2000a)开发了蒙特卡洛POMDP算法。

16.7 练习

暂略。