机器人路径规划方法综述

机器人原理与应用论文 题目 :机器人路径规划方法综述 学 院 : 信息科学与工程学院 专 业 : 控制科学与工程 班 级 : 研 132班 学 号 : 201304703039 学生姓名 : 张 梁

日 期 : 二○一四年五月 机器人路径规划方法综述

摘 要 :路径规划技术是机器人控制技术研究中的一个重要问题 , 目前的研究主要 分为全局规划方法和局部规划方法两大类。全局规划方法主要是以基于构形空 间的几何法和拓扑法为主;而局部规划方法主要是以基于直角坐标空间的人工 势场法为主。通过对机器人路径规划方法研究现状的分析,指出了各种方法的 优点及不足,并对其发展方向进行了展望。 关键词 :机器人;路径规划;人工势场;组合曲线;全局规划;局部规划 1 引 言

路径规划在自主移动机器人导航中起着重要作用,是指在有障碍物的环境 中规划一条从机器人的起始位置到目标位置的路径。移动机器人的路径规划是 机器人智能控制应用中的一项重要技术,是移动机器人导航技术中不可缺少的 重要组成部分 [1],路径规划是移动机器人完成任务的安全保障,同时也是移动 机器人智能化程度的重要标志 [2]。 机器人路径规划的研究起始于 20世纪 70年代,目前对这一问题的研究仍然 十分活跃,国内外学者作了大量工作 [3],提出了很多种路径规划的方法。比较 经典的方法有可视图法、切线图法、 Voronoi 图法、人工势场法、极坐标直方 图法、矢量场法、基于碰撞传感器的沿墙走法等。近十几年来,一些智能的方 法如模糊逻辑算法、神经网络、遗传算法等也用于路径规划。路径规划可分为: (1)全局路径规划:环境信息完全已知,根据环境地图按照一定的算法搜寻一条 最优或者近似最优的无碰撞路径,规划路径的精确程度取决于获取环境信息的 准确程度; (2)局部路径规划:环境信息完全未知或部分未知,根据传感器的信 息来不断地更新其内部的环境信息,从而确定出机器人在地图中的当前位置及 周围局部范围内的障碍物分布情况,并在此基础上,规划出一条从当前点到某 一子目标点的最优路径。 2 整体方法分析

多项式类型和三角函数类型的轨迹规划曲线是机器人系统常用的最基本, 最普遍曲线。但是随着生产技术的发展,对机器运动特性的要求不断提高,对 于轨迹规划曲线的要求也就越来越严格。机器人系统在一些场合下,对其轨迹 规划曲线不仅要求高阶导数连续,同时也要求具有良好的综合特性指标。单一 型

的轨迹规划曲线已经不能满足要求。因此,这就需要综合几种不同轨迹规划 曲线的特点,设计出一种具有良好综合特性的轨迹规划曲线,以便发扬各自的 优点和克服其缺点。通过几种不同函数组合在一起而设计出的轨迹规划曲线, 就是组合型的轨迹规划曲线。组合型的轨迹规划曲线是由分段函数组成的。在 各段函数的连接点处,需要建立临界条件,以便保证各分段函数在临界点处具 有相同的位移、速度、加速度。 3 路径规划

3.1 全 局路径规 划 3.1.1栅格分解法

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

拓扑法是由清华大学研究者提出的一种路径规划算法。其基本思想是先将 规划空间分为自由空间、半自由空间和障碍空间的子空间,然后搜索每个子空 间及与其相连的子空间,计算彼此之间的连通性,如此则建立了拓扑网络。路 径规划是在拓扑网络上搜索从起始点到目标点的最短的路径,从而大大减小了 高维空间路径规划的难度。用拓扑法进行路径规划,一般不需要移动机器人的 准确位置,这对于机器人移动过程中产生的位姿误差有很好的包容能力,但建 立拓扑网略的过程非常复杂,特别是当空间中障碍物发生改变时,拓扑网的重 构问题有待解决。 3.1.3 罚函数法

在机器人运行环境中因为有障碍物,使得机器人的路径规划成为一个有约 束的问题,惩罚函数法将这个有约束的问题转化为一系列无约束极小化问题, 再通过解决这些无约束问题获得原约束问题的最优解 [4]。 3.2 局部路径规划 3.2.1 人工势场法

