第九章：占用栅格建图

9.1 介绍

前两章中讨论了在低维感知问题上应用概率学技术，来估计机器人的位置。在机器人运动过程中，我们一直假设它有一个地图。但是很少有真实世界的应用能够满足这一假设，因为地图通常都是先验的，或者是人们手工创建的。在一些应用领域，没有过多的子原来建立先验地图。令人惊讶的是，大多数建筑的结构与蓝图都是不相符的。即使蓝图是准确的，它也不包含家具等其他物体，从机器人的角度来看，决定环境形状的只是一些墙和门。从无到有的学习一幅地图可以大大的降低不是一台移动机器人的工作量，使得机器人能够在无人监视的情况下适应环境变化。实际上，建图是真正自主的机器人的核心能力。

因为一些因素的制约，移动机器人自动建图是一项有挑战的工作:

巨大的假设空间，该空间覆盖了所有可能的地图。因为地图是定义在连续空间上的，覆盖所有地图的空间的纬度是无穷的。即使是在离散地近似形式下，比如说本章要使用的栅格近似，描述地图中的变量也很容易就到了$10^5$的量级甚至更多。仅仅是如此高维空间的大小就使得计算所有可能的地图的完整后验概率充满了挑战。因此在定位问题中工作的很好的贝叶斯滤波器就不再适合学习地图了，至少是这些算法的朴素实现方式不再适用了。
学习地图是一个"先有鸡还是先有蛋(chicken-and-egg)"的问题，因而人们通常称之为即时定位与建图问题simutaneous localization and mapping(SLAM)或者说是concurrent mapping and localization。首先它是一个定位问题。机器人在环境中运动，其里程计在不断的累计误差，使得机器人逐渐的迷失了。如果有了一幅地图，就有很多方法来确定机器人的位置。其次它还是一个建图的问题。如果知道了机器人的位置，那么构建一幅地图也是一件相对容易的事情，这点将在本章和后续的几章中得到证实。如果缺失了初始地图，也没有确切的位置信息，那么机器人就必须同时处理这两件事情，估计地图，并确定自己相对于该地图的位置。

显然，不是所有的建图问题的难度都一样。建图问题的难度取决于一系列的因素，其中最重要的有:

尺寸。相比于机器人的感知范围，环境越大就越难建图。
感知和执行噪声。如果机器人的传感器和执行器都是无噪声的，那么建图就会是一个简单的问题。噪声越大，问题越难。
感知的歧义。如果有很多地方长的都差不多，那么就很难及时的确定这些地方的地图。
环路。如果环境中有很多环路，那么构建地图就会尤其困难。如果只是让机器人在走廊里来来回回的走，在每次返回的时候，机器人都可以修正一下里程计的误差。但是如果有环路的存在，那么机器人可以通过不同的路径回到原点，如此形成的闭环将不利于里程计的修正，最终导致累计误差增大。

为了充分的了解建图问题的困难，让我们来考虑图9.1的情况，那是一个在很大的室内环境中收集的数据集。图9.1a中是机器人的原始里程计信息。图中的每一个黑点都对应着机器人的激光传感器扫描到的障碍物。图9.1b中显示了应用这些数据构建的栅格地图，该地图的构建算法是本章要描述的一种技术。这个例子充分的说明了这一问题的关键之处(译者按:其实文字上已经说的很清楚了，这张图实在不知道作者想说个啥~.~)。


(a)	(b)
图9.1. (a)原始距离数据，位置由里程计索引(b)占用栅格地图

在本章中，我们首先研究在已知机器人位姿的假设下进行建图的问题。换句话说，我们先回避SLAM问题中的难点，在建图的时候有神谕(oracle)告知我们机器人的正确路径。这个问题正如图9.2中描述的图模型一样，称为已知位姿的建图mapping with known poses。我们将讨论一族流行的算法，统称为占有栅格建图occupancy grid mapping。占有栅格地图假设机器人的位置已知，从有噪声和不确定性的测量数据中生成连续地图。其基本思想就是用随机变量的场来表示地图，并将之排列成为一个空间的栅格。每一个随机变量都是二值的，对应着其所覆盖的位置上的占用情况。占用栅格地图算法对这些随机变量近似估计其后验概率。

图9.2. 已知位姿建图的图模型。阴影中的便来嗯都是已知的(位置$x$和测量值$z$)。建图的目标就是恢复地图$m$。

读者可能会怀疑需要确切位置信息的建图技术的必要性。毕竟，没有机器人的里程计是完美的。占用栅格技术的主要用处就是其后处理过程，后续章节中讨论的很多SLAM技术都不生成用于路径规划和导航的地图。占用栅格地图通常用于通过其他手段解决SLAM问题之后，作为路径估计的结果。

9.2 占用栅格建图算法

任何占用栅格建图的黄金法则都是给定数据计算地图的后验概率。 $$ \begin{equation}\label{f1} p(m | z_{1:t}, x_{1:t}) \end{equation} $$ 其中，$m$是地图，$z_{1:t}$是从开始到$t$时刻的所有测量值，而$x_{1:t}$则是由机器人所有位姿的序列所定义的运行路径。控制量$u_{1:t}$在占用栅格地图中没有任何作用，因为路径是已知的。因此，它们将在本章中的略去。

