第5期(总第156期)2009年10月机械工程与自动化M ECHAN I CAL EN G I N EER I N G &　AU TOM A T I ON N o 15O ct 1文章编号:167226413(2009)0520194203机器人路径规划方法的研究李爱萍,李元宗(太原理工大学机械工程学院,山西　太原　030024)摘要:路径规划技术是机器人学研究领域中的一个重要部分。

目前的研究主要分为全局规划方法和局部规划方法两大类。

通过对机器人路径规划方法研究现状的分析,指出了各种方法的优点及不足,并对其发展方向进行了展望。

关键词:机器人;全局规划;局部规划中图分类号:T P 242 文献标识码:A收稿日期:2009201207;修回日期:2009204218作者简介:李爱萍(19792),女,山西晋中人,在读硕士研究生。

0　引言路径规划技术是机器人学研究领域中的一个重要部分。

机器人的最优路径规划就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短等),在其工作空间中找到一条从起始状态到目标状态的最优路径。

根据对环境信息的掌握程度不同,路径规划可分为:①全局路径规划:环境信息完全已知,根据环境地图按照一定的算法搜寻一条最优或者近似最优的无碰撞路径,规划路径的精确程度取决于获取环境信息的准确程度;②局部路径规划:环境信息完全未知或部分未知,根据传感器的信息来不断地更新其内部的环境信息,从而确定出机器人在地图中的当前位置及周围局部范围内的障碍物分布情况,并在此基础上,规划出一条从当前点到某一子目标点的最优路径。

1　全局规划方法111　栅格法栅格法是目前研究最广泛的路径规划方法之一。

该方法将机器人的工作空间分解为多个简单的区域(栅格),由这些栅格构成一个显式的连通图,或在搜索过程中形成隐式的连通图,然后在图上搜索一条从起始栅格到目标栅格的路径。

一般路径只需用栅格的序号表示。

但栅格的划分直接影响其规划结果,如果栅格划分过大,环境信息储藏量小,分辨率下降,规划能力就差;栅格划分过小,规划时间长,而且对信息存储能力的要求会急剧增加。

112　可视图法可视图法中的路径图由捕捉到的存在于机器人一维网络曲线(称为路径图)自由空间中的节点组成。

路径的初始状态和目标状态同路径图中的点相对应,这样路径规划问题就演变为在这些点间搜索路径的问题。

要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,即直线是“可视的”。

然后采用某种方法搜索从起始点到目标点的最优路径,搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。

该法能够求得最短路径,但需假设忽略机器人的尺寸大小,使得机器人通过障碍物顶点时离障碍物太近甚至接触,并且搜索时间长。

113　拓扑法拓扑法将规划空间分割成具有拓扑特征的子空间,根据彼此的连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。

拓扑法的基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。

其优点在于利用拓扑特征大大缩小了搜索空间,其算法的复杂性仅依赖于障碍物数目,在理论上是完备的;而且拓扑法通常不需要机器人的准确位置,对于位置误差也就有了更好的鲁棒性。

缺点是建立拓扑网络的过程相当复杂,特别是在增加障碍物时如何有效地修正已经存在的拓扑网是有待解决的问题。

114　自由空间法自由空间法采用预先定义的广义锥形或凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,通过搜索连通图来进行路径规划。

自由空间的构造方法是:从障碍物的一个顶点开始,依次作其他顶点的连接线,删除不必要的连接线,使得连接线与障碍物边界所围成的每一个自由空间都是面积最大的凸多边形,连接各连接线的中点形成的网络图即为机器人可自由运动的路线。

其优点是比较灵活,起始点和目标点的改变不会造成连通图的重构。

缺点是复杂程度与障碍物的多少成正比,且有时无法获得最短路径。

115　神经网络法人工神经网络是由大量神经元相互连接而形成的自适应非线性动态系统。

对于大范围的工作环境,在满足精度要求的情况下,用神经网络来表示环境可以取得较好的效果。

神经网络在全局路径规划的应用,将障碍约束转化为一个惩罚函数,从而使一个约束优化问题转化为一个无约束最优化问题,然后以神经网络来描述碰撞惩罚函数,进行全局路径规划。

虽然神经网络在路径规划中有学习能力强等优点,但整体应用却不是非常成功,主要原因是智能机器人所遇到的环境是千变万化的、随机的,并且很难以数学的公式来描述。

2　局部路径规划211　人工势场法人工势场法是由Khatib提出的一种虚拟方法,其基本思想是将机器人在未知环境中的运动视为一种虚拟人工受力场中的运动,目标点对机器人产生引力,障碍物对机器人产生斥力,最后通过求合力来控制机器人的运动。

该法结构简单,便于底层的实时控制,在实时避障和平滑的轨迹控制方面,得到了广泛应用;其不足在于存在局部最优解,因而可能使机器人在到达目标点之前就停留在局部最优点。

212　模糊逻辑控制算法模糊逻辑方法利用反射式机制,将当前环境中的障碍物信息作为模糊推理机的输入,推理机输出机器人期望的转向角和速度等。

该方法在环境未知或发生变化的情况下,能够快速而准确地规划机器人的局部路径,对于要求有较少路径规划时间的机器人是一种很好的规划方法。

但是,当障碍物数目增加时,该方法的计算量很大,影响规划结果,而且其只利用局部信息做出快速反应,较容易陷入局部最优。

213　遗传算法遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。

它采用群体搜索技术,通过选择、交叉和变异等一系列遗传操作,使种群得以进化,避免了困难的理论推导,直接获得问题的最优解。

