⾃主移动机器⼈同时定位与地图创建（SLAM）⽅法
1.引⾔：
机器⼈的研究越来越多的得到关注和投⼊，随着计算机技术和⼈⼯智能的发展，智能⾃主移动机器⼈成为机器⼈领域的⼀个重要研究⽅向和研究热点。移动机器⼈的定位和地图创建是⾃主移动机器⼈领域的热点研究问题。对于已知环境中的机器⼈⾃主定位和已知机器⼈位置的地图创建已经有了⼀些实⽤的解决⽅法。然⽽在很多环境中机器⼈不能利⽤全局定位系统进⾏定位，⽽且事先获取机器⼈⼯作环境的地图很困难，甚⾄是不可能的。这时机器⼈需要在⾃⾝位置不确定的条件下，在完全未知环境中创建地图，同时利⽤地图进⾏⾃主定位和导航。这就是移动机器⼈的同时定位与地图创建(SLAM) 问题，最先是由SmithSelf 和Cheeseman在1988年提出来的，被认为是实现真正全⾃主移动机器⼈的关键。 SLAM问题可以描述为：机器⼈在未知环境中从⼀个未知位置开始移动，在移动过程中根据位置估计和传感器数据进⾏⾃⾝定位，同时建造增量式地图。在SLAM中，机器⼈利⽤⾃⾝携带的传感器识别未知环境中的特征标志，然后根据机器⼈与特征标志之间的相对位置和⾥程计的读数估计机器⼈和特征标志的全局坐标。这种在线的定位与地图创建需要保持机器⼈与特征标志之间的详细信息。近⼏年来，SLAM的研究取得了很⼤的进展，并已应⽤于各种不同的环境，如：室内环境、⽔下、室外环境。 2.SLAM的关键性问题
2.1地图的表⽰⽅式
⽬前各国研究者已经提出了多种表⽰法，⼤致可分为三类：栅格表⽰、⼏何信息表⽰和拓扑图表⽰，每种⽅法都有⾃⼰的优缺点。
栅格地图表⽰法即将整个环境分为若⼲相同⼤⼩的栅格，对于每个栅格各指出其中是否存在障碍物。这种⽅法最早由Elfes和Moravec提出，⽽后Elfes进⾏了进⼀步的研究。它的优点在于创建和维护容易，尽量的保留了整个环境的各种信息，同时借助于该地图，可以⽅便地进⾏⾃定位和路径规划。缺点在于：当栅格数量增⼤时(在⼤规模环境或对环境划分⽐较详细时)，对地图的维护⾏为将变得困难，同时定位过程中搜索空间很⼤，如果没有较好的简化算法，实现实时应⽤⽐较困难。
智能营销客户管理系统
⼏何信息地图表⽰法是指机器⼈收集对环境的感知信息，从中提取更为抽象的⼏何特征，例如线段或曲线，使⽤这些⼏何信息描述环境。该⽅法更为紧凑，且便于位置估计和⽬标识别。⼏何⽅法利⽤卡尔曼滤波在局部区域内可获得较⾼精度，且计算量⼩，但在⼴域环境中却难以维持精确的坐标信息。但⼏何信息的提取需要对感知信息作额外处理，且需要⼀定数量的感知数据才能得到结果。
拓扑地图抽象度⾼，特别在环境⼤⽽简单时。这种⽅法将环境表⽰为⼀张拓扑意义中的图(graph)，图
中的节点对应于环境中的⼀个特征状态、地点。如果节点间存在直接连接的路径则相当于图中连接节点的弧。其优点是：
(1)有利于进⼀步的路径和任务规划，
(2)存储和搜索空间都⽐较⼩，计算效率⾼，
(3)可以使⽤很多现有成熟、⾼效的搜索和推理算法。
缺点在于对拓扑图的使⽤是建⽴在对拓扑节点的识别匹配基础上的，如当环境中存在两个很相似的地⽅时，拓扑图⽅法将很难确定这是否为同⼀点。
2.2不确定信息的描述
刮膜棒在完全未知环境中由机器⼈依靠其⾃⾝携带的传感器所提供的信息建⽴环境模型是移动机器⼈进⾏⾃主定位和导航的前提之⼀。所谓完全未知环境是指机器⼈对环境⼀⽆所知不存在任何先验信息，如环境形状、障碍物位置、⼈为设定的参照物等。在这种环境下，移动机器⼈必须依赖传感器所获得的信息，如⾥程计、声纳、激光测距仪、视觉等。由于传感器⾃⾝的限制，感知信息存在不同程度的不确定性，例如激光测距仪的不确定性主要来⾃距离的测量误差以及反光镜旋
转和激光散射引起的测量⾓误差。如图1-1所⽰，感知信息的不确定性必然导致所构建的环境模型也不可能是完全精确的，同样，当依靠模型和感知进⾏决策时也带有不确定性，即不确定性具有传递性。
对不确定性进⾏度量的⽅法主要有概率度量、信任度量、可能性度量、模糊度量和证据理论等。⽬前，在AMR地图构建中使⽤较多的是概率度量和模糊度量。概率度量主要存在两种形式：
木纤维袜子(1)以均值、⽅差和协⽅差等概率特征来描述不确定信息。这种度量⽅法的优点是均值等概率特征具有明确的⼏何意义，缺点是概率特征的离散计算公式还没有确定的形式；
(2)以概率模型来描述不确定信息，主要采⽤Bayes法则与Markov假设。这种度量⽅法的优点是以随机
概率模型描述机器⼈的位姿和环境信息，鲁棒性⾮常好，缺点是概率模型的计算量⾮常⼤⽽且必须事先知道模型的先验概率，给实际应⽤造成了困难。
2.3定位与环境特征提取
移动机器⼈⾃定位与环境建模问题是紧密相关的。环境模型的准确性依赖于定位精度，⽽定位的实现⼜离不开环境模型。在未知环境中，机器⼈没有什么参照物，只能依靠⾃⼰并不⼗分准确的传感器来获取外界信息，如同⼀个盲⼈在⼀个陌⽣环境中摸索的情况。这种情况下，定位是⽐较困难的。有地图的定位和有定位的地图创建都是容易解决的，但⽆地图的定位和未解决定位的地图创建如同"鸡--蛋"问题，⽆从下⼿。已有的研究中对这类问题的解决⽅法可分为两类：
1）利⽤⾃⾝携带的多种内部传感器（包括⾥程仪、罗盘、加速度计等），通过多种传感信息的融合减少定位的误差，使⽤的融合算法多为基于卡尔曼滤波的⽅法。这类⽅法由于没有参考外部信息，在长时间的漫游后误差的积累会⽐较⼤。
2）在依靠内部传感器估计⾃⾝运动的同时，使⽤外部传感器（如激光测距仪、视觉等）感知环境，对获得的信息进⾏分析提取环境特征并保存，在下⼀步通过对环境特征的⽐较对⾃⾝位置进⾏校正。但这种⽅法依赖于能够取得环境特征。环境特征提取的⽅法有：
（1） Hough transform是⼀类基于灰度图检测直线和其他曲线的⽅法。该⽅法需要⼀簇能被搜索的预先准备的特定曲线，并根据显⽰的灰度图中⼀簇曲线产⽣曲线参数。
（2） Clustering分析是⼀种数据探测⼯具，对于未分类样例是有效的，同时，它的⽬标就是把所针对对象分组成⾃然类别或基于相似性或距离的簇类。在被提取对象类别未知的情况中，簇技术是⼀类⽐HoughTransform更有效的技术。簇类应是以“凝聚”为中⼼，⽽不是⽀离破碎的、不相交的。⽽环境特征有时是很难提取出的，例如：环境特征不够明显时或者传感器信息⽐较少，难以从⼀次感知信息中获得环境特征。
2.4数据关联
数据关联是对两个特征标志进⾏匹配，确定它们是否对应环境中的同⼀物体。SLAM中的数据关联主要需要完成三个任务：1）新特征标志的检测2）特征标志的匹配3）地图之间的匹配。虽然在⽬标跟踪、传感融合等领域，数据关联已经得到较好的解决，但是这些⽅法的计算量⼤，不能满⾜SLAM的实时性要求。实
现m个标志与拥有n个标志的地图之间的数据关联的复杂度与m之间呈指数关系，假设每个观测到的标志i有个可能的匹配，那么对于m个标志需要在指数空间 =中搜索正确的匹配。数据关联的搜索空间与环境的复杂程度以及机器⼈的定位误差有关，环境的复杂程度的增加会使m增⼤，⽽误差的增⼤会使
Ni 增⼤。
2.5累积误差
SLAM中的误差主要来⾃三个⽅⾯：1）观测误差2）⾥程计的误差3）错误的数据关联带来的误差。当机器⼈在已知地图的环境中进⾏定位时，机器⼈可以通过观测位置已知的特征标志对⾥程计的误差进⾏补偿，每⼀次观测使机器⼈的位置误差趋向于观测误差与特征标志的位置误差之和。然⽽在SLAM中，由于机器⼈的位置和环境中的特征标志的位置都是未知的，观测信息不能有效纠正⾥程计的误差，机器⼈的位置误差随着机器⼈的运动距离⽽增⼤。⽽机器⼈的位置误差的增⼤将导致错误的数据关联，从⽽增⼤特征标志的位置误差：反过来，特征标志的误差⼜将增⼤机器⼈的位置误差。因此，机器⼈的位置误差与特征标志的位置误差密切相关。它们之间的相互影响使机器⼈和特征标志的位置估计产⽣累计误差，难以保证地图的⼀致性。
3.SLAM的实现⽅法
旋转倒立摆⽬前SLAM⽅法⼤致可分为两类：1）基于概率模型的⽅法：基于卡尔曼滤波的完全SLAM、压缩滤波、FastSLAM等2）⾮概率模型⽅法：SM-SLAM、扫描匹配、数据融合(dataassociation)、基于模糊逻辑等。
3.1基于卡尔曼滤波器的实现⽅法
从统计学的观点看，SLAM是⼀个滤波问题，也就是根据系统的初始状态和从0到t时刻的观测信息与控制信息（⾥程计的读数）估计系统的当前状态。在SLAM 中，系统的状态 = ，由机器⼈的位姿r和地图信息m组成（包含各特征标志的位置信息）。假设系统的运动模型和观测模型是带⾼斯噪声的线性模型，系统的状态服从⾼斯分布，那SLAM可以采⽤卡尔曼滤波器来实现。基于卡尔曼滤波器的SLAM 包括系统状态预测和更新两步，同时还需要进⾏地图信息的管理，如：新特征标志的加⼊与特征标志的删除等。
卡尔曼滤波器假设系统是线性系统，但是实际中机器⼈的运动模型与观测模型是⾮线性的。因此通常采⽤扩展卡尔曼滤波器（Extended Kalman Filter），扩展卡尔曼滤波器通过⼀阶泰勒展开来近似表⽰⾮线性模型。另⼀种适⽤于⾮线性模型的卡尔曼滤波器是UKF（Unscented Kalman Filter），UKF采⽤条件⾼斯分布来近似后验概率分布，与EKF相⽐，UKF的线性化精度更⾼，⽽且不需要计算雅可⽐矩阵。
卡尔曼滤波器已经成为实现SLAM的基本⽅法。其协⽅差矩阵包含了机器⼈的位置和地图的不确定信息。当机器⼈连续地观测环境中的特征标志时，协⽅差矩阵的任何⼦矩阵的⾏列式呈单调递减。从理论上讲，当观测次数趋向于⽆穷时，每个特征标志的协⽅差只与机器⼈起始位置的协⽅差有关。卡尔曼滤波器的时间复杂度是O( )，由于每⼀时刻机器⼈只能观测到少数的⼏个特征标志，基于卡尔曼滤波器的SLAM的时间复杂度可以优化为O()，n表⽰地图中的特征标志数。
3.2局部⼦地图法
局部⼦地图法从空间的⾓度将SLAM分解为⼀些较⼩的⼦问题。⼦地图法中主要需要考虑以下⼏个问题：1）如何划分⼦地图2）如何表⽰⼦地图间的相互关系3）如何将⼦地图的信息传递给全局地图以及能否保证全局地图的⼀致性。汽车水箱除垢剂
最简单局部⼦地图⽅法是不考虑各⼦地图之间的相互关系，将全局地图划分为包括固定特征标志数的独⽴⼦地图，在各⼦地图中分别实现SLAM，这种⽅法的时间复杂度为O(1)。但是，由于丢失了表⽰不同⼦地图之间相关关系的有⽤信息，这种⽅法不能保证地图的全局⼀致性。
sim卡托
对此，Leonard 等⼈提出了DSM（DecoupledStochastic Mapping）⽅法，DSM中各⼦地图分别保存⾃⼰的机器⼈位置估计，当机器⼈从⼀个⼦地图A进⼊另⼀个⼦地图B时，采⽤基于EKF的⽅法来将⼦地图A中的信息传送给⼦地图B；B.Williams等⼈提出了⼀种基于CLSF（ConstrainedLocal Submap Filter）的SLAM ⽅法，CLSF在地图中创建全局坐标已知的⼦地图，机器⼈前进过程中只利⽤观测信息更新机器⼈和局部⼦地图中的特征标志的位置，并且按⼀定的时间间隔把局部⼦地图信息传送给全局地图。虽然实验表明这两种算法具有很好的性能，但是没有从理论上证明它们能够保持地图的⼀致性。J.Guivant等⼈提出了⼀种没有任何信息丢失的SLAM优化算法CEKF(CompressedExtended Kalman Filter)。CEKF将已经观测到的特征标志分为A与B部分，A表⽰与机器⼈当前位置相邻的区域，
被称为活动⼦地图。当机器⼈在活动⼦地图A中运动时，利⽤观测信息实时更新机器⼈的位置与⼦地图A，并采⽤递归的⽅法记录观测信息对⼦地图B的影响；当机器⼈离开活动⼦地图A时，将观测信息⽆损失地传送给⼦地图B，⼀次性地实现⼦地图B的更新，同时创建新的活动⼦地图。该⽅法的计算时间由两部分组成：活动⼦地图中的SLAM，其时间复杂度为O( )，是活动⼦地图A中特征标志的数⽬；⼦地图B的更新，其时间复杂度为O( ) ，是地图B中特征标志的数⽬。当⼦地图合并的时间间隔较⼤时，CEKF能有效减少SLAM的计算量。
3.3去相关法
降低SLAM复杂度的另⼀种⽅法是将表⽰相关关系的协⽅差矩阵中⼀些取值较⼩的元素忽略掉，使其变为⼀个稀疏矩阵。然⽽这也会因信息的丢失⽽使地图失去⼀致性。但是，如果能改变协⽅差矩阵的表⽰⽅式，使其中的很多的元素接近于零或等于零，那么就可以将其安全地忽略了。基于扩展信息滤波器
EIF（ExtendedInformation Filter）的SLAM就是出于这⼀思想。EIF EKF的基于信息的表达形式，它们的区别在于表⽰信息的形式不⼀样。EIF采⽤协⽅差矩阵的逆矩阵来表征SLAM中的不确定信息，并称之为信息矩阵。两个不相关的信息矩阵的融合可以简单地表⽰为两个矩阵相加。信息矩阵中每个⾮对⾓线上的元素表⽰机器⼈与特征标志之间或特征标志与特征标志之间的⼀种约束关系，这些约束关
系可以通过系统状态的信关系进⾏局部更新。这种局部更新使得信息矩阵近似于稀疏矩阵，对其进⾏稀疏化产⽣的误差很⼩。根据这⼀点，S.Thrun等⼈提出了⼀种基于稀疏信息滤波器SEIF(Sparse Extended InformationFilter)的SLAM ⽅法，并证明利⽤稀疏的信息矩阵实现SLAM的时间复杂度是O(1)。虽然EIF可以有效降低SLAM的时间复杂度，但是在地图信息的表⽰和管理⽅⾯还存在⼀些问题。⾸先，在常数时间内只能近似算得系统状态的均值；其次，在基于EIF 的SLAM ⽅法中，特征标志的增删不⽅便。
3.4分解法（FastSLAM）
M.Montemerlo 等⼈提出了⼀种基于粒⼦滤波器(ParticleFilter) FastSLAM ⽅法。FastSLAM 将SLAM分解为机器⼈定位和特征标志的位置估计两个过程。粒⼦滤波器中的每个粒⼦代表机器⼈的⼀条可能运动路径，利⽤观测信息计算每个粒⼦的权重，以评价每条路径的好坏。对于每个粒⼦来说，机器⼈的运动路径是确定的，因此特征标志之间相互独⽴，特征标志的观测信息只与机器⼈的位姿有关，每个粒⼦可以采⽤n个卡尔曼滤波器分别估计地图中n个特征的位置。假设需要k个粒⼦实现SLAM、FastSLAM，总共有kn个卡尔曼滤波器。FastSLAM的时间复杂度为O(kn)，通过利⽤树型的数据结构进⾏优化，其时间复杂度可以达到O(klog n)。Fast2SLAM⽅法的另⼀个主要优点是通过采⽤粒⼦滤波器估计机器⼈的位姿，可以很好地表⽰机器⼈的⾮线性、⾮⾼斯运动模型。
3.5基于多机器⼈协作的SLAM
⼀些研究者对基于多机器⼈协作的同时定位与地图创建CSLAM（CooperativeSimultaneous Localizationand Mapping）进⾏了探讨和研究。与单机器⼈相⽐，通过机器⼈之间的相互协调与合作以及信息共享，CSLAM可以提⾼地图创建的效率和提⾼定位与地图的精度。CSLAM按照地图的存储与处理⽅式的不同可以分为两⼤类型：集中式CSLAM和分布式CSLAM。在集中式CSLAM中，存在⼀个中央处理模块，每个机器⼈分别在⾃⼰所在的局部地图中进⾏定位与地图创建，然后利⽤⽆线通信装置将在局部地图中获得的信息传送给中央模块。这种⽅法通过⼦地图的匹配，可以充分利⽤⼦地图间的冗余信息提⾼定位与地图创建的精度。但是，当机器⼈数量增加时中央模块的计算量会显著增⼤，⽽且集中式的信息传递需要很⼤的带宽；系统的可靠性也⽐较低，⼀旦中央模块出现故障，整个系统都会陷⼊瘫痪状态。在分布式CSLAM中，不存在中央模块，每个机器⼈都拥有⾃⼰的全局地图，在每⼀时刻机器⼈把来⾃其他相邻机器⼈的信息和⾃⼰的观测信息融合到⾃⼰的全局地图中，然后以点对点的⽅式将新的信息传送给其他机器⼈。每个机器⼈只能获得与其相邻的机器⼈的位置信息，不知道整个系统的拓扑结构。这种⽅法与分布式的信息融合⼗分相似，可以利⽤信息滤波器来实现。由于两个不相关信息矩阵的信息融合可以通过两个矩阵的相加⽽实现，所以利⽤信息滤波器实现分布式CSLAM可以避免复杂的计算。
4.研究⽅向与发展趋势
综上所述，近⼏年来机器⼈领域的研究者对SLAM进⾏了⼤量的研究，特别是在降低计算复杂度、提
⾼鲁棒性等⽅⾯取得了很⼤的进展。随着研究的深⼊，以下的⼏⽅⾯成为了当前SLAM的研究热点⽅向。
1. 扩展SLAM的应⽤环境：将⽬前局限⼆维静态环境中的研究与应⽤扩展到与现实中的环境切合的动态的三维环境；
2. 深⼊研究基于多机器⼈协作的SLAM，提⾼其应⽤⽔平；
3. 研究更有效的SLAM实现⽅法，将⼈⼯智能、智能控制等领域的⽅法引⼊到SLAM中，开发更有效的SLAM算法.；
4. 研究更好的地图表达⽅式，特别是复杂地形和⼤环境中的地图表达⽅式；
5. 研究更好的将视觉处理与其他传感器结合，提⾼环境特征提取的精度，减少误差，提⾼定位和构图的精确性。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议