《22路径规划综述教学内容》由会员分享，可在线阅读，更多相关《22路径规划综述教学内容（34页珍藏版）》请在金锄头文库上搜索。
1、机器人路径规划研究综述 王超群2016 06 27 1 什么是路径规划 依据某种最优准则 在工作空间中寻找一条从起始状态到目标状态的避开障碍物的最优路径 需要解决的问题 1 始于初始点止于目标点 2 避障 3 尽可能优化的路径 1 路径规划技术分类 1 静态结构化环境下的路径规划2 动态已知环境下的路径规划3 动态不确定环境下的路径规划 2 路径规划算法分类 2 路径规划算法分类 3 A D 算法 问题 从A移动到B 绕过障碍首要步骤 方格 三角形五角形 etc 划分空间 简化搜索区域 空间被划分为二维数组 数组中每个元素代表空间中的一个方格 可被标记为可行或不可行 未来的路径就是一系列可行方
2、块的集合 Nodes的概念涵盖了一系列可行方块 或其他形状 A B 障碍 http www policyalmanac org games aStarTutorial htm 3 A D 算法 步骤从节点A开始 搜索其临近节点 知道找到目标点 A B 障碍 http www policyalmanac org games aStarTutorial htm 3 A D 算法 步骤a 从节点A开始 把一系列待考虑的节点放入OpenList里面 OpenList存放着一系列需要检查的节点 方块 如图 首先检查起点周围的8个节点 A B 障碍 http www policyalmanac org g
3、ames aStarTutorial htm A 3 A D 算法 步骤a 给每个节点赋值F G HG 从初始点到给定待查节点的距离 可多种距离量度 H 从给定待检查节点到目标点B的距离 可多种距离量度 Heuristic计算时忽略到达目标点会遇到的障碍 A B 障碍 http www policyalmanac org games aStarTutorial htm A 3 A D 算法 步骤a 给每个节点赋值F G HG 从初始点到给定待查节点的距离 可多种距离量度 H 从给定待检查节点到目标点B的距离 可多种距离量度 Heuristic计算时忽略到达目标点会遇到的障碍 http www
4、policyalmanac org games aStarTutorial htm B A 3 A D 算法 F G H 3 A D 算法 步骤b 找到F值最小的节点作为新的起点将它从OpenLsit中删除 加入到ClosedList里面检查它的临近节点 忽略已经在ClosedList中的节点和不可行节点 障碍 如果临近节点已经在OpenList里面 则对比一下是否从现节点到临近节点的G值比原G值小 若是 把现节点作为父节点 否 不做改动 3 A D 算法 步骤c 上步骤中新节点未造成任何改动 我们继续在OpenList中寻找新的节点 如图重复a b 中的步骤 直到我们找到目标节点 新节点 3
5、 A D 算法 寻找到目标节点 3 A D 算法 从目标节点回溯可以找到初始点 从而确定路径 3 A D 算法 A 算法的特点 A 算法在理论上是时间最优的 但是也有缺点 它的空间增长是指数级别的 D 算法DynamicA 应用于在动态环境下的搜索 3 A D 算法 深度优先VS广度优先深度优先 3 A D 算法 深度优先VS广度优先广度优先 A 4 人工势场法 人工势场法是局部路径规划的一种比较常用的方法 4 人工势场法 4 人工势场法 引力场和斥力场的构建引力函数 引力场 4 人工势场法 引力场和斥力场的构建斥力场 斥力 4 人工势场法 4 人工势场法 人工势场法的优缺点优点 便于低层的实
6、时控制 在实时避障和平滑的轨迹控制方面 得到了广泛应用缺点 a 当物体离目标点比较远时 引力将变的特别大 相对较小的斥力在甚至可以忽略的情况下 物体路径上可能会碰到障碍物 b 当目标点附近有障碍物时 斥力将非常大 引力相对较小 物体很难到达目标点 c 在某个点 引力和斥力刚好大小相等 方向想反 则物体容易陷入局部最优解或震荡 5 快速搜索随机树 RRT 5 快速搜索随机树 RRT 5 快速搜索随机树 RRT 5 快速搜索随机树 RRT 5 快速搜索随机树 RRT 5 快速搜索随机树 RRT 优点 复杂度主要决定于寻找路径的难度 跟整个规划场景的大小和构型空间的维数基本无关缺点 1 基本无bias的RRT会在空间随机扩展2 输出路径非最优路径 6 当前研究 1 轨迹优化 样条插值 多项式插值等平滑方法2 未知环境下的路径规划 exploring 3 动态环境下的路径规划4 三维路径规划 Thankyou
