机器人路径规划方法的研究进展与趋势
朱明华,王霄,蔡兰
(江苏大学机械工程学院,江苏镇江212013)
摘要:对机器人路径规划的研究进行了概括和总结,阐述了机器人全局路径规划方法、局部路径规划方法及混合方法的研究现状、特点和主要成果,指出了其今后的发展方向及研究重点。
关键词:机器人;遗传算法;路径规划;粗糙集
中图分类号:T P242 文献标识码:A 文章编号:1001-3881(2006)3-005-4
R esearch P rogress and Future Develop m ent on Path P lanni n g for Robot
Z HU M inghua,WANG X iao,CA I Lan
(M echanical Eng i n eering Institute,Jiangsu Un i v ersity,Zhenjiang Jiangsu212013,China) Abstrac t:T he research of robo t pa t h plann i ng w as s umm arized,the research sta t us quo,character i stic and ma i n producti on of robo t g l obal path p l ann i ng m ethod,l oca l path p l ann i ng m ethod and hybr i d m ethod were expatiated,its deve l op m ent d irec tions and study f o cus w ere po i nted out.
K eyword s:R obot;G enetic a l gor it hm s;P ath p lann i ng;R ough set
路径规划技术是机器人研究领域中的一个重要分支,是机器人导航中最重要的任务之一。蒋新松在文献[1]中为路径规划作出了这样的定义:路径规划是自治式移动机器人的一个重要组成部分,它的任务就是在具有障碍物的环境内按照一定的评价标准,寻找一条从起始状态(包括位置和姿态)到达目标状态(包括位置和姿态)的无碰路径。障碍物在环境中的不同分布情况当然直接影响到规划的路径,而目标位置的确定则是由更高一级的任务分解模块提供的。目前,根据对环境的掌握情况,机器人的路径规划问题可以大致分为二大类:基于环境先验信息的全局路径规划;基于不确定环境的传感器信息的局部路径规划。
1 全局路径规划方法(G lobal Pat h Plann i n g)
依据已获取的全局环境信息,给机器人规划出一条从起点至终点的运动路径。规划路径的精确程度取决于获取环境信息的准确程度。全局路径规划规划方法通常可以寻找最优解,但需要预先知道准确的全局环境信息。通常该方法计算量大,实时性差,不能较好地适应动态非确定环境。基于环境建模的全局路径规划的方法主要有:自由空间法、构型空间法和栅格法等。
1 1 自由空间法(Free Space Approach)
自由空间法采用预先定义的如广义锥形[2]和凸多边形[3]等基本形状构造自由空间,并将自由空间表示为连通图,然后通过搜索连通图来进行路径规划,此方法比较灵活,即使起始点和目标点改变,也不必重构连通图,但是算法的复杂程度与障碍物的多少成正比,且不能保证任何情况下都能获得最短路径。因而该方法仅适用于路径精度要求不高,机器人速度不快的场合。按照划分自由空间方法的不同又可分为:凸区法、三角形法、广义锥法。
1 2 构型空间法
为了简化问题,通常将机器人缩小为一点,将其周围的障碍物按比例相应地进行拓展,使机器人在障碍物空间中能够任意移动而不与障碍物及其边界发生碰撞。目前研究比较成熟的有可视图法[4]和优化算法(如D ijkstra法[5]、A*搜索算法[6]等)。
1 2 1 可视图法(V-G r aph)
通过起始点和目标点及障碍物的顶点在内的一系列点来构造可视图。连接这些点使某点与其周围的某可视点相连,即要求机器人和障碍物各顶点之间、目标点和障碍物各顶点以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,也即直线是可视的。从而搜索最优路径的问题就转化为经过这些可视直线从起始点到目标点的最短距离问题。
1 2 2 优化算法(Optm i ization A l gorit hm)
优化算法可以删除一些不必要的连线以简化可视图,从而缩短搜索时间,求得最短路径。但是,优化算法缺乏灵活性,一旦起点和目标点改变,就必须重构可视图,并且搜索效率也较低。
1 3 栅格法(Grids)
栅格法[7]将机器人的工作环境分解成一系列具有二值信息的网格单元,并假设工作空间中障碍物的位置和大小已知且在机器人运动过程中不会发生变化。用尺寸相同的栅格对机器人的二维工作空间进行规划,栅格大小以机器人自身的尺寸为准。若某一栅格范围内不含任何障碍物,则称此栅格为自由栅格;反之,称为障碍栅格。这样,自由空间和障碍物均可表示为栅格块的集成。栅格的表识方法有两种:直角坐标法和序号法。直角坐标法如图1所示,以栅格阵左上角为坐标原点,水平向右为X轴正方向,竖直向
下为Y轴正方向,每一栅格区间对应坐标轴上的一个单位长度。因此,区间上的栅格与直角坐标(x, y)一一对应;序号法如图2所示,按从左到右,从上到下的顺序,从栅格阵左上角第一个开始,给每个
栅格一个序号,
序号与栅格块也一一对应。
图1 直角坐标法 图2 序号法
栅格法以栅格为单位记录环境信息,栅格大小对环境信息存储量的大小和规划时间的长短有着重要影响,栅格划分大了,环境信息存储量小,规划时间短,但分辨率就低;反之,虽然分辨率高了,但规划时间长。
2 局部路径规划方法(Loca lPath P lann i n g)
局部规划方法侧重考虑机器人探知的当前局部环境信息,这使机器人具有较好的避碰能力。现有的不少移动机器人路径规划方法都采用局部方法,其规划仅依靠传感系统实时感知的信息。与全局规划方法相比,局部规划更具实时性和实用性;对动态环境具有较强适应能力;其缺点是由于仅依靠局部信息,有时会产生局部极值点或振荡,无法保证机器人能顺利地到达目标点。
2 1 人工势场法(A rtific ial Potentia lF ield)
人工势场法[8]最早是由Khatib和K rogh提出的一种虚拟力法。在K hati b研究机器人手臂在笛卡儿空间中如何直接由任务相关的参数、运动、受力来控制其运动的问题中,K r ogh引入了一个重要的概念:广义势场(Generalized F iel d),即既考虑位置X,又考虑速度V=X。常用的有以下几种势场:牛顿型势场、圆形对称势场、超四次方势场、调和势场及虚拟力场。
在人工势场中,障碍物被看作斥力场,目标被看作引力场,所以障碍物对机器人产生斥力,目标对机器人产生引力,通过求引力和斥力的合力来控制机器人的运动。
人工势场法结构简单,计算量小,实时性好。因而广泛应用于实时避障和平滑轨迹控制方面。但是在局部最优解的问题上容易产生死锁现象(D ead Lock)现象[9],从而可能导致机器人陷入局部最优点。
2 2 遗传算法(Genetic A lgorith m s)
遗传算法是一种多点搜索算法,也是目前机器人路径规划研究中应用较多的一种方法。由于遗传算法的整体搜索策略和优化计算不依赖于梯度信息,且作为并行算法其隐并行性适用于全局搜索,所以解决了其它一些算法无法解决的问题。国内外很多专家、学者等在这方面作了大量研究,并取得了很多成果。
孙树栋等[10]实现了离散空间下移动机器人路径规划新方法,该方法采用栅格序号作为个体的编码形式,与传统的二进制编码方法相比,具有编码长度短、易于进行遗传操作等优点。在该方法中,提出了间断无障碍路径概念,引入插入和删除算子,方便了遗传算子的实现,保证了路径的连续和可行性。但该路径规划是基于确定环境模型的,所以有其局限性。在离散空间下路径规划中,K azuo Sugi hara and John S m ith[11]进行了更深入的研究,他们对栅格序号采用二进制编码,随机产生障碍物位置和数目,在搜索到最优路径后再在环境空间中随机插入障碍物,以此来模拟环境变化,仿真结果验证了其有效性和可行性。但是,规划空间的栅格法建模有其自身的缺陷,所以还有待改进。周明等提出一种连续空间下基于遗传算法的移动机器人路径规划方法[12],该方法在规划空间时有别于离散空间下的栅格法,而是在利用链接图[13]建模的基础上,先通过图论中成熟的算法粗略搜索出可行路径,再用遗传算法调整路径点得到最优路径。这种编码方法效率较高,不会产生无效路径,使用基本遗传算法就可以完成路径规划问题。但对于复杂环境链接图的建立有一定困难。此外,遗传算法运算速度低,进化众多的规划要占据较大存储空间和运算时间。
2 3 模糊逻辑算法(Fuzzy Log ic A l g orith m)
模糊逻辑算法是基于实时传感信息的一种在线规划方法。H art m ust Sur m a nn等[14]提出一种未知环境下的高级机器人模糊导航方法,由八个不同的超声传感器来提供环境信息,然后利用基于模糊控制的导航器计算这些信息,规划机器人路径。李彩虹等[15]提出了一种在未知环境下移动机器人的模糊控制算法,庄晓东等[16]提出一种动态环境中基于模糊概念的机器人路径搜索算法。
2 4 神经网络方法(A rtificia lNeura lNet w or k)
神经网络作为一个高度并行的分布式系统,为解决机器人系统实时性要求很高的问题提供了可能性,并应用于机器人路径规划方面。禹建丽等[17]提出了一种基于神经网络的机器人路径规划算法。禹建丽[18]又引进了线性再励的自适应变步长算法,提高了机器人路径规划速度。研究了障碍物形状和位置已知情况下的机器人路径规划算法,其能量函数的定义利用了神经网络结构,规划出的路径达到了折线形的
最短无碰路径,该方法计算简单、收敛速度快。刘成良等[19]提出了基于神经网络的机器人无碰撞路径规划方法,给出了无碰撞轨迹规划的人工神经网络算法,证明了其可行性,为神经网络真正用于机器人控制提供了基础。陈宗海[20]提出了一种在不确定环境中移动机器人的路径规划方法,采用基于案例的学习算法,进行案例的匹配、学习和扩充,使用ART-22神经网络实现,提高了路径规划的效率,以满足移动机器人在线路径规划的实时性要求。樊长虹等[21]针对移动机器人的未知环境下采用了一种局部连接H opfi eld神经网络规划器。对任意形状环境,ANN中兼顾处理了 过近 和 过远 来形成安全路径,而无需学习过程。为在单处理器上进行有效的在线路径规划,提出用基于距离变换的串行模拟,加速了数值势场的传播,该方法具有较高的实时性和环境适应性。
3 混合方法(H ybri d M ethod)
混合方法试图结合全局和局部方法的优点。在全局规划的基础上进行局部微调,相互结合、取长补短。目前,将遗传算法、模糊逻辑以及神经网络等方法相结合,组成了一些新的机器人路径规划方法,提高了规划的效率。
周明等提出利用遗传算法和模拟退火算法相结合的方法来解决机器人路径规划问题。这种混合方法也可以看作是遗传算法的改进,抑制了遗传算法的早熟现象,克服了其局部寻优能力较差的缺点,有效地提高了路径规划的质量。吴城东等[22]提出了一种基于粗糙集和遗传算法混合方法的机器人路径规划方法。引入粗糙集软计算方法,对遗传算法的种群初始化过程进行了改进,提高了机器人路径规划的速度和能力。龚进峰等[23]提出一种基于数字势场和遗传算法的机器人路径规划方法。该方法利用笛卡儿工作空间的几何信息,建立离散化工作空间的距离图和数字势场,基于启发函数引导机器人在构形空间使用遗传算法搜索,取得了一定的成效。
L H T soukalas等[24]提出一种用于半自主移动机器人路径规划的模糊神经网络方法。这种方法采用模糊描述来完成机器人行为编码,同时重复使用神经网络自适应技术,通过机器人的传感器提供局部环境输入,内部模糊神经网络进行环境预测,从而可以实现未知环境下机器人路径规划。
对机器人路径规划的研究不仅仅局限于上述几种方法。一些新的算法和方法也逐渐应用于这一领域。武彬等[25]介绍了一个基于免疫算法的移动机器人路径规划系统。宋道金等[26]针对多目标不确定环境下移动机器人路径规划算法的复杂问题,提出了混沌控制算法,并用V isual Basic语言进行了仿真。吴峰光等[27]提出了一种崭新的基于切线的路径规划方法,规划速度快、内存需求小。秦元庆等[28]提出一种分步路径规划方法,该方法简便可行,能够满足移动机器人导航的高实时性要求,是机器人路径规划的一个较好方案。等等。
4 结束语
机器人广泛应用于体育、娱乐、工业、服务领域中,尤其是在一些作业环境比较恶劣的情况下,如焊接、生化探测、火灾侦察、隧道凿岩及抢险救灾等,机器人路径规划是机器人学的一个重要研究领域,也是人工智能与机器人学的重要结合点。近年来有关机器人路径规划的文献[29-31]日益增多,与20世纪80年代研究初期相比,无论是在研究的深度还是广度上都有了巨大的发展,初步形成了理论、算法和应用的多方位研究。但还有不少工作值得进一步开展,目前智能算法在机器人路径规划中的应用受到了很大的局限,如神经网络局限于环境的建模和认知、模糊逻辑应用于复杂未知动态环境中,模糊规则较难提取等。所以智能方法还有很大的发展空间。此外,在多机器人协调作业环境下,由于障碍物和机器人数目增加,加大了路径规划的难度,以及如何使机器人在运动过程中根据不同的环境特点,高效地选择恰当的规划算法都是很有意义并且十分重要的研究课题。
参考文献
【1】蒋新松 机器人学导论[M] 辽宁科学技术出版社, 1994:511-516,543-554
【2】B rooks R A So l v i ng the F i nd-path proble m by good rep-resentation o f free space[J] IEEE T rans on Sys M an
and Cybern,1983,13(3):190-197
【3】Chatil a R P ath P lann i ng and Env iron m ent L earn i ng i n a M ob ile R obo t Syste m[C] P roc o f the European Conf on
A I,1982
【4】Pere A uto m atic planning of m anipulato r m ove m ents[J].
I EEE T rans on SysM an and Cyb,1981,11(11):681
-698
【5】D ijkstra E W A no te on t wo prob l em s i n connecti on w it h graphs[J] N u m ber M at h,1959(1):269-271 【6】A l exopou l os C,G r iffi n P M Pa t h planni ng for a mob ile ro-bo t[J] IEEE T rans on Syste m M an and Cybernetics,
1992,22(2):318-322
【7】M BM etea P l anni ng fo r i nte lligence aut onomous land veh i-
c l es usi ng hierarch ica l terrain representati on[A].Proc of
I EEE Int Conf on R obotics and R obotics and A ut om ati on
[C] 1987:1947-1952
【8】K ha ti b O R ea l-ti m e obstac le avo i dance for m an i pulators and m obil e robots[J] Int J R obotics R esearch,1986,
5(1):90-98
【9】Y ong K H W ang,N arendra A huja A potenti a l field ap-proach to path p l ann i ng[J] IEEE T ransacti ons on R o-
bo ti cs and A uto m a ti on,1992,8(1):23-32
【10】孙树栋,曲彦宾 遗传算法在机器人路径规划中的应用研究[J] 西北工业大学学报,1998,16
(1):79-83
【11】K azuo Sug i ba ra,John S m ith G eneti c a l go rith ms f o r adap-ti ve m oti on plann i ng of an autono mous m ob il e robots[A].
Prob le m s IEEE T rans S M C[C] USA:S I M,1997 【12】周明,孙树栋,彭炎午 用遗传算法规划移动机器人路径[M] 西北工业大学学报,1998,16(4):
581-583
【13】H ab itM K,A sa m a H Effi c ientM ethod to G enerate Co l-i s i on Free P aths for Au t ono m ous M ob ile R obo t Based on
N ew F ree Space Struc t ur i ng A pproach IEEE/R SJIRO S
91,1991:563-567
【14】H ar t m ut Ssur mann,Jrg H user,JensW ehki ng Path plan-ning f o r a fuzzy controlled autonomous m ob ile robot[A].
F ifth I EEE Int Conf On Fuzz y Systems Fuzz-IEEE 96
[C] UA S:N e w O r l eans,1996
【15】李彩虹,张景元,李贻斌 基于模糊控制的移动机器人的路径规划[J] 淄博学院学报,2001,3
(3):27-30
【16】庄晓东,孟庆春,殷波,等 动态环境中基于模糊概念的机器人路径搜索方法[J] 机器人,2001,
23(5):397-399
【17】禹建丽,韩平 一种基于神经网络的机器人路径规划算法[J] 洛阳工学院学报,2001,22(1):31
-34
【18】禹建丽,成久洋之,V a leri K rou m ov 线性再励的自适应变步长机器人神经网络路径规划算法[J] 燕
山大学学报,2002,26(3):259-266
【19】刘成良,张凯,付庄,等 神经网络在机器人路径规划中的应用研究[J] 机器人,2001,23(7):
605-608
【20】陈宗海,陈锋 一种不确定环境下移动机器人避障
规划算法[J] 机器人,2002,24(4):359-361 【21】樊长虹,卢有章,刘宏,等 基于神经网络的移动机器人路径规划[J] 计算机工程与应用,2004
(8):86-89
【22】吴成东,张颖,刘航 粗糙集遗传算法在机器人路径规划中的应用[J] 沈阳建筑工程学院学报,
2003,19(4):326-329
【23】龚进峰,彭商贤 数字势场和遗传算法的机器人路径规划的方法[J] 天津大学学报,2002,35
(4):525-529
【24】T souka l as LH,H oustis EN,Jones GV N euro f uzzy m o-tion planners f o r intelligent robots[J] Journa l o f In te-l
ligent and R obo ti c Sy stem s,1997,19:339-356 【25】武彬,吴耿锋,马飞,等 基于免疫算法的移动机器人路径规划系统,计算机工程,2004,30(12):
122-123
【26】宋道金,李宏涛,李彩,等 基于混沌控制的移动机器人的路径规划[J] 计算机应用研究,2004
(2):34-36
【27】吴峰光,奚宏生 一种新的基于切线的路径规划方法[J] 机器人,2004,26(3):193-197
【28】秦元庆,孙德宝,李宁,等 基于粒子群算法的移动机器人路径规划[J] 机器人,2004,26(3):
222-225
【29】柏艺琴,贺怀清 移动机器人路径规划方法简介[J] 中国民航学院学报,2003(2):206-209 【30】张颖,吴成东,原宝龙 机器人路径规划方法综述[J] 控制工程,2003,S0:152-155
【31】谢云,杨宜民 全自主机器人足球系统的研究综述[J] 机器人,2004,26(5):474-480
作者简介:朱明华(1981 ),男,硕士,研究方向为机器人路径规划、生产系统的建模与仿真。E-m a i:l zhu m i nghua@gm a il co m。
收稿时间:2004-11-24
(上接第67页)
加减速过程计算复杂的特点,提出了基于函数逼近的三角函数加减速策略。加速度沿正弦轨迹变化,保证在速度调整开始和终了时刻加速度恒为0。由于三角函数计算复杂,本文采用逼近误差小、收敛速度快的契比雪夫多项式对加速度正弦函数二阶展开,对速度和加减速区间长度直接利用基于二阶多项式的加速度积分求解,避免了函数逼近误差对变速过程参数计算的影响。速度、加速度和加加速度均连续有界,避免了加减速过程因为加速度和加加速度不平稳变化所带来的冲击和结构磨损。算法简单,工程实用性好。参考文献
【1】J W Jeon,S H Park,D I K m i A n efficient tra j ectory gen-era tion for i ndustr i a l rotots[C] Industry A pp licati ons So-
c i e t y A nnual M eeti ng,1993,Conference R eco r
d of the
1993IEEE 1993 10:2137-2143
【2】D I K i m,J W Jeon,S K i m So ft ware accelerati on dece-l erati on m ethods for i ndustr i a l robo ts and CNC mach i ne tools [J] M echatronics,1994,4(1):7-53
【3】E rko rk m az K,A lti ntas Y H i gh speed CNC syste m design.
Part I Jerk li m ited trajectory generati on and qui n tic spli ne
i nterpo lati on[J] Interati ona l Journa l o fM ach i ne T oo ls&
M anufact ure,2001,41(2):1323-1345
【4】郭新贵,李从心 一种新型柔性加减速算法[J] 上海交通大学学报,2003,7(2):205-207
作者简介:李加文(1970 ),男,博士研究生。主要研究方向:机械设备智能控制与信号处理。电话:021-********-8304。E-m a i:l liji aw en@163 com。
收稿时间:2004-12-29
3.23机器人路径运动操作步骤 任务：选取多个点构成一条路径，通过示教器完成机器人路径运动操作 相关知识：机器人路径示教器操作分为手动和自动两种模式 操作步骤： 一、手动模式 1、新建程序 （1）点击首页下拉菜单中“程序编辑器”选项，进入程序编辑器 （2）点击右上角“例行程序”选项，进如程序列表 （3）点击左下角“文件”，选择“新建例行程序”，新建例行程序 并命名 2、程序编写 （1）选择新建好的例行程序，进入程序编辑页面，点击左下角“添 加指令”，在右侧弹出菜单中选择轴运动指令“MoveJ” （2）根据需要修改显示的“MoveJ * ,v1000 , z50 , tool0”指令， *代表坐标点名称，v1000代表速度，z50代表路径选择幅度， tool0与工具坐标有关 （3）根据需要添加路径包含的点坐标并修改，完成全部路径点的设 置 3、调试 （1）从第一行“MoveJ”指令开始，利用示教器旋钮调节机器人至路 径点位，点击“修改位置”，程序与点位一一对应 （2）点位修改完成后，进行手动调试。点击“调试”选择“PP移动 至例行程序”，进入要调试的例行程序，光标选择调试的程序 行，再次点击“调试”，选择“PP移动至光标” （3）在右下角设置选项中选择机器人运行的速度
（4）左手按下示教器使能键，右手按下示教器上的“开始”按钮， 进行机器人路径运行操控 注意：机器人运行过程中不能松开示教器使能键 二、自动模式 1、完成手动调试模式调试后，点击“例行程序”菜单进入程序选择列表， 选择“Main”函数，进入函数编辑页面 2、光标选择
移动机器人路径规划方法 1.1路径规划方法 路径规划技术是机器人研究领域中的一个重要课题，是机器人导航中最重要的任务之一,国外文献常将其称为Path Planning,Find-PathProblem,Collision-Free,ObstacleAvoidance, MotionPlanning,etc.所谓机器人的最优路径规划问题，就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。 路径规划主要涉及的问题包括：利用获得的移动机器人环境信息建立较为合理的模型，再用某种算法寻找一条从起始状态到目标状态的最优或近似最优的无碰撞路径；能够处理环境模型中的不确定因素和路径跟踪中出现的误差，使外界物体对机器人的影响降到最小；如何利用已知的所有信息来引导机器人的动作，从而得到相对更优的行为决策。这其中的根本问题是世界模型的表达和搜寻策略。障碍物在环境中的不同分布情况当然直接影响到规划的路径，而目标位置的确定则是由更高一级的任务分解模块提供的[8]。 根据机器人对环境信息掌握的程度和障碍物运动状态的不同，移动机器人的路径规划基本上可分为以下四类:①已知环境下的对静态障碍物的路径规划;②未知环境下的对静态障碍物的路径规划;③已
知环境下对动态障碍物的路径规划;④未知环境下对动态障碍物的路径规划。因此根据机器人对环境信息掌握的程度不同，可将机器人的路径规划问题可分为二大类即：基于环境先验信息的全局路径规划问题和基于不确定环境的局部路径规划问题。目前，路径规划研究方法大概可分为两大类即：传统方法和智能方法。 1.2传统路径规划方法 传统的路径规划方法主要包括：可视图法(V-Graph)、自由空间法(Free Space Approach)、人工势场法（Artificial Potential Field）和栅格法(Grids)等。 ⑴可视图法（V-Graph） 可视图法是Nilsson1968年在文献[9]中首次提出。可视图法将移动机器人视为一点，将机器人起始点、目标点和多边形障碍物的各定点组合连接，保证这些直线不与障碍物相交，这就构成了一张无向图称为可视图。由于任意两条直线的定点都是可见的，从起点沿着这些直线到达目标点的路线都是无碰撞的。于是，搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。 这种方法的优点是可以得到最优路径，但缺陷是环境特征的提取比较困难，缺乏灵活性，一般需要机器人停止在障碍物前搜集传感器数据，并且传感器的精度对其影响也较大，尤其在复杂的非规整环境下更加难以实现安全无碰撞的路径规划。 ⑵自由空间法（Free Space Approach）
第5期(总第156期) 2009年10月机械工程与自动化 M ECHAN I CAL EN G I N EER I N G & AU TOM A T I ON N o 15 O ct 1 文章编号:167226413(2009)0520194203 机器人路径规划方法的研究 李爱萍,李元宗 (太原理工大学机械工程学院,山西 太原 030024) 摘要:路径规划技术是机器人学研究领域中的一个重要部分。目前的研究主要分为全局规划方法和局部规划方法两大类。通过对机器人路径规划方法研究现状的分析,指出了各种方法的优点及不足,并对其发展方向进行了展望。 关键词:机器人;全局规划;局部规划中图分类号:T P 242 文献标识码:A 收稿日期:2009201207;修回日期:2009204218 作者简介:李爱萍(19792),女,山西晋中人,在读硕士研究生。 0 引言 路径规划技术是机器人学研究领域中的一个重要 部分。机器人的最优路径规划就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短等),在其工作空间中找到一条从起始状态到目标状态的最优路径。根据对环境信息的掌握程度不同,路径规划可分为:①全局路径规划:环境信息完全已知,根据环境地图按照一定的算法搜寻一条最优或者近似最优的无碰撞路径,规划路径的精确程度取决于获取环境信息的准确程度;②局部路径规划:环境信息完全未知或部分未知,根据传感器的信息来不断地更新其内部的环境信息,从而确定出机器人在地图中的当前位置及周围局部范围内的障碍物分布情况,并在此基础上,规划出一条从当前点到某一子目标点的最优路径。 1 全局规划方法111 栅格法 栅格法是目前研究最广泛的路径规划方法之一。该方法将机器人的工作空间分解为多个简单的区域(栅格),由这些栅格构成一个显式的连通图,或在搜索过程中形成隐式的连通图,然后在图上搜索一条从起始栅格到目标栅格的路径。一般路径只需用栅格的序号表示。但栅格的划分直接影响其规划结果,如果栅格划分过大,环境信息储藏量小,分辨率下降,规划能力就差;栅格划分过小,规划时间长,而且对信息存储能力的要求会急剧增加。112 可视图法 可视图法中的路径图由捕捉到的存在于机器人一 维网络曲线(称为路径图)自由空间中的节点组成。路径的初始状态和目标状态同路径图中的点相对应,这样路径规划问题就演变为在这些点间搜索路径的问题。要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,即直线是“可视的”。然后采用某种方法搜索从起始点到目标点的最优路径,搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。该法能够求得最短路径,但需假设忽略机器人的尺寸大小,使得机器人通过障碍物顶点时离障碍物太近甚至接触,并且搜索时间长。113 拓扑法 拓扑法将规划空间分割成具有拓扑特征的子空间,根据彼此的连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。拓扑法的基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。其优点在于利用拓扑特征大大缩小了搜索空间,其算法的复杂性仅依赖于障碍物数目,在理论上是完备的;而且拓扑法通常不需要机器人的准确位置,对于位置误差也就有了更好的鲁棒性。缺点是建立拓扑网络的过程相当复杂,特别是在增加障碍物时如何有效地修正已经存在的拓扑网是有待解决的问题。 114 自由空间法 自由空间法采用预先定义的广义锥形或凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,通过搜索连通图来进行路径规划。自由空间的构
1绪论 1.1机器人简介 1.1.1什么是机器人 机器人一词不仅会在科幻小说、动画片等上看到和听到，有时也会在电视上看到在工厂进行作业的机器人，在实际中也有机会看到机器人的展示。今天，说不定机器人就在我们的身过，但这里我们要讨论的是什么是机器人学研究的机器人。 机器人（robot）一词来源下1920年捷克作家卡雷尔. 查培克（Kapel Capek）所编写的戏剧中的人造劳动者，在那里机器人被描写成像奴隶那样进行劳动的机器。 后来作为一种虚构的机械出现在许多作品中，代替人们去完成某些工作。20世纪60年代出现了作为可实用机械的机器人。为了反这种机器人同虚构的机器人及玩具机器人加以区别，称其为工业机器人。 工业机器人的兴起促进了大学及研究所开展机器人的研究。随着计算机的普及，又积极地开展了带有智能的机器人的研究。到70年代，机器人作为工程对象已经被确认，机器人一词也受到公认。目前，机器人学的研究对象已不仅仅是工业机器人了。 即便是实际存在的机器人，也很难把它定义为机器人，而且其定义也随着时代在变化。这里简单地反具有下述性质的机械看作是机器人： 1.代替人进行工作：机器人能像人那样使用工具和机械，因此，数控机床和 汽车不是机器人。 2.有通有性：既可简单地变换所进行的作为，又能按照工作状况的变化相应 地进行工作。一般的玩具机器人不能说有通用性。 3.直接对个界作工作：不仅是像计算机那样进行计算，而且能依据计算结果 对外界结果对外界产生作用。 机器人学把这样定义的机器人作为研究对象。
1.1.2机器人的分类 机器人的分类方法很多，这里我们依据三个有代表性的分类方法列举机器人的种类。 首先，由天机器人要代替人进行作业，因此可根据代替人的哪一个器官来分类： 操作机器人（手）：利用相当于手臂的机械手、相当于手指的手爪来使物体协作。 移动机器人（腿）：虽然已开发出了2足步行和4足步行机器人，但实用的却是用车轮进行移动的机器人。（本文以轮式移动机器人作为研究对象）视觉机器人（眼）：通过外观检查来除掉残次品，观看人的面孔认出是谁。虽然还有使用触觉的机器人，但由于它不是为了操作，所以不能说是触觉机器人。 也还有不仅代替单一器官的机器人，例如进行移动操作，或进行视觉和操作的机器人。 其次，按机器人的应用来分类： 工业机器人：可分为搬送、焊接、装配、喷漆、检查等机器人，主要用于工厂内。 极限作业器人：主要用在人们难以进入的核电站、海底、宇宙空间等进行作为的机器人。也包括建筑、农业机器人等。 娱乐机器人：有弹奏乐器的机器人、舞蹈机器人、宠物机器人等，具有某种程度的通用性。也有适应环境面改变行动的宠物机器人。 最后则是按照基于什么样的信息进行动作来分类： 表1基于动作信息的机器人分类
研究背景 近年来,机器人技术飞速发展,机器人的应用领域也在不断扩展。机器人的工作环境存在高度的多变性和复杂性,因此自主导航是实现真正智能化和完全自主移动的关键技术。机器人的导航问题可以归结为对“我在哪”、“我要去哪”以及“我如何到达那里”三个问题的回答。第三个问题就是路径规划,要求机器人在当前位置与目标位置之间寻找一条安全、合理、高效的路径,保证机器人能够安全地到达目标地点。机器人路径规划是机器人领域的一个研究热点。 一、课题应用 机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。 智能移动机器人[1]，是一个集环境感知、动态决策与规划、行为控制与执行等多功能于一体的综合系统。它集中了传感器技术、信息处理、电子工程、计算机工程、自动化控制工程以及人工智能等多学科的研究成果，代表机电一体化的最高成就，是目前科学技术发展最活跃的领域之一。随着机器人性能不断地完善，移动机器人的应用范围大为扩展，不仅在工业、农业、医疗、服务等行业中得到广泛的应用，而且在城市安全、国防和空间探测领域等有害与危险场合得到很好的应用。因此，移动机器人技术已经得到世界各国的普遍关注。 移动机器人的研究始于60 年代末期。斯坦福研究院(SRI)的Nils Nilssen 和Charles Rosen 等人，在1966年至1972 年中研发出了取名Shakey的自主移动机器人[1]。目的是研究应用人工智能技术，在复杂环境下机器人系统的自主推理、规划和控制。 根据移动方式来分，可分为：轮式移动机器人、步行移动机器人(单腿式、双腿式和多腿式)、履带式移动机器人、爬行机器人、蠕动式机器人和游动式机器人等类型；按工作环境来分，可分为：室内移动机器人和室外移动机器人；按控制体系结构来分，可分为:功能式(水平式)结构机器人、行为式(垂直式)结构机器人和混合式机器人；按功能和用途来分，可分为:医疗机器人、军用机器人、助残机器人、清洁机器人等； 一种由传感器、遥控操作器和自动控制的移动载体组成的机器人系统。移动机器人具有移动功能，在代替人从事危险、恶劣（如辐射、有毒等）环境下作业和人所不 及的（如宇宙空间、水下等）环境作业方面，比一般机器人有更大的机动性、灵活性。 移动机器人是一种在复杂环境下工作的，具有自行组织、自主运行、自主规划的智能机器人，融合了计算机技术、信息技术、通信技术、微电子技术和机器人技术等。 三、研究意义 路径规划技术是机器人研究领域中的一个重要分支,是机器人智能化的重要标志,是对
第25卷第7期V ol.25No.7 控制与决策 Control and Decision 2010年7月 Jul.2010移动机器人路径规划技术综述 文章编号:1001-0920(2010)07-0961-07 朱大奇,颜明重 (上海海事大学水下机器人与智能系统实验室，上海201306) 摘要:智能移动机器人路径规划问题一直是机器人研究的核心内容之一.将移动机器人路径规划方法概括为:基于模版匹配路径规划技术、基于人工势场路径规划技术、基于地图构建路径规划技术和基于人工智能的路径规划技术.分别对这几种方法进行总结与评价,最后展望了移动机器人路径规划的未来研究方向. 关键词:移动机器人；路径规划；人工势场；模板匹配；地图构建；神经网络；智能计算 中图分类号:TP18；TP273文献标识码:A Survey on technology of mobile robot path planning ZHU Da-qi,YAN Ming-zhong (Laboratory of Underwater Vehicles and Intelligent Systems，Shanghai Maritime University，Shanghai201306, China．Correspondent：ZHU Da-qi，E-mail：zdq367@https://www.doczj.com/doc/7a16123831.html,) Abstract:The technology of intelligent mobile robot path planning is one of the most important robot research areas.In this paper the methods of path planning are classi?ed into four classes:Template based,arti?cial potential?eld based,map building based and arti?cial intelligent based approaches.First,the basic theories of the path planning methods are introduced brie?y.Then,the advantages and limitations of the methods are pointed out.Finally,the technology development trends of intelligent mobile robot path planning are given. Key words:Mobile robot；Path planning；Arti?cial potential?eld；Template approach；Map building；Neural network; Intelligent computation 1引言 所谓移动机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务.移动机器人路径规划主要解决3个问题:1)使机器人能从初始点运动到目标点;2)用一定的算法使机器人能绕开障碍物,并且经过某些必须经过的点完成相应的作业任务;3)在完成以上任务的前提下,尽量优化机器人运行轨迹.机器人路径规划技术是智能移动机器人研究的核心内容之一,它起始于20世纪70年代,迄今为止,己有大量的研究成果报道.部分学者从机器人对环境感知的角度,将移动机器人路径规划方法分为3种类型[1]:基于环境模型的规划方法、基于事例学习的规划方法和基于行为的路径规划方法;从机器人路径规划的目标范围看,又可分为全局路径规划和局部路径规划;从规划环境是否随时间变化方面看,还可分为静态路径规划和动态路径规划. 本文从移动机器人路径规划的具体算法与策略上,将移动机器人路径规划技术概括为以下4类:模版匹配路径规划技术、人工势场路径规划技术、地图构建路径规划技术和人工智能路径规划技术.分别对这几种方法进行总结与评价,展望了移动机器人路径规划的未来发展方向. 2模版匹配路径规划技术 模版匹配方法是将机器人当前状态与过去经历相比较,找到最接近的状态,修改这一状态下的路径,便可得到一条新的路径[2,3].即首先利用路径规划所用到的或已产生的信息建立一个模版库,库中的任一模版包含每一次规划的环境信息和路径信息,这些模版可通过特定的索引取得;随后将当前规划任务和环境信息与模版库中的模版进行匹配,以寻找出一 收稿日期:2009-08-30；修回日期:2009-11-18. 基金项目:国家自然科学基金项目(50775136)；高校博士点基金项目(20093121110001)；上海市教委科研创新项目(10ZZ97). 作者简介:朱大奇(1964?),男,安徽安庆人,教授,博士生导师,从事水下机器人可靠性与路径规划等研究；颜明重(1977?),男,福建泉州人,博士生,从事水下机器人路径规划的研究.
多机器人路径规划研究方法（一） 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 e,itexpoundedthebottleneckofthepathplanningresearchfor ， ； 近年来，分布式人工智能（DAI）成为人工智能研究的一个重要分支。DAI 研究大致可以分为DPS （distributedproblemsolving ）和MAS （）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点,而路径规划研究又是其核心部分。
机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果 1~3］，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi 图法、自由空间法、栅格法、拓扑法、链接图法、证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。 1 多机器人路径规划方法单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。 目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi 图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学 习等；其他方法主要有动态规划、最优控制算法、模糊控制等。它们中的大部分都是从单个机器人路径规划方法扩展而来的。 1）传统方法多机器人路径规划传统方法的特点主要体现在基于图论的基础
龙源期刊网 https://www.doczj.com/doc/7a16123831.html, 移动机器人路径规划技术综述 作者：孙梅 来源：《山东工业技术》2016年第21期 摘要：移动机器人的设计与实现能够促进智能化应用的良好发展。路径规划技术是机器 人实现移动功能的主要技术之一。路径规划技术主要包含局部规划技术以及全局规划技术等。本文从路径规划技术的作用入手，对移动机器人路径规划技术进行研究和分析。 关键词：移动机器人；路径规划技术；综述 DOI：10.16640/https://www.doczj.com/doc/7a16123831.html,ki.37-1222/t.2016.21.135 0 前言 移动机器人的实现涉及自动控制、智能、机械等多种学科。它通常被应用在医疗领域、工业领域等方面。从整体角度来讲，移动机器人的应用促进了生产效率的显著提升。路径规划技术是移动机器人的关键技术之一，研究该技术具有一定的现实意义。 1 路径规划技术的作用 将路径规划技术应用在移动机器人中，能够产生的作用主要包含以下几种： （1）运动方面。路径规划技术的主要作用是其能够保证移动机器人完成从起点到终点的运动。（2）障碍物方面。设计移动机器人的最终目的是将其应用在实际环境中，在实际环境下，移动机器人的运行路线中可能存在一定数量的障碍物，为了保证最终目的地的顺利达到，需要利用路径规划技术实现对障碍物的有效避开[1]。（3）运行轨迹方面。对于移动机器人而言，除了实现障碍物躲避、达到最终目的地这两种作用之外，应用路径规划技术还可以产生一定的优化运行轨迹作用。在移动机器人的使用过程中，在路径规划技术的作用下，机器人可以完成对最佳运行路线的判断，进而更好地完成相应任务。 2 移动机器人路径规划技术综述 移动机器人的路径规划技术主要包含以下几种： 2.1 局部路径规划方面 在局部路径规划方面，能够被应用在移动机器人中的技术主要包含以下几种： （1）神经网络路径规划技术。从本质上讲，可以将移动机器人的路径规划看成是空间到行为空间感知过程的一种映射，因此，可以利用神经网络的方式将其表现出来。就神经网络路
多机器人路径规划研究方法 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝 摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multi robot.Then discussed the criterion of path planning research for multi robot based large of literature.Meanwhile,it expounded the bottleneck of the path planning research for multi robot，forecasted the future development of multi robot path planning. Key words:multi robot；path planning;reinforcement learning;evaluating criteria 近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI研究大致可以分为DPS（distributed problem solving）和MAS（multi agent system）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点,而路径规划研究又是其核心部分。 机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果[1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、Dempster Shafer 证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划
多机器人路径规划研究方法(一) 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝 摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 e,itexpoundedthebottleneckofthepathplanningresearchfor， ； 近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI 研究大致可以分为DPS（distributedproblemsolving）和MAS （）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术
界研究的热点,而路径规划研究又是其核心部分。 机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。 1多机器人路径规划方法 单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。 目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学
机器人路径规划方法的研究进展与趋势 朱明华,王霄,蔡兰 (江苏大学机械工程学院,江苏镇江212013) 摘要:对机器人路径规划的研究进行了概括和总结,阐述了机器人全局路径规划方法、局部路径规划方法及混合方法的研究现状、特点和主要成果,指出了其今后的发展方向及研究重点。 关键词:机器人;遗传算法;路径规划;粗糙集 中图分类号:T P242 文献标识码:A 文章编号:1001-3881(2006)3-005-4 R esearch P rogress and Future Develop m ent on Path P lanni n g for Robot Z HU M inghua,WANG X iao,CA I Lan (M echanical Eng i n eering Institute,Jiangsu Un i v ersity,Zhenjiang Jiangsu212013,China) Abstrac t:T he research of robo t pa t h plann i ng w as s umm arized,the research sta t us quo,character i stic and ma i n producti on of robo t g l obal path p l ann i ng m ethod,l oca l path p l ann i ng m ethod and hybr i d m ethod were expatiated,its deve l op m ent d irec tions and study f o cus w ere po i nted out. K eyword s:R obot;G enetic a l gor it hm s;P ath p lann i ng;R ough set 路径规划技术是机器人研究领域中的一个重要分支,是机器人导航中最重要的任务之一。蒋新松在文献[1]中为路径规划作出了这样的定义:路径规划是自治式移动机器人的一个重要组成部分,它的任务就是在具有障碍物的环境内按照一定的评价标准,寻找一条从起始状态(包括位置和姿态)到达目标状态(包括位置和姿态)的无碰路径。障碍物在环境中的不同分布情况当然直接影响到规划的路径,而目标位置的确定则是由更高一级的任务分解模块提供的。目前,根据对环境的掌握情况,机器人的路径规划问题可以大致分为二大类:基于环境先验信息的全局路径规划;基于不确定环境的传感器信息的局部路径规划。 1 全局路径规划方法(G lobal Pat h Plann i n g) 依据已获取的全局环境信息,给机器人规划出一条从起点至终点的运动路径。规划路径的精确程度取决于获取环境信息的准确程度。全局路径规划规划方法通常可以寻找最优解,但需要预先知道准确的全局环境信息。通常该方法计算量大,实时性差,不能较好地适应动态非确定环境。基于环境建模的全局路径规划的方法主要有:自由空间法、构型空间法和栅格法等。 1 1 自由空间法(Free Space Approach) 自由空间法采用预先定义的如广义锥形[2]和凸多边形[3]等基本形状构造自由空间,并将自由空间表示为连通图,然后通过搜索连通图来进行路径规划,此方法比较灵活,即使起始点和目标点改变,也不必重构连通图,但是算法的复杂程度与障碍物的多少成正比,且不能保证任何情况下都能获得最短路径。因而该方法仅适用于路径精度要求不高,机器人速度不快的场合。按照划分自由空间方法的不同又可分为:凸区法、三角形法、广义锥法。 1 2 构型空间法 为了简化问题,通常将机器人缩小为一点,将其周围的障碍物按比例相应地进行拓展,使机器人在障碍物空间中能够任意移动而不与障碍物及其边界发生碰撞。目前研究比较成熟的有可视图法[4]和优化算法(如D ijkstra法[5]、A*搜索算法[6]等)。 1 2 1 可视图法(V-G r aph) 通过起始点和目标点及障碍物的顶点在内的一系列点来构造可视图。连接这些点使某点与其周围的某可视点相连,即要求机器人和障碍物各顶点之间、目标点和障碍物各顶点以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,也即直线是可视的。从而搜索最优路径的问题就转化为经过这些可视直线从起始点到目标点的最短距离问题。 1 2 2 优化算法(Optm i ization A l gorit hm) 优化算法可以删除一些不必要的连线以简化可视图,从而缩短搜索时间,求得最短路径。但是,优化算法缺乏灵活性,一旦起点和目标点改变,就必须重构可视图,并且搜索效率也较低。 1 3 栅格法(Grids) 栅格法[7]将机器人的工作环境分解成一系列具有二值信息的网格单元,并假设工作空间中障碍物的位置和大小已知且在机器人运动过程中不会发生变化。用尺寸相同的栅格对机器人的二维工作空间进行规划,栅格大小以机器人自身的尺寸为准。若某一栅格范围内不含任何障碍物,则称此栅格为自由栅格;反之,称为障碍栅格。这样,自由空间和障碍物均可表示为栅格块的集成。栅格的表识方法有两种:直角坐标法和序号法。直角坐标法如图1所示,以栅格阵左上角为坐标原点,水平向右为X轴正方向,竖直向
机器人路径规划 冯赟:机器人路径规划方法研究 1绪论 1.1机器人简介 1.1.1什么是机器人 机器人一词不仅会在科幻小说、动画片等上看到和听到，有时也会在电视上看到在工厂进行作业的机器人，在实际中也有机会看到机器人的展示。今天，说不定机器人就在我们的身过，但这里我们要讨论的是什么是机器人学研究的机器人。 robot)一词来源下1920年捷克作家卡雷尔 . 查培克(Kapel Capek)机器人( 所编写的戏剧中的人造劳动者，在那里机器人被描写成像奴隶那样进行劳动的机器。 后来作为一种虚构的机械出现在许多作品中，代替人们去完成某些工作。20世纪60年代出现了作为可实用机械的机器人。为了反这种机器人同虚构的机器人及玩具机器人加以区别，称其为工业机器人。 工业机器人的兴起促进了大学及研究所开展机器人的研究。随着计算机的普及，又积极地开展了带有智能的机器人的研究。到70年代，机器人作为工程对象已经被确认，机器人一词也受到公认。目前，机器人学的研究对象已不仅仅是工业机器人了。 即便是实际存在的机器人，也很难把它定义为机器人，而且其定义也随着时代在变化。这里简单地反具有下述性质的机械看作是机器人: 1. 代替人进行工作:机器人能像人那样使用工具和机械，因此，数控机床和 汽车不是机器人。 2. 有通有性:既可简单地变换所进行的作为，又能按照工作状况的变化相应
地进行工作。一般的玩具机器人不能说有通用性。 3. 直接对个界作工作:不仅是像计算机那样进行计算，而且能依据计算结果 对外界结果对外界产生作用。 机器人学把这样定义的机器人作为研究对象。 - 1 - 郑州大学电气工程学院毕业设计(论文) 1.1.2机器人的分类 机器人的分类方法很多，这里我们依据三个有代表性的分类方法列举机器人的 种类。 首先，由天机器人要代替人进行作业，因此可根据代替人的哪一个器官来分类: 操作机器人(手):利用相当于手臂的机械手、相当于手指的手爪来使物体协 作。 移动机器人(腿):虽然已开发出了2足步行和4足步行机器人，但实用的却是 用车轮进行移动的机器人。(本文以轮式移动机器人作为研究对象) 视觉机器人(眼):通过外观检查来除掉残次品，观看人的面孔认出是谁。虽然 还有使用触觉的机器人，但由于它不是为了操作，所以不能说是触觉机器人。 也还有不仅代替单一器官的机器人，例如进行移动操作，或进行视觉和操作的 机器人。 其次，按机器人的应用来分类: 工业机器人:可分为搬送、焊接、装配、喷漆、检查等机器人，主要用于工厂 内。 极限作业器人:主要用在人们难以进入的核电站、海底、宇宙空间等进行作为 的机器人。也包括建筑、农业机器人等。
移动机器人路径规划综述 目录 1 引言 (2) 2 传统路径规划方法 (2) 2.1 自由空间法 (2) 2.2 图搜索法 (3) 2.3 栅格法 (3) 3 智能路径规划方法 (4) 3.1基于模糊逻辑的路径规划 (4) 3.2基于遗传算法的路径规划 (5) 3.3基于神经网络的路径规划 (5) 3.4人工势场法 (5) 3.5基于模糊逻辑与信息融合的路径规划 (6) 4 结论与展望 (6) 参考文献 (7)
1 引言 所谓移动机器人路径规划技术，就是机器人根据自身传感器对环境的感知，自行规划出一条安全的运行路线，同时高效完成作业任务。移动机器人路径规划主要解决3个问题： 1) 使机器人能从初始点运动到目标点； 2) 用一定的算法使机器人能绕开障碍物，并且经过某些必须经过的点完成相应的作业任务； 3) 在完成以上任务的前提下，尽量优化机器人运行轨迹。 机器人路径规划技术是智能移动机器人研究的核心内容之一，它起始于20 世纪70年代，迄今为止，己有大量的研究成果报道[1]。路径规划方法的分类也呈现多样化，可以分为基于地图的全局路径规划方法[2,3]和基于传感器的局部路径规划方法[4]，也可以分为传统路径规划方法[5]与智能路径规划方法[6]。 本文主要按传统路径规划方法与智能路径规划方法进行总结与评价。传统路径规划方法主要包含自由空间法，图搜索法，栅格法等，智能路径规划算法主要包含基于模糊逻辑的路径规划，基于神经网络的路径规划，基于遗传算法的路径规划，人工势场法以及信息融合方法等。 2 传统路径规划方法 2.1 自由空间法 自由空间法[7]应用于移动机器人路径规划，采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间，并将自由空间表示为连通图，通过搜索连通图来进行路径规划。自由空间的构造方法[8]是：从障碍物的一个顶点开始，依次作其它顶点的链接线，删除不必要的链接线，使得链接线与障碍物边界所围成的每一个自由空间都是面积最大的凸多边形；连接各链接线的中点形成的网络图即为机器人可自由运动的路线。其优点是比较灵活，起始点和目标点的改变不会造成连通图的重构，缺点是复杂程度与障碍物的多少成正比，且有时无法获得最短路
机器人路径规划 摘要：机器人路径规划是机器人技术的重要分支之一，路径规划技术的研究是研究机器人技术不可或缺的技术之一。本文首先介绍了当前研究人员热衷的ROS 系统是如何进行路径规划的，接着论述了作为群智能算法的蚁群算法应用于机器人的路径规划中。研究表明，可以将蚁群算法和ROS系统结合，进一步的进行机器人的路径规划。 关键词：路径规划，ROS系统，蚁群算法，机器人 1.引言 智能移动机器人技术是机器人技术的重要组成部分，应用前景十分广阔：工业，农业，国防，医疗，以及服务业等[1]。文献提出，未来数年内，中国服务机器人发展将超过传统的工业机器人[2]，机器人路径规划技术是服务机器人研究的核心内容之一[3]。可见，研究机器人的路径规划问题十分必要。 随着机器人领域的快速发展和复杂化，代码的复用性和模块化的需求原来越强烈，而已有的开源机器人系统又不能很好的适应需求。2010年Willow Garage 公司发布了开源机器人操作系统ROS（robot operating system），很快在机器人研究领域展开了学习和使用ROS的热潮。ROS系统是起源于2007年斯坦福大学人工智能实验室的项目与机器人技术公司Willow Garage的个人机器人项目（Personal Robots Program）之间的合作，2008年之后就由Willow Garage来进行推动。ROS的运行架构是一种使用ROS通信模块实现模块间P2P的松耦合的网络连接的处理架构，它执行若干种类型的通讯，包括基于服务的同步RPC（远程过程调用）通讯、基于Topic的异步数据流通讯，还有参数服务器上的数据存储。ROS系统以其独特优点引起了研究人员的兴趣。 近年来，各国学者致力于机器人路径规划的研究且取得了相当丰硕的研究成果。目前已有多种算法用于规划机器人的路径，文献【4】将其主要分为经典方
移动机器人是装备了机械腿、轮子、关节、抓握器等执行器以及控制器来完成特定任务的一种实体智能体。近年来，随着科学技术的飞快发展，移动机器人在工业、农业、医疗、服务、航空和军事等领域得到了广泛的应用，已成为学术研究的重点。在移动机器人的研究中，导航研究是核心，而路径规划是机器人导航研究的重要环节之一。在机器人执行任务时，要求机器人在工作环境中（有障碍物或无障碍物）能根据一定的评价标准搜索一条从起始地点到目标地点的最优或次优路径[1]。移动机器人的路径规划根据环境是否已知可分为基于地图的全局路径规划和基于传感器的局部路径规划。 1全局路径规划 1.1栅格分解法 栅格分解法是目前广泛研究的路径规划方法之一。该方法把移动机器人的运动环境分解为多个简单的栅格并根据它们是否被障碍物占据来进行状态描述，障碍物栅格和非障碍物栅格具有不同的标识值，它能快速直观地融合传感器信息。但是为了得到比较精确的规划结果，必须将环境划分为较小的栅格，这就导致存储空间增大，在大规模环境下路径规划的计算复杂程度将加大。为了克服栅格表示的存储空间问题，邰宜斌提了一种四叉树分割方法[2]，该算法递归地把环境分解为大小不一的矩形区域，这些矩形区域或者完全被障碍物占据，或者是完全自由可行的。每次递归都将一个较大的栅格划分为4个较小的栅格，取得了较好的计算效果。另外栅格分解法随着机器人自由度的增加会出现“维数灾难”问题，不适用于解决多自由度机器人在复杂环境中的路径规划。Frank在2004年提出了概率栅格分解算法，在该算法中引入随机采样，可使多自由度机器人在复杂环境中快速找到一条可行路径。2006年吕太之等在概率栅格分解算法的基础上引入了Anytime算法，将随机采样应用到栅格分解算法中，使算法效率得到了提高，但是受环境信息和随机采样的影响比较大[3]。 1.2拓扑法 拓扑法主要包括三部分：划分状态空间、构建特征网、在特征网上搜索路径。拓扑法的基本要素是节点和边，用节点表示某个特定的位置，用边表示这些位置之间的联系，可以用G=(V,E)描述空间的特征，其中V表示顶点集合，E表示连接顶点的边集合[4]。利用该方法可缩小搜索空间，使得存储需求小，适合于大规模环境的路径规划，但是构建特征网的过程比较复杂，而且当障碍物增加时如何将增加的节点与已有节点进行节点匹配是一个难点。2005年，王力虎等提出了一种适用于清扫机器人的区域充满拓扑算法，用传感器感知环境信息以建立环境的拓扑地图，机器人可以利用搜索图的方法搜索环境，可达到环境的有效覆盖，但在搜索时没有 移动机器人路径规划研究现状及展望 张海英,范进桢 (宁波职业技术学院,浙江宁波315800) 摘要：移动机器人路径规划技术是机器人研究领域中的核心技术之一。通过对全局路径规划和局部路径规划中各种方法的分析，指出了各种方法的优点和不足以及改进的办法，并对移动机器人路径规划技术的发展趋势进行了展望。 关键词：移动机器人；路径规划；遗传算法 中图分类号：TP242文献标识码：A文章编号：1674-7720(2011)02-0005-04 Research progress and future development of mobile robot path planning Zhang Haiying,Fan Jinzhen (Ningbo Polytechnic Institute，Ningbo315800,China) Abstract:Mobile robot path planning technology is one of core-technology in robot research domain.By analyzing algorithms of global path planning and local path planning,this paper points out the advantages and disadvantages of the present algorithms, and improved methods.In addition,describes the trend of mobile robot path planning. Key words:mobile robot;path planning;genetic algorithm 综述与评论Review and Comment 5 《微型机与应用》2011年第30卷第2期欢迎网上投稿https://www.doczj.com/doc/7a16123831.html,