度量路径规划-2015717

1、2022-6-81第10章 度量路径规划(metric path planning)2 10.1 目标与概述 10.2 结构空间及其表示法 10.3 基于图的规划器 10.4 基于波阵面的规划器 10.5 路径规划与反应式执行的交叉 10.6 小结310.1 目标与概述410.2 结构空间及其表示法 机器人和障碍物所在的物理空间称为环境空间(地图),将地图数字化，得到的一种数据结构称为结构空间。机器人通过结构空间来确定物体或自身的位姿(位置和姿态)。 下图显示了现实物体到结构空间的转换。510.2.1 牧场地图 牧场地图把自由空间转化成凸多边形。路径规划问题变成求解机器人所穿过多边形的最优序列

2、的问题。 规划器假设机器人是完整性的，并把机器人看做一个点，然后通过某些特征之间的线段来构造凸多边形。如图10.3,取中点，形成无向图。 6图10.3中任一条路径都有些据齿状,每个弯曲点都是路途点。一般使用路径松弛法,可以从路径中删掉大部分的锯齿。如图10.4存在的问题：1.计算复杂2.采用人为标志来决定多边形的边界，使得机器人无法准确操作。3.先验地图和现实环境不相符时，机器人无法修正地图。 710.2.2 广义Voronoi图法(Generalized Voronoi Graph)广义Voronoi图(GVG),其基本思想是是产生与所有边界点等距离的线,叫做Voronoi边,边之间交汇的点

3、称为Voronoi顶点,如图10.5。通过与所有障碍物均保持等距离的局部控制策略,机器入可以很容易地沿着GVG产生的路径前进。810.2.3 正则网格法 正则网格法是在环境空间上覆盖一个二维笛卡尔网格,如果区域中的物体位于某个网格单元上,这个网格单元就被标记为被占用,如图10.6.缺陷：即使物体仅仅占用部分单元网格,仍标记被占用,导致自由空间的浪费。910.2.4 四叉树法(Quadtree)四叉树法是正则网格法的一个改进。在三维情况下的四叉树称为八叉树。1010.3 基于图的规划器11节点A开始，当前只有B和C可供选择。计算节点B和C的可接受性：f(B)=g(B)+h(B)=1+2.24=3

4、 .24f(C)=g(C)+h(C)=1+1=2显然，f(C)f(B),选择从A到C这条路径。 这里假设每一个节点的h(n)都是已知的，因此算法必须递归地找出h(n)的正确值，这就需要对每一个节点进行计算。1213从D向后，可能的选择E、F：f*(E)=g*(E)+h*(E)=2.8f*(F)=g*(F)+h*(F)=3.4显然E是最佳选择。A*算法优点:可用于所有结构空间描述法局限性：很难用于除了距离之外还需考虑其他因素的路径规划问题。1410.5 基于波阵面的规划器基本原理:波阵面把结构空间视为一种导热物质，如果存在一个路径，热从起始节点向目标节点传导，如图所示，热量将最终达到目标节点。1516波阵面传播法可以处理地形。图10.12中的例子使用的是Trulla规划算法。1710.6 路径规划与反应式执行的交叉度量路径的反应式执行时有两个难题：1.子目标困扰是指机器人过分追求精确到达子目标位置而花费太多的时间和能量的情况。2.缺乏重新规划的机会。反应式的执行方式事实上缺乏抓住机会改进路径的能力。两类方法:D*算法(A*算法的变异)和Trulla算法的扩展。两种算法都从先验地图开始,计算每个位置到目标的最优路径。18如图10.13，机器人在避障到达新目标点后，不用重新规划就可以重新确定最优路径的走向。19Trulla采用预期路径向量和实际