第十四章：马尔可夫决策过程

14.1 动机

本章是本书中第一个关于概率规划和控制的章节。到目前为止，本书只讨论了机器人感知技术。我们已经讨论了很多概率算法，根据传感器的数据估计感兴趣的量。但是任何机器人软件的终极目的都是选择正确的行动。本章和后续的章节中将讨论针对行动选择的概率学算法。

为了推动对概率学规划算法的研究，我们考虑如下的一些问题。

一个机械手抓住并组装传送带上以随机形态到来的部件。部件到来的形态是未知的，但是最优的操作策略需要这些配置的信息。机器人该如何操作这些碎片? 有必要感知它吗? 如果需要，那么所有的传感策略都是一样好的吗? 存在一种操作策略不需要感知就可以得到很好的配置方式吗?
有一个水下机器人要从加拿大运动到里海。它应该冒着在冰面下迷失方向的分线通过北极走最短的路线吗？还是绕点远路从开放的水域过去呢？这样它可以频繁的使用GPS重定位。这样的决策在多大的程度上依赖于潜艇内部传感器的精度呢？
对于一个探索未知星球的机器人队伍尝试获得一个联合地图。这些机器人应该相互确认它们的相对位置吗？还是说他们应当尽量避免相互碰面，在更短的时间里探索更多的未知地形? 当不知道机器人的相对起始位置时，又该如何修改最优的探索策略呢？

这些问题说明很多机器人任务中的运动选择都与不确定性有着紧密的联系。在一些任务中，比如说机器人探索，降低不确定度时运动选择的直接目标。这个问题称为信息收集任务information gathering tasks。我们将在第17章中研究它们。在其它情况中，降低不确定度几乎是达到一些其它目的的手段，比如准确的到达目标位置。这些任务将在本章和下一章中介绍。

从算法设计的角度来说，我们常把不确定度分为两种类型:运动的不确定度，和感知的不确定度。

首先，我们将确定性的deterministic和随机性的stochastic运动结果区分开。很多机器人学中的理论结果都是建立在控制运动的结果时确定性的假设上的。实际上，运动会引入不确定性，因为运动的结果就是不确定的。不确定性源自于机器人及其工作环境自身的随机特性，这使得机器人在执行期间感知并对不可预见的情况做出反应，即使环境的状态是完全可观测的。运动过程中足够规划一个运动序列并盲目的执行它(译者按:最后这句话就是废话)。

其次，我们区分完全可观测系统和部分可观测系统。经典的机器人通常假设传感器可以测量环境的完全状态。如果总是这样，那么我们就不需要写这本书了！实际上，这种情况经常不成立。基本上所有的真实世界中的机器人问题，传感器的限制都是一个关键的因素。

显然，机器人在决定做什么的时候需要考虑它们当前的不确定度。在选择一个控制运动的时候，机器人至少要考虑各种结果，有些可能导致灾难性的后果，并根据这些结果可能出现的概率为之赋予权重。机器人控制必须处理未来的可预测的不确定性anticipate uncertainty。后者的示例我们在前面已经给出，当时我们在讨论机器人必须在一个没有GPS环境下的更短的路径，和一个更长的迷失风险较低的路径之间做出选择。最小化可预期的不确定度是很多机器人应用中的基础。

通过本章，我们将做出一个非常宽泛的综述，并且并不区分规划和控制。基本上规划和控制处理的都是一个问题——选择运动。它们在必须选择运动的时间约束上有所区别，而且执行过程中的传感器角色也不相同。本章中描述的算法在离线优化或者规划上都很相似。规划阶段的输出就是一个控制策略，描述了针对任何合理情形的控制动作。换句话说，控制策略实际上就是一个控制器。从这种意义上来说，它将在最小的计算时间里确定机器人的动作。需要选择算法并不意味着这是机器人学中处理不确定度的唯一方法。实际上，它反映了目前概率机器人学中算法风格。

本章中讨论的大多数算法都假设状态和运动空间是有限的。连续的空间则通过栅格的形式近似。后面四章内容组织如下:

本章中深入讨论了两种类型不确定的作用以及它们对算法设计的影响。作为第一个约束类问题的解决方案，我们引入值迭代value iteration，这是一种流行的概率系统的规划算法。本章中的讨论只限于第一种类型的不确定性，机器人的运动不确定性。它依赖于一个假设，就是状态是完全可观测的，其背后的数学框架就是所谓的马尔可夫决策过程Markov decision processes, MDP。
第15章中针对运动和感知两种类型的不确定性，对值迭代技术做出了扩展。该算法将值迭代应用于置信度状态表示中。该算法背后的框架称为部分可观测的马尔可夫决策过程partially observable Markov decision processes, POMDPs。POMDP算法预估不确定性，主动收集信息，并给定表现目标的最优值。第15章还讨论了各种近似方法，用于高效的计算控制策略。
第16章中介绍了一些针对POMDP的近似值迭代算法。这些算法有一个共同点，就是对概率规划过程进行近似，因而可以获得计算效率。有一种方法位概率规划提供了捷径，它假设在未来的某个时间点，状态就会变成完全可观测的。另有一种算法将置信度状态压缩到了一个低维的表示空间中，并在这个空间中做出规划。第三种算法使用粒子滤波器和机器学习的方法，来浓缩问题空间。所有的这三种算法都对计算有理想的提升效果，而且在实际机器人应用中表现很好。
第17章处理专门的机器人探索问题。这里机器人的目标就是收集关于环境的信息。尽管探索技术也会面临传感器不确定性的问题，这一问题也比完全POMDP问题简单很多，因此可以更高效的被干掉。概率探索技术在机器人学中很流行，因为机器人被频繁的用于获取未知空间中的信息。

