1第10 章度量路径规划(metric path planning) 2 目标与概述 结构空间及其表示法 基于图的规划器 基于波阵面的规划器 路径规划与反应式执行的交叉 小结 目标与概述度量路径规划(定量导航)拓扑路径规划(定性导航) 路径最优就意味着该路径是与所有可能的路径相比较得出的。度量路径规划器组成部分:表示部分(数据结构)和算法部分。规划器首先把环境按照适于路径规划的结构进行划分。? 结构空间及其表示法机器人和障碍物所在的物理空间称为环境空间(地图),将地图数字化,得到的一种数据结构称为结构空间。机器人通过结构空间来确定物体或自身的位姿(位置和姿态)。下图显示了现实物体到结构空间的转换。 牧场地图牧场地图把自由空间转化成凸多边形。路径规划问题变成求解机器人所穿过多边形的最优序列的问题。规划器假设机器人是完整性的,并把机器人看做一个点, 然后通过某些特征之间的线段来构造凸多边形。如图 , 取中点,形成无向图。 中任一条路径都有些据齿状,每个弯曲点都是路途点。一般使用路径松弛法,可以从路径中删掉大部分的锯齿。如图 存在的问题: ,使得机器人无法准确操作。 ,机器人无法修正地图。 7 广义 Voronoi 图法(Generalized Voronoi Graph) 广义 Voronoi 图(GVG) ,其基本思想是是产生与所有边界点等距离的线,叫做 Voronoi 边,边之间交汇的点称为 Voronoi 顶点, 。通过与所有障碍物均保持等距离的局部控制策略,机器入可以很容易地沿着 GVG 产生的路径前进。 正则网格法正则网格法是在环境空间上覆盖一个二维笛卡尔网格,如果区域中的物体位于某个网格单元上,这个网格单元就被标记为被占用,如图 . 缺陷: 即使物体仅仅占用部分单元网格,仍标记被占用,导致自由空间的浪费。 四叉树法( Quadtree )四叉树法是正则网格法的一个改进。在三维情况下的四叉树称为八叉树。 基于图的规划器 A搜索算法评估节点的可接受性的公式(或评价函数): (n) 表示加入节点 n所需的代价。.g(n) 表示从起始节点移动到节点 n的代价。.h(n) 表示从节点 n到目标节点的最小代价。下图 是应用这个公式的一个具体例子, 假设图 是由结构空间表示产生的图。?
度量路径规划-2015.7.17讲解 来自淘豆网m.daumloan.com转载请标明出处.
