（控制科学与工程专业论文）基于免疫遗传算法的移动机器人路径规划研究.pdf

中南大学硕十论文摘要 摘要 遗传算法是一种进化计算技术，也是一种基于叠代的工具。系统 初始化为一组随机解，通过叠代搜寻最优值。目前已广泛应用于函数 优化、神经网络训练、模糊系统控制以及其他应用领域。显示出遗传 算法在求解复杂问题方面的优越性。 本文综述了遗传算法的产生和发展历程，详细阐述了其生物学机 理；介绍了基本遗传算法的原理、特点、实施；同时针对遗传算法存 在的一些缺点，列举了当前的一些典型的遗传算法改进算法，对其在 各领域的应用做了简要的叙述，并在遗传算法的基础上提出了一种改 进的新算法免疫遗传算法。同时综述了机器人的起源与发展历 程，展望了未来机器人的发展方向智能机器人。智能机器人中最 重要的一个研究课题是移动机器人的路径规划，在文中详细地说明了 移动机器人路径规划的一般概念、特点、分类及其进行路径规划的一 些基本问题以及几种常见的路径规划方法。 在此基础上，本文结合移动机器人路径规划的特点，提出了基于 带精英保留的免疫遗传算法的移动机器人全局最优路径规划方法。该 算法很好的解决了遗传算法存在的一些问题，主要有早熟收敛、容易 陷入局部最优、局部搜索能力较弱、收敛速度慢等。基于精英保留免 疫遗传算法的移动机器人全局最优路径规划方法分为二步：第一步是 利用栅格法建立移动机器人的自由空间模型，第二步是采用免疫遗传 算法为机器人搜索出一条全局最优路径。我们已经对所提出的算法进 行了计算机仿真，通过结果对比，证实了本文所提出的方法无论是在 收敛速度，还是在动态收敛特征方面都比基于基本遗传算法移动机器 人全局路径规划方法更好。 关键字移动机器人，免疫遗传算法，栅格法，路径规划 中南大学硕十论文a b s t r a c t a bs t r a c t g e n e t i ca l g o r i t h m ( g a ) i sak i n do fn o v e l t ye v o l u t i o na l g o r i t h ma n d g aa l s oi sa p o p u l a t i o nb a s e do p t i m i z a t i o nt 0 0 1 t h es y s t e mi si n i t i a l i z e d w i t hap o p u l a t i o no fr a n d o ms o l u t i o n sa n ds e a r c h e sf o r o p t i m ab y u p d a t i n gg e n e r a t i o n s g ah a sb e e ns u c c e s s f u l l ya p p l i e di nm a n ya r e a s ： f u n c t i o no p t i m i z a t i o n ，a r t i f i c i a ln e u r a ln e t w o r kt r a i n i n g ，f u z z ys y s t e m c o n t r o l ，a n do t h e ra r e a s i t ss u p e r i o r i t yi ns o l v i n gc o m p l e xp r o b l e mh a s b e e nm a n i f e s t e d t h e o r i g i na n dt h ed e v e l o p m e n to f g e n e t i ca l g o r i t h ma r eo u t l i n e di n t h i sp a p e r ：t h ep r i n c i p a l ，t h eb i o l o g i c a lm e c h a n i s m s ，t h ec h a r a c t e r i s t i c s a n dt h ea p p l i c a t i o no ft h eg aa r ep r e s e n t e d ，m e a n w h i l e ，s o m ec l a s s i c a l i m p r o v e dg a t om a k eu pf o rt h es h o r t c o m i n g so fg aa n di t sw i d e s p r e a d a p p l i c a t i o n s h a v eb e e ni n t r o d u c e d o nt h eb a s i so ft h a t ，an e w m e t h o d 一一i m m u n eg e n e t i ca l g o r i t h mb a s e do ng aw a sp r o p o s e d t h e o r i g i na n dt h ed e v e l o p m e n to fm o b i l er o b o ta r ea l s oo u t l i n e di nt h i sp a p e r t h em o b i l er o b o t sp r o s p e c ta s p e c ti nt h ef u t u r e 一- i n t e l l i g e n tr o b o th a s b e e np r e s e n t e d t h ep a t hp l a n n i n gf o rm o b i l er o b o t si st h em o s ti m p o r t a n t a s p e c t o fi n t e l l i g e n tr o b o t t h e g e n e r a lc o n c e p t i o n s ，c h a r a c t e r i s t i c ， c l a s s i f yb a s e di s s u ea n ds o m ef a m i l i a rm e t h o d so fp a t hp l a n n i n ga r e p r e s e n t e d o nt h eb a s i so fg a ，a c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h ep a t h p l a n n i n go fm o b i l er o b o t si nt h es t a t i ce n v i r o n m e n t ，an e wm e t h o d - i m m u n eg e n e t i ca l g o r i t h mw i t he l i t i s m ( i g a e ) - 一w a sp r o p o s e d t h i s m e t h o di su s e dt os e t t l es o m em a jo rd r a w b a c k so fg as u c ha sp r e m a t u r e ， s t i c k st ol o c a lo p t i m u me a s i l y , l o wl o c a ls e a r c ha b i l i t ya n ds l o ws p e e do f c o n v e r g e n c e t h ep a t hp l a n n i n go f m o b i l er o b o t sb a s e do ni g a ei n c l u d e s t w os t e p s ：t h ef i r s ts t e pi sa d o p t i n gt h eg r i dt h e o r yt oe s t a b l i s ht h ef r e e s p a c em o d e l o ft h em o b i l er o b o t ；t h es e c o n ds t e pi sa d o p t i n gt h ei m m u n e g e n e t i ca l g o r i t h mt of i n do u tt h eg l o b a lo p t i m a lp a t h t h ec o m p u t e r s i m u l a t i o ne x p e r i m e n tw a sc a r r i e do u t b yc o m p a r i n gw i t ht h ep a t h p l a n n i n gm e t h o db a s e do nt h eg a ，i th a sb e e nc o n f i r m e dt h a tt h ei g a e h a sb e t t e rp e r f o r m a n c ei n c o n v e r g e n c es p e e d ，d y n a m i cc o n v e r g e n c e b e h a v i o r i i 中南大学硕士论文a b s t r a c t k e yw o r dm o b i l er o b o t ，i m m u n eg e n e t i ca l g o r i t h mw i t he l i t i s m ， g r i d ，p a t hp l a n n i n g i i i 原创性声明 本人声明，所呈交的学位论文是本人在导7 i l j j s l 导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特另i d i l 以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：缢亟日期：尘堕年三月生日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：鱼叠导师签名弛期：堕年月单日 中南大学硕：论文第一章绪论 第一章绪论 1 1 引言 机器人的诞生、机器人学的建立和发展是本世纪自动控制最具说服力的成 就，是2 0 世纪人类科学技术进步的重大成就。机器人从爬行到学会两腿直立行 走，仅仅只花了2 0 年，而人类的这一过程则经历了上百万年。现在全世界己经 拥有将近1 0 0 力台机器人，有近万家工厂在生产机器人，销售额每年增长2 0 以上，机器人工业和技术得到了前所未有的飞速发展。机器人己经能够使用工具、 能看、能听、能说，并且开始能进行一些决策和思考的智能行为。其应用也从传 统的加工制造业逐渐扩展到军事、海洋探测、宇宙探索等领域，并开始进入家庭 和服务行业。作为一种先进的机电一体化产品，机器人技术的发展与自动控制技 术的发展息息相关。自动控制系统是机器人的中枢神经，它控制着机器人的思维、 决策和行为。几乎所有的自动控制技术都在机器人的控制上得到过应用。近些年 来，智能控制的发展十分迅速，这必然将促使机器人的智能化水平达到一个新的 高度1 。3 1 。 机器人是关键的自动化技术之一，机器人学的研究和发展成为热点的原因在 于：( 1 ) 机器人的应用可增加生产力，提高生产过程的效益，如机器人焊接、零 件装配、物体搬运等；( 2 ) 机器入可以在恶劣环境和人类不可及环境中代替人类 完成期望的工作，如军事侦察、扫雷排险、防核化污染、宇宙空间的开发研究等。 因此，机器人的应用越来越广泛，几乎渗透到所有领域。 移动机器人是机器人学中的一个重要分支，早在6 0 年代，工程界就己经开 始了关于移动机器人的研究。关于移动机器人的研究涉及许多方面，具体可以分 为以下几个方面： 1 首先，移动方式的研究，可以是轮式的、履带式的、腿式( 单腿式、双腿 式和多腿式) 的，对于水下机器人，则是推进器； 2 其次，驱动器的控制研究，以使机器人按期望的方式运动； 3 第三，导航或路径规划的研究，对于后者，需要考虑更多的方面，如传 感器信息融合、特征提取、避障及环境映射等。 因此，移动机器人是一个集环境感知、动态决策与规划、行为控制与执行等 多种功能于一体的综合系统。目前，移动机器人的研究出现了许多新的、挑战性 的理论与工程课题，引起越来越多的专家、学者和工程技术人员的兴趣。 1 2 移动机器人的发展现状 现代机器人从其诞生到现在，已经发展到了第三代： 中南大学硕十论文第一章绪论 第一代机器人是示教再现型机器人。它装有记忆存储器，由人将作业的各种 操作要求示范给机器人，使之记住操作的程序和要领。当它接到再现命令时，则 自主地再现示教的动作。 第二代机器人是装有小型计算机和简单传感器的离线编程的工业机器人。它 能感知外界信息和进行“思维”，比第一代机器人更灵活，更能适应环境变化的 需要。 第三代是智能机器人。智能机器人是“具有感知、思维和动作的机器”。它 装有多种传感器，能识别作业环境，能自主决策，具有人类大脑的部分功能，且 动作灵活，是人工智能技术发展到高级阶段的产物。 从2 0 世纪8 0 年代开始，美国国防高级研究计划局( d a r p r ) 专门立项，制 定了地面无人作战平台的战略计划，从此，全世界开始了对移动机器人的全面研 究。初期的研究，主要从学术角度研究室外移动机器人的体系结构和信息处理， 并建立实验系统进行验证。虽然由于8 0 年代对机器人的智能行为期望过高，导 致室外移动机器人的研究未达到预期的效果，但却带动了相关技术的发展，为探 讨人类研制智能机器人的途径积累了经验，同时也推动了其它国家对移动机器人 的研究与开发。 进入9 0 年代，随着技术的进步，移动机器人开始在更现实的基础上，开拓 各个应用领域，向实用化进军。例如美国n a s a 资助研制的“丹蒂 八足行走 机器人。这是一个能提供对高移动性机器人运动的了解和远程机器人探险的行走 机器人。它于1 9 9 4 年在斯帕火山的火山口中进行了成功的演示，虽然在返回时， 在一条陡峭、泥泞的路上失去了稳定性，倒向了一边，但作为指定的探险任务早 己完成。德国也在商业轮椅的基础上研制了一种轮椅机器人，并在乌尔姆市中心 车站客流高峰期的环境和1 9 8 8 年汉诺威工业商品博览会的展览大厅环境中进行 了实地现场表演。该轮椅机器人在公共场所拥挤的、有大量乘客的环境中，进行 了超过3 6 个小时的考验，所表现出的性能是其它现有的轮椅机器人或移动机器 人不可比的。 除室外移动机器人外，世界各国在遥控移动机器人、高完整性机器人、生态 机器人学( 生物机器人学) 、多机器人系统、环境与移动机器人系统的集成等方面 都作了大量的研究。 国内在移动机器人的研究起步较晚，大多数研究尚处于某个单项研究阶段。 清华大学智能移动机器人【4 】于1 9 9 4 年通过鉴定，涉及到五个方面的关键技术： 1 基于地图的全局路径规划技术研究( 准结构道路网环境下的全局路径规 划、具有障碍物越野环境下的全局路径规划、自然地形环境下的全局路径规划) ； 2 基于传感器信息的局部路径规划技术研究( 基于多种传感器信息的“感知 2 中南大学硕十论文第一章绪论 动作 行为、基于环境势场法的“感知动作”行为、基于模糊控制的局 部路径规划与导航控制) ； 3 路径规划的仿真技术研究( 基于地图的全局路径规划系统的仿真模拟、室 外移动机器人规划系统的仿真模拟、室内移动机器人局部路径规划系统的仿真模 拟) ； 4 传感技术、信息融合技术研究( 差分全球卫星定位系统、磁罗盘和光码盘 定位系统、超声测距系统、视觉处理技术、信息融合技术) ； 5 智能跟踪控制是移动机器人运动控制的一个重要问题，也是一个非常实际 的问题。分为轨迹跟踪控制和路径跟踪控制两种。在轨迹跟踪控制中，移动机器 人要求跟踪的期望轨迹是以时间关系曲线图给出的；而在路径跟踪控制中，期望 轨迹是由方便的几何参数( 如路径的弧长) 来描述的。当要求机器人必须在一个特 定的时间内到达一个特定的点时，轨迹跟踪控制是必需的；当要求机器人以一个 期望的速度跟踪一条由几何参数给出的路径时，路径跟踪控制是合适的。已有的 轨迹跟踪方法在数学上很精致，并且得到许多有意义的结果，但对于设计跟踪控 制器来说，并不是最好的方法。事实上，在传统的自动化应用中，常常采用基于 几何路径跟踪概念的方法，控制器的设计更与人的直觉接近，并简单，易于实现。 关于这方面的工作，主要集中在早期。近期主要集中在考虑非完整约束和力学的 情况下，如何实现有效跟踪。 1 3 移动机器人研究的基本内容 一个理想化完善的移动机器人系统通常由3 个部分组成：移动机构、感知系 统和控制系统。移动机构是服务机器人的本体，决定机器人的运动空问，有步行 机构、轮式机构摄像机、激光测距仪、履带式机构和混合机构等几种。感知系统 一般采用c c d 超声测距仪、接触和接近传感器、红外线传感器和雷达定位传感 器等。随着计算机技术、人工智能技术和传感技术的迅速发展，移动式服务机器 人控制系统的研究具备了坚实的技术基础和良好的发展前景。服务机器人的控制 与工作环境的有关信息往往是多义的、不完全的或不准确的，还可能随着时间而 改变。因此在部分己知或未知的环境中同时又要求自主执行任务时，应以最大的 人员安全性及功能可靠性为条件，用传感器探测环境、分析信号，以及通过适当 的建模方式来理解环境，具有特别重要的意义。近年来对智能机器人的研究表明， 对于工作在复杂或非结构化环境中的自主式移动机器人，要进一步提高其自主程 度，主要依靠模式识别及障碍物识别，实时数据传输及适当的人工智能方法，还 要进一步开发全局模型，从而为机器人获取全局信息。目前发展较快、对移动机 器人的发展影响较大的关键技术是：传感技术、智能控制技术、路径规划技术、 电源技术等。 中南大学硕上论文第一章绪论 移动机器人的智能指标为适应性、自主性和交互性。适应性是指机器人具有 适应复杂工作环境的能力( 主要通过学习) ，不但能识别和测量周围的物体，还有 理解周围环境和所要执行任务的能力，并做出正确的判断及操作和移动等能力。 自主性是指机器人能根据工作任务和周围环境情况，自己确定工作步骤和工作方 式。交互性是智能产生的基础，交互包括机器入与环境、机器人与人及机器人之 间三种，主要涉及信息的获取、处理和理解。针对这些指标，移动机器人的研究 领域主要包括以下几个方面： 1 导航 移动机器人的导航方式可分为：基于环境信息的地图模型匹配导航、基于各 种导航信号的陆标导航、视觉导航和味觉导航等。 环境地图模型匹配导航是机器人通过自身的各种传感器，探测周围环境，利 用感知到的局部环境信息进行局部地图构造，并与其内部事先存储的完整地图进 行匹配。如两模型相互匹配，机器人可确定自身的位置，并根据预先规划的一条 全局路线，采用路径跟踪和避障技术，实现导航。它涉及环境地图模型建造和模 型匹配两大问题。 陆标导航是事先将环境中的一些特殊景物作为陆标，机器人在知道这些陆标 在环境中的坐标、形状等特征的前提下，通过对陆标的探测来确定自身的位置。 同时将全局路线分解成为陆标与陆标间的片段，不断地对陆标探测来完成导航。 根据陆标的不同，可分为人工陆标导航和自然陆标导航。人工陆标导航是机器人 通过对人为放置的特殊标志的识别实现导航，虽然比较容易实现，但它人为地改 变了机器人工作的环境。自然陆标导航不改变工作环境，是机器人通过对工作坏 境中的自然特征的识别完成导航，但陆标探测的稳定性和鲁棒性是研究的主要问 题。 视觉导航主要完成障碍物和陆标的探测及识别。t r a h a n i a s 利用视觉探测陆 标来完成机器人导航。其中陆标不是事先定义的人工陆标，而是在学习阶段自动 抽取的自然陆标。视觉导航中边缘锐化、特征提取等图像处理方法计算量大，实 时性差始终是一个瓶颈问题。解决该问题的关键在于设计一种快速的图像处理方 法。s t a n l e y 提出了基于神经网络的机器人视觉导航技术。该技术中估算逆雅可 比矩阵是基于视觉导航的一个关键问题。它将图像特征的变化与机器人的位置变 化对应起来，通过神经网络训练来近似特征雅可比矩阵的逆阵。该技术，通过提 取几何特征、平均压缩、向量量化和主成分提取来简化图像处理，实现实时视觉 导航。 味觉导航是通过机器人配备的化学传感器感知气味的浓度，根据气味的浓度 和气流的方向来控制机器人的运动。由于气味传感器具有灵敏度高、响应速度快 4 中南大学硕士论文第一章绪论 以及鲁棒性好等优点，近年来许多研究人员在气味导航技术土做了许多研究工 作。但该项技术能够真正应用到实际环境中的却很少，仍处于试验研究阶段。 f i g a r oe n g i n e e r i n gi n c 公司研制的氧化锡气味传感器，被广泛用于气味导航试验。 石英晶体微平衡气味传感器、导电聚合物气味传感器和一种模仿哺乳动物鼻子功 能的电子鼻等用于移动机器人味觉导航的传感器都处于试验阶段。目前的味觉导 航试验多采用将机器人起始点和目标点之间用特殊的化学药品，如酒精和樟脑丸 等，引导出一条无碰气味路径，机器人根据不同的道路跟踪算法，用气味传感器 感知气味的浓淡和气味源的方向进行机器人导航试验。味觉导航的研究具有很好 的研究价值，该种移动机器人可用来寻找化学药品泄露源。 2 定位 作为移动机器人导航最基本环节，定位是确定机器人在二维工作环境中相对 于全局坐标的位姿。定位方法根据机器人工作环境复杂性，配备传感器的种类和 数量等不同有多种方法。主要方法有：惯性定位、陆标定位和声音定位等。惯性 定位是在移动机器人的车轮上装有光电编码器，通过对车轮转动的记录来粗略地 确定位置和姿态。该方法虽然简单，但是由于车轮与地面存在打滑现象，产生的 累积误差随路径的增加而增大，定位误差会逐渐累积，引起更大的误差。y a m a u c h i 使用推测航行法和证据栅格柬实现动态环境中的机器人位置。该方法把在不同时 段建立的证据栅格匹配起来，使用一种爬山算法搜索可能的平移与转动空间，来 消除推测航行法的误差累积；陆标定位在移动机器人工作的环境里，人为地设置 一些坐标己知的陆标，如超声波发射器、激光反射板等，通过对陆标的探测来确 定自身的位姿。 三角测量法是陆标定位常用的方法，机器人在同一点探测到三个陆标，并通 过三角几何运算，可确定机器人在工作环境中的坐标。陆标定位是普遍采用的方 法，可获得较高的定位精度且计算量小，可用于实际的生产中。但该法需要对环 境作一些改造，不太符合真j 下意义的自主导航：声音定位用于物体超出视野之外 或光线很暗时，视觉导航和定位失效的情况之下。基于声音的无方向性和时间分 辨率高等优点，采用最大似然法、时空梯度法和m u s i c 法等方法可实现机器人 的精确定位。 3 路径规划 未来的机器人应该具有感知、规划和控制等高层能力。它们能从周围的环境 中收集知识，构造一个关于环境的符号化的世界模型，并使用这些模型来规划、 执行由应用者下达的高层任务。其中的规划模块能生成大部分的机器人要执行的 命令，其目标是实现机器人的使用者在较高的层次给机器人下达一些较宏观的任 务，由机器人系统自身来填充那些较底层的细节问题。因此路径规划是规划模块 中南大学硕士论文第一章绪论 中的一个重要组成部分。 移动机器人路径规划问题可以如下定义：在有障碍物的工作环境中，寻找 条从给定起点到终点的适当的运动路径，使机器入在运动过程中能安全、无碰撞 地绕过所有的障碍物。 路径规划是移动机器人导航中最重要的任务之一。路径规划技术是移动机器 人研究领域中的一个重要分支。所谓机器人的最优路径规划问题，就是依据某个 或某些优化准则( 如工作代价最小、行走路线最短、行走时间最短等) ，在其工作 空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径 规划问题可以建模为一个有约束条件的连续函数优化问题，要完成路径规划、定 位和避障等任务。路径规划主要涉及的问题包括：利用获得的移动机器人环境信 息建立较为合理的模型，再用某种算法寻找一条从起始状态到目标状态的最优或 近似最优的无碰撞路径；能够处理环境模型中的不确定因素和路径跟踪中出现的 误差，使外界物体对机器人的影响降到最小；如何利用己知的所有信息来引导机 器人的动作，从而得到相对更优的行为决策。 移动机器人路径规划是机器人应用中的一项重要技术，例如，在执行装配、 焊接及抢险救灾等任务时，采用良好的移动机器人路径规划技术可以节省大量机 器人作业时间、减少机器人磨损，同时也可以节约人力资源，减小资金投入，为 机器人在多种行业中的应用奠定良好的基础。将遗传算法、模糊逻辑以及神经网 络等方法相结合，可以组成新的智能型路径规划方法，从而提高机器入路径规划 的避障精度，加快规划速度，满足实际应用的需要。同时，多机器人协调作业环 境下的路径规划技术也将是研究的热点及难点问题，越来越受到人们的重视。由 于障碍物及机器人数目的增加，极大地增加了路径规划的难度，引入可以优化约 简知识的粗糙集理论，简化规划条件，提取路径规划特征参数，有可能进一步解 决诸如机器人路径规划速度等难题，因此，这将是一个有意义的研究课题。 近年来，移动机器人技术在工业、农业、航天及空间探测等许多领域都起到 了重要的作用，同时又显示了广泛的应用前景，因而成为国际机器入学术界研究 和关注的热点问题。目前，对于移动机器人路径规划技术的研究已经取得了大量 的成果，许多问题获锝了比较满意的答案。 1 4 本文主要研究内容 上面主要从移动机器人的起源、发展以及研究的基本内容做了简单的介绍。 下面主要从移动机器人路径规划问题上做深入的研究，包括移动机器人的导航与 定位，路径规划的概念、特点、分类以及规划算法的分类。提出了一种改进于遗 传算法的新算法免疫遗传算法。并提出了一种基于免疫算法的机器人路径规划 方法，该方法采用栅格法建立环境模型，用免疫遗传算法直接搜索到一条全局最 6 中南大学硕士论文 第一章绪论 优路径，该方法建模容易，算法参数少，很容易实现。通过与基本遗传算法进行 比较，说明了该改进算法在收敛速度、解的波动性、动态收敛特征及计算效率上 都优于基于基本遗传算法的机器人全局路径规划。本文主要内容如下：第一章主 要介绍了机器人的发展和起源、以及移动机器人几个基本研究领域；第二章主要 讲了移动机器人路径规划的研究和发展，移动机器人路径规划中的几个子问题， 移动机器人路径规划的相关基本概念、基本问题，后面重点介绍几种传统路径规 划方法和智能路径规划方法，并介绍了本文所提出的路径规划方法；第三章介绍 了基本遗传算法：包括遗传算法的起源、发展，遗传算法的生物学机理，遗传算 法的理论基础、特点以及遗传算法的实施；第四章针对第三章提出的基本遗传算 法存在的一些缺陷，介绍了当前应用比较广泛的一些改进的遗传算法及其在实际 中的应用，并提出了一种改进于遗传算法的新算法一免疫遗传算法；第五章根据 移动机器人路径规划的特性，提出了基于免疫遗传算法的移动机器入全局最优路 径规划方法，采用栅格法进行环境建模，用免疫遗传算法直接从中找出一条全局 最优路径，并进行了仿真试验，对在不同的环境中进行仿真，并将免疫遗传算法 与基本遗传算法进行了比较分析，仿真结果表明基于免疫遗传算法的路径规划方 法要优于基于基本遗传算法的路径规划方法；第六章指出了在基于免疫遗传算法 的机器人路径规划中，今后需要更深入的讨论的问题，以及未来的发展前景。 7 中南大学硕：论文第二章移动机器人路径规划技术 第二章移动机器人路径规划技术 2 1 路径规划概述 随着机器人在工业领域的应用越来越广泛，人们对机器人的“智能 的要 求也在提高，要求机器人在运动过程中具有与周围环境交互的能力。其中一个最 基本的需求就是能规划出避碰的运动路径，这种需求即为路径规划问题。路径规 划技术是智能机器人领域中的核心问题之一，也是机器人学中研究人工智能问题 的一个重要方面，在一定程度上标志着水下机器人智能水平的高低。 2 1 1 路径规划问题的描述 移动机器人的导航问题主要是由d u r r a n t w h y t ehf 提出的三个问题 ( 1 ) “我现在何处? ”( 2 ) “我要往何处去? ( 3 ) “要如何到该处去? ”路径规划 是移动机器人导航中的最重要的任务之一，它被描述成：给定一个移动机器人所 处的环境( 环境可以通过移动机器人视觉系统或其他途径获得) ，一个起始点和一 个期望的目标点，机器人路径规划根据一定的任务要求，寻求一条连接起始点到 终点且能避丌环境中障碍物的运动轨迹，即最优或次优有效路径。蒋新松在文献 【5 】中为路径规划做出了这样的定义：路径规划是自治式移动机器人的一个重要组 成部分，它的任务就是在具有障碍物的环境内，按照一定的评价标准，寻找一条 从起始状态( 包括位置和姿态) 到达目标状态( 位置和姿态) 的无碰路径。 j t s c h w a r t z 和m s h a i r i 6 j 对机器人的运动规划是这样描述的：设r 是一个 机器人系统，它是由一系列刚体性质的部件互相连接( 或不连接，即多机器人系 统) 而成，总共有k 个自由度。假设r 可在2 维或3 维的工作空间】，中，在不破 坏自身运动约束的情况下自由运动；同时，在工作空间中有一系列几何参数己知 的障碍。路径规划是指对给定的一个初始位形z 1 和一个目标位形z 2 ( 位形是指 能完全确定机器人系统状态的机器人的位置和姿态) ，要求求解一个机器人系统 r 的连续动作，使之无碰地从z 1 运动到z 2 。 需要指出的是，路径规划( p a t hp l a n n i n g ) 不同于轨迹规划( t r a j e c t o r y p l a n n i n g ) ，路径规划一般只给出机器人在几何意义上的位置和转角的值，而轨迹 规划同时还要考虑机器人的线速度和角速度。因此，路径规划问题可以看作是轨 迹规划问题的一个子集，它忽略了机器人的动力学特性。 机器人路径规划问题在理论上主要存在三个子问题1 7 j ： ( 1 ) 环境表示问题：指环境中障碍物的表示和自由空问的表示。环境建模就 是对机器人活动空问的有效描述。机器人在规划前首先要做的就是将环境的描述 由外部的原始形式通过一系列处理转化为适合规划的内部的世界模型，这个过程 8 中南人学硕十论文第- 二章移动机器人路径规划技术 我们称为环境建模，其中主要是障碍物的表示方法。合理的环境表示才能有利于 规划中搜索量的减少，才能有利于时空开销的减少。不同的规划方法是基于各种 不同的环境建模来进行的。 ( 2 ) 寻空间问题：在某个指定区域尺中，确定物体么的安全位置，使它不与 己有的其它物体8 j ( j = l ，2 ，m ) 相碰。 ( 3 ) 寻路径问题：在某个指定区域r 中，确定物体彳从初始位置移动到目标 位置的安全路径，使得移动过程中不发生a 与研的碰撞。一系列安全位置就可 以构成安全路径。 解决路径规划问题的关键在于设计一种恰当的环境模型表示方法，即一种数 据结构。该结构能反映出机器人在某位置上发生碰撞的可能性。然后，按照模型 中的连通性构造与之对应的可连通图。该连通图仅抽取环境模型的连通性，忽略 掉与路径规划不相干的信息，避免了因无关信息的引入使规划复杂化，这种连通 图构成了问题状态空间。在该状态空间内利用搜索技术进行搜索，便求解出一条 通路。将通路上的节点转化为实际模型中的表示形式( 如坐标点的序列) ，便得到 了机器人的无碰路径。 2 1 2 路径规划的分类及特点 大多数导航系统由两级规划组成，即局部规划( l o c a lp l a n n i n g ) 和全局规划 ( g l o b a lp l a n n i n g ) 。前者主要解决机器人定位和路径跟踪问题，而后者主要解决 全局目标分解成局部目标，再由局部规划实现局部目标。根据环境信息的完整程 度，移动机器人路径规划问题可分为两种【8 1 ：一种是基于先验完整信息的全局路 径规划，又称静态规划；另一种是基于传感器信息的局部路径规划，又称动态规 划，后者环境是未知或部分未知的。 路径规划问题己有的研究方法可以分为全局型方法、局部型方法以及混合型 方法三种。 全局规划方法依照己获取的环境信息，给机器人规划出一条路径。规划路径 的精确程度取决于获取环境信息的准确程度。全局方法通常可以寻找最优解，但 是需要预先知道环境的准确信息，并且计算量很大。 局部规划方法侧重于考虑机器人当前的局部环境信息，让机器人具有良好的 避碰能力。很多机器人导航方法通常是局部的方法，因为它的信息获取仅仅依靠 传感器系统获取的信息，并且随着环境的变化实时的发生变化。和全局规划方法 向比较，局部规划方法更具有实时性和实用性。缺陷是仅仅依靠局部信息，有时 会产生局部极点，无法保证机器人能顺利到达目的地。 混合型方法试图结合全局和局部的优点，将全局规划的“粗”路径作为局部 规划的子目标。从而引导机器入最终找到目标点。 9 中南大学硕士论文第二章移动机器人路径规划技术 路径规划问题的研究涉及到环境表达、规划方法、路径执行。环境表达有两 层含义，其一是有效的获取环境信息，这与视觉传感器相关；其二是如何将环 境信息有效地表达出来。规划方法关心的是在环境表达的基础上，采用有效的方 法规划路径并且进行优化。路径的执行与底层控制密切相关，并且考虑机器人的 动力学特性，控制机器人按照设定的路径行走。 按照障碍物的稀疏可把路径规划问题划分成粗规划和细规划。前者考虑问题 时所涉及到的自由空间远大于机器人的尺寸与机器人定位误差的和。后者考虑在 狭窄空间下的规划问题，它所要求的移动精度高于机器人定位误差的精度。 按照环境的特点，路经规划问题可分为“时变 规划问题和“时不变 规划 问题。当环境或障碍物的位置可以发生改变时，称之为“时变”规划问题，否则称 为“时不变”规划问题。如果机器人可以移动一部分障碍物，又称为“可移障碍物” 规划问题。 另外，根据完整性还可以把路径规划算法分为确定型和启发型两类。确定型 算法可以找到一个问题的答案，除非它证明该问题无解。启发型算法致力于在较 短的时间内找出问题的答案，它可能无法解决较困难的问题或无法给出一个问题 的最优解。 路径规划问题具有如下特点： ( 1 ) 复杂性：在复杂环境尤其是动态时变环境中，机器人路径规划非常复杂， 且需要很大的计算量。 ( 2 ) 随机性：复杂环境的变化往往存在很多随机性和不确定因素。动态障碍 物的出现也带有随机性。 ( 3 ) 多约束：机器人的运动存在几何约束和物理约束。几何约束是指机器人 的形状制约，而物理约束是指机器人的速度和能量等。 ( 4 ) 多目标：机器人运动过程中路径性能要求存在多种目标，如路径最短， 时间最优，安全性能最好，能源消耗最小。但这些目标之间往往存在冲突。 2 2 机器人路径规划的基本问题 这一节讨论机器人路径规划问题所要涉及到的基本问题。这包括位姿空间、 对象的表示、搜索方法运动的局部最优化等。路径规划大体可以分成这样几个步 骤。一，确定机器人的位姿参数( 也即找出机器人的运动的自由度) 。位姿空间的 概念是路径规划中最基本的概念，因为它是机器人所有可能的运动位姿的集合。 我们对位姿空间的概念给出详细的解释。二，机器人和障碍物都要用适当的方法 表示出来。三，需要选择一个搜索方法来找出一条路径。最后，需要修正路径使 得路径的光滑程度能够满足要求。 1 0 中南人学硕十论文第二章移动机器人路径规划技术 2 2 1 世界空间到位姿空间中的转换 世界空间是指机器人所在的物理空间。一个物体或者机器人的位姿是能够描 述物体或者机器人上的每一个点的相互独立的一些参数。位姿空间是一个物体运 动过程中所有可能的位姿的集合，在机器人的路径规划中起到一种基础的作用。 它第一次是在l o z a n o p e r e z 和w e s l e y 的奠基性的文章中首次提出来的。实际上， 所有机器人的路径规划问题被转换为位姿空问中时它们都是等价的。在位姿空间 中它们都转化成为寻找连接初始位姿到终止位姿的一系列的连接的点。位姿空问 的维数是描述一个位姿的参数的个数，也称之为自由度。 对于一个点式机器人，它的位姿空间和世界空间是等价的，并且都具有相同 的维数。例如，在平面上的一个多边形的位姿空间有三个自由度，其中的两个用 于描述多边形的位置，另一个用于描述多边形的方向。 位姿空间中所有与障碍物相碰的机器人的位姿的集合称为位姿障碍物。位姿 障碍物中的一个点对应于一个机器人与一个或多个障碍物相重叠( 这在现实的物 理世界空间中是不可z h 匕l - , 的) 的机器人的位姿。位姿障碍物边界上的一个点对应于 机器人恰恰接触到一个或多个障碍物的情况。 使机器人路径规划问题复杂化的主要因素是机器人位姿空间中的维数。对于 一个三维空间中的刚体机器人，其位姿空间的维数是6 维空间。如果对每一个维 数我们用1 0 个点来对这个一维空间进行分割的话，那么我们就会得到一个由1 0 1 2 个点组成的栅格。对于一个多机器人的系统用划分栅格的方法是不可能的。而位 姿空间中的障碍物一般都不能很容易的表示出来，所以机器人的路径规划问题是 一个富于挑战性的研究课题。 2 2 2 位姿空间的计算方法 对于位姿空间中的障碍物，我们有这样几种方法。即点验证式方法、 m i n k o w s k i 差集方法、边界方程方法以及降维分割方法等等。点验证式方法是这 罩最简单的方法。对于位姿空间中的所有的点，将机器人按照该点的位姿放置于 世界空间，如果机器人与障碍物相碰，则该点属于位姿空间的障碍物。否则它不 属于位姿空间中的障碍物。 集合4 和b 的m i n k o w s k i 差集定义为所有a 中的元素与b 中的元素的差构成 的集合。用符号表示艮0 m d i f ，b ) = ( 柚副，) 。对于一个不旋转的刚体 来说，其位姿空间中的障碍 ( a 物就是机器人a 占有b 的e 区b 域与障碍物占有的区域的 m i n k o w s k i 差集。 用边界方程表示就必须推导出位姿空间中的参数在机器人与障碍物相接触 时的约束方程。这些约束方程定义的位姿空间中的障碍物的边界。利用这些约束 公式很容易判断位姿空间中的一个点是否属于位姿空间中的障碍物。但是将位姿 中南大学硕，i ：论文第一二章移动机器人路径规划技术 空间中的障碍物表示成半代数集合的并集是非常困难的。特别是当位姿空间中的 维数大于3 时。 在降维分割方法中，先让位姿空间的参数固定，然后让一个参数变化，这就 变成一个一维的问题，计算出在这个一维空间中所有与位姿空间中的障碍物相碰 的位姿。这样可以计算出一些小区问。这些小区间中的任何一点都属于位姿障碍 物。这种方法一般只适用于位姿空间的维数是2 时的情况，对于高维的情况就不 适用。 2 2 3 物体信息的获取和表示 机器人在规划出一条路径之前必须将其环境中的障碍物的模型搞清楚。在一 个未知的环境或者是动态的环境中，机器人就要在极其短暂的时问间隔内对其周 围的障碍物进行探察。一般用视觉传感器，立体摄像机，或者基于声纳，红外线 和激光的范围传感器。这些传感器可以给出一个场景深度图，这些数据一般都通 过变换转换成简单的多面体的表示形式用以节省存储空间和减少以后计算过程 的计算量。但在一个熟知的环境中，如装配机器人系统世界空间中的各个部件都 是事先知道的( 有些是直接的c a d 的数据) 。这些数据都是从一些基本形体交与 并和构成的形体，一般用边界表示( b r e p ) 的形式给出。在这种情况下，传感器 只需要给物体的位置和方向定位。 当我们获得了物体的形状和位姿的信息，它们就可以用各种方法表示出来。 常用的方法是栅格，四叉树，八叉树，多面体，构造性的刚体几何( c s g ) ，以及 边界表示( b r e p ) 。这些方法可以被用来表示世界空间中或者位姿空间中的物体。 栅格实际上就是一系列的规则的单元。如果一个栅格被障碍物所占据则标记 这个栅格为1 。否则标记这个栅格为o 。有人可能会想，这样来表示一个物体效率 太低了。但是这种表示方法的简便性在计算方面有一定的优越性。特别是在有大 量的并行计算机同时运算的时候。例如一个不规则的物体的形状就可以通过这样 的表示计算出来。 多面体的表示方法在机器人的路径规划中是经常被用到的方法，因为很多物 体可以通过若干个多面体的并集来任意的逼近。计算两个凸多面体是否相交以及 两个凸多面体间的距离已经有很多的算法。两个凸多面体是否相交以及两个凸多 面体间距离的计算在机器人路径规划中是两个最重要的计算过程。 2 2 4 搜索方法 给定一个描述自由空间的方法，就可以判定一个机器人位姿是否与障碍物相 碰。机器人的路径规划问题就转化成为一个寻找从初始位姿点到终止位姿点的一 系列连接的无碰位姿的集合。我们将这样一个寻找从初始位姿点到终止位姿点的 一系列连接的无碰位姿的集合的过程称为搜索。在人工智能领域已经有不少的搜 1 2 中南大学硕士论文第_ 二章移动机器人路径规划技术 索方法，如深度优先搜索、广度优先搜索、a 幸搜索算法以及双向搜索算法。随 机搜索方法如模拟退火也被运用于机器人的路径规划问题。图论中的最短路搜索 算法( o g d i j k s t r a 算法) 在路径规划中也发挥了重要作用。近几十年，随着人工智 能研究不断取得进展，许多智能算法也被用到移动机器人的路径规划中，包括模 糊逻辑与增强学习算法、神经网络、遗传算法以及蚁群算法等。 深度优先搜索始终在最近生成的位姿点上寻找子节点。当然用这种方法找到 的解一般不是最短的。与此相反，广度优先搜索算法首先在最先生成的位姿点上 寻找子节点。但是这种方法要搜索的空间很大。所以，这两种搜索方法都不是非 常有效的搜索算法。 如果从当前位姿点到终止位姿点的距离可以通过某种方法计算出来，我们就 可以生成当前位姿点的所有子节点让机器人移动到离终止点最近的一个子节点。 这种方法称为优先搜索算法，又被称为爬山算法。在很多情况下这种方法都是非 常有效的。如果搜索空间非常狭窄时，这种方法需要用大量的时间。如果想求出 一条最小费用( 一般是最短路) 的解则往往需要a 木算法。如果用a 幸算法必须对 从当前点到终止点的费用函数有一个估计