其基本思想是:将路径个体表达为路径中一系列中途点,并转换为二进制串,首先初始化路径群体,然后进行遗传操作,如选择、交叉、复制、变异,经过若干代进化以后,停止进化,输出当前最优个体。

遗传算法存在运算时间长、路径在线规划困难、进化效果不明显等问题。

214　蚁群优化算法根据蚁群移动过程中途经各点周围的距离启发式信息概率,产生多条从起点到终点的可行移动路径,每一条路径代表了一只蚂蚁的爬行轨迹。

对所产生的每一条可行移动路径,分别计算路径的长度和对应信息素的增量,再采用设计的信息素轨迹更新函数对路径上各点所对应的信息素进行更新,将蚂蚁所走的弯曲路径逐渐拉直为一条由直线段连接的可行路径,并将此可行路径与记录的目前最短路径进行比较。

如果路径长度更小,则用该路径替换最短路径,并对路径上的各点信息素采用设计的信息素轨迹更新函数进行更新,综合使用当前点周围的距离启发式信息概率和给予信息素轨迹的转移概率产生下一条由起点到终点的可行路径,往复循环。

如果当前时刻已达到预先设定的终止时刻,则将当前路径作为最短路径输出。

215　粒子群算法粒子群优化算法是一种进化计算技术,由Eberhart博士和Kennedy博士发明,源于对鸟群捕食行为的研究。

在粒子群优化算法中,每个优化问题的解都是搜索空间中的一只鸟,我们称之为“粒子”。

所有的粒子都有一个由被优化的函数决定的适应值,每个粒子还有一个速度决定它们飞翔的方向和距离,然后粒子们就追随当前的最优粒子在解空间中搜索。

粒子群优化算法初始化为一群随机粒子(随机解),然后通过叠代找到最优解,在每一次叠代中,粒子通过跟踪两个“极值”来更新自己。

第一个极值就是粒子本身所找到的最优解,这个解叫做个体极值;另一个极值是整个种群目前找到的最优解,这个极值是全局极值。

另外也可以不用整个种群而只是用其中一部分作为粒子的邻居,那么在所有邻居中的极值就是局部极值。

在找到这两个最优值后,粒子根据相关公式来更新自己的速度和位置。

216　滚动窗口法基于滚动窗口的路径规划算法的基本思路是:首先进行场景预测,在滚动的每一步,机器人根据其探测到的局部窗口范围内的环境信息,用启发式方法生成局部子目标,并对动态障碍物的运动进行预测,判断机器人行进是否可能与动态障碍物相碰撞;其次机器人根据窗口内的环境信息及预测结果,选择局部规划算法,确定向子目标行进的局部路径,并依所规划的局部路径行进一步,窗口相应向前滚动;然后在新的滚动窗口产生后,根据传感器所获取的最新信息,对窗口内的环境及障碍物运动状况进行更新。

该方法放弃了对全局最优目标的过于理想的要求,利用机器人实时测得的局部环境信息,以滚动方式进行在线规划,具有良好的避碰能力。

但存在着规划的路径是否最优的问题,即存在局部极值问题。

・591・　2009年第5期 李爱萍,等:机器人路径规划方法的研究3　机器人路径规划的发展趋势311　性能指标上不断提高许多路径规划方法在完全已知环境中能得到令人满意的结果,但在未知环境特别是存在各种不规则障碍的复杂环境中,由于环境信息的时刻变化,对移动机器人的实时性提出了更高的要求,所以如何快速有效地完成移动机器人在复杂环境中的导航任务仍将是今后研究的主要方向之一。

312　多移动机器人系统的路径规划随着机器人系统应用的不断扩大,工作环境复杂度和任务的加重,对其要求不再局限于单个机器人,多移动机器人路径规划已成为新的研究热点。

在动态环境中单个机器人的路径规划与多机器人的合作需要很好统一。

此领域的难点在于多机器人之间的协调和避碰前进,因此,在协调多机器人更好实现实时规划方面,还有很大的研究空间。

313　多传感器信息融合用于路径规划单传感器难以保证输入信息准确与可靠,多传感器所获得的信息具有冗余性、互补性、实时性和低代价性,且可以快速并行分析现场环境。

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

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

参考文献:[1]　李士勇.蚁群算法及其应用[M ].哈尔滨:哈尔滨工业大学出版社,2004.[2]　邢军,王杰.神经网络在移动机器人路径规划中的应用研究[J ].微计算机信息,2005(22):1102111,153.[3]　樊晓平,李双艳,陈特放.基于新人工势场函数的机器人动态避障规划[J ].控制理论与应用,2005,22(5):7032707.Study on Robot Path Plann i ng M ethodL I A i -p i ng ,L IY uan -zong(Co llege of M echanical Engineering,T aiyuan U niversity of T echno logy,T aiyuan 030024,Ch ina )Abstract :Path p lanning techno logy is one of the mo st i m po rtant research field in robo tics ,w h ich is m ainly divided into tw o parts :O ne is global p lanning app roach ,and the o ther is local p lanning app roach .By analyzing the p resent conditi on of robo t path p lanning ,th is paper persents the advantages and disadvantages of the algo rithm s w h ich are commonly used ,and po ints out the develop ing p ro spect of robo t path p lanning .Key words :robo t ;global p lanning ;local p lanning(上接第193页)(2)对于PDC 使用性能要求较高时,采用真空扩散焊不仅能保持工件的几何尺寸和形状精度,而且可获得强度高、热稳定性好、抗震性好的优良接头。