14.2 动作选择的不确定性

图14.1中描述了一个类似玩具的环境，我们将用它来介绍机器人可能遇到的不同类型的不确定性。图中是一个移动机器人移动在一个类似走廊的环境中。这是一个高度对称的环境，唯一的区分特征就是其远端的形状不一样。机器人从图中的指示位置开始运动，它尝试到达标记的位置上。我们注意到有很多路径可以到达这个目标，有一条路很近但是很窄，另外两条路比较长但是路宽。

图 14.1. 一个具有窄的和宽的走廊的近似对称的环境。机器人在场景中间以未知的方向角开始运动。它的任务是运动到坐标的目标位置上。

在传统的机器人规划范式中是不存在不确定性的。机器人只是直到它的起始位置和目标位置。此外，在物理世界中执行的动作具有可预测的效果，而且这种效果是可以预规划的。在这种情况下，就没有必要感知。连续规划一个动作序列就足以在运行时执行了。图14.1中显示了这样的一个规划。显然，在机器人的运动没有误差的情形下，窄而短的路径要比另外两个较宽的路径要好。因此，一个传统的规划器就倾向于选择前者。

在实际应用中，这样的规划有不止一种原因导致失效。机器人盲目的行走在狭窄的走廊中，有撞墙的危险。此外，因为在执行规划过程中累积的误差，可能导致盲目的操作机器人而丢失目标位置。实际上，这种规划算法常常与一个基于传感器的反馈控制模组一起工作，如此得到的传感器读数可以用来修正规划，从而避免碰撞。这样的模组可能可以防止机器人在狭窄的走廊里碰撞。到那时，为了达到这一目的就不得不降低机器人速度，这使得狭窄的路径不如较长的大路。

