（模式识别与智能系统专业论文）基于智能算法的移动机器人路径规划研究.pdf

浙江大学硕士学位论文 摘要 移动机器人是一种集环境感知、动态决策与规划、行为控制与执行等多项功 能于一体的高智能化机器系统，移动机器人导航是移动机器人研究的重要方向， 而路径规划是移动机器人导航的最基本环节之一。本论文主要研究了单移动机器 人和多移动机器人在静态和动态环境下的智能路径规划问题。本文的主要工作包 括： 1 综述了移动机器人当前的研究进展和趋势，介绍了移动机器人路径规划 的研究背景及国内外同类课题的研究现状，并列举了全局和局部情况下的移动机 器人路径规划的常用方法，介绍了多移动机器人的路径规划方法，最后展望了移 动机器人路径规划的发展趋势。 2 研究了动态不确定环境下的移动机器人路径规划问题，动态不确定环境 下的移动机器人路径规划属于局部路径规划问题，针对全局环境未知且存在动态 障碍物情况下的移动机器人路径规划问题，文中提出了一种结合粒子群算法和滚 动优化策略的动态路径规划方法。通过在一系列移动空间窗口中进行在线规划来 充分利用机器人实时测得的局部环境信息，并用粒子群算法求解每一个移动窗口 内的最优路径。为及时躲避动态障碍物，提出了一种适用于动态未知环境下的适 应度函数。仿真试验表明，该方法克服了现有局部路径规划方法的高复杂性的缺 点，算法操作简单、具有全局寻优能力、收敛速度快、鲁棒性好，可以满足机器 人在复杂未知动态环境下路径规划的实时性要求。 3 研究了多机器人协作路径规划的问题，随着机器人研究领域的深入，多 机器人已经受到越来越多的人的关注，本文分析了竞争型协同进化算法的特点， 研究了竞争型协进化在多机器人协作路径规划领域中的应用。 4 以两个机器人抬木头作为多机器人合作的实例，运用本文算法求解未知 环境下两个机器人合作抬木头的问题。 最后，总结了全文的研究内容，提出了单移动机器人路径规划以及多移动 机器人协作有待于进一步解决的问题，展望了移动机器人路径规划的进一步研究 方向。 关键词：移动机器人；路径规划；障碍物：粒子群算法；遗传算法；协进化 浙江大学硕士学位论文 a b s t r a c t m o b i l er o b o ti so n ek i n do fh i g hi n t e l l e c t u a l i z e dm a c h i n es y s t e m i th a sm a n y f u n c t i o n s ，i n c l u d i n ge n v i r o n m e n ts e n s a t i o n , d y n a m i cd e c i s i o n - m a k i n ga n dp l a n n i n g ， b e h a v i o rc o n t r o la n de x e c u t i o n ，e t c m o b i l er o b o tn a v i g a t i o ni sa ni m p o r t a n td i r e c t i o n o f t h er o b o ts t u d y , a n dt h ep a t hp l a n n i n gi st h eb a s i cp o i n to f r o b o tn a v i g a t i o n i nt h i s p a p e r , t h ep a t hp l a n n i n go fs i n g l em o b i l er o b o ta n dm u l t i - r o b o t su n d e r t h es t a t i ca n d t h ed y n a m i ce n v i r o n m e n ti sm a i n l ys t u d i e d t h em a i nw o r kr e s u l ti n c l u d e s ： 1 s u m m a r i z ec u r r e n tr e s e a r c hp r o g r e s sa n dt h et e n d e n c yo fm o b i l er o b o t ，t h e r e s e a r c hb a c k g r o u n da n dd o m e s t i ca n di n t e r n a t i o n a ls i m i l a rr e s e a r c ha tp r e s e n ta r e i n t r o d u c e d , a n dac o n c i s er e v i e wo f p a t hp l a n n i n gi ns t a t i ca n dd y m m i ce n v i r o n m e n t i sa l s op r e s e n t e d t h ep a t hp l a n r l i l l go fm u l t i - r o b o t ss y s t e mi si n t r o d u c e d t h e d e v e l o p m e n tt r e n do f p a t hp l a n n i n gi se x p e c t e di nt h ee n d 2 t h ep a t hp l a n n i n go fm o b i l er o b o ti nd y n a m i cu n c e r t a i ne n v i r o n m e n ti s s t u d i e d , t h i sp r o b l e mi sal o c a lp a t hp l a n n i n gp r o b l e m , an e wp l a n n e rb a s e do ht h e c o m b i n a t i o no fap a r t i c l es w a r n la l g o r i t h ma n dar e c e d i n gh o r i z o no p t i m i z a t i o ni s d e v e l o p e di nt h i sp a p e rf o rt h ep a t hp l a n n i n go fs i n g l em o b i l er o b o ti nag l o b a l u n c e r t a i ne n v i r o n m e n tw i t hd y n a m i co b s t a c l e s t h er o b o tp a t hi sp l a n n e do n - l i n ei nn s e r i e so fr e c e d i n gs p a t i a lw i n d o w st om a k ef u l lu s eo ft h el o c a le n v i r o n m e n t i n f o r m a t i o ns e n s e db yt h er o b o t , a n dt h ep a r t i c l es v c a l n la l g o r i t h mi sa p p l i e di ne a c h r e c e d i n gw i n d o wt oo p t i m i z et h ep r e d i c t e dr o b o tp a t h a ne v a l u a t i o nf u n c t i o ns u i t a b l e f o ru n c e r t a i ne n v i r o n m e n ti sp r o p o s e dt oa v o i dd y n a m i co b s t a c l e si nt i m e s i m u l a t i o n r e s u l t si n d i c a t et h a tt h ep r o p o s e dm e t h o dh a sm a n ya d v a n t a g e si n c l u d i n gs i m p l e r e a l i z a t i o n , g l o b a lo p t i m i z a t i o n , r a p i dc o n v e r g e n c ea n dg o o dr o b u s t n e s s ，m e e t i n g r e a l - t i m er e q u i r e m e n t so fr o b o tp a t hp l a n n i n gi nc o m p l e xu n c e r t a i ne n v i r o n m e n t s w i m d y n a m i co b s t a c l e s 3 t h ep a t hp l a n n i n go fm u l t i - r o b o t sc o o p e r a t i o ni ss t u d i e d , a sr o b o tr e s e a r c h g o e so n , t h em u l t i - r o b o t ss y s t e ma l r e a d yc a t c h e sm o r ea n dm o r em a n yp e o p l e s a t t e n t i o n , t h ec o - e v o l u t i o na l g o r i t h mi nt h ep a t hp l a n n i n go fm u l t i - r o b o t si ss t u d i e d ， t h ec o m p e t i t i v ec o e v o l u t i o na l g o r i t h mf o rt h ep a t hp l a n n i n go f m u l t i - r o b o t si ss t u d i e d i n t h i s p a p e r 4 a ne x a m p l eo fl i f t i n gt h ew o o db yt w or o b o t si ss t u d i e da sam u l t i - r o b o t s c o o p e r a t i v em o d e l w cs o l v et h i sp r o b l e mu n d e rt h eu n c e r t a i ne n v i r o n m e n tu s i n gt h e a l g o r i t h mo f t h i sp a p e r f i n a l l y , t h ew o r ko ft h i s d i s s e r t a t i o ni ss u m m a r i z e da n dt h ep r o s p e c t i v eo f 1 1 1 浙江大学硕士学位论文 f u r t h g l r e s e a r c ho nt h ep a t hp l a n n i n go f m o b i l er o b o ti sd i s c u s s e d k e y w o r d s ：m o b i l er o b o t ；p a t hp l a n n i n g ；o b s t a c l e ；p a r t i c l es w a t h lo p t i m i z a t i o n ； g e n e t i ca l g o r i t h m ；c o e v o l u t i o na l g o r i t h m 浙江大学硕士学位论文 致谢 值此论文完成之际，我衷心地感谢我的导师李艳君老师。李老师严谨的治 学态度和敬业精神一直督促着我，指导我如何进行学术研究。李老师认真的生活 和工作态度也给我留下了深刻的印象。她既是良师，也是益友，不仅在学业上指 导我，在生活和其他方面也给予我关心。 感谢吴铁军老师的关心和指导。吴老师治学态度严谨，对工作一丝不苟， 亲力亲为；学识渊博，思维敏捷，分析问题一针见血、眼光独到且富于远见；讲 解问题旁征博引，深入浅出，语言幽默。吴老师的学识和人品，让我深深地钦佩 和敬仰，也是我以后的学习和工作道路上的榜样。吴老师在我论文的选题和完成 中给予了我极大的帮助。谆谆教导，铭记在心。 感谢刘山老师在我学习和工作中给予我的帮助和启迪。 感谢武晓莉师姐在学习和生活中给予我的帮助和关心。感谢孙丽丽、常爱 英、崔臣刚、杜方、李宗涛、宣琦、刘庆平等博士研究生，郑俊华、林坚、马俊、 李造、黄健生、帅鑫、于海生等硕士研究生，感谢我的室友，他们在学习和生活 中给予了我真诚的帮助。 感谢所有关心帮助过我的老师、同学和朋友们。 感谢我的父亲、母亲的养育和谆谆教诲，感谢我所有的亲人，他们一直以 来关爱和支持着我，是他们给了我前进的动力。谨以此文献给他们。 蔡晓慧 2 0 0 7 年5 月于求是园 v 浙江大学硕士学位论文 第一章绪论 摘要：路径规划技术是机器人研究领域中的一个重要分支，是机器人导航中最重要的任务之 一。本章重点介绍了机器人路径规划的研究背景和意义，并从全局路径规划和局部路径规划 两个方面介绍了国内外的机器人路径规划的主要研究方法，本章还重点介绍了多机器人路径 规划的方法，最后介绍了本文的研究内容以及创新点。 关键词：机器人；路径规划；障碍物 1 1 引言 自2 0 世纪4 0 年代后期，美国橡树岭和阿尔贡国家实验室研制出世界上第一 台“主从型”机械手至今，机器人的研制和应用在欧美和日本等国家中以惊人的 速度发展起来，相应地，机器人的路径规划及相关算法的研究领域也因此而快速 兴起。机器人是多学科交叉的产物，集成了运动学与动力学、机械设计与制造、 计算机硬件与软件、控制与传感器、模式识别与人工智能等学科领域的先进理论 与技术。同时，它又是一类典型的自动化机器，是专用自动机器、数控机器的延 伸与发展。当前，社会需求和技术进步都对机器人向智能化发展提出了新的要求。 随着工业要求的日益增长，越来越多的自动制造系统运用了机械手和传感反馈装 置，更重要的是，随着制造自动化的飞速发展，未来将需要大量更自主、更智能 的机器人。自主的智能机器人将拥有感知、规划和控制等高级能力，使它们能够 收集周围环境的信息，构造一个能以符号表达的环境模型，并通过应用程序，在 高水平层次上规划和实现布置给它们的任务。因此目前机器人学的研究旨在使得 一个自主的智能机器人系统能够更好地具备这些能力。在这些能力中，规划指的 是，利用一个环境模型来自动地实现机器人的运动。一般来说，在一个非常高水 平的层次上，使用者指定一个具体工作任务，然后让机器人系统通过程序去自动 地实现它。比如装配某种产品，使用者指定一系列装配工序，然后让机器人系统 根据基本的要求来规划无碰撞运动，这些动作包括抓取该产品的零部件，绕开工 作空间中的障碍，传送到它们各自相应的装配位置进行装配。在过去的2 0 多年里， 机器人运动的自动规划技术已经有了很大的发展。这个领域涉及到许多重要的数 第一章绪论 学内容，如经典几何学、拓扑学、代数几何学、代数学和组合学等，这些数学工 具都已经应用到相关的研究中。 1 2 机器人路径规划的问题描述 路径规划是自主式移动机器人导航的基本环节之一。它是按照某一性能指 标搜索一条从起始状态到目标状态的最优或近似最优的无碰路径。路径规划技术 是机器人研究领域中的一个重要分支，是机器人导航中最重要的任务之一。蒋新 松为路径规划做出了这样的定义：路径规划是自治式移动机器人的一个重要组成 部分，它的任务就是在具有障碍物的环境内按照一定的评价标准，寻找一条从起 始状态( 包括位置和姿态) 到达目标状态( 包括位置和姿态) 的无碰路径嘲。障碍物 在环境中的不同分布情况当然直接影响到规划的路径，而目标位置的确定则是由 更高一级的任务分解模块提供的。路径规划问题是机器人学中很重要的一个方 面，大多数国内外文献将此问题称为p a t hp l a n n i n g , f m d - p m hp r o b l e m , c o l l i s i o n - f r e eo b s t a c l ea v o i d a n c e m o t i o np l a n n i n g , c t c 路径规划的研究对象可 分为关节式机械手和移动式机器人。一般来说，前者具有更多的自由度，而后 者的作业范围则更大一些。就最简单的形式，路径规划问题可以按如下定义：设 b 为一机器人系统，这一系统共具有k 个自由度，并假设b 在一个二维或三维空 间矿中，在一组其几何性质已为该机器人系统所知的障碍物中，可以无碰撞运动。 这样，对于b 的路径规划问题即为：在空间y 中，给定口的一个初始位姿z l 和 一个目标位姿乙，以及一组障碍物，寻找一条从z l 到z 2 的连续的避碰最优路径， 如果该路径存在，那么规划出这样一条运动路径。移动机器人路径规划主要解决 三个问题：( 1 ) 使机器人能从初始点运动到目标点：( 2 ) 用一定的算法使机器人能绕 开障碍物并且经过某些必须经过的点：( 3 ) 在完成以上任务的前提下尽量优化机 器人运行轨迹。 根据工作环境路径规划模型可分为两种：基于模型的全局路径规划，作业 环境的全部信息已知，又称静态或离线路径规划；基于传感器的局部路径规划， 作业环境信息全部未知或部分未知，又称动态或在线路径规划。局部路径规划和 全局路径规划并没有本质区别，前者只是把全局路径规划的环境考虑得更复杂一 2 浙江大学硕士学位论文 些即环境是动态的，很多适用于全局路径规划的方法经过改进都可以用于局部路 径规划而适用于局部路径规划的方法都可以适用于全局路径规划。 1 3 机器人路径规划研究方法 1 3 1 全局路径规划方法 在环境信息全部已知的情况下，机器人的路径规划完全离线( o f - l i n e ) 进行， 即通过一定算法，根据环境状况为机器人计算出一条可行路径。即全局路径规划 方法，这种方法依据已获取的全局环境信息，给机器人规划出一条从起点至终点 的运动路径。规划路径的精确程度取决于获取环境信息的准确程度。全局路径规 划规划方法通常可以寻找最优解，但需要预先知道准确的全局环境信息。通常该 方法计算量大，实时性差，不能较好地适应动态非确定环境。基于环境建模的全 局路径规划的方法主要有：自由空间法1 、构型空间法0 1 和栅格法随”等。 全局规划方法主要是以基于c 空间的自由空间法等各种几何法以及拓扑法 为主，它包括环境建模和路径搜索两个子问题。最初开始研究路径规划的问题， 主要采用基于直角坐标空间的假设和检验方法，它是f h p i e p e r 于1 9 6 8 年提出的， 也是最早的机器人避障方法。此法由三个步骤组成：第一，在初始点和目标点之 间先假设一条路径；第二，为了避免可能的碰撞，检验路径上一组选定的点；第 三，如果发现碰撞，则通过检查导致碰撞的障碍物来修改这条路径。对于修改 后的运动再重复上述过程，直到完成无碰路径规划。这种早期的全局规划方法比 较简单，但实时性差，无法按指标优化路径。2 0 世纪8 0 年代初，来自麻省理工学 院人工智能实验室的l o z a n o p e r e z 提出了基于c 空间的自由空间法，并得到国内 外很多学者的青睐，与之相关的各种几何法和拓扑法也应运而生。 自由空间法 自由空间法阻9 1 采用预先定义的如广义锥形和凸多边形等基本形状构造自由 空间，并将自由空间表示为连通图，然后通过搜索连通图来进行路径规划，此方 法比较灵活，即使起始点和目标点改变，也不必重构连通图，但是算法的复杂程 度与障碍物的多少成正比，且不能保证任何情况下都能获得最短路径。因而该方 法仅适用于路径精度要求不高，机器人速度不快的场合。自由空间法用于机器人 第一章绪论 路径规划可以分为两个步骤： ( 1 ) 寻空间问题。在指定的环境中，确定机器人的安全位置，使它不与已有 的其他物体相碰撞。将机器人简化为一个点，同时相应地“膨胀”环境中的障碍 物体，从而形成另外二个空间障碍区。这样，通过构造一个虚拟数据结构，将运 动物体和障碍物的几何约束关系转化到另外个虚拟数据结构空间，从而简化问 题的求解。 ( 2 ) 寻路径问题。在指定的环境中，确定机器人从初始位置移动到目标位置 的安全路径，使其在移动过程中不与任何障碍物发生碰撞。经过前面的空间变化， 将问题进一步形式化为“可见”图的搜索问题。搜索从起始位置到目标位置的最 短路径就可以得到机器人的最短安全路径，进而确定具体的系统解决方案。 构型空问法 构型空间法脚是目前研究移动机器人路径规划的一个基本工具，其基本思想 是用构型空间中的一个点来表征移动机器人的位置与方向。 如图1 1 所示，机器人的起点为s ，目标点为g ，s 、g 之间存在一些障碍物 q 、d 2 、0 3 等( 把障碍物都看作为圆) 。规划任务为搜索一条由s 点到g 点的路 径长度较短的无碰路径。构型空间法的主体思想为：在已知环境下，将s 、g 、 o i 、d 2 、0 3 每两点之间相互连线，这些连线之间的交点以及和障碍物边缘的交 点分别称为正、乃乃、z ，这些交点和s 、g 两点构成了一个交织网( 图中黑 实线部分) ，再基于蚁群优化算法在这些线路上行走和避障，经过一定时间的行 走后，一条较优路径基本形成。其路程函数可表示为： ，= 她 ( 1 1 ) j - t 其中： 她：j ( 札一一再) 2 + ( - 一咒) 2 旭睨或件l 砚 ( 1 2 ) 。i 触， f ，i + i e 睨 ( 1 1 ) 和( 1 2 ) 中，a 表示为每一步的路程，m 是在行进中需要的几个关节点。r ， 为第，个障碍物的半径，o r ，表示在遇到障碍物时沿边缘走需要的路程， ( 工。一) 2 + ( y 。一y 。) 2 为在走直线时的距离，睨为第l 个障碍物上的点集 4 浙江大学硕士学位论文 图1 1 构型空间法示意图 为了简化问题，通常将机器人缩小为一点，将其周围的障碍物按比例相应地 进行拓展，使机器人在障碍物空间中能够任意移动而不与障碍物及其边界发生碰 撞。目前研究比较成熟的有可视图法“”( v - - g r a p h ) 和优化算法( 如d i j k s 舰法“”、 a 搜索算法“”等) 。 最常用的方法是可视图法，可视图法通过起始点和目标点及障碍物的顶点 在内的一系列点来构造可视图。即在一个无向图中，将移动机器人的起始点与终 止点以及移动机器人运动环境中各障碍物的顶点表征为点的形式，连接这些点使 某点与其周围的某可视点相连，即要求机器人和障碍物各项点之间、目标点和障 碍物各顶点以及各障碍物顶点与顶点之间的连线均不能穿越障碍物，也即直线是 可视的。从而移动机器人的有效路径就是这样的一些点之间与障碍物不相交的相 互连接的线段。搜索最优路径的问题就转化为经过这些可视直线从起始点到目标 点的最短距离问题。可视图法将机器人，目标点和多边形障碍物的各顶点进行组 合连接，连接的直线视为弧，使用这种方法时，缺乏灵活性，一般需要机器人停止 在障碍前搜集传感器数据，并且它受传感器精度影响较大。 优化算法( o p t i m i z a t i o na l g o r i t h m ) 优化算法可以删除一些不必要的连线以简 化可视图，从而缩短搜索时间，求得最短路径。但是，优化算法缺乏灵活性，一 第一章绪论 旦起点和目标点改变，就必须重构可视图，并且搜索效率也较低。 栅格法 栅格法1 1 3 】是由w e h o w d e n 在1 9 6 8 年提出的。他在进行路径规划时采用 了栅格( g r i d ) 表示地图。在处理障碍物的边界时，避免了复杂的计算。栅格法将 机器人的工作环境分解成一系列具有二值信息的网格单元，并假设工作空间中障 碍物的位置和大小已知且在机器人运动过程中不会发生变化。用尺寸相同的栅格 对机器人的二维工作空间进行规划，栅格大小以机器人自身的尺寸为准。若某一 栅格范围内不含任何障碍物，则称此栅格为自由栅格：反之，称为障碍栅格。这 样，自由空间和障碍物均可表示为栅格块的集成。栅格的表识方法有两种：直角 坐标法和序号法。 栅格法的模型一般按照如下方法表示：首先按照机器人及其有限的活动场 地大小进行栅格的定义和场地的栅格划分。为便于讨论，假设机器人的有限活动 场地为矩形，机器人在场地上占据的空间也为小矩形。将矩形场地平均划分为多 个小矩形栅格，以保证机器人可以在其中自由移动。对栅格划分好的场地进行编 号，编号方法可以采用序号法等。于是，用栅格法便可以完全表示的机器人活动 场地。针对每个栅格位置的不同，将栅格分为两大类：边界栅格、中间栅格。对 于中间栅格，假设其邻接周围没有障碍物，下步可以向邻接的8 个方位搜索。8 个方位分别为：右下、右、右上、上、左上、左、左下、下。按照栅格编号规律， 容易预知这8 个方位的序号及其与当前位置搬格序号的差值。对于边界栅格，下 一步搜索的方位表中要去掉不可达栅格序号。 栅格法以栅格为单位记录环境信息，栅格大小对环境信息存储量的大小和 规划时间的长短有着重要影响，栅格划分大了，环境信息存储量小，规划时间短， 但分辨率就低；反之，虽然分辨率高了，但规划时间长。可以看出，栅格粒度越 小，障碍物的示会越精确，但同时会占用大量的存储空间，算法的搜索范围将按 指数增加栅格的粒度太大，规划的路径会很不精确。所以栅格粒度大小的确定， 是栅格法中的主要问题。 1 3 。2 局部路径规划方法 6 当机器人对环境信息部分了解或全部未知时，机器人需要通过传感器对环 浙江大学硕士学位论文 境进行探索，并通过对传感器反馈信息的分析进行实时路径规划，即通常所说的 在线( o n 1 i n e ) 规划，未知环境下的机器人路径规划问题包含了机器探索、机器发 现、机器学习的智能行为过程，在硬件设备( 包括移动机器人平台、传感器设备、 定位系统等) 充分保证的情况下，机器人被赋予在没有预先环境信息的状况下从 环境中给定的出发点出发，最终到达目标点的任务。在这一任务中，机器人的探 索、发现是由传感器设备完成的，机器人对环境信息的学习与掌握是依靠指导其 行为的算法过程实现的。在线规划也即局部路径规划，局部规划方法侧重考虑机 器人探知的当前局部环境信息，这使机器人具有较好的避碰能力。现有的不少移 动机器人路径规划方法都采用局部方法，其规划仅依靠传感系统实时感知的信 息。与全局规划方法相比，局部规划更具实时性和实用性；对动态环境具有较强 适应能力；其缺点是由于仅依靠局部信息，有时会产生局部极值点或振荡，无法 保证机器人能顺利地到达目标点。这类方法包括：人工势场“伽( a r t i f i c i a l p o t e n t i a lf i e l d ) 、遗传算法删( g e n e t i ca l g o r i t h m ) 、模糊逻辑算法瑚( f u z z y l o g i ca l g o r i t h m ) 、神经网络方法( a r t i f i c i a ln e u r a ln e t w o r k ) 、蚁群算法啪 ( a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ) 、粒子群算法( p a r t i c l es w a mo p t i m i z a t i o n ) 等。 人工势场法 人工势场法f h k h a t i b 于1 9 8 6 年提出，基本思想是构造目标位姿引力场和障碍 物周围斥力场共同作用的人工势场，搜索势函数的下降方向来寻找无碰撞路径。 图1 2 为建立的人工势场，0 和g 分别表示障碍物和目标，势场函数、吸引力函数、 排斥力函数、势场角度函数分别表示如下： 妒= 1 d( 1 3 ) 耻毒 o 4 驴亩 o j ) 力= 么( 巴+ 只) ( 1 6 ) 7 第一章绪论 图1 2 人工势场示意图 人工势场法是移动机器人局部在线避碰最常用的方法之一，其原理是：移 动机器人在一个虚拟的力场中运动，障碍物被斥力势场( c ，) 包围，其产生的排斥 力( 只) 随机器人与障碍物距离的减少两迅速增大，方向背离障碍物i 目标点被引 力势场( ) 包围，其产生的吸引力( 兄) 随机器人与目标位姿的接近而减小，方 向指向目标点；然后按各个障碍物和目标位姿产生的人工势能的总和，取势函数 梯度下降的方向( 即沿排斥力矢量和吸引力矢量和的方向) 来实现无碰路径规划。 在该势场中的移动机器人受到其目标位姿引力场和障碍物周围斥力场的共同作 用，朝目标前进。由于机器人是受引力和斥力的合力的作用，合力为零时，机器 人将停止前进，即陷入局部极小点，机器入不能到达目标位置。在k h a t i b 研究机 器人手臂在笛卡儿空间中如何直接由任务相关的参数、运动、受力来控制其运动 的问题中，k r o g l l 引入了一个重要的概念：广义势场( g e n e r a l i z e d f i e l d ) ，即既考 虑位置，又考虑速度。常用的有以下几种势场：牛顿型势场、圆形对称势场、超 四次方势场、调和势场及虚拟力场。在人工势场中，障碍物被看作斥力场，目标 被看作引力场，所以障碍物对机器人产生斥力，目标对机器人产生引力，通过求 引力和斥力的合力来控制机器人的运动。 人工势场法结构简单，计算量小，实时性好。因而广泛应用于实时避障和 平滑轨迹控制方面。但是在局部最优解的问题上容易产生死锁现象( d e a dl 0 c k ) 现象，从而可能导致机器人陷入局部最优点。 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s 简称g a ) 是由美国m i c h i g a n 大学的j o h n 浙江大学硕士学位论文 h o l l a n d 教授于2 0 世纪6 0 年代末创建的。它来源于达尔文的进化论和孟德尔、摩 根的遗传学理论，通过模拟生物进化的机制来构造人工系统。遗传算法的研究有 着相当悠久的历史，至今已经形成了非常成熟的理论。遗传算法应用到了很多领 域。从1 9 8 5 年在美国卡耐基梅隆大学召开的第一届国际遗传算法会议到1 9 9 7 年5 月i e e e 的t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n 仓q 刊，遗传算法作为具有系统 优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法是一种自 适应全局优化概率搜索算法，它不同于枚举法、启发式算法、搜索算法等传统的 优化方法，主要有以下特点： ( 1 ) 自组织、自适应和学习性( 智能性) 。遗传算法消除了算法设计中的一个 最大障碍，即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法 应采取的措施，因此，它可用来解决复杂的非结构化问题，具有很强的鲁棒性。 ( 2 ) 直接处理的对象是参数的编码集而不是问题参数本身。 ( 3 ) 搜索过程中使用的是基于目标函数值的评价信息，搜索过程既不受优化 函数连续性的约束，也没有优化函数必须可导的要求。 ( 4 ) 具有显著的隐并行性。遗传算法按并行方式搜索一个种群数目的点，而 不是单点。它的并行性表现在两个方面：一是遗传算法是内在并行的、二是遗传 算法的内含并行性。 ( 5 ) 形式上简单明了。 遗传算法是一种多点搜索算法，也是目前机器人路径规划研究中应用较多 的一种方法。由于遗传算法的整体搜索策略和优化计算不依赖于梯度信息，且作 为并行算法其隐并行性适用于全局搜索，所以解决了其它一些算法无法解决的问 题。国内外很多专家、学者等在这方面作了大量研究，并取得了很多成果。孙树 栋等实现了离散空间下移动机器人路径规划新方法，该方法采用栅格序号作为个 体的编码形式，与传统的二进制编码方法相比，具有编码长度短、易于进行遗传 操作等优点。在该方法中，提出了间断无障碍路径概念，引入插入和删除算子， 方便了遗传算子的实现，保证了路径的连续和可行性。但该路径规划是基于确定 环境模型的，所以有其局限性。在离散空间下路径规划中，k a z u os u g i h a r aa n d j o l l l ls m i t h 进行了更深入的研究，他们对栅格序号采用二进制编码，随机产生障 碍物位置和数目，在搜索到最优路径后再在环境空间中随机插入障碍物，以此来 9 第一章绪论 模拟环境变化，仿真结果验证了其有效性和可行性：但是，规划空间的栅格法建 模有其自身的缺陷，所以还有待改进。周明等提出一种连续空间下基于遗传算法 的移动机器人路径规划方法，该方法在规划空间时有别于离散空间下的栅格法， 而是在利用链接图建模的基础上，先通过图论中成熟的算法粗略搜索出可行路 径，再用遗传算法调整路径点得到最优路径。这种编码方法效率较高，不会产生 无效路径，使用基本遗传算法就可以完成路径规划问题。但对于复杂环境链接图 的建立有一定困难。此外，遗传算法运算速度低，进化众多的规划要占据较大存 储空间和运算时间。 模糊逻辑算法 模糊逻辑算法是基于实时传感信息的一种在线规划方法。模糊有向图是引入 节点发生故障概率的一种符号有向图。节点分别表示系统的各个部件，分支及其 方向表示部件因果联系及作用方向。节点可以用正号、零和负号来分别表示相对 正常技术状况的正偏移、无偏移和负偏移；分支可以用正号、零和负号来表示作 用方向。h a r t m u s ts u r m a t m 等提出一种未知环境下的高级机器人模糊导航方法， 由八个不同的超声传感器来提供环境信息，然后利用基于模糊控制的导航器计算 这些信息，规划机器人路径；李彩虹等提出了一种在未知环境下移动机器人的模 糊控制算法；庄晓东等提出一种动态环境中基于模糊概念的机器人路径搜索算 法。 神经网络方法 神经网络是- - n 新兴交叉学科，始于2 0 世纪4 0 年代，是人类智能研究的重 要组成部分，已成为脑科学、神经科学、认知科学、心理学、计算机科学、数学 和物理学等共同关注的焦点。它模仿人脑神经网络的结构和某些工作机制建立一 种计算模型。神经网络的研究已经进入更加成熟的发展阶段，其中一个很重要的 标志是越来越多的心理学家、神经生理学家、医学工作者、数学家以及计算机科 学联合起来，开展跨学科的研究，以探讨神经网络的机理、功能以及相应的模型， 并且尽量与应用结合。 神经网络作为一个高度并行的分布式系统，为解决机器人系统实时性要求很 高的问题提供了可能性，并应用于智能自主移动机器人导航与路径规划等方面。 在本研究中，解决路径规划问题的思路是：利用神经网络来描述环境约束并计算 1 0 浙江大学硕士学位论文 碰撞能量函数。将迭代路径点集的碰撞能量函数与距离函数的和作为优化目标函 数，通过求优化目标函数的极值，确定点集的运动方程，最终使迭代路径点集趋 向于最优规划路径。禹建丽等提出了一种基于神经网络的机器人路径规划算法。 禹建丽又引进了线性再励的自适应变步长算法，提高了机器人路径规划速度，研 究了障碍物形状和位置已知情况下的机器人路径规划算法，其能量函数的定义利 用了神经网络结构，规划出的路径达到了折线形的最短无碰路径，该方法计算简 单、收敛速度快。刘成良等提出了基于神经网络的机器人无碰撞路径规划方法， 给出了无碰撞轨迹规划的人工神经网络算法，证明了其可行性，为神经网络真正 用于机器人控制提供了基础。陈宗海提出了一种在不确定环境中移动机器人的路 径规划方法，采用基于案例的学习算法，进行案例的匹配、学习和扩充，使用 p 灯- 2 2 神经网络实现，提高了路径规划的效率，以满足移动机器人在线路径规 划的实时性要求。樊长虹等针对移动机器人的未知环境下采用了一种局部连接 h o p f i e l d 神经网络规划器。对任意形状环境，a n n 中兼顾处理了“过近”和“过 远”来形成安全路径，而无需学习过程。为在单处理器上进行有效的在线路径规 划，提出用基于距离变换的串行模拟，加速了数值势场的传播，该方法具有较高 的实时性和环境适应性。 蚁群算法 a c o 算法是c o l o m i 和d o r i g o 等在2 0 世纪9 0 年代初提出的一种新型分布式智 能模拟仿生类算法，它模拟和借鉴了现实世界中蚂蚁种群的行为特征。虽然它仅 提出1 0 多年，但已逐渐引起广大学者的注意，并得到广泛的应用。生物学家发现 自然界中的蚂蚁群在觅食过程中具有一些显著的特征，例如：蚂蚁在移动过程中 会释放一种称为信息素的物质：释放的信息素会随着时间的推移而逐步减少；蚂 蚁能在一个特定的范围内觉察出是否有同类的信息素轨迹存在；蚂蚁会沿着信息 素轨迹多的路径移动等。正是基于这些基本特征，蚂蚁能找到一条从蚁巢到食物 源的最短路径。蚁群算法在机器人路径规划中的应用早已有所研究，但是在国内 还属于比较新的领域。 蚁群算法的优点可以归纳为以下几点： ( 1 ) 并行机制：所有“蚂蚁”独立行动，在并行运行环境( 如网格环境下) 可以同步寻优，加快了寻优速度； 第一章绪论 ( 2 ) 协作机制：随着迭代的进行，单只蚂蚁在寻优过程中可以共享其它蚂蚁 搜索经验，信息素轨迹量大的路径被选中的几率大； ( 3 ) 普适性：蚁群算法是一种通用性强的算法，稍加修改便可用于其它优化 问题。 不可避免地，蚁群算法也有其明显的缺陷，如它的计算量较大，搜索时间 较长，易于陷于局部最优解。 朱庆保，张玉兰提出了基于栅格法的机器人路径规划蚁群算法，该算法用栅 格法对场景进行建模，模拟蚂蚁的觅食行为，由多只蚂蚁协作完成最优路径的搜 索。朱庆保提出了动态复杂环境下的机器人路径规划蚂蚁预测方法该方法模拟蚂 蚁的觅食行为，由多组蚂蚁采用最近邻居搜索策略和趋近导向函数相互协作完成 全局最优路径的搜索。在此基础上用虚拟蚂蚁完成与动态障碍物碰撞的预测，并 用蚁群算法进行避障局部规划。朱庆保还提出了复杂环境下的机器人路径规划蚂 蚁算法，用于复杂的静态环境下的机器人路径规划。可见，动态环境下的机器人 路径规划方法也适合于静态环境。 粒子群算法 k e n n e d y 和e b e r h a r t 等于1 9 9 5 年开发出一种新的演化算法粒子群优化算 法。它的基本思路为：在问题的定义空间内将一定数量的等位微粒作随机分布， 然后根据各微粒在解空间中所处地位的相关信息作为微粒的优劣赋值记录，同时 对各微粒运动的最优历史信息作好记录，在随后的每次计算循环中，当前微粒的 运动模式都由其自身的最优历史记录和群体的最优历史记录决定，直到整个粒子 群体找到问题的最优解或者满足其他相关停止条件。 相比其它进化算法，p s o 保留基于种群的全局搜索策略，避免复杂的个体操 作，采用简单的速度调整模型，仅利用特有的记忆使其可以动态地跟踪当前搜索 状况，具有较强地鲁棒性和快速地寻优速度，且不需要借助问题的特征信息。因 此，p s o 作为一种更高效的并行搜索算法，非常适合于对实时性要求较高的复杂 优化问题进行求解。基于p s o 的高效寻优特性，本文将其应用于动态环境下对实 时性要求较高的机器人路径规划中。 粒子群算法虽然具有收敛速度快，算法简单，容易编程实现等特点，但p s o 算法也有一些严重的缺陷，其一是容易陷于局部极值点，导致得不到全局最优解， 1 2 浙江大学硕士学位论文 到目前为止，p s o 算法还不能从理论上严格证明收敛于任何类型函数的全局极值 点。其二是p s o 算法本身的参数设置，当参数选择不当时，会导致寻优过程中粒 子的多样性迅速消失，造成算法“早熟收敛”。基于p s o 的不足，已经有大量学 者对算法进行了改进研究，s h i & e b e r h a r t 探讨了p s o 算法中参数的设置对算法性 能的影响，提出了递减的惯性权重，本文将采用递减的惯性权重于p s o 在路径规 划中的应用。 目前粒子群算法在机器人路径规划中的应用还处在一个开始的阶段，只有 极少数学者在该方向有所研究，如国内的秦元庆，孙德宝等提出的粒子群算法在 全局路径规划中的应用粒子群算法与链接图方法结合起来求解最优路径【冽，雷开 友，邱玉辉等人将改进的粒子群算法应用到机器人的全局路径规划中【2 9 】，孙波， 陈卫东等人提出多步路径规划方法以及新的环境建模，将粒子群算法应用到机器 人路径规划中【3 0 】。x i n ( ；h e n 和y a n g m i nl i 运用随机p s o 进行机器人的平滑路径规 划【3 1 】，g a n e s hk 和s h e e t a l 将p s o 运用到模糊逻辑控制器中进行机器人的导航1 3 2 ， 总体来说，粒子群算法在机器人路径规划中的应用有待于进一步的研究。 混合方法 混合方法试图结合全局和局部方法的优点。在全局规划的基础上进行局部微 调，相互结合、取长补短。目前，将遗传算法、模糊逻辑以及神经网络等方法相 结合，组成了一些新的机器人路径规划方法，提高了规划的效率。周明等1 3 3 】提出 利用遗传算法和模拟退火算法相结合的方法来解决机器人路径规划问题。这种混 合方法也可以看作是遗传算法的改进，抑制了遗传算法的早熟现象，克服了其局 部寻优能力较差的缺点，有效地提高了路径规划的质量。吴成东等】提出了一种 基于粗糙集和遗传算法混合方法的机器人路径规划方法。引入粗糙集软计算方 法，对遗传算法的种群初始化过程进行了改进，提高了机器人路径规划的速度和 能力。龚进峰等提出一种基于数字势场和遗传算法的机器人路径规划方法。该 方法利用笛卡儿工作空间的几何信息，建立离散化工作空间的距离图和数字势 场，基于启发函数引导机器人在构形空间使用遗传算法搜索，取得了一定的成效。 l h t s o u k a l a s 等【3 6 提出一种用于半自主移动机器人路径规划的模糊神经网络方 法。这种方法采用模糊描述来完成机器人行为编码，同时重复使用神经网络自适 应技术，通过机器人的传感器提供局部环境输入，内部模糊神经网络进行环境预 第一章绪论 测，从而可以实现未知环境下机器人路径规划。 1 4 多机器人协作路径规划方法 8 0 年代末以来，协作机器入学已引起越来越多学者的关注，逐渐形成机器 人研究领域的新热点。每年在