基于2D激光雷达的SLAM算法研究综述

沈斯杰，田 昕，魏国亮，袁千贺

(1.上海理工大学 光电信息与计算机工程学院，上海 200093；2.上海理工大学 理学院，上海 200093)

0 引 言

随着人口老龄化日益严重和用人成本的上升，移动机器人在生活中出现的频率越来越高，如高端酒店中的迎宾机器人、疫情期间医院中的消毒机器人和抢险救灾的救援机器人等。在移动机器人众多应用场景中，周围环境不是一成不变的，有时候甚至是未知的。作为移动机器人在未知环境下实现自主导航的关键技术，SLAM因此显得尤为重要。

SLAM可以分为两大类：基于相机的视觉SLAM和基于激光雷达的SLAM。视觉SLAM对光的依赖度高，在暗处或无纹理区域运行效果较差，而激光SLAM可以在较差的光照条件下运行，并且配合其他传感器可以直接生成用于机器人导航的环境地图。

激光SLAM按适用空间可以分为2D激光SLAM和3D激光SLAM。2D激光SLAM是在二维平面内使用的SLAM方法，通过激光传感器获取机器人三个自由度的位姿信息及机器人所处的二维地图。同理，3D激光SLAM是在三维空间中使用的SLAM方法，它可以得到六个自由度的位姿信息及三维地图。由于2D激光雷达在成本方面要低于3D激光雷达，并且在室内环境下，2D激光SLAM的建图精度满足使用需求，所以在移动机器人领域得到了广泛的应用。因此，该文重点阐述了激光雷达的测距原理和2D激光SLAM的系统框架，并对主流的2D激光SLAM算法进行分析和比较。最后展望未来激光SLAM的发展方向。

1 激光雷达的测距方法

激光雷达作为移动机器人感知周围环境信息的主要工具之一，在机器人避障中起着十分重要的作用。目前，激光雷达主流的测距方法可以分为三角法与飞行时间法(time of flight)。

1.1 三角法

激光以一定的角度射向被测物体，反射光以一定的角度反射回光源旁的接收器，因为激光器和接收器间隔一段距离，所以不同距离的被测物体在接收器上的成像会在不同的位置。通过三角公式就可以计算出被测物体的距离，三角测距原理如图1所示。

图1 三角测距原理

1.2 飞行时间法

激光器发射一个激光脉冲，通过激光雷达中的计时器记录下发射的时间，反射光由接收器接收，通过计时器得到接收的时间。飞行时间通过接收时间与发射时间相减得到。由于光速已知，因此就可以计算出被测物体的距离，飞行时间测距原理如图2所示。

图2 飞行时间测距原理

从测量距离、测量精度、抗强光能力和成本四个方面对三角法与飞行时间法进行比较，如表1所示。

表1 三角法与飞行时间法比较

2 2D激光SLAM的系统框架

2D激光SLAM的系统框架主要可以分为：前端扫描匹配、后端优化、回环检测和地图构建。其中，回环检测不是必须存在的环节。前端扫描匹配是通过读取相邻两帧激光传感器扫描信息之间的关系来估计自身的位姿。后端优化是用来减少扫描匹配后产生的累积误差，并利用地图构建模块生成环境地图信息。回环检测则是通过检测当前位置的估计值和历史位置的估计值是否相同，来消除累积误差，从而减少地图漂移的现象。

2.1 前端扫描匹配

前端扫描匹配是实现同时定位与建图的基础。它可以分为：基于点的扫描匹配、基于特征的扫描匹配、基于数学特性的扫描匹配、基于相关性的扫描匹配和基于优化方法的扫描匹配。

2.1.1 基于点的扫描匹配

基于点的扫描匹配可以认为是对前后两帧激光点集进行匹配。其中，迭代最近点(ICP)的变种算法——PLICP(point-to-line ICP)，由于其原理简单、易于实现被广泛使用。PLICP与经典ICP相比，通过将点与点之间的距离改变成点到线之间的距离，从而加快求取闭合解的速度以及提高匹配精度。