在机器人运动中考虑不确定性的范式就是所谓的马尔可夫决策过程Markov decision process, MDP。MDP算法假设环境的状态可以在所有时间被完全感知。换句话说，感知模型$p(z|x)$是确定性的并且是一一映射。运动模型$p(x' | u, x)$可能是非确定性的。因此，不足以规划一个单一的动作序列。规划器所生成的运动，必须能够处理机器人可能面对的因为自身运动或者环境中其它不可预测的动态特性所产生的所有情况。这种从状态到动作的映射有很多名称，比如说控制策略control policy，通用规划universal plans，导航函数navigation functions等。

(a)

(b)

图 14.2. 确定的(a)和不确定的(b)运动效果下的MDP的值函数和控制策略。在确定性模型中，机器人完美的导航通过了狭窄的路径。当控制结果存在不确定性，它倾向于选择较长的路径，降低撞墙的风险，如图(b)所示。

如图14.2所示一个策略的示例。与其提供一个单一的运动序列，机器人计算一个从状态到运动的映射，如图中的箭头所示。一旦计算出了这样的一个映射，机器人就可以通过感知世界的状态并对应的做出运动来适应非确定的环境。图14.2a中显示了一个策略，图中的机器人几乎没有运动不确定性，在这种情况下狭窄的路径就适合了。图14.2b中描述了相同的情况，只是增加了机器人运动的随机特性。图中的狭窄路径更可能发生碰撞，更倾向于绕路。这个例子说明了两个事情，在运动规划过程中考虑不确定性的重要性，并且使用本章中描述的算法可以找到一个好的控制策略。

现在让我们回到最一般的，完全概率的情况，抛掉状态时完全可观测的假设。这种情况称为部分可观测马尔可夫决策过程partially observable Markov decision processes, POMDP。在大多数不是所有的机器人应用中，测量值$z$是状态$x$的具有噪声的映射。因此，状态只能在一定的程度上得到估计。为了说明这点，让我们再次回到我们的例子中，并做出不同的假设。假设机器人知道自己的初始位置，但是不知道它是朝左还是朝右。此外，它没有传感器来感知它是否到达了目标位置。

显然，环境的对称性使得消解方向上的歧义很困难。通过直接朝着目标状态移动，机器人有50%的概率丢失目标，并运动到环境中的对称位置上。因此最优的规划，就是先运动到环境中的任何一个角落，这样感知信息就足够丰富，可以消除方向的歧义了。图14.3a中显示了这样的一种运动策略。基于其初始方向，机器人可能沿着图中的两个路径之一运动。当它走到了角落中，它的传感器就揭示了其朝向，因此得到了其相对于环境的实际位置。机器人可能发现它在图14.3b或者c中的一个位置上，从这点出发它就可以安全的导航到目标位置。

(a)

(b)

(c)

图 14.3. 在POMDP中收集动作信息。为了以超过50%的机会到达它的目标，置信度状态空间规划器，首先导航到一个可以确定全局方向的位置。图(a)中显示了对应的策略，以及机器人可能的运行路径。基于这个位置，机器人将发现它在图(b)还是图(c)所示的位置上，从这一点出发，它将安全的导航到目标点。

这个例子说明了概率机器人学中的一个关键。机器人必须主动收集信息，为了做到这点，机器人可能需要绕道来确认它的状态。这个问题在机器人学中至关重要。几乎任何机器人任务，机器人的传感器在了解从哪里可以获得什么信息都有内在的限制。类似的情况在定位和找回、星际探索、城市搜索和救援等任务上也会发生。

现在的问题就变成了如何设计一种运动选择算法来处理这种类型的不确定性。我们将看到，这并不是一个无关紧要的问题。我们可能需要根据当前状态的知识，分析每种可能的情况，来决定该做什么。在我们的例子中，有两种这样的情况，一种是机器人初始方向的左上方，另一种是其右下方。在这两种情况下，优化策略都不能通过这两个地方消除其位置的歧义，确定机器人的位置。在部分可观测的环境中的规划问题是不能通过考虑所有可能的环境和解决方案的均值来解决。

关键的思想就是在置信度空间belief space(信息空间的同义词information space)中生成规划。置信度空间组合了机器人掌握的所有的后验置信度空间。图14.3中的三幅子图描述了我们的例子的置信度空间。上图显示了这样的置信度空间策略，它显示了机器人未知自己方向时的初始策略。在这个策略下，将机器人导航到环境中的一个角落里，在那里机器人可以确定自己的位置。一单定位之后，它就可以安全的导航到目标位置上，正如图14.3中下面两幅图中所示。因为每个朝向的先验概率都是一样的，机器人将经历一个随机变换，有50%的机会到达下面两幅子图中所示位置的其中一个。

在我们的小例子中，不同的状态数量是有限的，机器人要么知道要么没有一点线索。在实际应用中，通常不是这样的。有限数量状态的世界中，置信度空间通常是连续的，但是维度是有限的。实际上，置信度空间的维度与该空间下的状态数量一样。如果状态空间是连续的，置信度空间将有无限的维度。

这个例子中说明了一个基本的属性，机器人不能完美的感知世界的状态，它的重要性在机器人学中常常不被人重视。在位置的世界中机器人规划算法在做控制决策的时候必须考虑状态信息。也就是说，只考虑最可能的状态是不充分的。通过建立在置信度状态的运动，而不是最可能的实际状态，机器人可以主动的收集信息。实际上，在置信度空间的最优规划就会最优的收集信息，它只寻求新的信息来扩充知识，实际上有助于生成机器人的运动。相比于传统的、确定性的、全知的方法，产生最优的控制策略的能力是概率学方法的关键优势。然而，我们将会看到，它将付出复杂度增加的代价。

14.3 值迭代

我们的第一个寻找控制策略的算法称为值迭代value iteration。值迭代递归的计算每个动作的作用，及其回报函数。本章中我们的讨论将想定在第一类的不确定性，机器人和物理世界的随机性。关于由于传感器的限制带来的不确定性的讨论将推迟到后续的章节中。因此，现在我们假设世界的状态在任何时间点都是完全可观测的。

14.3.1 目标和回报

在描述一个具体的算法之前，让我们首先以更简明的形式定义问题。一般的，机器人运动的选择是由目标goal驱动的。目标可能对应着特定的配置，比如成功被机械臂抓取和装配的部件，或者它们可能表示在长时间内维持的状态，比如倒立摆的平衡。在机器人学中，我们有时需要在达到特定目标配置的同时，优化其他的参数，通常由代价cost来衡量。比如，我们可能希望在移动机械臂的执行末端到特定位置的同时，最小化时间、能量消耗、或者与障碍物的碰撞次数。

乍一眼看来，我们可能倾向于用两个量来表示这些需求。我们期望最大化其中一个量，比如用于标志机器人是否到达目标位置的二值量。同时期望最小化另一个量，比如机器人消耗的总体能量。这两个量可以用一个称为回报函数payoff function的函数来表示。

令$r$表示回报，它是一个关于状态和机器人控制的函数。下面就是一种简单回报函数的例子: $$ \begin{equation}\label{f1} r(x, u) = \begin{cases} +100 & \mathrm{if}\ u\ \mathrm{leads\ to\ a\ goal\ configuration\ or\ state} \\ -1 & \mathrm{otherwise} \end{cases} \end{equation} $$ 这个汇报函数"奖励"机器人$+100$，如果它能达到目标配置，否则只要机器人没有达到配置，就在每个时间点上"惩罚"机器人$-1$。如果机器人能够以最短的时间达到目标配置，那么这样的一个回报函数将返回一个最大的累积量。

为什么使用一个单一的回报变量来表示目标达成度和代价？这主要有两个原因：首先，这样的符号表示可以避免后续的公式过于混乱，它可以统一本书中处理代价和目标达成度的方式。其次，并且是更重要的一点，它是在目标达成度和代价之间做出权衡的依据。因为机器人与生俱来的不确定性，它们不能确定的知道目标配置是否达成了。我们所能期望的是它以最大的可能达到了目标。这种在目标达成度和代价之间的权衡可以用一个问题来总结:增大达成目标的概率所付出的代价是否值得？用一个数值因子处理目标达成度和代价，使得我们可以在它们之间做出权衡，因此提供了一个一致的框架，在不确定的情况下选择行动。

我们希望设计一套程序来生成行动，优化未来的回报。这个程序通常称为控制策略control policy，或者简称策略policy。我们用如下的符号表示: $$ \begin{equation}\label{f2} \pi : z_{1:t-1}, u_{1:t-1} \longrightarrow u_t \end{equation} $$ 在完全可观测的情况下，我们有更简单的形式: $$ \begin{equation}\label{f3} \pi : x_t \longrightarrow u_t \end{equation} $$ 因此，策略$\pi$是将过去的数据映射到控制的函数，当状态时可观测的时候，可以说是从状态到控制的映射。

到目前为止，我们的控制策略定义还没有描述它的计算特性。它可能是一个快速的、应激式的算法，只依赖于最近的数据项做出决策；也可能是一个精心设计的规划算法。实际上，必须考虑计算特性，因为任何计算控制的延迟都可能给机器人的表现带来负面的影响。我们关于策略$\pi$的定义也没有承诺它是确定性的还是非确定性的。

在创建控制策略的上下文中的一个有趣的概念就是规划周期planning horizon。有时，它足以选择一个控制动作，最大化下一刻的回报值。大多数时间，动作可能没有立即的回报。比如说，机器人朝着目标位置移动时，只有当他最后到达了其目标才会获得最终的回报。因此，回报可能是有延迟的。一个很是的不表就是选择动作，来最大化所有未来回报的和。我们将称这个和位累积回报cumulative payoff。因为世界是非确定性的，最好是优化预期的累积回报expected cumulative payoff，可以方便的写作: $$ \begin{equation}\label{f4} R_T = E \left[\sum_{\tau = 1}^T \gamma^{\tau} r_{t+\tau} \right] \end{equation} $$ 其中期望$E[·]$是对从$t$到$t+T$时刻累积的回报函数$r_{t+\tau}$的期望。独立的回报$r_{t+\tau}$乘上了一个因子$\gamma^{\tau}$，称为折扣因子discount factor。 $\gamma$的值是一个问题相关的参数，而且被约束在区间$[0;1]$中。如果$\gamma = 1$，对于任意$\tau$我们有$\gamma^{\tau} = 1$，因此这个因子可以从式($\ref{f4}$)中省略掉。 $\gamma$折扣系数在未来将以指数的形式衰减，使得早期的回报值的重要性以指数级的形式优于晚期的。我们将在后于的讨论中详细研究折扣因子的重要性，它与金钱的价值类似，因为通货膨胀，它的值也随着时间以指数的形式衰减。

我们注意到$R_T$是$T$时间步的求和。$T$称为规划周期，或者简称周期。我们讨论三种重要的情况:

$T=1$。这是一种贪婪情况greedy case，机器人只寻求优化下一时刻的回报。尽管这种方法没有考虑一步以后的动作的作用，而有所缺陷，但是它在实际应用中扮演者重要的角色。因为它的重要性源自于，贪婪优化比多步优化简单很多。在很多机器人问题中，贪婪算法是目前已知的解决方案中最好的，可以在多项式时间里完成计算。显然，贪婪优化的折扣因子$\gamma$是不变的，但是必须满足$\gamma > 0$。
$T$大于1，但是有极限。这种情况称为有穷周期finite-horizon case。特别的，回报不是随着时间打折扣的，即$\gamma = 1$。有人可能认为只需要考虑有穷周期的情况，因为所有实际目标的时间都是有穷的。然而，有穷周期的最佳特性通常比折扣的无穷周期下的最佳特性更难获得。为什么会这样？第一个因素是优化控制动作是时间周期的函数。在时间周期的远端附近，最优的策略可能与早期的最优选择有很大的差别，即使在相同的条件(同样的状态，同样的置信度)下也是这样。如此一来，在有穷周期的规划算法将必须为不同的周期维护不同的路径，这将增加不必要的复杂度。
$T$是无穷的。这种情况称为无穷周期infinite-horizon case。这种情况不会面临有穷周期情况相同的问题，因为在任何时间点，剩余的时间步都是一样的。但是，这里的折扣因子$\gamma$就很重要了。为了说明原因，让我们考虑一个场景。我们有两个机器人控制程序，一个为我们每小时赚的一元，另一个每小时赚100块钱。在有穷周期的情况下，后者显然比前者更好。无论周期是多少，后者的期望累积回报都是前者的100倍。在无穷周期的情况下就不是这样的。没有折扣，这两个机器人都将我们赚得无穷的金钱，这使得期望累积回报$R^T$不足以选定哪个是更好的程序。假设每个回报都是有界的，即$|r| < r_{max}$，折扣能够保证$R_{\infty}$是有穷的，尽管求和项是无穷的。具体的，我们有 $$ \begin{equation}\label{f5} R_{infty} ≤ r_{max} + \gamma r_{max} + \gamma^2 r_{max} + \gamma^3 r_{max} + \cdots = \frac{r_{max}}{1 - \gamma} \end{equation} $$ 这说明只要$\gamma$小于1，$R_{\infty}$就是有穷的。我们注意到另一种折扣方法是最大化的平均回报而不是总回报。本书中不会研究最大化平均回报的算法。

有时，我们将在状态$x_t$的条件下累积回报$R_T$，它可以写成如下的形式: $$ \begin{equation}\label{f6} R_T(x_t) = E \left[ \sum_{\tau = 1}^T \gamma^{\tau} r_{t + \tau} |_{x_t}\right] \end{equation} $$ 回报$R_T$的累积是机器人动作选择策略的函数。有时，显式的写出这种依赖关系是有好处的: $$ \begin{equation}\label{f7} R_T^{\pi}(x_t) = E \left[ \sum_{\tau = 1}^T \gamma^{\tau} r_{t + \tau} |_{u_{t+\tau}} = \pi(z_{1:t+\tau -1}, u_{1:t+\tau -1}) \right] \end{equation} $$ 这种表示方式使得我们能够对比两种控制策略$\pi$和$\pi'$，并确定哪一个更好。简单的对比$R_T^{\pi}$和$R_T^{\pi'}$并选择具有更高折扣期望回报的算法。

