SLAM导航常用概念及技术

ref：基于激光 SLAM 的无人驾驶扫地机三维地图构建与路径规划研究

d531aca40016d4a4660afe975befeb6f.png

移动机器人位姿估计：

1. 即时定位与地图构建：机器人在未知环境地图的情况下同时完成位姿估计和地图构建；
2. 利用先验地图和传感器信息(如里程计、雷达、摄像机、IMU 等)进行位姿定位；
3. 不需要地图构建即可进行机器人定位，如 GPS 定位，用于户外移动机器人的定位跟踪。

SLAM算法

• FastSLAM：一种基于粒子滤波的 SLAM 方法，利用了 RB定理来有效分解定位和地图构建问题；
• Cartographer：通过优化方法将雷达扫描数据和局部地图进行扫描匹配，以获得最佳位姿，采用分枝定界加速技术实现快速的扫描匹配和回环检测，进而构建优化问题，对机器人的所有位姿和路标点信息进行精细调整，通过建立一个图模型来描述机器人在不同时间点的位姿及其间的约束关系。
• CNN-SLAM： 利用卷积神经网络(CNN)对深度信息进行估计，从而增强传统 SLAM 系统的深度感知能力；
• ORB-SLAM2：通过将SLAM与深度学习特征提取器结合，以改进其性能，特别是在特征匮乏或重复的场景中;
• LSD-SLAM: 一种基于直接法的 SLAM 算法，通过深度学习方法增强，例如使用 CNN 改善其深度估计的精度和鲁棒性；
• DeepSLAM：提出了一个深度学习框架，用于从头开始学习 SLAM 系统的全部组件，包括特征提取、匹配、位姿估计等；
• Neural-SLAM:利用神经网络来学习环境的表示，以及如何在此环境中进行有效的探索和地图构建；
• LOAM： 利用激光雷达的高精度进行实时定位和地图搭建，通过集成激光雷达和 IMU 数据，系统的鲁棒性和精确性可以得到进一步的提升
• FAST-LIO：一种快速的激光与惯性融合的定位与地图构建系统，高效率和低延迟，适合用于需要快速响应的应用场景；
• SuMa 算法：利用激光雷达的表面元(Surfel)表示进行高效的 3D 地图构建，通过将激光数据与其他传感器，如 IMU 和 GPS 数据融合，能够在自动驾驶场景下提供准确的定位和地图信息
• HDL-Graph SLAM：采用距离阈值法回环检测，在构建过程中逐帧参与回环检测可能导致不必要的计算资源及内存浪费

SLAM前端优化

• 点云降采样：计算一个能够刚好包裹点云数据的体素，然后根据分辨率将大体素分割成数个大小相同的小体素。计算小体素内点的质心，以质心的坐标近似体素内的点，从而完成对点云的下采样；
• 滤除离群点云：计算每个点到其邻近点的平均距离，根据这个平均距离的全局分布（假设数据点之间的距离遵循高斯分布)，确定分布的均值和标准差来定义一个标准，然后根据这个标准修剪掉那些超出这个范围的离群点。
• LiDAR 里程计帧间匹配：将当前帧的激光点云与关键帧的激光点云进行匹配得到相对位姿，再将历史的相对位姿进行拼接融合得到全局特征子地图和全局的里程计位姿。
• 点云配准：将在不同传感器坐标系下测量得到的点云数据进行坐标变换，从而得到整体的一致性数据模型，伴随有两个坐标系的变换关系(估计合适的坐标变换矩阵 R 和平移向量 T)，使测量的三维点云经坐标变换后在不同视角下所能达到的最小距离。

SLAM后端优化

• 韩超：利用曲率计算点云中特征点的特征向量，通过特征向量与中心点坐标系的角度分布和尺度分布关系，构建点云全局特征描述子
• OverlapNet神经网络模型：使用两帧点云的重合率来代替距离检测回环，以此消除漂移误差的影响
• OverlapTransformer：采用 yaw 角旋转不变的结构创建地点描述子向量，提高自动驾驶车辆多角度地点识别的准确率
• LCDNet：通过网络提取的点云特征，将其转化为回环检测的描述子，用来估计两个点云间的相对位姿
• SC(Scan Context)：通过统计点云的z 方向最大值来形成描述子，但体量较轻，容易形成虚假的闭环
• SC++：基于笛卡尔坐标系和极坐标系的两种描述子计算方式，但该方法在实际的系统上运行时不容易做到两种描述子的切换
• ISC(Intensity Scan Context)：与 SC 相同，把高度信息换成了点云强度信息
• Iris：利用高度信息，形成二进制的描述子，但随着时间 的增长，该方法的回环搜索速度会大幅下降
• 刘如飞：一种利用地理实体目标特征的点云配准方法来提高建图效果

路径规划

全局路径规划适合已知的环境地图，指导机器人到达目标点；局部路径规划在机器人接近目标或环境发生变化或环境地图未知时，实时更新周围环境信息，完成避障功能以适应动态环境。

