第一章：介绍
1.1 机器人学中的不确定性
机器人学是一门通过计算机控制的设备来感知和操控物理世界的学科。用于行星探测的移动平台、装配线上的工业机械臂、 跑在高速公路上的自动驾驶汽车、辅助外科手术的医疗机器人等等都是成功的机器人系统的例子。机器人系统在物理世界中通常都有一个实体， 通过传感器感知世界，通过物理力来操控世界。
机器人学目前在很大程度上还处于婴儿阶段，其理念就是智能的操控设备，它具有极大的改变社会的潜能。 如果所有的汽车都能够安全的自动驾驶，让汽车事故成为历史岂不是一项伟大的事业？ 用机器人替代人类来清除像切尔诺贝利这样的核废墟岂不是一个伟大的创举？ 在家庭中用智能服务机器人来完成一些无聊的家务难道不是很有意义吗？
为了完成这些任务，机器人必须能够适应物理世界中普遍存在的各种不确定性。有很多产生机器人的不确定性的因素。
首先而且也是最重要的一点，机器人环境robot environments本来就是不可预测的。 虽然工作在良结构化(well-structured)环境中的装配线上的不确定度比较低，但是像高速公路、室内这样的环境却具有较高的动态特性和不可预测性。 工作在有人类活动的环境中的机器人的不确定度尤其高。
传感器sensors则受限于它的测量能力。量程和灵敏度受限于物理定律，比如说，相机不能透视，而且相机的分辨率是有限的。 此外，传感器是有噪声的，它以一种不可预测的形式干扰传感器的测量值，因此限制了它获取信息的能力。最后，传感器是会损坏的。 检测到一个失效的传感器是机器人困难的。
机器人动作robot actuation在一定程度上也是不可预测的。由于控制的误差、传动机构的间隙将导致机器人的执行器不能完全按照指令工作。 有些执行器，比如说工业机械臂就需要很高的精度，而一些低成本的移动机器人就没有很高的要求。
一些不确定性是由机器人软件导致的。世界的所有内部模型internal models都是近似的。模型是真实世界的抽象， 我们只能对机器人和其环境进行部分建模。尽管我们现在所用的机器人模型很多时候都不是很精致， 但由模型误差所带来的不确定性在机器人学中通常是被忽略的。
此外算法的近似algorithmic approximations也会产生不确定性。机器人是一个实时的系统，对于计算量有要求。 目前所用的很多算法都是近似算法，牺牲了精度来换取响应的实时性。
不确定性的等级依赖于应用场景。在一些机器人应用中，比如说装配线，人们可以很聪明的管理系统，所以不确定性只有很小的影响。 相比之下，在家庭环境中，或者是其它星球上，机器人就必须处理各种潜在的不确定性。无论是它们的传感器， 还是内在的模型都不能够提供足够的信息，让机器人完全确定的做出正确决策，但是它还是得工作。现在机器人学已经进入了一个开放的世界， 不确定性的问题已经成了设计智能机器人系统的绊脚石。管理不确定性可能是迈向鲁棒的真实世界机器人系统的最重要的一步。
因此有了本书。
 |