占用栅格地图所用的地图类型是在连续的位置空间上细粒度的栅格。目前为止，最常用的占用栅格地图是2维的平面地图，描述的是3维世界中的一个2维切片。 2维地图的表示形式通常用于机器人在一个平面上进行导航，而且其上装备的传感器也只能捕获世界中的一个切片。把占用栅格技术推广到3维的表示形式，需要花费大量的计算资源。

令$m_i$表示索引为$i$的栅格单元。占用栅格地图将空间划分为有限多个单元: $$ \begin{equation}\label{f2} m = \{ m_i \} \end{equation} $$ 每个$m_i$都关联一个二值的占用状态，表示对应单元是否被占用了。"1"表示被占用，"0"表示空闲。符号$p(m_i = 1)$或者$p(m_i)$表示一个栅格单元被占用的概率。

公式($\ref{f1}$)中后验概率的问题是它的维度，像图9.1中的栅格地图有上万个栅格单元。对一个有10,000个栅格单元的地图，所能表示的地图数量为$2^{10,000}$。因此为每一个地图计算一个后验概率是很繁琐的。

标准的占用栅格方法将估计地图的问题拆分为一系列独立的子问题，对每一个栅格单元$m_i$计算一个后验概率 $$ \begin{equation}\label{f3} p(m_i | z_{1:t}, x_{1:t}) \end{equation} $$ 这样的每一个估计问题都是在计算静态的二值概率。这种分解很方便但并不是没有问题。特别的，它不能表示相邻单元之间的依赖关系，实际上整个地图的后验概率近似为它们的乘积，形式如下: $$ \begin{equation}\label{f4} p(m | z_{1:t}, x_{1:t}) = \prod_i p(m_i | z_{1:t}, x_{1:t}) \end{equation} $$ 我们将在9.4节中讨论更多改进的建图算法时，重新回到这个问题上来。现在为了方便我们先采用这个因式分解形式。

得益于我们的因式分解，估计每个栅格单元的占用概率现在就成为了一个静态的二值估计问题。我们已经在4.2节中讨论过这个问题的一个滤波器——二值贝叶斯滤波器binary Bayes filter。对应的算法已经在算法4.2中描述过。

算法9.1. 占用栅格算法，算法4.2中的二值贝叶斯滤波器的一种实现。

在算法9.1将这一滤波器应用到占用栅格建图问题中。因为在原始的滤波器中，我们的占用栅格建图算法使用对数差异比log odds表示占用概率: $$ \begin{equation}\label{f5} l_{t,i} = \log \frac{p(m_i | z_{1:t}, x_{1:t})}{1 - p(m_i | z_{1:t}, x_{1:t})} \end{equation} $$ 这种表示形式已经在4.2节中介绍过。对数差异比的形式相比于概率形式的优点在于，可以避免0或者1附近具有较大数值误差的概率值。我们可以很容易的从对数差异比中恢复概率值: $$ \begin{equation}\label{f6} p(m_i | z_{1:t}, x_{1:t}) = 1 - \frac{1}{1 + \exp \{ l_{t,i} \}} \end{equation} $$

算法9.1occupancy_grid_mapping循环遍历了所有的栅格单元$i$，并更新那些落在传感器测量值$z_t$的锥范围内的单元。对于那些需要更新的单元，在算法的第4行中通过函数inverse_sensor_model来更新。其他的占用栅格中的数值都保持不变，正如第6行所示。常数$l_0$是用对数差异比的形式表示的先验占用概率: $$ \begin{equation}\label{f7} l_0 = \log \frac{p(m_i = 1)}{p(m_i = 0)} = \log \frac{p(m_i)}{1 - p(m_i)} \end{equation} $$ 函数inverse_sensor_model实现了对数差异比形式的逆测量模型$p(m_i | z_t, x_t)$: $$ \begin{equation}\label{f8} \mathbf{inverse\_sensor\_model}(m_i, x_t, z_t) = \log \frac{p(m_i | z_t, x_t)}{1 - p(m_i | z_t, x_t)} \end{equation} $$

算法9.2. 一个简单的逆测量模型，用于装备有距离传感器的机器人。其中$\alpha$是障碍物的厚度，$\beta$是传感器波束的宽度。第9和11行的$l_{occ}$和$l_{free}$分别表示测量读数中携带两类不同状态的证据数量。

算法9.2就是这样一种函数的简单实现。图9.3示例了两个不同的测量范围下的模型。这个模型为每一个栅格单元赋予一个占用值$l_{occ}$。在算法9.2中，区域的宽度有参数$\alpha$来控制，测量波束的开度角由参数$\beta$控制。我们注意到这个模型有点简单，目前的实现，在测量锥边界上的占用概率通常是不稳定的。