• 基于搜索的路径规划方法是在预定义的环境中，通过探索从起点到终点之间的所有可能路径来寻找最优路径或满足某些特定条件的路径的一种策略，法依赖于对环境的数学建模以及高效的搜索算法来预测和评估路径，包括无信息搜索（广度优先搜索(BFS)和深度优先搜索(DFS)）和启发式搜索（Dijkstra算法和 A*算法）。无信息搜索不利用关于目标位置的任何信息，仅依靠搜索过程中遍历的节点来找到路径；启发式搜索使用启发式函数来估计从当前状态到目标状态的距离，以指导搜索过程，要求状态空间可枚举，需要将连续状态空间离散化成有限数量的离散状态，常见的离散化方法有网格化、状态量化、采样方法、图构建、特征间离散化、动态离散化等，选择离散化方法取决于具体问题的特点、状态空间的维度、计算资源的限制以及对解决方案质量的需求。
• 基于采样的路径规划算法适用于解决高维空间和复杂约束条件下的路径规划问题，通过在机器人的配置空间(所有可能的状态空间)中进行随机采样，生成一系列可能的状态点，然后通过连接这些点来探索从起始点到目标点的路径。这类算法主要包括概率路图(PRM)和快速随机采样树(RRT)及其变体，PRM 算法通过在整个配置空间随机采样，生成一组节点，然后尝试将这些节点相连，构建一个图，最后在图上搜索从起点到终点的路径，适合静态环境下的稳定的环境布局中路径规划问题；RRT 算法以其树形结构的构建方式，通过随机采样和目标向导的策略，有效地实现了路径的逐步构建，适合于动态或未知环境的快速路径规划。
• 人工势场法的核心思想是通过模拟物理世界中的势场来引导机器人从起点移动到终点，同时避开障碍物，把目标点视为吸引力源，把障碍物视为斥力源，机器人在这些力的作用下沿着势能最低的路径移动，从而达到规避障碍的目的。
• 集群优化算法如遗传算法、蚁群算法、粒子群算法和模拟退火算法，通过模拟种群的演化过程，遗传算法利用基因、染色体的概念来找到最佳路径，但可能陷入局部最优解。蚁群算法可以通过模拟传播蚂蚁信息素来求得最佳答案。粒子群算法是利用个人间的信息共享，从而演化出最优化的解决方法。模拟退火算法则借鉴了物体退火过程中的能量减少原理来搜索最优解，但对初始状态较为敏感。

全覆盖路径规划

全覆盖路径规划技术是在确保覆盖特定区域内所有可能位置的同时，在最小程度上实现重复覆盖和未覆盖区域的技术，目标是设计出一条有效的路径，使得设备能够经过区域内的每一个点至少一次，同时又要尽可能地减少路径的总长度和时间，主要分为离线式和在线式两种：离线式是环境地图已知的情况下进行路径规划，而在线式路径规划则利用机器人携带的传感器同时建图与规划路线。

• 离线式路径规划的典型算法包括 Boustrophedon 技术和基于内螺旋的全覆盖路径规划技术，内螺旋全覆盖路径规划算法的基本思想是从给定区域的边界开始，逐渐向内部移动，形成一个螺旋状的路径，通过系统地缩减覆盖的外边界，直至覆盖整个区域，同时尽量减少路径的重复和交叉。
• 在线式全覆盖路径规划包括基于单元分解的方法（将大型或复杂形状的区域细分，然后独立地为每个子区域规划路径，最终将这些路径组合成一个完整的覆盖路径）、梯形分解法（早期的算法）、牛耕分解法（在梯形分解法基础上合并了部分子单元，降低规划的复杂度）、线扫分割法（根据路径转弯次数选择最优的切割方向）等。

33dea71cae534d47d90487a44ca4eb14.png

定位：

• 定位失败：在机器人导航系统中是一个复杂的问题，其原因并不仅仅局限于定位评估本身的失败，传感器所固有的高噪声水平以及初始全球定位粒子的高度分散性也是导致平均测量概率低下的重要因素。
• 局部定位：在已知初始位姿的情况下进行的定位，依赖于计算过程来减少由于运动引起的噪声影响，不确定性大多数情况下围绕真实位姿附近，因此采用单峰分布方法描述位姿的不确定性；
• 全局定位：问题出现在初始位姿未知的情况下，不再适合用单峰分布来形容这个位置的不确定性，因为可能会出现多个位置；
• 绑架机器人：是全局定位问题的一个特例，这种情况发生在机器人被瞬间移动到一个新的、未知的位置时，而机器人可能还错误地认为自己处在移动前的位置。这一问题特别用于测试定位算法在面对极端情况下的自我恢复能力，成为评价一个定位算法在遭遇定位失效后恢复能力的重要标准。
• 蒙特卡罗定位算法(MCL)：通过实验的方法求解某种事件出现概率的问题，基于粒子滤波算法实现，在地图环境已知时，所有粒子按照机器人的运动模型移动，根据传感器的读数决定概率，使更多的粒子向概率高的方向移动。
• 自适应蒙特卡罗定位算法(AMCL)：结合增强的蒙特卡洛定位技术和库尔贝克-莱布勒散度采样，通过向粒子集中添加随机粒子，并合理的权重分配，保证新加入的随机粒子不会影响定位的准确性，有效解决了传统MCL固定样本集和绑架机器人定位失败带来的问题