移动机器人的同步自定位与地图创建研究进展_基于自适应方法的移动机器人同时定位与地图构建研究

转http://blog.sina.com.cn/s/blog_4fb72d4e01000cul.html

基础知识介绍的非常好，而且居然是07年的文章了，这十年，看国内的发展好像并不是十分大

作者：陈卫东，张 飞

摘要：自主移动机器人在未知环境下作业时，首先要解决的基本问题就是其自身的定位问题，而定位问题与环境地图的创建又是相辅相成的．本文从相关理论和关键技术等方面，系统地总结了同步自定位和地图创建的研究现状，着重介绍了基于概率论的方法，分析了目前存在的难题，并指出了未来研究的发展方向．

 

1 SLAM的相关理论与关键技术(Theories and technologies of SLAM )

该领域所涉及的关键性问题可以归结为：

(1) 地图的表示方式 (大致可分为3类:栅格表示、几何特征表示和拓扑图表示)

(2) 不确定性信息处理方法------不确定性信息处理必须解决以下问题：

   ·在地图和位置的表示中，如何描述运动和感知信息的不确定性?

·在迭代过程中，如何处理旧信息与新信息的关系，连续更新地图与位置?

·如何依据不确定的信息进行决策?

(3) 数据的关联；(为了获得全局的环境地图和实现定位，还需要将不同时间、不同地点的感知信息进行匹配和联合，存在局部数据之间的关联问题，也存在局部数据与全局数据的关联与匹配问题)

(4) 自定位；(移动机器人的定位按照有无环境地图可以分为基于地图的定位和无地图的定位)

(5) 探索规划(主要目的是提高地图创建的效率，使机器人在较短的时间内感知范围覆盖尽可能大的区域，在这方面的研究成果较少)

其中，前2个属于工具选择上的问题，而后3个则是SLAM 问题所包含的研究内容．虽然这里列出了5个问题，但这些问题并不是孤立考虑的，彼此间存在紧密的关联和渗透．

 

2 基于概率论的SLAM算法(SLAM algorithms based on probabilistic methodology)

由于SLAM 问题涉及未知且不确定的环境描述和传感器噪声，一般使用概率方法来描述该问

题．扩展Kalman滤波方法是多种SLAM算法的基础,用于同步创建地图和估计机器人的位置．但是其计算量大和对数据关联问题处理困难的缺点也十分明显，随后提出的稀疏扩展信息滤波算法和FastSLAM算法在这两方面有所改进．

3 目前存在的问题与解决途径(Open issues and approaches)

虽然各国学者在自定位和地图创建理论和技术上进行了诸多探索，但多集中在对已知地图或已知位置的前提下的现有方法的扩展和改进，对SLAM的系统性研究才刚刚起步，仍然面临众多难题．

1)适用环境．

目前的概率和模糊方法是基于先验模型的，大多数研究都是假设机器人所在的环境是一个静态环境，当环境发生变化或存在动态障碍物(例如走动的人)时，会造成系统误差增大甚至失效．对于大型环境，现有SLAM算法的时、空需求矛盾更加突出，不确定性的连续传递所造成的系统误差更严重，需要寻找更有效的估计算法和探索规划方法．对于室外或复杂环境，由于感知的不确定性更为严重，需要更为准确、鲁棒的环境特征提取和建模方法，以及更有效的数据关联技术．

2)迭代与收敛性．

SLAM中的地图创建和自定位过程是相互迭代，连续进行的．对该过程的收敛性以及收敛速度缺乏严格的理论分析．

3)计算效率．

3种主要地图表示(栅格、几何特征和拓扑地图)在定位精度和计算复杂度上存在矛盾．目前广泛采用的栅格地图，虽然便于递增计算，但计算复杂度高．因此有机地综合其它地图表示方式，将是提高计算效率的有效途径。基于Kalman滤波和Markov推理(包括它的扩展Monte Carlo方法)的各种定位方法可以用于多种场合，同时获得很高的定位精度，并且在噪声环境下可以保持令人满意的鲁棒性，但是由于都是基于大量统计数据的概率模型，其计算复杂度为0(K²~K³)，计算效率低，实时眭差，限制了在大型和室外复杂环境中的应用．

4)基于视觉的SLAM．

SLAM中使用的外传感器主要是声纳和激光雷达，随着机器视觉的发展，应该更好地利用视觉传感器所提供的丰富环境信息，但必须解决视觉应用的环境适应性、鲁棒性和计算效率问题．

5)3维空间．

目前的应用环境、地图表示和定位算法主要是在2维空间 ，向3维空间的拓展既是应用的需要也是克服目前2维SLAM 问题的一种有效途径．对于以上问题，一方面需要提高机器人个体的感知能力，另一方面也需要在现有的机器人感知能力限制下，设计更好的SLAM结构和算法，以提高系统的实用性．我国学者在自定位 和地图创建两个分支领域已取得了初步成果，但对SLAM 问题还缺乏系统化的研究．

 

 

