移动机器人路径规划技术研究(2)

洁、易于实现和鲁棒性好等优点, 对种群大小不敏感, 收敛速度快, 非常适合于实时性要求较高、复杂的移动机器人路径规划求解问题。针对当前移动机器人路径规划求解问题中存在的一些问题, 将粒子群算法引入到路径规划中, 提出一种新的移动机器人路径规划算法。该方法将路径规划分为两步, 首先用自由空间法建立规划环境模型, 间的线段不穿过障碍物 ,即称直线是可视的 ,如此生成的图称之为可视图. 由于可视图中所有线段均“可视”,所以搜索最优路径的问题就转化为通过这些“可视”的线段从起始点到目标点最短距离的问题 ,还可以通过优化算法来删除一些不必要线段以简化视图 ,提高搜索效率. 用可视图法对移动机器人进行路径规划 ,由于忽略了用图论方法寻求一条无碰次优路径, 然后用粒子群算法优化次优路径, 得全局最优路径。

2 全局路径规划

全局路径规划 ,又称为静态或离线路径规划 ,作业的环境信息完全已知 ,主要方法有:栅格法、可视图法、链接图法、概率路径图法、拓扑法等. 2. 1 栅格法

栅格法是由 W. E. Hovcden 在 1968 年提出的. 栅格法将机器人的工作空间分解成一系列具有二值信息的网格单元 ,多数情况下采用四叉树或八叉树来表示 ,通过启发式优化算法搜索安全路径. 在栅格法中 ,栅格大小的选取将直接影响算法的性能. 栅格选的小 ,环境的分辨率就高 ,在密集障碍物或狭窄通道中发现路径的能力强 ,但环境信息的储存量大 ,规划时间长 ,降低了系统的实时性;栅格选的大了 ,环境信息储存量小,决策速度快 ,抗干扰能力强 ,但环境的分辨率低 ,在相应环境中发现路径的能力变差. 一般来说选定的栅格大小通常与机器人的移动步长相适应. 栅格法用栅格记录规划空间信息 ,其一致性和规范性使得空间中邻接关系简单化 ,在赋予环境中每个栅格一个通行因子后 ,路径规划问题就变成寻求两个栅格间最优路径问题. 常用的启发式搜索算法有 A 3 算法和 D 3 算法. 2. 2 可视图法

可视图法的基本思想是将机器人视为一点 ,然后把机器人起始点、目标点和多边形障碍物的所有顶点用线段进行组合连接. 如果起始点与障碍物顶点之间、目标点与障碍物顶点之间以及障碍物与障碍物顶点之

机器人尺寸 ,易造成机器人通过障碍物时与障碍物的摩擦甚至碰撞,且该方法缺乏灵活性,不能解决障碍物为圆形的路径规划问题 ,也不适用于三维及以上空间. 2. 3 链接图法

链接图法用于移动机器人的路径规划基于以下两点假设:(1)移动机器人可视为在二维平面中运动 ,机器人用点来表示;(2)规划环境的边界及障碍物可用凸多边形描述.链接图的构造方法是:

1)依次连接所有障碍物顶点 ,做不与障碍物交叉的链接线 ,并删除一些没有必要的链接线 ,保证链接线与障碍物边界所围的每个自由空间是面积最大的凸边形.

2)设置各链接线的中点为可能的路径点 ,并将机器人的起始点和目标点链接到所有可能的路径点上.用链接图法进行路径规划具有灵活多变的特点 ,起始点和目标点的改变不容易造成连通图的重构;算法 的复杂程度与障碍物的数量成正比 ,而且并不是在任何情况下都能获得最短路径. 2. 4 概率路径图法

概率路径图法(PRM)是 90 年代初期由 M. H. Overmars , P. Svestka 等人提出 ,该算法通过在构型空间中随机采样构建 Roadmap 图 ,然后通过查询得到移动机器人的路径规划序列. PRM 算法的 Roadmap 图是以某种概率技术来构造的 ,这跟以前的 Roadmap 图方法以确定方式构造的形式有很大的不同. 算法通过在构型空间中进行采样 ,对采样点进行碰撞检测 ,测试相邻采样点是否连接来表示路径图的连通性. PRM 算法的一个巨大优势在于:其复杂程度主要取决于路径搜索的难度 ,而跟整个规划空间的维数和大小无关. 然而当规划的路径需要经过密集的障碍物或者需要经过