14.3.2 完全可观测的情况下寻找最优控制策略

本章将给出一个具体的值迭代算法，来计算完全可观测情况下的控制策略。乍一看，该算法是从概率机器人学的基本假设中来的，即状态时不可观测的。但是，在特定的应用中，我们可以安全的假设后验概率$p(x_t | z_{1:t}, u_{1:t})$可以很好的由其期望$E\left[p(x_t | z_{1:t}, u_{1:t})\right]$表示。

完全可观测的场景还是有一定价值的。讨论这样的算法可以为更一般形式的部分可观测的情况做准备。

我们已经注意到，完全可观测状态的随机环境框架被称为马尔可夫决策过程(MDP)。在MDP中，测试是从状态到控制动作的映射: $$ \begin{equation}\label{f8} \pi : x \longrightarrow u \end{equation} $$ 实际上，根据状态就足以决策最优控制，这是我们在2.4.4节中提到的马尔可夫假设的直接结果。在MDP框架下，规划的目标是确定能够最大化未来累积回报的策略$\pi$。

让我们从规划周期$T=1$时优化策略的定义开始，因此我们只关心最优化下一时刻的回报的策略。这个策略记为$\pi_1(x)$并通过最大化1步回报期望来获得: $$ \begin{equation}\label{f9} \pi_1(x) = \arg \max_u r(x,u) \end{equation} $$ 因此，最优的动作就是最大化下一刻回报的期望。选择这样的动作的策略就是最优化预期。

