蒙特卡罗定位

蒙特卡罗定位通常被称为粒子滤波（Particle Filter），这是一种重要性重采样（SIR），也被称为自举滤波（bootstrap filter）、蒙特卡罗滤波、凝聚算法（condensation algorithm）或适者生存算法（survival of the fittest algorithm）。其关键思想是通过一个有N个加权的、随机的样本或粒子S的集合来表示后验可信度Bel(l)。

MCL中的样本表示成<<x, y, theta>, p>，表示了机器人的位置（坐标x,y，方向theta）和数值权重因子p，并假设：

\sum_{n=1}^{N}p_{n}=1

机器人移动

当机器人移动时，MCL在移动命令之后生成N个近似该机器人位置的新样本，其中每一个样本都是从之前计算出的样本集中随机取出的，取出概率由它们的p值决定。

我们记 l' 为当前样本机器人的位置，然后使用观察到的动作 a，从 P(l | l' , a) 中随机抽取一个单个随机样本，进而得到该新样本的 l。该新样本的 p 值为 N^{-1}。

上图描述了一个非传感机器人的基于采样的位置可信度近似

注意这种采样技术的效果——从一个已知的起始位置开始，然后按实线的指示和不确定性不断增加的样本集近似分布来执行动作；其中不断增加的不确定性代表了由于滑移和漂移所造成的位置信息的逐渐损失。该运动模型必须为噪声提供补偿。这会不可避免地导致运动更新过程中粒子发散。这是可以预见的，因为如果一个机器人不感知环境地盲目移动，那么它对自己的位置就不会很确信。

上图：机器人运动的概率模型：在如图所示的运动之后积累的不确定度：(a) 40 米，(b) 80 米

图 2：机器人感知的概率模型：(a) 在感知到 5 米距离内的一个地标后的不确定度，(b) 相应的地图

传感器读数

传感器读数是通过重新加权样本集而整合进来的，这种方式在马尔可夫定位中实现了贝叶斯规则。这种加好的样本对于机器人丢失其位置轨迹的罕见事件中的重新定位（relocalization）是很关键的。如果当MCL使用有限样本集时没有生成接近机器人正确位置的样本，那么通过加入数量很少的随机样本，MCL可以有效地重新定位机器人以解决该问题。

假设<l, p>是一个样本，p ← alpha P(s | l)，其中s是传感器的测量，而alpha是归一化（normalization）。这些参数总的来说必须使：

\sum_{n=1}^{N}p_{n}=1

一种能在 O(N) 时间有效执行这个重采样过程的算法可见于 Carpenter 等人于1997年的论文 An improved particle filter for non-linear problems.

[引用来源：https://www.jiqizhixin.com/articles/2017-02-13-7]

发展历史

描述(300字)

蒙特卡罗定位最初由卡耐基梅隆大学计算机科学学院的Dieter Fox等人在1999年的国际机器人与自动化会议（International Conference on Robotics and Automation）上提出的，并在机器人领域的基于样本的评估（sample-based estimation）中首次得到了应用，而现在它已经在种类广泛的应用中得到了使用。

MCL算法有多种变异算法，使其能更好的适应不同的应用场景，更加高效，其中一种比较著名的是使用相对熵（KL散度）来创立一个直方图从而使得收敛更加迅速。

MCL算法的另一位主要作者是谷歌无人车之父 Sebastian Thrun， Thrun 于2011年创办了优达学城（UDACITY）专注于无人驾驶，机器学习的在线课程，其中包含MCL算法，致力于为无人驾驶输出人才。

主要事件

发展分析

瓶颈

相对于这一领域早期的成果，MCL有几个关键优势：

• 与已有的基于卡尔曼滤波的技术相比，它能够表征多模态分布，因此能够全局地定位机器人。
• 相比于基于网格的马尔可夫定位，它能极大地减少对内存的需求，并且可以以相当高的频率集成测量。这个在线的算法非常适合任何时间的实现。
• 因为其样本中所表征的状态不是离散的，所以其在有固定的单元大小时比马尔可夫定位更加准确。
• 其实现要容易得多。

相比比大多数之前精确的马尔可夫定位算法，MCL给出了显著更加精确的结果，同时内存和计算资源的消耗也低一个数量级。在一些案例中，MCL能可靠地定位之前的方法无法起效的机器人。大体来说，在固定的样本集上，自适应采样的表现和MCL差不多。但在涉及到许多有不同不确定度的场景（全局vs局部）中，自适应采样比固定样本大小更优。MCL依照先验概率中最可能的方式随机的猜测可能的位置，并调整样本数量与传感器数据中的不一致数量比。

MCL的一个问题就是如果机器人在没有移动的情况下，而不断的采集更新数据，会使得一些正确状态的值被舍弃从而导致算法的失败。

未来发展方向

未来，这种基于样本的定位的更高效将会被应用到多机器人场景中，其中不同机器人的样本集可以在机器人检测到其它机器人时进行同步，同时将蒙特卡罗方法也将应用于机器人地图获取问题，2016年，来自西班牙的PAL Robotics基于适应性MCL算法开发出一套可以即时更新地图的机器人导航系统。随着无人驾驶技术的发展，MCL算法将更多的应用在地图感知和建模中，为无人驾驶保驾护航。

Contributor: Chao Yang