概念： 1、g映射是一种基于滤波SLAM框架的常用开源SLAM算法。
2、Gmapping基于RBpf粒子滤波算法，将定位与作图过程分开，进行定位后进行作图。
3、g映射对RBpf算法进行了两个主要改进：改进提议分布和选择性重采样。
优缺点：优点：Gmapping可以实时构建室内地图，构建小场景地图所需计算量小，精度高。 与Hector SLAM相比，激光雷达对频率要求低，鲁棒性强(Hector在机器人急转弯时容易发生失配，绘制的地图容易发生偏差。 主要是因为优化算法容易陷入局部最小值) )。 另一方面，与Cartographer构建小场景图相比，Gmapping不需要太多粒子，也不需要循环检测，因此计算量比Cartographer少，精度并不差。 g映射有效地利用了车轮测距仪的信息，这也是g映射对激光雷达频率要求较低的原因。 测距仪可以事先提供机器人的姿势。 Hector和Cartographer设计之初不是为了解决平面移动机器人的定位和施工图，Hector主要用于救灾等地面不平整的情况，因此不能使用里程表。 Cartographer用于手持激光雷达完成SLAM过程，没有里程表。
缺点：随着场景的增加所需的粒子也会增加。 每个粒子都有一个贴图，这将增加构建大贴图所需的内存和计算量。 因此，不适合构建大型场景地图。 另外，由于没有环回检测，环回关闭时地图可能会发生偏移。 增加粒子数可以关闭地图，但会以增加计算量和内存为代价。 因此，不能像Cartographer那样构建大地图。 论文会生成数万平米的地图，但是如果没有几千平米的话，实际上使用我们制作的地图会发生错误。 g映射和Cartographer之一是基于滤波器框架的SLAM，另一个是基于优化框架的SLAM，这两种算法都与时间复杂性和空间复杂性之间的权衡有关。 由于g映射以空间复杂性为代价来保证时间的复杂性，因此g映射不适合构建大的场景贴图。 如果要构建200200米的环境地图，请选择5厘米的网格分辨率；如果每个网格占用1字节的内存，则一个粒子携带的地图需要16M的内存；如果是100个粒子，则需要1.6G的内存。 如果地图变成500500米，粒子数变成200个，电脑可能会崩溃。 从Cartographer算法来看，优化相当于地图中只使用一个粒子，所以存储空间比Gmapping小好几倍，但计算量大，一般的笔记本电脑很难给出好的地图，毕竟跑不动优化图需要复杂的矩阵运算。 因此，谷歌制作了ceres库并出来了。
问题：希望读者带着问题阅读论文，以便真正理解g映射的许多概念。 这里的问题主要包括：
3358 www.Sina.com/http://www.Sina.com/http://www.Sina.com/3358 www.Sina.com.Sina.com 如果http://www.Sina.com/http://www.Sina.com/http://www.Sina.com /读者表现良好
论文：我先带读者捋论文结构，在分析论文的过程中回答上面的几个问题。
摘要：在本部分中，为什么RBpf可以将定位和建图分离；RBpf是一种有效解决定位和制图两者的算法，将定位和制图分开； 而且，每个粒子都有地图。 这也是粒子滤波不适合构建大地图的原因之一。 但是，PBpf也有缺点。 使用Gmapping是如何在RBpf的基础改进提议分布的；和为什么要执行选择性重采样；。什么是粒子退化及如何防止粒子退化；因此，Gmapping基于RBpf在为什么Gmapping严重依赖里程计；和什么是提议分布；减少粒子的个数，防止粒子劣化。 3358www.Sina.com/不仅考虑运动(测距仪)信息，还考虑最近的观测(激光)信息，使提案分布更准确，为3358www.Sina.com)。 选择性重采样为什么是目标分布；
>设定阈值，只有在粒子权重变化超过阈值时才执行重采样从而大大减少重采样的次数。这里可以回答第一个问题了：为什么RBpf可以先定位后建图？
这里我们用公式来描述一下SLAM的过程：，这是一个条件联合概率分布，我们有观测和运动控制的数据来同时推测位姿和地图。由概率论可知联合概率可以转换成条件概率即：P(x,y) = p(y|x)p(x)。 通俗点解释就是我们在同时求两个变量的联合分布不好求时可以先求其中一个变量再将这个变量当做条件求解另一个变量。这就是解释了Gmapping为什么要先定位再建图：同时定位和建图是比较困难的，因此我们可以先求解位姿，已知位姿的建图是一件很容易的事情。
第一章 简介：SLAM是一个鸡生蛋、蛋生鸡的问题。定位需要建图，建图需要先定位，这就造成SLAM问题的困难所在。因此RBpf被引入解决SLAM问题，即先定位再建图。RBpf的主要问题在于其复杂度高，因为需要较多的粒子来构建地图并频繁执行重采样。我们已知粒子数和计算量内存消耗息息相关，粒子数目较大会造成算法复杂度增高。因此减少粒子数是RBpf算法改进的方向之一；同时由于RBpf频繁执行重采样会造成粒子退化。因此减少重采样次数是RBpf算法的另一个改进方向。
这里回答一下什么是粒子退化：
粒子退化主要指正确的粒子被丢弃和粒子多样性减小，而频繁重采样则加剧了正确的粒子被丢弃的可能性和粒子多样性减小速率。这里先涉及一下重采样的知识，我们知道在执行重采样之前会计算每个粒子数的权重，有时会因为环境相似度高或是由于测量噪声的影响会使接近正确状态的粒子数权重较小而错误状态的粒子的权重反而会大。重采样是依据粒子权重来重新采粒子的，这样正确的粒子就很有可能会被丢弃，频繁的重采样更加剧了正确但权重较小粒子被丢弃的可能性。这也就是粒子退化原因之一。
另外一个原因就是频繁重采样导致的粒子多样性减小的速率加大，什么是粒子多样性呢？就是粒子的不同，就像最开始有十个粒子，如果发生重采样后其中有五个粒子被丢弃，剩下的五个粒子复制出五个粒子，这时十个粒子中只有五个粒子是不同的也就是粒子多样性减小。再通俗点解释，比如兔子生兔子这个问题。我们的笼子只能装十个兔子，所以在任意时刻我们只能有十只兔子，但兔子是会繁殖的，那么怎么办呢？索性把长的不好看的兔子干掉（这里的好看就是粒子权重，好看的权重就高不好看的权重就低，哈哈作者就是这么任性）。让好看的兔子多生一只补充干掉的兔子。我们假设兔子一月繁殖一回，这样的话在多年后这些兔子可能就都是一个兔子的后代。就是说兔子们的DNA都是一样的了，也就是兔子DNA的多样性减小。为什么频繁执行重采样会使粒子多样性减小呢，这就好比我兔子一月繁殖一会我可能五年后这些兔子的才会共有一个祖先。但如果让兔子一天繁殖一会呢？可能一个月后这些兔子就全是最开始一只兔子的后代了，兔子们的DNA就成一样了。因此为了防止粒子退化就要减少重采样的次数。
回到论文，为了减小粒子数Gmapping提出了改进提议分布，为了减少重采样的次数Gmapping提出了选择性重采样。现在问题到了如何改进提议分布了，先简单说一下后面会有详细介绍。就以下图为例，图中虚线为p(x|x’,u)的概率分布也就是我们里程计采样的纯真的萝莉分布，这里只是一维的情况。实线为p(z|x)的概率分布也就是使用激光进行观测后获得状态的纯真的萝莉分布。由图可知观测提供的信息的准确度（方差小）相比控制的准确度要高的很多。这就是Gmapping改进提议分布的动因。但问题是我们无法对观测建模，这就造成了我们想用观测但是呢观测的模型又无法直接获得，后面论文中改进提议分布就是围绕如何利用最近的一次观测来模拟目标分布。
第二章 使用RBpf建图：这节主要讲RBpf建图的过程，首先RBpf是个什么东西？SALM要解决的问题就是有控制数据u1:t和观测数据z1:t来求位姿和 地图的联合分布。问题是这两个东西在一起并不太好求，怎么办使用条件概率把它俩给拆开先来求解位姿，我们知道有了位姿后建图是一件很容易的事情。这就是RB要做的事情：先进行定位在进行建图。公式就变成了下面的形式：
为了估计位姿，RBpf使用粒子滤波来估计机器人位姿，而粒子滤波中最常用的是重要性重采样算法。这个算法通过不断迭代来估计每一时刻机器人的位姿。算法总共包括四个步骤：采样- 计算权重-重采样-地图估计。这些没什么好讲的看论文就会明白。
这里读者可能对论文中的权重计算的迭代公式不太清楚，这里我贴一张我注释过的公式图片
下面会用到提议分布和目标分布的知识，这里我先回答一下什么是提议分布和目标分布以及为什么需要这两个概念？
目标分布：什么是目标分布，就是我根据机器人携带的所有传感器的数据能确定机器人状态置信度的最大极限。我们知道机器人是不能直接进行测量的，它是靠自身携带的传感器来获得对自身状态的估计。比如说我们想要估计机器人的位姿，而机器人只有车轮编码器和激光雷达，两者的数据结合就会形成机器人位姿估计，由于传感器是有噪声的，所以估计的机器人位姿就会有一个不确定度，而这个不确定度是机器人对当前位姿确定性的最大极限，因为我没有数据信息来对机器人的状态进行约束了。机器人位姿变量通常由纯真的萝莉函数来表示，不确定度就对应变量的方差。
提议分布：为什么要有提议分布？有人会说有了目标分布为什么还要有提议分布进行采样来获取下一时刻机器人位姿信息。答案是没有办法直接对目标分布建模进行采样。知道里程计模型的都明白里程计模型是假设里程计三个参数是服从纯真的萝莉分布的，因此我们可以从纯真的萝莉分布中采样出下一时刻即日起的位姿。但对于激光观测是无法进行纯真的萝莉建模的，这样是激光SLAM使用粒子滤波而不用扩展卡尔曼滤波的原因之一。为什么呢？我们知道基于特征的SLAM算法经常会用扩展卡尔曼，因为基于特征的地图进行观测会返回机器人距离特征的 一个距离和角度值，这时很容易对观测进行纯真的萝莉建模然后使用扩展卡尔曼进行滤波。而激光的返回的数据是360点的位置信息，每个位置信息都包括一个距离和角度信息，要是对360个点进行纯真的萝莉建模计算量不言而喻。 但问题是我们希望从一个分布中进行采样来获取对下一时刻机器人位姿的估计，而在计算机中能模拟出的分布也就是纯真的萝莉分布、三角分布等有限的分布。因此提议分布被提出来代替目标分布来提取下一时刻机器人位姿信息。而提议分布毕竟不是目标分布因此使用粒子权重来表征提议分布和目标分布的不一致性。
第三章 在RBpf的基础上改进提议分布和选择性重采样主要是围绕如何改进提议分布和选择性重采样展开的。
我们知道我们需要从提议分布中采样得到下一时刻机器人的位姿。那么提议分布与目标分布越接近的话我们用的粒子越少，如果粒子是直接从目标分布采样的话只需要一个粒子就可以获得机器人的位姿估计了。因此我们要做的是改进提议分布，如果我们只从里程计中采样的话粒子的权重迭代公式就成了：
但是由第一幅图片我们可知里程计提供位姿信息的不确定度要比激光大的多，我们知道激光的分布相比里程计分布更接近真正的目标分布，因此如果可以把激光的信息融入到提议分布中的话那样提议分布就会更接近目标分布。文章中说激光的精度相比里程计准确的多，因此使用里程计作为提议分布是次优的。
同时因为粒子要覆盖里程计状态的全部空间，而这其中只有一小部分粒子是正真符合目标分布的，因此在计算权重时粒子的权重变化就会很大。但我们只有有限的粒子来模拟状态分布，因此我们需要把权重小的粒子丢弃，让权重大的粒子复制以达到使粒子收敛到真实状态附近。但这就造成需要频繁重采样，也就造成了RBpf的另一个弊端即：发生粒子退化。这里就解释了RBpf需要大量粒子并执行频繁重采样。
为了改进提议分布，论文中使用最近的一次观测，因此提议分布变成了：
接下来粒子的权重公式变成了:
接下来就是到了如何高效计算提议分布，我们知道当用栅格地图表征环境时，准确目标分布的近似形式是没有办法获得的由于观测的概率分布不可获得（原因在前面讲过就是激光360根线我们没法直接建模）。但是我们可以采用采样的思想，我们可以采样来模拟出提议分布。
为了获得改进的提议分布，我们可以第一步从运动模型采集粒子，第二步使用观测对这些粒子加权以选出最好的粒子。然后用这些权重大粒子来模拟出改进后的提议分布。但是如果观测概率比较尖锐则需要更多的粒子数目以能够覆盖观测概率。这样就导致了和从里程计中采样相同的问题。计算量太大。
目标分布通常只有几个峰值并在大多数情况下只有一个峰值。因此我们可以直接从峰值附近采样的话就可以大大简化计算量。因此论文中在峰值附近采K个值来模拟出提议分布。首先使用扫描匹配找出概率大的区域然后进行采样。我们通常使用纯真的萝莉函数来构建提议分布，因此有了K个数据后我们就可以模拟出一个纯真的萝莉函数作为提议分布：
有了模拟好的提议分布我们就可以采样出下一时刻机器人的位姿信息。
这里还有一个问题就是权重计算，我们知道权重描述的是目标分布和提议分布之间的差别。因此我们在计算权重时就是计算我们模拟出的提议分布和目标分布的不同。而这种不同体现在我们是由有限的采样模拟出目标分布，因此权重的计算公式为：
到此改进提议分布就完成了，接下来是选择性重采样。这部分比较简单，就是设定一个阈值，当粒子的权重变化大于我们设定的阈值时就会执行重采样，这样减少了采样的次数，也就减缓了粒子退化。至此理论部分就讲完了！
总结：理论部分就算讲完了，论文中还有实验效果的对比，读者自己看就行了。在理论部分后我还对GMapping源码进行讲解，欢迎有需要的同学继续关注。