《自主移动机器人 》课件 第5章 地图表示与构建

第五章

移动机器人的地图表示与构建熊蓉浙江大学控制科学与工程学院5.1概述地图地图是环境知识的一种表达方式，是移动机器人定位导航的基础根据地图中所记录障碍物位置，规划机器人从当前点到目标点的可行路径通过实时感知和地图信息的匹配，定位移动机器人在环境中的位置地图表示方法需要有效表示空间环境帮助机器人完成特定的任务容易加入新的信息更新地图便于计算机进行信息处理地图表示方法直接影响定位和导航方法可行性、高效性、精确性地图表示方法与传感器地图表示方法受传感器能够获得的数据类型影响常用传感器5.2常用环境感知传感器测距传感器ToF原理三角测距法二维激光传感器可测量某一平面上障碍物边缘点到传感器的距离和角度信息可测距离远、范围大，测量精度高随着距离增大，相邻点分布稀疏三维激光传感器一定俯仰角360度范围内障碍物边缘点到传感器的距离和角度信息可测距离远范围大，测量精度高，随着距离增大，相邻点分布稀疏相机信息丰富，价格便宜单目缺失深度信息，受光照、季节、气候等影响，数据量大RGBD传感器同时获得RGB图像信息和深度信息测量范围近，测量误差大，容易受物体表面影响，基本不能用于室外5.4地图表示方法常用地图表示方法点云地图栅格地图特征地图拓扑地图1.点云地图(pointcloud)由空间中障碍物边缘点集合构成PointCloud=a“cloud”(i.e.,collection)ofnpoints

激光测距仪、深度相机、相机等传感器均可用于构建点云地图采用二维激光测距仪获得的点云地图直接获得局部点云地图，结合里程估计/定位构建全局点云地图采用三维激光测距仪获得的点云地图直接获得局部点云地图，结合里程估计/定位构建全局点云地图采用RGBD传感器获得的点云地图直接获得具有RGB信息的局部点云地图，数据具有稠密特性采用相机构建的点云地图需对图像进行处理，直接双目匹配恢复匹配点视深，形成视觉像素点云，或者提取特征后估计特征空间位置，形成视觉特征点云，具有稀疏特性激光和视觉数据融合得到的点云地图激光测距仪+视觉RGBD传感器空间坐标+颜色纹理法向量、梯度等信息通过相邻点计算根据法向量和深度的点云分割1.点云地图(pointcloud)优点：完全表示环境三维信息所构建地图不需要预先定义尺寸可方便地利用ICP等匹配方法进行里程估计和定位1.点云地图(pointcloud)缺点：存储要求高16通道三维点云数据有30万点/秒1.点云地图(pointcloud)缺点：存储要求高环境描述层次低，未区分所测量物体是道路还是障碍物，也没有说明点与点之间的空间是空闲、被占还是未知，需处理后才能应用于导航2.栅格地图也称为占用栅格地图(OccupiedGridMap)基本思想：将环境分解成一系列离散栅格，每个栅格有一个值，表示该栅格被障碍物占用的情况

表示栅格单元被障碍物占用的可能性

2.栅格地图三维栅格地图2.栅格地图主要采用激光测距仪数据来构建优点：是一种几何度量地图，可以详细描述环境信息可以方便地采用A*等搜索算法进行最优路径规划可以方便地根据栅格被占概率计算获得当前观测的可能性，实现定位估计缺点：由于地图存储空间由所需建图的环境范围和栅格的分辨率确定，因此随着栅格数量的增加和环境的扩大，地图所需内存和维护时间也迅速增长，地图维度的增加更会随着环境的扩大造成空间需求呈指数级增长栅格地图降低存储空间的方法：采用四叉树/八叉树表示通过分辨率可变来减少存储空间需求栅格地图降低存储空间的方法：采用四叉树/八叉树表示通过分辨率可变来减少存储空间需求栅格地图降低存储空间的方法：采用四叉树/八叉树表示通过分辨率可变来减少存储空间需求通过限制查询的深度，可以随时获得同一地图的多个分辨率八叉树地图体素分辨率为0.08m

点云地图

查询不同深度获得的八叉树地图体素分辨率分别为0.64m和1.28m