每个策略都关联有一个值函数value function，它对未来折扣回报进行累加，计算了这一特定策略的期望值。对于$\pi_1$，值函数仅仅是下一刻预期的回报值，乘上一个折扣因子$\gamma$: $$ \begin{equation}\label{f10} V_1(x) = \gamma \max_u r(x,u) \end{equation} $$

这个用于长规划周期的值现在就可以写成递归的形式。周期$T = 2$的最优策略选择的控制最大化了一步最优值$V_1(x)$及其下一步的回报: $$ \begin{equation}\label{f11} \pi_2(x) = \arg \max_u \left[r(x,u) + \int V_1(x') p(x' | u, x) dx' \right] \end{equation} $$

显然这种策略是最优的。该策略的值以状态$x$为条件，以如下的折扣表达式给出: $$ \begin{equation}\label{f12} V_2(x) = \gamma \max_u \left[r(x,u) + \int V_1(x') p(x' | u, x) dx' \right] \end{equation} $$ $T = 2$的最优策略和值函数，是通过$T=1$的最优值函数的递归形式构建的。这就意味着对于任何有限周期$T$的最优策略，及其相关的值函数，可以通过$T = 1$的最优策略和值函数递归得到。 $$ \begin{equation}\label{f13} \pi_T(x) = \arg \max_u \left[r(x,u) + \int V_{T-1}(x')p(x' | u, x) dx' \right] \end{equation} $$ 如此得到的策略$\pi_T(x)$是规划周期为$T$的最优形式。其关联的值函数以如下的递归形式定义: $$ \begin{equation}\label{f14} V_T(x) = \gamma \max_u \left[r(x,u) + \int V_{T-1}(x')p(x' | u, x) dx' \right] \end{equation} $$ 对于无穷周期，最优值函数倾向于达到一种平衡，只有一些极少见的确定性系统，不存在这种平衡形式: $$ \begin{equation}\label{f15} V_{\infty}(x) = \gamma \max_u \left[r(x,u) + \int V_{\infty}(x')p(x' | u, x) dx' \right] \end{equation} $$ 这种不变性称为贝尔曼方程Bellman equation。我们注意到每个满足条件($\ref{f15}$)值函数$V$对于得到最优的策略都是必要且充分的。

14.3.3 计算值函数

这一考虑导致在具有完全状态可观测的随机系统中计算最优策略的实际算法的定义。值迭代通过逐次接近式($\ref{f15}$)中的最优值函数来做到这点。

细节上，令$\hat{V}$表示值函数的近似。初始时候，$\hat{V}$被设定为$r_{min}$，即下一刻回报的最小可能值: $$ \begin{equation}\label{f16} \hat{V} \longleftarrow r_{min} \end{equation} $$ 值迭代就可以通过如下的递归形式逐次更新，它为增加的周期计算值函数: $$ \begin{equation}\label{f17} \hat{V}(x) \longleftarrow \gamma \max_u \left[r(x,u) + \int \hat{V}(x')p(x' | u, x)dx' \right] \end{equation} $$ 因为每个更新通过值函数反向的传播信息，通常称之为反向过程backup step。

值迭代规则具有与之前周期$T$的优化规则类似。如果$\gamma < 1$那么值迭代就会收敛，有些特殊情况$\gamma =1$时也会收敛。只要每个状态时无限次更新的，那么状态更新的顺序就与值迭代没有关系。在实际应用中，一般在很少的几次迭代之后就会收敛。

在任何时间点，值函数$\hat{V}(x)$都定义了如下的策略： $$ \begin{equation}\label{f18} \pi(x) = \arg \max_u \left[r(x,u) + \int \hat{V}(x')p(x' | u, x)dx' \right] \end{equation} $$ 值迭代收敛之后，关于最终值函数的贪婪策略就是最优的。

我们注意到所有的这些等式描述的都是一般状态空间。对于有限的状态空间，每个等式中的积分都可以通过一个多所有状态的有限项求和来实现。这个求和通常可以高效的计算，因为$p(x' | u, x)$对于相对较少的状态$x$和$x'$通常是非零的。

下面给出了三个算法。一般的值迭代算法MDP_value_iteration适用于任何状态和运动空间。 MDP_discrete_value_iteration是它在有限状态空间的离散变型。policy_MDP用于从值函数中获取最优控制动作。

算法14.1. 针对MDP的值迭代算法。这里描述的是它最常用的形式，以及用有限状态和控制空间下的MDP算法。最下面的算法用于计算最优的控制动作。

第一个算法MDP_value_iteration在第3行中初始化值函数。第5到9行递归的计算值函数。一旦值函数收敛，得到的值函数$\hat{V}$包含着最优的策略。如果状态空间是有限的，积分过程用有限的求和运算来替代，如MDP_discrete_value_iteration所示。因子$\gamma$是一个折扣因子。在算法policy_MDP中处理状态$x$下的最优值函数，并返回最大化预期值的控制量$u$。

图14.4描述了一个针对我们在上面讨论的例子的值函数的例子。每个栅格单元的阴影对应着它的值，白色对应着$V = 100$黑色则是$V = 0$。根据公式($\ref{f18}$)在这个值函数上使用爬山算法就得到了图14.2a所示的策略。

图 14.4. 一个无线周期$T_{infty}$的值函数示例，假设目标状态是一个吸收状态。该值函数导出了图14.2a中的策略。

14.4 机器人控制的应用

简单的值迭代算法可以用于地位的机器人运动规划和控制问题。为了做到这点，我们将引入两个近似。

首先，算法14.1(译者按:原文是14.5，怀疑是笔误)中定义了一个关于连续空间，需要最大化并对连续空间积分的值函数。在实际应用中，常常通过一个离散分解来对状态空间近似，这点与4.1节中的直方图表示类似。类似的，对控制空间离散化也是很常见的。函数$\hat{V}$就可以很容易的通过一个查找表来实现。但是由于维度灾难，这样的离散化工作只适用于低维的状态和控制空间。在更高维的情况下，常常引入学习算法来表示值函数。

其次，我们需要一个状态！正如上面所提到的，可以使用如下的模式来替代后验概率: $$ \begin{equation}\label{f19} \hat{x}_t = E\left[ p(x_t | z_{1:t}, u_{1:t}) \right] \end{equation} $$ 在机器人定位的上下文中，如果我们能够保证机器人重视近似的被定位，而且后验概率中残余的不确定度是局部的，那么这样的近似就可以工作的很好。当机器人进行全局定位或者被绑架了，它也可以工作。

图14.5中举例说明了在机器人路径规划问题的上下文中的值迭代。图中显示了一个机器人配置空间的二维映射。这个配置空间是所有物理上可行的$\langle x, y, \theta\rangle$坐标构成的空间。对于这个机器人，其配置空间通过对地图中的障碍物膨胀机器人的半径得到。膨胀后的障碍物如图14.5所示。


(a)	(b)
图 14.5. 用于机器人运动的状态空间上的值迭代。图中障碍物显示成黑色。值函数有灰色阴影区域表示。针对值函数的贪婪运动选择将产生最优控制，假设机器人的位姿是可观测的。尽管该图中描述的是根据贪婪策略得到的示例路径。

值函数用灰度来描述，越亮的区域值就越高。跟随着最优策略获得的路径到达了预期的目标位置，如图14.5所示。可以看出，值函数是定义在整个状态空间上的，使得机器人无论在什么位置都可以选择一个动作。这对于非确定性的世界是很重要的，在这样的世界中动作对于机器人的状态有随机的影响。

生成图14.5中的路径的路径规划器做了特定的假设，来保持计算量可控。对于可以原地转圈的圆形的机器人，常常只在二维笛卡尔坐标系下计算值函数，忽略了转向的代价。我们也忽略了像机器人速度这样的状态变量，尽管在任何给定的时间点，实际速度都清晰的约束了机器人可以移动的范围。为了将这样的控制策略转换为实际的机器人控制，实际操作总常常将这样的规划器，与快速的、应激臂章模块组合起来，生成满足动力学约束的电机速度。一个考虑了完全机器人状态的路劲规划器至少要在5维的空间上做规划，包括三维的位姿，机器人的线速度和角速度。在低端的PC机上，不需要一秒就可以计算出来，类似上面那样二维环境的值函数。

图14.6a中给出了第二个示例。图中显示了一个具有两个自由度的机械臂模型，他具有肩关节和肘关节。可以通过安装在关节上的编码器，来确定这些关节的确切配置。因此式($\ref{f19}$)中的近似就适用于这个例子。到那时，机械臂的运动通常是有噪声的，这种控制噪声应当在规划过程中考虑到。这使得机械臂控制成为了概率学的MDP类算法的一种主要应用。机械臂运动常常在配置空间中处理，如图14.6b所示。这里的横轴描述了肩关节的转角，纵轴则是肘关节的转角。图中的每个点都对应着一个空间配置。实际上，图14.6b中的小点对应着图14.6a中的配置。


(a)	(b)
图 14.6. (a)一个2自由度机械臂在一个有障碍物的环境中。(b)该机械臂的配置空间，横轴对应着肩关节，纵轴描述了肘关节配置。障碍物用灰色表示。图中的小点对应着左边的配置。

常常将配置空间划分为机器人可以移动的区域和它需要回避的区域，如图14.6b所示。图中白色的区域对应着不会发生碰撞的配置空间，常常称为自由空间。配置空间的黑色边界是由工作台和封闭空间的约束。图14.6a上方伸出的竖直障碍物，对应着图14.6b中间的浅灰色区域。这幅图不是很直观，读者可能需要花几分钟来想象一下机器人碰撞到这个障碍物的配置。

图14.7a中显示了子粗糙离散化的配置空间中的值迭代。这里的值通过一个确定性的运动模型来传播，如图中的路径所示。在执行的时候，这个策略将产生图14.7b所示的运动。图14.8中显示了一个概率运动模型的结果，以及机械臂的运动结果。这里的值迭代假设机械臂的配置是完全可感测的，很少有满足这一假设的例子。


(a)	(b)
图 14.7. (a) 应用在粗糙离散化配置空间的值迭代。(b) 在工作空间坐标中的路径。机器人确实避免了竖直的障碍。


(a)	(b)
图 14.8. (a) 在精细栅格化的概率值迭代。(b) 对应的路径。

14.5 总结

本章介绍了概率学控制的基本框架。

我们明确了机器人可能面临的两类不确定度，控制的不确定度，和感知的不确定度。前者使得它很难确定将要发生什么，而后者使得它很难分辨前面是什么。来自环境的不可预测时间的不确定度默认都会包含到这一类中。
我们通过回报函数定义了控制目标，该函数将状态和控制映射到了一个优劣值。回报值使得我们同时表示行为目标和操作代价。整个控制目标就是最大化所有的、下一刻的、或者未来某个时间点的回报。为了避免可能的无穷和，我们引入了一个所谓的折扣因子对未来的回报打指数级的折。
我们讨论了一种通过设计一种控制策略解决概率学控制问题的方法。这个控制策略定义了将要选用的控制动作，作为一个机器人关于世界信息的函数。如果其最大化未来累积回报的和，那么这个策略就是最优的。这个策略在一个规划阶段计算，超前于机器人的操作。一旦计算结束，它就得到了机器人可能遇到的任何情形中最优的控制动作。
我们设计了一个针对状态完全可观测的情况下的，具体的寻找最优控制策略的算法。这个领域称为马尔可夫决策过程。该算法涉及到值函数的计算，它衡量了预期的累积回报。这个值函数定义了一个贪婪地选择使得值最大化的控制策略。如果值函数是最优的，那么策略也就是最优的。值迭代算法通过递归更新逐渐的提高值函数。
我们讨论了将MDP值递归方法应用于概率机器人学问题中。我们提取了状态的置信度模式，并对一个低维栅格中地值函数做出了近似，使得即使动作效果是非确定性的机器人也能够导航。

本章中的材料是下一章的基础工作，我们将处理更一般的在测量不确定性下的控制问题，也成为部分可感测的MDP问题。我们已经直观的讨论了为什么这个问题比MDP问题困难很多。然而，还是有一些直觉和基本算法处理这种情形。

我们选择本章来简述有很多备选的技术，用于在不确定性下的概率学规划和控制。我们选择值迭代作为基本方法，因为它很流行。进一步的，值迭代技术是最好理解的解决更一般的POMDP情况的技术之一。

值迭代不是最高效的生成控制的算法。一般规划算法包括A*算法，使用一些启发式规则来计算值函数，或者直接策略搜索技术，通过梯度下降法来确定一个局部最优的策略。但是，值迭代在下一章中扮演者轴心的作用，我们将处理更加困难的，在传感器不确定性下的最优控制。

14.6 参考文献

动态规划的思想要追溯到Bellman (1957) and Howard (1960)。Bellman (1957)确定了值迭代的平衡方程，因此它称为贝尔曼方程Bellman equation。 Astrom (1965)第一次讨论了不完全状态估计的马尔科夫决策过程(MDPs)，关于MDP的早期工作还可以参见Mine and Osaki (1970)。自此，针对控制的动态规划就成了一个广阔的领域(Bertsekas and Tsitsiklis 1996)。最近对于基本范式的改进技术包括，实时值迭代(Korf 1988)，通过与环境的交互指引的值迭代技术(Barto et al. 1991)，无模型的值迭代(Watkins 1989)，和用参数表示的值函数的值迭代技术(Roy and Tsitsiklis 1996; Gordon 1995)，或者使用树(Moore 1991) (还可以参考(Mahadevan and Kaelbling 1996))。 Parr and Russell (1998) and Dietterich (2000)开发了层级值迭代技术。Boutilier et al. (1998)通过可达性分析，改进了MDP值迭代的效率。还有很多值迭代应用的文献，比如Barniv (1990)在移动目标检测上的例子。在这些大量的文献的光辉下，本章的材料是对最简单的值迭代技术的一个基本探索，为后续章节中要描述的技术做了准备。

在机器人学中，机器人运动规划的问题已经在非概率学框架下得到了研究。正如所提到的，通常假设机器人和它的环境是完全可知的，而且控制具有确定性的结果。复杂度在高维的连续的状态空间中得到了体现。这个领域的标准文献是Latombe (1991)。他的工作还可以向前追溯到很多基本的运动规划技术，可视图(Wesley and Lozano-Perez 1979)，势场控制(Khatib 1986)，以及Canny’s (1987)著名的剪影算法silhouette algorithm。Rowat (1979)介绍了在机器人控制领域中使用Voronoi图的技术， Guibas et al. (1992)显示了如何高效的计算它们。Choset (1996)将这一技术开发成为了一族高效的在线探索和建图技术。还有一组使用随机的但不是概率学的技术搜索机器人路径的可能空间(Kavraki and Latombe 1994)。同期还有一个介绍这个主题的数据Choset et al. (2004)。

在机器人运动规划领域中，本章讨论的方法是近似元胞分解法approximate cell decompositions，在确定性的场景下，不能保证完备性。将连续的空间拆分为有限的图已经在机器人学中研究了几十年。Reif (1979)开发了一系列的技术，将连续的空间拆分为有限个元胞，同时保持运动规划的完备性。配置空间的思想，必须使用本章描述的技术检查碰撞，最初是由Lozano-Perez (1983)提出的。用于配置空间规划的递归元胞分解技术可以在文献Brooks and Lozano-Perez (1985)中找到，其中所有的技术都建立在非概率的假设下认为模型和机器人都是完美的。在部分信息的情况下运动是由Goldberg (1993)提出来的，他在他的博士论文中开发了一种算法，用于在缺少传感器的情况下定位部件。Sharma (1992)开发了有随机障碍的机器人路径规划技术。

为每个可能的机器人状态赋予一个控制动作的策略函数被称为控制器controller。i设计控制策略的算法通常被称为最优控制器optimal controller(Koditschek 1987; Rimon and Koditschek 1992)。配合上AI，它们也被称为通用规划universal plans(Schoppers 1987)，而且很多符号规划算法致力于寻找这样的通用规划(Dean et al. 1995; Kushmerick et al. 1995; Hoey et al. 1999)。有些机器人工作致力于在通用规划和开环运动序列之间架起一座桥梁，比如Nourbakhsh’s (1987)的博士论文。

在本书中有些时候"控制"也是有狭窄定义的。本章特意没有提及那些在控制领域中的标准技术，比如PID控制器还有其它一些流行的技术通常可以在工业的数据中找到(Dorf and Bishop 2001)。显然，这样都是是很多真实机器人系统中所必须而且可行的技术。我们选择省略它们是基于空间约束的，而且大多数这样的技术都不依赖不确定性的显式表达方式。

14.7 练习

暂略。