第25卷第7期V ol.25No.7
姜gary事件
控制与决策
Control and Decision
2010年7月
文章编号: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@yahoo)
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 classified into four classes:Template based,artificial potentialfield based,map building based and artificial intelligent based approaches.First,the basic theories of the path planning methods are introduced briefly.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；Artificial potentialfield；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−)，男，福建泉州人，博士生，从事水下机器人路径规划的研究.
962控制与决策第25卷
个最优匹配模版；然后对该模版进行修正，并以此作为最后的结果.模版匹配技术在环境确定情况下，有较好的应用效果.如Vasudevan等[4]提出的基于案例的自治水下机器人(AUV)路径规划方法,Liu等[5,6]提出的清洁机器人的模版匹配路径规划方法.为了提高模版匹配路径规划技术对环境变化的适应性，部分学者提出了将模版匹配与神经网络学习相结合的方法，如Ram等[7]将基于事例的在线匹配和增强式学习相结合，提高了模版匹配规划方法中机器人的自适应性能，使机器人能部分地适应环境的变化，以及Arleo等[8,9]将环境模版与神经网络学习相结合的路径规划方法等.
模版匹配路径规划方法原理简单，在匹配成功时效果较好.但该方法的致命缺陷是依赖机器人的过去经验，如果案例库中没有足够的路径模版，就可能不到与当前状态相匹配的路径；同时该方法主要针对静态环境的路径规划，一旦环境动态变化，则较难到匹配的路径模版.这些不足严重限制了模版匹配路径规划技术的深入研究与推广应用，因此模版匹配要具有足够匹配的案例(路径)及对环境变化的适应性. 3人工势场路径规划技术
人工势场路径规划技术的基本思想是将机器人在环境中的运动视为一种机器人在虚拟的人工受力场中的运动.障碍物对机器人产生斥力，目标点对机器人产生引力，引力和斥力的合力作为机器人的控制力，从而控制机器人避开障碍物而到达目标位置.
早期人工势场路径规划研究是一种静态环境的人工势场，即将障碍物和目标物均看成是静态不变的.机器人仅根据静态环境中障碍物和目标物的具体位置规划运动路径，不考虑它们的移动速度.然而，现实世界中的环境往往是动态的，障碍物和目标物都可能是移动的.为了解决动态环境中机器人的路径规划问题,Fujimura等[10,11]提出一种相对动态的人工势场方法，将时间看成规划模型的一维参量，而移动的障碍物在扩展的模型中仍被看成是静态的，这样动态路径规划仍可运用静态路径规划方法加以实现.该方法存在的主要问题是假设机器人的轨迹总是已知的，但这一点在现实世界中难以实现.对此,Ko等[12]将障碍物的速度参量引入到斥力势函数的构造中，提出动态环境中的路径规划策略，并给出了仿真结果.但是，该方法的两个假设使其与实际的动态环境存在距离:1)仅考虑环境中障碍物的运动速度，
未考虑机器人的运动速度;2)认为障碍物与机器人之间的相对速度是固定不变的，这不是完整的动态环境.对于动态路径规划问题来说，与机器人避障相关的主要是机器人与障碍物之间的相对位置和相对速度，而非绝对位置和速度.对此,Ge等[13,14]将机器人与目标物的相对位置与相对速度引入吸引势函数，将机器人与障碍物的相对位置与相对速度引入排斥势函数，提出动态环境下的机器人路径规划算法，并将该算法应用于全方位足球移动机器人的路径规划中，取得了比较满意的仿真与实验结果.Dennis等[15-18]在此基础上，进一步考虑到多障碍物的路径规划和人工势场路径规划的局部极小问题，提出移动机器人“能见度势场”的概念，给出一种障碍物削减策略，以解决多障碍物路径规划产生的计算量激增问题.最近,Jaradat等[19,20]将模糊理论与人工势场技术相结合，提出模糊人工势场算法，并与机器人动力学模型相结合，给出了相对完整的移动机器人路径规划与驱动控制方法.
人工势场路径规划技术原理简单，便于底层的实时控制，在机器人的实时避障和平滑轨迹控制等方面得到了广泛研究.但人工势场路径规划方法通常存在局部极小点，尽管也有不少针对局部极小的改进方法，但到目前为止，仍未到完全满意的答案.另外，在引力和斥力场设计时存在人为不确定因素，在障碍物较多时还存在计算量过大等问题，这些因素的存在限制了人工势场路径规划方法的广泛应用.应用中的难点是动态环境中引力场与斥力场的设计、局部极小问题的解决.
4地图构建路径规划技术
地图构建路径规划技术，是按照机器人自身传感器搜索的障碍物信息，将机器人周围区域划分为不同的网格空间(如自由空间和限制空间等)，计算网格空间的障碍物占有情况，再依据一定规则确定最优路径[21-23].地图构建又分为路标法和栅格法，也称单元分解法.前者是构造一幅由标志点和连接边线组成的机器人可行路径图，如可视线方法[24]、切线图方法[25]、V oronoi图方法[26,27]和概率图展开法等[28,29].
可视图法将机器人看成一个点，机器人、目标点和多边形障碍物的各顶点进行组合连接，并保证这些直线均不与障碍物相交，便形成一张图，称为可视图.由于任意两直线的顶点都是可见的，从起点沿着这些直线到达目标点的所有路径均是运动物体的无碰路径，路径规划就是搜索从起点到目标点经过这些可视直线的最短距离问题；切线图法和V oronoi图法对可视图法进行了改造.切线图法以多边形障碍物模型为基础，任意形状障碍物用近似多边形替代，在自由空间中构造切线图，因此从起始点到目标点机器人是沿着切线行走，即机器人必须几乎接近障碍物行走，路径较短.但如果控制过程中产生位置误差，移动机器人碰撞的可能性会很高.V oronoi图由一系列的直线段和抛物线段构成.直线由两个障碍物的顶点或
第7期
朱大奇等：移动机器人路径规划技术综述
963
两个障碍物的边定义生成，直线段上所有点必须距离障碍物的顶点或障碍物的边相等.抛物线段由一个障碍物的顶点和一个障碍物的边定义生成，抛物线段同样要求与障碍物顶点和障碍物的边有相同距离.与切线法相比,V oronoi 图法从起始节点到目标节点的路径将会增长，但采用这种控制方式时，即使产生位置误差，移动机器人也不会碰到障碍物，安全性较高.图1为切线图法与V oronoi 图法示意图.
(a)
(b)Voronoi
图1切线图法与V oronoi 图法石家庄化工厂爆炸
栅格法是将机器人周围空间分解为相互连接且不重叠的空间单元：栅格(cell)，由这些栅格构成一个连通图，依据障碍物占有情况，在此图上搜索一条从起始栅格到目标栅格无碰撞的最优路径.这其中根据栅格处理方法的不同，又分为精确栅格法和近似栅格法，后者也称概率栅格法[30,31].精确栅格法[32]是将自由空间分解成多个不重叠的单元，这些单元的组合与原自由空间精确相等，如图2就是常用的一种精确栅格分解法—–梯形栅格分解.
图2梯形栅格分解示意图
与精确栅格法不同，近似栅格法的所有栅格都是预定的形状，通常为矩形.整个环境被分割成多个较大的矩形，每个矩形之间都是连续的.典型的方法是“四叉树”法，如果大矩形内部包含障碍物或者边界，则将其分割成4个小矩形.对所有稍大的栅格都进行这种划分，然后在划分的最后界限内形成的小栅格间重复执行该程序，直到达到解的界限为止.
地图构建法直观明了，它常与其他路径规划方法集成使用，如Araujo [33]提出的ART 神经网络的地图构建路径规划算法,Najjaran [34]提出的卡尔曼滤波器的地图构建路径规划,Yang 等[35]提出的基于生物启发神经网络与地图构建集成的清洁机器人完全覆盖路径规划技术(CCPP)等.
目前，地图构建技术已引起机器人研究领域的广泛关注，成为移动机器人路径规划的研究热点之一.但机器人传感器信息资源有限，使得网格地图障碍物信息很难计算与处理，同时由于机器人要动态快速地更新地图数据，在网格数较多、分辨率较高时难以保证路径规划的实时性.因此，地图构建方法必须在地图网格分辨率与路径规划实时性上寻求平衡.
5人工智能路径规划技术
人工智能路径规划技术是将现代人工智能技术应用于移动机器人的路径规划中，如人工神经网络、进化计算、模糊逻辑与信息融合等[36-39].遗传算法是最早应用于组合优化问题的智能优化算法，该算法及其派生算法在机器人路径规划研究领域已得到
应用[40-42].在蚁算法较好解决旅行商问题(TSP)的基础上，许多学者进一步将蚁优化算法引入到水下机器人(UV)的路径规划研究中[43,44].最近，徐玉如等[45]考虑了海流因素的影响，提出了一种基于遗传算法和粒子优化(PSO)算法的AUV 全局路径规划思想.由于模糊逻辑和信息融合技术在不确定性信息处理方面有极好的表现，且移动机器人传感器采集的环境信息存在不确定性和不完整性，使得
模糊逻辑和信息融合技术在移动机器人路径规划中有较好的应用.如Lang 等[46]针对全覆盖路径规划提出的移动机器人模糊路径规划方法,Perez 等[47]提出的基于速度场的模糊路径规划方法等,Zun 等[48,49]提出基于信息融合技术的移动机器人和无人机的路径规划与避碰方法.神经网络作为人工智能的重要内容，在移动机器人路径规划研究中得到了广泛关注[35,36,50-52]，如Ghatee 等[38]将Hopfield 神经网络应用到路径距离的优化中;Zhu 等[51]将自组织SOM 神经网络应用到多任务多机器人的任务分配与路径规划中.近年来加拿大学者Simon [53,54]提出一种新的生物启发动态神经网络模型，将神经网络的神经元与二维规划空间的离散坐标对应起来，通过规定障碍物和非障碍物对神经元输入激励和抑制的不同，直接计算相关神经元的输出，由此判定机器人的运行方向.由于该神经网络不需要学习训练过程，路径规划实时性好，同时利用神经网络本身的快速衰减特性，较好地解决了机器人路径规划的死区问题[35,55,56].图3为用于局部路径规划的生物启发神经网络结构图.图中所示为机器人(处于神经元处)传感器的感受半径，每个神经元与环境位置坐标对应，动态计算机器人邻近神经元输出，机器人根据神经元输出大小决定下一步运行目标，从而实现安全的路径规划.
人工智能技术应用于移动机器人路径规划，增强了机器人的“智能”特性，克服了许多传统规划方法
中国商标数据库964控制与决策第25卷
r=3
r=2灰铸铁牌号
r=1
r
0 j
w
ij
C k l
(,)i
图3基于生物启发神经网络路径规划
的不足.但该方法也有不足之处，有关遗传优化与蚁算法路径规划技术主要针对路径规划中的部分问题，利用进化计算进行优化处理，并与其他路径规划方法结合在一起使用，单独完成路径规划任务的情况较少.信息融合技术主要应用于机器人传感器信号处理方面，而非直接的路径规划策略.对神经网
络路径规划而言，大多数神经网络路径规划均存在规划知识的学习过程，不仅存在学习样本难以获取，而且存在学习滞后问题，从而影响神经网络路径规划的实时性.生物启发神经网络路径规划虽然实时性较好，但其输入激励与抑制的设定也存在人为不确定因素.
6移动机器人路径规划技术展望
毫无疑问，移动机器人路径规划研究已取得了重要进展，但在具体规划算法设计中，均有它们的局限性.如模版匹配方法过于依赖机器人过去的经验；人工势场路径规划方法通常存在局部极小点和计算量过大的问题；地图构建与人工神经网络技术均存在路径规划的实时性问题.从过去的研究状况和机器人未来的发展需求来看，目前移动机器人路径规划技术研究主要集中在以下几个方面.
喷雾干燥法
6.1新的路径规划方法的研究
新的路径规划方法研究，永远是移动机器人路径规划的重要内容，主要是其结合了现代科技的发展(如新的人工智能方法、新的数理方法等)，寻易于实现，同时能避开现有方法缺点的新技术[57-62].另外，现代集成路径规划算法研究也是一个重要内容，即利用已有的各种规划方法的优点，克服他们的不足.如神经网络与地图构建技术结合[35,56]、信息融合与地图构建技术集成[63]、进化计算与人工势场技术的结合[64]等.
6.2机器人底层控制与路径规划算法的结合研究
以上是从路径规划策略上看移动机器人路径规划的发展.从应用角度看，路径规划的研究极大多数集中在规划算法的设计与仿真研究上，而将路径规划算法应用于实际的报道还很少，即使是一些实物仿真实验，研究也较少.但理论研究最终要应用于实际，因此有关机器人底层控制与路径规划算法的结合研究将是它的发展方向之一[65,66]，不仅要研究路径规划算法，而且要研究机器人的动力学控制与轨迹跟踪，使机器人路径规划研究实用化、系统化.
6.3多机器人任务分配、通信协作及路径规划的
研究
以往有关单机器人的路径规划研究报道较多，而多机器人路径规划及相关技术研究较少[51,56].实际上，多机器人协作作业与路径规划在现实世界还非常常见，如足球机器人比赛、空中无人机编队飞行、自治水下机器人的合作搜救与观察等.它将涉及多方面研究，包括多机器人多任务分配问题、机器人之间的协作与通信问题、机器人的全局与局部路径规划问题、机器人传感与控制问题等.
6.4高维环境中移动机器人路径规划的研究
从路径规划的环境描述来看，针对二维平面环境的路径规划研究较多，而三维环境下的路径规划研究较少[67,68].但是，大多数机器人作业与运行是在三维空间中进行的，如飞行机器人、水下机器人等.
因此，加强三维环境中移动机器人路径规划技术的研究是机器人技术实际应用的需要，也是移动机器人路径规划技术的发展方向之一.
6.5空中机器人与水下机器人的研究
从具体的研究对象来看，移动机器人路径规划大多是针对陆地工作的智能机器人展开路径规划研究，如足球机器人、清扫机器人、收割机器人等；而针对空中飞行机器人和自治水下机器人的研究较少[42-45,69,70].陆地机器人一般是处于温和的现实世界，而空中机器人与水下机器人面临的外部环境非常恶劣，传感器资源更加有限，甚至会面临一种敌对的不确定的危险环境.因此，他们的路径规划与避险研究更加困难和迫切.
7结论
智能移动机器人路径规划问题一直是机器人研究的核心内容之一.本文从模版匹配路径规划、人工势场路径规划、地图构建路径规划和人工智能路径规划4个方面，对移动机器人路径规划技术研究现状及其未来发展进行系统的总结与评价，对移动机器人技术目前的研究与未来的发展将有一定的参考价值.
致谢感谢加拿大Guelph大学高级机器人
第7期朱大奇等：移动机器人路径规划技术综述965
与智能系统实验室主任Simon X.Yang教授在文献资料查阅及论文成文过程给予的指导与帮助！
参考文献(References)
[1]戴博，肖晓明，蔡自兴.移动机器人路径规划技术的研
究现状与展望[J].控制工程,2005,12(3):198-202.
(Dai B,Xiao X M,Cai Z X.Current status and future development of mobile robot path planning technology[J].
Control Engineering of China,2005,12(3):198-202.) [2]Hofner C,Schmidt G.Path planning and guidance
techniques for an autonomous mobile robot[J].Robotic and Autonomous Systems,1995,14(2):199-212.
[3]Schmidt G,Hofner C.An advaced planning and navigation
approach for autonomous cleaning robot operationa[C].
IEEE Int Conf Intelligent Robots System.Victoria,1998: 1230-1235.
[4]Vasudevan C,Ganesan K.Case-based path planning for
autonomous underwater vehicles[C].IEEE Int Symposium on Intelligent Control.Columbus,1994:160-165.
[5]Liu Y.Zhu S,Jin B,et al.Sensory navigation of
autonomous cleaning robots[C].The5th World Conf on Intelligent Control Automation.Hangzhou,2004:4793-4796.
[6]De Carvalho R N,Vidal H A,Vieira P,et al.Complete
coverage path planning and guidance for cleaning robots[C].IEEE Int Conf Industry Electrontics.Guimaraes, 1997:677-682.
[7]Ram A,Santamaria J C.Continuous case-based
reasoning[J].Artificial Inteligence,1997,90(1/2):25-77.
[8]Arleo A,Smeraldi F,Gerstner W.Cognitive navigation
based on non-uniform Gabor space sampling,unsupervised growing Networks,and reinforcement learning[J].IEEE Trans on Neural Network,2004,15(3):639-652.
[9]尚游，徐玉如，庞永杰.自主式水下机器人全局路径规
划的基于案例的学习算法[J].机器人,1998,20(6):427-432.
(Shang Y,Xu Y R,Pang Y J.AUV global path planning using case based learning algorithm[J].Robot,1998, 20(6):427-432.)
[10]Fujimura K,Samet H.A hierarchical strategy for path
planning among moving obstacles[J].IEEE Trans on Robotic Automation,1989,5(1):61-69.
[11]Conn R A,Kam M.Robot motion planning on N-
dimensional star worlds among moving obstacles[J].IEEE Trans on Robotic Automation,1998,14(2):320-325. [12]Ko N Y,Lee B H.Avoid ability measure in moving
obstacle avoidance problem and its use for robot motion planning[C].IEEE Int Conf on Intelligent Robots and System.Osaka,1996:1296-1303.
[13]Ge S S,Cui Y J.New potential functions for mobile robot
path planning[J].IEEE Trans on Robotic Automation, 2000,16(5):615-620.[14]Ge S S,Cui Y J.Dynamic motion planning for
mobile robots using potentialfield method[J].Autonomous Robots,2002,13(2):207-222.
[15]Erdinc S C.Path planning using potentialfields for highly
redundant manipulators[J].Robotics and Autonomous Systems,2005,52(2):209-228.
[16]Dennis B,Jeroen H,Renvan M.Real-time motion
path generation using sub-targets in a rapidly changing Environment[J].Robotics and Autonomous Systems, 2007,55(3):470-479.
[17]Velagic J,Lacevic B,PerunicicB.New concept of the
fast reactive mobile robot navigation using a pruning of relevant obstacles[C].IEEE Int Symposium on Industrial Electronics.Dubrovnik,2005:161-166.
[18]Velagic J,Lacevic B,Perunicic B.A3-level autonomous
mobile robot navigation system designed by using reasoning/search approaches[J].Robotics and Autonomous Systems,2006,54(8):989-1004.
[19]Jaradat M,Garibeh M H,Feilat E A.Dynamic motion
planning for autonomous mobile robot using fuzzy potentialfield[C].6th Int Symposium on Mechatronics and Its Applications.Sharjah,2009:24-26.
[20]Masoud A A.Managing the dynamics of a harmonic
potentialfield-guided robot in a cluttered environment[J].
IEEE Trans on Industrial Electronics,2009,56(2):488-496.
[21]Toledo F J,Luis J D,Tomas L M,et al.Map building
with ultrasonic sensors of indoor environments using neural networks[C].IEEE Int Conf Systems,Man,and Cybernetics.Nashville,2000:920-925.
[22]Wong S C,MacDonald B A.A topological coverage
algorithm for mobile robots[C].IEEE Int Conf Intelligent Robots System.Las Vegas,2003:1685-1690.
[23]Oh J S,Choi Y H,Park J B,et al.Complete coverage
navigation of cleaning robots using triangular-cell-based map[J].IEEE Trans on Industrial Electronics,2004,51(3): 718-726.
[24]Tarjan R E.A unified approach to path problems[J].J of the
Association for Computing Machinery,1981,28(3):577-593.
[25]Canny J F.The complexity of robot motion planning[M].
Boston:MIT Press,1988.
[26]Takahashi O,Schilling R J.Motion planning in a plane
using generalized V oronoi diagrams[J].IEEE Trans on Robotics and Automation,1989,5(2):143-150.
[27]Avneesh S,Erik A,Sean C,et al.Real-time path
planning in dynamic virtual environment using multiagent navigation graphs[J].IEEE Trans on Visualization and Computer Graphics,2008,14(3):526-538.
[28]Kavraki L E,Svestka P,Latombe J C,et al.Probabilistic
roadmaps for path planning in high-dimensional
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议