栅格地图降低存储空间的方法：采用四叉树/八叉树表示通过分辨率可变来减少存储空间需求通过限制查询的深度，可以随时获得同一地图的多个分辨率随着观测的获取增量式更新观测区域的地图，从而不需要预先定义地图的大小，避免了未知区域占用存储空间存在问题：实现复杂（存储结构、更新方法，地图文件…）高度栅格地图(Elevationmap)针对问题：实现不平整地面上的高效导航规划二维栅格地图只能表示某个平面的环境信息，无法表示不平整地面三维栅格地图对存储资源和计算时间要求高，八叉树实现复杂高度栅格地图(Elevationmap)基本思路：采用二维栅格地图表示方法，在每个栅格中存储该栅格内障碍物的高度信息，通过高斯分布来表示高度估计和不确定性也称为2.5维占用栅格地图

栅格中可存储其他信息

栅格中可存储其他信息截断距离场（TruncatedSignedDistanceFields,TSDF）只计算障碍物附近一定距离内栅格的ESDF数值，其他截断栅格中可存储其他信息截断距离场（TruncatedSignedDistanceFields,TSDF）只计算障碍物附近一定距离内栅格的ESDF数值，其他截断隐式地表征了环境表面信息，

可用于重构高分辨率三维曲

面，减少计算量

3.特征地图基本思想：以抽象的特征描述环境，通常采用拟合障碍物的陆标、线段、平面、多边形等结构性几何特征，通过一组参数对特征进行建模线段特征地图陆标特征地图3.特征地图基本思想：以抽象的特征描述环境，通常采用拟合障碍物的陆标、线段、平面、多边形等结构性几何特征，通过一组参数对特征进行建模

陆标特征地图3.特征地图实际应用时，需通过传感器信息处理来构建陆标特征悉尼大学野外机器人研究中心Victoriapark

dataset采用聚类方法从激光测距仪数据中提取得到树干，作为陆标特征3.特征地图有些应用采用人工放置特定陆标的方法悉尼大学野外机器人研究中心水下探测

声纳目标

3.特征地图发展趋势1:从二维特征向三维特征发展3DplanarfeatureFigurecourtesyofAlexanderJ.B.Trevor3.特征地图发展趋势2:

提升环境描述的层次3.特征地图优点简洁、紧凑、内存占用量小表示方式更接近人对环境的感知对环境具有更高层次的描述性，使定位与建图的鲁棒性更强缺点无法精确表征复杂的真实环境不能表示环境被占用/空闲/未知情况，不能直接用于导航规划4.拓扑地图(TopologicalMap)基本思想：把环境表示为带结点和相关连接线的拓扑结构图，其中结点表示环境中的重要位置点，边表示结点间的连接关系优点：易于扩展，可以实现快速路径规划缺点：由于信息的抽象性，使得机器人难

以实现精确可靠的自定位地图表示研究趋势1:混合地图表示/多层地图表示视觉点云地图和线段特征地图混合地图表示研究趋势1:混合地图表示/多层地图表示拓扑地图与视觉点云地图结合

地图表示研究趋势2:语义地图语义地图是除了环境的空间信息之外还包含已知类别的实体特征的地图。这些实体的信息独立于地图内容，可用于一些特定知识背景中的推理可使传统路径规划转化为面向任务的规划，提高人机交互性能

地图表示研究趋势2:语义地图语义地图的载体可以是前述各种地图表示形式，除了传统地图的基本属性外，地图的每个组成单元还包含该单元对应的语义信息地图表示研究趋势2:语义地图语义地图的载体可以是前述各种地图表示形式，除了传统地图的基本属性外，地图的每个组成单元还包含该单元对应的语义信息5.5局部地图构建局部地图构建在传感器坐标系下，根据当前传感器获得数据构建地图基于传感器坐标系下的局部地图，结合传感器与机器人坐标系之间的标定，可以得到机器人坐标系下的局部地图通过局部地图和全局地图的匹配，可以估计机器人位姿根据机器人位姿估计，可以拼接构建全局地图局部地图构建主要介绍：从激光传感器构建局部栅格地图从激光传感器构建局部线段特征地图5.5局部地图构建

5.5.1局部栅格地图构建占用栅格地图构建

