无人驾驶技术原理及应用 课件 7.2 全局路径规划

张军7.2全局路径规划1全局路径规划与局部路径规划的关系2全局路径规划的方法3全局路径生成实例目录全局路径规划是在环境信息已知的条件下，一次性完成的，又称为一次路径规划，或静态规划、路由寻径等；局部路径规划是基于全局路径规划的结果、根据实时周边信息进行的规划，因此也称为二次路径规划或动态规划。局部路径规划以全局路径规划的结果作为基础，根据实时的环境信息对原有的路径进行局部修正和优化，从而达到对安全性的约束和对效率的追求。全局路径规划与局部路径规划的关系：全局对局部起导向和约束作用,局部是对全局的具体优化与调整。1.全局路径规划与局部路径规划的关系2.全局路径规划的方法全局路径规划常见的算法包括基于图搜索的算法、基于曲线拟合的算法、基于数值优化的算法等。基于图搜索的算法比较典型的代表包括Dijkstra算法（迪杰斯特拉算法）和A*算法。Dijkstra算法的时间、空间复杂程度都较高，本质上是一种发散式的广度优先搜索策略方法；A*算法是一种启发式算法，也可认为是一种深度优先的算法。

Dijkstra算法是由E.W.Dijkstra于1959年提出，又叫迪杰斯特拉算法，是目前较为简单并且应用较多的求解全局最优路径的方法。算法主要解决网络中的一个节点到其他节点的最优路径。在到达终点的过程中，每一次选择下一个的顶点为距离当前点最近的一个节点。优点：核心算法简单，容易理解，对所有的路网信息都适用，适用性较强，保证能找到一条从初始点到目标点的最短路径；缺点：需要遍历完所有的节点才能获得最短路径。

