7机器人运动规划.ppt

机器人运动规划 轨迹规划 概要 问题提出 基本方法： 路线图 可见图 Voronoi图 区域划分 势场 方法扩展 采样技术 在线算法 机器人运动规划 有哪些信誉好的足球投注网站，如A*、随机有哪些信誉好的足球投注网站等方法的应用 几何构型中有哪些信誉好的足球投注网站 空间推理 挑战： 连续状态空间 高维空间 自由度 一个机器人的几何构形是由p个自由度（DOF）来定义的。 假设p个DOF，一个机器人的几何构形A是由p个变量来定义的：A(q)，q={q1,…,qp} 例子： 棱柱（平移）DOF：qi是沿某方向的平移量。 旋转DOF ：qi是绕某轴的旋转量。 示例 示例 构形空间（C空间） 构形空间C=机器人合法构形的q值的集 定义可能参数的集（有哪些信誉好的足球投注网站空间）和允许路径的集 自由空间：点机器人 Cfree={A(q)不与障碍物交叉的参数的集} 例子： 对2D平面上的一个点机器人：R2减去障碍物区 自由空间：对称机器人 自由空间：对称机器人 C=R2，因为取向无关 以机器人半径来扩大障碍物尺寸，则该问题可简化为点机器人问题 自由空间：非对称机器人 构形空间是3D（x,y,?） 对每个?值，需对障碍物实施一个相应的（不同的）扩张 仍可通过扩张障碍物，把问题简化为点机器人问题 更复杂的C空间 在所有场合下，通过扩张障碍物，就把问题简化为寻找一个点穿越构形空间的路经 运动规划问题 轨迹规划：对求解问题的空间几何轨迹及其生成进行规划 A=在2D或3D中有p个自由度的机器人 CB=障碍物集 如果不导致机器人与障碍物交叉，则构形q是合法的。 已知起始与最终构形(qstart, qgoal)，寻找一个从qstart到qgoal的合法构形的连续序列。 如果没找到路径，则报告失败。 形式化保证：普适钢琴搬动者问题 形式化结论（但在实际算法上不太有用）： p：C的维数 m：用来描述Cfree的多项式的数目 d：多项式的最高次方 如路径存在，则能按p的指数时间，以及m与d的多项式时间来找到该条路径。 处理方法 基本方法： 路线图 可见图 Voronoi图 区域划分 势场 扩展 采样技术 在线算法 注：在所有场合，先将在连续C空间中难处理的问题简化为在离散空间中可处理的问题。则可以使用已知的技术，如，A*，随机有哪些信誉好的足球投注网站等。 路线图 路线图：自由空间中的一维曲线网络 一般思路： 避免有哪些信誉好的足球投注网站整个空间 预先计算一幅路线图，呆在路线图所指明的道路上能保证规避障碍物。 在路线图上寻找一条qstart到达qgoal的路径。 可见图 无障碍时，最佳路径就是qstart与qgoal之间的直线 可见图 多边形障碍物时，最短路径似乎是一系列连接障碍物顶点的直线段。 总对吗？ 可见图 可见图G=障碍物顶点(外加上qstart和qgoal )之间无遮挡线段的集。 如果从一结点P可看见另一结点P’，则将P与P’相连接。 解=可见图中的最短路径。 扫描算法 绕着每个顶点，扫动一条源于该点的射线。 记录那些到达其它可见顶点的线段。 复杂性 构建可视图是昂贵的： N=多边形障碍物的顶点总数 简单：O(N3)，因为有O(N2)对顶点，多边形障碍物有O(N)条边 扫描：O(N2logN)，因为每个顶点要访问(N-1)个其它顶点，并且在每次访问中，要依据在该方向上的障碍物序列来确定其可见性，开销为O(logN)。 最佳：O(N2)，因为每个顶点都有一条从-?/2移到?/2的扫描线，而所有扫描线都同时移动（旋转树）。 可见图：弱点 最短路径，但： 试着尽可能靠近障碍物 任何执行错误将引起碰撞 2D以上空间中很复杂 只要能找到一条安全路径，可不严格介意最佳性。因为规避障碍比寻找最短路径更重要。 需要定义其它类型的路线图。 Voronoi图 已知平面上一组数据点 着色整个面，使得平面上任何点的颜色与其最近邻点的颜色是相同的。 Voronoi图 Voronoi图=用来划分不同颜色区域的线段集 线段（边沿）=与两个数据点等距离的点 顶点=与两个以上数据点等距离的点 Voronoi图 Voronoi图=划分不同颜色区的线段集 线段（边沿）=与两个数据点等距离的点 顶点=与两个以上数据点等距离的点 Voronoi图 复杂性： 时间：O(NlogN)，等同于给N个点排序 空间：O(N) 非点的Voronoi图 边是直线段与二次曲线段的组合 直线边：与两线等距的点 曲线边：与一个角点和一条线等距的点 Voronoi图（多边形） Voronoi图（多边形） 主要性质：Voronoi图中的边点离障碍物最远。 思路：沿着Voronoi图中的边构建一条由qstart到qgoal的路径。 把Voronoi图作为路线图。 Voronoi图：规划 寻找Voronoi图中qstart的最接近点q*start 寻找Voronoi图中qgoal的最接近点q*goal 计算Voronoi图中从q*sta