(a)	(b)
图9.3. 两种不同测量范围的逆测量模型。每个栅格单元的灰度表示其被占用的概率。这个模型很简单，目前的实现，在测量锥边界上的占用概率通常不稳定。

算法inverse_sensor_model计算逆模型的时候，首先确定栅格单元$m_i$质心所对应的波束索引$k$和距离$r$。这一过程在算法9.2中的第2到5行得到了体现。按照惯例，我们用$x_t = \begin{pmatrix} x & y & \theta \end{pmatrix}^T$表示机器人的位姿。在第7行中，它以对数差异比的形式返回了占用先验概率，描述了栅格单元在传感器波束的测量范围之外，或者是在检测距离$z_t^k$之后的$\frac{\alpha}{2}$之外。如果栅格单元落于测量距离$z_t^k ± \frac{\alpha}{2}$的范围之内，那么就在第9行中返回了$l_{occ} > l_0$。如果栅格的距离小于$z_t^k - \frac{\alpha}{2}$就返回$l_{free} < l_0$。

图9.4中给出了一种典型的应用于超声传感器的逆传感器模型。从初始地图开始，机器人通过逆传感器模型构建局部地图，并逐渐的将之融入初始地图中。图9.5中给出了在相同环境下的一个更大的占用栅格地图。


图9.4. 在走廊的环境中使用超声数据，增量地学习地占用栅格地图。左上角显示地是初始地图，右下角则是学习之后地地图。第2到4列都是通过逆传感器模型构建的局部地图。 2.5m以上的测量值都不在考虑范围之内，每一个测量锥的开度角为15度。图片由美国弗里堡大学的Cyrill Stachmiss提供。	图9.5. 使用声纳传感器对一个办公环境构建的栅格地图。图片由美国弗里堡大学的Cyrill Stachmiss提供。

图9.6中给出了一个大型开放展厅的结构蓝图，以及一个机器人对其构建的占用栅格地图。这个地图是通过几分钟的激光雷达数据构建的，图中灰度等级表示对应栅格被占用的后验概率，颜色越深就越可能被占用。占用地图本身就是概率学形式的，通常很快就能够收敛到两个极端的后验概率值‘1’和'0'上。对比学习得到的地图和建筑蓝图，建筑栅格地图中显示了所有的主要物体，以及雷达扫描平面上的所有障碍物。通过细心的对比，读者可以发现建筑蓝图与实际的环境之间有一些微小的差异。


(a)	(b)
图9.6. (a)占用栅格地图(b)一个大型开放展厅的结构蓝图。注意实际上有些地方与蓝图不一致。

图9.7中对比了传感器的原始数据和用之生成的占用栅格地图。图(a)给出了由一个SLAM算法预处理之后的数据，因而它们是已知机器人姿态下采集的数据。有些数据因为人类的存在被截断了，占用栅格地图成功的从这些数据中过滤了人类的存在。这使得占用栅格地图比扫描端点数据更适合用于机器人导航。将原始的传感器扫描端点提供给规划器，将会花费很多时间来找到一条路径从散布的障碍物中间穿过。即使有证据表明这些栅格更可能是空闲的而不是被占用的。


(a)	(b)
图9.7. (a)具有正确的位姿信息的激光雷达扫描数据。每个圆点都对应着一个检测到的障碍物。大多数障碍物都是静态的，比如说墙面。但有些是动态的，因为在采集数据的时候，机器人的周围是有人在运动的。(b)从数据中生成的占用栅格地图。灰度表示后验概率，深色的部分表示对应部分大概率上是被占用的，而白色的部分则表示大概率上是空闲的。灰色背景表示先验概率。图(a)是由Steffen Gutmann提供的。

我们注意到这些算法只是用传感器测量值来做出占用决策。另一个信息来源是机器人自身所占用的空间，当机器人位于$x_t$时，其周围的空间一定是不能被占用的。我们可以简单的对算法9.2中的逆测量模型做出修改，让它能够处理这部分信息，将位于$x_t$的机器人占用的所有栅格都用一个很大的负数来表示。在实际构建地图的过程中，这是一种很好的考虑机器人自身体积的方法，尤其是环境中挤满了人类的时候。

9.2.1 多传感器融合

机器人通常装备有不止一种类型的传感器，因此，很自然的我们会想办法把多个传感器的数据都融合到地图信息中。多传感器融合是一个很有意思的问题，尤其是当这些传感器具有不同的特性的时候。比如说图9.8中显示了一个使用立体视觉构建占用栅格地图的例子，它将视差图投影到一个二维平面上，并将投影结果卷积上了一个高斯函数。显然立体视觉的特性与基于声纳的距离传感器是不同的，它们能够探测不同类型的障碍物。


(a)	(b)	(c)
图9.8. 使用立体视觉估计占用地图 (a) 摄像机图像。(b) 稀疏视差地图。(c)将视差地图投影到二维平面上，并将投影结果卷积一个高斯函数，由此得到的占用栅格地图。该图是由Thorsten Fröhlinghaus提供的。