简写为

占用栅格地图构建

简写为

在测量数据条件下计算栅格被占的联合概率分布

可以假设栅格单元彼此独立

以激光测量数据为条件估计每个栅格单元被占概率每个栅格单元被占概率乘积为所求栅格地图的被占概率

贝叶斯规则

每个激光束是独立的

计算几率作Log运算

逆传感器模型

根据某个激光测量数据，估计栅格单元的被占概率根据测距仪检测障碍物的射线模型进行推导59

高度栅格地图构建

采用最大似然估计方法求取高斯分布参数高度栅格地图构建存在问题：地面上存在机器人可行空间，而可行空间上方存在障碍物，取最高部分数据点估计栅格高度将形成虚拟障碍物，造成机器人可行通路被阻塞高度栅格地图构建优化：识别单元是立式结构还是包含有空隙如果地面上包含有空隙，检查所包含的空隙是否超过机器人的高度，超过的话，取空隙下方的数据红色对应于立式结构栅格，蓝色是包含有空隙的栅格高度栅格地图构建优化：优点：为机器人路径规划提供了从障碍物下方通过的可能性缺点：每个单元只能表示1层信息，从而无法利用穿过桥的路径多层平面描述的栅格地图每一个栅格存储多个patch，每个patch描述该栅格上的一层平面，包括以下信息：高度均值高度方差深度值对于地面等平坦物体的单元，深度值为0多层平面描述的栅格地图构建方法为每个三维点确定其所在栅格在垂直方向上做数据簇分割将数据簇分为垂直（>10cm）和水平两类对于水平数据簇，基于簇内所有数据点，利用MLE估计高度均值与方差对垂直数据簇，取最高测量值的均值和方差为估计值多层平面描述的栅格地图优点：可以表示多层信息缺点：无法表示未知信息

增加了垂直维度上的数据量5.5局部地图构建

5.5.2

局部线段特征地图构建从激光测距仪数据到线段特征问题1：给定了属于某条线段的点，线段拟合方法TotalLeastSquare(TLS)RANSAC问题2：激光点云数据分割方法IncrementallinefittingSplitandmergeHoughTransformLeastsquareslinefitting线段表示线性最小二乘问题存在的问题：接近于垂直的线会有一个很大的误差和一个很奇怪的拟合假设误差仅发生在y方向

Totalleastsquare线段表示

假设误差发生在点到线的距离

Totalleastsquare存在cos和sin的非线性带约束最小化问题ConstrainedminimizationUsingLagrangemultipliers

TLS存在问题线段拟合受噪声点影响，即噪声点参与到线段拟合中，对线段参数起作用RANSAC（RANdomSAmpleConsensus）于1981年由Fischler和Bolles最先提出产生背景：数据集中总是包含有噪声TLS法受噪声影响基本假设：样本中包含正确数据(inliers）

这些数据可以被模型描述异常数据(Outliers）

这些数据偏离正常范围很远、无法适应数学模型RANSAC基本步骤随机采样:在样本集中随机抽取n个样本，所抽取样本集合称为S，基于S中的样本进行初始模型M的估计模型验证：计算样本集中其他样本到模型的误差，误差小于设定阈值的样本及S构成内点集合S*，S*是S的一致集(ConsensusSet)可利用集合S*采用LS重新计算新的模型M’保留到目前为止估计得最好的模型M*重新上述过程，直到试验足够多次输出最佳模型M*的参数RANSAClinefittingexample1.随机选择两个点RANSAClinefittingexample随机选择两个点根据这两个点生成初始线段模型RANSAClinefittingexample随机选择两个点根据这两个点生成初始线段模型计算样本集中其他样本到模型的误差，误差函数为点到线的距离RANSAClinefittingexample随机选择两个点根据这两个点生成初始线段模型计算样本集中其他样本到模型的误差，误差函数为点到线的距离得到与模型相一致的点，构成内点集合，重新估计线段模型RANSAClinefittingexampleRANSAC在K次试验中选择到正确样本，K=?随机采样得到的样本均为内点的概率为随机采样得到的样本不全是内点的概率为K次不能得到一个好的样本的概率为在K次实验中至少有1次选择得到好的样本的概率为RANSACRANSAC