2.1.2 基于特征的扫描匹配

基于特征的扫描匹配方法，其思想就是从激光扫描信息中提取点、线、面等元素进行匹配。Zhao等人从扫描数据中提取隐函数作为特征，在具有闭合图形的场合下，具有优异的效果。针对传统的平面扫描匹配方法缺乏足够的边缘和角点特征，Zhao等人提出基于二次曲线特征的匹配方法。

2.1.3 基于数学特性的扫描匹配

此类算法的核心是通过各种数学特性来描述帧与帧之间的位姿变化。正态分布变换(NDT)是基于数学特性的匹配算法中最为典型的。该算法将当前帧扫描到的2D平面离散为栅格，根据每个栅格上点的分布，计算出该栅格的概率密度函数。通过牛顿的优化方法求解出概率密度之和最大的变换参数，从而达到最优匹配结果。

2.1.4 基于相关性的扫描匹配

相关性扫描匹配由Olson提出，首先构造似然场模型，然后在指定的搜索空间内进行搜索，计算每个位姿的得分，最后根据位姿得分，计算本轮位姿匹配的方差。由于该方法使用暴力搜索，因此需要较长的匹配时间。不过，该方法可以结合分枝定界策略加速匹配。

2.1.5 基于优化方法的扫描匹配

将扫描匹配问题转换为非线性最小二乘问题，通过梯度下降的方式来求解，因此需要选择合适的初始位置，否则容易陷入局部极值。

目前，在2D激光SLAM中，相关性扫描匹配结合梯度优化是最主流的前端扫描匹配方法。

2.2 后端优化

SLAM中的后端优化环节主要是减少扫描匹配所产生的累积误差。目前，可以分为两大类：基于贝叶斯滤波的后端优化方法和基于图优化的后端优化方法。

2.2.1 基于贝叶斯滤波器的后端优化

基于贝叶斯滤波的SLAM方法都是在马尔可夫假设的前提下进行的，即当前时刻机器人的状态只与当前时刻的测量值和上一时刻的状态相关，与其他时刻的无关。根据后验概率表示方法的不同，可以分为卡尔曼滤波和粒子滤波。滤波类方法最大的缺点就是无法建立大尺度地图，因为一旦当前时刻的估计出现偏差，偏差就无法消除，从而导致所建立的地图有错位的情况。

2.2.2 基于图优化的后端优化

基于图优化的SLAM方法则没有马尔可夫假设，当前时刻机器人的状态与之前所有的测量值都相关，图优化的系统框架如图3所示。所谓图优化，就是将图论的思想引入到SLAM的问题中。它将机器人的位姿表示成一个节点，相邻节点之间的弧表示空间约束关系，以此构成的图就是位姿图。通过调整位姿图中的节点以最大程度满足空间约束关系，从而获得机器人的位姿信息和地图。

图3 图优化的系统框架

2.3 回环检测

回环检测是指机器人通过传感器测量的数据检测到自己又回到之前来过的位置。这里可以借助控制科学中经典的反馈控制理论，来理解闭环检测在SLAM中的作用，消除累积误差，从而改善建图效果。

2.3.1 帧与帧(scan-to-scan)的回环检测

Scan-to-scan是利用Olson所提出的相关性扫描匹配，将两帧激光雷达数据通过相对平移和旋转角度进行匹配，从而达到回环检测的目的。然而，因为单帧激光数据包含的信息量太少，容易出现匹配失败的情况。

2.3.2 帧与子图(scan-to-map)的回环检测

将当前帧的激光雷达数据与子图进行匹配，该子图由一段时间内连续的激光数据帧构成。其中最具代表性的是于2016年google提出的cartographer算法，通过scan-to-map的回环检测方法，减少连续多帧激光雷达数据之间的冗余性，提高回环的效率。

2.3.3 子图与子图(map-to-map)的回环检测

Map-to-map就是将当前连续时间内的激光数据帧构建成子图，与之前生成的子图进行匹配，从而改善单帧激光数据所含信息量少的问题。文国成所提出的map-to-map的回环检测方法，使用定位筛选和压缩表对回环候选集进行优化，在构建大尺度地图时，可以加快回环速度，降低回环出错的可能性。