不幸的是，用贝叶斯滤波器融合多传感器的数据并不是一件容易的事情。一种朴素的思想就是，以不同传感器形式运行算法9.1occupancy_grid_mapping。但是这种方式有一个很明显的缺陷，如果不同的传感器采集的是不同类型的障碍物数据，那么由此得到的贝叶斯滤波器将是病态的。比如说，有一个障碍物能够被一种传感器检测到，却不能被另一种传感器感知，那么这两个传感器将给出互相矛盾的信息，如此得到的地图将依赖于每一个传感器系统所提供的证据数量。这并不是我们所期望的，因为判定栅格单元是否被占用，依赖于各个传感器被查询的频率。

融合多个传感器信息的一种比较流行的方法就是，为每一种传感器单独建立一个地图，并使用一个比较合理的函数融合它们。令$m^k = \{m_i^k\}$表示由第$k$个传感器构建的地图，如果所有传感器的测量值都是相互独立的，那么我们就可以只接用De Morgan's law来组合它们。 $$ \begin{equation}\label{f9} p(m_i) = 1 - \prod_k \left(1 - p(m_i^k) \right) \end{equation} $$ 或者，我们可以取所有地图中的最大值: $$ \begin{equation}\label{f10} p(m_i) = \max_k p(m_i^k) \end{equation} $$ 如此，生成的是对这些栅格的最悲观的估计，只要有传感器地图中表示栅格单元被占用了，那么该状态就会体现在组合之后的地图中。

9.3 学习逆测量模型

9.3.1 逆测量模型

占用栅格地图算法需要一个被边缘化的逆测量模型inverse measurement model，$p(m_i | x, z)$。之所以称这个概率为"逆"，是因为它从结果归纳原因，根据对环境的测量来提供关于环境的信息。对于第$i$个栅格单元而言，它是被边缘化的，$p(m | x, z)$是一种完整形式的逆。在基本的算法阐述过程中，我们已经在算法9.2中提供了一种逆模型的实现。这就带来一个问题，我们是否可以从传统的测量模型开始，获得一个更为严谨的逆测量模型。

答案是可以的，但需要一些额外的操作。根据贝叶斯公式: $$ \begin{equation}\label{f11} p(m | x, z) = \frac{p(z | m, x)p(m | x)}{p(z | x)} = \eta p(z | m, x)p(m) \end{equation} $$ 这里我们假设$p(m | x) = p(m)$，因此机器人的位姿并不能够为我们提供任何关于地图的信息，这个假设纯粹是为了方便计算。如果我们的目标是为整幅地图计算逆模型，现在就已经结束了。但是，我们的占用栅格地图算法使用的是每个栅格单元$m_i$的边缘后验概率对其做出的近似。第$i$个栅格单元的逆模型通过选择第$i$个栅格单元的边缘概率得到: $$ \begin{equation}\label{f12} p(m_i | x, z) = \eta \sum_{m:m(i) = m_i} p(z | x, m)p(m) \end{equation} $$ 这个表达式对所有栅格单元$i$的占用值为$m_i$的地图$m$求和，显然这个求和运算是不可能实现的，因为所有的地图空间是非常大的，不可能穷举之。

现在我们介绍一种对这一表达式的近似方法。这一算法涉及到从测量模型中生成样本，并使用类似逻辑回归logistic regression或者神经网络neural network等有监督学习算法supervised learning algorithm来近似逆模型。

9.3.2 对前向模型采样

其基本思想是简单而通用的，如果对于栅格单元$m_i$，我们可以生成关于位姿$x_t^{[k]}$、测量值$z_t^{[k]}$和地图占用数据$m_i^{[k]}$的随机三元组，那么我们就可以学习一个以位姿$x$和测量值$z$为输入的函数，来计算$m_i$的占用概率。

我们可以通过如下的过程来生成$\begin{pmatrix} x_t^{[k]} & z_t^{[k]} & m_t^{[k]} \end{pmatrix}$形式的样本:

采样一个随机地图$m^{[k]} \sim p(m)$。比如说我们已经有一个关于地图的数据库来表示$p(m)$，就可以从这个数据库中随机的抓取一个地图。
在采样地图中随机的生成一个位置样本$x_t^{[k]}$。我们可以认为这些位置是服从均匀分布的。
采样一个服从分布$z_t^{[k]} \sim p(z | x_t^{[k]}, m^{[k]})$的测量样本。这个过程可以让人们联想到在机器人模拟器中模拟传感器测量的随机过程。
从地图$m$中提取关于目标栅格单元的"真实"占用值$m_i$。

这样就得到了位置$x_t^{[k]}$，测量值$z_t^{[k]}$，以及栅格单元$m_i$占用数据的样本。重复这个采样过程就得到了一个数据集合: $$ \begin{matrix} x_t^{[1]} & z_t^{[1]} & \rightarrow & \mathrm{occ}(m_i)^{[1]} \\ x_t^{[2]} & z_t^{[2]} & \rightarrow & \mathrm{occ}(m_i)^{[2]} \\ x_t^{[3]} & z_t^{[3]} & \rightarrow & \mathrm{occ}(m_i)^{[3]} \\ \vdots & \vdots & & \vdots \\ \end{matrix} $$ 这些三元组可以用作有监督学习算法的训练集training examples。它们是对目标条件概率$p(m_i | z, x)$的一种近似。其中测量值$z$和位姿$x$是输入变量，占用值$\mathrm{occ}(m_i)$是学习算法的输出目标。

