（计算机应用技术专业论文）基于正反馈遗传算法的新型机器人路径规划方法.pdf

南京师范大学硕士学位论文 摘要 摘要 根据对环境信息掌握程度的不同，移动机器人路径规划可分为环境信息完全 已知的离线全局路径规划和环境信息完全未知或部分未知的在线局部路径规划。 遗传算法由于具有并行性及全局搜索能力强等特点，被引入到路径规划之中，但 这些应用多采用栅格法及可视图法对环境建模，前者栅格大小难以控制，后者建 模过程复杂，且对障碍物的依赖性较强，加之遗传算法的收敛速度较慢，致使路 径规划的效率并不高为此，根据遗传算法的特点，研究了一种新型的建模方法， 该方法依据机器人出发点、目标点位置建立起新的坐标空间，染色体各基因位于 机器人出发点及目标点连线的各等分点的垂线上，具有过程简单、容易实现的特 点为解决算法收敛速度慢的问题，借鉴蚁群算法的思想，将正反馈机制引入到 遗传算法中，用一个二维矩阵记录整个环境的累积值信息，使位于累积值高的区 域的基因以较低的概率参加交叉及变异运算，以使个体中的优良基因段以较高的 概率遗传到下一代仿真实验显示了此算法能够提高全局路径规划的收敛速度， 且获得较优化的解。为了解决这一新建模方法使染色体各基因只能位于起始点至 目标点连线各等分点的垂线上，从而可能影响某些更优路径的获得的问题，在正 反馈遗传算法中，引入新型的遗传算子添加结点算子及删除结点算子，使染 色体的各基因不再仅位于起始点至目标点连线各等分点的垂线上。之后，借鉴预 测控制的基本原理，结合滚动窗口法，将改进型币反馈遗传算法应用于局部路径 规划当中，实现未知环境下的路径规划。最后的仿真实验显示无论在静态未知环 境中还是在动态未知环境中，改进型正反馈遗传算法均能获得较优化的解。 关键字：机器人路径规划；遗传算法：环境建模：正反馈；新型遗传算子； 滚动窗口法 n l 南京师范大学硕士学位论文a b s t r a c t a b s t r a c t m o b i l er o b o tp a t hp l a n n i n gi sc o m p r i s e do fo n - l i n eg l o b a lp a t hp l a n n i n g ，w h i c h b a s e do nm o d e lt h a tt h ee n v i r o n m e n to ft h er o b o ti sc e r t a i n , a n d0 i f - l i n el o e a lp a t h p l a n n i n g ，w h i c hb a s e do ns e n s o rt h a tt h ee n v i r o n m e n to ft h er o b o ti s u n c e r t a i n b e c a u s eo fc h a r a c t e r i s t i c so fp a r a l l e l i s ma n db ep r o f i c i e n ta tg l o b a ls e a r c h g e n e t i c a l g o r i t h m ( g a ) i sa p p l i e dt or o b o tp a t hp l a n n i n g b u tt h em o d e l i n gm e t h o di nt h e s e a p p l i c a t i o n si se i t h e rg r i dm e t h o do rv i s i b i i i t yg r a p h s ，t h ef o r m e rh a sd i f f i c u l t yi n d e c i d i n gt h eg r i d ss i g n ，也el a t t e rh a sg r e a td e p e n d e n c eo no b s t a c l e s i na d d i t i o n ，t h e g a c o n v e r g e st ot h eg l o b a lb e s ts l o w l y , s ot h ee x i s t i n gp a t hp l a n n i n gm e t h o db a s e d o ng ai si n e f l i e i e n t s o ，an o v e l t ym o d e l i n gm e t h o di sp r e s e n t e df o rg ai nr o b o tp a t h p l a n n i n g ，w h i c hi si m p l e m e n t e do n l yd e p e n d e n to nt h ep o s i t i o n so ft h es t a r tn o d ea n d t h eg o a ln o d e o ft h er o b o t ，a v o i d i n gt h ed i s a d v a n t a g e so fv i s i b i l i t yg r a p h sm e t h o da n d g r i dm e t h o d g e n e si nt h i sm e t h o dl i ei nt h ev e r t i c a ll i n e so fn o d e st h a te q u a l l yd i v i d e t h el i n ef r o mt h es t a r tn o d eo ft h er o b o tt ot h eg o a ln o d e t os p e e du pt h ec o n v e r g e n c e o fg a ，t h ep o s i t i v ef e e d b a c ki nt h ea n tc o l o n yo p t i m i z a t i o n ( a c o ) i si n t r o d u c c dt o b a s i cg a t br e s e r v eq u a l i t ys e q u e n c e so fc h r o m o s o m ei n t on e x tg e n e r a t i o n am a t r i x i su s e df o rr e g i s t e r i n gt h ev a l u eo fw o r k i n gs p a c e ag e n ew i t hh i g h e rv a l u e p a r t i c i p a t e si nc r o s s o v e ro p e r a t i o na n dm u t a t i o no p e r a t i o nw i t hl o w e rp r o b a b i l i t y t h e e x p e r i m e n tr e s u l t sd e m o n s t r a t ep o s i t i v ef e e d b a c kg aa l g o r i t h mc a ni m m e d i a t e l yf i n d a p a t he v e ni nc o m p l e xe n v i r o n m e n t s t og e tb e t t e rp a t h ，a d d i n gg e n e so p e r a t i o na n d d e l e t i n gg e n e so p e r a t i o na 他i n t r o d u c e dt op o s i t i v ef e e d b a c kg a w h i c hc a ng e n e r a t e g e n e sn o to n l yi nt h ev e r t i c a ll i n e s a s s o c i a t e dw i t hr o l l i n gw i n d o wp l a n n i n g , t h i s a l g o r i t h mi sa p p l i e dt ol o c a lp a t hp l a n n i n g ，n 坨s i m u l a t i o nr e s u l ts h o w st h a tt h i s a l g o r i t h mi se i f e c t i v e l yn o to n l yi nu n c e r t a i ne n v i r o n m e n tw i t h o u tm o b i l eo b s t a c l e s b u ta l s oi nu n c e r t a i ne m h r o n m e n tw i t hm o b i l eo b s t a c l e s k e y w o r d s ：r o b o tp a t hp l a n n i n g ；g e n e t i ca l g o r i t h m ( g a ) ；e n v i r o n m e n tm o d e l i n g ； p o s i t i v ef e e d b a c k ；n e wg ao p e r a t o r , r o l l i n gw i n d o wp l a n n i n g 学位论文独创性声明 本人郑重声明： l 、坚持以搿求实、创新糟的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研 究成果 3 、本论文中除引文外，所有实验、数据和有关材料均是真实 的 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机 构已经发表或撰写过的研究成果 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表 示了谢意 作者签名： 日 期：矛4 归 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规 定，学校有权保留学位论文并向国家主管部门或其指定机构送交论文 的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据 库进行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论 文在解密后适用本规定 作者签名： 日期；弘珥卫 南京师范大学硕士学位论文第一章绪论 第_ 章绪论 机器人路径规划是自主式机器人研究中的一项关键技术，截至目前，无论是 全局路径规划还是局部路径规划均取得长足发展，但由于规划问题的复杂性以及 规划方法本身的缺陷，机器人路径规划，特别是环境中存在未知动静态障碍物的 路径规划仍将是今后一段时期的重要研究对象 遗传算法是一种仿生智能搜索算法，由于具有较强的全局搜索能力等特点， 在路径规划领域得到了深入的应用n 州，但遗传算法存在一个收敛速度慢的固有 缺陷，加快算法的收敛速度，提高路径规划的效率一直受到学术界的关注。 1 1 研究背景及意义 机器人是现代科学技术发展的佼佼者，在2 1 世纪将发挥出越来越重要的作 用，使人类的生产活动和家庭生活发生巨大的变化移动机器人的研究始于2 0 世纪6 0 年代末期，7 0 年代末随着计算机技术和传感器技术的发展，国际上的一 批公司开始研究移动机器人平台近年来，自主式移动机器人( a u t o n o m o u s m o b i l er o b 0 1 ) 技术在工业、农业、医学及社会服务领域显示了越来越广泛的 应用前景，因而成为国际机器人学术研究的热点问题斓。 机器人学的终极目标之一是创造自主机器人，对一个自主机器人来说，在真 实世界里运动并完成任务，规划自己的移动路径是最起码的功能，这也是机器人 研究中的一项关键技术路径规划。移动机器人路径规划就是给定机器人及其 工作环境信息，按照某种优化目标，在起始点和目标点之间规划出一条与环境障 碍物无碰的最优或次优路径，通常为路径最短嘲。根据对环境信息掌握程度及障 碍物的不同，移动机器人路径规划可分为以下几类：已知环境下仅有静态障碍物 时的路径规划；未知环境下仅有静态障碍物时的路径规划；已知环境下含有动态 障碍物时的路径规划；未知环境下含有动态障碍物时的路径规划。 根据对环境信息掌握程度的不同，移动机器人路径规划可分为以下两种类 型：基于环境信息完全已知的离线全局路径规划简称全局路径规划；基于信息 实时探测的在线局部路径规划，简称局部路径规划后者中环境是未知或部分未 知的，即障碍物的尺寸、形状和位置等信息必须通过传感器实时获取口1 。机器人 南京师范大学硕士学位论文第一章绪论 路径规划在理论上包括以下三个子问题： ( 1 ) 环境表示问题：指环境中障碍物的表示和自由空间的表示，合理的环 境表示才能有利于规划中搜索量的减少，有利于时空开销的减少 ( 2 ) 路径搜索问题：在环境模型的基础上，采用某种搜索算法搜索出一条 从起点到目标点的最优路径，并满足一定的效率要求。 ( 3 ) 避碰问题：在环境信息完全未知或部分未知的情况下，机器人在行进 的过程中。当遇到障碍物时如何有效地避免碰撞发生，绕开障碍物继续前进，从 而无碰地到达终点嘲 遗传算法是一种较新型的智能搜索算法，具有并行性、不易陷入局部最优及 全局搜索能力强等特点因此，将该算法用于路径规划具有独特的优势。已有学 者研究了基于遗传算法的路径规划，算法总体上是成功的，但存在收敛速度慢， 容易产生无效路径等闯题。因此，如何提高遗传算法在全局及局部路径规划过程 中的收敛速度是一个仍需要进一步挖掘的问题州本文就是针对这一研究现状， 研究基于正反馈遗传算法的新型机器人路径规划方法，目标就是解决已有成果存 在的缺陷。 1 2 国内外研究现状 1 2 1 基于遗传算法的机器人路径规划 应用遗传算法进行路径规划的第一步是进行环境建模，目前常用的建模方法 有栅格法及可视图法 ( 1 ) 环境建模 栅格法栅格法是目前应用最广泛的环境建模方法之一，由m b m e t e a 首 先提出渊。栅格法将移动机器人的工作环境分解成一系列具有二值信息的栅格 单元，并以栅格为单位记录环境信息。常见的实现方法是将存在障碍物的栅格记 为值“1 ”，无障碍物的栅格记为值。0 打，相连的无障碍物的栅格组成自由区域n u 。 栅格法建模过程简单，且易于计算机处理，但环境被量化为具有一定分辨率 的栅格，所以栅格的大小直接影响环境信息存储量和路径规划时间。而栅格的大 2 南京师耗大学硕士学位论文第一章绪论 小难以控制，栅格划分大了，环境信息存储量小，规划时间短，但分辨率下降， 在密集环境下发现路径的能力减弱；栅格划分小了，环境分辨率高，在密集环境 下发现路径的能力强，但环境信息存储量大，路径规划的时间亦会相应增加n 铂。 可视图法可视图法是一种基于自由空间几何构造的规划方法，此类方法的 基本思想就是构造某种图来描述自由空间，从图上找到满足某一准则的最优路 径此法一般包括两个阶段：首先构造一个描述自由空间的关系图，然后按照一 定的准则( 最短路径、最少时间等) 寻找一条最优路径“羽可视图法构造自由空 间关系图的过程如下： 用直线将机器人运动的起始点、工作空白j 中所有多边形障碍物的顶点( 任意 形状的障碍物用近似多边形代替) 以及目标点连接起来，并保证这些直线段不与 工作空间中的任何障碍物相交，这样形成的一张图就称为可视图n 耵 环境模型建立起来之后，可采用某种图搜索算法寻找从起始点到目标点的最 短路径，路径规划问题就转化为从寻找起始点到目标点经过这些可视直线的最短 距离的问题，运用优化算法，可删除一些不必要的连线以简化可视图，缩短规划 时间n 射但可视图法忽略了机器人的大小，将其视为一点，使得机器人通过障碍 物顶点时离障碍物太近j 甚至接触。另外，可视图法建立起来的环境模型依赖环 境中的障碍物形状，障碍物的改变会造成环境模型的较大变动，且建模过程复杂， 不易将其应用于局部路径规划环境建模当中n 卅 ( 2 ) 遗传算法路径搜索 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a 是以自然遗传和自然选择等生 物进化理论为基础，构造的一种仿生搜索算法。它使用了群体搜索技术，种群代 表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作，从而 产生新一代的种群，并逐步使种群进化到包含最优解或近似最优解的状态。由于 具有并行性及全局搜索能力强等特点n 力，遗传算法被引入到机器人路径规划领域 之中 g e l e g h o n ( 1 9 8 8 年) 首先应用遗传算法来求解平面避障问题，在国内，孙树 栋首先将遗传应用于机器人路径规划领域，解决离散空间下的路径规划问题n 耵， 但其是基于静态模型的，即工作空间中障碍物的位置是己知的且是静态的。此后 3 南京师范大学硕士学位论文第一章绪论 遗传算法在机器人路径规划领域中的研究逐步展开，主要成果集中在提高遗传算 法在静态环境下路径规划的优化性，以及在含有未知动静态障碍物的环境中与其 他方法结合进行实时路径规划与避障方面n 蝴1 。由于受环境建模的影响，如采用 栅格法建模容易产生无效路径，且不易消除，可视图法建模对环境中的障碍物依 赖性较大，不利于局部路径规划，加之遗传算法本身存在收敛速度慢的固有缺陷， 致使遗传算法在路径规划应用中存在着过程复杂，效率不高的问题。 1 2 2 其他路径规划方法 移动机器人路径规划的研究始于2 0 世纪6 0 年代，路径规划方法包括传统 的基于图的搜索方法，如d i j k s t r a 算法、a 算法等，以及包括遗传算法在内的 新型的智能算法，如蚁群算法、神经网络方法等以下从全局路径规划方法及局 部路径规划方法的角度对已有的路径规划方法加以分类概述。 ( 1 ) 全局路径规划方法 全局路径规划是指在环境信息完全已知的情况下所进行的路径规划，规划方 法主要有贪心算法、d ij k s t r a 算法、a + 算法及d 算法等。 贪心算法是最简单的图搜索算法，其是一种只考虑局部代价最小化，忽略了 全局最优的搜索算法，该法不能保证找到最优解。d ij k s t r a 算法是最短路径搜 索算法，该算法能够找到图中一个节点到其他任意节点的最短路径，若以机器人 运动起点为源点，终点为目标点，则可以找到一条从源节点到目标节点的最短路 径，算法的复杂度为o ( n * n ) ，其中n 为图的节点数。譬1 a 算法是应用极广的启发 式搜索算法，应用在栅格结构上性能较优，经过栅格x 的路径代价为 f ( x ) = g ( x ) + h ( x ) ，其中，g ( x ) 为从起点到x 点的实际代价，h ( x ) 为从x 点到目标 点代价的估计值，若h ( x ) 是真实路径代价的下界，a 算法可保证找到一条最优路 径，但a 算法限于在静态图上搜索，d 算法弥补了这一缺点，可以在动态图上搜 索到一条最短路径嘲 4 南京师范大学硕士学位论文 第一章绪论 ( 2 ) 局部路径规划方法 局部路径规划是指在信息完全未知或部分未知的情况下所进行的路径规划， 环境信息需要通过传感器实时获取其与全局路径规划并没有本质区别，能用于 全局路径规划的方法均能用于局部路径规划当中h 1 目前，局部路径规划的常用 方法有：人工势场法、神经网络法、模糊逻辑算法、蚁群算法及遗传算法等。 人工势场法k h a t i b 于1 9 8 6 年首次将人工势场( a r t i f i c i a lp o t e n t i a l f i e l d ，简称a p f ) 应用于机器人路径规划当中踟。其基本思想是：将机器人在未 知环境中的运动视为一种在虚拟的人工受力势场中的运动，即在目标点附近虚拟 一个引力势场，对机器人产生引力，而障碍物附近虚拟一个斥力势场，对机器入 产生斥力，引力和斥力的合力就是机器人运动的虚拟力，这个虚拟力控制机器人 的运动删人工势场法具有结构简单，计算量小，实时性好等优点，但其有一 个固有缺陷是容易陷入局部极小点，后人结合其他方法包括模拟退火法等在一定 程度上解决了这一问题凹侧 人工神经网络法人工神经网络模型( a r t i f i c i a ln e u r a ln e t w o r k s 简称 a n n ) 具有高度的并行性和容易实现非线性映射的能力，可以处理难以用模型或 规则描述的问题，从而被引入到机器人路径规划研究之中其基本过程是：将机 器人的前一位置或者前一位鹭的走向作为输入，所期望的下一次的位置或者下一 次位置的运动方向作为输出，进行训练学习，引导机器人避障行驶，直至到达目 的地洲神经网络系统受学习样本的影响较大，但选择代表性强的样本集是十分 困难的，因而样本的选择与设计是应用人工神经网络法于机器人路径规划领域的 一大难题洲 模糊逻辑算法模糊逻辑算法是基于对驾驶员工作过程的观察研究得出的。 驾驶员的避碰动作并非对环境信息精确计算完成的，而是根据模糊的环境信息， 通过查表得到的，从而完成局部路径规划。其优点是不易产生局部极小问题，对 处理未知环境下的规划问题显示出很大的优越性，对于用通常的定量方法来说是 很复杂的问题或当外界只能提供定性近似的、不确定信息数据时非常有效口。假 设检测的是障碍物与机器人的距离和障碍物的运动信息，输出机器人速度变化d v 和转角变化do ，模糊控制算法控制结构框图如图i - i 所示嘲 5 南京师范大学硕士学位论文 第一章绪论 图i - i 模糊逻辑算法控制图 蚁群算法受自然界中真实蚁群集体觅食行为的启发，d o r i g o 等提出了蚁 群算法( a n tc o l o n yo p t i m i z a t i o n 简称a c o ) 该算法是一种具有高度并行性 且个体间高效通信协作性的仿生算法，这两个特性使蚁群算法成为在机器人路径 规划中应用较多的算法，国内外学者做了大量的研究并取得了丰富成果删 文献 3 5 首先将蚁群算法引入到机器人路径规划研究领域，并尝试在蚁群算 法中通过调整避障系数，得到不同的优化轨迹机器人的工作环境很多是动态不 确定的，对这类环境中的动态障碍物，机器人很难具有先验知识，这样，机器入 只能根据实时探测到的环境信息进行规划，针对这个问题，文献 3 6 ，3 7 提出了 复杂环境下的蚂蚁算法 1 2 3 机器人路径规划难点及发展趋势 ( 1 ) 机器人路径规划难点概述 路径规划分为全局路径规划及局部路径规划两种，学术界已经探究出许多有 效的全局路径规划算法，包括：传统的基于图的路径搜索方法( 可视图、切线图 法等) 、随机树、蚁群算法、神经网络方法等删由于算法本身的局限性及待 解决问题的复杂性，现有方法普遍存在着搜索空间大、效率不高等问题，特别是 已有方法对障碍物模型存在一定的依赖性，对于一些复杂的障碍物，如u 形障碍 物，仍没有有效的解决办法 动静态环境完全未知或部分未知时的路径规划已经证明是一个n p - h a r d 问 题，如何在动静态障碍物未知的环境中搜索一条最优或次优的路径一直是路径规 划的难点之一现有的方法主要有：人工势场法、神经网络、滚动窗口规划方法 以及各类定位导航方法删，但由于算法本身的局限性及未知环境的复杂性，现 有方法普遍暴露出规划过程复杂、路径优化效果差，实时性差等缺陷。 6 南京师范大学硕士学位论文第一章绪论 ( 2 ) 机器人路径规划发展趋势 随着移动机器人应用范围的扩大，对于规划技术的要求也越来越高，单个规 划方法有时不能很好地解决某些规划问题，路径规划新的发展趋向于多种方法之 间的融合嘲： ( a ) 全局路径规划与局部路径规划的结合 全局路径规划建立在环境信息已知的基础之上，适应范围相对有限，局部路 径规划能适用于环境未知的情况，但有时反应速度不够快，如果把两者结合则能 达到更好的规划效果。文献 4 7 1 在应用蚂蚁算法进行局部路径规划时采用双层规 划，首先用最近邻居法搜索到一条全局最优路径，然后应用蚂蚁算法进行局部避 障，获得较好的路径规划效果。 ( b ) 传统规划方法与新型智能方法之间的结合 近年来，包括遗传算法等一些新兴的智能技术逐渐被引入到路径规划中来， 新兴的智能技术具有鲁棒性较强、不易陷入局部最优等优点，但计算效率一般较 差，收敛速度较慢，结合一些传统的路径规划方法，如人工势场法、模拟退火算 法等，就能够扬长避短。文献c 4 8 先用神经网络法对环境进行分类以避免陷入局 部最小，然后使用人工势场法引导机器人前进，该方法具有较好的鲁棒性，对动 态环境具有一定的适应性 1 3 本文解决的主要问题与研究内容 1 3 1 新型建模方法的研究 传统的环境建模方法有可视图法和栅格法，栅格法存在栅格粒度难以控制的 缺陷，可视图法建模过程复杂，且不适用于动态环境。针对遗传算法的特点，本 课题采用了一种新颖的建模方法，该方法根据机器人出发点、目标点的位置建立 起新的坐标空间，染色体各基因位于机器人出发点及目标点连线的各等分点垂线 上 7 南京师范大学硕- j ：学位论文第一章绪论 l3 2 基于正反馈遗传算法的全局路径规划 遗传算法的一个固有缺陷是收敛速度较慢。本文在分析遗传算法收敛速度慢 的原因的基础之上，借鉴蚁群算法的思想，将正反馈机制引入基本遗传算法，从 而提高遗传算法的路径规划收敛速度，并将其应用到全局路径规划当中。 1 3 3 改进型正反馈遗传算法的滚动路径规划 为了提高路径规划的优化效果，消除本课题建模方法中染色体各基因只能位 于起始点目标点之间的等分点的垂线上的限制，本课题将添加结点及删除结点两 个新型的遗传算子引入到j 下反馈遗传算法之中，并结合滚动路径规划方法将其应 用于环境信息未知的局部路径规划当中，从而在一定程度上解决局部路径规划中 路径规划实时性差及路径优化效果差的问题。 1 4 本课题的主要创新点 本课题的创新之处体现在以下三个方面： ( 1 ) 新型的环境建模方法，该方法根据机器入出发点、目标点的位置建立 起新的坐标空间，染色体各基因位于机器人出发点及目标点连线的各等分点垂线 上，可使算法实现过程简化 ( 2 ) 借鉴蚁群算法的基本原理，将正反馈机制引入到基本遗传算法当中， 提高遗传算法在全局路径规划过程中的收敛速度 ( 3 ) 新型遗传算法子的引入，引入添加结点与删除结点算子到正反馈遗传 算法中，使可行路径中的各点不再局限于起始点至目标点各等分点的垂线上，并 将其应用于局部路径规划当中，进一步提高路径规划的优化效果及路径规划的实 时性 1 5 文章的组织结构 第一章概述了机器人路径规划这一主题，主要介绍了路径规划的基本问题及 遗传算法在路径规划中的应用情况以及其他路径规划方法的发展情况，并分别指 8 雨京师范大学硕士学位论文 第一犟绪论 出它们的优点及不足，随后介绍了目前机器人路径规划存在的问题以及路径规划 方法的发展趋势，最后说明了本课题的研究内容及创新之处。 第二章首先系统介绍遗传算法，说明了遗传算法的基本过程、基本要素及运 行参数的选取标准。最后介绍了遗传算法路径规划的基本过程以及存在的问题和 解决方向 第三章讲解基于正反馈遗传算法的全局路径规划。文章首先介绍环境建模， 之后，介绍蚁群算法的正反馈思想并将其引入到基本遗传算法当中，解决机器人 全局路径规划问题，最后分析了环境中存在u 形障碍物时的解决办法。 第四章改进基本的遗传算子，引入添加结点算子及删除结点算子，消除正反 馈遗传算法中染色体各基因只能位于起始点至目标点连线的等分点的垂线上所 带来的不精确性，最后结合滚动窗口法将其应用到局部路径规划当中。 第五章总结全文，并指出以后的努力方向 本章小结 本章为绪论部分，首先概述了机器人路径规划的基本内容，包括定义、分类 以及路径规划发展的基本情况，最后介绍了本文的研究内容、创新点及文章的组 织结构。 机器人路径规划就是在给定的环境中按照特定优化目标的要求，规划出从起 始点至目标点的一条无碰的最优或次优路径。环境建模是路径规划的重要一环， 常用的环境建模方法有可视图法及栅格法。路径规划可分为全局路径规划及局部 路径规划，全局路径规划的方法主要有贪心算法、d i j k s t r a 算法、a 算法及d 算法等，局部路径规划的方法主要有人工势场法、神经网络法、模糊逻辑算法及 蚁群算法等。遗传算法作为一种新型的智能算法由于具有并行性及全局搜索能力 强等特点也被引入到路径规划当中 针对路径规划的难点及遗传算法的缺陷，本课题主要研究如何结合蚁群算法 到遗传算法当中，提高遗传算法在路径规划中的收敛速度具体包括三个部分： 一是建模方法的研究，二是全局路径规划的研究以及环境中存在复杂障碍物时的 解决办法，三是局部路径规划中提高规划实时性及路径优化效果的手段研究。 9 南京师范大学硕士学位论文 第二章基于遗传算法的毒l 器入路径规划 第二章基于遗传算法的机器人路径规划 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型， 是一种新型的搜索寻优算法，它是美国的m i c h i g a n 大学的j h o l l a n d 教授于 19 7 5 年首先提出来的其模仿自然界中适者生存的原理，是一种群体性操作， 以群体中所有染色体为对象，以适应度函数为选择的标准，在问题的解空间中做 有向搜索，其基本元素包括染色体的编码、适应度函数、选择、交叉及变异三种 遗传算子“刀遗传算法由于具有并行性、较强的全局搜索能力及不易陷入局部 最小点等优点被引入到路径规划领域之中，但其有一个固有缺陷是收敛速度慢， 与其他智能算法结合是遗传算法在机器人路径规划领域应用中的一个重要发展 方向 本章系统讲述遗传算法及基于遗传算法的机器人路径规划方法以作为全文 的基础。 2 1 遗传算法简介 2 1 1 基本原理 遗传算法模拟自然进化过程，通过作用于染色体上的基因寻找好的染色体来 求解问题，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值 来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随 机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体，通过适应 度函数给每个个体一个数值评价，以概率原则选择高适应度的个体参加遗传操 作，包括选择、交叉及变异，经过遗传操作的个体集合形成下一代种群，然后对 这个新种群进行新一轮的遗传操作，直至满足终止条件心1 这就是遗传算法的基 本原理 2 1 2 工作流程及实现 遗传算法的工作过程是一个在适应值的指导下的自适应的非线性搜索过程， 解决问题的过程就是在可行解空间中，寻找出一个具有最佳适应值的解。遗传算 1 0 南京师范大学硕士学位论文第二章基于遗传算法的机器人路径规划 法的工作流程归纳如下： ( 1 ) 初始化群体； ( 2 ) 计算初始群体中的各个个体的适应度： ( 3 ) 按照由个体适应度值所决定的规则选择进入迭代的个体； ( 4 ) 两两随机配对，按概率p c 进行交叉操作； ( 5 ) 按概率p 对种群中的个体进行变异操作： ( 6 ) 若满足终止条件，转( 7 ) ，否则，转( 2 ) ； ( 7 ) 输出种群中适应值最优的染色体作为问题的解。 程序的终止条件有如下两种：完成了预先给定的进化迭代次数：种群中的最 优个体的适应值在连续若干代没有或基本没有变优以下是对遗传算法的详细描 述： ( 1 ) 种群初始化 采取随机的方式，生成m ( m 为设定的种群大小) 个特定编码方式的个体， 作为遗传算法迭代的初始种群，参与之后的选择、交叉及变异运算种群的规模 要适当，种群规模太小，种群中就没有充分的多样性，不利于适应度值高的染色 体的进化，但种群的规模越大每一轮进化花费的时间也越长 ( 2 ) 适应度函数 算法中个体的优良程度评价标准是个体的适应值，适应值较高的个体遗传到 下一代的概率就相对较大，而适应度较低的个体遗传到下一代的概率就相对小一 些。适应值的计算依据是适应度函数f ( x ) ，适应度函数的构造对遗传算法的性 能影响较大，需结合所求解问题的实际情况对适应度函数作适当的变换，提高选 择过程的效率 ( 3 ) 遗传操作 遗传算法中有选择、交叉及变异三种基本的遗传操作。 选择操作依据个体适应值对个体进行优胜劣汰操作，适应度较高的个体被选 择的概率较大，适应度较低的个体被选择的概率较小选择操作的主要目的是为 了提高全局收敛性和计算效率最常用的选择算子是比例选择算子 交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从 而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它 南京师范大学硕士学位论文 第二二章基于遗传算法的机器人路径土蔸划 在遗传算法中起着关键作用，是产生新个体的主要方法。 变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座 上的其他等位基因来替换，从而产生一个新的个体。从遗传运算过程中产生新个 体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传运算的全 局搜索能力；而变异运算只是产生新个体的辅助方法，但它也是必不可少的一个 运算步骤，因为它决定了遗传算法的局部搜索能力。交叉算子与变异算子的相互 配合，共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法能够以良 好的搜索性能完成最优化问题的寻优过程。 ( 4 ) 运行参数 遗传算法的运行参数主要有个体编码串长度l 、群体规模m 、终止迭代次数 t 、交叉概率凡与变异概率p 个体的编码方式有二进制编码、实数编码、符号编码等几种。使用二进制编 码来表示个体时，编码串长度l 的选取与问题所要求的求解精度有关；使用浮点 数编码来表示个体时，编码串长度l 与决策变量的个数n 相等；使用符号编码来 表示个体时，编码串长度l 由问题的编码方式来确定；另外，也可使用变长度的 编码来表示个体 群体规模m 表示群体中所含个体的数量。当m 取值较小时，可提高遗传算法 的运算速度，但却降低了群体的多样性，有可能会引起遗传算法的早熟现象；而 当m 取值较大时，又会使得遗传算法的运行效率降低。一般建议的取值范围是 2 0 - - 1 0 0 终止迭代次数t 是表示遗传算法运行结束条件的一个参数，它表示遗传算法 运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问 题的最优解输出一般建议的取值范围是l o 卜1 0 0 0 交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率一般应取较大 值，但若取值过大的话，它又会破坏群体中的优良模式，对进化运算反而产生不 利影响。一般建议的取值范围是0 4 - 一o 9 9 。另外，也可使用自适应的思想来确 定交叉概率p c 变异概率p - 若取值较大的话，虽然能够产生较多的新个体，但 也有可能破坏掉很多较好的模式，使得遗传算法的性能近似与随机搜索算法的性 能：若取值太小的话，则变异操作产生新个体的能力和抑制早熟现象的能力就会 南京师范大学硕士学位论文 第二章基于遗传算法的机器人路径规划 较差。一般建议的取值范围是0 0 0 0 l 卅1 。 需要说明的是这几个运行参数对遗传算法的求解结果和求解效率都有一定 影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需 要经过多次试算后才能确定出这些参数合理的取值大小或取值范围仃 2 1 3 基本特征 遗传算法采用群体方式对目标函数空间进行并行搜索，可同时对多个可行解 进行检查，具有较强的并行性，且交叉和变异操作使可行解之间交换信息和产生 新的可行解，使其不易陷入局部极小点，解的选择和产生采用概率方式，因此具 有较强的适应能力和鲁棒性。但遗传算法的一个固有缺陷是收敛速度慢，计算效 率差。 2 2 基于遗传算法的机器人路径规划 2 2 1 基本思想 应用遗传算法进行路径规划的两个关键问题是：问题解的编码和适应度评价 函数的定义。环境模型中一条可行路径即从起始点至目标点的一个点的序列被看 作遗传算法种群中的一个个体，也就是一个染色体，可采用的编码方式有二进制 编码、实数编码等，为提高计算精度常采用实数编码方式：某可行路径的适应度 函数值越大表示路径越优，反之则越差，所以适应度函数常取路径长度的倒数。 为在环境模型中搜索到一条从起始点到目标点的最优路径，算法在适应度函数的 指引下，进行选择、交叉及变异三种遗传操作，进行算法的迭代，在迭代过程终 止时即得到一条从起始点到目标点的最优路径。 2 2 2 算法步骤 应用遗传算法解决机器人路径规划的首要问题是进行环境建模，环境建模是 实现机器人工作的物理空间到算法处理的抽象空间的一个映射，目前常用的环境 建模方法有栅格法及可视图法等。环境模型建立起来之后，就可按照遗传算法的 1 3 南京师范大学硕士学位论文第二章基于遗传算法的机器人路径规划 基本过程在环境模型上进行路径搜索。其基本过程如下： ( 1 ) 初始化操作，初始化遗传算法的运行参数，包括个体编码串长度l 、 群体规模m 、终止迭代次数t 、交叉概率p 与变异概率p - ，确定对个体优劣性评 价的适应度函数，并在相关参数的控制下，产生初始种群初始种群是遗传算法 进行路径规划的起点，它由一定数目( 称种群规模m ) 的个体组成，为了保障路 径规划的全局最优性，初始种群应尽可能随机分布在搜索空间的每一个区域，并 计算种群中各个个体的适应值。 ( 2 ) 选择操作，依据个体适应值，按照概率选择原则，选择m 个个体，并 两两配对进入交叉操作 ( 3 ) 将每对配对的个体按照某种方式，以交叉概率p c 交换它们的部分染色 体，产生两个新的个体 ( 4 ) 对交叉操作产生的新个体，按照变异概率p - 对个体进行变异操作 ( 5 ) 对以上操作产生的无效路径进行处理，消除群体中的无效路径 ( 6 ) 判断是否满足终止条件，若满足，转( 7 ) ，否则，转( 2 ) 。 ( 7 ) 输出群体中适应度值最大的个体，作为最优路径 基于遗传算法的路径规划的基本流程可用图2 一l 简单描述： 同 、- - _ - - - - _ 一 图2 - 1 基本遗传算法路径规划流程图 1 4 南京师范大学硕士学位论文第二章基于遗传算法的帆器人路径规划 2 2 3 存在的主要问题及解决方向 应用遗传算法首先要解决的问题是环境建模，目前用于遗传算法路径规划的 环境建模方法主要有栅格法及可视图法等。应用栅格法进行环境建模时，存在栅 格粒度难以控制的缺陷，栅格划分大了，计算量降低，但发现最优路径的能力减 弱；栅格划分小了，发现最优路径能力增强，但计算量增大，计算效率降低。且 在交叉操作过程中，容易产生无效路径，且无有效的措施迅速地消除无效路径。 采用可视图法建模时，存在建模过程复杂，且可环境模型对障碍物的依赖性较大， 障碍物变动会引起环境模型的较大变动，不适用于动态环境下的环境建模。除此 之外，遗传算法还存在一个收敛速度慢的固有缺陷，以上两点致使应用遗传算法 进行路径规划存在计算量较大规划效率较低及优化效果差等问题。 基于以上存在的问题，应用遗传算法进行路径规划的改进主要体现在以下两 点： ( 1 ) 新型建模方法的研究，新的建模方法要容易实现，过程简单，能够有 效地表示出环境中的障碍物和自由空间。 ( 2 ) 提高遗传算法收敛性的手段研究，提高遗传算法收敛性的研究由来已 久，结合传统的搜索方法包括模拟退火法等确实能够提高遗传算法的收敛速度， 但存在过程复杂的缺陷，新型的智能算法包括蚁群算法( a c o ) 、粒子群算法( p s o ) 及人工神经网络法( a n n ) 由于具有较强的智能性及鲁棒性等特点，在很多领域 引起广泛重视，有效地结合其它新型智能算法，提高遗传算法的收敛速度是路径 规划的一个重要发展方向。 本章小结 本章首先介绍了遗传算法的基本原理，并介绍了应用遗传算法解决实际问题 的一般过程，在此部分，文中详细地说明了遗传算法的基本要素，遗传算法的基 本要素包括种群的初始化操作、评价个体优劣标准的适应度函数、选择、交叉及 变异三种基本的遗传算子以及遗传算法运行所涉及的基本参数，最后总结了遗传 算法的基本特征。 1 5 南京师范大学硕士学位论文 第二章甚于遗传算法的机器人路径规划 文中第二个部分主要介绍如何应用遗传算法解决机器人路径规划闯题，首先 介绍了基于遗传算法的路径规划的基本思想，接着介绍了算法的具体实现过程， 包括环境建模以及应用遗传算法进行路径搜索两个部分最后针对遗传算法的缺 陷，指出了遗传算法在路径规划领域中的重要发展趋势。 南京师范大学硕士学位论文第三章正反馈遗传算法路径规划 第三章正反馈遗传算法路径规划 针对常用的可视图法及栅格法建模的不足，本文研究了一种新颖的建模方 法。针对遗传算法收敛速度慢，影响路径规划效率的问题，借鉴蚁群算法的思想， 本文提出了正反馈遗传算法，文中使用一个二维矩阵记录环境中各部分的累积 值，依据累积值的大小，产生交叉及变异概率值，从而降低种群中个体的优良信 息被破坏的可能性，并将其用于解决全局路径规划问题，最后的仿真实验显示了 算法的有效性。 3 1 环境建模 目前常用的环境建模方法有栅格法及可视图法。栅格法建模时，栅格粒度难 以控制，栅格粒度过大，则路径优化效果差，栅格粒度过小，则算法计算量大， 影响路径规划的效率；可视图法建模过程复杂，且对环境中障碍物的依赖性较大， 不宜应用于局部路径规划当中。针对遗传算法的特点，研究了一种新颖的建模方 法，该方法根据机器人出发点、目标点的位置建立起新的坐标空间，染色体各基 因位于机器人出发点及目标点连线的各等分点的垂线上 机器人路径规划就是在工作环境中寻找一个从起始点到目标点的点的序列， 这些点及相邻点之间的连线不与环境中障碍物相交，且在所有这样的序列中，该 序列的路径长度最短。如图3 - i 所示，机器人的工作环境在坐标系x 咿y 中，s t a r t 为机器人的出发点，g o a l 为目标点，黑色实心物体表示障碍物，机器人路径规 划即是寻找一个点的序列p ： p = s t a r t ，p t ，p z ，p - ，g o a l 其中p ，( j = l ，2 ，n ) 不为障碍物点，其与相邻点的连接不与环境中的任何障 碍物相交，且满足路径长度最短的要求。 1 7 南京师范大学硕士学位论文 第三章正反馈遗传算法路径规划 r 图3 - 1 机器人工作模型图 在机器人的