2.3.4 特殊的回环检测

Olson提出一种基于多分辨率扫描匹配的方法，将当前激光数据帧和多分辨率地图进行匹配。该方法即使在位置不确定的场合下，也能通过枚举法找到最佳匹配。Yin等人提出一种基于孪生神经网络的激光雷达点云半手工表示学习方法，在此基础上，进一步建立KD树，加速回环检测。

目前，在2D激光SLAM 领域中，使用最多的回环检测方法是帧与子图之间的匹配，利用分枝定界法加速回环并且通过延时决策(lazy decision)降低回环出错的可能性。

2.4 地图构建

SLAM所构建的地图是移动机器人实现自主导航与定位的前提与基础。地图可以分为：尺度地图、拓扑地图和语义地图。在2D激光SLAM中，主要针对尺度地图中的栅格地图和特征地图进行研究。

2.4.1 栅格地图

栅格地图是尺度地图中最为常用的一种。栅格地图是指将环境空间划分成一个个大小相等的栅格单元，每个栅格单元中含有被障碍物占据的概率值。如果栅格被占用，则概率值越接近于1。当栅格中不含物体时，则概率值越接近于0。若不确定栅格中是否有物体，则概率值等于0.5。栅格地图具有高准确性并且能够充分反映出环境的结构特征，因此栅格地图可以直接用于移动机器人的自主导航与定位。

2.4.2 特征地图

特征地图又称为几何地图，一般由环境信息中提取到的点、线或圆弧等几何特征构成。当构建小场景地图时，特征地图占用的资源较少且建图精度尚可；当构建环境较大的地图时，由于特征地图无法有效表现出真实环境中的详细信息，其建图精度会大打折扣，因此不适用于大场景建图。

3 主流的2D激光SLAM算法

主流的2D激光SLAM可以分为：基于贝叶斯滤波、基于图优化和基于高斯牛顿优化的激光SLAM。

3.1 基于贝叶斯滤波的激光SLAM

扩展卡尔曼滤波(EKF)被用来解决SLAM问题最早可追溯到1987年，通过联合状态向量来同时表示机器人的位姿和路标所处的位置。虽然EKF SLAM开创了将概率统计运用于SLAM上的先河，但是此方法存在着一些问题，如所占用的计算资源较大、算法稳定性较差和所建立的特征地图无法直接用于机器人的自主导航等。

基于粒子滤波器的激光SLAM方法对上述问题进行改善。2003年，Montemerlo等人提出Fast SLAM1.0算法，将SLAM问题分解成机器人位姿的估计和位置路标的估计，分别使用粒子滤波器和卡尔曼滤波器求解。但是粒子滤波器存在粒子退化的问题，为此Fast SLAM2.0算法提出一种求取重要性函数的方法。为了继续优化Fast SLAM，Gmapping于2007年被提出，它通过改进提议分布和选择性重采样，进一步改善粒子退化的情况，建图效果如图4所示。

图4 Gmapping算法

由于每个粒子都携带机器人的轨迹和对应的环境地图，所以占用的计算资源较大。2010年提出的Core SLAM，是一种只有200行代码的轻量化SLAM方法，因此性能损耗较小。

不管是基于卡尔曼滤波器还是粒子滤波器的SLAM算法，由于缺少回环检测，因此在构建大尺度地图时无法取得理想的效果。

3.2 基于图优化的激光SLAM

图优化的思想在SLAM中的使用最早可追溯到1997年，其通过最小二乘法来解决前端匹配所产生的累积误差。由于没有考虑到矩阵稀疏性，当时采用矩阵求逆的方法来求解，只能离线使用，无法满足实时构建地图的需求。1999年，Gutmann等人提出与当前相似的图优化框架，但仍忽视矩阵稀疏性。千禧年以后，随着研究者们的深入探索，SLAM中的矩阵稀疏性得以发现，使得高效求解成为可能。正是站在巨人的肩膀上，在2010年，Konolige等人提出Karto SLAM算法。这是首个基于图优化的开源算法，利用高度优化和非迭代平方根法分解从而进行稀疏化解耦求解，建图效果如图5所示。但是该算法依然有不足之处，在回环检测部分，需要预先构建局部子图。