这种方法不是那么有效，因为它不能利用那些已知的逆传感器模型的属性:

测量数据不会携带其测量范围之外的栅格单元的信息。这一现象有两层含义：首先，我们可以将三元组的采样过程集中在测量锥内的栅格单元$m_i$上。其次对该单元做预测的时候，我们只需要以与测量值$z$相关的数据的一个子集作为算法的输入。
在进行测量的时候，传感器关于机器人的绝对坐标系或者栅格单元的特性是不变的。只有相对坐标系在起作用，如果我们用$x_t = \begin{pmatrix} x & y & \theta \end{pmatrix}^T$表示机器人位姿，并用$m_i = \begin{pmatrix} x_{m_i} & y_{m_i} \end{pmatrix}^T$表示栅格单元的坐标，那么就可以通过如下的平移和旋转变换，将栅格单元的坐标映射到机器人的局部坐标系上: $$ \begin{pmatrix} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \end{pmatrix} \begin{pmatrix} x_{m_i} - x \\ y_{m_i} - y \end{pmatrix} $$ 在装备有圆形距离传感器阵列的机器人上，使用熟悉的极坐标形式来编码栅格单元的相对位置是合理的。
在逆传感器模型中相邻的传感器应当具有相似的表现形式。这一平滑特性建议我们，学习一个以单一的栅格单元的坐标为输入的函数，要比为每个栅格单元分别学习一个函数更有效。
如果机器人装备了功能上完全相同的传感器，逆传感器模型应当能够在不同的传感器之间来回切换。对于装备有圆形距离传感器阵列的机器人，任何一个传感器波束得到的逆传感器模型都是一样的。

增强这种不变性的基本方法是，通过选择合适的输入变量来约束学习算法。一种好的选择是使用使用相对位置信息，这样学习算法就不能基于绝对坐标系做出决策。省略那些与占用预测无关的传感器测量值也是一个不错的想法，这样可以在传感器的测量范围内进一步的细化栅格单元的预测值。使用这些不变量的信息，可以显著的缩小训练样本集。

9.3.3 误差函数

为了训练学习算法，我们需要一个近似的误差函数。一个比较流行的例子就是使用后向传播Back-Propagation, BP算法的人工神经网络。 BP算法通过在参数空间中的梯度下降法gradient descent来训练神经网络。给定一个描述网络激励与预期输出之间的不匹配度"mismatich"的误差函数，BP算法计算目标函数和神经网络参数的一阶微分，然后沿着梯度的反向来调整网络参数来削弱不匹配度。这就带来一个问题:我们应该使用什么样的误差函数?

一种常用的方法是，训练学习算法使得训练数据的对数似然度log-likelihood最大化。更具体的，给定如下形式的训练集: $$ \begin{equation}\label{f13} \begin{matrix} \mathrm{input}^{[1]} & \rightarrow & \mathrm{occ}(m_i)^{[1]} \\ \mathrm{input}^{[2]} & \rightarrow & \mathrm{occ}(m_i)^{[2]} \\ \mathrm{input}^{[3]} & \rightarrow & \mathrm{occ}(m_i)^{[3]} \\ \vdots & & \vdots \\ \end{matrix} \end{equation} $$ 其中，$\mathrm{occ}(m_i)^{[k]}$为目标条件概率的第$k$个样本，$\mathrm{input}^{[k]}$是对应的学习算法的输入。显然，输入的具体形式可以根据对已知不变量的编码结果来决定。但是其具体的输入形式与误差函数的形式无关。

令$W$为学习算法的参数，假设训练集中的各个样本都是独立生成的，那么训练数据的似然度就可以表示为: $$ \begin{equation}\label{f14} \prod_i p(m_i^{[k]} | \mathrm{input}^{[k]}, W) \end{equation} $$ 其负对数形式为: $$ \begin{equation}\label{f15} J(W) = - \sum_i \log p(m_i^{[k]} | \mathrm{input}^{[k]}, W) \end{equation} $$ 其中，$J$表示在训练过程中最小化的目标函数。

令$f(\mathrm{input}^{[k]}, W)$表示学习算法，其值域为$[0,1]$。训练之后，我们希望学习算法给出占用的概率: $$ \begin{equation}\label{f16} p(m_i^{[k]} | \mathrm{input}^{[k]}, W) = \begin{cases} f(\mathrm{input}^{[k]}, W) & \mathrm{if}\ m_i^{[k]} = 1 \\ 1 - f(\mathrm{input}^{[k]}, W) & \mathrm{if}\ m_i^{[k]} = 0 \\ \end{cases} \end{equation} $$

