CN108763287B - 大规模可通行区域驾驶地图的构建方法及其无人驾驶应用方法 - Google Patents

Abstract

本发明大规模可通行区域驾驶地图的构建方法及其无人驾驶应用方法是一种面向无人驾驶需求的大规模可通行区域驾驶地图的全自动建图、更新以及在线分发方法。本发明提出了一种基于多线激光雷达的大规模可通行区域地图的全自动建图、更新方法与在线分发方法。利用装备有多线激光雷达的采集车实现地图构建与更新，将建图结果上传至服务器进行维护，服务器通过响应多辆无人车的在线请求分发其周边的可通行区域高精地图，从而为无人驾驶提供决策和规划参考，补充甚至部分取代无人车的自身传感器系统。可为道路上运行的多辆无人车提供高精度、高可用的可通行区域地图服务，能够提高无人驾驶的安全性并大幅降低单辆无人车传感器配置成本。

Description

大规模可通行区域驾驶地图的构建方法及其无人驾驶应用 方法

技术领域

本发明是一种面向无人驾驶需求的大规模可通行区域驾驶地图的全自动建图、更新以及在线分发方法。可为道路上运行的多辆无人车提供高精度、高可用的可通行区域地图服务，作为其自主决策参考与行驶保障，能够提高无人驾驶的安全性并大幅降低单辆无人车传感器配置成本。

背景技术

当前无人驾驶对高精度驾驶地图的需求日益增大，而现有的依赖人工或半自动的建图方法信息丰富，但效率低下，更新困难，代价高昂。基于激光雷达原始点云的高精度建图存储代价高，难以扩展到大规模与多车共用。而基于计算机视觉的特征建图主要用于定位，无法提供无人车决策所需的可通行区域范围。在机器人领域常用的基于概率格网的建图方法能够实现在小范围区域，如室内空间，对障碍物分布的全自动建图。但现有技术受到概率格网内存存储的容量限制，无法扩展到大规模的场景中。因此，当前迫切需要一种自动化、高可用且大规模的建图与更新系统来满足无人车驾驶对地图的需求。

发明内容

本发明面向无人驾驶应用需求，提出了一种基于多线激光雷达的大规模可通行区域地图的全自动建图、更新方法与在线分发方法。利用装备有多线激光雷达的采集车实现地图构建与更新，将建图结果上传至服务器进行维护，服务器通过响应多辆无人车的在线请求分发其周边的可通行区域高精地图，从而为无人驾驶提供决策和规划参考，补充甚至部分取代无人车的自身传感器系统。

本发明所采用的技术方案是(附系统流程图11)：

需要保护的方法技术方案一

一种大规模可通行区域驾驶地图的构建方法，其特征在于，包括如下步骤：

1、采集车系统上，使用多线激光雷达对道路环境进行扫描，利用高差实现地面滤除与障碍物分割，得到实时的道路边界障碍物分布图；结合差分全球卫星导航系统(GNSS)与惯性导航设备提供的高精度位姿信息，对多帧的道路边界障碍物分布进行可通行区域概率格网建图。(该步骤沿用了已有通用的常规技术)

2、采集车系统上，在概率格网建图过程中根据雷达帧数与采集车运动变化量进行自适应的子图分块构建，并引入R-Tree将不同大小的子图作为结点构建空间索引。实时根据R-Tree将远离采集车的结点移出内存并存储在磁盘上，并同时将磁盘中已存在的临近采集车的结点读回内存，从而实现建图过程中的内存动态调度，实现大规模建图(该步骤为本方法创新之一)。

3、在建图暂停后将R-Tree及其所有结点数据存储到磁盘。其可继续由采集车建图系统读取并恢复建图过程，从而实现对已建图区域的更新和扩展建图，采集车系统实现了地图大规模建图和更新的自动化(该步骤为本方法创新之一)。

需要保护的方法技术方案二

1.一种大规模可通行区域驾驶地图构建后其在无人驾驶应用方法，其特征在于，采集车系统在建图完成之后，将R-Tree及其所有子图数据上传至服务器，提供地图在线分发服务。服务器响应多个无人车客户端的并发请求，利用R-Tree索引快速搜索无人车客户端所临近的子图结点，并对子图进行融合，实时发送给无人车，从而辅助其进行超越可见范围内的高精度可通行区域地图，辅助无人驾驶的决策和规划过程(该步骤为本方法创新)。