图5 Karto算法

一般的图优化方法都需要初始假设，即起始点经过多次迭代后得到局部代价函数的最小值。然而在2011年，Carlone等人提出一种近似线性化的图优化SLAM方法。2016年，Google团队开源了Cartographer算法，通过相关性扫描匹配结合梯度优化完成前端匹配，利用分枝定界法加速回环检测以及结合延时决策(lazy decision)降低回环出错的可能性，建图效果如图6所示。2020年，Li等人利用高斯过程(Gaussian process，GP)回归，提出了一种基于区域化GP地图重建算法的新型地图表示方法。该方法可以采用简洁的数学方法完成位姿估计和地图更新。

图6 Cartographer算法

3.3 基于高斯牛顿优化的激光SLAM

2011年，Kohlbrecher等人提出Hector SLAM算法，该算法无后端优化部分且不需要借助额外的传感器，所以需要高更新频率且测量噪声小的激光雷达。Hector SLAM将当前帧的激光雷达数据与子图进行匹配，通过高斯牛顿法进行位姿优化。为了避免陷入局部最优解，求得全局最优解，Hector SLAM采取多分辨率地图的策略。此算法在旋转过快时，建图易发生漂移，建图效果如图7所示。

图7 Hector算法

目前，主流的激光SLAM算法的优缺点分析如表2所示。

表2 激光SLAM算法的优缺点分析

4 激光SLAM的发展趋势

激光SLAM的系统框架已经成熟，但是仍有很多工程应用问题有待解决，目前的发展趋势有以下三种：

(1)多传感器融合。

在复杂环境下，多传感器融合是一种必然的趋势。李陆君等人提出将二维激光雷达与深度相机融合，从而提高传感器的抗干扰能力、探测范围和建图精度。陈志键等人针对室内定位中UWB存在非视距的影响以及激光雷达有误差累积问题，将UWB绝对定位技术和激光雷达相对定位技术相融合，提高定位准确度。

(2)与深度学习的结合。

近些年，深度学习得到蓬勃的发展和广泛的关注度。深度学习在特征提取和特征学习方面性能突出，不少研究者在SLAM中引入深度学习改善前端匹配与回环检测的性能。Wang等人将深度学习用于激光里程计系统，提高预测位姿的鲁棒性与准确度。邹勤提出一种基于深度学习的激光SLAM回环检测方法，将SLAM回环检测的问题转化为SLAM数据样本的检索问题。

(3)优化激光SLAM算法。

为了推动移动机器人在日常生活中的普及，需要进一步提升SLAM算法的稳定性和实时性，降低硬件成本。刘哲铭通过速度估计补偿法和里程计插值模型去除激光雷达中的运动畸变，提升前端扫描匹配的精确度。Zhang等人提出一种新颖的序列数据处理流程，该方法有效减少了建图漂移现象，提升了系统的鲁棒性。Pang等人通过对激光扫描数据进行分割，提取出特殊的边缘或角点特征，使其在低成本的设备下可以保持较高的建图精度。

5 结束语

文中主要对2D激光SLAM的系统框架和发展现状进行了概述，总结分析了主流2D激光SLAM算法，不难发现，基于图优化的激光SLAM将是未来的主流。若要进一步提高SLAM算法的实时性、鲁棒性和准确性，结合多传感器融合与深度学习技术符合当下的发展趋势。

移动机器人是人工智能的重要载体，而激光SLAM是机器人学中的关键技术，是实现机器人自主探索的基石。现如今激光SLAM技术的建图精度和硬件成本仍呈正比关系，相信在未来，随着激光SLAM技术的深入发展和硬件成本的降低，会出现低成本高精度的激光SLAM技术。到那时，越来越多的移动机器人会出现在人们的视野中，便利你我的生活。