如此，我们要寻找一个误差函数来调整$W$，以最小化目标概率与由训练样本所描述的概率之间差异。为了寻找这样一个函数，我们对式($\ref{f16}$)重写如下: $$ \begin{equation}\label{f17} p(m_i^{[k]} | \mathrm{input}^{[k]}, W) = f(\mathrm{input}^{[k]}, W)^{m_i^{[k]}}(1 - f(\mathrm{input}^{[k]}, W))^{1-m_i^{[k]}} \end{equation} $$ 容易看出，这个乘积与式($\ref{f16}$)是一样的。在这个乘积中有一项一定为1，因为其指数项为0。将该式代入式($\ref{f15}$)有 $$ \begin{align}\label{f18} J(W) & = - \sum_i \log \left[ f(\mathrm{input}^{[k]}, W)^{m_i^{[k]}}(1 - f(\mathrm{input}^{[k]}, W))^{1-m_i^{[k]}} \right] \\ & = - \sum_i \left[ m_i^{[i]} \log f(\mathrm{input}^{[k]}, W) + (1 - m_i^{[k]}) \log (1 - f(\mathrm{input}^{[k]}, W)) \right] \end{align} $$ $J(W)$就是训练学习算法所要最小化的误差函数。它可以很容易地封装到任何使用梯度下降法来调参的算法中。

9.3.4 例子和一些考量

图9.9给出了一个用训练后的神经网络来模拟逆传感器模型的例子。这个例子中的机器人，在差不多桌子那么高的位置上，装备了一圈声纳传感器阵列。网络的输入是到目标单元的相对距离和方向角，以及5个邻接的距离测量值。网络的输出是占用概率，单元格越深就越可能被占用。正如这个例子所描述的那样，这个方法正确的将空闲空间与占用空间中区分出来了。障碍物后面均匀的灰色区域对应着先验的占用概率，在使用占用栅格建图算法的过程中没有被改变。图9.9b的左下角有一个错误的短距测量。只有一个读数是不足以认为对应位置上有障碍物的概率很高。

图9.9. 从数据中学习的逆传感器数据。上面一行的三幅图是三个声纳扫描的样本，下面则是由神经网络生成的局部占用地图。浅色区域表示空闲空间，深色区域表示墙和障碍物。

我们注意到有很多方法来使用实际的数据训练一个近似函数，而不是使用前向模型来模拟数据。一般来说，这是可以用来学习的最正确的数据，因为传感器模型本身就是一个近似值。这样的方法适用于工作在已知环境中的机器人，它还具有环境的地图。借助马尔科夫定位，我们可以定位机器人，并用其实际记录的测量值和已知的地图占用信息来组合训练样本。甚至可以从一个近似的地图开始，使用学习的传感器模型来生成一个更好的地图，并用上述的过程来改进逆测量模型。

9.4 最大化后验的占用地图

9.4.1 依赖的案例分析

在本章的剩余内容中，我们将要回到占用栅格建图算法的一个非常基本的假设。在9.2节中，我们假设可以将定义在高维空间中的全地图推理问题，安全的分解为一系列针对单个单元的建图问题。这一假设在式($\ref{f4}$)中归结为一个因式分解: $$ \begin{equation}\label{f19} p(m | z_{1:t}, x_{1:t}) = \prod_i p(m_i | z_{1:t}, x_{1:t}) \end{equation} $$ 这存在一个问题:对于建立在一个如此强的假设上的算法，我们应该有多么信任它的结果呢？

图9.10中列举了一个直接由这一因式分解所导致的问题。图中描述了一个机面对着墙的机器人接收到了两个无噪声的声纳距离测量值。因为因式分解的方法沿着整个测量范围的圆弧预测障碍物，所以位于这个圆弧上的所有栅格单元的占用值都会增加。当组合图9.10(c)和(d)中所示的这两个不同的测量值时，就产生了一个冲突，如图9.10(e)所示。标准的占用栅格建图算法通过综合占用值的正面和负面的证据来消解冲突。但是，这会反映出两种类型的测量值的相对频率，而这不是我们所期望的。


(a)	(b)	(c)	(d)	(e)	(f)
图9.10. 9.2节中描述的标准占用栅格建图算法的问题。在图(a)所示的环境中，一个路过的机器人可能接收到如图(b)所示的无噪声的测量值。因式分解的方法将这些波束映射到概率地图中，分别对应着每个栅格单元和每个波束，如图(c)和(d)所示。将这两个地图组合到一起就得到了如图(e)所示的地图。显然在重叠的区域有一个冲突，在图(e)中用圆圈圈出来了。实际上存在这样一个地图，如图(f)所示，能够完美的解释传感器的数据让它们没有冲突。对于一个待解释的传感器数据，假设障碍物存在于测量锥中的某个地方somewhere就可以了，而不是每个地方everywhere。

但是存在这样的地图，如图9.10(f)所示，可以完美的解释传感器的数据而不存在冲突。这是因为，对于一个待解释的传感器读数，它假设障碍物在测量锥面上的某处somewhere。换句话说，实际的测量锥扫过多个栅格单元，这在相邻的栅格单元之间引入了重要的依赖关系。当将建图问题分解为成千上万个单独的栅格单元的估计问题时，我们就丧失了考虑这些依赖关系的能力。

