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

第十七章：探索

17.1 介绍

本章关注于机器人探索的问题。探索就是控制机器人来最大化其关于外部世界的知识。在很多机器人应用中，使用机器人设备的主要目的，即使为用途提供信息。 一些环境本身就可能不适合人类，还有一些环境派一个人过去很不经济，机器人可能是获取信息最经济的手段。探索问题在机器人学中是至关重要的。 机器人已经探索过废弃的矿井，核废墟，甚至是火星。

探索问题有很多不同的方面。比如说，一个机器人需要一个关于静态环境的地图。入托我们用占用栅格地图来表示环境，那么探索问题就是最大化每个栅格单元信息的问题。 这一问题还有一种更为动态的版本，可能涉及到移动的物体。比如，在一个跟踪逃避问题pursuit evasion problem中，机器人需要在已知的环境中寻找一个人。 其目标可能是最大化关于这个人位置的信息，而且找到这个人可能需要探索整个环境。但是，因为人可能会移动，探索策略可能需要多次探索一些区域。 第三种探索问题出现在机器人定位过程中，它尝试确定自己的位置。这个问题通常称为主动定位active localization，其目标就是最大化关于机器人自身位置的信息。 在机器人操控中，当装备有传感器的执行器面临一个未知物体的时候，就会产生一个探索问题。通过这个简单的讨论，我们可以看到探索问题几乎涉及到机器人学的方方面面。

乍一眼，我们可能认为探索问题可以完全包含在之前章节中讨论的POMDP框架中。因为我们看到，POMDPs本身就是致力于信息收集的。将POMDP转换称为一个算法， 纯粹就是要最大化信息，我们所要做的就是为之提供一个合适的汇报函数。一种合适的选择就是信息增益，它测量了机器人置信度的熵减，这是一个关于机器人动作的函数。 在这样的回报函数的加持下，POMDPs就可以解决探索问题。

但是，使用POMDP框架的探索通常不是一个很好的方案。这是因为在很多探索问题中，未知的状态变量是海量的，其可能的观测值数量更是巨大。让我们考虑一个探索未知星球的问题， 用于描述星球表面的变量数量将是不可思量的，机器人可能产生的观测集合也是这样。我们已经发现在通用POMDP框架中，在最差的情况下，规划的复杂度随着观测的数量增加， 以双倍指数的形式增长。因此，计算一个值函数几乎是不可能的。实际上在探索问题中，给定未知状态变量巨大数量的可能值，任何尝试整合所有这些可能值的算法， 都不可避免地因为计算量的问题，不能应用。

本章讨论一组实际的算法，解决高维的探索问题。这里讨论的技术都是贪心的。换句话说，它们的预期都局限于一种探索动作。但是，一个探索动作可能引入一系列的控制动作。 比如说，我们将要讨论选择探索地图位置的算法，运动到那里就被认为是一个探索动作。这里讨论的算法基于感知来近似知识增益，进而降低计算量。

本章内容组织如下:

下面描述的探索技术已经在大量的文献中得到了广泛的讨论，并且得到了大量的实际应用。它们也涉及了很多不同的表示方式和机器人问题。

17.2 基本探索算法

17.2.1 信息增益

探索的关键就是信息。我们已经在概率机器人学中考虑了很多信息的使用方式。在探索的上下文中，我们定义了概率分布\(p\)的熵\(H_p(x)\)， 描述了信息的期望\(E \left[ - \log p \right]\) $$ \begin{equation}\label{f1} H_p(x) = - \int p(x) \log p(x) dx ~~~~~~~~\text{or}~~~~~~~~ -\sum_x p(x)\log p(x) \end{equation} $$ 我们已经在本书的2.2节中简要讨论了熵。如果\(p\)是一个均匀分布， 那么\(H_p(x)\)就会取得它的最大值。当\(p\)是一个质点分布，它就会取得最小值。但是，在特定的连续状态下，比如高斯分布，我们可能永远不能获得完全的置信度。

条件熵conditional entropy是定义在一个条件分布上的熵。在探索问题中，我尝试最小化执行了动作之后的置信度的预期熵。 因此置信度状态变换的定义本身就是以测量值\(z\)和控制量\(u\)为条件的。

