智联网汽车技术 课件 6.4基于采样的路径规划算法

基于采样的路径规划算法项目三汽车决策控制系统任务6路径规划系统主讲人：杨时川智能网联汽车技术课程导入想象一下，如果让汽车在一个复杂动态环境中快速规划出一条安全驾驶路径，应该如何高效实现呢?学习目标学习基于采样的路径规划的几种算法01学会解释基于采样的路径规划算法及其效率优势02学习任务共同完成对几种典型采样算法的介绍01激活旧知随机采样搜索与传统全局搜索有什么不同吗?随机采样搜索更高效传统全局搜索时间长探索新知基于随机采样的路径规划算法适用于高维度空间，由于求解时间是有限制的，大部分情况下只能得到一个概率层面上的最优路径，可提高搜索效率。基于随机采样的路径规划算法探索新知基于随机采样的路径规划算法基于随机采样的路径规划算法单查询算法渐近最优算法找到可行路径，侧重快速性找到的路径进行逐步优化达到最优，侧重最优性探索新知基于随机采样的路径规划算法概率路图法PRM(ProbabilisticRoadMap)算法随机扩展树法RRT(Rapidly-exploringRandomTrees)算法动态窗口法DWA算法探索新知随机路图法（PRM）以图结构为基础的路径规划算法分为两个阶段：学习阶段和查询阶段首先将连续空间转换成离散空间，在规划空间内随机选取N个节点。随机路图法（PRM）探索新知随机路图法（PRM）学习阶段（构建图）在有起始点和目标点的C-空间内随机撒下N个粒子删除在障碍物中的点每个点连接到最近的点，得到无碰路径图距离太长或者连线有经过障碍物的，不连接探索新知随机路图法（PRM）查询阶段（搜索路径）在路线图上搜索以找到从开始到目标的路径(使用Dijkstra's或A*)路线图与网格图（或简化的网格图相似）探索新知小贴士随机路图法（PRM）的算法过程？从构建的图上的起点使用图搜索算法(A*、Dijkstra)规划一条从起点到终点的路径，然后将每个点与它相邻的点(一定距离内)连接起来，剔除碰到障碍物的连接。连续空间转换成离散空间构建图（红色和绿色的线不连接）剔除碰到障碍物的连接搜索路径探索新知随机路图法（PRM）在多数问题上，相对少的样本足够来覆盖大分的可行空间，并且找到路径的概率为百分之百。当随机采样点太少或分布不合理时，PRM算法是不完备的，但随着采用点的增加可以达到完备，所以PRM是概率完备且不最优的。探索新知快速探索随机树路径规划方法（RRT）一种适用于多维空间中路径规划方法以一个初始点作为根节点，通过随机对空间中的路径点进行采样来增添子节点，以此构造一个随机扩展树。当随机树中的子节点进入了目标点所在的目标区域内时，已成功寻找到路径。该方法得到的路径是一条蜿蜒曲折的路径。快速探索随机树路径规划方法（RRT）探索新知快速探索随机树路径规划方法（RRT）与PRM方法相似，该方法也是概率不完备的，利用该方法所求得的最终路径往往不是最优，而且当面对狭窄通道型障碍物时，RRT算法往往需要花费很多时间进行随机树扩展才可以找到出口。探索新知快速探索随机树路径规划方法（RRT）PRM算法：在一开始就通过抽样在地图上构建出完整的无向图，再进行图搜索RRT算法：从某个点出发一边搜索，一边抽样并建图探索新知动态窗口法根据机器人或自动驾驶汽车当前的线速度和角速度，在速度空间中进行采样，通过所设计的评价指标对一定时间内的运动轨迹进行评价，并选择最优轨迹所对应的控制量对机器人或车辆进行控制。DWA算法（动态窗口法）探索新知动态窗口法DWA算法核心采样动态规划空间维度的采样（轨迹采样）时间维度的采样（速度采样）探索新知动态窗口法动态窗口法中，在不同场景下需要进行代价函数的选择和设计DWA算法的仿真结果需考虑的因素01保证机器人或者自动驾驶汽车行进方向不会频繁切换02不会与障碍物或者道路边缘发生碰撞03航向角没有突变04局部路径方向与目标点方向一致05速度在区间内