本发明的有益效果是：

1、实现面向无人驾驶需求的高精度可通行区域地图的全自动建图和更新，无需人工交互，并可中断并恢复建图过程，技术可用性高；

2、通过服务器对建图结果进行维护，能够并发响应多个无人车客户端的地图请求，并快速按需分发高精度的可通行区域地图融合结果，从而降低无人车系统的感知代价，能够有效降低无人车感知系统的成本；

创新点：

1.基于一体化R-Tree的空间索引，在建图、更新、扩建以及地图分发服务中实现高效的子图搜索以及内存动态调度，从而能够在有限的内存占用条件下实现任意规模的地图构建，以及实时的地图分发与融合；

提供了一种面向无人车系统的高可用、高精度的可通行区域地图，能够弥补无人车自身传感器的缺陷，降低配置成本，并提高驾驶安全性。

附图说明

图1地图采集车处理平台示意

图2道路可通行区域提取前后效果(前(a)；后(b))

图3自适应地图分块与内存动态调度流程图(步骤2)

图4 R-Tree空间索引图示(其中R8-R19部分列举具体二维几何数据)

图5子图与全局地图示意

图6地图的更新与扩展建图流程图(步骤3)

图7客户端请求与处理流程图(步骤4)

图8大范围可通行区域的建图结果示例

图9可通行区域地图融合结果

图10实施例2地图处理、分发系统示意图

图11建图系统及应用的流程框图

具体实施方式

无人车的行驶路径规划依赖于对周围环境的感知，而传感器受限于分辨率、遮挡、天气等因素影响，难以鲁棒提取可通行区域范围。因此，通过采集车对路沿、护栏等静态障碍物所限定的可通行区域的高精度自动建图，并利用服务器进行在线分发，可为多辆无人车提供高可用的可通行区域地图信息，保证其决策与路径规划的正确性，并降低无人车对自身传感器的依赖，进而降低其成本。基于本发明技术方案，以下结合附图对本发明技术方案做更为详细的介绍。

各个步骤依次为：

实施例1

大规模可通行区域驾驶地图的构建过程

1、可通行区域的提取与概率格网建图

1.1基于多线激光雷达的可通行区域提取

通过安置于采集平台车的多线激光雷达(如图1)，对车辆周边道路环境进行扫描。利用基于高差的点云筛选方法，获得道路边界障碍分布，即可通行区域。

1.1.1多线激光雷达布置与外参数标定

本发明采用多线激光雷达(多个16线、32线或单个64线等)，安置于采集车车顶。使其扫描区域能够覆盖整个道路区域。利用自动或手动方法，对激光雷达的外参数进行标定。通过坐标系变换将雷达坐标系中表达的三维点云转换至车辆局部定位坐标系下。

1.1.2可通行区域提取

将雷达可见平面范围划分为大小为1m*1m的网格单元，统计每一个网格单元区域内三维点云高度值的最小值z_min，给定阈值Δ₁，将该区域点云数据中坐标满足z-z_min>Δ₁的点标记为障碍物点。再将障碍物点投影到建图所需分辨率的二维网格单元地图(如0.2m*0.2m)。遍历网格单元，统计每个网格单元中的障碍物点数，并与车辆的垂直可通行范围进行对比。如有障碍物点位于车辆的通行范围内，则将该网格单元标记为障碍物单元，其余则为可通行区域。可通行区域提取前后如图2所示。

1.2可通行区域概率格网建图

由于单帧的可通行区域提取结果可能由于噪声等原因导致的鲁棒性问题，因此本发明需要利用多帧的提取结果进行概率格网建图。以建图起点作为全局地图坐标系原点，正东、正北分别为X、Y正方向，建立笛卡尔坐标系。建图过程中，通过实时获取采集车高精度位姿，将点云由车辆局部定位坐标系转换至全局坐标系(见步骤1.2.1)。利用多帧可通行区域提取结果对网格单元地图中的障碍物概率值进行初始化与更新，实现概率格网建图(见步骤1.2.2)。

1.2.1位姿数据获取与坐标系转换