| 图 1.1. 一个全局定位的移动机器人。 我们将在第七章和第八章中介绍马尔科夫定位技术。 |
1.2 概率机器人学
本书将要提供一个概率机器人学probabilistic robotics的全面综述。概率机器人学是一个较新的机器人学方法， 致力于研究机器人感知和执行中的不确定性。 概率机器人学的核心思想就是使用概率论的公式来显式的表达不确定性。换句话说，概率算法并不是针对世界中的一个现象做出最好的猜测， 而是利用整个假设空间下的概率密度函数来表达信息。如此，它们就可以用数学的形式描述歧义和可信度。即使有不确定的存在， 也可以鲁棒的做出控制选择，而且在控制选择靠谱的情况下，概率机器人学还可以主动的削减它们的不确定性。 因此，概率学算法潇洒的处理了它所面临的不确定性。这因为这样，它们在很多真实世界应用中打败了其它的技术。
我们将以两个生动的例子来说明概率机器人学，一个涉及到了机器人感知，另一个则是规划和控制。
我么的第一个例子就是移动机器人定位(mobile robot localization)。机器人定位问题就是估计机器人相对于一个外部参考系的坐标。 机器人具有其工作环境的地图，但是需要根据传感器的数据来确定其在这个地图中的位置。 来估计机器人的坐标。右图描述了这样一种情况，已知环境中有三个不同的门。 机器人的任务就是通过感知和运动，找出它在哪里。
这个具体的定位问题被称为全局定位global localization。在全局定位中，机器人被放置在一个已知环境中然后定位自己。 在概率学范式中, 机器人的瞬时估计(momentary estimate也称为belief)是用对于空间中所有位置的概率密度函数来表示的。 在一开始机器人什么信息都没有掌握，就用均匀分布来描述这种最大的不确定度，如图1.1a所示。
假设机器人进行了第一次的传感器数据采集，发现它在一个门的旁边。概率学技术应用这一技术来更新置信度，其后验置信度如图1.1b所示。 门旁边的概率增加了，其它地方的概率相对低了很多。我们注意到，这个分布有三个峰值，每一个都对应着环境中的一个门。因此机器人还是无法指导自己到底在哪里。 实际上，他又三个假设在给定传感器数据的情况下具有相同的可能性。我们还注意到，即使不在门的附近也有一个非零的概率值。 这是感知所固有的不确定性的自然结果，机器人判定它在看到一个门时，有一个很小的非零概率出错。这种维护低概率假设的能力是获得鲁棒性的基础。
现在假设机器人继续往前走。图1.1c中显示了机器人的移动对置信度的影响。随着机器人的移动，置信度的峰值也在随着漂移。 而且在不断的扩散，这反映了在机器人的运动过程中引入的不确定性。在图1.1d中机器人又发现了一个门。这个发现使得我们的算法把最高的可能性定位在了一个门前， 此时机器人就很确信自己的位置了。最终图1.1e中显示了机器人继续沿着走廊运动下去的置信度。
这个例子说明了概率学范式的很多方面。用概率学的语言来说，机器人的感知问题就是一个状态估计问题， 我们的定位问题的例子使用了一种称为贝叶斯过滤器(Bayes filter)的算法来后验的估计机器人在空间中的位置。 信息的表示是一个概率密度函数，该函数的更新表示通过传感器测量值获得的信息，或者机器人不确定度增长时信息丢失的过程。
第二个例子将带领我们进入机器人规划和控制的领域。正如我们刚刚提到的，概率学算法可以计算机器人当前的不确定性。此外，它们还可以操作未来的不确定性， 并在确定正确的控制选择的时候考虑这样的不确定性。这样的算法称为海岸线导航coastal navigation。图1.2中显示了一个海岸线导航的例子，图中是一个实际建筑的2维地图。 图(a)对比了一个估计的路径和实际的路径，这个差距就是刚刚讨论的机器人运动的不确定性的结果。一个有趣的现象就是，并不是所有的轨迹具有相同的不确定性等级。 图1.2a中的路径通向了一个相对开阔的空间，缺少可以辅助机器人定位的特征。图1.2b中显示了另外一条路径。这条路径通往一个有特征的角落，通过贴近墙壁来保持定位。 不出意外地，后者的不确定性得到了削减，因此其到达目标位置的机会更高。
 |
 |