参考文献(References)：

[1] ELFES A,MORAVEC H．High resolution maps from wide angle sonar[C]∥Proc of the IEEE Int Conf on Robotics and Automation．St．Louis MO：IEEE Press.1985:1l6-121．

------基于栅格的地图表示方法,将整个环境分为若干相同大小的栅格

[1,2]------自从移动机器人诞生以来，对定位问题的研究就和地图创建问题密切关联，已知环境地图的定位问题和已知定位的地图创建问题已经被广泛研究，提出了多种有效的解决途径

[1,2,5]------ 基于地图的定位技术近年来取得了较大进展，提出了一些针对真实环境具有较高实时性和实用性的新方法，如GVG，三角定位法以及Markov定位法

 

[2] BORENSTEIN J,EVEREIT H R,FENG L, el a1．Mobile robot positioning：sensors and techniques[J].J of Robotic Systems，Special Issue on Mobile Robots,1997,14(4):23l-249.

------无地图的定位主要采用基于人工路标(Land—mark)的方法，其缺点在于需要人工干预，在现场设置路标，这些人为工作相当于对环境的再结构化．

[2,7,8]------当前的移动机器人大多考虑采用各种机载的传感器(如激光测距仪，声纳，视

觉，码盘等)进行定位

[2,6,9]------ SLAM中使用的外传感器主要是声纳和激光雷达

 

[3] SMITHR,SELFM,CHEESEMANP.A stochastic map for uncertain spatial relationships [C] //Proc of the 4th Int Symposium or Robotic Research．Cambridge MA:MIT Press.1987:467-474．

------机器人位置和地图两者的估算是高度相关的，任何一方都无法独立获取．这样一种相辅相生、不断迭代的过程，曾有人形象地比喻为“鸡和蛋”的问题．被学术界简称为SLAM 问题，即同步定位和地图创建(simultaneous localization and map building)问题，随着移动机器人应用环境日趋复杂和非结构化，其已成为自主移动机器人面临的急需解决的重要基础性难题，日益受到关注

 

[4] THRUN S，BUCKEN A．Integrating grid-based and topological maps for mobile robot navigation[C]//Proc of the 13th National Conf on Artificial Intelligence Portland Oregon：AAAI Press，1996：944-950．

[4,5]------对于每个栅格指出其中是否存在障碍物,已经在许多机器人系统中得到应用, 是使用较为成功的一种方法. ．栅格地图的缺点是：当栅格数量增大时(在大规模环境或对环境划分比较详细时)，对于地图的维护所占用的内存和CPU时间迅速增长，使计算机的实时处理变得很困难