通过扩展卡尔曼滤波对RTK GPS、惯导、车辆车速信息进行融合，实现在RTK GPS良好以及暂时缺失的区域获取高频率、高精度的车辆位姿数据。然后利用坐标变换将可通行区域中的障碍物坐标由车辆局部定位坐标系转换至全局坐标系(式1)。

其中P(p_{x_global},p_{y_global})代表全局坐标系下的障碍格网坐标，P(p_{x_local},p_{x_local})代表车辆局部定位坐标系下的障碍格网坐标，θ为航向角，Δx、Δy为车辆局部定位坐标系原点与建图原点之间的偏移量。

1.2.2概率格网地图初始化与更新

概率格网地图使用概率值描述某一个地图网格单元作为障碍的可能性。设定概率值越高代表网格单元为障碍的可能性越大。基于每帧的可通行区域提取结果，将概率格网地图中对应的网格单元划分为有障碍(hit)与无障碍(miss)两个集合，分配概率值为p_hit＝0.55或p_miss＝0.45。若网格单元已被初始化，后续根据每帧可通行区域提取结果对网格单元概率值进行概率更新(见式2)。

其中M_new为更新后的网格单元概率值，M_old为更新前的网格单元概率值，clamp为对概率值的有效范围进行限制的函数。

2、自适应分块与动态内存调度

步骤1中的概率格网地图需要根据建图范围分配固定大小的内存空间，因此受内存大小限制难以扩展到大规模场景下的建图应用。因此，为了实现大规模建图，本发明需对概率格网地图进行自适应分块，构建子图。并本发明又提出对所述子图构建R-Tree空间索引，实现子图的动态调度机制的方法实现内存占用基本恒定，流程图见图3。

详述如下：

2.1地图自适应分块

提出一种自适应的地图分块方法，其综合了雷达扫描帧数量与采集车运动变化量，在建图过程中自动对格网地图进行分块。首先，初始子图范围为以当前位置为中心点，范围a₀*a₀的正方形区域。当有效扫描帧数超过设定阈值或采集车运动到子图范围外，则完成当前子图构建。对子图分配ID，并创建该子图的最小外包围矩形(MBR)，作为一个结点插入到R-Tree中。同时新建一个子图并初始化用于接收数据，相邻子图含有重叠部分(约子图大小的10％)。

2.2基于R-Tree的内存动态调度

所述R-Tree是一棵动态平衡搜索树，R-Tree及其各类变种的平均操作复杂度为对数阶，从而可以高效地对MBR所表示的空间对象进行索引的插入、更新、删除和搜索等操作。

2.2.1R-Tree的维护

所述R-Tree中每一个结点包含1至n个由子图编号ID与空间对象的MBR组成的单元，即(MBR，ID)。其中n为可调参数，用于聚类临近单元从而降低索引数据量。向R-Tree内新增子图结点时，遵循使R-Tree结点MBR重叠区域最小的原则，选择插入位置添加新结点，将子图ID作为结点的唯一标识索引，由子图的空间坐标计算x_min、y_min与x_max、x_max范围属性，确定子图的MBR。(图4为地图R-Tree结构示例)。

2.2.2内存动态调度方法

在实时建图过程中，当子图分块被添加至R-Tree中后，同时基于R-Tree进行空间查询(见步骤4.2)，搜索车辆当前位置附近的n张子图，将其余子图按标识ID写出转移保存到磁盘并从内存中去除。当车辆移动到已建图区域时，通过R-Tree索引搜索结点编号，由磁盘读取对应的子图分块并加载到内存中，进行格网地图更新。如此，子图在内存、磁盘中进行动态的移出与回读，实现内存的动态调度，保证了建图系统的内存占用恒定，从而实现了大规模建图(图5为子图、全局地图结果)。

3、大规模可通行区域地图自动扩展与更新

由于在实用中无法单次完成大规模区域的建图，并且因道路修建、路线变更等原因需要对地图进行更新，故要求建图结果易于更新与扩展。

本发明所提出的建图系统可利用动态调度方法，根据当前位置坐标恢复到上一次的建图流程中：当建图完成后，将生成的可通行区域地图文件输出，同时存储地图的起始位置坐标及子图分块信息的R-Tree空间索引至磁盘。

