任务5.5 路径规划算法-课件

主讲老师：李锋路径规划算法项目5：智能驾驶AP应用开发与算法简介任务5.5《车载计算平台技术与应用》目录任务导入AssignmentINTRO学习目标LearningobjectivesCONTENTS0102知识准备Backgroundknowledge03任务实施Assignmentimplement课堂总结Classroomsummary040605课堂小测ClassroomquizzPART01任务导入AssignmentINTRO任务导入路径规划是整个智能驾驶系统中最核心的部分之一，前面的课程已经讲解全局路径规划的内容，本任务将着重讲解局部路径规划。局部规划和全局规划有什么异同点呢？局部路径规划PART02学习目标Learningobjectives学习目标素质目标通过路径规划算法的流程，培养学生的逻辑思维和创新思维；了解环境处理模块的逻辑，提高学生在技能上的职业素养。能力目标能列举路径规划常见算法[A65]；能举例讲解环境预处理模块的逻辑[A66]。知识目标能理解路径规划的基本概念[K79]；能描述拟人式和场景编排式路径规划算法的流程[K80]；能理解环境处理模块的工作流程[K81]。PART03知识准备Backgroundknowledge一、路径规划算法背景在本任务中所描述的Planning更侧重于局部路径规划，Planning会考虑所有当前信息和历史信息，生成一条最终车辆要行驶的路径交给控制模块去控制车辆行驶。自动驾驶中的路径规划是指根据车辆的起始点和目标点生成一条无碰撞且满足车辆自身约束的轨迹，一般情况下路径规划不包含时间信息。路径规划一、路径规划算法背景整个智能驾驶系统可以划分为两大块：广义感知和广义规控。在规控部分可划分为地图定位、全局导航、路径规划、安全边界、运动控制等，其中路径规划是整个规控的核心模块。1.路径规划算法的作用感知多传感器融合与预测广义感知定位路径规划全局导航安全边界运动控制广义规控广义感知和规控一、路径规划算法背景业界常用的路径规划算法可以分为四大类。2.常见的路径规划算法基于图形搜索的规划器将地图、车辆的信息三格化，在三格化的图形中搜索出一条无碰撞且代价很小的路径基于采样的规划器相对图算法更加迅速，但在特定一些复杂的空间下，采样会导致效率下降插值曲线规划器通过少数的控制点去生成光滑的插值曲线，但是这些插值曲线未必满足约束条件数值优化方法设定曲率、位移速度、光滑可导等约束条件，通过数值优化的方法去求解轨迹点，能得到最优轨迹一、路径规划算法背景各路径规划算法的比较。2.常见的路径规划算法算法分类算法名字优点缺点基于图形搜索的规划器Dijkstras不仅求出起点到终点的最短路径以及长度，而且还求解出了起点到图中各个点的的最短路径，适用于结构化和非结构化环境中的全局规划。当节点数目n比较大的时候，该算法的时间复杂度急剧增加，存在速度慢或者空间不足的问题，难以满足实时性的要求。A*系列基于Dijkstra算法，搜索中增加了启发函数，减少了搜索节点，提高了搜索效率，目前全局路径规划运用最为广泛的算法。启发函数大多情况下不好确定，其空间增长是指数级别的。状态格算法能够处理多个维度（位置、速度、加速度、时间），适用于局部规划和动态环境下的规划。对数据库中每个可能的解决方案进行了评估，计算非常耗时。一、路径规划算法背景各路径规划算法的比较。2.常见的路径规划算法算法分类算法名字优点缺点插值曲线规划器多项式曲线计算量较小，可用于多条曲线的串联，规划结果舒适性较高。曲率连续最低要求4次，关键参数不容易获取。贝塞尔曲线计算量较小，可用于多条曲线的串联，规划结果舒适性较高。曲线阶数增加，曲线的延展性下降，计算时间也随之增加。样条曲线计算量较小，得出由不同控制点拟合出的连续曲线。结果更侧重于实现节点之间的连续性，而不是适应道路约束的延展性。一、路径规划算法背景各路径规划算法的比较。2.常见的路径规划算法算法分类算法名字优点缺点基于采样的规划器RRT系列算法能在多维系统中提供快速解决方案。适用于全局和局部规划。产生的轨迹不连续，当空间中包含大量障碍物或者狭窄通道约束时，算法的收敛速度极慢，效率会大幅下降。数值优化方法功能优化可以将道路的约束、车辆状态的约束以及其他的交通参与者直接表示出来并通过数学方法进行求解。每个运动状态下都会进行实时的计算，计算量大且非常耗时，依赖于全局导航的路点信息。二、路径规划算法概述拟人式规划算法框架是一种基于状态迁移的规划算法，可以理解为该算法是从一个正常人类司机开车的角度出发，设定一系列横向、纵向的行为以及一系列的目标，并根据这些信息生成相应的决策行为和轨迹规划。1.拟人式规划算法（状态迁移式）拟人式规划算法框架二、路径规划算法概述通过时间、空间范围内的安全、效率、利他等因素，进行行为的状态迁移。输出信息如下：1.拟人式规划算法（状态迁移式）（1）行为决策横向行为车道保持/避障、（取消/强制）变道、泊车、掉头、路口左/右转、汇入汇出纵向行为free、跟车、汇入、（V/P/E）停车、泊车、倒车速度目标速度限制，虚拟墙、减速度、P-stop距离跟踪目标ID，速度，距离，需要保持的距离变道gap（旁路）目标目标gap（前后车速度、距离）、bypass旁路距离二、路径规划算法概述根据不同行为，确定路点序列。输出信息如下：1.拟人式规划算法（状态迁移式）（2）轨迹规划路点序列速度信息[目标速度（限制）]提前的灯控信息二、路径规划算法概述场景编排式规划算法的核心是把规划过程根据功能需求进行job（单一场景的路径规划策略）化的拆分，按照模块化的思路，通过不同驾驶场景的需求来进行不同job的组合，来实现对应的功能。2.场景编排式规划算法场景编排式规划算法框架二、路径规划算法概述2.场景编排式规划算法场景编排式规划算法的整体流程类似一个流水线，环境处理模块提供的planningBUS(数据流)相当于“原材料”，每一个job对数据总线上的“原材料”进行获取和修改，最终获得轨迹信息。场景编排式规划算法流程思政专栏算法是计算机科学的精髓更是软件的灵魂。国产工业软件算法专家-周培德教授，作为我国计算几何算法界的权威专家，从1982年开始研究算法，曾独立发明各类几何算法236个，解决相关问题200多个，独立发表学术论文七十余篇，并有两本专著及两本研究生教材，退休后仍然从事算法设计方面的工作，帮助很多国内企业解决实际生产问题。并被世界著名几何专家罗密欧誉为“天才”数学家。周培德教授国产工业软件算法专家周培德思政专栏作为一名资深的“算法工程师”，周教授称：如果你想成为一名优秀的程序员，建议你尽早学习，研究与你工作有关的各种算法。当然。并不是每一个人都需要在算法上有很深刻的造话，毕竟每一个程序员所选择的发展方向是不一样的。也许几年以后，有些程序员将从事项目管理，质量控制等相关的工作，在这些工作中就不必用到算法。国产工业软件算法专家周培德周培德教授给《程序员》读者提建议三、路径规划算法环境处理模块1.地图导航信息处理从路径规划算法的流程框架中可以发现，路径规划的必要步骤是对环境信息进行提取和处理，路径规划环境预处理流程如下：环境预处理流程输入输出①地图导航信息处理②障碍物投影三、路径规划算法环境处理模块1.地图导航信息处理参考线的生成即基于车道线中心线进行生成，但是自车行驶的车道信息需要地图全局导航结果，因此首先要进行地图全局导航信息的处理，根据全局导航信息的结果以及自车当前的位置，找出自车即将要走的一段路线上的车道信息，一般包括主车前后两三百米的车道信息，从而生成一条局部的导航路径。参考线生成三、路径规划算法环境处理模块1.地图导航信息处理此时得到的参考线，实质上是一个基于车道信息提取的车道中心线的一系列采样点，但是初始的参考线还是离散的，需要对其进行平滑处理，对这些离散的点进行曲线的拟合。参考线拟合三、路径规划算法环境处理模块有了一条平滑的参考线后，如图中的红色曲线，还需要根据各种信息做投影，从左图上弯曲的道路信息，障碍物信息、预测轨迹都投影到右图上的统一直角坐标系中，最终得到一条包含障碍物的参考线，用于后续的规划算法。2.障碍物投影障碍物投影PART04Assignmentimplement任务实施一、路径规划导航1.概述本实训任务的将使用自动驾驶一体化框架AutoWare，通过加载场景及视像bag包以及自动驾驶算法，构建虚拟仿真场景，复现路径规划导航。AutoWare一、路径规划导航2.实验环境准备本次实验环境包括电源线，安装Ubuntu18.04虚拟环境的PC机一台（最低CPU配置为I510代）。每套实验环境适用于4~12名学生同时上机操作。（1）设备检查设备名称数量备注电源线1组所有实验组共用笔记本或台式机每组1台台式机要有无线网卡一、路径规划导航2.实验环境准备本次实验的PC机为双系统的，在开机时需要将Ubuntu20.04虚拟环境切换为Ubuntu18.04虚拟环境。（1）设备检查系统切换一、路径规划导航2.实验环境准备视觉里程计项目文件：5-5aw_ws文件夹。（2）项目描述项目描述一、路径规划导航3.进入工程目录打开主目录\MDC300Sample-1.0.107.2\5-4Dijkstra_ws文件夹，右键鼠标打开终端框。进入工程目录一、路径规划导航4.构建环境变量打开终端框后，必须先将工作空间的路径加入到环境变量中，才能使用ros相关的命令，输入以下命令：sourceinstall/setup.bash执行命令后:构建环境变量一、路径规划导航5.运行项目脚本执行命令后，终端框会输出进程启动信息以及软件启动信息。项目启动命令一、路径规划导航5.运行项目脚本将自启动RuntimeManager软件，显示图像化界面。RuntimeManager界面一、路径规划导航6.加载bag包点击Simulation选项卡，选择aw_ws项目文件夹中的sample_moriyama_150324.bag包。加载bag包一、路径规划导航6.加载bag包设置倍率Rate：0.5，开始时间StartTime(s)：140，点击“Play”按钮播放bag包，当播放1秒后，点击“Pause”按钮暂停播放。加载播放bag包一、路径规划导航7.读取算法文件点击QuickStart选项卡，依次点击Map（地图）、Sensing（传感器）、Localization（定位）、Detection（检测信息）、MissionPlanning（任务规划）、MotionPlanning（路径规划）按钮，加载相关算法程序文件。读取资源文件一、路径规划导航7.读取算法文件若终端框中出现如图所示提示，则表示加载成功。文件加载成功一、路径规划导航8.启动RViz读取完所有资源文件后，点击Rviz按钮，启动RViz软件。启动Rviz软件一、路径规划导航9.加载配置文件点击左上角File->OpenConfig选项。打开配置界面一、路径规划导航9.加载配置文件打开配置界面后，选中“quickstart.rviz”项，并点击“open”按钮加载该配置文件。加载配置文件一、路径规划导航10.播放bag包在“RuntimeManager”软件界面中，重新点击“Simulation”选项卡，再次点击“Pause”按钮重新播放bag包。重新播放bag包一、路径规划导航11.查看路径规划导航画面打开Rviz界面，读取所有数据的导航信息，并显示路径规划画面。路径规划导航画面PART05Classroomquizz课堂小测课堂小测1)相对图算法更加迅速，但在特定一些复杂的空间下，采样会导致效率下降的路径规划算法是（）。(单选)A) 基于图形搜索的规划器B) 基于采样的规划器C) 插值曲线规划器D) 数值优化方法B2)环境处理模块提供的（

）相当于“原材料”，每一个job对数据总线上的“原材料”进行获取和修改，最终获得轨迹信息。（单选）A) jobB) planningC) planningBUSD) SubLaneC课堂小