2.全局路径规划的方法算法思路：1.指定一个节点，例如我们要计算‘A’到其他节点的最短路径；2.引入两个集合（S、U），S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点（以及A到该点的路径，注意，A->C由于没有直接相连，初始时为∞）；3.初始化两个集合，S集合初始时只有当前要计算的节点，A->A=0，U集合初始时为A->B=4,A->C=∞,A->D=2,A->E=∞；4.从U集合中找出路径最短的点，加入S集合，例如A->D=2；5.更新U集合路径，if(‘D到B,C,E的距离’+‘AD距离’<‘A到B,C,E的距离’)则更新U；6.循环执行4、5两步骤，直至遍历结束，得到A到其他节点的最短路径。2.全局路径规划的方法Dijkstra算法主要解决的是节点之间带有权重的最短路径问题。例如，对于下图这样一个有权图，Dijkstra算法可以计算任意节点到其他节点的最短路径。2.全局路径规划的方法A*算法在Dijkstra算法的基础上加入了启发式策略从而提高搜索效率，其主要改进在于利用启发式函数来决定每个节点搜索的权重。传统A*算法通过定义启发式函数来评估代价，选择其中代价最小的栅格，不断迭代而确定最优路径。启发式函数为:f(n)=g(n)+h(n)式中：n为当前节点；f(n)为从起始点经过当前节点n到达目标点的最优代价解的估计代价；g(n)为起始点到当前节点n的实际估价值；h(n)为当前节点n到目标点的需要付出的估价值。利用A*算法得到的最优路径A*算法原理：设置一个合适的启发式函数，全面评估各扩展搜索节点的估价值，通过比较各扩展节点的估价值，选取代价最小节点加以扩展，直至到达目标点。实际上，对于大范围的场景，A*算法的空间和时间复杂度过高。因此在复杂的无人驾驶场景中，A*算法更适合于在已知的局部环境中搜索最短路径。2.全局路径规划的方法以国家自然科学基金委员会每年在常熟举办的中国智能车未来挑战赛为例。比赛以给定路网文件、在指定区域设定特定任务的方式对无人驾驶车辆进行道路测试，着重考察无人驾驶车辆的交通场景识别能力、不同道路环境的适应性和行驶机动性等4S性能（即安全性Safety、平顺性Smoothness、敏捷性Sharpness和智能性Smartness）。比赛一般包括真实道路环境测试（含城乡道路和高架快速道路测试）和复杂环境认知水平能力离线测试两部分。真实道路环境测试的比赛任务以任务文件形式提供，任务文件为一组包含GPS坐标的任务点列表，要求参赛车辆完全自主地从起点出发，依次通过各个任务点，到达终点。任务点通常包括遵守交通信号、礼让行人、避让作业车辆、施工占道场景下的避让通行等。无人驾驶车必须同时具备全局和局部规划的能力，才能完成比赛任务。无人车通过先验驾驶地图与关键点路网文件、结合全局路径规划算法产生全局最优路径，再结合实时感知的道路环境信息进行局部路径规划，从而完成各指定任务。3.全局路径生成实例(1).驾驶地图驾驶员在驾车时利用自己大脑中已建立的先验地图知识作为依据，进行道路的选取以及具体路径的确定。无人车驾驶也借鉴这一原理，拥有自己的先验地图知识，让车自己认识路，从而进行自主驾驶。这种先验地图知识的表现形式就是驾驶地图。驾驶地图要具有与普通电子地图相同的特性，指明可行驶的道路，但不同的是，驾驶地图的精度更高，而且还应该包括尽可能多的有用信息，比如道路特征、交通灯、静态障碍物、上下坡、拱桥、匝道等信息。驾驶地图需要有表征道路特性的属性，用以辅助决策层对车辆进行决策控制。道路特性具体指的就是这段路固有的属性，比如这条路是直道还是弯道。对于车辆的控制，无外乎横向控制和纵向控制。横向控制就是方向控制，纵向控制也就代表着速度控制。驾驶地图的路线是方向控制的依据，驾驶地图的道路特性值是速度控制的重要参照。因此驾驶地图应该要包括这两部分：路线图和道路特性值。3.全局路径生成实例北京联合大学北苑校区操场采集路线图一系列经纬度点连接成路段，一系列路段拼接成路线图。驾驶地图的路线图就是由众多经纬度点组成。点的延伸趋势就是车辆转角控制的关键依据。右图是经纬度点构成的一张简单的北京联合大学北苑校区操场的路线图。红色曲线就是围绕操场一圈的轨迹图。3.全局路径生成实例驾驶地图应该包含道路特性值。道路特性值的初步划分主要是以道路弯曲程度和道路上对速度控制有影响的因素作为划分依据。小曲率弯道时，车速可以很快，大曲率弯道时，则车速应该适当降低。车速的快慢与道路的弯曲程度紧密关联，因此道路特性值的标注有利于决策程序对车速进行智能控制。当无人车行驶过程中遇到红绿灯时，检测道路特性值是203，表明此时车的位置接近于红绿灯，可以通知图像模块进行红绿灯的识别，具体的道路属性划分如右表所示。道路特性值属性200直道201小曲率弯道202大曲率弯道203有红绿灯路口204无红绿灯路口205U字掉头206施工路段207隧道208侧方停车209拱桥210上坡211下坡导航采集地图集数据属性表3.全局路径生成实例(2).驾驶地图数据集构建右图展示的就是建立的一张在江苏常熟九宫格地区的地图数据集。这个地图数据集就是利用精密的差分GPS导航设备采集的经纬度路线的地图数据。该区域中，总共有108个路口特征、40个路段特征。采集时，通过驾驶员驾驶带有GPS设备的车辆在九宫格区域反复兜圈，确保途经所有的路段和路口，所有的直行、转弯、调头被采集到。在车辆行驶过程中，采集人员需要利用地图采集程序记录下途经点的经纬度、航向角等实时信息，并手工设置道路的属性。中国智能车未来挑战赛九宫格地区地图数据集3.全局路径生成实例3.全局路径生成实例地图存储时主要有两种方案。对于区域范围较小的地区，将地图数据可保存在txt文本文件中，对于区域范围较大的地区，则可将地图数据保存在Access数据库中。对于采集到的原始数据集，需要通过地图处理软件进行路段与路口的分割，对于漏采的情况需要进行路径拟合或者重新采集。地图集处理完，还需要进行实车验证是否可用；如不可用，则还需修改或重新采集。通过整个一个流程，才能构建一个属于无人车的高精度驾驶地图。另外，驾驶地图为无人车构建了一张静态地图，而车辆行驶时还需要一张以驾驶地图为底图的动态地图，一般采用栅格地图，用于局部路径规划。表1

路点属性1对照表属性值类型0起点1交叉口入点2交叉口出点3普通路点4进入停车区5驶出停车区6停车位位置7终点停车表2路点属性2对照表属性值含义0行驶方向和交通标志均未知1直行2右转3左转4掉头5有交通标志(3).路网文件路网文件(RoadNetworkDefinitionFile,RNDF)定义无人车可以访问的道路信息，可采用点、线、面相结合的方式。点包括路点（指道路上带有经纬度信息的点）和检测点（无人车完成指定任务必须经过的特殊路点）；线的信息包括标志线的宽度、颜色、条数、道路宽度和车道数；面的信息包括特定区域（如自主泊车区域等）。每一个点的具体信息除了包括经纬度、高度信息，还包括属性1和属性2。属性1用于提供该点的类型，具体的类型对照表1。属性2用于提供该路口行驶方向或有无交通标志，具体的规定如表2。3.全局路径生成实例图2014年中国智能车未来挑战赛九宫格的全局路径规划结果(4).全局路径形成根据路网文件中给出的关键点的经纬度，