需进行地图扩展或更新时，读取磁盘中的子图文件、以及对应的R-Tree空间索引与起始位置配置信息，可将建图系统恢复到前次建图流程中，在已有的建图区域的基础上，从任意位置对地图进行多次概率更新与新区域扩展建图，达到增量式建图与自动更新，从而实现大规模地图的建图和维护，流程图见

图6。

实施例2

以下在实施例1的基础上进一步给出步骤4介绍建图后在无人驾驶中的应用

4、可通行区域地图管理与应用，流程图见图7。

为实现无人车客户端的并发地图服务，以MapServer开源地图引擎构建服务器平台，用于发布基于实施例1最终建立的大规模可通行区域驾驶地图。由于整个可通行区域地图由多个重叠的子图构成，根据客户端位置坐标，通过R-Tree空间索引，高效完成子图搜索、融合、在线分发的任务。对于多个子图的重叠区域，使用加权方式融合重叠区域的概率格网，生成最终的可通行区域二值地图。

4.1基于位置的客户端搜索请求

当无人驾驶中客户端向服务器发送地图请求时，基于用户的位置，服务器端利用与子图数据对应的R-Tree进行邻近子图搜索(具体方法见实施步骤4.2)，将查询到符合距离条件的子图数据作为融合对象。

4.2基于R-Tree的子图搜索

在给出一个以客户端车身周边范围为(L*W)的矩形作为空间目标搜索矩形的搜索请求后，从R-Tree的根节点进行递归遍历，通过以平均时间复杂度O(logN)的方式自顶向下遍历R-Tree所包含的结点指针，进行空间多边形包含查询(N为索引数据总数)，快速查询获取车辆当前位置附近的n张子图索引ID。

4.3子图融合

对包含重叠区域的n个子图根据时间戳分配值w_i，将最终可通行区域地图格网的概率p_i(i＝1,2...n)进行加权平均，得到障碍物概率值表示结果p′(式3)。取概率阈值θ作为障碍分类依据，将p′>θ的格网单元标记为障碍物，则可获得无人车可通行区域的二值地图，如图8所示。根据无人车客户端的位姿，可获得当前位姿下的可通行区域无人车局部地图，为驾驶决策与路径规划提供高精度的分析参考(如图9所示)，对车辆自身传感器的感知范围、障碍结果进行补充。

4.4在线分发

系统基于成熟的地图引擎，可响应多客户端的地图请求，实现快速的地图下载与缓存，满足无人驾驶的实时性需求。地图的管理与分发系统流程如图10所示。

Claims (3)

1.一种大规模可通行区域驾驶地图的构建方法，其特征在于，包括如下步骤：

步骤1、采集车系统上，使用多线激光雷达对道路环境进行扫描，利用高差实现地面滤除与障碍物分割，得到实时的道路边界障碍物分布图；结合差分全球卫星导航系统与惯性导航设备提供的高精度位姿信息，对多帧的道路边界障碍物分布进行可通行区域概率格网建图；

步骤2、采集车系统上，在概率格网建图过程中根据雷达帧数与采集车运动变化量进行自适应的子图分块构建，并引入R-Tree将不同大小的子图作为结点构建空间索引；实时根据R-Tree将远离采集车的结点移出内存并存储在磁盘上，并同时将磁盘中已存在的临近采集车的结点读回内存，从而实现建图过程中的内存动态调度，实现大规模建图；

步骤3、在建图暂停后将R-Tree及其所有结点数据存储到磁盘；其继续由采集车建图系统读取并恢复建图过程，从而实现对已建图区域的更新和扩展建图，采集车系统实现了地图大规模建图和更新的自动化；

步骤1中的概率格网地图根据建图范围分配固定大小的内存空间，因此受内存大小限制难以扩展到大规模场景下的建图应用；因此，为了实现大规模建图，对概率格网地图进行自适应分块，构建子图；对所述子图构建R-Tree空间索引，实现子图的动态调度机制的方法实现内存占用基本恒定；

详述如下：

2.1地图自适应分块

