（计算机应用技术专业论文）用于水下机器人路径规划的优化算法研究.pdf

c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ho no p t i m i z a t i o na l g o r i t h m s u s e dt op a t hp l a n n i n go fa u t o n o m o u s u n d e r w a t e rv e h i c l e s c a n d i d a t e ：d ij i a n h u a s u p e r v is o r ：p r o f z h a n gr u b o a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y d a t eo fs u b m is s i o n ： j a n u a r y ，2 0 0 9 d a t eo fo r a le x a m i n a ti o n ：m a r c h ，2 0 0 9 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 、_ 0 _ 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 ， 作者( 签字) ：协萝，髯 日期：伽7 年? 月9 e l 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可涟授予学位1 2 个月后0 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：厅节遂鼻 e l 期：伽7 年；月9e t - , - 9 , ) i t i ( 签字) ：致後锹 钞7 年歹月尹日 ， 。 _ 、 疗 0 p 摘要 路径规划技术是决定机器人智能化水平高低的关键技术，它是自主导航 中的一个重要组成部分。对于智能水下机器人( a u v ) 来讲，在有障碍物存在 和其它限制的条件下寻找一条安全、高效的路径是十分重要的，而用于水下 机器人路径规划的优化算法对规划效果起着至关重要的作用。本文主要研究 用于水下机器人路径规划的优化算法，基于规划效果对现有的优化算法进行 比较、分析、改进使其达到更好的和适用不同需要的规划结果。 在论文中，首先简要介绍了a u v 的发展概况、路径规划的相关概念及用 于路径规划的优化算法，接着在讨论了基于电子海图s h a p e f i l e 文件的环境建 模方法，然后研究粒子群与蚁群算法用于水下机器人路径规划，改进粒子群 算法取得较好效果，并利用多目标粒子群完成路径规划，和传统a 木算法规划 比较，最后改进蚁群算法使其适用于海流影响下路径规划。 本文以优化算法为研究重点，主要研究了改进的自适应粒子群算法、考 虑海流影响的蚁群算法及多目标粒子群算法，在基于电子海图环境建模的基 础上将上述算法用于水下机器人路径规划，并与传统的a 木算法比较，从规划 时间、效果等方面分析算法性能。 关键字：水下机器人；全局路径规划；优化算法：电子海图 - f ， - _ ， f - a b s t r a c t p a t hp l a n n i n gi sak e yt e c h n o l o g yt h a td e c i d e st h ei n t e l l i g e n tl e v e lo fr o b o t i t p l a y sa l li m p o r t a n tr o l ei na u t o n o m o u sn a v i g a t i o ns y s t e m f o ra l la u t o n o m o u s u n d e r w a t e rv e h i c l e ( a u v ) ，i ti sv e r yi m p o r t a n tt os e a r c has a f ea n de f f i c i e n tp a t h i nt h ee n v i r o n m e n t 晰廿lo b s t a c l e sa n do t h e rc o n s t r a i n t s ，a n dt h ep a t hp l a n n i n g a l g o r i t h m so f u n d e r w a t e rr o b o tp l a yav i t a lp a r ti nt h ep l a n n i n gr e s u l t t h i st h e s i s m a i n l yr e s e a r c h e s o n o p t i m i z a t i o na l g o r i t h m s u s e df o r p a t h p l a n n i n g o f u n d e r w a t e rr o b o t t h ee x i s t i n ga l g o r i t h m sb a s e do nt h ep l a nr e s u l t sa r ec o m p a r e d ， a n a l y z e da n di m p r o v e ds ot h a tt h e yc a ng e tb e t t e ra p p l i c a t i o na n df i td i f f e r e n t n e e d s i nt h et h e s i s ，ab r i e fo v e r v i e wo ft h ed e v e l o p m e n to fa u v , c o n c e p t so fp a t h p l a n n i n ga n dt h ea l g o r i t h m su s e df o rp a t hp l a n n i n ga r e f i r s t g i v e n t h e n ， e n v i r o n m e n t a lm o d e l i n gb a s e do nt h es h a p ef i l eo fe l e c t r o n i cc h a r ti sd i s c u s s e d a f t e rt h a t ，t h ep s o ，a c oa n dm u l t i - o b j e c tp s oa l g o r i t h m sw h i c hc a nb eu s e dt o p a t hp l a n n i n ga l es t u d i e d p a t hp l a n n i n gw i t ho c e a nc u r r e n tb yi m p r o v i n ga c o a l g o r i t h mi sd i s c u s s e da tl a s t t h i st h e s i sf o c u s e so nt h es t u d yo fo p t i m i z a t i o na l g o r i t h m s ：t h ei m p r o v e d a d a p t i v ep s o ，a n tc o l o n ya l g o r i t h mw i t ht h ei m p a c to fo c e a n c u r r e n ta n d m u l t i o b j e c t i v ep s o t h e nt h ea l g o r i t h m sm e n t i o n e da r eu s e di n t op a t hp l a n n i n g o fu n d e r w a t e rr o b o tb a s e do ne l e c t r o n i cc h a r tm o d e l i n g ，c o m p a r e dt h e m 诵mt h e t r a d i t i o n a la 牵a l g o r i t h ma n da n a l y z et h ep e r f o r m a n c eo fa l g o r i t h m sf r o mt h e a s p e c t so fp l a n n i n gt i m ea n dp l a n n i n ge f f e c t k e y w o r d s ：a u t o n o m o u su n d e r w a t e rv e h i c l e ；g l o b a lp a t hp l a n n i n g ；o p t i m i z a t i o n a l g o r i t h m ；e l e c t r o n i cc h a r t 目录 第1 章绪论1 1 1 概述1 1 2 水下机器人路径规划研究进展1 1 3 本课题的研究背景和意义3 1 4 论文的主要工作和论文组织3 第2 章水下机器人路径规划与优化算法5 2 1 路径规划概述5 2 1 1 路径规划的定义、分类、特点及问题实现5 2 1 2 全局路径规划方法6 2 2 水下机器人路径规划特点7 2 2 1 分析海洋环境7 2 2 2 水下机器人路径规划优化目标8 2 2 3 水下机器人路径规划特点8 2 3 用于机器人路径规划的优化算法概述9 2 3 1 普通优化算法9 2 3 2 智能优化算法1 0 2 4 多目标优化问题1 4 2 4 1 基于单目标的多目标求解方法1 4 2 4 2 基于多目标进化算法的平行求解方法l5 2 5 本章小结1 9 第3 章基于电子海图的海洋环境建模2 0 3 1 电子海图系统与s h a p e f i l e 文件格式简介一2 0 3 1 1 电子海图系统2 0 3 1 2e s r i 电子海图s h a p e f i l e 文件格式2 0 3 2 基于电子海图的海洋环境建模2 3 3 2 1 海图文件的读取2 3 3 2 2 海洋环境的凸多边形建模2 6 3 2 3 海洋环境的栅格建模3 0 3 l 3 2 4 1 用于机器人全局路径规划的改进粒子群优化算法3 2 4 1 1 粒子群算法概述3 2 4 1 2 用于机器人路径规划改进的自适应粒子群优化算法3 3 4 2 基于多目标优化算法的水下机器人路径规划3 9 4 2 1 多目标路径规划问题3 9 4 2 2 基于变权重系数法的水下机器人全局路径规划3 9 4 3 基于蚁群算法的水下机器人全局路径规划4 2 4 3 1 蚁群原理。4 2 4 3 2 路径规划及平滑处理4 4 4 3 3 多点规划4 6 4 4 改进蚁群算法用于考虑海流影响的a u v 全局路径规划4 7 4 4 1 海洋环境的模拟。4 8 4 4 2 改进蚁群算法用于海流影响下路径规划。5 0 4 5 算法性能比较分析5 6 4 6 本章小结6 0 结论6 2 参考文献6 4 攻读硕士期间发表的论文和取得的科研成果7 0 致谢7 1 1 1 概述 第1 章绪论 2 1 世纪是开发海洋的世纪，占地球表面积7 1 的海洋是一个巨大的资源 宝库，除了丰富的水资源与生物资源外，海洋石油与其他矿物资源数量也非 常巨大。随着陆地资源的不断消耗，海洋将逐渐成为人类赖以生存的第二空 间。海洋地位的提高，使得海洋的开发和利用成了很多国家的战略重点，也 使得海洋成为大国争夺的战场，而且愈演愈烈。我国总面积达3 0 0 多万平方 公里的海洋以及总长度达2 万多公里的海岸线，既是我们开发海洋资源的重 要基地，也是我们保家卫国的前线。由于常规的海洋舰船和武器系统在应付 现代高科技海洋战争中具有一定的局限性，我们必须进行军事海洋高科技的 开发，发展有特色的海军新装备，尤其是军事智能潜水器和水下机器人技术。 海洋蕴藏着丰富的资源，同时也是交通要道和兵戎相见的战场，它的战 略重要性是不言而喻的。2 1 世纪是人类向海洋进军的世纪。深海作为人类尚 未开发的宝地与高技术领域之一，己经成为各国的重要战略目标，也是近些 年国际上激烈竞争的焦点之一。近年来人们把注意力投向自主式水下机器人 ( a u t o n o m o u su n d e r w a t e rv e h i c l e ，简称a u v ) 的研究和开发上来。这主要是 由于自主式水下机器人在实际的水下作业中无需人工干预，它们可以自主地 运行在远程的、难于接近的、无法预知的或危险的海洋环境之中，完成自主 导航、自主避障和自主作业等任务。因此，无论在军事上，还是在商业上的 那些不适合潜水员作业的场合，例如充当深海工作平台、海洋勘探采样、水 下测量等研究应用领域，自主式水下机器人都具有无可比拟的优越性f lj 。 1 2 水下机器人路径规划研究进展 自治式水下机器人( a u v ) 的路径规划能力体现了水下机器人的智能水 平，海洋的探索和开发以及军事应用的发展，对自治式水下机器人的智能水 平提出了更高的要求，作为一种自主式海洋运载器，a u v 自主能力的真正含 义是具有和外部环境进行交互的能力，这种交互的一个重要方面就是具有全 局路径规划以及突发事件下的全局重规划和躲避障碍的能力。能够在未知、 非结构化的海洋环境下完成复杂的使命，也是自主水下机器人智能行为的重 要体现。 在水下机器人的路径规划研究中，国内外学者做了大量的工作，也取得 了许多成果： k a z u os u g i h a r a 和j u n k uy 曲提出了遗传算法路径规划法【2 0 】，该方法适用 于二维、三维时变环境，即可用于水下机器人的在线规划，也可用于离线规 划。j o a os e q u e i r a 和m a r i ai s a b e lr i b e i r o 提出了分两层规划的方法1 4 引，高级 规划模块基于已有的环境信息，并针对海流环境下的机器人能量消耗最小化 得到从起点到终点的一系列中间关键点，低级规划模块则产生相邻关键点间 的机器人位姿的变化序列。c l e m e n tp e t r e l ，y a hp a i l h a s 等提出f m * 算法【6 j ，应 用f m * 算法描述a u v 的二维环境进行快速的路径规划。a l v a r e z a 等人提出 了一种改进的遗传算法【7 】，用于解决具有强海流、时空高度可变性的海洋环 境中的a u v 路径规划问题。该文采用三维栅格对海洋环境进行建模，且每 个栅格点上给出海流沿三个坐标轴的流速分量，遗传算法的初始化操作生成 n 个随机个体，每个个体代表一条候选路径，算法以能耗最小作为适应度评 价函数。文献 8 】中认为a u v 推进功率是恒定的，降低航行时间可以有效节 能，因此该文在文献【7 的海洋环境模型基础上提出了复杂海流情况下的a 掌 路径搜索算法，并以最大可能航速( 海流速度+ a 1 j v 推进速度) 作为启发式 函数，因为a u v 推进速度是恒定的，所以a 术算法在实际搜索过程中考虑的 海流对a u v 航速的影响。a n t h o n ys t e n t z 提出了d 木算法用于解决未知和动 态环境下机器人的规划，s v e nk o e n i g 和m a x i ml i k h a e h e v 提出了d 木l i t e 方 法用以解决同样的问题 9 1 。h o n g j i a nw a n g ，d e h u iz h a o 等将自适应遗传算法 应用于a u v 路径规划，在确定环境下根据优化准则寻找最优路径，同时也 可用于基于传感器的动态实时规划【1 0 】。g ey a n g 等人采用模糊逻辑方法研究 了水下机器人在海流中的局部路径规划方法，将障碍物、海流影响以及机器 人三者的关系引入了实时环境评估【1 1 1 。z o n g h uc h a n g 基于前视声纳在未知 环境中采集的信息，采用遗传算法进行路径规划研究，编码采用浮点数法， 2 将多种限制因素考虑进评价函数中，有效的完成了海洋环境下动态的路径规 划【1 2 】。洪哗，王宏健，边信黔等提出了基于分层马尔可夫决策过程的路径规 划方法，并建立了基本的马尔可夫决策模型和结合状态聚类的分层马尔可夫 决策模型，同时给出了两种规划的仿真实验及结果分析。实验证明，此类方法能 够很好地求解大范围复杂环境内a u v 的二维路径规划问题【1 3 】。 1 3 本课题的研究背景和意义 全局路径规划是a u v 应具有的一种智能行为。全局路径规划是根据先 验知识( 如给定地图) ，在某些约束条件下，规划出一条从起点到终点的无碰 路径。全局规划如果从实质上来一说，它是一个有约束的优化问题。一般而 言，机器人完成给定任务可选择的路径有许多条，实际应用中往往要选择一 条在一定准则下为最优( 或近最优) 的路径，常有的准则有：路径最短、消耗 能量最少或使用时间最短等。 能够在未知、非结构化的海洋环境下完成复杂的使命，也是自主水下机 器人智能行为的重要体现。要使水下机器人实现在水下的自治航行，机器人 的路径规划是一个重要环节。路径规划水平的高低，在一定程度上标志着机 器人的工作水平，也是保证机器人安全可靠工作的关键，因此引起了国内外 学者的重视。 本文主要研究用于水下机器人路径规划的优化算法及基于电子海图的建 模方法。水下机器人路径规划的效果与算法和建模方法的选择有很大的关系， 本课题通过研究与分析用于水下机器人路径规划的优化算法、算法的适用情 况，使其得到较好的规划结果。 1 4 论文的主要工作和组织结构 本文的主要工作分为三大部分：首先是对电子海图的研究，包括对电子 海图标准的研究，海图文件的组织形式，海图数据的存储结构等，从电子海 图中提取出可用于路径规划的障碍模型，并进行相应的处理以适用于路径规 划。然后是对可用于水下机器人路径规划的优化算法的研究。分析传统的优 0 化与新兴的智能算法用于路径规划的效果差异，及改进方法等，并在电子海 图上显示规划结果。最后对海流特性的研究，并讨论在其影响下水下机器人 全局路径规划的特点。 本论文分为4 章，组织方式如下： 第1 章介绍了水下机器人路径规划技术的研究动态，简述本课题的研究背 景和意义，并给出了论文的主要工作和组织结构； 第2 章介绍了机器人路径规划相关概念、水下机器人路径规划特点、当今 流行的优化算法，并简要讨论了多目标优化问题； 第3 章简要介绍电子海 i 拘s h a p e 文件组织形式等内容，实现在海图文件 中提取障碍并简化以适用于路径规划； 第4 章研究改进的自适应粒子群算法、多目标粒子群算法在机器人路径规 划中的应用，结合电子海图实现海图上的规划显示，并给出了实验结果和性 能分析；阐述了基于蚁群算法的路径规划的基础上研究了考虑海流影响的全 局路径规划，以节能为主要目标，提出加入海流影响因子的蚁群算法，通过 实验分析其效果。 第2 章水下机器人路径规划与优化算法 2 1 路径规划概述 路径规划技术是智能水下机器人领域中的核心问题之一，也是机器人学 中研究人工智能问题的个重要方面。我们希望未来的智能机器入能具有感 知、规划和控制的高层能力，它们渴望能自主地从周围的环境中收集知识， 构造一个关于环境的符号化的世界模型，并且利用这些模型来规划、执行由 应用者下达的高层任务，其中，规划模块能生成大部分的机器人要执行的命 令，其目标是实现机器人的使用者在较高层次上下达一些较宏观的任务，由 机器人系统自身来填充那些较底层的细节问题。全局路径规划则是规划模块 中一个重要组成部分。 2 1 1 路径规划的定义、分类、特点及问题实现 路径规划技术是机器人研究领域的一个重要分支。所谓机器人的最优路 径规划问题，就是依据某个或某些优化准则( 如工作代价最小、行走路线最短、 行走时间最短等) ，在其工作空间中找到一条从起始状态到目标状态的能避开 障碍物的最优路径。 移动机器入的路径规划是移动机器人研究领域中非常重要的问题，总的 控制目标是使移动机器人运动到目标点，总的约束是在整个过程中，机器人 不碰到任何一个障碍物。该问题根据对环境信息的掌握程度可以分为两类： 一类是环境信息己知的全局规划，另一类是环境信息未知的局部规划。全局 规划方法依照已获取的环境信息，给机器人规划出一条路径。规划路径的精 确程度取决于获取环境信息的准确程度。全局方法通常可以寻找最优解，但 是需要预先知道环境的准确信息，并且计算量很大。局部规划方法侧重于考 虑机器人当前的局部环境信息，让机器人具有良好的避碰能力。很多机器人 导航方法通常是局部的方法，因为它的信息获取仅仅依靠传感器系统获取的 哈尔滨工程大学硕士学位论文 信息，并且随着环境的变化实时的发生变化。和全局规划方法相比较，局部 规划方法更具有实时性和实用性。缺陷是仅仅依靠局部信息，有时会产生局 部极点，无法保证机器人能顺利到达目的地【1 4 1 。 由于机器人路径规划面临环境的复杂性和要求的多样性，使路径规划问 题呈现以下特剧协j ： 1 ) 复杂性：在复杂环境尤其是动态时变环境中，机器人路径规划问题非 常复杂，且需要很大的计算量。 2 ) 随机性：复杂环境的变化往往存在很多随即和不确定的因素。未知环 境中动态障碍物的出现也往往带有不确定性。事先不可准确预知。 3 ) 多约束：机器人的运动存在几何约束和物理约束。几何约束是指机器 人的形状制约，而物理约束是指机器人的速度和加速度约束。 。 4 ) 多目标：机器人运动过程中对路径性能的要求存在多种目标【1 6 1 ，如路 径最短，时间最优，能量消耗最小，但是它们之间往往存在冲突。 路径规划的主要环节包括环境建模、路径搜索及生成、路径优化或平滑。 在机器人规划前，它首先要做的就是，将机器人活动空间的描述由外部 的原始形式通过一系列处理转化为适合规划的内部模型，这个过程我们称为 环境建模，其中主要是障碍物的表示方法。简单地说，就是要将物理上的环 境描述为计算机可以识别的形式。合理的环境表示有利于减少规划中的搜索 量及时空开销。不同的规划方法正是基于不同的环境建模基础之上的。路径 搜索算法负责从环境模型中搜索出路径的可行空间，而且，一般都与建模方 法有关。路径生成则是从搜索到的路径可行空间中生成一条可行路径。路径 优化是在考虑智能机器人自身动力学特性的基础上，为了让路径更有利于机 器人的执行而对路径进行的平滑。 2 1 2 全局路径规划方法 全局路径规划技术是智能机器人领域中的核心问题之一，全局路径规划 是指在已知环境信息的情况下，在有限条件下规划出一条由起点到终点的最 优或较优路径。全局路径规划从实质上来说是一个有约束的优化问题。一般 而言，机器人完成给定任务可选择的路径有许多条，实际应用中往往要选择 一条在一定准则下为最优( 或近似最优) 的路径，常用的准则有：路径最短、 6 耗能最少以及用时最短等。全局路径规划包括环境建模和路径搜索策略两个 子问题。其中，环境建模的方法主要有：可视图法、自由空间法和栅格法等 1 7 , 1 9 l 。路径搜索策略的方法主要有：a 木算法、遗传算法和模拟退火算法等【1 9 1 。 2 2 水下机器人路径规划特点 2 2 1 分析海洋环境 海洋环境中，海水的运动非常复杂，包括海流、海浪、潮汐、内波、风 暴涌、海水层流和湍流等，在这些因素的共同干扰下，机器人会偏离原来的 路径运行而可能导致与障碍物的相碰。因而，对于a u v 的路径规划必须要 考虑到海洋环境因素的干扰【l 。 在众多因素中，海流对水下机器人的影响最为主要。在航海上，一般将 海流分成潮流、定海流和风生流以及余流。其中定海流( o c e a nc u r r e n t ) 是海 水受较稳定的风( 如信风和季风) 长期吹动或海水密度分布不均匀等原因产生 的。其特点是流向、流速在一定的海区和时间内几乎不变，在大洋中比较明 显。潮流( t i d a ls t r e a m ) 是海水受日、月引潮力的作用而产生的海水水平方向 的流动。其特点是流向、流速随地点、时间呈周期性变化。风生流( w i dc u r r e n t ) 是海水受基本恒定的风力一定时间( 连续4 6 小时以上) 作用，而产生的一段时 间内的海水水平流动。其特点是流向、流速随风向、风速的变化而变化，一 般风停后仍能持续一段时间。各种海流都随深度的不同而有所变化。因此， a u v 处于不同深度将受到不同海流要素的影响【2 0 】。海流是海水较大规模相 对稳定的非周期性流动，随季节、气候、海域、地形、深度变化而变化，是 时间和空间的复杂函数，目前很难用精确的数学表达式描述其运动规律。但 海流随时间和空间的变化而变化是在较大范围内发生的，而在有限的特定海 域和特定时间段内，海流的流速和流向都是比较稳定的，同时考虑水下机器 人的航行能力有限，只能在特定的时间段内和海域内作短距离航行。文献 2 l 】 详细分析了海流自身运动特性，及对水下机器人运动影响。指出海流运动规 律很难精确表示，研究中主要考虑海流定常流动和对水下机器人的定常干扰。 2 2 2 水下机器人路径规划优化目标 机器人的最优路径规划问题，就是依据某个或某些优化准则( 如工作代价 最小、行走路线最短、行走时间最短等) ，在其工作空间中找到一条从起始状 态到目标状态的能避开障碍物的最优路径。 针对其特点水下机器人路径规划的优化目标大体包括：路径长度，耗能， 航行时间，路径平滑性，路径安全性。 路径长度最短作为路径规划的一个主要目标是我们规划的重点，路径长 度的大小可以反映出规划效果的好坏，在单目标路径规划中，往往将其作为 优化目标；能耗在水下机器人路径规划中显得尤为重要，特别当水下机器人 在大范围海洋环境航行时，能耗问题就变得十分突出，需要考虑执行任务中 其自身的能量和机器人跟踪路径时的实际能耗问题；航行时间与路径长度相 关，在要求机器人在最短时间到达目的地时，应以航行时间作为优化目标； 以路径长度为目标的规划结果往往是一系列不平滑的折线，为提高水下机器 人运动的稳定性和减小不必要的转弯时能量消耗，路径平滑性也是优化目标 之一，一般以拐点数或拐点夹角作为评判标准；为保证水下机器人安全工作， 路径安全性也是优化目标之一，一般路径到障碍的最短距离作为评判标准。 水下机器人路径规划既可以是考虑一个主要优化目标的单目标优化问 题，也可以是同时考虑多个目标的多目标优化问题。各优化目标之间存在着 内在的联系，如路径长度与路径平滑性对能耗与航行时间有影响，而确保规 划的路径安全是规划任务的前提。 2 2 3 水下机器人路径规划特点 机器人路径规划方法一般可用于水下机器人路径规划，但由于其海洋下 的特定工作环境，水下机器人路径规划有其自身的特点： 1 ) 海洋环境下水下机器人路径规划，机器人可定会受到海流的影响，在 海洋环境中，海流通常为水平方向的，它对机器人的作用力分布在x ，y 两 个方向上，其中x 方向沿机器人水平中轴线方向，y 方向垂直于机器人的水 平中轴线，所以x 和y 方向的分力也称为纵向力和横向力。同时由于横向力 和纵向力的合力的作用点与机器人的质心不重合，还会产生水平面内的摇艏 8 哈尔滨工程大学硕士学位论文 力矩。也就是说，海流对机器人的影响分布在水平面内的三个自由度上。 2 ) 海洋环境下能源对水下机器人相对重要，所以水下机器人路径规划也 应把节能问题作为规划效果的评判手段。 3 ) 大范围海洋环境下相对陆地上机器人路径规划障碍物较稀疏。 4 1 水下机器人工作的海洋环境是复杂的三维空间。 5 ) 海洋环境下对机器人规划的可靠性和安全性有更高的要求。 2 3 用于机器人路径规划的优化算法概述 2 3 1 普通优化算法 1 ) 算法 彳算法是应用极广泛的启发式搜索算法( h e u r i s t i cs e a r c ha l g o r i t h m ) ，许 多研究者对使用算法进行路径规划作了深入的研究。算法采用一个评价 函数( e v a l t m t i o nf t m c t i o n ) f ( n ) 来指导o p e n 表中扩展结点的选择。 f ( n ) = g ( n ) + 办( 玎)( 2 1 ) 式( 2 1 ) 中g ( n ) 为从出发点、到结点1 1 己发现最优路径的代价，h ( n ) 是依 赖于问题领域的启发式信息，反映从n 到目标点之间路径代价的估计。 令矿( 聆) 为从n 到目标点之间的实际最优路径的代价值，算法要求 办( 以) 矿( 胛) 。a + 算法可以保证找到一条最优路径( 在给定的代价函数和环境 表示下) ，只要该路径存在，即a 算法是可采纳的算法。其中g ( 刀) 和h ( n ) 的 数学表达方法可以根据实际情况而定。 彳算法的实现虽然简单直观，但在问题规模较大时时间和空间复杂度太 高。当环境复杂、规模较大时，它也是低效率的，经常几乎要扩展整个规划 空间才能找到目标。 2 ) d i j k s t r a 算法 通过建立环境障碍的链接图模型或栅格模型，将规划转化为图上求最短 路径。d i j k s t r a 算法是典型最短路算法，用于计算一个节点到其他所有节点的 最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 d i j k s t r a 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以 9 哈尔滨工程大学硕士学位论文 效率低。 算法大概过程为先创建两个表，o p e n ，c l o s e 。o p e n 表保存所有已生 成而未考察的节点，c l o s e 表中记录已访问过的节点。首先访问路网中距离 起始点最近且没有被检查过的点，把这个点放入o p e n 组中等待检查。然后 从o p e n 表中找出距起始点最近的点，找出这个点的所有子节点，把这个点 放到c l o s e 表中。第三遍历考察这个点的子节点。求出这些子节点距起始 点的距离值，放子节点到o p e n 表中。最后重复第2 和第3 步，直到o p e n 表 为空，或找到目标点。 此法可删除一些不必要的连线以简化可视图、缩短搜索时间，能够求得 最短路径。但假设机器人的尺寸大小忽略不计，会使机器人通过障碍物顶点 时离障碍物太近甚至接触，并且搜索时间长。另外的缺点就是此法缺乏灵活 性，即一旦机器人的起点和目标点发生改变，就要重新构造可视图，比较麻 烦。 2 3 2 智能优化算法 1 ) 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是一种有效的解决最优化i 口- j 题的方法。 它最先是由j o h nh o l l a n d 于1 9 7 5 年提出的 明。从那以后，它逐渐发展成为一 种通过模拟自然进化过程解决最优化问题的计算模型。利用遗传算法解最优 化问题，首先应对可行域中的点进行编码( 一般采用二进制编码) ，然后在可 行域中随便挑选一些编码组成作为进化起点的第一代编码组，并计算每个解 的目标函数值，也就是编码的适应度。接着就像自然界中一样，利用选择机 制从编码组中随便挑选编码作为繁殖过程前的编码样本。选择机制应保证适 应度较高的解能够保留较多的样本；而适应度较低的解则保留较少的样本， 甚至被淘汰。在接下去繁殖过程中，遗传算法提供了交叉和变异两种算子对 挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异 算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁 殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结束条件满足为 止。进化过程最后一代中的最优解就是用遗传算法解最优化问题得到的最终 结果。 l o 哈尔滨工程大学硕士学位论文 基于遗传算法的移动机器人全局路径规划方法首先把机器人工作空间用 栅格离散化，其次用一系列栅格序号的有序排列来表示一条机器人的运动路 径( 即一个个体) ，以多条运动路径所组成的群体作为优化搜索基础，最后采 用遗传算子对此群体进行遗传操作，从而得到“路径长度最短”这一评价准则 下的机器人最优运动路径。 将遗传算法与已有的其他路径规划方法相结合来解决路径规划问题，取 二者之所长，提高了路径规划问题的求解质量和求解效率。例如，遗传算法 与栅格法相结合，采用栅格法对机器人工作空间进行划分，用序号表示栅格， 并以此序号作为机器人路径规划阐述编码，用遗传算法对机器人路径规划进 行研究。遗传算法还可与凸区法结合，先用凸区法进行粗路径的搜索，再用 遗传算法进行路径节点的调整，从而规划出机器人的行走路线。此外，遗传 算法还可与人工势场、模糊理论等结合。 2 ) 基于群集智能的优化算法 近几年，模仿自然界中生物的一些群体行为，诞生了很多群智能算法， 包括粒子群算法、蚁群算法、鱼群算法等。粒子群算法( p a r t i c l es w a r m o p t i m i z a t i o n ，p s o ) 是最近出现的一种模拟鸟群飞行的仿生算法，有着个体数 目少、计算简单、鲁棒性好等优点，在各类多维连续空间优化问题上均取得 非常好的效果。文献【2 3 提出一种分步路径规划方法，首先采用链接图建立 机器人工作空间模型，用d i j k s t r a 算法求得链接图最短路径，然后用粒子群 算法对此路径进行优化，得到全局最优路径。文献【2 4 】在粒子群算法中，加 进了突变算子，避免算法在执行过程中陷入局部极小值。 蚁群算法是基于生物界群体启发行为的一种随机搜索寻优方法，它的正 反馈性和协同性使其可用于分布式系统，隐含的并行性更使其具有极强的发 展潜力，它在解决优化组合的问题上有着良好的适应性。因此将其应用在智 能机器人全局路径规划中，其目的是探索一种新的路径寻优算法。文献 2 5 】 在基于栅格划分的环境中，研究了机器人路径规划问题中蚁群系统的“外激 素”表示及更新方式，并将遗传算法的交叉操作结合到蚁群系统的路径寻优过 程中，提高了蚁群系统的路径寻优能力。 群集智能算法是一类新型进化算法，其主要特点是群体搜索策略和群体 之间的信息交换。这类算法对目标函数的性态没有特殊要求，在求解时不依 赖于梯度信息，因而特别适用于传统方法解决不了的大规模复杂问题，具有 广泛的应用范围。但群集智能优化算法的研究刚刚起步，还有着更大的发展 空间。 3 ) 神经网络规划方法 人工神经网络是模拟人脑结构的模型，具有并行处理、容错性和知识分 布存储等特点。神经网络规划方法应用并列连接网络结构，对一系列的路径 点进行规划，使得整个路径的长度尽量短，同时又尽可能远离障碍物。无碰 撞路径用一系列中间点表示，相邻点之间用线段相连。用碰撞罚函数对路径 与障碍物之间的碰撞性质加以量化，其定义为各路径点的碰撞罚函数之和， 而一个点的碰撞罚函数通过它对各个障碍物的神经网络来表示1 2 引。其基本思 想是，障碍物均假设为多面体，可用一组不等式来表示，于是在障碍物中的 点必定满足所有不等式的限制。 神经网络路径规划算法的主要优点是其隐含的并行性，缺点是较难找到 三维物体的不等式表达式。 4 ) 模糊逻辑规划方法 模糊控制算法模拟驾驶员的驾驶思想，将模糊控制本身所具有的鲁棒性 与基于生理学上的“感知，动作”行为结合起来，适用于时变未知环境下的路 径规划，实时性较好1 1 4 j 。 在移动机器人自主导航过程中，对于环境的描述经常包含着不确定因素， 不能将其直接归类到某一环境特征或采取某一明确的规则，这时就可采用模 糊逻辑。模糊逻辑由于符合人类思维习惯，不仅不需要建立系统的数学模型， 而且易于将专家知识直接转换为控制信号。利用模糊逻辑可将不确定性直接 表示在推理过程中。基于模糊规则的目标识别融合计算非常简单，通过指定 一个0 到1 之间的实数来表示真实度，这相当于隐式算子的前提。利用模糊 逻辑对传感器信息的精度要求不高，对移动机器人周围环境以及本身位姿信 息的不确定性也不敏感，这样就使得移动机器人的行为体现出很好的一致性、 稳定性和连续性。然而由于实际环境的复杂性，一方面很难预料到所有可能 的情况，另一方面对于多输入、多输出系统，要构造其全部模糊规则也非常 复杂和困难，而且模糊推理的运算量随着模糊规则的增长而按指数级增长。 因此让移动机器人能自己学会模糊规则是非常必要的。 哈尔滨- 丁程大学硕士学位论文 墨鲁宣昌宣昌宣；皇；置；宣；昌昌昌昌置昌宣墨宣置i i 暑；i 昌；暑暑暑昌；i 暑宣昌i 暑；i ；- 一 1 宣葺暑薯昌暑；置置；皇暑昌高昌宣 5 ) 模拟退火优化 模拟退火是一种通用概率算法，用来在一个大的搜寻空间内找寻命 题的最优解。它是一种可以跳出局部极值的有效方法。所谓模拟退火就是模 拟金属退火的过程，即首先用高温将金属融化，然后逐渐缓慢冷却，直到形 成良好的晶体结构，也就是进入一种具有最小能量的状态。 模拟退火算法与初始值无关，算法求得的解与初始解状态s ( 是算法 迭代的起点) 无关；模拟退火算法具有渐近收敛性，已在理论上被证明是 一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并 行性。文献 2 7 1 中提出为提高路径规划问题的求解质量和求解效率，在利用 神经网络算法、遗传算法进行路径规划的基础上，引入模拟退火算法，既能抑 制遗传算法的早熟现象，又克服了其局部寻优能力较差的缺点，形成一种新 的路径规划算法来解决机器人路径规划问题。文献1 2 8 针对传统遗传算法在 基于神经网络模型的移动机器人静态路径规划中求解最优路径时存在的收敛 较慢、易陷入局部极值点的问题，提出了一种基于遗传模拟退火算法的静态路 径规划方法。通过对算法进行实验仿真，结果表明提出的静态路径规划方法是 正确有效的。 6 ) 人工免疫算法 免疫算法( i a ) 模仿人体免疫系统，基于免疫网络模型，提出了免疫优化算 法。免疫算法从体细胞理论和网络理论中得到启发，实现了类似于免疫系统 的自我调节和生成不同抗体的功能，已在实际中得到应用【2 9 j 。 免疫系统是抵抗细菌、病毒和其它致病因子入侵的基本防御系统。免疫 系统由淋巴细胞把自身细胞与抗原识别出来，并产生抗体对付入侵的抗原， 达到消灭抗原的目的。免疫系统对自身也有免疫能力，能够抑制过多抗体的 产生。免疫算法具有保存多样性及记忆训练等优点，正是由于这些优点，免 疫算法在求解t s p 问题、函数优化、机器学习等方面有较大优势。文献 3 0 】 将免疫算法应用于移动机器人路径规划，提出一种任意多边形障碍物复杂布 局环境下的机器人路径规划的人工免疫算法，仿真证明该算法可以准确地找 到全局最优路径，而且能够适应各种复杂的环境。 哈尔滨工程大学硕士学位论文 2 4 多目标优化问题 研究多于一个目标函数在指定区域上的优化，又称多目标优化。在很多 实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方 案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目 标有时是不甚协调，甚至是矛盾的。 多目标优化问题的一般描述为： 给定决策向量x = ( 一，x 2 ，) ，它满足下列约束： g ，( x ) o ( i = 1 ，2 ，七)( 2 2 ) 曩( x ) = o ( i = l ，2 ，)( 2 3 ) 设有r 个优化目标，且这r 个优化目标是相互冲突的，优化目标可表示为 f ( x ) = ( 石(