人工势场法最早由 Khatib 提出 [5],该方法的基本思想是构造目标位置引力 场和障碍物周围斥力场共同作用的人工势场,搜索势函数的下降方向来寻找无 碰路径。具体方法是首先在机器人的运动空间中创建一个势场。该势场有引力 场和斥力场两部分组成,引力场方向指向目标点,斥力场方向指向远离障碍物

方向。整个势场势其引力部分和斥力部分的叠加,机器人就沿着合成的势场力

方向运动,绕开障碍物,向目标点运动。该法结构简单,便于低层的实时控制, 在实时避障和平滑的轨迹控制方面,得到了广泛应用。但是,由于势场法把所 有信息压缩为单个合力,这样就存在把有关障碍物分布的有价值的信息抛弃的 缺陷,且易陷入局部最小值 [6]。为解决局部极小值问题,已经研究出一些改进 算法,如 Sato 提出的 Laplace 势场法,改进算法是通过数学上合理定义势场方 程来保证势场中不存在局部极值 [7];还有一种改进就是当机器人陷入摆动状态 后,让机器人沿着斥力的法向量方向运动的沿墙走方法 [8]。 3.2.2 遗传算法

遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随 机、自适应搜索算法。它采用群体搜索技术,通过选择、交叉和变异等一系列 遗传操作,使种群得以进化,避免了困难的理论推导,直接获得问题的最优解。 其基本思想是:将路径个体表达为路径中一系列中途点,并转换为二进制串, 首先初始化路径群体,然后进行遗传操作,如选择、交叉、复制、变异,经过 若干代进化以后,停止进化,输出当前最优个体。遗传算法存在运算时间长、 路径在线规划困难、进化效果不明显等问题。 孙树栋等人用遗传算法完成了离散空间下机器人的路径规划 , 并获得了较好 的仿真结果。但是 , 该路径规划是基于确定环境模型的 , 即工作空间中的障碍物 位置是已知的、确定的。 在遗传算法的改进上 , 周明等人提出一种遗传模拟退火算法 , 利用遗传算法 与模拟退火算法相结合来解决机器人路径规划问题。有效地提高了路径规划的 计算速度 , 保证了路径规划的质量。 3.2.3 模拟退火算法

模拟退火算法依据固体退火原理,固体在加温时,内部粒子运动随温升增 强,变为无序状,再进行退火,粒子运动减弱并渐趋有序,最后达到稳定。把 机器人在未知环境中的运动看作是粒子的布朗运动,可以对其随机性的扰动应 用模拟退火算法来引导机器人向势能最小的方向运动,从而实现机器人在线的 路径规划。 3.2.4 蚁群算法

蚁群算法是 20世纪 90年代意大利学者 MDorigo , VManiezzo ,

Acolorni 从 生物进化的机制中受到启发,通过模拟自然界中蚂蚁搜索路径的行为而提出的。 其原理可表述为:蚂蚁在觅食途中会留下一种外激素,蚂蚁利用外激素与其他 蚂蚁进行交流和合作。经过某条路径的蚂蚁越多,外激素的强度就会越大,而 蚂蚁择路偏向选择外激素强度大的路径。蚁群算法是一种新型的无启发式优化 算法,具有较强的发现路径的能力。蚁群算法可使规划出的路径具有较强的鲁 棒性,它是一种基于种群的分布式进化算法,具有并行性,易与其他启发式算

法结合,从而改善算法的性能,但蚁群算法的研究刚刚起步,没有系统的分析 方法和坚实的数学基础,参数的选择多靠试验和经验,计算时间长,实时性差, 有待进一步的研究 [9]。 3.3 混合路径规划方法

混合路径规划方法是结合一种或两种算法的优点,相互之间取长补短,以 提高规划效率的方法。 L.II.Tsoukalas 等 [10]人提出一种用于半自主移动机器人 路径规划的模糊神经网络方法。所谓半自主移动机器人就是具有在人类示教基 础上增加了学习功能的器件的机器人。这种方法采用模糊描述来完成机器人行 为编码 , 同时重复使用神经网络自适应技术。由机器人上的传感器提供局部的环 境输入 , 由内部模糊神经网络进行环境预测 , 进而可以在未知环境下规划机器人 路径。 4 机器人路径规划的发展趋势 4.1 性能指标上不断提高