9.4.2 具有前向模型的占用栅格建图

这些依赖关系被融入到了一个以模型的后验概率为输出的算法中，该算法不再输出全后验概率了。这个模型被定为地图后验概率的最大对数值: $$ \begin{equation}\label{f20} m^* = \operatorname{argmax}_m \log p(m | z_{1:t}, x_{1:t}) \end{equation} $$ 地图的后验概率由一个地图的先验概率和测量值的似然度为因子，参考式($\ref{f11}$): $$ \begin{equation}\label{f21} \log p(m | z_{1:t}, x_{1:t}) = \mathrm{const}. + \log p(z_{1:t} | x_{1:t}, m) + \log p(m) \end{equation} $$ 对数似然度$\log p(z_{1:t} | x_{1:t}, m)$可以分解为各独立测量值的对数似然度之和: $$ \begin{equation}\label{f22} \log p(z_{1:t} | x_{1:t}, m) = \sum \log p(z_t | x_t, m) \end{equation} $$ 更进一步的，对数先验概率也可以分解。我们注意到任何地图$m$的先验概率可以由以下形式的乘积得到: $$ \begin{align}\label{f23} p(m) & = \prod_i p(m)^{m_i} \left(1 - p(m)\right)^{1 - m_i} \\ & = \left(1 - p(m)\right)^N \prod_i p(m)^{m_i} \left(1 - p(m)\right)^{-m_i} \\ & = \eta \prod_i p(m)^{m_i} \left(1 - p(m)\right)^{-m_i} \end{align} $$ 其中$p(m)$是占用值的先验概率，$N$是地图中栅格单元的数量。表达式$(1 - p(m))^N$仅仅是一个常数，按照惯例收录到归一化因子$\eta$中。

