机器人技术
文章编号：１００８—帖７０（２咖６）１１—２－０２４４—０３
中文核心期刊‘微计算机信息＞（嵌入式与ＳＯＣ）２００６年第２２卷第１１－２期
智能机器人路径规划及算法研究
Ｒｅｓｅａｒｃｈ
ｏｎ
ＰａｔｈＰ｜ａｎｎｉｎｇａｎｄＡｌｇｏｒｉｔｈｍｓｆｏｒＩｎｔｅｌｌｉｇｅｎｔＲｏｂｏ￡ｓ
（西南科技大学）宋晖张华高小明
ＳＯＮＧＨＵＩ
ＺＨＡＮＧＨＵＡＧＡＯＸｌＡＯＭＩＮＧ
摘要：路径规划技术是机器人控制技术研究中的一个重要问题。目前的研究主要分为全局规划方法和局部规划方法两大类。在对一些较有代表性的研究思想及其相关算法分析的基础上，比较各种方法的优缺点，提出了机器人路径规划今后的研究重点。关键词：智能机器人；全局规划；局部规划；优化算法中图分类号：ＴＰ２４２．６文献标识码：Ａ．
ｐｌａｎｎｉｎｇｔｅｃｈｎｏｌｏｇｙｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｐｒｏｂｌｅｍｉｎｉｎｔｅｌｌｉｇｅｎｔｒｏｂｏｔ．Ａｔｐｒｅｓｅｎｔ，ｔｈｅｔｗｏｒｅｓｅａｒｃｈｗａｙｓ：ｏｎｅｉｓｇｌｏｂａｌｐｌａｎｎｉｎｇａｎｄｔｈｅｏｔｈｅｒｉｓｌｏｃａｌｐｌａｎｎｉｎｇ．Ｏｎｔｈｅｂａｓｉｓｏｆｔｈｅａｎａｌｙｓｉｓｏｆｓｏｍｅｔｙｐｉｃａｌｉｄｅａｓ，ｍｅｔｈｏｄｓａｎｄｒｅｌａｔｅｄａｌｇｏｒｉｔｈｍｓｏｆｐａｔｈｐｌａｎｎｉｎｇｆｏｒｉｎｔｅｌｌｉｇｅｎｔｒｏｂｏｔ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｅｍｐｈａｓｉｓｏｆｒｏｂｏｔｐａｔｈｐｌａｎｎｉｎｇ．
Ａｂｓｔｒａｃｔ：Ｐａｔｈ
Ｋｅｙｗｏｒｄｓ：ｉｎｔｅｌｌｌｇｅｎｔｒｏｂｏｔ，ｇｌｏｂａｌｐｌａｎｎｉｎｇ，ｌｏｃａｌｐｈ瑚ｌｉｎｇ，ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓ
１引言
自５０年代世界上第一台机器人装置诞生以来，机器人的发展经历了一个从低级到高级的发展过程。
第一代示教再现型机器人，可以根据人示教的结果再现出动作．它对于外界的环境没有感知。在２０世纪７０年代后期人们开始研究第二代机器人：带感觉的机器人。这种机器人是类似人某种感觉的功能，如力觉、触觉、滑觉、视觉、听觉。第三代机器人是智能机器人阶段。机器人通过各种传感器获取环境信息，利用人工智能进行识别、理解、推理并做出判断和决策来完成一定的任务。这就要求智能机器人除了具有感知环境和简单的适应环境能力外，还具有较强的识别理解功能和决策规划功能。
①复杂性：在复杂环境中，机器人路径规划非常复杂，且需要很大的计算量。
②随机性：复杂环境的变化往往存在很多随机性
和不确定因素。
③多约束：机器人的形状、速度和加速度等对机器人的运动存在约束。
３全局路径规划
全局规划方法主包括构型空间法、拓扑法、栅格解耦法、自由空间法、神经网络法等。
３．１构型空间法
构型空间法的基本思想是将机器人缩小为一个点。根据机器人形状和尺寸将障碍物进行拓展。其中研究较成熟的有：可视图法和优化算法。
３．１．１可视图法
可视图法中的路径图由捕捉到的存在于机器人一维网络曲线（称为路径图）自由空间中的节点组成。路径的初始状态和目标状态同路径图中的点相对应，这样路径规划问题就演变为在这些点间搜索路径的问题。要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物，即直线是“可视的”，然后采用某种方法搜索从起始点到目标点的最优路径。搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。该法能够求得最短路径，但假设忽略智能机器人的尺寸大小。使得机器人通过障碍物顶点时离障碍物太近甚至接触，并且搜索时间长。
３．１．２优化算法
此法可删除一些不必要的连线以简化可视图、缩短搜索时间。能够求得最短路径。但假设机器人的尺
２智能机器人的路径规划技术分类
智能机器人路径规划是指在有障碍物的工作环境中，如何寻找一条从给定起点到终点适当的运动路径，使机器人在运动过程中能安全、无碰地绕过所有障碍物。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。根据机器人对环境信息掌握的程度不同将智能机器人路径规划分为基于模型的全局路径规划和基于传感器的局部路径规划。前者是指作业环境的全部信息已知，又称静态或离线路径规划；后者是指作业环境信息全部未知或部分未知，又称动态或在线路径规划。智能机器人路径规划存在以下特点：
宋晖：讲师硕士
基金项目：国家自然科学基金（６０４０４０１４）；西南科技大学青年基金资助项目（ＺＫ０５３０３３）
一２４４—３６０元，年邮局订阅号：８２—９４６
万方数据
机器人技术
寸大小忽略不计，会使机器人通过障碍物顶点时离障在满足精度要求的情况下，用神经网络来表示环境则碍物太近甚至接触，并且搜索时间长。另外的缺点就可以取得较好的效果。神经网络在全局路径规划的应是此法缺乏灵活性，即一旦机器人的起点和目标点发用，将障碍约束转化为一个惩罚函数，从而使一个约生改变，就要重新构造可视图，比较麻烦。这类算法包束优化问题转化为一个无约束最优化问题，然后以神括Ｄｉｊｋｓｔｒａ算法，Ａ木算法等。
经网络来描述碰撞惩罚函数，进行全局路径规划。
３．２拓扑法
虽然神经网络在路径规划中有学习能力强等优拓扑法将规划空间分割成具有拓扑特征子空间，点，但整体应用却不是非常成功，主要原因是智能机根据彼此连通性建立拓扑网络，在网络上寻找起始点器人所遇到的环境是千变万化的、随机的，并且很难到目标点的拓扑路径，最终由拓扑路径求出几何路以数学的公式来描述。
径。拓扑法基本思想是降维法，即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性４局部路径规划
的问题。优点在于利用拓扑特征大大缩小了搜索空局部路径规划的主要方法有：人工势场法、模糊间。算法复杂性仅依赖于障碍物数目，理论上是完备逻辑控制法、混合法、滚动窗口法等。
的。而且拓扑法通常不需要机器人的准确位置，对于４．１人工势场法
位置误差也就有了更好的鲁棒性；缺点是建立拓扑网人工势场法是由Ｋｈａｔｉｂ提出的一种虚拟力法。其络的过程相当复杂，特别在增加障碍物时如何有效地基本思想是将智能机器人在环境中的运动视为一种修正已经存在的拓扑网是有待解决的问题。
虚拟人工受力场中的运动。把智能机器人在环境中的３．３栅格解耦法
运动视为一种在抽象的人造受力场中的运动，目标点栅格解耦法是目前研究最广泛的路径规划方法。对智能机器人产生引力，障碍物对智能机器人产生斥该方法将机器人的工作空间解耦为多个简单的区域，力，最后通过求合力来控制智能机器人的运动。该法结一般称为栅格。由这些栅格构成了一个连通图，在这个构简单，便于低层的实时控制，在实时避障和平滑的连通图上搜索一条从起始栅格到目标栅格的路径，这条路径是用栅格的序号来表示的。整个图被分割成多
轨迹控制方面，得到了广泛应用，其不足在于存在局部最优解，容易产生死锁现象，因而可能使智能机器个较大的矩形，每个矩形之间都是连续的。如果大矩形人在到达目标点之前就停留在局部最优点。
内部包含障碍物或者边界，则又被分割成４个小矩形，４．２模糊逻辑控制算法
对所有稍大的栅格都进行这种划分，然后在划分的最模糊方法不需要建立完整的环境模型，不需要进后界限内形成的小栅格间重复执行程序，直到达到解行复杂的计算和推理．尤其对传感器信息的精度要求的界限为止。该法以栅格为单位记录环境信息，环境不高。对机器人周围环境和机器人的位姿信息的具有被量化成具有一定分辨率的栅格，栅格的大小直接影不确定性、不敏感的特点，能使机器人的行为体现出响着环境信息存储量的大小和规划时间的长短，栅格很好的一致性、稳定性和连续性，能比较圆满地解决划分大了，环境信息存储量小，规划时间短，分辨率下一些规划问题．对处理未知环境下的规划问题显示出降；栅格划分小了，环境分辨率高。
很大优越性，对于解决用通常的定量方法来说是很复３．４自由空间法
杂的问题或当外界只能提供定性近似的、不确定信息自由空间法采用预先定义的如广义锥形和凸多数据时非常有效。但模糊规则往往是人们通过经验预边形等基本形状构造自由空间，并将自由空间表示为先制定的，所以存在着无法学习、灵活性差的缺点。
连通图。通过搜索连通图来进行路径规划。自由空间４．３遗传算法
的构造方法是：从障碍物的一个顶点开始，依次作其遗传算法是一种借鉴生物界自然选择和进化机它顶点的链接线，删除不必要的链接线，使得链接线制发展起来的高度并行、随机、自适应搜索算法。它采与障碍物边界所围成的每一个自由空间都是面积最用群体搜索技术，通过选择、交叉和变异等一系列遗大的凸多边形：连接各链接线的中点形成的网络图即传操作，使种群得以进化。避免了困难的理论推导，直为机器人可自由栅格法运动的路线。其优点是比较灵接获得问题的最优解。其基本思想是：将路径个体表活，、起始点和目标点的改变不会造成连通图的重构，达为路径中一系列中途点，并转换为二进制串。首先缺点是复杂程度与障碍物的多少成正比，且有时无法初始化路径群体，然后进行遗传操作，如选择、交叉、获得最短路径。
复制、变异。经过若干代进化以后，停止进化，输出当３．５神经网络法
前最优个体。
人工神经网络是由大量神经元相互连接而形成遗传算法存在运算时间长，实现路径的在线规划的自适应非线性动态系统，对于大范围的工作环境，
困难。而且在机器人的路径规划问题中应用存在着个
万
方数据＠眦一邮局订冁８２铷３６０，Ｌ／－ｑ－＿２４５—
机器人技术
中文核心期刊＜微计算机信息＞（嵌入式与ＳＯＣ）２００６年第２２卷第１１－２期
体编码不合理、效率低、进化效果不明显等问题。
（３）多传感器信息融合用于路径规划。单传感器难４．４混合法
以保证输入信息准确与可靠。多传感器所获得信息具
混合法是一种用于半自主智能机器人路径规划有冗余性，互补性，实时陛和低代价性，且可以快速并
的模糊神经网络方法。所谓半自主智能机器人就是具行分析现场环境。
有在人类示教基础上增加了学习功能的器件的机器（４）基于功能／；行为的智能机器人路径规划。基于模人。这种方法采用模糊描述来完成机器人行为编码，同型自顶向下的感知一建模一规划一动作是一种典型慎思时重复使用神经网络自适应技术。由机器人上的传感结构，称为基于功能的控制体系结构。基于行为的方器提供局部的环境输入，由内部模糊神经网络进行环法是一种自底向上的构建系统方法，并与环境交互作
境预测，进而可以在未知环境下规划机器人路径。此用中最终达到目标。基于功能珩为的机器人控制结构
外，也有人提出基于模糊神经网络和遗传算法的机器融合了两者优点，这是研究的新动向之一。
人自适应控制方法。将规划过程分为离线学习和在线学习两部分。该方法是一种混合的机器人自适应控制６结语
方法，可以自适应调整机器人的行走路线，达到避障和本文作者的创新点：深入研究了国内外关于机器路径最短的双重优化。
人路径规划算法的发展现状、最新进展和各种算法的４．５滚动窗口法
优缺点。并对未来机器人路径规划技术的发展趋势进滚动窗口借鉴了预测控制滚动优化原理，把控制行了综合分析：指出机器人路径规划技术未来的研究论中优化和反馈两种基本机制合理地融为一体，使得重点是“仿人、仿生”智能，并还将紧密的结合认知科整个控制既基于模型与优化的，又是基于反馈的。基学、人工智能、与计算智能的研究成果，提升机器人行
于滚动窗口的路径规划算法的基本思路：首先进行场为的智能度。
景预测，在滚动的每一步，机器人根据其探测到的局参考文献：
部窗口范围内的环境信息。用启发式方法生成局部子［１】宗光华．机器人的创意设计与实践叫】．北京：北京航空航天大目标，并对动态障碍物的运动进行预测，判断机器人 学出版社，２００３．
行进是否可能与动态障碍物相碰撞。其次机器人根据［２】Ｒｏｂｉｎ著，杜军平译．人工智能机器人学导论［Ｍ］．北京：电子工业出版社．２００３．
窗口内的环境信息及预测结果，选择局部规划算法，［３］席裕庚，张纯刚．一类动态不确定环境下机器人的滚动路径确定向子目标行进的局部路径，并依所规划的局部路规划叨．自动化学报，２００２，２８．
径行进一步，窗口相应向前滚动。然后在新的滚动窗【４】诸静．机器人与控制技术［Ｍ】．杭州：浙江大学出版社，１９９１．１３产生后，根据传感器所获取的最新信息，对窗口内［５］ＸｕＷ
Ｌ，ＴＳＯＳ
Ｋ．Ｓｅｎｓｏｒｂａｓｅｄｆｕｚｚｙｒｅａｃｔｉｖｅｎａｖｉｇａｔｉｏｎｏｆ
ａ
的环境及障碍物运动状况进行更新。该方法放弃了对ｍｏｂｉｌｅ
ｒｏｂｏｔｔｈｒｏｕｇｈｌｏｃａｌｔａｒｇｅｔｓｗｉｔｃｈｉｎｇ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓ
ｏｎ
全局最有目标的过于理想的要求。利用机器人实时测Ｓｙｓｔｅｍｓ，１９９９，２９．
得的局部环境信息，以滚动方式进行在线规划，具有［６］Ｋｒｓｈｎａ
Ｋ
Ｍ，ＫａｌｒａＰＫ．Ｐｅｒｃｅｐｔｉｏｎａｎｄｒｅｍｅｍｂｅｒａｎｃｅｏｆｔｈｅ
良好的避碰能力。但存在着规划的路径是非最优的问ｅｎｖｉｒｏｎｍｅｎｔｄｕｒｉｎｇ
ｒｅａｌ－ｔｉｍｅ
ｎａｖｉｇａｔｉｏｎ
ｏｆ
ａ
ｍｏｂｉｌｅ
ｒｏｂｏｔ［Ｊ】．
题，即存在局部极值问题。
ＲｏｂｔｉｃｓａｎｄＡｕｔｏｎｏｍｏｕｓＳｙｓｔｅｍｓ，２００１，３７．
［７】邢军，王杰．神经网络在移动机器人路径规划中的应用研究
５智能机器人路径规划技术的展望
【Ｊ］．微计算机信息，２００５，２２：１１０—１１１
随着计算机、传感器及控制技术的发展，特别是［８】Ｋｈａｔｉｂ．Ｒｅａｌ－ｔｉｍｅｏｂｓｔａｃｌｅｆｏｒ
ｍａｎｉｐｕｌａｔｏｒｓａｎｄｍｏｂｉｌｅｒｏｂｏｔ
各种新算法不断涌现，智能机器人路径规划技术已经［Ｊ］．ＴｈｅＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌ
ｏｆ
ＲｏｂｏｔｉｃＲｅｓｅａｒｃｈ．１９８６，１．
取得了丰硕研究成果。特别是周围环境已知的全局路［９】薛艳茹，郑冰等．基于模糊控制信息融合方法的机器人导航径规划，其理论研究已比较完善，目前比较活跃的领系统［Ｊ】．微计算机信息，２００５，２２：１０７—１０９
域是研究在环境未知情况下的局部规划。从研究成果［１０】周明，孙树栋．遗传算法原理及应用［Ｍ】．北京：：国防工业出版看。有以下趋势：
社。２０００．
［１１】Ｋａｚｕｏ（１）智能化的算法将会不断涌现。模糊控制、神经网ＳｕｇｉｈａｒａｊｏｈｎＳｍｉｔｈ．ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓｆｏｒＡｄａｐｔｉｖｅ
Ｍｏｔｉｏｎ
Ｐｌａｎｎｉｎｇ
ｏｆ
ａｎ
Ａｕｔｏｎｏｍｏｕｓ
ＭｏｂｉｌｅＲｏｂｏｔ［Ａ】．Ｐｒｏｃｅｅｄｉｎｇｓ
络、遗传算法以及它们的相互结合也是研究热点之一。１９９７ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍ
ｏｎ
ＣｏｍｐｕｔａｔｉｏｎａｌＩｎｔｅｌｌｉｇｅｎｃｅ
（２）多智能机器人系统的路径规划。随着智能机器ｉｎ
ＲｏｂｏｔｉｃｓａｎｄＡｕｔｏｍａｔｉｏｎ［Ｃ］．１９９７．
人工作环境复杂度和任务的加重，对其要求不再局限［１２］１ＴｓｏｕｋａｌａｓＬＨ，ＨｏｕｓｔｉｓＥＮ，ＪｏｎｅｓＧＶ．Ｎｅｕｒｏｆｕｚｚｙ于单台智能机器人，在动态环境中多智能机器人的合ｍｏｆｉｏｎｐｌａｎｎｅｒｓｆｏｒｉｎｔｅｌｌｉｇｅｎｔｒｏｂｏｔｓ
叨．Ｊｏｕｍａｌｏｆ
Ｉｎｔｅｌｌｉｇｅｎｔａｎ—
作与单个机器人路径规划要很好地统一。
ｄＲｏｂｏｔｉｃＳｙｓｔｅｍｓ，１９９７，１９．丌转第２５２页）
一２４６—３６０元，年邮局订阅号：８２－９４６
万
方数据
机器人技术
中文核心期刊《：微计算机信息＞（嵌入式与ＳＯＣ）２００６年第２２卷第１１・２期
实验．插值Ａ木规划的路径代价大约是Ａ木算法的ｐａｇｅｓ３３１０－３３１７．
［３１Ｋ．Ｋｏｎｏｌｉｇｅ．Ａｇｒａｄｉｅｎｔｍｅｔｈｏｄｆｏｒｒｅａｌｔｉｍｅｒｏｂｏｔｃｏｎｔｒ０１．Ｉｎ０．９４．其计算时间是大约Ａ木算法的１．３５倍。图１１中
Ｉｎｔｅｌｌｉｇｅｎｔ展示了在１２５×７５地图，障碍物密度是３３．３％，用Ａ木ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ
ＲｏｂｏｔｓａｎｄＳｙｓｔｅｍｓ０ＲＯＳ），２０００．算法和插值Ａ】Ｉｃ算法规划在的路径。图中黑线表示Ａ半
［４１Ｒ．ＰｈｉｌｉｐｐｓｅｎａｎｄＲ．Ｓｉｅｇｗａｒｔ．ＡｎＩｎｔｅｒｐｏｌａｔｅｄＤｙｎａｍｉｃ算法规划的路径，红线表示插值Ａ术算法规划的路径。
ＮａｖｉｇａｔｉｏｎＦｕｎｃｔｉｏｎ．ＩｎＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌ从图中可以看出红线规划的路径不一定从节点的中
ＣｏｎｆｅｒｅｎｃｅＲｏｂｏｔｉｃｓａｎｄＡｕｔｏｍａｔｉｏｎ（ｍｍＡ），２００５・间通过。故路径明显的比黑线规划的路径代价少。表１
【５】Ｄ．ＦｅｒｇｕｓｏｎａｎｄＡ．Ｓｔｅｎｔｚ．ＦｉｅｌｄＤ＋：ＡｎＩｎｔｅｒｐｏｌａｔｉｏｎ—ｂａｓｅｄＰａｔｈ显示了两种算法比较的结果。
ｏｎ
ｏｎ
ＰｌａｎｎｅｒａｎｄＲｅｐｌａｎｎｅｒ．ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ
Ｃａｒｎｅｇｉｅ
ＣＭＵＲＩ—ＴＲ一７—１６．
ＭｅＨｏｎＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，２００５．
［６１＝Ｆ俭，肖金球，王林芳．一种改进的机器人路径规划蚂蚁算法【Ｊ】．微计算机信息。２００５，５：５３
［７］邢军，王杰．神经网络在移动机器人路径规划中的应用研究［Ｊ］．微计算机信息，２００５，１１－２：１１０
作者简介：吕太之，男，１９７９—１０，硕士研究生，高工，研究方向人工智能与模式识别．Ｅ—ｍａｉｈｌｖｔａｉｚｈｉ＠１６３．ｃｏｒｎ；赵春霞，女，１９６４—０５，教授（博导），研究方向计算机应用、模式识别与智能系统。
图５用舻算法和插值舻算法在１２５×７５的栅格上规划路径，
且每个节点的路径代价不一样。
表１两种算法的比较结果
Ａ｝算法
插值Ａ｝算法
４．６５８７
Ｏ。９４５
Ｂｉｏｇｒａｐｈｙ：ＬｖＴａｉＺｈｉ，Ｍａｌｅ，１９７９－１０，ｇｒａｄｕａｔｅ
ｉｓ
Ｐａｔｔｅｒｎｒｅｃｏｇｎｉｔｉｏｎ
ｓｔｕｄｅｎｔ，ｓｅｎｉｏｒ
ｅｎｇｉｎｅｅｒ．Ｔｈｅ８ｔｕｄｙｄｉｒｅｃｔｉｏｎ
ａｎｄ
ＡＩ．
（２１１１７０江苏海事职业技术学院信息工程系）吕太之
（２１∞９４江苏南京南京理工大学计算机学院）赵春霞
通讯地址：（２１１１７０江苏省南京市江宁区格致路３０９号江苏海事职业技术学院信息工程系）吕太之
（收稿日期：２００６．３．２８）（修稿Ｅｔ期：２００６．４．２８）
计算时间（秒）路径长度（相对的）
３．５８７９Ｅ．７
１．ＯＯ
在实际的应用中。可以将实际的环境设置为不同的路径代价。比如可以将公路设置为１，草地设置为５，不平坦的路面设置为１５，障碍物设置为３１。实验结果显示在此算法尤其适用与地形环境复杂的室外环境中。
（上接第２４６页）
［１３］王超．王志良．基于个性和ＯＣＣ的机器人情感建模研究［Ｊ］．微计算机信息。２００５，３：１８０—１８１
５综述
插值Ａ，．ｃ算法是在Ａ，｜ｃ算法基础上提出的一种启发式路径搜索算法。虽然插值Ａ木算法可以节省路径，但是其计算时间也多与Ａ木算法，当计算资源有限时，这个算法的优越性就无法体现出来，所以每个算法都有自己的优缺点，有各自的适用环境。
现在路径规划的算法很多。但是还没有那一个算法可以处于绝对的地位。可以适用与所有环境。如何将各种算法结合起来，发挥各个算法的优点，屏蔽各个算法的缺点，在这个方面还是有很多的理论和实践值得深入研究。
．
作者简介：宋晖（１９７４一），男，陕西周至人，西南科技大学计算机学院讲师，硕士，主要研究方向：机器人控制技术
和嵌入式系统．Ｅ—ｍａｉｌ：ｓｏｎｇｈ７１７＠１６３．ｃｏｍ；张华：（１９６９一
），男，四川绵阳人，西南科技大学工程技术中心教授，博士，主要研究方向：模式识别与智能系统、图像处理与虚拟现实技术。
（６２１０１０四川绵阳西南科技大学计算机学院）宋晖高小明
（６２１０１０四川绵阳西南科技大学工程技术中心）张华
（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒ。ＳｃｉｅｎｃｅＳｏｕｔｈｗｅｓｔＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅ
＆Ｔｅｃｈｎｏｌｏｇｙ，ＭｉａｎｙａｎｇＳｉｃｈｕａｎ６２１０１０，Ｃｈｉｎａ）ＳｏｎｇＨｕｉ
ＧａｏＸｉａｏｍｉｎｇ
本文创新点：创造性地将插值算法加入到路径搜索算法中，使得生成的路径更加平滑，路径代价更小。
参考文献：［１】Ｅ．Ｄｉｊｋｓｔｒａ．Ａ
ｎｏｔｅ
ｏｎ
（Ｔｈｅ
ｃｅｎｔｅｒ
ｏｆｅｎｇｉｎｅｅｒａｎｄｔｅｃｈｎｏｌｏｇｙ，ＳｏｕｔｈｗｅｓｔＵｎｉｖｅｒｓｉｔｙ
６２１０１０＇．Ｃｈｉｎａ）
ｏｆＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，ＭｉａｎｙａｎｇＳｉｃｈｕａｎ
Ｚｈａｎｇ
Ｈｕａ
ｔｗｏ
ｐｒｏｂｌｅｍｓｉｎ
ｃｏｎｎｅｘｉｏｎ
ｗｉｔｈｇｒａｐｈｓ．
ＮｕｍｅｆｉｓｅｈｅＭａｔｈｅｍａｔｉｋ，１：２６９—２７１，１９５９．
通讯地址：（６２１０１０四川绵阳四川省绵阳市西南科技大学计算机学院）宋晖
（收稿日期：２００６．３．２８）偿｝稿日期：２００６．４．２５）
【２】Ａ．Ｓｔｅｎｔｚ．Ｏｐｔｉｍａｌａｎｄ
ｅｆｆｉｃｉｅｎｔ
ｐａｔｈｐｌａｎｎｉｎｇｆｏｒ
ｐ枷ａｕｙ—
ｋｎｏｗｎｅｎｖｉｒｏｎｍｅｎｔｓ．ＩｎＩＥＥＥＩｎｔ．Ｃｏｎｆ．Ｒｏｂｏｔ．＆Ａｕｔｏｍ．，１９９４，
一２５２—３６０元，年邮局订阅号：８２．９４６
万方数据
智能机器人路径规划及算法研究
作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：
宋晖， 张华， 高小明， SONG HUI， ZHANG HUA， GAOXIAOMING
宋晖,高小明,SONG HUI,GAOXIAOMING(621010,四川,绵阳,西南科技大学,计算机学院)， 张华,ZHANG HUA(621010,四川,绵阳,西南科技大学,工程技术中心)微计算机信息
CONTROL & AUTOMATION2006,22(32)23次
参考文献(13条)
1.宗光华 机器人的创意设计与实践 20032.Robin;杜军平 人工智能机器入学导论 2003
3.席裕庚,张纯刚 一类动态不确定环境下机器人的滚动路径规划[期刊论文]-自动化学报 2002(2)4.诸静 机器人与控制技术 1991
5.Xu W L;TSO S K Sensor based fuzzy reactive navigation of a mobile robot through local targetswitching 1999
6.Krishna K M;Kalra P K Perception and re me mberance of the environment during real-time navigationof a mobile robot 2001
7.邢军,王杰 神经网络在移动机器人路径规划中的应用研究[期刊论文]-微计算机信息 2005(32)8.Khatib Real-time obstacle for manipulators and mobile robot 1986(01)
9.薛艳茹,郑冰,郝兴贞,李谦 基于模糊控制信息融合方法的机器人导航系统[期刊论文]-微计算机信息 2005(32)10.周明;孙树栋 遗传算法原理及应用 2000
11.Kazuo Sugihara;John Smith Genetic Algorithms for Adaptive Motion Planning of an Autonomous MobileRobot 1997
12.TsoukalasLH;HoustisEN;JonesGV Neurofuzzy motionplannersforintelligentrobots 199713.王超,王志良 基于个性和OCC的机器人情感建模研究[期刊论文]-微计算机信息 2005(3)
本文读者也读过(2条)
1. 蒋玉杰.曾岑.Jiang Yujie.Zeng Cen 清洁机器人基于遗传算法的全区域路径规划[期刊论文]-机械制造2009,47(5)
2. 王作为.张汝波.WANG Zuo-wei.ZHANG Ru-bo 基于进化算法的智能机器人行为学习研究[期刊论文]-哈尔滨工程大学学报2006,27(z1)
引证文献(18条)
1.张江梅,王姮 一种机器人寻迹行走控制系统[期刊论文]-微计算机信息 2009(05)
2.胡春安,王华金 基于AI-CODE智能坦克机器人的设计[期刊论文]-江西理工大学学报 2009(06)3.王挺,麦范金,郑安兵 基于极坐标、栅格和模糊方法的路径规划[期刊论文]-微计算机信息 2008(05)4.魏宁,刘一松 基于栅格模型的移动机器人全局路径规划研究[期刊论文]-微计算机信息 2008(11)5.李林雷 基于弹性带理论的机器人路径规划算法研究[学位论文]硕士 2013
6.邓本再,王江银,张中景,王国伟,张岳刚 基于专家PID控制的足球机器人截球的研究[期刊论文]-工业控制计算机2010(08)
智能机器人路径规划及算法研究
作者：
作者单位：
刊名：
英文刊名：
年，卷(期)：
被引用次数：宋晖， 张华， 高小明， SONG HUI， ZHANG HUA， GAOXIAOMING宋晖,高小明,SONG HUI,GAOXIAOMING(621010,四川,绵阳,西南科技大学,计算机学院)， 张华,ZHANG HUA(621010,四川,绵阳,西南科技大学,工程技术中心)微计算机信息CONTROL & AUTOMATION2006,22(32)23次
参考文献(13条)
1.宗光华 机器人的创意设计与实践 2003
2.Robin;杜军平 人工智能机器入学导论 2003
3.席裕庚,张纯刚 一类动态不确定环境下机器人的滚动路径规划[期刊论文]-自动化学报 2002(2)
4.诸静 机器人与控制技术 1991
5.Xu W L;TSO S K Sensor based fuzzy reactive navigation of a mobile robot through local targetswitching 1999
6.Krishna K M;Kalra P K Perception and re me mberance of the environment during real-time navigationof a mobile robot 2001
7.邢军,王杰 神经网络在移动机器人路径规划中的应用研究[期刊论文]-微计算机信息 2005(32)
8.Khatib Real-time obstacle for manipulators and mobile robot 1986(01)
9.薛艳茹,郑冰,郝兴贞,李谦 基于模糊控制信息融合方法的机器人导航系统[期刊论文]-微计算机信息 2005(32)
10.周明;孙树栋 遗传算法原理及应用 2000
11.Kazuo Sugihara;John Smith Genetic Algorithms for Adaptive Motion Planning of an Autonomous MobileRobot 1997
12.TsoukalasLH;HoustisEN;JonesGV Neurofuzzy motionplannersforintelligentrobots 1997
13.王超,王志良 基于个性和OCC的机器人情感建模研究[期刊论文]-微计算机信息 2005(3)
本文读者也读过(2条)
1. 蒋玉杰.曾岑.Jiang Yujie.Zeng Cen 清洁机器人基于遗传算法的全区域路径规划[期刊论文]-机械制造2009,47(5)
2. 王作为.张汝波.WANG Zuo-wei.ZHANG Ru-bo 基于进化算法的智能机器人行为学习研究[期刊论文]-哈尔滨工程大学学报2006,27(z1)
引证文献(18条)
1.张江梅,王姮 一种机器人寻迹行走控制系统[期刊论文]-微计算机信息 2009(05)
2.胡春安,王华金 基于AI-CODE智能坦克机器人的设计[期刊论文]-江西理工大学学报 2009(06)
3.王挺,麦范金,郑安兵 基于极坐标、栅格和模糊方法的路径规划[期刊论文]-微计算机信息 2008(05)
4.魏宁,刘一松 基于栅格模型的移动机器人全局路径规划研究[期刊论文]-微计算机信息 2008(11)
5.李林雷 基于弹性带理论的机器人路径规划算法研究[学位论文]硕士 2013
6.邓本再,王江银,张中景,王国伟,张岳刚 基于专家PID控制的足球机器人截球的研究[期刊论文]-工业控制计算机2010(08)
7.王欣 基于三角网追踪的机器人路径规划[学位论文]硕士 2009
8.谢文明 动态环境下基于人工势场引导进化算法的移动机器人路径规划[学位论文]硕士 2008
9.李星毅,郑亮,施化吉 基于NN改进PSO算法的机器人路径规划[期刊论文]-微计算机信息 2009(12)
10.郭世龙,李文锋,李波 基于Player/Stage仿真机器人的绘图系统实现[期刊论文]-微计算机信息 2008(26)
11.张红平 楼宇三维寻径分析研究[学位论文]硕士 2011
12.向东伟 基于ARM的深海机器人轨迹跟踪的研究[学位论文]硕士 2010
13.蒋亮谋 基于信息融合的深海集矿机路径规划[学位论文]硕士 2008
14.王赟 MiroSot足球机器人的路径规划研究[学位论文]硕士 2007
15.梅传根 连以粒子群最佳化为基础之机器人足球之研究[学位论文]硕士 2009
16.亓晓彬 集中式机器人足球系统的决策与无线通信研究[学位论文]硕士 2008
17.吴海波 基于四足机器人的视觉避障的研究[学位论文]硕士 2008
18.雷永锋 基于AVR微控制器的仿生六足机器人研究[学位论文]硕士 2008
引用本文格式：宋晖.张华.高小明.SONG HUI.ZHANG HUA.GAOXIAOMING 智能机器人路径规划及算法研究[期刊论文]-微计算机信息 2006(32)
机器人技术
文章编号：１００８—帖７０（２咖６）１１—２－０２４４—０３
中文核心期刊‘微计算机信息＞（嵌入式与ＳＯＣ）２００６年第２２卷第１１－２期
智能机器人路径规划及算法研究
Ｒｅｓｅａｒｃｈ
ｏｎ
ＰａｔｈＰ｜ａｎｎｉｎｇａｎｄＡｌｇｏｒｉｔｈｍｓｆｏｒＩｎｔｅｌｌｉｇｅｎｔＲｏｂｏ￡ｓ
（西南科技大学）宋晖张华高小明
ＳＯＮＧＨＵＩ
ＺＨＡＮＧＨＵＡＧＡＯＸｌＡＯＭＩＮＧ
摘要：路径规划技术是机器人控制技术研究中的一个重要问题。目前的研究主要分为全局规划方法和局部规划方法两大类。在对一些较有代表性的研究思想及其相关算法分析的基础上，比较各种方法的优缺点，提出了机器人路径规划今后的研究重点。关键词：智能机器人；全局规划；局部规划；优化算法中图分类号：ＴＰ２４２．６文献标识码：Ａ．
ｐｌａｎｎｉｎｇｔｅｃｈｎｏｌｏｇｙｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｐｒｏｂｌｅｍｉｎｉｎｔｅｌｌｉｇｅｎｔｒｏｂｏｔ．Ａｔｐｒｅｓｅｎｔ，ｔｈｅｔｗｏｒｅｓｅａｒｃｈｗａｙｓ：ｏｎｅｉｓｇｌｏｂａｌｐｌａｎｎｉｎｇａｎｄｔｈｅｏｔｈｅｒｉｓｌｏｃａｌｐｌａｎｎｉｎｇ．Ｏｎｔｈｅｂａｓｉｓｏｆｔｈｅａｎａｌｙｓｉｓｏｆｓｏｍｅｔｙｐｉｃａｌｉｄｅａｓ，ｍｅｔｈｏｄｓａｎｄｒｅｌａｔｅｄａｌｇｏｒｉｔｈｍｓｏｆｐａｔｈｐｌａｎｎｉｎｇｆｏｒｉｎｔｅｌｌｉｇｅｎｔｒｏｂｏｔ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｅｍｐｈａｓｉｓｏｆｒｏｂｏｔｐａｔｈｐｌａｎｎｉｎｇ．
Ａｂｓｔｒａｃｔ：Ｐａｔｈ
Ｋｅｙｗｏｒｄｓ：ｉｎｔｅｌｌｌｇｅｎｔｒｏｂｏｔ，ｇｌｏｂａｌｐｌａｎｎｉｎｇ，ｌｏｃａｌｐｈ瑚ｌｉｎｇ，ｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓ
１引言
自５０年代世界上第一台机器人装置诞生以来，机器人的发展经历了一个从低级到高级的发展过程。
第一代示教再现型机器人，可以根据人示教的结果再现出动作．它对于外界的环境没有感知。在２０世纪７０年代后期人们开始研究第二代机器人：带感觉的机器人。这种机器人是类似人某种感觉的功能，如力觉、触觉、滑觉、视觉、听觉。第三代机器人是智能机器人阶段。机器人通过各种传感器获取环境信息，利用人工智能进行识别、理解、推理并做出判断和决策来完成一定的任务。这就要求智能机器人除了具有感知环境和简单的适应环境能力外，还具有较强的识别理解功能和决策规划功能。
①复杂性：在复杂环境中，机器人路径规划非常复杂，且需要很大的计算量。
②随机性：复杂环境的变化往往存在很多随机性
和不确定因素。
③多约束：机器人的形状、速度和加速度等对机器人的运动存在约束。
３全局路径规划
全局规划方法主包括构型空间法、拓扑法、栅格解耦法、自由空间法、神经网络法等。
３．１构型空间法
构型空间法的基本思想是将机器人缩小为一个点。根据机器人形状和尺寸将障碍物进行拓展。其中研究较成熟的有：可视图法和优化算法。
３．１．１可视图法
可视图法中的路径图由捕捉到的存在于机器人一维网络曲线（称为路径图）自由空间中的节点组成。路径的初始状态和目标状态同路径图中的点相对应，这样路径规划问题就演变为在这些点间搜索路径的问题。要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物，即直线是“可视的”，然后采用某种方法搜索从起始点到目标点的最优路径。搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。该法能够求得最短路径，但假设忽略智能机器人的尺寸大小。使得机器人通过障碍物顶点时离障碍物太近甚至接触，并且搜索时间长。
３．１．２优化算法
此法可删除一些不必要的连线以简化可视图、缩短搜索时间。能够求得最短路径。但假设机器人的尺
２智能机器人的路径规划技术分类
智能机器人路径规划是指在有障碍物的工作环境中，如何寻找一条从给定起点到终点适当的运动路径，使机器人在运动过程中能安全、无碰地绕过所有障碍物。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。根据机器人对环境信息掌握的程度不同将智能机器人路径规划分为基于模型的全局路径规划和基于传感器的局部路径规划。前者是指作业环境的全部信息已知，又称静态或离线路径规划；后者是指作业环境信息全部未知或部分未知，又称动态或在线路径规划。智能机器人路径规划存在以下特点：
宋晖：讲师硕士
基金项目：国家自然科学基金（６０４０４０１４）；西南科技大学青年基金资助项目（ＺＫ０５３０３３）
一２４４—３６０元，年邮局订阅号：８２—９４６
万方数据
机器人技术
寸大小忽略不计，会使机器人通过障碍物顶点时离障在满足精度要求的情况下，用神经网络来表示环境则碍物太近甚至接触，并且搜索时间长。另外的缺点就可以取得较好的效果。神经网络在全局路径规划的应是此法缺乏灵活性，即一旦机器人的起点和目标点发用，将障碍约束转化为一个惩罚函数，从而使一个约生改变，就要重新构造可视图，比较麻烦。这类算法包束优化问题转化为一个无约束最优化问题，然后以神括Ｄｉｊｋｓｔｒａ算法，Ａ木算法等。
经网络来描述碰撞惩罚函数，进行全局路径规划。
３．２拓扑法
虽然神经网络在路径规划中有学习能力强等优拓扑法将规划空间分割成具有拓扑特征子空间，点，但整体应用却不是非常成功，主要原因是智能机根据彼此连通性建立拓扑网络，在网络上寻找起始点器人所遇到的环境是千变万化的、随机的，并且很难到目标点的拓扑路径，最终由拓扑路径求出几何路以数学的公式来描述。
径。拓扑法基本思想是降维法，即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性４局部路径规划
的问题。优点在于利用拓扑特征大大缩小了搜索空局部路径规划的主要方法有：人工势场法、模糊间。算法复杂性仅依赖于障碍物数目，理论上是完备逻辑控制法、混合法、滚动窗口法等。
的。而且拓扑法通常不需要机器人的准确位置，对于４．１人工势场法
位置误差也就有了更好的鲁棒性；缺点是建立拓扑网人工势场法是由Ｋｈａｔｉｂ提出的一种虚拟力法。其络的过程相当复杂，特别在增加障碍物时如何有效地基本思想是将智能机器人在环境中的运动视为一种修正已经存在的拓扑网是有待解决的问题。
虚拟人工受力场中的运动。把智能机器人在环境中的３．３栅格解耦法
运动视为一种在抽象的人造受力场中的运动，目标点栅格解耦法是目前研究最广泛的路径规划方法。对智能机器人产生引力，障碍物对智能机器人产生斥该方法将机器人的工作空间解耦为多个简单的区域，力，最后通过求合力来控制智能机器人的运动。该法结一般称为栅格。由这些栅格构成了一个连通图，在这个构简单，便于低层的实时控制，在实时避障和平滑的连通图上搜索一条从起始栅格到目标栅格的路径，这条路径是用栅格的序号来表示的。整个图被分割成多
轨迹控制方面，得到了广泛应用，其不足在于存在局部最优解，容易产生死锁现象，因而可能使智能机器个较大的矩形，每个矩形之间都是连续的。如果大矩形人在到达目标点之前就停留在局部最优点。
内部包含障碍物或者边界，则又被分割成４个小矩形，４．２模糊逻辑控制算法
对所有稍大的栅格都进行这种划分，然后在划分的最模糊方法不需要建立完整的环境模型，不需要进后界限内形成的小栅格间重复执行程序，直到达到解行复杂的计算和推理．尤其对传感器信息的精度要求的界限为止。该法以栅格为单位记录环境信息，环境不高。对机器人周围环境和机器人的位姿信息的具有被量化成具有一定分辨率的栅格，栅格的大小直接影不确定性、不敏感的特点，能使机器人的行为体现出响着环境信息存储量的大小和规划时间的长短，栅格很好的一致性、稳定性和连续性，能比较圆满地解决划分大了，环境信息存储量小，规划时间短，分辨率下一些规划问题．对处理未知环境下的规划问题显示出降；栅格划分小了，环境分辨率高。
很大优越性，对于解决用通常的定量方法来说是很复３．４自由空间法
杂的问题或当外界只能提供定性近似的、不确定信息自由空间法采用预先定义的如广义锥形和凸多数据时非常有效。但模糊规则往往是人们通过经验预边形等基本形状构造自由空间，并将自由空间表示为先制定的，所以存在着无法学习、灵活性差的缺点。
连通图。通过搜索连通图来进行路径规划。自由空间４．３遗传算法
的构造方法是：从障碍物的一个顶点开始，依次作其遗传算法是一种借鉴生物界自然选择和进化机它顶点的链接线，删除不必要的链接线，使得链接线制发展起来的高度并行、随机、自适应搜索算法。它采与障碍物边界所围成的每一个自由空间都是面积最用群体搜索技术，通过选择、交叉和变异等一系列遗大的凸多边形：连接各链接线的中点形成的网络图即传操作，使种群得以进化。避免了困难的理论推导，直为机器人可自由栅格法运动的路线。其优点是比较灵接获得问题的最优解。其基本思想是：将路径个体表活，、起始点和目标点的改变不会造成连通图的重构，达为路径中一系列中途点，并转换为二进制串。首先缺点是复杂程度与障碍物的多少成正比，且有时无法初始化路径群体，然后进行遗传操作，如选择、交叉、获得最短路径。
复制、变异。经过若干代进化以后，停止进化，输出当３．５神经网络法
前最优个体。
人工神经网络是由大量神经元相互连接而形成遗传算法存在运算时间长，实现路径的在线规划的自适应非线性动态系统，对于大范围的工作环境，
困难。而且在机器人的路径规划问题中应用存在着个
万
方数据＠眦一邮局订冁８２铷３６０，Ｌ／－ｑ－＿２４５—
机器人技术
中文核心期刊＜微计算机信息＞（嵌入式与ＳＯＣ）２００６年第２２卷第１１－２期
体编码不合理、效率低、进化效果不明显等问题。
（３）多传感器信息融合用于路径规划。单传感器难４．４混合法
以保证输入信息准确与可靠。多传感器所获得信息具
混合法是一种用于半自主智能机器人路径规划有冗余性，互补性，实时陛和低代价性，且可以快速并
的模糊神经网络方法。所谓半自主智能机器人就是具行分析现场环境。
有在人类示教基础上增加了学习功能的器件的机器（４）基于功能／；行为的智能机器人路径规划。基于模人。这种方法采用模糊描述来完成机器人行为编码，同型自顶向下的感知一建模一规划一动作是一种典型慎思时重复使用神经网络自适应技术。由机器人上的传感结构，称为基于功能的控制体系结构。基于行为的方器提供局部的环境输入，由内部模糊神经网络进行环法是一种自底向上的构建系统方法，并与环境交互作
境预测，进而可以在未知环境下规划机器人路径。此用中最终达到目标。基于功能珩为的机器人控制结构
外，也有人提出基于模糊神经网络和遗传算法的机器融合了两者优点，这是研究的新动向之一。
人自适应控制方法。将规划过程分为离线学习和在线学习两部分。该方法是一种混合的机器人自适应控制６结语
方法，可以自适应调整机器人的行走路线，达到避障和本文作者的创新点：深入研究了国内外关于机器路径最短的双重优化。
人路径规划算法的发展现状、最新进展和各种算法的４．５滚动窗口法
优缺点。并对未来机器人路径规划技术的发展趋势进滚动窗口借鉴了预测控制滚动优化原理，把控制行了综合分析：指出机器人路径规划技术未来的研究论中优化和反馈两种基本机制合理地融为一体，使得重点是“仿人、仿生”智能，并还将紧密的结合认知科整个控制既基于模型与优化的，又是基于反馈的。基学、人工智能、与计算智能的研究成果，提升机器人行
于滚动窗口的路径规划算法的基本思路：首先进行场为的智能度。
景预测，在滚动的每一步，机器人根据其探测到的局参考文献：
部窗口范围内的环境信息。用启发式方法生成局部子［１】宗光华．机器人的创意设计与实践叫】．北京：北京航空航天大目标，并对动态障碍物的运动进行预测，判断机器人 学出版社，２００３．
行进是否可能与动态障碍物相碰撞。其次机器人根据［２】Ｒｏｂｉｎ著，杜军平译．人工智能机器人学导论［Ｍ］．北京：电子工业出版社．２００３．
窗口内的环境信息及预测结果，选择局部规划算法，［３］席裕庚，张纯刚．一类动态不确定环境下机器人的滚动路径确定向子目标行进的局部路径，并依所规划的局部路规划叨．自动化学报，２００２，２８．
径行进一步，窗口相应向前滚动。然后在新的滚动窗【４】诸静．机器人与控制技术［Ｍ】．杭州：浙江大学出版社，１９９１．１３产生后，根据传感器所获取的最新信息，对窗口内［５］ＸｕＷ
Ｌ，ＴＳＯＳ
Ｋ．Ｓｅｎｓｏｒｂａｓｅｄｆｕｚｚｙｒｅａｃｔｉｖｅｎａｖｉｇａｔｉｏｎｏｆ
ａ
的环境及障碍物运动状况进行更新。该方法放弃了对ｍｏｂｉｌｅ
ｒｏｂｏｔｔｈｒｏｕｇｈｌｏｃａｌｔａｒｇｅｔｓｗｉｔｃｈｉｎｇ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓ
ｏｎ
全局最有目标的过于理想的要求。利用机器人实时测Ｓｙｓｔｅｍｓ，１９９９，２９．
得的局部环境信息，以滚动方式进行在线规划，具有［６］Ｋｒｓｈｎａ
Ｋ
Ｍ，ＫａｌｒａＰＫ．Ｐｅｒｃｅｐｔｉｏｎａｎｄｒｅｍｅｍｂｅｒａｎｃｅｏｆｔｈｅ
良好的避碰能力。但存在着规划的路径是非最优的问ｅｎｖｉｒｏｎｍｅｎｔｄｕｒｉｎｇ
ｒｅａｌ－ｔｉｍｅ
ｎａｖｉｇａｔｉｏｎ
ｏｆ
ａ
ｍｏｂｉｌｅ
ｒｏｂｏｔ［Ｊ】．
题，即存在局部极值问题。
ＲｏｂｔｉｃｓａｎｄＡｕｔｏｎｏｍｏｕｓＳｙｓｔｅｍｓ，２００１，３７．
［７】邢军，王杰．神经网络在移动机器人路径规划中的应用研究
５智能机器人路径规划技术的展望
【Ｊ］．微计算机信息，２００５，２２：１１０—１１１
随着计算机、传感器及控制技术的发展，特别是［８】Ｋｈａｔｉｂ．Ｒｅａｌ－ｔｉｍｅｏｂｓｔａｃｌｅｆｏｒ
ｍａｎｉｐｕｌａｔｏｒｓａｎｄｍｏｂｉｌｅｒｏｂｏｔ
各种新算法不断涌现，智能机器人路径规划技术已经［Ｊ］．ＴｈｅＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌ
ｏｆ
ＲｏｂｏｔｉｃＲｅｓｅａｒｃｈ．１９８６，１．
取得了丰硕研究成果。特别是周围环境已知的全局路［９】薛艳茹，郑冰等．基于模糊控制信息融合方法的机器人导航径规划，其理论研究已比较完善，目前比较活跃的领系统［Ｊ】．微计算机信息，２００５，２２：１０７—１０９
域是研究在环境未知情况下的局部规划。从研究成果［１０】周明，孙树栋．遗传算法原理及应用［Ｍ】．北京：：国防工业出版看。有以下趋势：
社。２０００．
［１１】Ｋａｚｕｏ（１）智能化的算法将会不断涌现。模糊控制、神经网ＳｕｇｉｈａｒａｊｏｈｎＳｍｉｔｈ．ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓｆｏｒＡｄａｐｔｉｖｅ
Ｍｏｔｉｏｎ
Ｐｌａｎｎｉｎｇ
ｏｆ
ａｎ
Ａｕｔｏｎｏｍｏｕｓ
ＭｏｂｉｌｅＲｏｂｏｔ［Ａ】．Ｐｒｏｃｅｅｄｉｎｇｓ
络、遗传算法以及它们的相互结合也是研究热点之一。１９９７ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍ
ｏｎ
ＣｏｍｐｕｔａｔｉｏｎａｌＩｎｔｅｌｌｉｇｅｎｃｅ
（２）多智能机器人系统的路径规划。随着智能机器ｉｎ
ＲｏｂｏｔｉｃｓａｎｄＡｕｔｏｍａｔｉｏｎ［Ｃ］．１９９７．
人工作环境复杂度和任务的加重，对其要求不再局限［１２］１ＴｓｏｕｋａｌａｓＬＨ，ＨｏｕｓｔｉｓＥＮ，ＪｏｎｅｓＧＶ．Ｎｅｕｒｏｆｕｚｚｙ于单台智能机器人，在动态环境中多智能机器人的合ｍｏｆｉｏｎｐｌａｎｎｅｒｓｆｏｒｉｎｔｅｌｌｉｇｅｎｔｒｏｂｏｔｓ
叨．Ｊｏｕｍａｌｏｆ
Ｉｎｔｅｌｌｉｇｅｎｔａｎ—
作与单个机器人路径规划要很好地统一。
ｄＲｏｂｏｔｉｃＳｙｓｔｅｍｓ，１９９７，１９．丌转第２５２页）
一２４６—３６０元，年邮局订阅号：８２－９４６
万
方数据
机器人技术
中文核心期刊《：微计算机信息＞（嵌入式与ＳＯＣ）２００６年第２２卷第１１・２期
实验．插值Ａ木规划的路径代价大约是Ａ木算法的ｐａｇｅｓ３３１０－３３１７．
［３１Ｋ．Ｋｏｎｏｌｉｇｅ．Ａｇｒａｄｉｅｎｔｍｅｔｈｏｄｆｏｒｒｅａｌｔｉｍｅｒｏｂｏｔｃｏｎｔｒ０１．Ｉｎ０．９４．其计算时间是大约Ａ木算法的１．３５倍。图１１中
Ｉｎｔｅｌｌｉｇｅｎｔ展示了在１２５×７５地图，障碍物密度是３３．３％，用Ａ木ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ
ＲｏｂｏｔｓａｎｄＳｙｓｔｅｍｓ０ＲＯＳ），２０００．算法和插值Ａ】Ｉｃ算法规划在的路径。图中黑线表示Ａ半
［４１Ｒ．ＰｈｉｌｉｐｐｓｅｎａｎｄＲ．Ｓｉｅｇｗａｒｔ．ＡｎＩｎｔｅｒｐｏｌａｔｅｄＤｙｎａｍｉｃ算法规划的路径，红线表示插值Ａ术算法规划的路径。
ＮａｖｉｇａｔｉｏｎＦｕｎｃｔｉｏｎ．ＩｎＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌ从图中可以看出红线规划的路径不一定从节点的中
ＣｏｎｆｅｒｅｎｃｅＲｏｂｏｔｉｃｓａｎｄＡｕｔｏｍａｔｉｏｎ（ｍｍＡ），２００５・间通过。故路径明显的比黑线规划的路径代价少。表１
【５】Ｄ．ＦｅｒｇｕｓｏｎａｎｄＡ．Ｓｔｅｎｔｚ．ＦｉｅｌｄＤ＋：ＡｎＩｎｔｅｒｐｏｌａｔｉｏｎ—ｂａｓｅｄＰａｔｈ显示了两种算法比较的结果。
ｏｎ
ｏｎ
ＰｌａｎｎｅｒａｎｄＲｅｐｌａｎｎｅｒ．ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ
Ｃａｒｎｅｇｉｅ
ＣＭＵＲＩ—ＴＲ一７—１６．
ＭｅＨｏｎＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，２００５．
［６１＝Ｆ俭，肖金球，王林芳．一种改进的机器人路径规划蚂蚁算法【Ｊ】．微计算机信息。２００５，５：５３
［７］邢军，王杰．神经网络在移动机器人路径规划中的应用研究［Ｊ］．微计算机信息，２００５，１１－２：１１０
作者简介：吕太之，男，１９７９—１０，硕士研究生，高工，研究方向人工智能与模式识别．Ｅ—ｍａｉｈｌｖｔａｉｚｈｉ＠１６３．ｃｏｒｎ；赵春霞，女，１９６４—０５，教授（博导），研究方向计算机应用、模式识别与智能系统。
图５用舻算法和插值舻算法在１２５×７５的栅格上规划路径，
且每个节点的路径代价不一样。
表１两种算法的比较结果
Ａ｝算法
插值Ａ｝算法
４．６５８７
Ｏ。９４５
Ｂｉｏｇｒａｐｈｙ：ＬｖＴａｉＺｈｉ，Ｍａｌｅ，１９７９－１０，ｇｒａｄｕａｔｅ
ｉｓ
Ｐａｔｔｅｒｎｒｅｃｏｇｎｉｔｉｏｎ
ｓｔｕｄｅｎｔ，ｓｅｎｉｏｒ
ｅｎｇｉｎｅｅｒ．Ｔｈｅ８ｔｕｄｙｄｉｒｅｃｔｉｏｎ
ａｎｄ
ＡＩ．
（２１１１７０江苏海事职业技术学院信息工程系）吕太之
（２１∞９４江苏南京南京理工大学计算机学院）赵春霞
通讯地址：（２１１１７０江苏省南京市江宁区格致路３０９号江苏海事职业技术学院信息工程系）吕太之
（收稿日期：２００６．３．２８）（修稿Ｅｔ期：２００６．４．２８）
计算时间（秒）路径长度（相对的）
３．５８７９Ｅ．７
１．ＯＯ
在实际的应用中。可以将实际的环境设置为不同的路径代价。比如可以将公路设置为１，草地设置为５，不平坦的路面设置为１５，障碍物设置为３１。实验结果显示在此算法尤其适用与地形环境复杂的室外环境中。
（上接第２４６页）
［１３］王超．王志良．基于个性和ＯＣＣ的机器人情感建模研究［Ｊ］．微计算机信息。２００５，３：１８０—１８１
５综述
插值Ａ，．ｃ算法是在Ａ，｜ｃ算法基础上提出的一种启发式路径搜索算法。虽然插值Ａ木算法可以节省路径，但是其计算时间也多与Ａ木算法，当计算资源有限时，这个算法的优越性就无法体现出来，所以每个算法都有自己的优缺点，有各自的适用环境。
现在路径规划的算法很多。但是还没有那一个算法可以处于绝对的地位。可以适用与所有环境。如何将各种算法结合起来，发挥各个算法的优点，屏蔽各个算法的缺点，在这个方面还是有很多的理论和实践值得深入研究。
．
作者简介：宋晖（１９７４一），男，陕西周至人，西南科技大学计算机学院讲师，硕士，主要研究方向：机器人控制技术
和嵌入式系统．Ｅ—ｍａｉｌ：ｓｏｎｇｈ７１７＠１６３．ｃｏｍ；张华：（１９６９一
），男，四川绵阳人，西南科技大学工程技术中心教授，博士，主要研究方向：模式识别与智能系统、图像处理与虚拟现实技术。
（６２１０１０四川绵阳西南科技大学计算机学院）宋晖高小明
（６２１０１０四川绵阳西南科技大学工程技术中心）张华
（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒ。ＳｃｉｅｎｃｅＳｏｕｔｈｗｅｓｔＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅ
＆Ｔｅｃｈｎｏｌｏｇｙ，ＭｉａｎｙａｎｇＳｉｃｈｕａｎ６２１０１０，Ｃｈｉｎａ）ＳｏｎｇＨｕｉ
ＧａｏＸｉａｏｍｉｎｇ
本文创新点：创造性地将插值算法加入到路径搜索算法中，使得生成的路径更加平滑，路径代价更小。
参考文献：［１】Ｅ．Ｄｉｊｋｓｔｒａ．Ａ
ｎｏｔｅ
ｏｎ
（Ｔｈｅ
ｃｅｎｔｅｒ
ｏｆｅｎｇｉｎｅｅｒａｎｄｔｅｃｈｎｏｌｏｇｙ，ＳｏｕｔｈｗｅｓｔＵｎｉｖｅｒｓｉｔｙ
６２１０１０＇．Ｃｈｉｎａ）
ｏｆＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，ＭｉａｎｙａｎｇＳｉｃｈｕａｎ
Ｚｈａｎｇ
Ｈｕａ
ｔｗｏ
ｐｒｏｂｌｅｍｓｉｎ
ｃｏｎｎｅｘｉｏｎ
ｗｉｔｈｇｒａｐｈｓ．
ＮｕｍｅｆｉｓｅｈｅＭａｔｈｅｍａｔｉｋ，１：２６９—２７１，１９５９．
通讯地址：（６２１０１０四川绵阳四川省绵阳市西南科技大学计算机学院）宋晖
（收稿日期：２００６．３．２８）偿｝稿日期：２００６．４．２５）
【２】Ａ．Ｓｔｅｎｔｚ．Ｏｐｔｉｍａｌａｎｄ
ｅｆｆｉｃｉｅｎｔ
ｐａｔｈｐｌａｎｎｉｎｇｆｏｒ
ｐ枷ａｕｙ—
ｋｎｏｗｎｅｎｖｉｒｏｎｍｅｎｔｓ．ＩｎＩＥＥＥＩｎｔ．Ｃｏｎｆ．Ｒｏｂｏｔ．＆Ａｕｔｏｍ．，１９９４，
一２５２—３６０元，年邮局订阅号：８２．９４６
万方数据
智能机器人路径规划及算法研究
作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：
宋晖， 张华， 高小明， SONG HUI， ZHANG HUA， GAOXIAOMING
宋晖,高小明,SONG HUI,GAOXIAOMING(621010,四川,绵阳,西南科技大学,计算机学院)， 张华,ZHANG HUA(621010,四川,绵阳,西南科技大学,工程技术中心)微计算机信息
CONTROL & AUTOMATION2006,22(32)23次
参考文献(13条)
1.宗光华 机器人的创意设计与实践 20032.Robin;杜军平 人工智能机器入学导论 2003
3.席裕庚,张纯刚 一类动态不确定环境下机器人的滚动路径规划[期刊论文]-自动化学报 2002(2)4.诸静 机器人与控制技术 1991
5.Xu W L;TSO S K Sensor based fuzzy reactive navigation of a mobile robot through local targetswitching 1999
6.Krishna K M;Kalra P K Perception and re me mberance of the environment during real-time navigationof a mobile robot 2001
7.邢军,王杰 神经网络在移动机器人路径规划中的应用研究[期刊论文]-微计算机信息 2005(32)8.Khatib Real-time obstacle for manipulators and mobile robot 1986(01)
9.薛艳茹,郑冰,郝兴贞,李谦 基于模糊控制信息融合方法的机器人导航系统[期刊论文]-微计算机信息 2005(32)10.周明;孙树栋 遗传算法原理及应用 2000
11.Kazuo Sugihara;John Smith Genetic Algorithms for Adaptive Motion Planning of an Autonomous MobileRobot 1997
12.TsoukalasLH;HoustisEN;JonesGV Neurofuzzy motionplannersforintelligentrobots 199713.王超,王志良 基于个性和OCC的机器人情感建模研究[期刊论文]-微计算机信息 2005(3)
本文读者也读过(2条)
1. 蒋玉杰.曾岑.Jiang Yujie.Zeng Cen 清洁机器人基于遗传算法的全区域路径规划[期刊论文]-机械制造2009,47(5)
2. 王作为.张汝波.WANG Zuo-wei.ZHANG Ru-bo 基于进化算法的智能机器人行为学习研究[期刊论文]-哈尔滨工程大学学报2006,27(z1)
引证文献(18条)
1.张江梅,王姮 一种机器人寻迹行走控制系统[期刊论文]-微计算机信息 2009(05)
2.胡春安,王华金 基于AI-CODE智能坦克机器人的设计[期刊论文]-江西理工大学学报 2009(06)3.王挺,麦范金,郑安兵 基于极坐标、栅格和模糊方法的路径规划[期刊论文]-微计算机信息 2008(05)4.魏宁,刘一松 基于栅格模型的移动机器人全局路径规划研究[期刊论文]-微计算机信息 2008(11)5.李林雷 基于弹性带理论的机器人路径规划算法研究[学位论文]硕士 2013
6.邓本再,王江银,张中景,王国伟,张岳刚 基于专家PID控制的足球机器人截球的研究[期刊论文]-工业控制计算机2010(08)
智能机器人路径规划及算法研究
作者：
作者单位：
刊名：
英文刊名：
年，卷(期)：
被引用次数：宋晖， 张华， 高小明， SONG HUI， ZHANG HUA， GAOXIAOMING宋晖,高小明,SONG HUI,GAOXIAOMING(621010,四川,绵阳,西南科技大学,计算机学院)， 张华,ZHANG HUA(621010,四川,绵阳,西南科技大学,工程技术中心)微计算机信息CONTROL & AUTOMATION2006,22(32)23次
参考文献(13条)
1.宗光华 机器人的创意设计与实践 2003
2.Robin;杜军平 人工智能机器入学导论 2003
3.席裕庚,张纯刚 一类动态不确定环境下机器人的滚动路径规划[期刊论文]-自动化学报 2002(2)
4.诸静 机器人与控制技术 1991
5.Xu W L;TSO S K Sensor based fuzzy reactive navigation of a mobile robot through local targetswitching 1999
6.Krishna K M;Kalra P K Perception and re me mberance of the environment during real-time navigationof a mobile robot 2001
7.邢军,王杰 神经网络在移动机器人路径规划中的应用研究[期刊论文]-微计算机信息 2005(32)
8.Khatib Real-time obstacle for manipulators and mobile robot 1986(01)
9.薛艳茹,郑冰,郝兴贞,李谦 基于模糊控制信息融合方法的机器人导航系统[期刊论文]-微计算机信息 2005(32)
10.周明;孙树栋 遗传算法原理及应用 2000
11.Kazuo Sugihara;John Smith Genetic Algorithms for Adaptive Motion Planning of an Autonomous MobileRobot 1997
12.TsoukalasLH;HoustisEN;JonesGV Neurofuzzy motionplannersforintelligentrobots 1997
13.王超,王志良 基于个性和OCC的机器人情感建模研究[期刊论文]-微计算机信息 2005(3)
本文读者也读过(2条)
1. 蒋玉杰.曾岑.Jiang Yujie.Zeng Cen 清洁机器人基于遗传算法的全区域路径规划[期刊论文]-机械制造2009,47(5)
2. 王作为.张汝波.WANG Zuo-wei.ZHANG Ru-bo 基于进化算法的智能机器人行为学习研究[期刊论文]-哈尔滨工程大学学报2006,27(z1)
引证文献(18条)
1.张江梅,王姮 一种机器人寻迹行走控制系统[期刊论文]-微计算机信息 2009(05)
2.胡春安,王华金 基于AI-CODE智能坦克机器人的设计[期刊论文]-江西理工大学学报 2009(06)
3.王挺,麦范金,郑安兵 基于极坐标、栅格和模糊方法的路径规划[期刊论文]-微计算机信息 2008(05)
4.魏宁,刘一松 基于栅格模型的移动机器人全局路径规划研究[期刊论文]-微计算机信息 2008(11)
5.李林雷 基于弹性带理论的机器人路径规划算法研究[学位论文]硕士 2013
6.邓本再,王江银,张中景,王国伟,张岳刚 基于专家PID控制的足球机器人截球的研究[期刊论文]-工业控制计算机2010(08)
7.王欣 基于三角网追踪的机器人路径规划[学位论文]硕士 2009
8.谢文明 动态环境下基于人工势场引导进化算法的移动机器人路径规划[学位论文]硕士 2008
9.李星毅,郑亮,施化吉 基于NN改进PSO算法的机器人路径规划[期刊论文]-微计算机信息 2009(12)
10.郭世龙,李文锋,李波 基于Player/Stage仿真机器人的绘图系统实现[期刊论文]-微计算机信息 2008(26)
11.张红平 楼宇三维寻径分析研究[学位论文]硕士 2011
12.向东伟 基于ARM的深海机器人轨迹跟踪的研究[学位论文]硕士 2010
13.蒋亮谋 基于信息融合的深海集矿机路径规划[学位论文]硕士 2008
14.王赟 MiroSot足球机器人的路径规划研究[学位论文]硕士 2007
15.梅传根 连以粒子群最佳化为基础之机器人足球之研究[学位论文]硕士 2009
16.亓晓彬 集中式机器人足球系统的决策与无线通信研究[学位论文]硕士 2008
17.吴海波 基于四足机器人的视觉避障的研究[学位论文]硕士 2008
18.雷永锋 基于AVR微控制器的仿生六足机器人研究[学位论文]硕士 2008
引用本文格式：宋晖.张华.高小明.SONG HUI.ZHANG HUA.GAOXIAOMING 智能机器人路径规划及算法研究[期刊论文]-微计算机信息 2006(32)