许多路径规划方法在完全已知环境中能得到令人满意的结果,但在未知环 境特别是存在各种不规则障碍的复杂环境中,由于环境信息的时刻变化,对机 器人的实时性提出了更高的要求,所以如何快速有效地完成机器人在复杂环境 中的导航任务仍将是今后研究的主要方向之一。 4.2 多移动机器人系统的路径规划

随着机器人系统应用的不断扩大,工作环境复杂度和任务的加重,对其要 求不再局限于单个机器人,多移动机器人路径规划已成为新的研究热点。在动 态环境中单个机器人的路径规划与多机器人的合作需要很好统一。此领域的难 点在于多机器人之间的协调和避碰前进,因此,在协调多机器人更好实现实时 规划方面,还有很大的研究空间。 4.3 多传感器信息融合用于路径规划

单传感器难以保证输入信息准确与可靠,多传感器所获得的信息具有冗余 性、互补性、实时性和低代价性,且可以快速并行分析现场环境。 4.4 更加智能化的仿生算法

智能仿生算法的应用,赋予了机器人一定的智能,但对于含有动态障碍物 的复杂环境显得不够,特别是在有效地避免机器人陷入局部最优路径方面。如

何使机器人及时地知道自己已经陷入局部最优,甚至提前预知将陷入局部最优 而采取措施加以避免,需要赋予机器人更多智能。 5 总结

机器人的全局路径规划和局部路径规划并没有本质上的区别,很多方法既 适用于全局规划又可用于局部规划。无论采用哪种方法进行路径规划,基本上 都要遵循以下两步:(1)环境建模; (2)搜索路径。 移动机器人的路径规划方法在完全已知环境中能得到令人满意的结果,但 在未知环境特别是存在各种不规则障碍物的复杂环境中,却很可能失去效用

[11]。 所以如何快速有效地完成移动机器人在复杂环境中的导航任务仍将是今后研究 的主要方向之一。lzq7IGf02E 另外,随着空间探测和无人战争的发展需要,机器人的研究也越来越注重 于在崎岖地形和存在大量障碍物的复杂环境中自主导航,为了满足这种要求, 路径规划技术将会向着高维自由度机器人、多机器人协调、动态未知环境中的 规划发展,这些都有待于进一步深入的探索和研究。zvpgeqJ1hk 参考文献:

[1] A. Martinez, E. Tunstel, M. Jamshidi. Collision avoidance of mobile robots using fuzzy logic, Robotics and Manufacturing, 1994,7(4):193-198NrpoJac3v1 [2] 吴涛 . 移动机器人避障与路径规划研究 . 华中科技大学硕士论文 . 2010:12-18 [3] R. Huq, G. K. I. Mann, R. G. Gosine. Mobile robot navigation using motor schema and fuzzy context dependent behavior modulation, Applied Soft Computing, 2008,8(1): 422-4361nowfTG4KI [4] 张泽建,吴玉香.一种基于罚函数的机器人路径规划方法.计算机测量与控 制, 2006.(01):104-106.fjnFLDa5Zo [5]O. Khatib. Real-time obstacle avoidance for manipulators and mobile robots, International Journal of Robotics Research,1986,5(1):90-98tfnNhnE6e5 [6] 张建英,赵志萍,刘暾 . 基于人工势场法的机器人路径规划 [J].哈尔滨工业大 学学报, 2006 (8).HbmVN777sL [7] 林丹 , 李敏强 , 冠纪淞 . 基于遗传算法求解约束优化问题的一种算法 . 软件学报 ,

2001,12(4):628-632

[8] 竺志超 , 李志祥 . 引纬机构的遗传算法优化设计 . 纺织学报 , 2002,23(3):34-35 [9] 张美玉,黄翰,郝志峰,杨晓伟.基于蚁群算法的机器人路径规划.计算机 工程与应用. 2005, 25, (6):50-54.V7l4jRB8Hs [10] TsoukalasL.II,Houstis EN,Jones GV.Neurofuzzy motion planners for intelligent robots[J].Journal of Intelligent and Robotic Systems,1997,19:339-356.83lcPA59W9 [11] S. K. Pradhan, D. R. Parhi, A. K. Panda. Navigation of multiple mobile robots using rule-based-neuro-fuzzy technique,

International Journal of Computational Intelligence, 2006,3(2):142-152mZkklkzaaP