22路径规划综述

机器人路径规划研究综述王超群2016/06/271•路径规划的概念2•路径规划分类简介3•路径规划的发展现状4•A*、D*算法4•人工势场法（APF）5•快速搜索随机树（RRT）6•当前研究1.什么是路径规划路径规划技术是机器人研究领域中的一个重要分支。所谓机器人的最优路径规划问题,就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短等),在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。1.什么是路径规划依据某种最优准则，在工作空间中寻找一条从起始状态到目标状态的避开障碍物的最优路径。需要解决的问题：1.始于初始点止于目标点。2.避障。3.尽可能优化的路径。1.路径规划技术分类1.静态结构化环境下的路径规划2.动态已知环境下的路径规划3.动态不确定环境下的路径规划2.路径规划算法分类路径规划算法基于采样的方法Voronoi,RRT,PRM基于节点的方法Dijkstra,A*,D*基于数学模型的算法MILP,NLP基于生物启发式的算法NN,GN多融合算法PRM-Nodebased2.路径规划算法分类路径规划算法传统算法模拟退化法人工势场法etc智能算法遗传算法神经网络算法etc3.A*、D*算法问题：从A移动到B，绕过障碍首要步骤：方格（三角形五角形.etc）划分空间,简化搜索区域。空间被划分为二维数组，数组中每个元素代表空间中的一个方格，可被标记为可行或不可行。未来的路径就是一系列可行方块的集合。Nodes的概念涵盖了一系列可行方块（或其他形状）AB障碍*、D*算法步骤从节点A开始，搜索其临近节点，知道找到目标点AB障碍*、D*算法步骤a)从节点A开始，把一系列待考虑的节点放入OpenList里面，OpenList存放着一系列需要检查的节点（方块），如图，首先检查起点周围的8个节点AB障碍*、D*算法步骤a)给每个节点赋值F=G+HG：从初始点到给定待查节点的距离（可多种距离量度）H：从给定待检查节点到目标点B的距离（可多种距离量度）（Heuristic计算时忽略到达目标点会遇到的障碍）AB障碍*、D*算法步骤a)给每个节点赋值F=G+HG：从初始点到给定待查节点的距离（可多种距离量度）H：从给定待检查节点到目标点B的距离（可多种距离量度）（Heuristic计算时忽略到达目标点会遇到的障碍）*、D*算法FGH3.A*、D*算法步骤b)找到F值最小的节点作为新的起点将它从OpenLsit中删除，加入到ClosedList里面检查它的临近节点，忽略已经在ClosedList中的节点和不可行节点（障碍）如果临近节点已经在OpenList里面，则对比一下是否从现节点到临近节点的G值比原G值小，若是，把现节点作为父节点。否，不做改动3.A*、D*算法步骤c)上步骤中新节点未造成任何改动，我们继续在OpenList中寻找新的节点。如图重复a),b)中的步骤，直到我们找到目标节点新节点3.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.人工势场法人工势场法的优缺点优点：便于低层的实时控制，在实时避障和平滑的轨迹控制方面，得到了广泛应用缺点：（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.三维路径规划