[4,8]------拓扑图也是一种紧凑的地图表示方法，特别在环境大而简单时．这种方法将环境表示为一张拓扑图(graph)，图中的节点对应于环境中的一个特征状态、地点(由感知决定)，如果节点间存在直接连接的路径则相当于图中连接节点的弧．这种表示方法可以实现快速的路径规划．由于拓扑图通常不需要机器人准确的位置信息，对于机器人的位置误差也就有了更好的鲁棒性．但当环境中存在两个很相似的地方时，拓扑图的方法将很难确定这是否为同一节点(特别是机器人从不同的路径到达这些节点时

 

[5] ORIOLO G，ULM G，VENDITI'EIJJ M．Fuzzy maps：A new tool for mobile robot perception and planning [J]．J of Robotic System，1997．14(3)：179—197．

------模糊逻辑解决不确定性问题。模糊逻辑提供了一个处理不确定性(特别是声纳感知的不确定性)较为鲁棒且有效的工具，同时，在对多种不确定性信息进行建模和融合时可以有更多的操作符供选择．

 

[6] OHYA A，NAGASHIMA Y，YUTA S．Explore unknown environment and map construction using ultrasonic sensing of normal direction of walls[C]∥Proc of the IEEE Int Conf on Robotics and Automation．San Diego CA; IEEE Press．1994：485—492．

------

[7] CHONG K S，KLEEMAN L．Mobile—robot map building from an advanced sonar array and accurate odometry [J]．Int f of Robotics Research，1999，18(1)：20—36．

[6,7]------基于几何特征的地图表示方法是指机器人收集对环境的感知信息，从中提取更为抽象的几何特征，例如线段或曲线，使用这些几何信息描述环境

 

[8] KORTENKAMP D，WEYNOUTH T．Topological mapping for mobile robots using a combination of sonar and vision sensing [c]∥Proc of the 12^th National Conf on Artificial Intelligence．Menlo Park：AAAI Press，1994：979—984．

------

[9] THRUN s，FOX D，BURGARD W．A probabilistic approach to concurrent mapping and localization for mobile robots [J]．Machine Learning，1998，31(1-3)：29—53．

------概率的方法解决不确定性问题，如Bayes估计，Kalman滤波和Markov推理等

[9,12,14]------ 由于SLAM 问题涉及未知且不确定的环境描述和传感器噪声，一般使用概率方法来描述该问题

 

[10] CASTELANOS J A，NEIRA J，TARDOS J D．Multisensor fusion for simultaneous localization and map building[J]．IEEE Trans on Robotics and Automation，2001，17(6)：908—914．

------Markov推理解决不确定性问题。以概率描述信息的不确定性其优点在于：适应不确定模型，对于性能差的传感器也能表示其感知信息，在实际应用中鲁棒性较好，在很多实现中得到了应用．缺点是计算量较大。

[10，12，24~28] 扩展Kalman滤波(EKF)是非线性系统的线性估计，广泛应用于定位、创建地图和导航等算法上，同时它也是多种SLAM算法的基础

 

[11] NEIRA J，TARDOS J D．Data association in stochastic mapping using the joint compatibility test[J]．IEEE Trans on Robotics and Automation，2001，17(6)：890—897．

------在SLAM 中使用的数据关联算法也多种多样，如近邻算法和联合相容性算法[11]

 

 

[l2] DISSANAYAKE G,NEWMAN P,CLARK S,et a1.A solution to the simultaneous localisation and map building(SLAM)problem [J] IEEE Trans on Robotics and Automation,2001,17(3):229-241．

------研究探索规划，一般遵循的策略是：让机器人总是沿着最短路径到最近的未探索区域. 这种方法原理上效率较高，但考虑到信息的不确定性，精心设计的路径未必可行，而且复杂的算法也会影响计算的实时性．因此，需要设计更高效的控制策略，实现精确性和实时性的折衷，既能利用重复定位获取的关联数据来提高地图和定位精度，又能保证全局的收敛性和较高的探索效率．

 

[12,13]------基于地图的定位方法被广泛扩展到SLAM 中.其核心在于机器人获取的局部环境信息与已知地图中的环境信息的搜索和匹配．由于机器人感知能力有限，外界环境又存在大量扰动，另一方面在搜索匹配过程中精度要求的提高又伴随着计算量的指数递增，因此鲁棒而又高效的算法设计一直是定位研究的难题．

 

[13] GUIVANT J，NEBOT E．Optimization of simultaneous localization and map building algorithm for real time implementation[J]．IEEE Trans on Robotic and Automation，2001，17(3)：242—257．

------基于Kalman滤波和Markov推理(包括它的扩展Monte Carlo方法)的各种定位方法可以用于多种场合，同时获得很高的定位精度，并且在噪声环境下可以保持令人满意的鲁棒性，但是由于都是基于大量统计数据的概率模型，其计算复杂度为0(K²~K³)，计算效率低，实时性差，限制了在大型和室外复杂环境中的应用．

 

[14] FO X D，BURGARD W，KRUPPA H，et a1．A probabilistic approach to collaborative multi-robot localization[J]．Autonomous Robots，20OO，8(3)：325—344．

[14,15]------ 针对大规模环境，为了提高作业速度，多机器人的SLAM问题的研究也得到关注. 在多机器人的探索策略方面存在两种思路：一种是完全分布式的，机器人之间共享信息，但独立作出探索决策；另一种策略是分散探索，集中决策和创建地图．

 

[l5] SIMMONS R，APFELBAUM D，BURGARD W，et a1．Coordination for multi-robot exploration and mapping[C]∥Proc of the National Conf on Artificial Intelligence．Austin TX：AAA Press，20OO：852—858．

------

[16] KALMAN R E．A new approach to linear filtering and prediction problems[J]．Tram of the ASME，J of Basic Engineering，1960，82 (Ser．D)：35—45．

[16,17]-----Kalman滤波方法,是多种SLAM算法的基础, 用于同步创建地图和估计机器人的位置

 

[17] MAYBECK P. Stochastic Models, Estimation, and Control [M].New York: Academic Press,1979.

------

[18] SMITH R，SELFM ，CHEESEMAN P．Estimating Uncertain Spatial Relationships in Robotics [M ]．Autonomous Robot Vehicles．Springer-Verlag，1990：167-193．

------多种SLAM算法的基础

 

[19] LIU Y，THRUN S．Results for outdoor-SLAM using sparse extended information  fillers[C]//Proc of the IEEE Int Conf on Robotics＆Automat／on．Taipei：IEEE Press．2003：1227-1233．

------稀疏扩展信息滤波算法. 稀疏扩展信息滤波(SEIF)算法基于Kalman滤波的信息形式，即扩展信息滤波(extended information filter)

 

[20] MONTEMERLO M ，THRUN S．Simultaneous localization and mapping with unknown data association using FastSLAM [C]∥Proc of the IEEE Int Conf on Robotics＆Automation．Taipei：IEEE Press．2003：1985一l991．

------在过去的l0年中，扩展Kalman滤波是解决SLAM问题中使用的最多的方法．但是它有两个明显的缺陷．

1)计算量大．Kalman滤波的协方差矩阵包含l²个元素，复杂度为0(l² )，也就是说，即使只观测到一个路标，整个协方差矩阵都要被更新．如果面对包含数百万个特征的复杂自然环境，其平方复杂性将拖累其实际应用．

