智能机器人路径规划及算法研究由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“机器人的路径规划算法”。
机器人技术
文章编号:1008-0570(2006)11-2-0244-03
中文核心期刊《微计算机信息》(嵌入式与SOC)2006年第22卷第11-2期
智能机器人路径规划及算法研究
ResearchonPathPlanningandAlgorithmsforIntelligentRobots
(西南科技大学)宋晖张华高小明
SONGHUIZHANGHUAGAOXIAOMING
摘要:路径规划技术是机器人控制技术研究中的一个重要问题,目前的研究主要分为全局规划方法和局部规划方法两大类。在对一些较有代表性的研究思想及其相关算法分析的基础上,比较各种方法的优缺点,提出了机器人路径规划今后的研究重点。关键词:智能机器人;全局规划;局部规划;优化算法 中图分类号:TP242.6 文献标识码:A
技
1引言 术
自50年代世界上第一台机器人装置诞生以来, 创 机器人的发展经历了一个从低级到高级的发展过程。
第一代示教再现型机器人,可以根据人示教的结果再 新 现出动作,它对于外界的环境没有感知。在20世纪70
年代后期人们开始研究第二代机器人:带感觉的机器 人,这种机器人是类似人某种感觉的功能,如力觉、触 觉、滑觉、视觉、听觉。第三代机器人是智能机器人阶 段,机器人通过各种传感器获取环境信息,利用人工 智能进行识别、理解、推理并做出判断和决策来完成 一定的任务。这就要求智能机器人除了具有感知环境 和简单的适应环境能力外,还具有较强的识别理解功 能和决策规划功能。（智械科技）Abstract:Pathplanningtechnologyisoneoftheimportantprobleminintelligentrobot.Atpresent,thetworesearchways:oneis globalplanningandtheotherislocalplanning.Onthebasisoftheanalysisofsometypicalideas,methodsandrelatedalgorithms ofpathplanningforintelligentrobot,thispaperproposesthefutureresearchemphasisofrobotpathplanning.Keywords:intelligentrobot,globalplanning,localplanning,optimizationalgorithms
①复杂性:在复杂环境中,机器人路径规划非常 复杂,且需要很大的计算量。
②随机性:复杂环境的变化往往存在很多随机性 和不确定因素。
③多约束:机器人的形状、速度和加速度等对机 器人的运动存在约束。
3全局路径规划
全局规划方法主包括构型空间法、拓扑法、栅格 解耦法、自由空间法、神经网络法等。
3.1构型空间法
构型空间法的基本思想是将机器人缩小为一个 点,根据机器人形状和尺寸将障碍物进行拓展。其中 研究较成熟的有:可视图法和优化算法。
3.1.1可视图法
可视图法中的路径图由捕捉到的存在于机器人 一维网络曲线(称为路径图)自由空间中的节点组成。路径的初始状态和目标状态同路径图中的点相对应, 这样路径规划问题就演变为在这些点间搜索路径的 问题。要求机器人和障碍物各顶点之间、目标点和障碍 物各顶点之间以及各障碍物顶点与顶点之间的连线均 不能穿越障碍物,即直线是“可视的”,然后采用某种方 法搜索从起始点到目标点的最优路径,搜索最优路径 的问题就转化为从起始点到目标点经过这些可视直线 的最短距离问题。该法能够求得最短路径,但假设忽略 智能机器人的尺寸大小,使得机器人通过障碍物顶点 时离障碍物太近甚至接触,并且搜索时间长。
3.1.2优化算法 此法可删除一些不必要的连线以简化可视图、缩 短搜索时间,能够求得最短路径。但假设机器人的尺
《 现场总线技术应用200例》 2智能机器人的路径规划技术分类
智能机器人路径规划是指在有障碍物的工作环 境中,如何寻找一条从给定起点到终点适当的运动路 径,使机器人在运动过程中能安全、无碰地绕过所有 障碍物。机器人路径规划问题可以建模为一个有约束 的优化问题,都要完成路径规划、定位和避障等任务。根据机器人对环境信息掌握的程度不同将智能机器 人路径规划分为基于模型的全局路径规划和基于传 感器的局部路径规划。前者是指作业环境的全部信息 已知,又称静态或离线路径规划;后者是指作业环境 信息全部未知或部分未知,又称动态或在线路径规 划。智能机器人路径规划存在以下特点: 宋晖:讲师硕士
基金项目:国家自然科学基金(60404014);
西南科技大学青年基金资助项目(ZK053033)
-244-360元/年邮局订阅号:82-946 您的论文得到两院院士关注 机器人技术
在满足精度要求的情况下,用神经网络来表示环境则 可以取得较好的效果。神经网络在全局路径规划的应 用,将障碍约束转化为一个惩罚函数,从而使一个约 束优化问题转化为一个无约束最优化问题,然后以神 经网络来描述碰撞惩罚函数,进行全局路径规划。
虽然神经网络在路径规划中有学习能力强等优 点,但整体应用却不是非常成功,主要原因是智能机 器人所遇到的环境是千变万化的、随机的,并且很难 以数学的公式来描述。寸大小忽略不计,会使机器人通过障碍物顶点时离障 碍物太近甚至接触,并且搜索时间长。另外的缺点就 是此法缺乏灵活性,即一旦机器人的起点和目标点发 生改变,就要重新构造可视图,比较麻烦。这类算法包 括Dijkstra算法,A*算法等。（智械科技）
3.2拓扑法
拓扑法将规划空间分割成具有拓扑特征子空间, 根据彼此连通性建立拓扑网络,在网络上寻找起始点 到目标点的拓扑路径,最终由拓扑路径求出几何路 径。拓扑法基本思想是降维法,即将在高维几何空间 中求路径的问题转化为低维拓扑空间中判别连通性 的问题。优点在于利用拓扑特征大大缩小了搜索空 间。算法复杂性仅依赖于障碍物数目,理论上是完备 的。而且拓扑法通常不需要机器人的准确位置,对于 位置误差也就有了更好的鲁棒性;缺点是建立拓扑网 络的过程相当复杂,特别在增加障碍物时如何有效地 修正已经存在的拓扑网是有待解决的问题。
3.3栅格解耦法
栅格解耦法是目前研究最广泛的路径规划方法。该方法将机器人的工作空间解耦为多个简单的区域, 一般称为栅格。由这些栅格构成了一个连通图,在这个 连通图上搜索一条从起始栅格到目标栅格的路径,这 条路径是用栅格的序号来表示的。整个图被分割成多 个较大的矩形,每个矩形之间都是连续的。如果大矩形 内部包含障碍物或者边界,则又被分割成4个小矩形, 对所有稍大的栅格都进行这种划分,然后在划分的最 后界限内形成的小栅格间重复执行程序,直到达到解 的界限为止。该法以栅格为单位记录环境信息,环境 被量化成具有一定分辨率的栅格,栅格的大小直接影 响着环境信息存储量的大小和规划时间的长短,栅格 划分大了,环境信息存储量小,规划时间短,分辨率下 降;栅格划分小了,环境分辨率高。
3.4自由空间法
自由空间法采用预先定义的如广义锥形和凸多 边形等基本形状构造自由空间,并将自由空间表示为 连通图,通过搜索连通图来进行路径规划。自由空间 的构造方法是:从障碍物的一个顶点开始,依次作其 它顶点的链接线,删除不必要的链接线,使得链接线 与障碍物边界所围成的每一个自由空间都是面积最 大的凸多边形;连接各链接线的中点形成的网络图即 为机器人可自由栅格法运动的路线。其优点是比较灵 活,起始点和目标点的改变不会造成连通图的重构, 缺点是复杂程度与障碍物的多少成正比,且有时无法 获得最短路径。
3.5神经网络法
人工神经网络是由大量神经元相互连接而形成 的自适应非线性动态系统,对于大范围的工作环境,《PLC技术应用200例》
4局部路径规划
局部路径规划的主要方法有:人工势场法、模糊 逻辑控制法、混合法、滚动窗口法等。
4.1人工势场法
人工势场法是由Khatib提出的一种虚拟力法。其 基本思想是将智能机器人在环境中的运动视为一种 虚拟人工受力场中的运动。把智能机器人在环境中的 运动视为一种在抽象的人造受力场中的运动,目标点 对智能机器人产生引力,障碍物对智能机器人产生斥 力,最后通过求合力来控制智能机器人的运动。该法结 构简单,便于低层的实时控制,在实时避障和平滑的 轨迹控制方面,得到了广泛应用,其不足在于存在局 部最优解,容易产生死锁现象,因而可能使智能机器 人在到达目标点之前就停留在局部最优点。
4.2模糊逻辑控制算法 模糊方法不需要建立完整的环境模型,不需要进 行复杂的计算和推理,尤其对传感器信息的精度要求 不高,对机器人周围环境和机器人的位姿信息的具有 不确定性、不敏感的特点,能使机器人的行为体现出 很好的一致性、稳定性和连续性,能比较圆满地解决 一些规划问题,对处理未知环境下的规划问题显示出 很大优越性,对于解决用通常的定量方法来说是很复 杂的问题或当外界只能提供定性近似的、不确定信息 数据时非常有效。但模糊规则往往是人们通过经验预 先制定的,所以存在着无法学习、灵活性差的缺点。
技 术 创 新
4.3遗传算法
遗传算法是一种借鉴生物界自然选择和进化机 制发展起来的高度并行、随机、自适应搜索算法,它采 用群体搜索技术,通过选择、交叉和变异等一系列遗 传操作,使种群得以进化。避免了困难的理论推导,直 接获得问题的最优解。其基本思想是:将路径个体表 达为路径中一系列中途点,并转换为二进制串。首先 初始化路径群体,然后进行遗传操作,如选择、交叉、复制、变异。经过若干代进化以后,停止进化,输出当 前最优个体。
遗传算法存在运算时间长,实现路径的在线规划 困难,而且在机器人的路径规划问题中应用存在着个
邮局订阅号:82-946360元/年
-245-机器人技术 中文核心期刊《微计算机信息》(嵌入式与SOC)2006年第22卷第11-2期
体编码不合理、效率低、进化效果不明显等问题。
4.4混合法 混合法是一种用于半自主智能机器人路径规划 的模糊神经网络方法。所谓半自主智能机器人就是具 有在人类示教基础上增加了学习功能的器件的机器 人。这种方法采用模糊描述来完成机器人行为编码,同 时重复使用神经网络自适应技术。由机器人上的传感 器提供局部的环境输入,由内部模糊神经网络进行环 境预测,进而可以在未知环境下规划机器人路径。此 外,也有人提出基于模糊神经网络和遗传算法的机器 人自适应控制方法。将规划过程分为离线学习和在线 学习两部分。该方法是一种混合的机器人自适应控制 方法,可以自适应调整机器人的行走路线,达到避障和 路径最短的双重优化。（智械科技）
(3)多传感器信息融合用于路径规划。单传感器难 以保证输入信息准确与可靠。多传感器所获得信息具 有冗余性,互补性,实时性和低代价性,且可以快速并 行分析现场环境。
(4)基于功能/行为的智能机器人路径规划。基于模 型自顶向下的感知-建模-规划-动作是一种典型慎思 结构,称为基于功能的控制体系结构。基于行为的方 法是一种自底向上的构建系统方法,并与环境交互作 用中最终达到目标。基于功能/行为的机器人控制结构 融合了两者优点,这是研究的新动向之一。
6结语
本文作者的创新点:深入研究了国内外关于机器 人路径规划算法的发展现状、最新进展和各种算法的 优缺点,并对未来机器人路径规划技术的发展趋势进 行了综合分析;指出机器人路径规划技术未来的研究 重点是“仿人、仿生”智能,并还将紧密的结合认知科 学、人工智能、与计算智能的研究成果,提升机器人行 为的智能度。
参考文献:
[1]宗光华.机器人的创意设计与实践[M].北京：北京航空航天大 学出版社,2003.[2]Robin著,杜军平译.人工智能机器人学导论[M].北京：电子工 业出版社，2003.[3]席裕庚,张纯刚.一类动态不确定环境下机器人的滚动路径 规划[J].自动化学报,2002,28.[4]诸静.机器人与控制技术[M].杭州：浙江大学出版社,1991.[5]XuWL,TSOSK.Sensorbasedfuzzyreactivenavigationofa mobilerobotthroughlocaltargetswitching[J].IEEETransactionson Systems,1999，29.[6]KrishnaKM,KalraPK.Perceptionandrememberanceofthe environmentduringreal-timenavigationofamobilerobot[J].RobticsandAutonomousSystems,2001,37.[7]邢军,王杰.神经网络在移动机器人路径规划中的应用研究[J].微计算机信息,2005,22:110-111
[8]Khatib.Real-timeobstacleformanipulatorsandmobilerobot [J].TheInternationalJournalofRoboticResearch.1986,1.[9]薛艳茹,郑冰等.基于模糊控制信息融合方法的机器人导航系 统[J].微计算机信息,2005,22:107-109
[10]周明,孙树栋.遗传算法原理及应用[M].北京：:国防工业出版 社,2000.[11]KazuoSugihara,JohnSmith.GeneticAlgorithmsforAdaptive MotionPlanningofanAutonomousMobileRobot[A].Proceedings 1997IEEEInternationalSymposiumonComputationalIntelligence inRoboticsandAutomation[C].1997.[12]TsoukalasLH,HoustisEN,JonesGV.Neurofuzzy motionplannersforintelligentrobots
[J].Journalof
Intelligentan-
dRoboticSystems,1997,19.(下转第252页)
《 现场总线技术应用200例》 技 整个控制既基于模型与优化的,又是基于反馈的。基
:首先进行场 术 于滚动窗口的路径规划算法的基本思路景预测,在滚动的每一步,机器人根据其探测到的局 创4.5滚动窗口法
滚动窗口借鉴了预测控制滚动优化原理,把控制 论中优化和反馈两种基本机制合理地融为一体,使得
新 部窗口范围内的环境信息,用启发式方法生成局部子 目标,并对动态障碍物的运动进行预测,判断机器人 行进是否可能与动态障碍物相碰撞。其次机器人根据 窗口内的环境信息及预测结果,选择局部规划算法, 确定向子目标行进的局部路径,并依所规划的局部路 径行进一步,窗口相应向前滚动。然后在新的滚动窗 口产生后,根据传感器所获取的最新信息,对窗口内 的环境及障碍物运动状况进行更新。该方法放弃了对 全局最有目标的过于理想的要求,利用机器人实时测 得的局部环境信息,以滚动方式进行在线规划,具有 良好的避碰能力。但存在着规划的路径是非最优的问 题,即存在局部极值问题。
5智能机器人路径规划技术的展望
随着计算机、传感器及控制技术的发展,特别是 各种新算法不断涌现,智能机器人路径规划技术已经 取得了丰硕研究成果。特别是周围环境已知的全局路 径规划,其理论研究已比较完善,目前比较活跃的领 域是研究在环境未知情况下的局部规划。从研究成果 看,有以下趋势:
(1)智能化的算法将会不断涌现。模糊控制、神经网 络、遗传算法以及它们的相互结合也是研究热点之一。(2)多智能机器人系统的路径规划。随着智能机器 人工作环境复杂度和任务的加重,对其要求不再局限 于单台智能机器人,在动态环境中多智能机器人的合 作与单个机器人路径规划要很好地统一。
-246-360元/年邮局订阅号:82-946 机器人技术 中文核心期刊《微计算机信息》(嵌入式与SOC)2006年第22卷第11-2期
实验,插值A*规划的路径代价大约是A*算法的0.94,其计算时间是大约A*算法的1.35倍。图11中 展示了在125×75地图,障碍物密度是33.3%,用A*
算法和插值A*算法规划在的路径。图中黑线表示A* 算法规划的路径,红线表示插值A*算法规划的路径。从图中可以看出红线规划的路径不一定从节点的中 间通过,故路径明显的比黑线规划的路径代价少。表1 显示了两种算法比较的结果。
pages3310-3317.[3]K.Konolige.Agradientmethodforrealtimerobotcontrol.In ProceedingsoftheIEEEInternationalConferenceonIntelligent RobotsandSystems(IROS),2000.[4]R.PhilippsenandR.Siegwart.AnInterpolatedDynamic NavigationFunction.InProceedingsoftheIEEEInternational ConferenceonRoboticsandAutomation(ICRA),2005.[5]D.FergusonandA.Stentz.FieldD*:AnInterpolation-basedPath PlannerandReplanner.TechnicalReportCMURI-TR-7-16, CarnegieMellonSchoolofComputerScience,2005.[6]王俭,肖金球,王林芳.一种改进的机器人路径规划蚂蚁算法[J].微计算机信息,2005,5:53
[7]邢军,王杰.神经网络在移动机器人路径规划中的应用研究[J].微计算机信息,2005,11-2:110
作者简介:吕太之,男,1979-10,硕士研究生,高工,研究 方向人工智能与模式识别.E-mail:lvtaizhi@163.com;赵 春霞,女,1964-05,教授(博导),研究方向计算机应用、模式识别与智能系统。
Biography:LvTaiZhi,Male,1979-10,graduatestudent,senior engineer.ThestudydirectionisPatternrecognitionandAI.技 图5用A*算法和插值A*算法在125×75的栅格上规划路径,且每个节点的路径代价不一样。术 表1两种算法的比较结果 创 新
在实际的应用中,可以将实际的环境设置为不 同的路径代价。比如可以将公路设置为1,草地设置 为5,不平坦的路面设置为15,障碍物设置为31。实 验结果显示在此算法尤其适用与地形环境复杂的室 外环境中。（智械科技）
(211170江苏海事职业技术学院信息工程系)吕太之(210094江苏南京南京理工大学计算机学院)赵春霞 通讯地址:(211170江苏省南京市江宁区格致路309 号江苏海事职业技术学院信息工程系)吕太之
(收稿日期:2006.3.28)(修稿日期:2006.4.28)
(上接第246页)
[17]王超.王志良.基于个性和OCC的机器人情感建模研究[J].微 计算机信息，2005,3:180-181
5综述
插值A*算法是在A*算法基础上提出的一种启 发式路径搜索算法。虽然插值A*算法可以节省路径, 但是其计算时间也多与A*算法,当计算资源有限时, 这个算法的优越性就无法体现出来,所以每个算法都 有自己的优缺点,有各自的适用环境。
现在路径规划的算法很多,但是还没有那一个算 法可以处于绝对的地位,可以适用与所有环境。如何 将各种算法结合起来,发挥各个算法的优点,屏蔽各 个算法的缺点,在这个方面还是有很多的理论和实践 值得深入研究。
本文创新点:创造性地将插值算法加入到路径搜 索算法中,使得生成的路径更加平滑,路径代价更小。
参考文献:
[1]E.Dijkstra.Anoteontwoproblemsinconnexionwithgraphs.NumerischeMathematik,1:269-271,1959.[2]A.Stentz.Optimalandefficientpathplanningforpartially-knownenvironments.InIEEEInt.Conf.Robot.&Autom.,1994,-252-360元/年邮局订阅号:82-946
作者简介:宋晖(1974-),男,陕西周至人,西南科技大学 计算机学院讲师,硕士,主要研究方向:机器人控制技术 和嵌入式系统.E-mail:songh717@163.com;张华:(1969-),男,四川绵阳人,西南科技大学工程技术中心教授, 博士,主要研究方向:模式识别与智能系统、图像处理 与虚拟现实技术。
(621010四川绵阳西南科技大学计算机学院)宋晖 高小明
(621010四川绵阳西南科技大学工程技术中心)张华
(CollegeofComputer,ScienceSouthwestUniversityofScience &Technology,MianyangSichuan621010,China)SongHui GaoXiaoming
(Thecenterofengineerandtechnology,SouthwestUniversity ofScience&Technology,MianyangSichuan621010,China)ZhangHua
通讯地址:(621010四川绵阳四川省绵阳市西南科技 大学计算机学院)宋晖
(收稿日期:2006.3.28)(修稿日期:2006.4.25)
《 现场总线技术应用200例》
