移动机器人路径规划技术研究摘要: 研究移动机器人路径规划问题。针对传统移动机器人路径规划算法搜索时间长, 效率低, 寻优能力差等问题, 提出了一种基于粒子群算法的机器人路径规划方法。该方法首先采用神经网络描述机器人工作环境,在此基础上通过坐标变换建立新地图; 然后将机器人路径表示为粒子位置, 并以路径长度为粒子群的适应度值; 最后粒子之间的相互协作, 不断更新粒子位置和速度, 获得一条从起始点到目标点全局最优路径。在 MATLAB平台上对该方法进行了仿真, 实验结果表明, 基于粒子群的机器人路径规划方法提高了路径规划的计算效率和可靠性, 可应用于机器人的实时导航。关键词: 移动机器人; 粒子群算法; 路径规划0 引言移动机器人是集环境感知、动态决策、行为控制与执行的多功能于一体的综合性系统 ,目前广泛应用于航空航天、军事侦查、安全医疗和家庭服务等行业. 移动机器人的研究涉及到许多领域 ,包括光学、机械、微电子、自动控制和人工智能等,由于其作业环境的复杂性 ,决定了路径规划技术在移动机器人研究中的重要地位. 本文系统的阐述了移动机器人路径规划技术的研究现状和发展趋势1 路径规划路径规划是移动机器人研究领域的核心问题之一。所谓路径规划是指移动机器人在有障碍物的工作环境中, 搜索一条从起始状态到目标状态的最优或次最优路径, 使机器人在运动过程中能无碰撞地、安全绕过所有的障碍物, 同时所经过的路径较短。移动机器人路径规划方法可以分为全局路径规划和局部路径规划两种, 全局路径规划方法通常可以找到最优解,但首先需要知道准确的全局环境信息。到目前为止, 针对全局路径规划问题, 国内外学者对其进行了大量的研究, 并相应产生了许多方法。传统的路径规划算法有人工势场法和可视图法等。人工势场法的基本思想是将机器人看成处于一个虚拟力场中的“点”, 规划目标点对机器人有吸引力, 机器人对障碍物有排斥力, 在吸引力和排斥力的合力决定机器人运动方向。该方法具有实时性好、计算量小的特点, 但由于在规划过程中存在陷阱区, 很容易导致规划失败。可视图算法的基本思想是首先根据障碍物几何特征将工作空间中的可行区域映射为一个加权图, 然后利用图搜索策略在这个空间进行搜索, 根据图搜索算法的完备性理论, 完全能够规划出最优路径, 但由于图搜索算法比较复杂,可视图算法有潜在的组合爆炸危险。因此, 这些方法自身都存在一定的缺陷, 使得路径搜索出现计算量过大、效率不高、寻优能力差等难题, 不能满足路径规划的计算效率和可靠性要求。近年来, 出现了一些启发式路径规划算法如遗传算法和神经网络算法, 并得到了广泛的应用。但是遗传算法和神经网络法都存在局部最优的缺点, 导致寻优的路径质量不可靠。为了提高了移动机器人路径规划性能, 进一步丰富路径规划的方法, 需要不断的引入新的算法。粒子群优化算法 ( particle swarm optimization algorithm, PSO)是一种模拟鸟群时示的仿生算法, 具有算法简洁、易于实现和鲁棒性好等优点, 对种群大小不敏感, 收敛速度快, 非常适合于实时性要求较高、复杂的移动机器人路径规划求解问题。针对当前移动机器人路径规划求解问题中存在的一些问题, 将粒子群算法引入到路径规划中, 提出一种新的移动机器人路径规划算法。该方法将路径规划分为两步, 首先用自由空间法建立规划环境模型, 用图论方法寻求一条无碰次优路径, 然后用粒子群算法优化次优路径, 得全局最优路径。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 算法的一个巨大优势在于:其复杂程度主要取决于路径搜索的难度 ,而跟整个规划空间的维数和大小无关. 然而当规划的路径需要经过密集的障碍物或者需要经过狭窄的通道时 ,传统的 PRM 方法的效率变的低下 ,后来提出了一种采用分阶段混合采样策略的改进的 PRM 法 ,有效的解决了这一问题.2. 5 拓扑法拓扑法是由清华大学研究者提出的一种路径规划算法. 其基本思想是先将规划空间分为自由空间、半自由空间和障碍空间的子空间 ,然后搜索每个子空间及与其相连的子空间 ,计算彼此之间的连通性 ,如此则建立了拓扑网络. 路径规划是在拓扑网络上搜索从起始点到目标点的最短的路径 ,即判断拓扑网络的连通性 ,从而大大减小了高维空间路径规划的难度. 用拓扑法进行路径规划 ,一般不需要移动机器人的准确位置 ,这对于机器人移动过程中产生的位姿误差有很好的包容能力 ,但建立拓扑网略的过程非常复杂 ,特别是当空间中障碍物发生改变时 ,拓扑网的重构问题有待解决.3 局部路径规划局部路径规划 ,又称为动态或在线路径规划 ,作业环境部分未知或完全未知 ,主要方法有:人工势场法、模糊逻辑算法、遗传算法、蚁群算法、免疫算法等.3. 1 人工势场法人工势场法10是由 Khatib 和 Krogh 提出的一种虚拟力场法. 它的基本思想是将移动机器人所处的空间虚拟称一个存在力的场地 ,并且把这种力分为引力和斥力 ,移动机器人所受的引力是由目标点产生的 ,随距离的增大而减小 ,斥力是由障碍物产生的 ,并随距离的减小而增大 ,整个势场是引力和斥力的矢量叠加. 机器人沿着“势峰”间的“势谷”前进 ,从而绕过障碍物到达目标点. 人工势场法结构简单 ,便于底层的实时控制 ,且无需大量的计算 ,自动生成较光滑的路径 ,在实时避障和平滑轨迹控制方面得到了广泛的应用 ,但也存在着以下几个方面的缺陷:存在陷阱区域;通过狭窄通道时摆动;在障碍物前震荡;动态环境适应性差;求出的路径可能不是最优路径. 为了克服上述缺陷 ,已经研究出了一些改进方法 ,如重新定义势函数 ,减少或使之没有局部极小点;在局部极小点处引入一个“填平势场”来引导移动机器人走出局部极小点;还可以利用如模拟退火法、遗传算法、粒子群算法等搜索算法跳出局部极小点 .3. 2 模糊逻辑算法模糊逻辑算法是根据经验 ,通过查表来得到规划信息 ,实现局部路径规划. 由于模糊逻辑算法基于实施传感信息 ,在处理动态变化或者未知环境下的路径规划问题显示出巨大的优越性 ,具有较好的实时性 ,且克服了势场法容易产生局部极小值的问题 ,避开了传统算法中对环境信息依赖强的缺点 ,但对于模糊隶属函数以及模糊控制规则的设计 ,目前还没有系统的理论方法 ,主要靠经验 ,因此隶属函数和控制规则的设计成为实现模糊逻辑算法的关键.3. 3 遗传算法遗传算法是一种基于自然选择和群体遗传机理的搜索算法 ,它基于达尔文“物竞天择 ,适者生存”的进化原理 ,模拟了自然界的生存法则. 遗传算法是一种全局优化算法 ,其算法流程是:首先初始化路径种群 ,将路径个体表述为路径上一系列的点 ,并进行参数编码;然后对参数编码的字符串采用抽象出来的几个算子进行选择、复制、交叉、变异遗传操作;经过特定进化次数或者达到优化目标即停止进化 ,输出当前优的个体.遗传算法主要的优点是:1)遗传算法是一种多线程的搜索算法 ,可同时对多个可行解进行遗传操作 ,从而产生新的可行解 ,一定程度上避免了陷入局部极小点.2)整体搜索策略和优化计算不依赖于梯度信息 ,只需可行解目标函数的值 ,因而解决了一些其他优化算法无法解决的问题 ,避免了复杂的理论推导.遗传算法是一种多线程的搜索算法 ,可同时对多个可行解进行遗传操作. 文献17给出了一种基于粗糙集约简决策规则和删除冗余属性的方法 ,大大减小了遗传算法初始种群的规模 ,提高了规划效率.3. 4 蚁群算法蚁群算法是 20 世纪 90 年代意大利学者 M. Dorigo , V. Maniezzo , A. colorni 从生物进化的机制中受到启发 ,通过模拟自然界中蚂蚁搜索路径的行为而提出的. 其原理可表述为:蚂蚁在觅食途中会留下一种外激素 ,蚂蚁利用外激素与其他蚂蚁进行交流和合作. 经过某条路径的蚂蚁越多 ,外激素的强度就会越大 ,而蚂蚁择路偏向选择外激素强度大的路径. 蚁群算法的提出 ,最初是为了求解旅行商问题 ,近些年的研究发现 ,蚁群算法在求解复杂优化问题时具有优势 ,是一种新型的无启发式优化算法 ,具有较强的发现路径的能力.蚁群算法可使规划出的路径具有较强的鲁棒性 ,它是一种基于种群的分布式进化算法 ,具有并行性 ,易与其他启发式算法结合 ,从而改善算法的性能 ,但蚁群算法的研究刚刚起步 ,没有系统的分析方法和坚实的数学基础 ,参数的选择多靠试验和经验 ,计算时间长 ,实时性差 ,有待进一步的研究.3. 5 人工免疫算法人工免疫算法是模仿自然界生物免疫系统的一种仿生智能算法 ,是通过学习生物免疫系统的功能、原理及特征并