（模式识别与智能系统专业论文）基于免疫进化与混沌变异的移动机器人路径规划.pdf

哈尔滨理工大学工学硕十学位论文 基于免疫进化与混沌变异的移动机器人路径规划 摘要 目前，随着机器人技术的不断进步，机器人学科越来越具有强大的生命 力，它在某种程度上已经代表当今信息技术、自动化技术、系统集成等技术的 最新发展。 从移动机器人的历史和现状出发，对比了国内外的不同发展状况，对移动 机器人领域的研究方向进行了综述。路径规划是移动机器人系统中的一个重要 内容，因为它的好坏直接影响到机器人所完成任务的质量，所以路径规划成为 移动机器人领域的一个研究热点。着重介绍了移动机器人路径规划中常用的方 法，对其中的势场法、栅格法、遗传算法进行了逐一的分析阐述。 本文针对路径规划的特点，对算法的各个环节进行了细致的分析，包括染色 体的表示和编码，适应度函数的设计，遗传操作算子的设计，算法参数的分析和选 取提出了将免疫进化算法应用与移动机器人路径规划的综合解决方法 应用免疫进化算法实现了移动机器人静态环境下的路径规划。在执行规划 程序之前先建立了机器人的工作环境，然后执行基于免疫进化算法的路径规划 算法。在此算法中：编码方式采用简化的实数编码方法，把机器人的二维坐标 简化为一维，加快了机器人最优路径的搜索速度：初始化方法采用大范围初始 化，通过综合考虑路径的可行性、路径的光滑性和路径长度，制定了有效的适 应度函数：交叉算子采用单点交叉策略：通过免疫算子把所有的路径优化成可行 路径，然后通过混沌变异算子进行路径的全局搜索。 针对传统进化算法的“早熟收敛”和“收敛速度慢”两大致命缺点，在分 析了导致以上缺点原因的基础上，提出了一种基于人工免疫与混沌变异的双群 进化算法。在该算法中，进化在两个子群间同时进行，一个种群使用混沌变异 算子对解空间进行充分搜索，另一个种群使用指数衰减的高斯算子进行局部搜 索，较快速地规划出性能是全局优化的可行路径。通过在m a t l a b 中的仿真证 明：采用免疫进化方法进行机器人的路径规划是有效的和可行的。 关键词移动机器人；路径规划；进化算法；免疫；混沌 - i 一 堕查鎏耋三奎兰三兰堡圭兰堡鎏塞 p a t hp l a n n i n gb a s e do ni m m u n e e v o l u t i o na n dc h a o t i cm i j r l a o nf o r m o b i l er o b o t a b s t r a c t w i t ht h ec o n t i n u o u sp r o g r e s so fr o b o t st e c h n o l o g y , m o b i l er o b o tr e p r e s e n tt h e d e v e l o p m e n t o fi n f o r m a t i o n t e c h n o l o g y ，a u t o m m i o nt e c h n o l o g y 、s y s t e m i n t e g r a t i o nt e c h n o l o g yt os o m ee x t e n t t h et h e s i sm a k e sas u m m a r yo nd i f f e r e n tr e s e a r c ha s p e c t so fm o b i l er o b o ta n d c o n t r a s tt h ed i f f e r e n td e v e l o p m e n tl e v e lo ff o r e i g na n dd o m e s t i c i np a r t i c u l a r , p a t h p l a n n i n gi si m p o r t a n tt om o b i l er o b o ts y s t e mb e c a u s ei td e t e r m i n e st h eq u a l i t yo ft h e r o b o t st a s la sar e s u l t ，p a t hp l a n n i n gh a sa t t a i n e dm o r ea n dm o r ea t t e n t i o ni nt h e f i e l do fm o b i l er o b o t s e v e r a lm e t h o d ss u c ha sp o t e n t i a lf i e l dm e t h o d 、g r i d m e t h o d 、 g e n e t i ca l g o r i t h mm e t h o d , w h i c hu s e d i nm o b i l er o b o t so b s t a c l e a v o i d a n c ea n dp a t hp l a n n i n ga r ed e s c r i b e di nd e t a i l a c c o r d i n gt ot h ec h a r a c t e r i s t i co fp a t hp l a n n i n gp r o b l e m ，e v e r yc o m p o n e n to f t h ea l g o r i t h m sa r ea n a l y z e dc a r e f u l l y , i n c l u d i n gc h r o m o s o m er e p r e s e n t a t i o n 、p a t h e v a l u a t i o n 、g e n e t i co p e r a t o r sd e s i g na n dg ap a r a m e t e r ss e l e c t i o n an e wg e n e t i c a l g o r i t h mi sp r e s e n t e db yu s eo fg e n e t i ca l g o r i t h mt oo p t i m i z et h ev a l i dp a t h g e n e r a t e db yn u m e r i c a lp o t e n t i a lm e t h o d u s i n gt h ec o n c e p to fi m m u n ee v o l u t i o n a p p l y i n gt op a t hp l a n n i n g i nt h ef o l l o w i n gc o n t e x t , w eu s et h eg e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h mt o c a r r yo u tg l o b a lp a t hp l a n n i n gi ns t a t i c b e f o r ep a t hp l u m i n gp r o c e s s , r o b o t s w o r k i n ge n v i r o n m e n ti s b u i l tb yv e r t e xm e t h o d i nt h ea l g o r i t h m ，as i m p l er e a l n u m b e rc o d i n gt e c h n i q u ei su s e dt oa c c e l e r a t et h es e a r c ho fo p t i m u mp a t h t h e c o m p l i c a t e dt w o d i m e n s i o n a lp a t h - c o d i n gp r o b l e mi sr e d u c e dt o as i m p l eo n e - d i m e n s i o n a lp r o b l e mi nt h ec o d i n gs c h e m e l a r g e - s c a l ei n i t i a l i z a t i o nc o m b i n e dw i t h 一 堕查篓矍三奎兰三耋堡占兰堡鎏耋 t h es e l e c t i n gm e c h a n i s mi sa p p l i e dt oi n i t i a l i z et h es t a r t i n gp o i n to u to ft h eb a r r i e r a r e a t h ef e a s i b i l i t y 、s m o o t h n e s sa n dl e n g t ho fap a t hd e t e r m i n ea ne f f i c i e n t a d a p t i v ef u n c t i o n s e l e c ts t r a t e g yu s e sp r o p o a i o ns e l e c tm e t h o d ；c r o s s o v e ro p e r a t o r i so n e - p o i n tc r o s s o v e rs t r a t e g y i m m u n eo p e r a t o rf w s f l yu s e st o a l g o r i t h m t o t r a n s f o r ma l lt h ep a t h st of e a s i b l ep a t h s ；t h e nt h eo p e r a t o ro fc h a o f i cm u t a t i o ni su s e d f o rg l o b a lp a t hp l a n n i n g p r e m a t u r e l ya n dl o wc o n v e r g e n ts p e e di s t h et w of a t a l s h o r t c o m i n go f t r a d i t i o n a le v o l u t i o na l g o r i t h m i nt h i sp a p e r , b a s e do nt h es h o r t c o m i n ga n a l y s i s a b o v ea l l ，ab i g r o u pe v o l u t i o n a r ya l g o r i t h mb a s e do na r t i f i c i a li m m u n ea n dc h a o t i c m u t a t i o ni sp r o p o s e d i nt h i sa l g o r i t h m ，e v o l u t i o n so fs u b g r o u p sa l ep a r a l l e l p e r f o r m e dw i t hd i f f e r e n tm u t a t i o ns t r a t e g y o n eo ft h es u b g r o u p st a k e sc h a o t i c m u t a t i o no p e r a t o rt oe x p l o r et h es o l u t i o ns p a r es e p a r a t e l y , a n dt h eo t h e rs u b g r o u p s e a r c h e st h el o c a lp a r td e t a i l e du s i n ge x p o n e n t i a ld e s c e n to p e r a t o r t h i sa l g o r i t h m c o u l dq u i c k l yp l a ng l o b a l - o p t i m a lp a t h a si ti sp r o v e db yt h er e s u l t so ft h et e s t , t h e s i m u l a t i o nr e s u l tc o n f i r m st h a tt h eg e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h mi sf e a s i b l e a n de f f i c i e n tf o rm o b i l er o b o tp a t hp l a n n i n g 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 ：e v o l u t i o n a r ya l g o r i t h m ；i m m u n e ： c h a o $ 一m 一 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于免疫进化与混沌变异的 移动机器人路径规划，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位 期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不 包含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集 体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名婚吼砷年弓月”日 f 7 。 哈尔滨理工大学硕士学位论文使用授权书 基于免疫进化与混沌变异的移动机器人路径规划系本人在哈尔滨理工 大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果 归哈尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人 完全了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向 有关部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工 大学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部 分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密口。 作者躲j 侈 导师签名：雀豆& 一 日期：刀多年多月踢日 醐。硝乡月罗日 哈尔滨理工大学1 二学硕十学位论文 1 1 引言 第1 章绪论 智能移动机器人是一类能够通过传感器感知环境和自身状态，实现在有 障碍物的环境中面向目标的自主运动，从而完成一定的作业功能的机器人系 统【1 1 。移动机器人导航技术【2 5 】的研究内容主要包括移动机器人的同步定位与 地图创建【“、路径规划1 1 。”、多传感器信息融合【1 s 柳、控制结构设计l “、 故障诊断与检测系统【“1 若干方面的内容。 移动机器人的研究始于2 0 世纪6 0 年代末期，7 0 年代末随着计算机技术和 传感器技术的发展，世界上的一批公司开始研究移动机器人平台，这些移动 机器人平台主要作为大学实验室及研究机构的移动机器人平台近年来，自 主式移动机器人( a u t o n o m o u sm o b i l er o b o t ) 技术【”冽在工业、农业、医学及 社会服务领域显示了越来越广泛的应用前景，因而成为国际机器人学术研究 的热点问题。移动机器人是一种使用比较广泛的机器人。移动机器人的路径 规划就是给定机器人及其工作环境信息，按照某种优化指标，在起始点和目 标点间规划出一条与环境障碍无碰的路径。机器人路径规划的研究始于2 0 世 纪7 0 年代，目前对这一问题的研究仍十分活跃，许多学者做了大量的工作。 其主要研究内容按机器人工作环境不同可分为静态结构化环境、动态己知环 境和动态不确定环境：按机器人获取环境信息的方式不同可分为基于模型的 路径规划和基于传感器的路径规划。 近年来，移动机器人技术在工业、航空航天，特别是空间探测等许多领 域发挥着重要作用，因此越来越成为学术界关注的热点。目前，在确定环境 下的导航技术已经取得了大量的研究和应用成果，但对未知环境下的导航技 术仍有许多问题有待解决。本文对移动机器人导航技术进行了分类并进行了 较为详细的分析介绍，最后对其发展趋势做了进一步的阐述。 移动机器人路径规划算法的效率直接影响了移动机器人导航系统的性能， 很多学者对路径规划做了大量的研究并提出了一些方法，常用的有可视图 法、栅格法和人工势场法等，但这些算法都存在着各自的缺点。可视图法当 障碍物过多时，搜索速度会很慢，并且对圆形障碍物无法处理等。栅格法当 空间增大时所需存储空间剧增，决策速度慢。人工势场法结构简单，便于底 哈尔滨理工大学工学硕士学位论文 层实时控制，但它有在障碍物前振荡、在狭窄通道中摆动等缺点。 遗传算法1 2 9 l i 驯p l l ( g e n e t i ca l g o r i t h m ：g a ) 是1 9 6 2 年由美国学者h o l a n d 提出 的模拟生物进化机制形成的一种随机并行搜索优化方法，由于它在优化问题 上没有对函数要求连续以及能微分的限制，并且是一种多点搜索算法，近年 来逐渐成为研究的热点，但也存在一些亟待克服的弱点：进化容易出现早熟 现象以及进化后期的搜索效率降低，对初始参数敏感等缺点。很多学者对此 做了改进，改进了选择方法、交叉概率和变异概率等，但这些改进都是局部 的，性能指标提高不大。 遗传算法、进化规划和进化策略均属于进化算法。近年来，随着生物免 疫技术的发展，人们开始了解并对人体免疫系统开始建立模型，即建立的人工 免疫模型，这将有利于我们对免疫系统的理解和应用。 本文针对传统的进化算法的弱点，提出了一种基于人工免疫模型【3 2 1 1 3 3 1 的 双群进化算法( a r t i f i e i a li m m u n eb a s e db i g r o u pe v o l u t i o n a r ya i g o d t h m ： a i b e a ) 在该算法中，进化在两个平行的子群问同时进行，其中一个子 群使用混沌变异算子进行充分搜索，使种群中的部分个体落在全局最优解的 邻域，另一个子群使用递减的高斯变异算子进行详细搜索，以期以高精度逼 近全局最优解。通过测试表明，该算法能以较快地速度规划出移动机器人的 全局优化路径。 1 2 移动机器人技术 1 2 1 移动机器人的研究现状 机器人技术在国际上发展很快，其中日本的机器人发展最好。日本索尼 公司和东芝公司最近相继推出运动性能更佳、会话能力更强的新型机器人。 索尼公司日前宣布，该公司的小型双腿直立行走机器人“s d r 一4 x l l ”在身 体失去平衡的情况下，能根据自己的判断采取行动，防止摔倒。若不慎摔 倒，也能迅速敏捷地用适当的姿势减少地面对自身的冲击力本田公司投入 巨资，经过1 0 多年的开发，终于研制出了在世界上居领先地位的双足步行机 器人一p 3 ，p 3 通过它的身体的重力感应器和脚底的触觉传感器把地面的状况 送回电脑，电脑则根据路面情况做出判断，进而平衡身体，稳定地前后左右 行走。它不仅能走平路，还可以走台阶和倾斜的路。本田公司最近又推出一 种新型智能机器人“阿西莫”( a s i m o ) 。与1 9 7 7 年诞生的p 3 相比，它具有 哈尔滨理工大学t 学硕十学位论文 体型小、质量轻、动作紧凑轻柔的特点。阿西莫身高1 2 0 c m ，体重4 3 公斤， 更适合于家庭操作和自然行走。 在自主移动机器人中有一类机器人叫做进化机器人，它用进化算法来实 现机器人控制、机构等方面的优化，在路径规划中主要是能够进化出合适的 运动轨迹。d f l o r e a n o 和em o n d a d a 成功地用k h e p e r a 机器人实现了一个进化 系统。自从j o h n r k o z a 提出遗传规划( g e n e t i cp r o g r a m m i n g ，g p ) 以来，遗 传规划已经在许多方面得到了应用，如缠绕的螺旋线的分辨( s p i r a l c l a s s i f i c a t i o n ) 、图像压缩( i m a g ec o m p r e s s i o n ) 、符号回归( s y m b o l i c r e g r e s s i o n ) 等问题。 进化规划在机器人路径规划中的应用也是国外许多学者研究的目标，并 且己经出现了许多令人兴奋的成果。其中比较早影响也比较大的是人工蚂蚁 的问题，这些应用进化规划来规划路径的蚂蚁能够自主地寻找食物并吃掉食 物，而且能够避开障碍。在机器人沿墙运动方面也有研究，d a i nra 已经开 发了一种基于测距仪的仿真移动机器人，导航策略在不同的环境中测试以获 得稳定的解决方案，仿真实验也证明了这一点。 国内外对自主移动机器人的导航和避障问题己经做了大量的研究工作， 比如哈尔滨工业大学机器人研究所在1 9 9 6 年1 1 月研制成功一个“导游小 姐”，该机器人能够实现避障和自主路径规划，识别障碍物的类型，具有一 定的语音功能，具有极强的遥控功能。这个机器人能够根据传感器信息自主 规划路径。由行走部分、行使控制器、显示器、语音识别系统和大量的传感 器组成，行走部分采用差速驱动的方式。既可以不确定环境下进行路径规 划，也可以显示机器人行走的路径和某个时刻导游机器人所在的位置。大面 积宽阔地面的清扫工作一直是一项繁重的体力劳动，人工清扫费时、费力且 工作效率低，将机器人用于清扫服务，具有广阔的应用前景。为实现适合我 国国情的宽阔地面自动清扫，清华大学与香港中文大学合作，联合研制开发 出一种全方位移动清扫机器人。该机器人具有如下特点：( 1 ) 采用全方位轮实 现任意方向的移动，使得机器人可执行对狭窄区域的清扫任务。( 2 ) 采用开 放式机器人控制结构，实现硬件可扩展、软件可移植、可继承，使机器人作 为服务载体具有更好的功能适应性。( 3 ) 机器人具有在拥挤环境下的实时避 障功能，能适应不断变化的清扫工作环境。( 4 ) 具有遥控操作和自主运动两 种运行方式。( 5 ) 吸尘机构可实现吸尘腔路的自动转换，提高了吸尘效率。 ( 6 ) 具有智能电源管理功能，延长了运行时间，提高了对有限的移动动力资 源的利用率。 国内在遗传规划方面研究主要是西安建筑科技大学，云庆夏教授编写的 进化算法比较详细介绍了遗传规划相关内容，并且把遗传规划应用于优 化地下采切工程结构，实现了崩落采矿方法底部结构和采切巷道布置的智能 化和自动化，制作了遗传规划应用于地下井巷结构优化的软件，对于给定的 矿山地质条件及技术经济指标，经过遗传规划的复制、交叉、突变等操作可 以自动得出满意的井巷布置方案，为矿山设计自动化和智能化提供了一种新 的技术工具。 另外，上海交通大学自动化所利用c + + 语言也对该算法在机器人沿墙移 动问题进行了仿真实验，通过对移动机器入的行为策略迸行符号型编码，然 后对这些策略的组合( g p 算法个体) 迸行自然选择、优胜劣汰，最后进化出 满足任务需要的优良个体，这些个体实际上就是机器人沿墙移动的一系列指 令有序组合。最后的仿真结果说明了应用g p 算法来演化移动机器人沿墙走 行为的有效性。 1 2 2 移动机器人路径规划技术的研究现状 移动机器人路进规划技术按其规划方式不同可以分为：基于地图的规划 方法、基于环境建模的规划方法、基于行为的规划方法三种类型。 地图更新法是机器人根据当前的地图信息规划路径，沿路径前进一段时 间后，利用这段时间收集到的环境信息更新地图，然后利用更新过的全局地 图重新规划和调整路径。这种过程循环下去，直到到达目标为止。 基于事例路径的学习规划方法依靠过去的经验进行学习及问题求解，一 个新的事例路径可以通过修改事例路径库中与当前情况相似的旧的事例路径 来获得，将其应用于移动机器人的路径规划中可以描述为：首先，利用路径规 划所用到的或已产生的信息建立一个事例路径库，库中的任一事例路径包含 每一次规划时的环境信息和路径信息，这些事例路径可以通过特定的索引取 得：随后，将由当前规划任务和环境信息产生的事例路径与事例路径库中的事 例路径进行匹配，以寻找出一个最优匹配事例路径，然后对该事例路径进行修 正。并以此作为最后的结果。 该方法首先需要建立一个关于机器人运动环境的环境模型，在很多时候 由于移动机器人的工作环境具有不确定性( 包括非结构性、动态性等) ，使得 移动机器人无法建立全局环境模型，而只能根据传感器信息实时地建立局部 环境模型，因此局部模型的实时性，可靠性成为影响移动机器人是否可以安 全、连续二平稳运动的关键。 基于环境建模的方法基本上可以分为两类：网络图建模方法，基于网格的 建模方法，前者主要包括自由空间法、顶点图像法、广义锥法等，利用它们在 进行路径规划时可得到比较精确的解，但所耗费的计算量相当大，不适合于实 际的应用，而后者在实现上要简单许多，所以应用比较广泛，其典型代表就是 四叉树建模法及其扩展算法( 如基于位置码四叉树建模法f r a m e d q u a d t r e e s 建模法等) 基于环境模型的规划方法根据掌握环境信息的完整程度可以细分 为环境信息完全已知的全局路径规划和环境信息完全未知或部分未知的局部 路径规划，由于环境模型是已知的，全局路径规划的设计标准是尽量使规划的 效果达到最优，在此领域已经有了许多成熟的方法，包括可视图法、切线图 法、v o r o n o i 图法、拓扑法、惩罚函数法、栅格法等。前4 种方法都是采用 基于图论的思想，将目标机器人及其工作空间用一个连接图表示，如此一来， 路径规划问题就转化为在图上寻找一条从起始节点到目标节点的路线。惩罚 函数法将路径规划这个有约束的问题( 受到障碍物的限制) 转化为一个无约束 最优化问题，再求解就可得出解答。栅格法用网格描述机器人的工作环境，根 据栅格的可信度值可确定出障碍物的分布，此时通过避障规划就可得到无碰 路径。作为当前规划研究的热点问题，局部路径规划得到了深入细致的研 究，对环境信息完全未知的情况，机器人没有任何先验信息，因此规划是以提 高机器人的避障能力为主，而效果作为其次。k o e i n gs 等提出了增量式的 d l i t e 算法，该方法利用启发式策略搜索一条从目标点指向机器人当前位置 的路径，并在机器人向目标运动过程中根据局部环境的更新信息来实时重规 划路径，由此得出一条最优路径。在国内，张纯刚等提出了基于滚动窗口的规 划方法，也取得了较好的效果。 在环境部分已知部分未知时的规划方法主要有人工势场法、模糊逻辑算 法、遗传算法、人工神经网络、模拟退火算法、蚁群优化算法、粒子群算法 和启发式搜索方法等。前4 种方法相对应用较广，后几种则是近年来才比较 流行，其中启发式方法的研究取得了较大进展，启发式方法的最初代表是。 算法，而其新发展是d 。和f o c u s s e dd + 这两种由s t e n t za 提出的增量式图搜索 算法( 又称作d y n a m i co 算法) 的产生d 算法可以理解为动态的d i j k s t r a ( 最 短路径) 算法，而f o c u s s e dd 算法则利用了a + 算法的主要优点即使用启发式 估价函数，两种方法都能根据机器人在移动中探测到的新的环境信息快速地 修正和重规划出最优路径，减少了局部规划的时间，对于在线的实时路径规划 有很好的效果。此外，还出现了一些基于a 的改进算法，它们一般都是通过 哈尔滨理t 大学t 学硕士学位论文 修改a 算法中的估价函数和图搜索方向而实现的，可以较大地提高路径规划 的速度，具有一定的复杂环境自适应能力。 基于行为的方法由b r o o k s 在他著名的包容式结构中建立。它是一门从生 物系统收到启发而产生的用来设计自主机器人的技术，它采用类似动物进化 的自底向上的原理体系，尝试从简单的智能体来建立一个复杂的系统。将其 用于解决移动机器人路径规划问题是一种新的发展趋势，它把导航问题分解 为许多相对独立的行为单元，比如跟踪、避碰、目标制导等。这些行为单元 是一些由传感器和执行器组成的完整的运动控制单元，具有相应的导航功能， 各行为单元所采用的行为方式各不相同，这些单元通过相互协调工作来完成 导航任务。基于行为的方法大体可以分为反射式行为、反应式行为、慎思行 为3 种类型。 1 2 3 移动机器人路径规划技术的应用 近年来，自主式水下机器人由于其在海底资源探测上的优势而受到各国 的关注，但因为水下环境十分复杂( 能见度差、定位困难等) ，导致一般的规划 方法都难以奏效，而水下环境的拥挤程度相对较低，机器人工作在同一区域 的可能性较大这一特征恰好有利于基于事例的规划方法的应用，因此该方法 被广泛的用于解决水下机器人的路径规划问题，试验证明其效果也较为理想， 图1 1 中俄研制的“c r - 0 1 ”6 0 0 0 m 自治水下机器人。 图1 - 1 “c r - 0 1 ”6 0 0 0 m 自治水下机器人 f i g u r e1 - 1 “c r - 0 1 ”6 0 0 0 ma u t o n o m o u ss u b a q u e o u sr o b o t 美国于1 9 9 6 年1 2 月发射了“火星探路者”探测器，并用所携带的“索 哈尔滨理t 大学1 = 学硕十二学位论文 杰纳”火星车( 如图1 - 2 所示) 对火星进行了实地考察，获得了很大的成功。 索杰纳所采用路径规划方法就是d 算法，它使索杰纳能在火星表面自如而谨 慎地行走，且能自主判断出前进道路上的障碍物，并通过实时重规划来作出后 面行动的决策，真正做到了“三思而后行”，图1 2 “索杰纳”火星车。 图1 - 2 “索杰纳”火星车 f i g u r e1 - 2 “s o j o u r n e r v e h i c l eo fm a r s 基于行为的方法在中智能家庭等商业领域受到了许多研究人员的青睐， 刘瑜等成功地研制出两代自主智能吸尘机器人样机( 如图1 3 所示) ，将基于 行为的思想引入机器人的作业规划中，提高了规划的效率和对环境的适应度， 具有良好的应用前景，图1 3 浙江大学的智能吸尘机器人h s r 2 0 0 0 。 图1 - 3 智能吸尘机器人h s r 2 0 0 0 f i g u r e1 - 3i n t e l l i g e n tc l e a nr o b o th s r 2 0 0 0 哈尔滨理1 = 大学t 学硕t 学位论文 1 2 4 移动机器人路径规划技术的发展方向 1 基于反应式行为规划与基于慎思行为规划的结合 基于反应式行为的规划方法在能建立静态环境模型的前提下可取得不错 的规划效果，但它不适合于环境中存在一些非模型障碍物( 如桌子、人等) 的 情况。为此，一些学者提出了混合控制的结构，即将慎思行为与反应式行为相 结合，可以较好地解决这种类型的问题。l o wkh 将结合两者的混合控制结 构运用在不可预知环境下的避撞导航，各个行为模块之间是异步运行的，与一 般的控制结构相比，其规划模块得出的是一系列的点集而不是一条完整的路 径，反应式模块具有避碰和目标制导的双重功能g a te 提出了著名的三层控 制结构，包括控制层、序列层、慎思层、控制层利用反应式行为迅速地感应 环境，慎思层主要进行路径规划等处理过程，序列层用于连接以上2 层，该结 构保证了机器人在时间上对环境的准确把握h a s s a nh 也提出了一种实时的 混合控制结构，能在有限的时间内选择合理的执行动作，并能根据环境信息来 调节机器人的行为，具有较强的灵活性，有效地解决了有限可用时间与慎思行 为需要消耗一定时间之间的矛盾，满足了反应式行为的变化要求。 2 全局路径规划与局部路径规划的结合 全局规划一般是建立在已知环境信息的基础上，适应范围相对有限：局部 规划能适用于环境未知的情况，但有时反应速度不快，对规划系统品质的要求 较高，因此如果把两者结合就可以达到更好的规划效果，g u l d n e r 提出了三层 控制结构，以全局规划作为最高层，采用势场方法的局部规划为第二层，最底 层用航向角方法( s t e e r a n g l ef i e l d a p p r o a c h ) 来进行避障，适合于杂乱环境中 的路径规划。d i e g u e za r 提出了一种新的多级结构，包括全局规划、局部规 划、智能监督、传感器信息融合、路径选择和导航6 个层次，其中局部规划 层还可以分为局部路径计算和路径优化两部分，该方法能有效地利用局部规 划时间从而得出相对更好的路径。 3 传统规划方法与新的智能方法之间的结合 近年来，一些新的智能技术逐渐被引入到路径规划中来，也促使了各种方 法的融合发展，例如人工势场与神经网络、模糊控制的结合等。k y u ny 的混 合控制结构先用神经网络对环境进行分类以避免陷入局部最小，并建立基于 反应式行为的控制器，再根据场法选择一个特定的反应式行为来引导移动机 器人前进，该结构有较好的鲁棒稳定性，对动态环境具有一定的适应性。 m b e d ejb 设计了一种融合了模糊逻辑和人工势场函数的模糊控制器，解决 哈尔滨理工大学t 学硕士学位论文 了已知环境中存在未知动态障碍的规划问题，较大地提高了运动规划的效率， 适合于实时应用。w ukh 先利用人工势场法引导移动机器人向目标前进， 再采用模糊逻辑的方法使机器人能走出势能陷阱并产生一条平坦而安全的路 径，实验结果证明了该方法具有可行性。 路径规划将朝着多层规划和多方法相结合的方向发展。采用基于反应式 的行为规划与基于慎思行为规划相结合的方法：用基于行为的模块化单元作 为控制底层，用信息融合算法单元作为慎思层，这样更容易找到最优路径。 全局路径规划和局部路径规划相结合更有利于复杂环境的避障规划。传统方 法与新的智能方法相结合将给路径规划问题提供新的思路。 总结目前的研究可以看出：第一，许多路径规划方法在完全已知环境中能 得到令人满意的结果，但在未知环境特别是存在各种不规则障碍的复杂环境 中，却很可能失去效用所以如何快速有效地完成移动机器人在复杂环境中 的导航任务仍将是今后研究的主要方向之一第二，对于各种规划方法的改 进有这样一个趋势) 从对某一种方法的局部修改转向把某几种方法相互结 合。因此怎样把各种方法的优点融合到一起以达到更好的效果也是一个有待 探讨的问题。第三，目前大多数规划方法都只针对固定目标点而没有考虑移 动目标点( 如足球机器人比赛中的足球) 的情况，此时的规划由于要考虑机器 人，目标的位置信息和速度信息而更加复杂，这方面研究也是今后发展的重 点。此外，多智能机器人系统( 如足球机器人) 作为一项新的智能技术逐渐成 为关注热点，它是在单体智能机器发展到需要协调作业的条件下产生的，其规 划的难点在于多机器人的协调和避碰前进，这也将是移动机器人技术急需拓 展的领域。 1 3 进化算法和人工免疫算法 进化算法和应用方面的研究在近年来有了很大发展。1 9 9 4 年第一届工业 进化计算国际会议就设置了进化算法专题，相应的子标题有理论、分析、控 制及扩展等。进化算法己成为进化计算中的一个重要方法。进化算法的主要 发展趋势表现在以下方面： ( 1 ) 算法本身的研究与改进。进化算法中问题约束、个体表示、适应度 定义、选择策略和进化算子等均是重要研究内容。可以从算法设计、结构描 述和数学的形式化建模等方面入手，结合实际应用进行研究。 ( 2 ) 进化算法的理论研究。目前进化算法的有关理论体系还很不完整， 诸如适应度状态、收敛性等方面的研究还仅局限于定性分析阶段。泛函空间 分析、随机过程和集映射等数学工具将更多的应用于该领域的研究。 ( 3 ) 进化算法在程序设计和实现方面的改进。数据结构对算法的效率有 很大影响，如何构造更适用于进化算法的数据结构也是一个比较活跃的研究 领域。如在进化算法的个体表示上己经出现了层状、网状模型，堆栈结构成 为一个新的探索方向，己有人在这方面作了一些很有意义的工作。 ( 4 ) 在虚拟现实和信息检索方面的应用。这方面己做的工作还不多，但 由于进化算法个体表达形式的特点，具有广阔的发展前景。 ( 5 ) 与其他方法相结合。与进化算法一样，进化算法也日益与神经网 络、专家系统、灰色系统以及其他数学工具相融合，一起解决具体应用问 题。 免疫是生物体的特异性生理反应，由具有免疫功能的器官、组织、细 胞、免疫效应分子及基因等组成。免疫系统通过分布在全身的不同种类的淋 巴细胞识别和清除侵入生物体的抗原性异物。当生物系统受到外界病毒侵害 时，便激活自身的免疫系统，其目标是尽可能保证整个生物系统的基本生理功 能得到正常运转。当人工免疫系统受到外界攻击时，内在的免疫机制被激活， 其目标是保证整个智能信息系统的基本信息处理功能正常运作。 今后免疫算法的研究重点大致集中在以下几方面： ( 1 ) 免疫算法的有效性：类似于人的免疫系统的抗病能力，人工免疫系统 的免疫算法必须是有效的，必须确实能够自适应性地减弱或消除外来的损害， 例如杀毒。 ( 2 ) 自我一非自我的智能化识别能力：用智能化技术增强免疫算法的异己 识别能力是重点之一。 ( 3 ) 免疫算法的智能效果：将免疫算法引入应用系统是否能增强系统的整 体智能是评价算法成败的一个重要指标。 ( 4 ) 并行免疫算法与网络：免疫算法与网络的并行化是算法发展的必然趋 势，并正成为研究的热点之一。而自然免疫系统的潜在并行处理能力无疑为 免疫算法与网络的并行化奠定了根本的生物基础。 ( 5 ) 免疫算法在网络、智能系统和鲁棒系统中的应用：由于免疫算法来源 于基于神经网络和内分泌网络的自然免疫系统，网络和智能必将成为免疫算 法发展的不可缺少的特征，也是其重要应用领域。免疫算法能增强系统的鲁 棒性，而且免疫性与鲁棒性之间存在的必然联系使得免疫算法将在鲁棒系统 中得到较好的应用。 哈尔滨理工大学1 = 学硕+ 学位论文 免疫算法是人工免疫系统的重要算法，用来模拟自然界中生物免疫原理， 对外界侵害进行识别、学习和防御操作，达到系统损害的最小化，从而实现系 统鲁棒性、安全性和智能性的最大化。根据免疫算法的研究经验，外来侵害 的检测和内部学习机制的优化成为两大难点。目前使用的外来侵害检测算法 还十分简单低能，与生物体的机能差距很大，远不能满足实际应用的需要。改 进免疫算法的识别模块需要利用模式识别、决策、网络入侵等方面的知识和 技术。现在的免疫算法一般建立在精确的数学模型公式或进化计算的基础 上。数学模型固然简单、易于实现，但功能不强，结果往往失真，智能度不高。 也不便于改进。进化计算是一种比较成功也比较成熟的仿生优化算法，可以 实现全局最优，也可以进行并行分布式计算，但其弱点在于效率不高，随机性 不好把握。为了提高算法的效率，可进行并行处理，也可根据具体问题的信息， 在免疫算法中加入问题的启发性信息，以优化算法的效率。虽然免疫算法的 发展主要有以上两个难点，但免疫算法的发展前景依然十分乐观，实际应用的 召唤和成功实例大大增强了免疫算法发展的必要性和可能性。以后随着人工 免疫系统的发展，免疫算法会逐步成熟，成为人工免疫系统的计算中心。免疫 算法在计算机网络方面的应用将会不断增强和扩展，网络的安全性和鲁棒性 将会得到实质性的提高，其智能水平也会不断提高。机器人作为研究的热点， 免疫机器人的提出、研究和开发将成为智能机器人的一个亮点：故障诊断的 智能化是发展趋势，免疫算法在故障诊断方面的应用能大大提高其智能度，增 强诊断效果。 1 4 本课题的研究内容和意义 本论文模拟了一个的移动机器人，在环境己知情况下，寻找一条路径最 短的无碰路径，并与障碍物的距离保持大于等于最小安全距离。主要的工作 有以下几点： ( 1 ) 全局的环境建模。要求移动机器人寻找一条从起始点到目标点的无 碰路径。并做如下假设：机器人对工作环境信息己知，其工作环境为二维有 界环境，并且障碍物的位置、大小均已知且不发生变化，机器人可以向各个 方向运动。 ( 2 ) 全局的路径规划。在全局的环境建模后，进化算法搜索到全局的最 佳路径。进化模拟自然界的“适者生存”的自然法则。 ( 3 ) 进化算法的实现及改进。本文中的路径规划的实现是通过免疫原理 哈尔滨理1 = 大学t 学硕士学位论文 和进化规划算法相结合来实现的。 ( 4 ) 机器人路径规划仿真。通过编写程序在计算机上实现模拟机器人应 用于实际的情况是必要的。 经过以上的说明和论述，本文的创新点主要有一下几个方面： ( 1 ) 免疫进化模型：模仿了人体免疫系统的b 细胞抗体进化过程，抗体 通过克隆、超变异来消灭抗原，本文构造了克隆算子和超变异算子。提高了 进化速度。 ( 2 ) 一维的路径编码机制：现在大多采用二维的路径编码，x 和y 坐标 都需要进行优化，本文通过需要精度和障碍物间距将x 。长度n 等分，进行 y 坐标优化，简化为一维坐标优化，减少了计算量。 ( 3 ) 混沌变异算子：根据混沌理论构造了混沌变异算子，使优化的y 值 具有全局最优性，有利于全局路径规划。较大的变异有利于提高种群的多样 性，提高了算法后期的收敛速度。 ( 4 ) 小生境技术( 双群) 进化：双群进化有效的防止了进化的早熟现 象 ( 5 ) 递减的高斯变异算子和免疫算予：他们都提高了局部路径规划的效 率，提高了局部路径规划的精度，有利于提高算法的收敛速度。 免疫算法作为一种新兴的仿生算法，具备许多特有的优点，如全局优化、 鲁棒性好，易于并行处理、智能度高等免疫算法已获得较的应用，必将成 为网络、智能、控制、计算等领域研究的重点和热点之一。本文给出了免疫 算法的定义和概念，总结了免疫算法的发展史，比较了不同免疫算法设计的优 劣，既从传统计算的流程图、复杂性等方面对其进行了分析，也从自然计算的 角度讨论了免疫算法，并举例说明了免疫算法的应用，探讨了免疫算法的未来 应用领域。最后对免疫算法发展的难点和重点进行了探讨，展望了免疫算法 的美好前景，为免疫算法的研究提供了一些经验性的建议和预见。 哈尔滨理t 大学t 学硕十学位论文 2 1 前言 第2 章移动机器人路径规划技术 移动机器人路进规划技术按其规划方式不同可以分为：基于地图的规划 方法【“h ”l 、基于环境建模的规划方法【3 6 l 【”1 1 3 ”、基于行为的规划方法【3 9 j 三种 类型。 路径规划技术是智能机器人领域中的核心问题之一，也是机器入学中研 究人工智能