遵从之前介绍的符号体系，令\(B(b, z, u)\)表示执行了控制量\(u\)并且在置信度\(b\)下观测到测量值\(z\)的置信度。 那么执行了控制量\(u\)和获得测量值\(z\)之后的条件熵定义如下: $$ \begin{equation}\label{f2} H_b(x' | z, u) = - \int B(b,z,u)(x') \log B(b,z,u)(x') dx' \end{equation} $$ 其中\(B(b, z, u)\)通过贝叶斯滤波器计算。在机器人学中，我们只能根据控制动作\(u\)做出选择，不能挑选\(z\)。因此，我们考虑控制量\(u\)下的条件熵，积分消除测量值: $$ \begin{equation}\label{f3} H_b(x' | u) \approx E_z\left[ H_b(x' | z, u) \right] = \int \int H_b(x' | z, u)p(z | x')p(x' |u, x)b(x) dz dx' dx \end{equation} $$ 注意，这只是一种近似，因为最终的表达式反转了求和和对数运算的顺序。在置信度\(b\)下动作\(u\)的信息增益通过如下的差值给出 $$ \begin{equation}\label{f4} I_b(u) = H_p(x) - E_z\left[ H_b(x' | z, u) \right] \end{equation} $$

17.2.2 贪心技术

期望的信息增益使得我们可以将探索问题刻画成为一个之前章节中处理的决策论问题。具体的，令\(r(x, u)\)为在状态\(x\)下应用控制动作\(u\)的代价， 这里我们假设\(r(x,u) < 0\)。那么对于置信度\(b\)，最优的贪心探索最大化了权重因子\(\alpha\)下，信息增益与代价之间的距离。 $$ \begin{equation}\label{f5} \pi(b) = \arg \max_u \alpha \left(H_p(x) - E_z\left[H_b(x' | z, u)\right]\right) + \int r(x, u)b(x) dx \end{equation} $$ 其中，\(\left(H_p(x) - E_z\left[H_b(x' | z, u)\right]\right)\)为期望的信息增益，\(\int r(x, u)b(x) dx\)是期望的代价。 因子\(\alpha\)在信息与执行\(u\)的代价之间建立了相对关系。它描述了机器人获取信息的值，它测量了机器人为获取信息所愿意付出的代价。

式(\(\ref{f5}\))可以变换为如下的形式: $$ \begin{align}\label{f6} \pi(b) & = \arg \max_u -\alpha E_z\left[H_b(x' | z, u)\right] + \int r(x, u)b(x) dx \\ & = \arg \max_u \int \left[r(x,u) - \alpha \int \int H_b(x' | z, u)p(z | x') p(x' | u, x) dz dx'\right] b(x) dx \end{align} $$ 简单来说，为了了解控制量\(u\)的作用，我们需要计算执行\(u\)和观测之后的期望熵。这个期望熵通过对所有可能的测量值\(z\)积分，并乘以它们的概率得到。 通过常数\(\alpha\)将之转换成为作用。接着我们减去了执行动作的期望代价\(r\)。

大多数探索技术用的都是这种贪心策略，实际上是在周期1上的最优化。之所以依赖于贪心技术，是因为探索中广泛的分支因子，它使得多步规划称为了不可能。 大量的分支因子是探索问题与生俱来的特性。探索的目标是获取新的信息，但是一旦获得了需要的信息，机器人就处于了一个新的置信度状态下了，因此需要调整它的策略。 因此，测量值本身就是不可预测的。

图17.1中描述了这样一个场景，机器人已经对两个房间和部分走廊建了图。此刻，最优的探索可能是探索一个走廊，图17.1a中描述了一个合适的动作序列。 但是，我们很难估计这样的动作序列是否可以执行。比如说，机器人可能如图17.1b所示那样在发现自己在一个死胡同里，预估这样的一个动作序列是不切实际的。

(a) (b)
图 17.1. 探索问题的不可预测性。(a) 机器人可能预估三个控制的序列， 但是这个序列是否可以执行依赖于机器人沿着这个路径找到的信息。任何探索策略都必须快速的反应(highly reactive)。

17.2.3 蒙特卡洛探索

算法Monte_Carlo_exploration是一个简单的概率学探索算法。算法17.1中描述了式(\(\ref{f6}\))的贪心策略的一种蒙特卡洛近似。 该算法在贪心算法中通过采样来替代积分。在第4行中，它从当前置信度\(b\)中对状态\(x\)进行了采样。接着采样下一个状态\(x'\)和对应的观测\(z'\)。 这样就可以在第8行中计算一个新的后验置信度，并在第9行中获得熵-代价权衡量(entropy-cost trade-off)。第12行中返回了具有最高的蒙特卡洛信息增益的动作。

算法 17.1. 贪心探索算法的蒙特卡洛实现，它通过最大化信息增益和代价的权衡量来选择动作。

一般情况下，贪心的蒙特卡洛算法可能任然需要大量的时间，在一定程度上变得不现实。主要的复杂度源自于对测量值\(z\)的采样。 当探索一个未知的环境并建图的时候，可能的测量值数量是巨大的。比如说，对于一个装备了24个超声传感器的机器人，每个都报告一个字节的距离数据， 那么在一个特定的位置上可能的声纳扫描数据的数量是\(256^24\)。当然，并不是所有的这些测量值都是合理的。但是，合理的测量值数量至少与合理的局部地图数量一样。 而对于任何实际的建图问题，可能的地图数量都是海量的！接下来，我们将要讨论通过对期望的信息增益的闭式分析来规避积分的探索技术。

17.2.4 多步技术

在测量值和状态空间受限的情形下，是有可能将信息收集的原则扩展到任何有限周期\(T > 1\)的情形下。假设我们将要最优化周期\(T\)下的信息-代价权衡量(information-cost trade-off)。它是通过如下的探索回报函数获得的:

$$ \begin{equation}\label{f7} r_{exp}(b_t, u_t) = \begin{cases} \int r(x_t, u_t) b(x_t) dx_t & \text{if}~~ t \lt T \\ \alpha H_{b_t}(x_t) & \text{if}~~ t = T \end{cases} \end{equation} $$

在这个回报函数下，POMDP规划器寻找一个控制策略，来最小化最终置信度\(b_T\)的熵与获取这个置信度的代价的差。之前讨论的所有POMDP技术都可用。

读者可能注意到它与之前章节中讨论的扩展MDP类似。其不同之处在于，我们只声明了回报函数，而不是置信度状态表达。因为大部分探索问题在通用POMDP模型中计算量很大， 很难对付，本书中我们将不再进一步探讨这个方法了。

17.3 主动定位

估计低维变量的状态可以得到探索问题的最简单的形式。主动定位就是这样的一个问题，在给定环境地图的情形下，收集关于机器人位置\(x_t\)的信息。 在全局定位问题中，主动定位就特别有意思，因为控制的选择对于信息增益有着极大的影响。在很多环境中，无目标的漫游使得全局定位变得很困难，然而移动到正确的位置上， 可以极快速的定位。

图17.2a中就描述了这样一个环境。这里机器人被放置在一个对称的走廊中，无论探测多长的距离，只要不从一个开着的门中通过离开走廊，它都无法解出它的位置。 因此任何主动定位问题的解决方案，最终都会引导机器人离开走廊进入一个房间中。

(a) 环境和一个示例后验概率 (b) 探索动作的作用
图 17.2. (a) 在一个对称环境中的主动定位: 这里显示的是一个对称的走廊环境，但是房间的布置是非对称的， 分别标记为A,B,C。该图中也显示了一个探索路径。(b) 探索动作示例"后退9米，左移4米"。如果机器人位姿的后验概率，像图示那样有两个模态， 在全局世界坐标下的实际控制可能导致两个不同的位置。

我们可以根据刚刚提及的算法，贪婪地解决主动定位问题。其关键内涵在于动作表达方式的选择上。显然，如果像本书中很多地方提及的那样，将动作定义在一个低级的控制动作上， 任何可行的探索规划都必须引入一个长长的控制链，才能解决位置上的歧义。为了通过贪婪探索来解决主动定位问题，我们需要一个动作的定义，使得机器人可以贪婪的收集信息。

一种可能的解决方案就是定义一个通过目标位置的探索动作，以机器人局部坐标系的形式表示。比如说，"移动到相对于机器人局部坐标系的\(\Delta x = -9m\), \(\Delta y = 4m\)的点"就是这样的一种动作，只要我们可以设计一个低级的导航模块，可以将这个动作回馈到底层控制上。图17.2b中在全局世界坐标系上可视化了这一动作的效果。 在这个例子中，后验概率具有两个模态，因此这个动作可以将机器人带到两个不同的位置上。

相对运动动作的定义，使得我们可以通过一种与算法17.1相同的贪心探索算法，来解决主动定位问题。我们将要通过这个例子描述这个算法。 图17.3a中显示了沿着一系列标记位置的主动定位路径。我们从定位的中间开始，如图17.3b所示，是机器人从位置"1"向位置"2"中移动之后的置信度。这个置信度有6个模态， 每个都对应着图17.3b中的一个圆圈。对于这一置信度，图17.3c中描述了在机器人坐标系中预期的占用值。这个图只是将每个可能的机器人位姿叠加到占用栅格地图上得到的， 通过对应的概率值加权。因为机器人并不确切的知道自己的位置，它并不知道位置的占用情况，导致了预期的代价地图的模糊特性"fuzziness"。 但是，机器人以很高的概率在可以移动的走廊形状的区域中。

(a) 定位机器人的路径 (b) 6个模态的早期置信度分布 (c) 在机器人坐标中的占用概率
(d) 期望的运动代价 (e) 在机器人坐标中期望的信息增益 (f) 增益+代价(颜色越深，结果越好)
图 17.3. 主动定位示例。这幅图中显示了计算最优控制的辅助函数，对于多假设位姿分布。

虽然图17.3c中描述了在目标位置的代价，我们还需要运动到该目标位置的代价。我们已经讨论了一个计算这样的运动代价的算法，及其生成的最优路径——值迭代， 参见第14章。图17.3d中显示了值迭代的结果，它将之应用于图17.3b中的地图，作为代价函数。 这里的值通过机器人向外传播(与第14章中的定义那个，相反与从目标开始传播)。这使得计算移动到地图中任何潜在的目标位置的代价称为了可能。

正如这幅图所示，在机器人附近有很多区域都是安全的。实际上，这个区域对应着走廊，与机器人实际的位置无关。移出这个区域，并进入一个房间中，引入了更高的期望代价， 因为这样的运动的合法性与机器人真实位置相关，但我们却不知道。

对于贪婪的探索，我们现在需要确定期望的信息增益。它可以以一种近似的方法得到，将机器人放置到一个位置，仿真可能的测量值，融合结果，并测量贝叶斯更新之后的信息。 为每个可能的位置重复这一估计过程，就得到了一个期望的信息增益地图，如图17.3e所示。地图中的颜色越深，对应位置就可以提供更多关于机器人位姿估计的信息。 显然，任何一个房间都可以提供很多信息，走廊的尽头也是如此。因此，纯粹从信息收集的角度来看，机器人都应该尝试进入其中一个房间中。

将代价地图与期望的信息增益叠加就得到了图17.3f中所示的结果，颜色越深越好。在这个组合的函数中，房间外的区域仍然具有很高的值， 它们的作用已经被移动的相对较高的代价削减了。在这一点上，走量的尽头具有最高的得分。

现在机器人将移动到具有最高组合值的位置上，这将引导机器人在走廊上仍然安全的区域运动。在图17.3a中，这对应着从位置"2"到位置"3"的变换。

现在再次迭代贪婪的主动探索规则。图17.4a中描述了位置"3"的置信度。显然，之前的探索动作具有削减后验概率中的模态的效果，已经从6个降到了3个。 图17.4b中显示了以机器人为中心的新占用地图。图17.4c中描述了对应的值函数。现在期望的信息增益只在房间中具有相对较高的值，如图17.4d所示。 图17.4e中显示了组合的增益-代价地图。此刻，进入任何一个对称开着门的房间中的运动代价是最低的，因此机器人移动到那里之后，就可以极大的消解歧义。 一个时间步骤之后，经过新一轮的考量之后，得到的最终置信度如图17.4f所示。

(a) 置信度分布 (b) 在机器人坐标系中的占用概率 (c) 期望的运动代价
(d) 在机器人坐标系中期望的信息增益 (e) 增益+代价(颜色越深，结果越好) (f) 执行了主动定位后的最终置信度
图 17.4. 在相对较晚的时间点上的主动定位示例。置信度中有两个不同的模态。

这个贪婪的主动定位算法不是没有缺点。一个缺点源自于它的贪心，他不能组合多个探索动作，从而最大化信息增益。另一个缺点就是我们的动作定义。 该算法不能考虑测量值，而测量值确实移动到目标位置所需要的。实际上，它以一种开环的控制方式来处理这些运动，如此机器人就不能够对测量值做出反应。 显然，如果面对一个关闭的门，真实的机器人可以在到达目标点之前就放弃之。但是，在规划的过程中没有这样的一个条款。这解释了上述示例中的次优选择， 机器人在探索房间A之前探索了房间B。因此，定位倾向于选择一条比理论上更长的路径。但是，这个算法在实际中的表现很好。

17.4 为了学习占用栅格地图的探索

17.4.1 计算信息增益

贪婪探索也可以应用于机器人建图。建图问题涉及到比机器人定位更多的未知变量，因此我们需要一个计算期望的信息增益的技术来解决高位估计问题。 我们将看到，在占用栅格地图中探索的"技巧"，与一个高效更新占用栅格地图的算法，非常类似。我们认为各个栅格单元中的信息增益是独立的。

考虑一个如图17.5a所示的占用栅格地图。部分地图已经被很好的探索了，比如说地图中间的大量空闲区域，而且很多墙和障碍物的位置已经很清楚了。 剩下的部分是未探测的，比如说地图之外大量的灰色区域。贪婪的探索将引导机器人到最近的未知区域中，那里的信息增益是最大的。这就产生了一个如何计算增益的问题。

(a) 占用栅格地图 (b) 元胞熵 (c) 探索的和未探索的区域 (d) 探索的值函数
图 17.5. 针对建图的探索问题的基本步骤示例。(a) 一个部分栅格地图;(b) 地图熵的描述; (c)显示了零信息的区域;(d)描绘了最优探索的值函数。

我们将要讨论三种可能的技术。这三种方法有一个共同点，就是为每个栅格单元计算信息增益，而且不是以机器人动作为函数的。这就可以方便的得到一个信息增益地图， 这是一个定义在与原始栅格地图相同的栅格熵的2维地图。这些技术的不同之处在于近似的质量上。

17.4.2 传播增益

现在剩余的问题就是开发一个使用这些地图的贪心探索算法。正如我们的主动定位的例子一样，它需要一个合适的探索动作的定义。

一个简单有效的定义就是在沿着一个最小代价路径移动到\(x\)-\(y\)位置上，然后感知围绕着机器人的一个小半径的圆所覆盖的所有栅格单元。因此，地图中的每个位置都定义了一个可能的探索动作。

最优贪婪探索动作的计算现在就可以简单的通过值迭代的方式实现。图17.5d中显示了对图17.5a中的地图计算的值函数，其二值信息增益地图如图17.5c所示。值迭代的方法假设有一个二值的增益地图， 只有在未探索的区域才能收割增益。

中心的值更新可以通过如下的迭代过程实现: $$ \begin{equation}\label{f16} V_T(m_i) = \begin{cases} \max_j r(m_i, m_j) + V_{T-1}(m_j) & \text{if}~~I(m_i) = 0 \\ I(m_i) & \text{if}~~I(m_i) > 0 \end{cases} \end{equation} $$ 这里的\(V\)是值函数，\(j\)索引了\(m_i\)附近的所有栅格单元，\(r\)测量移动的代价，通常是一个占用栅格地图的函数，\(I(m_i)\)是我们能够从元胞\(m_i\)获得的信息。 终止条件\(I(m_i) > 0\)只在二维信息增益地图中未探索的栅格单元中才成立。

图17.5d中显示了收敛之后的一个值函数。在地图中开放区域的附近具有最高的值，地图内部的值相对较低。现在探索技术就可以简单的通过在这个地图中的爬山算法来确定最优的路径。 这个路径将引导机器人直接到最近的未探索边界上。

(a) 探索值函数 (b) 探索路径
图 17.7. 自主探索示例(a) 探索值\(V\)，通过值迭代计算。白色区域是完全没有探索的。沿着灰度梯度，机器人以最低代价路径移动到下一个未探索的区域。 大黑举行指示着全局的墙朝向\(\theta_{wall}\) (b) 自主探索过程中实际的运动路径，以及得到的尺度地图。

显然，这个探索技术仅仅是一个粗糙的近似。它完全忽略了机器人移动到目标位置所需要的信息，错误的假设沿途没有感知数据。但是它在实际应用中工作的很好。图17.7中显示了一个值函数和一个探索机器人的地图。 这幅地图很有历史，它是从1994年AAAI机器人大赛上得到的，它以最快的速度获得了环境地图。机器人装备一个24声纳传感器阵列，得到的地图准确度相对较低。机器人的路径是这幅图的亮点，如图17.7b所示， 一开始的探索很有效率，机器人在未探索的走廊里漫游。后来，机器人开始在不同的目标位置间来回切换。这种切换的行为正是贪心探索算法的普遍特点，最新的改进提供了附加的机制来避免这一行为。

图17.8所示的是第二个例子。机器人的路径如图(b)所示，说明了贪心探索算法的效率。

(a) (b)
图 17.8. (a) 用于室内和户外探索的城市机器人。这个城市机器人的里程计很次。(b) 该自主探索机器人生成的探索路径，使用了本文中所描述的探索技术。

17.4.3 多机器人系统的扩展

寻求增益的探索规则经常被扩展到多机器人系统中，机器人通过合作探索来得到一个地图。一般来说，使用\(K\)个机器人的加速效果是线性的。它也可能是super-unitary的，\(K\)个机器人常常比一个机器人的\(K\)倍还快。 这种super-unitary加速效果得益于单一的机器人可能需要对很多地方探索两次，一次是出去并探索，另一次则是探索环境中其它区域的时候还要回来。合适数量的机器人，这种回头路可能就不再需要了， 那么加速效果就接近于\(2K\)。对于那些可以在所有方向上任意导航的机器人而言，\(2K\)是一个上限。

多机器人探索的关键是协同工作。在静态探索中，很容易通过贪心的任务分配技术完成。考虑一个具有\(K\)个机器人的情形，它们被放置在一个部分探索的地图中，有很多边界位置需要探索， 我们需要一个算法位这些机器人分配任务，来贪心地最大化总体探索结果。

算法17.2描述了一个非常简单地多机器人探索算法。它位\(K\)个机器人的集合计算了\(K\)个探索目标，分别分配给各个机器人。

算法 17.2. 多机器人探索算法

该算法首先在第2到10行为每个机器人计算了值函数\(V_k\)。但是，这些值函数的定义与之前看到的有些不一样，最小值实在机器人的位姿上获得的。距离机器人越远的单元，值越大。 图17.9和图17.10显示这样的值函数的几个例子。在每种情况下，机器人的位置具有最小的值，沿着可达的空间值在不断增大。

(a) (b) (a) (b)
图 17.9. 两个机器人探索一个环境。没有任何协同的情况下，两个机器人都做出到达同一个目标位置的决策。 每幅图都显示了一个机器人、地图、以及它的值函数。黑色的举行表示具有最低代价的目标点。 图 17.10. 使用协同地方法获得的目标位置。在这种情况下第二个机器人的目标点向左偏移了一些。

容易看出这些值函数测量了移动到任何可能的栅格单元的代价。对于每个机器人，通过算法17.2的第13行，计算探索的最优边界单元。 根据第11行种计算的二值增益地图，未探索单元\(V_k\)中具有最小代价的单元，就是目标点。它"不鼓励"其它机器人使用相同的或者附近的目标位置， 我们的算法在增益地图中选择的目标位置上将之重置位0，如第14到16行所示。

多机器人探索的协同机制可以总结如下，每个机器人都在贪婪的选择最合适的探索目标点，并阻止其它机器人选择相同的或者附近的目标点。图17.9和图17.10说明了这个协同工作的作用。 在图17.9中的两个机器人，虽然在不同的位置上，却选择了相同的边界单元进行探索。因此，在没有协同的情况下，它们将朝着相同的区域探索。 图17.10就不一样，其中第一个机器人做出了选择， 屏蔽了第二个机器人选择这个位置。反过来，第二个机器人选择了一个更好的位置。如此得到的联合探索动作规避了冲突，探索效率更高了。

显然，协同机制很简单，它很容易就陷进了一个局部极小值。如果在图17.10中我们让第二个机器人选择第一个位置会发生什么呢？第一个机器人就会被强制选择一个更远的目标位置， 两个机器人的路径就会有交叉的部分。显然，对于一个次优解而言路径交叉也是可以的。但是，没有这样的路径交叉也不能保证最优的结果。

改进的协同技术考虑了这样的冲突，允许机器人相互之间交易目标点。有一种流行的技术，在可以降低总体探索代价的情况下，允许机器人互相交换目标点。这样的技术通常称为拍卖机制， 也就是所谓的基于市场的算法。

图17.11描述的是一个在真实环境中应用多机器人探索算法的例子。一种有三个机器人探索未知环境。最左边的图中显示了所有的机器人和它们的起始位置。其他的图中描述了协同探索过程中的不同情形。 图17.12描述的是相同的机器人构建的地图。可以看出它们实际上散布在环境中。

图 17.11. 协同机制加持的机器人探索队。最终它们散布在环境中。 图 17.12. 三个机器人8分钟构建的\(62×43m^2\)的大型地图。

图17.13中在同一个机器人队伍上对比了这个算法与使用没有协同机制的蒙特卡洛探索算法的表现。图中的横坐标指示了机器人数量，纵轴显示了完成探索任务所需要的时间步数。 在这些实验中，假设机器人总是共享着它们的局部地图，并且所有的机器人的起始位置都比较接近。这个结果很有说服力，显然无协同 机制的机器人探索效率远低于有协同机制的队伍。

图 17.13. 仿真环境下，不同数量的机器人队伍探索效率对比

到目前为止，所讨论的协同策略都假设机器人共享一个地图，并且指导互相的相对位置。考虑了相对机器人位置的不确定性，多机器人探索可以扩展到从不同的未知位置出发探索的情况。

图17.14中显示了一个使用这一扩展的协同技术的探索过程。有两个机器人A和B，它们不知道相对的起始位置。最初，机器人相对独立的探索。在探索过程中， 每个机器人都在使用一个改进的MCL定位算法，来估计另一个机器人相对于自己的地图的位置。在决定下一步要移动的目标之前，A和B都在考虑移动到一个未探索的位置上是否更好， 还是应该验证对其他机器人位置的假设。在某一点上，B决定验证其对A的位置假设。它向A发送一个消息让A停下来，然后移动到A的假设位置上，在图17.14中标记为碰面点。 当到达了这个位置上后，两个机器人就会使用它们的传感器查找对方的存在。当它们发现了对方，就会合并地图，并且共享一个参考坐标系。从此以后，它们就是用多机器人探索算法来探索环境。 这样一种从位置起始位置开始的探索技术，可以应用于不止两个机器人的更为复杂的场景中。

图 17.14. 从未知的起始位置开始的协同探索。机器人通过约会来估计并验证它们的相对位置来，进而建立了一个通用的坐标系。 一旦它们碰面了，就会探索的地图和坐标系。Courtesy of Jonathan Ko and Benson Limketkai.

17.5 用于SLAM的探索

本书中最后一个使用贪心探索思想的算法是一个完全SLAM算法。在之前的章节中，我们重视假设地图或者机器人的位置是已知的。但是在SLAM问题中，我们哪个也不知道。 相应的，在选择如何探索的时候，我们不仅需要考虑地图中的不确定性还要考虑机器人位置的不确定性。显然，没有机器人位置的信息，将传感器信息融合进地图中就会导致严重的错误。 另一方面，机器人为了降低自身位置的不确定性就不会移动，这样就永远不能收集到除了初始的传感器探测范围之外的任何关于环境的信息。

17.5.1 在SLAM中的熵分解

在SLAM中最优探索的关键内涵在于SLAM后验概率的熵是可以分解为两个部分的，一个是位姿后验概率的熵，另一个包含了地图中期望的熵。 这样，探索SLAM机器人就可以在地图的不确定性和位姿不确定性之间做出权衡。控制动作倾向于减少其中一项，当环路闭合的时候，机器人主要是降低其位置的不确定性。 当在开放的未探索地形中运动的时候，则主要降低的是地图的不确定性。通过考虑这两者，无论哪个削减占据主要作用，机器人有时会在开阔的地形中运动，有时会回到已知的地形中来重定位。

实际上，对于完全SLAM问题，熵的分解是普遍的。对于完全SLAM后验概率: $$ \begin{equation}\label{f17} p(x_{1:t}, m | z_{1:t}, u_{1:t}) \end{equation} $$ 我们已经在第十三章中讨论过，它可以分解为: $$ \begin{equation}\label{f18} p(x_{1:t}, m | z_{1:t}, u_{1:t}) = p(m | x_{1:t}, z_{1:t}, u_{1:t})p(x_{1:t} | z_{1:t}, u_{1:t}) \end{equation} $$ 这意味着 $$ \begin{equation}\label{f19} H\left[p(x_{1:t}, m | z_{1:t}, u_{1:t})\right] = H\left[p(x_{1:t} | z_{1:t}, u_{1:t})\right] + E\left[H\left[p(m | x_{1:t}, z_{1:t}, u_{1:t})\right] \right] \end{equation} $$ 这里使用期望来代替后验概率\(p(x_{1:t} | z_{1:t}, u_{1:t})\)。

将完全后验概率\(p(x_{1:t}, m | z_{1:t}, u_{1:t})\)，我们可以从第一性原则出发推导这个求和项的分解:

$$ \begin{align}\label{f20} H(x, m) & = E_{x,m}\left[- \log p(x,m) \right] \\ & = E_{x,m}\left[- \log \left( p(x) p(m | x)\right) \right] \\ & = E_{x,m}\left[- \log p(x) - \log p(m | x) \right] \\ & = E_{x,m}\left[- \log p(x) \right] + E_{x,m}\left[ - \log p(m|x) \right] \\ & = E_x\left[- \log p(x)\right] + \int_{x,m} -p(x,m)\log p(m|x) dx dm \\ & = E_x\left[- \log p(x)\right] + \int_{x,m} -p(m | x)p(x) \log p(m | x) dxdm \\ & = E_x\left[- \log p(x)\right] + \int_x p(x) \int_m -p(m | x) \log p(m | x) dx dm \\ & = H(x) + \int_x p(x)H(m | x)dx \\ & = H(x) + E_x\left[ H(m | x) \right] \end{align} $$
算法 17.3. 针对基于栅格地图的FastSLAM的探索算法。它以粒子集合\(Y_t\)为输入。 每个粒子\(y_t^{[k]}\)包含了一个采样的机器人路径\(x_{1:t}^{[k]}\)，以及一个关联的占用栅格地图\(m^{[k]}\)。它输出了一个探索路径，以相对动作命令的形式来表达的。

该变换直接蕴含着式(\(\ref{f19}\))的分解。它证明了SLAM熵是路径熵和期望的地图熵的和。

17.5.2 FastSLAM探索

现在熵分解就对实际的SLAM探索技术有了影响。我们的方法基于本书中第十三章所描述的基于三个的FastSLAM算法。 FastSLAM用一个粒子集合表示SLAM的后验概率。每个粒子都包含了一个机器人路径。在基于栅格的实现中，每个粒子还有一个占用栅格地图。这使得用熵来测量占用栅格地图称为可能， 正如我们在之前的章节中讨论的那样。

算法17.3中给出了一个确定探索动作序列的算法。在该算法中有很多重要的实现问题都还是开放的，这里只是一个示例策略。但是他也说明了实际的SLAM探索实现中所有主要过程。

FastSLAM探索算法本质上是一种测试-评估test-and-evaluate算法。它提供了用于探索的运动路线。接着它通过测试残余的熵，评估了这些动作。建立在上述讨论的内涵基础之上， 这个熵可以通过两项的求和计算得到，其中一项对应着在提出的探索序列末端的机器人位姿，另一项则包含了期望的地图熵。探索算法接着选择那些最小化熵的控制。

详细的，FastSLAM探索算法FastSLAM_exploration以粒子集合为输入，并处处用于探索的控制序列。算法17.3的第四行中提出了一个潜在的控制序列。 并在第5到16行对这一控制序列进行评估。它被组织成为三个部分。首先，基于粒子集合中的一个随机粒子来模拟机器人。这个模拟过程使用机器人和其环境的随机过程模型。 其结果是一个粒子集合的序列，都指向控制轨迹的末端。这个模拟过程在第5行到9行实现。

因此，最终粒子集合的熵就得到计算。通过式(\(\ref{f19}\))中的数学分解，熵被分解为两个部分，其中一项对应着\(T\)时刻估计的机器人位姿的熵，另一项于期望的地图不确定性有关系。 第一项在第11和12行中得到了计算。其正确性将在引理17.4中通过对一个高斯分布的熵的计算得到证实。

第二项的熵在第13到16行中得到计算。注意，对第二个项的计算涉及到地图\(m\)的熵。对于占用栅格地图，这个计算于之前章节中讨论的方式类似。在第13到16行，计算地图的平均熵， 这个平均值是建立在\(T\)时刻所有粒子上的。得到的结果是值\(h\)，它测量了\(T\)时刻以提出的控制序列为条件的的期望熵。第17到20行选择了能够最小化期望熵的动作序列，并最终在第22行返回。

注意这个算法在第11行中，使用一个近似手段来计算估计的后验概率的熵。与其为所有的轨迹粒子\(y_T^{[k]}\)适配一个高斯分布，它只基于最后的位姿\(x_T^{[k]}\)计算了这个熵。 这个近似方法在实际应用中工作的很好，而且和我们的探索动作近似的概念类似。

综上所述，FastSLAM探索算法本质上是算法17.1中所述的蒙特卡洛探索算法的扩展，有两个方面的内涵。首先它应用整个控制序列，不仅仅是一个控制。 更重要的是FastSLAM探索算法计算了两种类型的熵，一个是机器人路径的，另一个是地图的。

引理 17.4. 多变量高斯分布的熵

17.5.3 实验分析

探索算法将产生合适的探索行为，尤其是在循环的环境中。图17.15中显示了这样的一个场景，机器人探索一个具有环路的环境。机器人从环路的右下角出发，在图中标记为"start"。 在第35个时间步，机器人考虑到引导他回到起点的动作，此时标记点左边的区域还是未知的。回到起点的预期信息增益比移动到未知地形中的要高。因为在这些新地图信息的加入，位姿的不确定度将得到削减。 因此，探索机器人主动的决定闭合回路，并进入之前已经探索的地形。

图17.15. 一个探索有环路的环境的机器人。机器人从环路的右下角出发，再次路过该点以后，它决定沿着之前的路线在走一遍，以降低其不确定性。接着它继续探索走廊。 Courtesy of Cyrill Stachniss, University of Freiburg.

图17.16中进一步研究了代价-收益(cost-benefit)的权衡。图中标记了8个不同的动作。其中动作1的作用最高，远远高于动作4以及其它非闭环动作的作用。 在第45个时间步上，机器人闭合了环路，如图17.15所示。此时，位姿的不确定性最小，而地图的不确定性成为了主要因素。此时，闭环运动变得没那么有吸引力了。在第88个时间步上，机器人选择探索开放区域， 它就沿着图17.15所示的路径前进。

(a) (b)
图17.16. 机器人确定可能的动作的期望作用。(a) 机器人考虑的探索动作。(b) 每个动作的期望作用。这里选择了动作1，因为它具有最大的期望作用。 Courtesy of Cyrill Stachniss, University of Freiburg. 图17.17. 探索环境过程中熵的演化。Courtesy of Cyrill Stachniss, University of Freiburg.

图17.17中描述了整个实验过程中熵随时间的演化。在第30步之前，地图不确定性的下降补偿了机器人位姿不确定性的增加。因此，熵或多或少的维持在一个常数附近。但是闭环动作的执行降低了机器人轨迹的置信度中的熵， 而地图不确定度的变化相对很小。这导致了总体的熵的下降。只要机器人整合了目前覆盖水平走廊的测量值，地图和位姿不确定度的变化互相补偿。总体的熵在第90步左右得到了下降，因为它观测到了水平走廊中比较宽的部分。 这是因为，在占用栅格地图中，地图不确定性的降低是通过整合距离扫描得到的，它通常线性依赖于未知区域的大小。

路径和地图的不确定度的错综复杂的相互作用，以及对应的信息增益项，在探索算法中扮演者基本的角色。在合适的情况下，机器人有时更期望定位，有时更期望在未建图的地形中移动。

17.6 总结

本章中，我们研究了机器人探索。本章中所有的算法都是出于一个目的——最大化机器人的信息增益。通过指引控制动作来最大化信息增益，机器人就可以高效的探索了。该思想应用于很多不同的探索问题中:

本章中讨论的大多数探索技术都是贪婪的，机器人在它的探索决策过程中只考虑了一个动作选择。在大多数探索问题中，有巨多的分支因素，这使得多步规划十分困难，所以贪心算法也是对这问题的妥协。 尽管如此，选择合适的探索动作的时候也需要仔细思考一下。

本章中的算法将移动到机器人局部坐标系中的任何一点看作一个探索动作。因此， 这里考虑的基本动作单元大大超出了第五章中定义的基本机器人控制动作。正是这个动作的定义， 使得简单的探索技术可以用于复杂的多步机器人探索问题中。

我们注意到探索也可以形式化为一般的POMDP问题，使用一个回报函数来替代信息增益。但是，最好是在分支因素较少的情况下使用POMDPs，而且可能的观测值数量是有限的。 探索问题的状态和观测空间很大，因此最好通过最大化信息增益的贪心技术来解决。

17.7 参考文献

探索已经是机器人系统中的一个主要的应用领域，目前典型的应用包括火山探测(Bares and Wettergreen 1999; Wettergreen et al. 1999)，行星/月球探测(Gat et al. 1994; Höllerer et al. 1999; Krotkov et al. 1999; Matthies et al. 1995; Li et al. 2000)，搜索救援(Murphy 2004)，废弃矿井探测(Madhavan et al. 1999; Thrun et al. 2004c; Baker et al. 2004)，南极陨石搜索(Urm-son et al. 2001; Apostolopoulos et al. 2001)， 废墟探索(Bapna et al. 1998)以及水下探索(Ballard 1987; Sandwell 1997; Smith and Dunn 1995; Whitcomb 2000)。

机器人探索算法的设计的根源在于前两章中提及的信息收集和决策理论。Kuipers and Byun (1990) and Kuipers and Byun (1991)描述了一个早期的机器人探索方法, 还有Pierce and Kuipers (1994)。在这个方法中， 机器人确定了所谓的局部可分辨区域，使得它能够区分已经探测的和尚未探测的区域。Dudek et al. (1991)还发表了一篇类似的文章，开发了一个探索策略来探索未知的类图环境。他们的算法没有考虑距离尺度， 特意为那些感知能力有限的机器人设计的。

Koenig and Simmons (1993)提出了一种早期的用于移动机器人上学习拓扑地图的探索技术。使用动态规划方法主动的探索占用栅格地图的思想可以追溯到Moravec (1988) and Thrun (1993)。 Tailor and Kriegman (1993)描述了一种用于学习基于特征地图的方法，访问环境中所有的路标。在这个系统中，机器人维护了一个列表，记录了环境中尚未访问的所有路标。 使用统计学公式最大化用于探索的信息的思想可以在文献Kaelbling et al. (1996)中找到。 Yamauchi et al. (1999)介绍了基于边缘的方法用于移动机器人探索，主要是在寻找探索的和未探索的区域边界，用于指导机器人运动。 González-Baños and Latombe (2001)提出了一个探索策略，考虑从不同的视角机器人可能看到却未看到的区域数量，来决定下一步动作。类似的探索策略在3维物体建模领域中也流行了起来。 比如说，Whaite and Ferrie (1997)研究了扫描物体的问题，考虑了模型参数中的不确定性，进而确定了下一个最优的视点。

探索方法已经扩展到了协作探索的机器人队伍中了。Burgard et al. (2000), and Simmons et al. (2000a)将贪心的探索框架扩展到了机器人队伍中，他们联合探索并尝试最大化地图信息，see also Burgard et al. (2004)。 这个方法于Howard et al. (2002)提出的增量部署技术类似，还有Stroupe (2004)提出的算法。用于协同探索的基于市场的技术是由Zlot et al. (2002)提出的。Dias et al. (2004)分析了在多机器人协同过程中， 潜在的失效情况，并提供了一个改进的算法。Singh and Fujimura (1993)提供了一种处理异质的队伍的方法。Ko et al. (2003)引入了一种未知起始位置的多机器人协同探索的方法，并彻底地在Konolige et al. (2005)做了测试。 该方法使用一个对环境结构化地估计以及一个改进版本地MCL定位方法来估计机器人的相对位置(Fox et al. 2005)。在Rekleitis et al. (2001b)中提出了一个探索技术，一个机器人观测着另一个进行探索， 这样就降低了它的局部不确定性。本章中展现的一些多机器人探索实验发表在文献Thrun (2001)中。

在一些论文中，地图探索问题被当作一个覆盖问题来研究，他们致力于设计一种算法来穷尽的覆盖一个未知环境。Choset (2001)提供了一个这个领域的详尽综述。 一些较新的技术(Acar and Choset 2002; Acar et al. 2003)通过统计学的技术来处理这一问题，所用的算法于这里讨论的没有什么不同。

在SLAM的背景下，一些作者设计了探索技术可以最优化地图覆盖的同时主动定位。Makarenko et al. (2002)描述了一种方法，基于期望的信息增益和探索未知地形来确定动作，该方法根据重复观测的路标计算期望的信息增益， 这样是为了更准确的确定机器人的位姿。Newman et al. (2003)描述了一种用于高效SLAM的Atlas (Bosse et al. 2003)框架的探索方法。机器人构建一个图结构来表示可视的区域。 Sim et al. (2004)解决了在SLAM中的轨迹规划问题。他在基于EKF方法的背景下，考虑了一族参数化的螺旋轨迹策略，来解决SLAM问题。本章中描述的FastSLAM探索技术归功于Stachniss and Burgard (2003, 2004)。 Batalin and Sukhatme (2003)描述了一种通过机器人设定标记来辅助定位的方法，作为SLAM探索的技术。

分析机器人探索策略的表现也是相当受关注的话题。研究者们提供了数学上的或者实验上的分析研究了不同的探索策略的复杂度(Albers and Henzinger 2000; Deng and Papadimitriou 1998; Koenig and Tovey 2003; Lumelsky et al. 1990; Rao et al. 1993)。比如说，Lee and Recce (1997)报告了一个实验研究，他们对比了单个机器人的不同探索策略的性能。

我们的用于移动机器人主动定位的技术，最早发表在Burgard et al.(1997) and Fox et al. (1998)。近期，Jensfelt and Christensen (2001a)提出了一个系统，使用一个混合高斯分布来描述机器人位姿的后验概率， 并描述了在给定这样的描述的情况下，如何进行主动定位。人们还通过理论的方法研究了主动定位问题，比如说Kleinberg (1994)的研究，建立在完美传感器的假设下。

一些学者开发了用于动态环境的机器人探索策略。他们对追踪-逃避游戏非常感兴趣，在大量的微分博弈文献中都有讨论它(Isaacs 1965; Bardi et al. 1999)。 用于室内移动机器人的追逃问题的技术归功于LaValle et al. (1997) and Guibas et al. (1999)，近期Gerkey et al. (2004)又对其做了扩展。

最后，探索问题在自动机理论中得到了大量的研究。顺序的决策形成了一个范式，只要学习者的实验最初在简单有限状态机下研究认为是赌博机，它就可以获得报酬，参见文献Feldman (1962); Berry and Fristedt (1985); Robbins (1952)。学习有限状态机结构的技术要追溯到Rivest and Schapire (1987a,b) and Mozer and Bachrach (1989)，他们开发了生成测试序列的技术，来区分FSA中的不同状态。 Koenig and Simmons (1993) and Thrun (1992)推导了，探索确定性环境的复杂度的基于状态的界限，后来被kearns and Singh(2003)扩展到随机环境中。

17.8 练习

暂略




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