首页 关于
树枝想去撕裂天空 / 却只戳了几个微小的窟窿 / 它透出天外的光亮 / 人们把它叫做月亮和星星
目录

第十五章：部分可观的马尔可夫决策过程

15.1 动机

本章讨论针对部分可观测机器人控制问题的算法。这些算法不仅要处理控制的不确定性，还要处理测量的不确定性。 它们对上一章中讨论的值迭代算法进行了扩展，让它不仅仅可以处理运动效果的不确定性。 这里研究的框架称为部分客观的马尔可夫决策过程partially observable Markov decision processes, POMDPs，这个名字来自控制研究领域。“部分”表示世界的状态不能直接的感知得到。 实际上，机器人接收的测量值是不完全的，通常是这些状态的带有噪声的映射。

正如本书中的很多章节中讨论的那样，部分可观性意味着机器人必须估计可能的世界状态的后验分布。针对有限世界的寻找最优控制策略的算法是存在的，状态空间、运动空间、观测空间、以及规划周期\(T\)都是有限的。 不幸的是，确实有一些方法需要很多计算量。对于更多有趣的连续情况，最好的算法都是近似的。

本章所研究的所有算法都是建立在之前讨论的值迭代方法上的。让我们重述一下公式(14.14)， 它是解决MDP问题的值迭代方法的中心更新公式: $$ \begin{equation}\label{f1} V_T(x) = \gamma \max_u \left[ r(x, u) + \int V_{T-1}(x')p(x' | u, x)dx' \right] \end{equation} $$ 其中\(V_1(x) = \gamma \max_u r(x, u)\)。在POMDPs中，我们也是使用这一思想。只是此时状态\(x\)不是可观测的了。机器人必须根据状态的置信度做出决策，也就是状态的后验分布空间。 本章和后续的章节，我们用\(b\)表示置信度，替代之前章节中较长的\(bel\)。

POMDPs在置信度空间上计算一个值函数: $$ \begin{equation}\label{f2} V_T(b) = \gamma \max_u \left[ r(b, u) + \int V_{T-1}(b')p(b' | u, b)db' \right] \end{equation} $$ 其中\(V_1(b) = \gamma \max_u E_x\left[ r(x, u) \right]\)。如此得到的控制策略如下: $$ \begin{equation}\label{f3} \pi_T(b) = \arg \max_u \left[ r(b, u) + \int V_{T-1}(b')p(b' | u, b)db' \right] \end{equation} $$ 置信度是一个概率分布，因此POMDP中的每个值都是一个对于整个概率分布的函数。这是有问题的。如果状态空间是有限的，置信度空间就是连续的，因为它是状态空间下所有分布的空间， 因此存在不同值的continuum。然而在MDP问题中，只有有限数量的不同取值。对于连续的状态空间，这种情况就更加微妙，它的置信度空间是一个无限维的continuum。

值函数的计算特性还会额外增加复杂度。公式(\(\ref{f2}\))和(\(\ref{f3}\))对所有的置信度\(b'\)积分。因为置信空间本身就是十分复杂的，这些积分很难准确的计算出来， 或者找到一个有效的近似方法。因此在置信度空间下计算值函数\(V_T\)比在状态空间下计算更加困难一点也不奇怪。

幸运的是，确实存在一种准确的解决方案，可以处理有限世界的特殊情况，此时状态空间、动作空间、观测空间、以及规划周期都是有限的。这种方案通过对置信度空间的分段线性化， 来表示值函数。我们应当看到，这种表示方式的线性特性直接来自于期望算子是线性的这一事实。这种分段特性得益于机器人选择控制的能力，在不同的置信度空间下，它将选择不同的控制。 所有的这些陈述将在本章中得到证明。

本章讨论通用的POMDP算法，计算定义在所有置信度分布空间下的策略。该算法在计算上很臃肿，但是对于有限的POMDP问题它是准确的。我们还将讨论它的一种更容易驾驭的变型。 接下来的章节将讨论各种更高效的POMDP算法，它们都是近似算法，但很适用于实际的机器人问题。

15.2 案例分析

15.2.1 案例描述

我们通过一个数值的例子来具体说明置信度空间下的值迭代方法。这个实例很简单，但是通过对它的讨论，我们可以了解置信度空间下值迭代的所有主要要素。

如图15.1所示，是一个有两个状态的世界。状态用\(x_1\)和\(x_2\)标记。机器人可以选择三种不同的动作，\(u_1, u_2\)和\(u_3\)。动作\(u_1\)和\(u_2\)是终结者，当执行该动作时， 它们会立即产生如下的回报: $$ \begin{equation}\label{f4} \begin{matrix} r(x_1, u_1) = -100 & r(x_2, u_1) = +100 \\ r(x_1, u_2) = +100 & r(x_2, u_2) = -50 \end{matrix} \end{equation} $$ 困境就是这两个动作在各个状态下提供了相反的回报，在状态\(x_1\)下，\(u_2\)就是最优的动作，而状态\(x_2\)的最优动作就是\(u_1\)。因此，在选择最优动作的时候， 状态变换信息直接影响了回报。

图 15.1. 用于说明置信度空间值迭代的两状态环境

为了获得这样的信息，为机器人提供了第三个控制动作，\(u_3\)。执行该动作会产生一个中间消耗\(-1\)，即 $$ \begin{equation}\label{f6} r(x_1, u_3) = r(x_2, u_3) = -1 \end{equation} $$ 我们可以认为这是等待的代价，或者是感知的代价。动作\(u_3\)以一种非确定性的方式影响着世界的状态: $$ \begin{equation}\label{f7} \begin{matrix} p(x_1'| x_1, u_3) = 0.2 & p(x_2' | x_1, u_3) = 0.8 \\ p(x_1'| x_2, u_3) = 0.8 & p(x_2' | x_2, u_3) = 0.2 \end{matrix} \end{equation} $$ 换句话说，当值机器人执行\(u_3\)后，以0.8的概率转换到另一个状态下，而且机器人只花费了一个单位的代价。

但是，执行动作\(u_3\)是有益处的。在每个控制决策之前，机器人都可以感知。通过感知，机器人获得了关于状态的信息，返回来可以用它来更好的做出控制决策，以获得更高的回报。 动作\(u_3\)使得机器人感知世界，并不是一个终结动作。

在我们的例子中，测量模型通过如下的概率分布描述: $$ \begin{equation}\label{f9} \begin{matrix} p(z_1| x_1) = 0.7 & p(z_2 | x_1) = 0.3 \\ p(z_1| x_2) = 0.3 & p(z_2 | x_2) = 0.7 \end{matrix} \end{equation} $$ 换句话说，如果机器人测得\(z_1\)，它就会更加坚定的认为自己处于\(x_1\)，同样的\(z_2\)对应着\(x_2\)。

之所以选择一个两状态的例子，是因为它可以简化置信度空间的图函数。特别的，一个置信度状态\(b\)可以表述为\(p_1 = b(x_1)\)和\(p_2 = b(x_2)\)。但是，我们知道\(p_2 = 1 - p_1\)， 因此这就足以刻画\(p_1\)。对应的控制策略\(\pi\)是将单位区间\([0;1]\)映射到空间中所有动作的函数: $$ \begin{equation}\label{f11} \pi : [0;1] \longrightarrow u \end{equation} $$

15.2.2 控制选择

至于在什么时候应该执行什么动作，让我们从三个动作\(u_1, u_2, u_3\)产生的立即回报开始分析。在之前的章节中，将回报看作是状态和动作的函数。因为我们不知道状态， 就不得不定义一个概念来描述置信度状态的回报。具体的，对于任意给定的置信度\(b = (p_1, p_2)\)，在这个置信度下预期的回报可以通过下式表示: $$ \begin{equation}\label{f12} r(b, u) = E_x\left[ r(x, u) \right] = p_1 r(x_1, u) + p_2 r(x_2, u) \end{equation} $$ 函数\(r(b,u)\)定义了POMDPs中的回报payoff in POMDPs。

(a). 动作\(u_1\)的回报\(r(b, u_1)\) (b). 动作\(u_2\)的回报\(r(b, u_2)\) (c). 动作\(u_3\)的回报\(r(b, u_3)\) (d). \(V_1(b) = \max_u r(b,u)\)
图 15.2. (a),(b),(c)描述了一置信度状态\(p_1 = b(x_1)\)为参数的，对于三个动作\(u_1, u_2, u_3\)的回报函数\(r\)。 (d) 周期\(T = 1\)时对应于这三个线性函数最大值的值函数。

图15.2a中描述了在参数\(p_1\)下选择控制\(u_1\)的预期回报\(r(b, u_1)\)。在图中最左端，我们有\(p_1 = 0\)，因此机器人完全认定世界处于\(x_2\)的状态。 因此执行动作\(u_1\)将产生\(r(x_2, u_1) = 100\)的回报，如式(\(\ref{f4}\))描述的那样。在最右端，有\(p_1 = 1\)，因此状态是\(x_1\)，此时控制选择\(u_1\)将产生\(r(x_1, u_1) = -100\)。 期望就是这两个值的线性组合，如图15.2a所示。 $$ \begin{equation}\label{f13} r(b, u_1) = -100 p_1 + 100 p_2 = -100 p_1 + 100 (1 - p_1) \end{equation} $$

图15.2b和c中分别显示了动作\(u_2\)和\(u_3\)所对应的函数。对于\(u_2\)有: $$ \begin{equation}\label{f14} r(b, u_2) = 100 p_1 - 50 (1 - p_1) \end{equation} $$ 对于\(u_3\)，我们可以得到一个常值函数: $$ \begin{equation}\label{f15} r(b, u_3) = -1 p_1 - 1 (1 - p_1) = -1 \end{equation} $$ 理解置信度空间的值迭代的第一个练习将聚焦于值函数\(V_1\)的计算，这是在周期为\(T=1\)决策过程下最优选择的值函数。在一个决策周期中，我们的机器人可以在这三个不同控制动作之间做出选择。 那么我们应该选择哪个？

对这几幅图研究到现在，我们可以很容易给出答案。对于任意置信度状态\(p_1\)，图15.2的(a)(b)(c)中描绘了各个控制选择的回报。因为目标是最大化回报， 机器人简单的选择了具有最高回报的动作。这在图15.2(d)中可以看到，该图中叠加了三个回报函数。在左边的区域中，\(u_1\)是最优的动作，因为它的值函数最大。 当\(r(b,u_1) = r(b, u_2)\)时，就会发生转移，转折点就是\(p_1 = \frac{3}{7}\)。对于大于\(\frac{3}{7}\)的值\(p_1\)，\(u_2\)时更好的选择。因此\(T=1\)的最优策略就是: $$ \begin{equation}\label{f16} \pi_1(b) = \begin{cases} u_1 & \mathcal{if}\ p_1 ≤ \frac{3}{7} \\ u_2 & \mathcal{if}\ p_1 > \frac{3}{7} \end{cases} \end{equation} $$ 对应的值就是图15.2d中上方的粗线所示。这个图时分段线性化的，凸函数。它是图15.2(a)(b)(c)中各个回报函数中的最大值。因此，我们可以将它写成求三个函数最大值的操作: $$ \begin{align}\label{f17} V_1(b) & = \max_u r(b,u) \\ & = \max \begin{Bmatrix} -100 p_1 +100 (1 - p_1) \\ 100 p_1 -50(1 - p_1) \\ -1 \end{Bmatrix} \begin{matrix} (*) \\ (*) \\ \ \end{matrix} \end{align} $$ 显然，上式(\(\ref{f17}\))中只有标记为\((*)\)的线性函数才有作用。我们可以安全的将上式裁剪为: $$ \begin{equation}\label{f18} V_1(b) = \max \begin{Bmatrix} -100 p_1 +100 (1 - p_1) \\ 100 p_1 -50(1 - p_1) \\ \end{Bmatrix} \end{equation} $$ 我们将在示例中反复的使用这种裁剪技术。可裁剪的线性约束如图15.2d中的虚线所示，后文中还有很多其它图表也是这样。

15.2.3 感知

下面我们的推理就要涉及到感知了。如果机器人在选择动作之前可以感知会怎么样？这将如何影响最优的值函数？显然，感知提供了关于状态的信息，因此应当使得机器人能够选择更好的控制动作。 具体的，对于最差的置信度，\(p_1 = \frac{3}{7}\)，在我们的示例中预期的回报是\(\frac{100}{7} \approx 14.3\)，这就对应着图15.2d中的转折点。显然，如果我们可以先感知， 就会发现在感知之后，我们处于一个不同的置信度下。这个置信度的值比刚刚的14.3更好，但是好多少呢？

这个答案是让人吃惊的。建设我们感知到了\(z_1\)。图15.3a中显示了感知到\(z_1\)后的置信度，它是感知动作前置信度的函数。让我们来剖析一下这个函数。 如果我们的前感知置信度是\(p_1 = 0\)，那么我们的后感知置信度仍然是\(p_1 = 0\)，无论测量值是什么。类似的，对于\(p_1 = 1\)也是这样。因此，在极端的情况下，这个函数的结果是确定性的。 在中间状态下，我们不能确定世界的状态具体是什么，测量到\(z_1\)改变了我们的置信度。这个改变量由贝叶斯公式决定: $$ \begin{equation}\label{f19} p_1' = p(x_1 | z) = \frac{p(z_1 | x_1)p(x_1)}{p(z_1)} = \frac{0.7p_1}{p(z_1)} \end{equation} $$ 而且 $$ \begin{equation}\label{f20} p_2' = \frac{0.3(1 - p_1)}{p(z_1)} \end{equation} $$ 归一算子\(p(z_1)\)在图15.3a中添加了非线性度。在我们的例子中，其值为: $$ \begin{equation}\label{f21} p(z_1) = 0.7p_1 + 0.3(1 - p_1) = 0.4 p_1 + 0.3 \end{equation} $$ 因此\(p_1' = \frac{0.7p_1}{0.4p_1 + 0.3}\)。但是，后面我们会看到，这个归一化算子被漂亮的干掉了。

让我们首先研究一下这个非线性变换函数的在值函数\(V_1\)上的效果。假设我们已知观测到了\(z_1\)，并且必须做出一个动作选择。那么它的选择是什么呢？与之相对应的值函数应该长什么样？ 这个答案在图15.3c中形式化的给出了。该图描述了图15.3b中的分段线性化值函数， 它是通过上面讨论的非线性测量函数(如图15.3a中所示)映射出来的。读者可能需要花点时间来找到这里的方向， 对于置信度\(p_1\)，根据我们的非线性函数将之映射到置信度\(p_1'\)上，如图15.3b中所示。对于所有的\(p_1 \in [0;1]\)， 这个过程就产生了图15.3c中的结果。

(a). 感知到\(z_1\)后的\(p_1'\) (b). \(V_1(b)\) (c). \(V_1(b | z_1)\)
(d). \(p(z_1)V_1(b | z_1)\) (e). \(p(z_2)V_1(b | z_2)\) (f). \(\bar{V}_1(b) = \sum p(z_i)V_1(b | z_i)\)
图 15.3. 感知在值函数上的作用: (a) 感知到\(z_1\)后的置信度，它是以感知\(z_1\)之前置信度的函数。 感知到\(z_1\)使得机器人更加坚定的认为状态就是\(x_1\)。在图(b)中将值函数通过这个非线性函数映射之后得到了如图(c)所示的非线性值函数。 (d)通过观测值\(z_1\)将这个值函数拆分为一个分段线性函数。(e)测量值\(z_2\)下相同的分段线性函数。(f)感知之后的预期值函数。

数学上，这个图通过下式给出: $$ \begin{equation}\label{f22} V_1(b | z_1) = \max \begin{Bmatrix} -100 · \frac{0.7p_1}{p(z_1)} + 100 · \frac{0.3(1 - p_1)}{p(z_1)} \\ 100 · \frac{0.7p_1}{p(z_1)} - 50 · \frac{0.3(1 - p_1)}{p(z_1)} \end{Bmatrix} = \frac{1}{p(z_1)} \max \begin{Bmatrix} -70 p_1 + 30(1 - p_1) \\ 70p_1 - 15(1 - p_1) \end{Bmatrix} \end{equation} $$ 这仅仅是在式(\(\ref{f18}\))中描述的值函数\(V_1\)中用\(p_1\)来替换\(p_1'\)的结果。我们注意到在图15.3c中，最差值的置信度向左移动了一点。 现在感知到\(z_1\)之后，最差的置信度使得我们相信有\(\frac{3}{7}\)的概率在状态\(x_1\)下。

然而，这只考虑了两个测量值中的一个，在感知之前的值必需考虑到两种测量值。具体的感知之前的值\(\bar{V}_1\)通过如下的期望值给出: $$ \begin{equation}\label{f23} \bar{V}_1(b) = E_z\left[ V_1(b | z) \right] = \sum_{i=1}^2 p(z_i)V_1(b | z_i) \end{equation} $$ 我们立即注意到在这个期望中，每个有贡献的值函数\(V_1(b | z_i)\)都乘上了一个概率\(p(z_i)\)这导致了测量前(pre-measurement)值函数的非线性，代入式(\(\ref{f19}\))，得到: $$ \begin{align}\label{f24} \bar{V}_1(b) & = \sum_{i=1}^2 p(z_i)V_1\left(\frac{p(z_i | x_1)p_1}{p(z_i)}\right) \\ & = \sum_{i=1}^2 p(z_i)\frac{1}{p(z_i)} V_1\left( p(z_i | x_1)p_1 \right) \\ & = \sum_{i=1}^2 V_1\left( p(z_i | x_1)p_1 \right) \end{align} $$ 这个变换是成立的，因为\(V_1\)中的每个要素关于\(1/p(z_i)\)都是线性的，如式(\(\ref{f22}\))中的示例所述。因此我们可以把因子\(1/p(z_i)\)从最大化过程中移除， 因为最大化中的每一项都要乘上这个因子。在对应的修复了这些项后，就可以简单的将\(p(z_i)\)移除。

在我们的例子中，有两个测量值，因此我们可以为每个这样的测量值计算期望值\(p(z_i)V_1(b | z_i)\)。这正是式(\(\ref{f23}\))中参加求和的那些项。对于\(z_1\)， 我们已经在式(\(\ref{f22}\))中计算了\(V_1(b | z_i)\)，因此 $$ \begin{equation}\label{f25} p(z_1)V_1(b | z_1) = \max \begin{Bmatrix} -70 p_1 + 30(1 - p_1) \\ 70p_1 - 15(1 - p_1) \end{Bmatrix} \end{equation} $$ 这个函数如图15.3d所示，它实际上式两个线性函数的最大值。类似的，对于\(z_2\)我们有 $$ \begin{equation}\label{f26} p(z_2)V_1(b | z_2) = \max \begin{Bmatrix} -30 p_1 + 70(1 - p_1) \\ 30p_1 - 35(1 - p_1) \end{Bmatrix} \end{equation} $$ 该函数如图15.3e所示。感知之前的值函数就可以根据式(\(\ref{f23}\))对这两项求和得到: $$ \begin{equation}\label{f27} \bar{V}_1 = \max \begin{Bmatrix} -70 p_1 + 30(1 - p_1) \\ 70 p_1 - 15(1 - p_1) \end{Bmatrix} + \max \begin{Bmatrix} -30 p_1 + 70(1 - p_1) \\ 30 p_1 - 35(1 - p_1) \end{Bmatrix} \end{equation} $$ 这个求和如图15.3f所示。它有两个转折点，将值函数分成了三个不同的线性部分。对于左边的部分，无论机器人感知到了什么信息，\(u_1\)都是最优动作。类似的，对于右边的部分，\(u_2\)式最优控制动作。 而中间的部分，感知就有作用了，需要根据机器人的感知信息来确定最优的控制。如此中间部分得到了一个比没有感知时(如图15.2d所示)大很多的值。本质上， 感知能力将整个区域的值函数提高到了一个更高的等级，在这个区域中，机器人对于世界的状态具有最高的不确定性。这个发现说明在置信度空间中的值迭代确实评价了感知， 但是只在它对未来的控制选择上有影响时才有意义。

让我们回到这个值函数的计算上来，因为它可能比看起来还容易。公式(\(\ref{f27}\))要求我们计算两个线性函数的最大值的和。将它写成我们的标准形式，which is the maximum over linear functions without the sum。具体的，我们的新值函数\(\bar{V}_1\)是有界的，低于任何将第一个最大值表达式中的线性函数与第二个最大值表达式中的线性函数的求和形式。我们一共有四种可能的组合形式: $$ \begin{align}\label{f28} \bar{V}_b & = \max \begin{Bmatrix} -70 p_1 + 30(1 - p_1) -30 p_1 + 70(1 - p_1) \\ -70 p_1 + 30(1 - p_1) +30 p_1 - 35(1 - p_1) \\ 70 p_1 - 15(1 - p_1) -30 p_1 + 70(1 - p_1) \\ 70 p_1 - 15(1 - p_1) +30 p_1 - 35(1 - p_1) \end{Bmatrix} \\ & = \max \begin{Bmatrix} -100p_1 + 100(1 - p_1) \\ -40p_1 - 5(1 - p_1) \\ 40p_1 + 55(1 - p_1) \\ 100p_1 - 50(1 - p_1) \end{Bmatrix} \begin{matrix} (*) \\ \\ (*) \\ (*) \end{matrix} \\ & = \max \begin{Bmatrix} -100p_1 + 100(1 - p_1) \\ 40p_1 + 55(1 - p_1) \\ 100p_1 - 50(1 - p_1) \end{Bmatrix} \end{align} $$ 这里我们再次使用\((*)\)表示对值函数有实际贡献的项。如图15.3f所示，只有其中的三个线性函数，因此将第四个剪除了。

15.2.4 预测

当机器人选择一个动作的时候，它的状态就会改变。为了以大于1的周期进行规划，我们必须考虑到这点，并对应的映射值函数。在我们的例子中，\(u_1\)和\(u_2\)都是终止动作。 因此，我们只需要考虑动作\(u_3\)的效果。

幸运的是，在POMDP中的状态变化并不像测量值那样复杂。图15.4a中显示了执行\(u_3\)的置信度映射。具体的，假设我们确定是从状态\(x_1\)开始的，那么就有\(p_1 = 1\)。 根据式(\(\ref{f7}\))的转移概率模型，我们有\(p_1' = p(x_1' | x_1, u_3) = 0.2\)。类似的，对于\(p_1 = 0\)我们有\(p_1' = p(x_1' | x_2, u_3) = 0.8\)。在这两个极端情况中间就是一个线性函数: $$ \begin{equation}\label{f29} p_1' = E_x\left[ p(x_1' | x, u_3) \right] = \sum_{i=1}^2 p(x_1' | x_i, u_3)p_i = 0.2p_1 + 0.8(1 - p_1) = 0.8 - 0.6p_1 \end{equation} $$ 这个函数如图15.4a所示。如果我们现在反向映射值函数如图15.4b所示(它与图15.3f一致)，我们就得到了图15.4c中的值函数。这个值函数比映射之前的更平整，说明在状态变换的时候丢失了信息。 它也是镜像的，反映了执行\(u_3\)时状态的改变。

(a). 执行\(u_3\)之后的\(p_1\) (b). \(\bar{V}_1(b)\) (c). \(V_2(b, u_3)\) (d). \(V_2(b) = \max_u V_2(b,u)\)
图 15.4. (a)执行动作\(u_3\)后的置信度状态参数\(p_1'\)，它是执行动作前参数\(p_1\)的函数。在图(b)中显示了该置信度的传播， 通过对这个映射求逆就得到了图(c)中显示额置信度。通过最大化传播的置信度函数得到值函数\(V_2\)，如图(d)所示，以及两个动作\(u_1\)和\(u_2\)的回报。

数学上，这个值函数由式(\(\ref{f28}\))经过式(\(\ref{f29}\))映射计算得到。

$$ \begin{equation}\label{f30} \bar{V}_1(b | u_3) = \max \begin{Bmatrix} -100(0.8 - 0.6p_1) + 100(1 - (0.8 - 0.6p_1)) \\ 40(0.8 - 0.6p_1) + 55(1 - (0.8 - 0.6p_1)) \\ 100(0.8 - 0.6p_1) - 50(1 - (0.8 - 0.6p_1)) \end{Bmatrix} = \max \begin{Bmatrix} 60p_1 - 60(1 - p_1) \\ 52p_1 + 43(1 - p_1) \\ -20p_1 + 70(1 - p_1) \end{Bmatrix} \end{equation} $$

这些变换可以很容易通过手动计算。图15.4c中显示了这一函数，以及最优控制动作。

现在我们就快要完成规划周期为\(T = 2\)的值函数\(V_2\)了。此时，机器人又面临了一个是否选择执行控制\(u_3\)的问题，或者直接执行终结操作\(u_1\)或\(u_2\)。正如之前提到的， 这个选择通过在我们的考虑中添加两个新的选项来实现，它们表示成为两个线性函数\(r(b, u_1)\)和\(r(b, u_2)\)。我们还必须从值函数中减去执行动作\(u_3\)的代价。如此得到了图15.4d所示的图，其形式为 $$ \begin{equation}\label{f31} \bar{V}_2(b) = \max \begin{Bmatrix} -100p_1 + 100(1 - p_1) \\ 100p_1 - 50(1 - p_1) \\ 59p_1 - 61(1 - p_1) \\ 51p_1 + 42(1 - p_1) \\ -21p_1 + 69(1 - p_1) \end{Bmatrix} \begin{matrix} (*) \\ (*) \\ \\ (*) \\ \ \end{matrix} \end{equation} $$ 注意我们只添加了两个选项(第一行和第二行)，并从其它线性约束中减去了\(u_3\)的单位代价。其中只有三个约束是有用的，用\((*)\)标注。如此得到的值可以重写为： $$ \begin{equation}\label{f32} \bar{V}_2(b) = \max \begin{Bmatrix} -100p_1 + 100(1 - p_1) \\ 100p_1 - 50(1 - p_1) \\ 51p_1 + 42(1 - p_1) \\ \end{Bmatrix} \end{equation} $$

15.2.5 深度周期和剪枝

现在我们已经执行了一个完整的在置信空间中的备份操作backup step in belief space。这个算法是很容易写成递归形式的。图15.5中分别显示了周期为\(T = 10\)和\(T = 20\)的值函数。 这些值函数看些来很类似，在近似截断的形势下，\(V_{20}\)只有13项 $$ \begin{equation}\label{f33} \bar{V}_20(b) = \max \begin{Bmatrix} -100p_1 + 100(1 - p_1) \\ 100p_1 - 50(1 - p_1) \\ 64.1512p_1 + 65.9454(1 - p_1) \\ 64.1513p_1 + 65.9454(1 - p_1) \\ 64.1531p_1 + 65.9442(1 - p_1) \\ 68.7968p_1 + 62.0658(1 - p_1) \\ 68.7968p_1 + 62.0658(1 - p_1) \\ 69.0914p_1 + 61.5714(1 - p_1) \\ 68.8167p_1 + 62.0439(1 - p_1) \\ 69.0369p_1 + 61.6779(1 - p_1) \\ 41.7249p_1 + 76.5944(1 - p_1) \\ 39.8427p_1 + 77.1759(1 - p_1) \\ 39.8334p_1 + 77.1786(1 - p_1) \end{Bmatrix} \end{equation} $$ 我们认识最上面两个熟悉的线性函数，其他的都对应着特定的测量和动作选择序列。

简单的分析一下就会发现剪枝是很必要的。如果没有剪枝，每个更新操作都会引入两个新的线性约束，即运动选择，接着就会产生约束数量的平方个测量约束。因此对于\(T = 20\)的周期， 未剪枝的值函数就会产生\(10^{547864}\)个线性函数，对于\(T = 30\)则有\(10^{561012337}\)个线性约束。而相比之下，剪枝的值函数只有13个这样的约束。

(a). 周期为\(T = 10\)的\(V_{10}(b)\) (b). 周期为\(T = 20\)的\(V_{20}(b)\)
图 15.5. 针对周期为\(T = 10\)和\(T = 20\)的值函数\(V\)。注意图中的纵轴与之前的图表范围不一样。

这种线性碎片的巨大爆炸是朴素的POMDP实现是不现实的关键原因。图15.6中对比了剪枝和未剪枝的计算值函数\(V_2\)的各个步骤。图(a)(c)(e)中显示了我们的剪枝后的函数， 而(b)(d)(f)中则是没有剪枝的所有线性函数。尽管这里只有一个测量更新，没用的函数数量就已经很大了。后面我们设计高效的近似POMDP算法时，还会回到这个问题上。

(a). 剪枝的\(V_1(b)\) (b). 没有剪枝的\(V_1(b)\) (c). 剪枝的\(\bar{V}_1(b)\) (d). 没有剪枝的\(\bar{V}_1(b)\) (e). 剪枝的\(V_2(b | u_3)\) (f). 没有剪枝的\(V_2(b | u_3)\)
图 15.6. 对于最初几步的POMDP规划算法(b)(d)(f)，与剪枝算法(a)(c)(e)的对比。显然，没有剪枝的化线性约束的数量增长的很快。 在\(T = 20\)的时候，未剪枝的值函数就有\(10^{547864}\)个线性函数了，而剪枝的只有13个这样的函数。

任何有限周期的最优值函数时连续的，分段线性化的，并且是凸的。每个线性片段都对应着未来同一时刻的不同运动选择。值函数的凸性也说明了一个符合直觉的结论，就是知道总比不知道好。 给定两个置信度状态\(b\)和\(b'\)，置信度状态的混合值都大于或者等于混置信度状态的值，对于一些混合参数\(0 ≤ \beta ≤ 1\)： $$ \begin{equation}\label{f34} \beta V(b) + (1 - \beta)V(b') ≥ V(\beta b + (1 - \beta)b') \end{equation} $$ 这一特征只在有限周期的情况下成立。在无限周期中，值函数可以是不连续的和非线性的。

15.3 有限世界POMDP算法

在之前的章节中通过例子说明了如何计算有限世界的值函数。这里在从第一性原则触发推导一个通用的计算值函数的算法之前，我们先简单讨论一下它。

算法15.1中列出了POMDP算法。该算法只有一个输入参数，POMDP的规划周期。它返回的是一个参数向量集合，每个都有如下的形式 $$ \begin{equation}\label{f35} (v_1, \cdots, v_N) \end{equation} $$ 这些参数各个都描述了一个置信度空间的值函数，其形式为 $$ \begin{equation}\label{f36} \sum_i v_i p_i \end{equation} $$ 实际的值由所有这些线性函数的最大值决定: $$ \begin{equation}\label{f37} \max_{(p_1, \cdots, p_N)} \sum_i v_i p_i \end{equation} $$ 算法POMDP递归的计算这个值函数。在算法15.1的第二行中，设定伪周期\(T = 0\)的初始集合。算法POMDP接着就在第3到24行中的嵌套循环中迭代的计算新的集合。 其中第9行是关键的计算过程，线性函数的协同参数\(v_{u,z,j}^k\)需要计算下一个线性约束集合。每个线性函数都是执行动作\(u\)的结果，接着是观测到的测量值\(z\)，然后执行控制\(u'\)。 对应于\(u'\)的线性约束时在上一次迭代时针对较小的规划周期计算的。因此到第14行，该算法为每个控制动作、测量值、以及之前值函数的线性约束的组合都生成了一个线性函数。

算法 15.1. 用于离散世界的POMDP算法。该算法用一个线性约束集合表示最优值函数，它是可以递归计算的。

新值函数的线性约束通过在14到21行对测量值的期望计算得到。对于每个控制动作，该算法在第15行生成\(K^M\)个这样的线性约束。这是一个很大的值，因为每个期望都有\(M\)个可能的测量值， 而每个测量值又可以组合上次迭代的值函数的\(K\)个约束。如此得到的约束将在第19行添加到新的约束集合中。

算法15.2中列举了寻找最优控制动作的算法。其输入是参数化表示的置信度状态\(b = (p_1, \cdots, p_N)\)，以及线性函数集合\(\Upsilon\)。通过在所有的线性函数中的搜索，选择其中能够使得\(b\)达到最大值的， 作为最优动作。在policy_POMDP的第3行返回该值。

算法 15.2. 根据线性函数集合\(\Upsilon\)确定最优动作的算法。

15.4 POMDPs的数学推导

暂略

15.5 实际考量

到目前为止讨论的值迭代算法离实际应用还差的很远。对于任何合理的状态、测量值、控制的数量，值函数的复杂度都是及其巨大的，即使是在规划周期的起始阶段。

我们有很多机会来实现更高效的算法，在我们的例子中就已经讨论了一种。线性约束的数量很快就会增长到一个巨大的数量，幸运的是，我们可以安全的忽略其中很多线性约束， 因为它们对于最大值没有任何实质性的贡献。

值迭代算法的另一个缺点就是它需要计算所有置信度状态的值函数，而不是最可能的哪个。当机器人从一个定义良好的置信度状态开始，所能到达的置信度状态数量通常小很多。 比如说，如果机器人尝试通过两个门，它并不确认这两个门是否开着。当到达第2个门的时候，它就可以确切知道第一个门的状态。因此不可能只知道第二个门的状态却不清楚第一个门的状态。 在很多领域中，置信度空间中有大量的子空间是不可能到达的。

即使对于可达的置信度，有些也只在极小的概率下才能到达。其他的可能不满足需求，所及机器人总是会避免它们。值迭代算法并不区分它们。实际上， 值计算所需要的时间和资源与实际关联的置信度状态的概率无关。

还有很多算法在计算值函数的置信度状态子空间上具有更多的选择性。其中一个就是基于点的值迭代point-based value iteration, PBVI。它的思想就是维护一个典型的置信度状态集合， 对至少一个置信度状态最大化其值函数。更具体的，假设我们有一个置信度状态集合\(B = \left\{ b_1, b_2, \cdots \right\}\)，称为置信度点belief points。 那么关于\(B\)的削减的值函数reduced value function\(V\)就是一个约束的集合，对于每个\(v \in V\)我们都可以找到至少一个\(b_i \in B\)使得\(v(b_i) = V(b_i)\)。 换句话说，就是要抛弃不符合\(B\)的任何离散置信点的线性分段。原始的PBVI算法通过不产生不被任何点支持的约束，来高效地计算值函数。但是，相同的思想也可以通过， 剪去由标准地POMDP支持算法生成地所有line segments来实现。

维护一个置信度点集合\(B\)地思想可以使得值迭代地效率显著提高。图15.7a中所示的值函数是另外一个例子，它与15.2节中的例子在一个方面有所差别: 其状态转移函数是确定性的，就是将式(\(\ref{f7}\))中的0.8替换为1，0.2改为0。图15.7a中的值函数是周期为\(T = 30\)的最优值。小心的剪枝使得约束从\(10^{561012337}\)个下降到了120个。 对于一个简单的点集合\(B = \left\{ p_1 = 0.0, p_1 = 0.1, p_1 = 0.2, \cdots, p_1 = 1 \right\}\)，我们所获得的值函数如右边的图15.7b所示。这个值函数是近似的，而且它只有11个线性函数。 更重要的是，它的计算速度要快1000倍。

(a). 剪枝的值函数\(V_{30}(b)\) (b). PBVI的值函数\(V_{30}(b)\)
图 15.7. 基于点的值迭代相比于通用值迭代地优势，图(a)中显示了周期为\(T=30\)地确切值函数，剪枝后有120个约束。 右边是PBVI算法地结果只保留了11个线性函数。这两种方法在控制上基本没有差别。

使用置信度点还有第二个重要意义，就是可以选择与规划过程紧密相关的置信度点。有很多启发式规则可以确定一个置信度点集合。主要就是通过在POMDP中仿真机器人等手段，来确定可达的置信度， 并且找到那些相互距离比较合理的置信度。这样做通常可以获得比POMDP算法快几个数量级的算法。实际上，我们可以增量的扩展集合\(B\)，每当新添加一个置信度点，就添加它们的所有新线性约束， 如此增量的构建值函数集合\(V_1, V_2, \cdots, V_T\)。这样，规划算法就变成了anytime的形式，随着时间的发展，它所产生的结果会越来越好。

在机器人学中有一种新兴的观点，出色的置信度状态数量胜于只是用常数因子的状态数量。因此，在置信度空间中主动选择合适的区域，来在规划过程中更新。 这与平面的、未选择值迭代方法的缩放特性有根本的不同。

图15.8和图15.9中给出了PBVI的一个典型的机器人策略。图15.8a中描述了一个在室内环境中的占用栅格地图，该地图中有一个长长的走廊和一个房间。机器人从图中的右端开始。 它的任务是找到一个做布朗运动的入侵者。为了让PBVI规划适用于这个任务，需要有一个低纬度的状态空间。这里所用的状态空间如图15.8b所示。它把上个地图划分为22个离散的区域。 这个划分粒度足以解决这个任务，同时使得计算PBVI的值函数称为可能。

(a) (b)
图 15.8. 室内环境，我们尝试为需按照一个移动的入侵者提供控制策略。(a) 占用栅格地图，(b) POMDP使用的离散状态集合。 机器人成功的跟踪了它的位置，其位姿的不确定度可以忽略。剩余的不确定性是人的位置。Courtesy of Joelle Pineau, McGill University。

寻找这样一个入侵者的任务的概率特性是与生俱来的。任何控制策略都必须意识到环境的不确定性，并尝试减少它。此外，它本身就是动态的。只有在空间中的移动还没有充分的描述。 图15.9中显示了一个典型的POMDP规划的结果。这里机器人必须确定一个控制策略，首先探索相对较小的房间，接着沿着走廊前进。这个控制策略应用了一个特性，当机器人扫描房间的时候， 入侵者没有充足的时间通过走廊。因此这个策略具有很高的成功概率。

(a)\(t = 1\) (b)\(t = 7\) (c)\(t = 12\) (d)\(t = 17\) (e)\(t = 29\)
图 15.9. 一个成功的搜索策略。这里通过例子滤波器来跟踪入侵者的位置，并将其投影到POMDP使用的直方图表示形式上。 机器人首先清除了顶部的房间，接着沿着走廊前进。Courtesy of Joelle Pineau, McGill University。

这是一个使用POMDP值迭代的方式解决真实机器人控制问题的例子。即使使用积极的剪枝策略的PBVI，值函数的结果仍然受限于少数的几十个状态中。 只要找到了这样一个低维状态表示方法，POMDP技术就可以通过机器人内在的不确定度得到出色的结果。

15.6 总结

本章中，我们介绍了在不确定环境下用于机器人控制的基本值迭代算法。

本章中列举的材料在恨到程度上都是理论层面上的。值迭代算法定义了大量高效的决策算法的基本更新机制。但是，它自己并不是可计算的。高效的计算就是一种近似，比如说这里讨论的PBVI技术。

15.9 参考文献

在不确定性下做决策的主题已经在统计学中得到了充分的研究，也就是所谓的实验设计。这一领域中的关键读本有Winer et al. (1971) and Kirk and Kirk (1995)， 最近的工作可以在Cohn (1994)中找到。

本章中描述的值迭代算法可以追溯到Sondik (1971) and Smallwood and Sondik (1973)，他们是第一个研究POMDP问题的人之一。其它早期的工作可以在文献Monahan (1982)中找到， 以及文献Lovejoy (1991)中早期的基于栅格的近似方法。 POMDP的查找策略因为巨大的计算复杂度很长时间都被认为是不可行的。这个问题被Kaelbling et al. (1998)引入到了人工智能领域。 Cassandra et al. (1997) and Littman et al. (1995)中的剪枝算法对之前的算法做出了重大的改进。伴随着计算机速度和内存数量的提升，他们的工作使得POMDPs成长为一个解决小型AI问题的工具。 Hauskrecht (1997)提供了解决POMDP问题的复杂度边界。

伴随着下一章中将要讨论的近似技术的到来，产生了这一进程的最重大的浪潮。Hauskrecht (2000)设计了一种改进的POMDP置信度空间的栅格近似。Brafman (1997)介绍了不同分辨率的栅格。 可达性分析开始在计算策略中起作用了。Poon (2001) and Zhang and Zhang (2001)开发了基于点的POMDP技术，在该技术中置信度状态集合是有限制的。与Hauskrecht’s (2000)的工作不同的是， 这些技术依赖分段线性函数，来表示值函数。这个技术在Pineau et al. (2003b)的基于点的值迭代算法中达到了顶峰。他们开发了新的anytime技术，通过搜索相关置信度空间来解决POMDPs问题。 后来他们的工作被Pineau et al. 2003a扩展到了基于树的表达形式中。

Geffner and Bonet (1998)将动态规划应用到离散版本的置信度空间中解决了很多挑战性的问题。Likhachev et al. (2004)扩展了这个工作， 他将A*算法(Nilsson 1982)应用到一个受限制的POMDP问题中。Fergu-son et al. (2004)将之扩展到动态环境中的D*规划(Stentz 1995)。

另外有一族使用粒子计算策略的技术，配合着粒子集合空间的最近邻定义了一种值函数的近似(Thrun 2000a)。Poupart et al. (2001)还将粒子用于POMDP监视。 Poupart and Boutilier (2000)设计了一种算法，使用一种对值本身敏感的技术做出近似，得到了目前最好的结果。Dearden and Boutilier (1994)的一种技术通过交替的规划和执行部分策略，获得了效率。 参考文献Smith and Simmons (2004)额外研究了启发式的交替规划搜索和执行的方法。使用Pineau et al. (2003c)讨论的域知识，以及Washington (1997)提供了有边界的增量技术。 Aberdeen (2002); Murphy (2000b)讨论了其它一些近似解决POMDP问题的工作。CMU的Nursebot是已知的少数几个使用POMDP值迭代进行控制的系统， 它的上层控制器和对话管理器就是POMDP的(Pineau et al. 2003d; Roy et al. 2000)。

一种搜索POMDP控制策略的替代方案就是直接在策略空间中搜索，而不计算值函数。这一思想要追溯到Williams (1992)，他开发了在MDP的上下文中进行策略梯度搜索技术。 Baxter et al. (2001) and Ng and Jordan (2000).描述了当前的策略梯度搜索技术。Bagnell and Schneider (2001) and Ng et al. (2003)成功的将这种技术应用于自主直升机的悬停控制。 实际上，Ng et al. (2003)报告说他使用一个学习的模型，只用了11天就设计了这样一个使用POMDP技术的控制器。在更近期的工作中， Ng et al. (2004)使用这些技术来确认一个控制器反转直升机飞行的能力，这是一个开放问题。Roy and Thrun (2002)将策略搜索技术应用到机器人导航中，并讨论了策略搜索和值迭代技术的组合。

在学习POMDP模型方面的进展相对较小。早期从环境的交互过程中学习一个POMDP的模型的尝试失败了(Lin and Mitchell 1992; Chrisman 1992)，因为问题难度很大。 一些近期学习层级模型的工作中更有前景(Theocharous et al. 2001)。近期的工作已经从学些隐马尔可夫链(HMM)形式的模型中离开了，进入了另一个表达方式中。 表示和学习部分可观测随机环境的技术可以在文献Jaeger (2000); Littman et al. (2001); James and Singh. (2004); Rosencrantz et al. (2004)中找到。 尽管这些论文都没有完全解决POMDP问题，他们也都是很聪明的方法，而且为概率学机器人控制的大型开放问题提供了新的思路。

15.8 练习

暂略




Copyright @ 高乙超. All Rights Reserved. 京ICP备16033081号-1