对其求对数有: $$ \begin{align}\label{f24} \log p(m) & = \mathrm{const}. + \sum_i m_i \log p(m) - m_i \log (1 - p(m) \\ & = \mathrm{const}. + \sum_i m_i \log \frac{p(m)}{1-p(m)} \\ & = \mathrm{const}. + \sum_i m_i l_0 \end{align} $$ 其中常数$l_0$来自于($\ref{f7}$)。项$M \log (1 - p(m_i))$明显与地图无关。因此我们可以将剩余的表达式和数据对数似然度化简为: $$ \begin{equation}\label{f25} m^* = \operatorname{argmax}_m \sum_t \log p(z_t | x_t, m) + l_0 \sum_i m_i \end{equation} $$

算法9.3中提供了一个最大化该对数概率的爬山算法。该算法在第2行中从全空闲地图(all-free map)开始，在第4到6行中反转那些栅格单元的占用值，只要反转操作能够增购数据的似然度。对于这个算法，其得以运行的基础就是占用值的先验概率$p(m_i)$不是很接近1，否则他可能返回一个全占用地图(all-occupied map)。因为任何爬山算法都只能保证找到一个局部最大值。实际上，局部极大值很少。

算法9.3. 最大化后验占用栅格算法，使用传统的测量模型替代逆模型。

图9.11是一个MAP占用栅格算法的效果。图9.11a中给出了描述了机器人通过一个门的无噪声数据集。一些声纳测量值检测到了打开着的门，而其它的测量波束则被门柱反射回来了。标准的使用逆模型的占用建图算法不能够捕获到打开的门，如图9.11b所示。而图9.11c所示的后验模型则能够检测到。这个地图正确的对打开的门建模了，所以它比标准占用栅格建图算法更适用于机器人的导航。图9.11d中描述了地图中剩余的不确定度。该图得益于栅格单元灵敏度的分析，反转一个栅格单元降低了对数似然函数的等级，如图中单元的灰度所示。与正则占用栅格地图类似，该图中说明在障碍物后面的栅格具有最大的不确定度。


(a)	(b)	(c)	(d)
图9.11.(a)无噪声模拟的声纳距离测量值。(b)标准占用地图的输出，缺少打开的门。(c)最大化的后验地图。(d)地图中残存的不确定度，通过测量地图中对于独立的栅格单元似然函数的灵敏度得到的(译者按:~.~!!!不懂原文的意思)。这个地图中清晰的显示了门的存在，还包含了两端平坦的墙面。

对于算法MSP_occupancy_grid_mapping而言，存在着很多限制，而我们有很多种手段来改进它。该算法是一种最大化后验概率的方法，它对于残留在地图上的不确定度没有概念。虽然灵敏度分析对不确定度做出了近似，但是这个近似过于自信，因为灵敏度分析只检查模型的局部。此外，该算法是一个批处理的方法，不能够增量的运行。实际上，MAP算法需要将所有的数据都保存在内存中。从计算的角度来说，该算法可以通过正则占用栅格地图代替空地图进行初始化，进而加速算法。最后在算法9.3中的第5行中，只有一小部分测量值受到了栅格单元反转的影响。由于每个求和都很大，所以求解最大化函数的时候，只需要检查一小部分的要素。我们可以将这一属性用于基本算法，来增加其计算效率。

9.5 总结

本章介绍了学习占用栅格的算法。本章中所有的算法都需要为机器人提取位置估计，因此它们不需要解决一般的建图问题。

标准的占用建图算法，计算每个栅格单元的占用后验概率。它是在静态环境中二值贝叶斯滤波器的一种实现。
来自多个传感器的数据，有两种方式融合进一个地图中。其一，通过使用贝叶斯滤波器来维护一个地图。其二，维护多个地图，每个地图对应一个传感器。当不同的传感器能够感知不同的障碍物时，第二种方法往往能够取得更好的效果。
标准的占用栅格建图算法依赖于逆测量模型，它从现象(测量值)来归纳原因(占用值)。这点与在定位问题中贝叶斯滤波器不同。在定位问题中，贝叶斯滤波器建立在一个传统的测量模型，从原因来推导现象。
实际上，我们可以从传统的测量模型中学习一个逆测量模型，这是对传感器因果关系的建模。这种方法需要生成学习样本，并使用监督学习方法来训练逆模型。
标准的占用栅格算法不维护占用值之间的依赖关系。这是因为该算法将对整个地图后验概率的估计问题，分解成大量的独立的栅格单元的后验概率的估计问题了。
全地图的后验概率通常是不可计算的，因为定义在栅格上的地图不胜枚举。但是可以最大化这一后验概率。最大化的算法所生成的地图，比使用贝叶斯滤波器的占用栅格算法，在数据上更连续。但是最大化的过程需要用到所有的数据，而且最大化的后验地图并不能捕获地图中剩余的不确定度。

毋庸置疑，占用栅格地图建图方法以及它的各种变型在机器人学中非常流行。这是因为它们非常容易实现，而且能够捕获到机器人导航过程中需要的重要元素。

9.6 参考文献

Elfes (1987)在他的博士论文(1989)中提出了占用栅格地图。被大量引用的文章Moravec (1988)对这一主题做出了很好的介绍，而且本章的核心内容所罗列的基本概率学方法都来自于此。在未发表的工作当中，Moravec and Martin (1994)使用立体视觉作为主要传感器将占用栅格建图方法扩展到了3维场景中。Thrun et al. (1998a)提出了在占用栅格建图中的多传感器融合技术。本章所提到的学习逆传感器测量模型的方法可以在文献Thrun (1998b)中找到。此外，本章所提到的前向建模方法，也是建立在Thrun (2003)的工作基础上的。

占用栅格地图被用于很多不同的目的。Borenstein and Koren (1991)第一个将占用栅格地图用于避障。很多人都用占用栅格地图来定位，他们通过交叉匹配两个占用栅格地图来实现。这种地图匹配方法已经在第七章中详细的讨论过了。 Biswas et al. (2002)使用占用栅格地图来学习动态环境中移动物体的外形。这一方法后来被扩展为学习动态物体的层级分类模型，所有的这些都是用占用栅格地图来表示的(Anguelov et al. 2002)。占用栅格地图已经被广泛的应用于即时定位于建图问题(SLAM)中。这些应用将在后续的章节中讨论。

使用栅格来描述空间的思想，只是移动机器人技术所探索的众多思想之一。传统的运动规划方法假设环境是由多边形构成的，但是并没有给出如何从数据中构建这些模型的方法(Schwartz et al. 1987)。 Chatila and Laumond (1985)给出了一个早期的学习多边形地图的方法。第一个将卡尔曼滤波器应用于声纳数据的fitting line的是Crowley (1989)。更近的工作中， Anguelov et al. (2004)发明了从声纳数据中确定直线门(straight-line door)的方法，并学习可视化的属性用于提升门的检测率。

早期的空间表示范式是拓扑逻辑范式，其空间是由一个局部关系的集合来表示的，通常对应于一个特定的动作使得机器人能够在相邻的节点之间导航通过。拓扑逻辑建图算法的例子包括：Kuipers and Levitt’s (1988)在Spatial Semantic hierarchy上的工作，还有Kuipers et al. (2004)。 Matari´c’s (1990)的硕士学位论文, Kortenkamp and Weymouth’s (1994)从声纳和视觉数据中提取拓扑图的工作。 Shatkay and Kaelbling’s (1997)建立在弧长信息上的空间隐马尔可夫模型(spatial HMM)上的方法。占用栅格地图是其互补范式的一种：尺度表达。尺度表示在一些绝对的坐标系统中直接描述机器人的环境。第二种尺度方法就是EKF SLAM算法，它们将在后续的章节中讨论。

人们已经探索建图算法很多年了，收获了两个最主要的范式：拓扑和尺度。Tomatis et al. (2002)使用拓扑逻辑表达形式一致的实现了闭环，然后将之转化为尺度模式。 Thrun (1998b)首先建立了尺度占用栅格地图，接着从中提取了拓扑框架用于辅助及快速运动规划。在第十一章中，我们将研究跨立在拓扑和尺度两个范式之间的桥梁方法。

9.7 练习

暂略