提出一种自适应的地图分块方法，其综合了雷达扫描帧数量与采集车运动变化量，在建图过程中自动对格网地图进行分块；首先，初始子图范围为以当前位置为中心点，范围a₀*a₀的正方形区域；当有效扫描帧数超过设定阈值或采集车运动到子图范围外，则完成当前子图构建；对子图分配ID，并创建该子图的最小外包围矩形(MBR)，作为一个结点插入到R-Tree中；同时新建一个子图并初始化用于接收数据，相邻子图含有重叠部分；

2.2基于R-Tree的内存动态调度

所述R-Tree是一棵动态平衡搜索树，R-Tree及其各类变种的平均操作复杂度为对数阶，从而对MBR所表示的空间对象进行索引的插入、更新、删除和搜索操作；

2.2.1 R-Tree的维护

所述R-Tree中每一个结点包含1至n个由子图编号ID与空间对象的MBR组成的单元；其中n为可调参数，用于聚类临近单元从而降低索引数据量；向R-Tree内新增子图结点时，遵循使R-Tree结点MBR重叠区域最小的原则，选择插入位置添加新结点，将子图ID作为结点的唯一标识索引，由子图的空间坐标计算x_min、y_min与x_max、y_max范围属性，确定子图的MBR；

2.2.2内存动态调度方法

在实时建图过程中，当子图分块被添加至R-Tree中后，同时基于R-Tree进行空间查询，搜索车辆当前位置附近的n张子图，将其余子图按标识ID写出转移保存到磁盘并从内存中去除；当车辆移动到已建图区域时，通过R-Tree索引搜索结点编号，由磁盘读取对应的子图分块并加载到内存中，进行格网地图更新；如此，子图在内存、磁盘中进行动态的移出与回读，实现内存的动态调度，保证了建图系统的内存占用恒定，从而实现了大规模建图。

2.根据权利要求1所述的一种大规模可通行区域驾驶地图的构建方法，其特征在于，步骤3中所述建图系统利用动态调度方法，根据当前位置坐标恢复到上一次的建图流程中：当建图完成后，将生成的可通行区域地图文件输出，同时存储地图的起始位置坐标及子图分块信息的R-Tree空间索引至磁盘；

需进行地图扩展或更新时，读取磁盘中的子图文件、以及对应的R-Tree空间索引与起始位置配置信息，将建图系统恢复到前次建图流程中，在已有的建图区域的基础上，从任意位置对地图进行多次概率更新与新区域扩展建图，达到增量式建图与自动更新，从而实现大规模地图的建图和维护。

3.一种大规模可通行区域驾驶地图构建后其在无人驾驶应用方法，其特征在于，采集车系统在建图完成之后，将R-Tree及其所有子图数据上传至服务器，提供地图在线分发服务；服务器响应多个无人车客户端的并发请求，利用R-Tree索引快速搜索无人车客户端所临近的子图结点，并对子图进行融合，实时发送给无人车，从而辅助其进行超越可见范围内的高精度可通行区域地图，辅助无人驾驶的决策和规划过程；

包括步骤：

4.1基于位置的客户端搜索请求

当无人驾驶中客户端向服务器发送地图请求时，基于用户的位置，服务器端利用与子图数据对应的R-Tree进行邻近子图搜索，将查询到符合距离条件的子图数据作为融合对象；

4.2基于R-Tree的子图搜索

在给出一个以客户端车身周边范围为L*W的矩形作为空间目标搜索矩形的搜索请求后，从R-Tree的根节点进行递归遍历，通过以平均时间复杂度O(logN)的方式自顶向下遍历R-Tree所包含的结点指针，进行空间多边形包含查询，快速查询获取车辆当前位置附近的n张子图索引ID；N为索引数据总数；

4.3子图融合

对包含重叠区域的n个子图根据时间戳分配值w_i，将最终可通行区域地图格网的概率p_i进行加权平均，i＝1,2...n，得到障碍物概率值表示结果p′；取概率阈值θ作为障碍分类依据，将p′>θ的格网单元标记为障碍物，则可获得无人车可通行区域的二值地图；根据无人车客户端的位姿，获得当前位姿下的可通行区域无人车局部地图，为驾驶决策与路径规划提供高精度的分析参考，对车辆自身传感器的感知范围、障碍结果进行补充；

4.4在线分发

系统基于地图引擎，响应多客户端的地图请求，实现快速的地图下载与缓存，满足无人驾驶的实时性需求。

Images