2)EKF算法是基于已知观测值和路标之间对应关系这个假设的．这样，一小部分观测值与路标之间的错误关联将导致EKF算法发散．这个观测值与路标之间的关联问题就是所谓的数据关联问题．

 

[20,21]------ FastSLAM算法

 

[21] WANG C,THORPE C,THRUN S，KOILER D，et a1．FASTSLAM 2.0：an improved particle filtering algorithm for simultaneous localization and mapping that provably converges [c]//Proc of the Int Joint Conf on Artificial Intelligence．Acapulco Mexico：AAAI Press，2O03：l15l-l156．

------

[22] WANG C，THORPE C，THRUN S．Online simultaneous localization and mapping with detection and tracking of moving objects：theory and results from a ground vehicle in crowded urban areas[c]∥Proc of the IEEE Int Conf on Robotics＆Automation，Taipei：IEEE Press，2003：842—849．

------SLAM 问题的概率描述相关的符号表示

 

[23] THRUN S，FOX D，BURGARD W ．Monte Carlo localization with mixture proposal distribution[c]∥Proc of她7th National Conf on Artificial Intelligence．Austin，TX：AAAI Press，2000：859—865．

------应用Bayes公式，推出基于机器人运动是Markov过程和周围环境是静态的这两个假设

 

 

[24] DURRANT-WHYTE H，MAJUMDER S.THRUN S．et a1． A Bayesian algorithm for simultaneous localization and map building [C]//Proc of the 10th Int Symposium of Robotics Research．Lome，Australia：Springer-Verlag，2001：49—66．

------

[25]LEONARD J J．FEDER H J S．A computationally efficient method for large-scale concurrent mapping and localization[C]∥ Proc of the 9th Int Symposium on Robotics Research．London：Springer-Verlag，1999：169-176．

------

[26] NEWMAN P．On the structure and solution of the simultaneous localisation and map building problem [D3．University of Sydney，Sydney，Australia：Australian Centre for Field Robotics，2000．

------

[27] DOUCET A，FREIFAS N，MURPHY K，et a1．Rao-Blackwellised particle filtering for dynamic Bayesian networks[C]∥Proc of the16th Conf on Uncertainty in Artificial Intelligence．San Francisco：Morgan Kaufmann，20OO：176— 183．

------ FastSLAM算法使用粒子滤波(Particle filter)估计机器人路径，类似于Monte Carlo定位算法．从运动模型中采样多条路径，每条路径就是一个粒子．数据关联问题对于每个粒子都是单独考虑的，关联问题的影响降低

 

[28] LU F，MILIOS E．Globally consistent range scan alignment for environment mapping[J]．Autonomous Robots，1997，4(4)：333—349．

------

[29] KOUZOUBOV K，AUSTIN D．Hybrid topological／metric approach to SLAM [C]∥Proc of the IEEE Int Conf on Robotics and Automation，New Orleans，LA:IEEE Press，2004：872-877．

------有机地综合其它地图表示方式，将是提高计算效率的有效途径

 

[30] GARCIA M A，SOLANAS A．3D simultaneous localization and modeling from stereo vision[C]∥Proc of the IEEE Int Conf on Robotics and Automation．New Orleans，LA：IEEE Press，2004：847-853．

------目前的应用环境、地图表示和定位算法主要是在2维空间，向3维空间的拓展既是应用的需要也是克服目前2维SLAM 问题的一种有效途径

 

[31] 吴庆祥，BELLD．可移动机器人的马尔可夫自定位算法研究 [J]．自动化学报，2003，29(1)：154—160．(WU Qingxiang，BELL D．A Study on Markov localization for mobile robots[J]．Acta Automatica Sinica，2003，29(1)：154-160．)

------自定位

 

[32] 王卫华，陈卫东，席裕庚．移动机器人地图创建中的不确定传感信息处理[J]．自动化学报，2003，29(2)：267—274．(WANG Weihua，CHEN Weidong，XI Yugeng．Un~ vj sensor

information processing in map building of mobile robot[J]Actu Automatica Sinica，2003，29(2)：267—274．)．

------地图创建