| (a) | (b) |
| 图 1.2. （a) 一个机器人通过开放的没有特征的看空间，可能会迷失。 (b) 这点可以通过沿着已知障碍物附近移动来避免。这些图片是一个称为海岸线导航算法的结果， 我们将在第十六章中讨论。Images courtesy of Nicholas Roy, MIT. | |
这个例子说明了合适的不确定性考量对机器人控制的众多影响中的一种。在我们的例子中，对沿途中可能的不确定性的预期，使得机器人更喜欢第二种路径。尽管比较长，但是可以减少不确定性。 由于机器人具有更高的机会到达目标，第二种路径更好。实际上，第二个路径是一个主动信息收集的例子。机器人通过概率学考量，选择最好的动作，来收集沿途的信息，进而到达它的目标位置。 概率学路径规划技术预估了不确定性，并为了收集信息做出规划。概率学控制技术则具体实现了这样的规划的结果。
1.3 内涵
概率机器人学完美的继承了模型和传感器数据，同时克服了两只的限制。这些思想不仅仅关系到底层的控制，从最底层到最上层，它涉及到了机器人软件的所有方面。
相比于类似基于模型的运动规划技术，或者基于行为的反射方法，这样的传统机器人技术，概率学的方法在面对传感器和模型的限制时，具有更高的鲁棒性。 这使得它们能够在复杂的真实世界环境中更好的工作，在这样的环境中不确定性具有更总要的影响。实际上，概率学算法是目前已知的唯一的解决方案，可以处理困难的机器人估计问题， 比如刚刚讨论的机器人定位问题，或者为一个非常大的环境构建准确的地图的问题。
与传统的基于模型的机器人技术对比，概率学算法对机器人模型的准确性有更松的要求。这就解除了程序员的一个难以克服的重担，不再需要构建准确的模型了。 概率学算法对传感器的精度的要求，也比那些只用当前的传感器作为控制输入的反射式技术的要求更宽松。从概率学的角度来看，机器人学习的问题robot learning problem是一个长期的估计问题。 因此，概率学算法为很多机器人学习问题提供了一个有效的方法论。
但是，这些优势是有代价的。概率学算法被提到最多的限制就是计算复杂度，以及需要近似。 概率学算法本身计算效率就低，因为它要考虑整个概率密度函数，而不是只做单一的猜测。需要做出近似是因为大多数机器人的世界都是连续的， 计算准确的后验概率分布通常是不可行的。有时，不确定性可以幸运的用一个参数模型(比如说离散分布或者高斯分布)来近似； 有些情况下，使用这样的近似就太不精确了，需要更复杂的模型来解决。
最近计算机硬件的发展使得我们可以以便宜的价钱获得空前的计算能力。这个发展为概率机器人学领域做出了很多实质性的贡献，最近的研究已经成功的提高了概率学算法的计算效率， 解决了很多困难的机器人学问题，本书将深度的分析很多这样的问题。尽管如此，计算瓶颈仍然存在。我们需要从很多方面重新审视这些问题，分析各种具体的概率学解决方案的力量和缺陷所在。
1.4 路线图
本书被组织为四个主要的部分：
- 第2到第4章介绍本书所描述的算法背后的基本数学框架，以及关键的算法。这些章节是本书的数学基础。
- 第5到6章展现了移动机器人的概率学模型。在很多形式上，这些章节都是经典机器人模型的概率学扩展。它们形成了后续内容中的机器人基础。
- 在第7和第8章中讨论了移动机器人定位问题。这些章节在第5和6章讨论的概率学模型的基础上，组合了基本的估计算法。
- 第9到13章讨论了机器人建图算法。和之前一样，它们都基于基础章节中讨论的算法，但是它们使用了很多技巧来适应建图问题的巨大复杂度。
- 在第14到17章中讨论了概率学的规划和控制问题。我们从一些基础的技术开始介绍，接着发展到通过概率来实际控制机器人的算法中。 最后一章，第17章，从概率学的视角讨论了机器人探索问题。
本书最好按照顺序从头读到尾。但是，我们尝试让每个章节都具有一定的自解释能力。所以，那些"...的数学推导"的章节在第一次阅读的时候可以先跳过，并不会影响本书总体的连贯性。
1.5 概率机器人教学
如果在课堂上使用本书，我们不建议从头到尾的按照顺序教学，除非学生们具有非同寻常的抽象数学概念的理解能力。 粒子滤波器要比高斯滤波器更容易教学，而且移动机器人定位问题也比抽象的滤波器算法更容易让学生们兴奋。在我们自己的教学当中，我们通常从第2章开始，接着直接跳到第7和第8章中。 在教定位问题的时候，我们会根据需要回过头来介绍第3到第6章的内容中。我们也会提前教第14章，在课程的早期就把关于规划和控制的问题暴露在学生面前。
作为教师，请放心使用本书网站上的课件和动画来举例说明本书中的各种算法。也欢迎给我们这些作者发送你们的课程网站链接，以及任何可以帮助概率机器人学教学的材料。
本书中的材料的最好教学方式就是亲手实现各种任务。在机器人学中没有比编程控制实际的机器人更好的教学材料了。而且没有人可以比自然更好的解释机器人学中的各种坑！
1.6 参考文献
机器人学中的软件设计已经经历了几个范式。第一个主要的范式出现在1970年代中叶，称为基于模型的范式。基于模型的范式从一系列的研究开始， 揭示了在连续空间中控制高自由度机器人的难度(Reif 1979)。在类似Schwartz et al.’s (1987)的文献中，分析了机器人运动的复杂度，这一范式的研究达到的巅峰。 第一个单指数通用运动规划算法由Canny (1987)提出，Latombe’s (1991)是基于模型的运动规划领域中具有甚远影响的介绍文章， 在第十四章中我们将讨论更多的里程碑式的贡献。 尽管已经开始广泛的使用随机化的技术来解决困难的运动规划问题(Kavraki et al. 1996)，但是这些早期的工作严重忽略了不确定性问题。 在机器人和环境的模型都是完全和准确的假设下，机器人是确定性的。模型必须足够精确，剩余的不确定性则通过底层的运动控制器来管理。 尽管像潜在场(potential fields) (Khatib 1986)，导航函数(Koditschek 1987)这样的技术，提供了对可能感知到的未预见的事物做出反应的机制， 大多数运动规划技术只是简单的生成单一的参考路径用于控制执行器的轨迹。这些早期技术的应用，限定在任何细微的不确定性都可以工程化解决，或者传感具有足够的准确性的环境中。
在1980年代中其，这个领域发生了激进的变化。此时缺乏传感反馈已经变成了整个机器人研究社区的焦点。具有坚定的信念，基于行为的机器人学领域摒弃了任何内部模型的思想。 实际上它是一个情景代理situated agent与物理环境的交互(Kaelbling and Rosenschein 1991)，创建了机器人运动中的复杂度， 这一现象通常被称为紧急行为emergent behavior(Steels 1991)。因此，传感扮演了一个至关重要的角色，并且摒弃了内在模型(Brooks 1990)。
这一领域的热情被有一些早期的成功案例所点燃，远远的超出了传统的基于模型的运动规划算法的范围。其中包括Brooks (1986)开发的称为"成吉思汗"的六足机器人。 一个相对简单的有限状态自动机就能够控制这个机器人的步态，即使在崎岖不平的地形上也没有问题。这一技术成功的关键就是感知，控制完全是由与环境的交互来驱动的， 都是通过机器人的传感器来收集的信息。有些早期的工作，通过聪明的环境探索反馈，创造了一个相对复杂的机器人，而收到人们的膜拜(Connell 1990)。后来，这一范式获得了商业上的成功， 这是一个真空清洁机器人(IRobots Inc. 2004)，它的软件就是基于行为范式的。
因为缺少内在模型，并且关注于简单的控制机制，大多数机器人系统都被限定在相对简单的任务上。这些任务中瞬时的传感器信息足以确定正确的控制动作。 意识到这些限制，该领域中的一些更近期的工作拥抱了混合控制结构(Arkin 1998)，基于行为的技术提供了底层的控制，而基于模型的规划器在上层，以一种抽象的形式协调着机器人的动作。 这样的混合结构在今天的机器人中也很常见。它们与Gat (1998)的影响深远的三层结构的工作没有什么不相似之处，它起源于"Shakey the Robot"(Nilsson 1984)。
现代的概率机器人学出现在1990年代，尽管它们的根源可以追溯到卡尔曼滤波的提出(Kalman 1960)。在很多层面上，概率机器人学是介于基于模型和基于行为的技术之间。 在概率机器人学中，是有模型的，但是它们假设控制都是不完整和不充分的。也有传感器测量，也被认为是不完整和不充分的。通过整合运动和测量模型， 就可以设计一个控制动作。统计学提供了整合运动和测量模型的数学胶水。
在未来的章节中，我们将讨论概率机器人学中很多关键的优势。这个领域中的一些基石包括Smith and Cheeseman (1986)开发的用于高维感知问题的卡尔曼滤波器技术， Elfes 1987; Moravec 1988提出的占用栅格地图，Kaelbling et al. (1998)再次引进的部分可观测规划技术。在过去的十年就已经看到了一种探索技术， 粒子滤波器已经变得非常流行(Dellaert et al. 1999)，而且研究者们还开发了新的编程方法，关注于贝叶斯信息处理(Thrun 2000b; Lebeltel et al. 2004; Park et al. 2005)。 这一技术发展的同时，伴随着由概率学算法驱动的物理机器人系统的发展，比如说Durrant-Whyte (1996)设计的用于货运的工业机器，博物馆中的娱乐机器人(Bur-gard et al. 1999a; Thrun et al. 2000a; Siegwart et al. 2003)，以及用于医护和康复的机器人(Pineau et al. 2003d)。Montemerlo et al. (2003a)描述了一个大量使用概率学技术的，用于移动机器人控制的， 开源软件包。
商业机器人领域也进入了一个转折点。在每年的世界机器人调查中， 联合国和国际机器人联盟(the United Nations and the International Federation of Robotics)在2004发现世界的机器人市场每年上升19%。更为显著的是市场划分的变化， 表现出从工业应用像服务机器人和消费产品的转变。