（船舶与海洋结构物设计制造专业论文）某型auv全局路径规划技术研究.pdf

哈尔滨丁程大学硕+ 学位论文诵要智能水下机器人( a u v ) 研究领域中的一个重要问题是全局路径规划，它的目标是在已知障碍物的环境中寻找一条从起始位置到达目标位置的无碰最短路径。遗传算法是一种模拟生物进化原理的优化算法，而改进型遗传算法针对遗传算法易陷入局部最优的不足，在标准遗传算法基础上加入了三个新的操作复原、重构和录优。使改进后的遗传算法收敛于全局最优。本论文的主要内容就是研究改进型遗传算法应用于智能水下机器人的全局路径规划中的问题。在论文中，介绍了智能水下机器人的发展概况和全局路径规划的研究背景及意义、解决全局路径规划的各种方法，遗传算法的原理、概念以及特点。然后在标准遗传算法路径规划方法的基础上，引入了改进型遗传算法，并进行了二维和三维全局路径规划的研究，其中，用栅格模型来构造二维环境，同时采用改进了的遗传算予进行规划；用分层模型来构造三维环境，利用自适应概率计算公式计算遗传算子的概率。最后在水下机器人仿真系统中进行了联调仿真验证，验证了算法的有效性，并进行了算法性能分析，在相同的工作环境和条件下，比较分析了标准遗传算法和改进遗传算法的规划结果，证明了改进遗传算法是更加有效的一种算法。关键词：智能水下机器人；全局路径规划；改进型遗传算法；栅格模型；分层模型哈尔滨丁程大学硕士学位论文a b s t r a c ta ni m p o r t a n tr e s e a r c hf i e l do fa 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 ll sg l o b a lp a t hp l a n n i n g ( g p p ) w h i c hi st of i n dac o l l i s i o n - f r e ep a t hf r o mt h es o u r c ep o s i t i o nt ot h ed e s t i n a t i o np o s i t i o na m o n gk n o w no b s t a c l e s g e n e t i ca l g o r i t h m( g a ) i ss u c ha l la l g o r i t h mt h a ts i m u l a t i n gt h ep r i n c i p l eo fb i o l o g ye v o l u t i o n a sf a ra sw ek n o w , t h ec o n v e r g e n c eo f s t a n d a r dg e n e t i ca l g o r i t h m ( s g a ) t e n d st og e ti n t oal o c a lo p t i m u m a i m i n ga tt h i sd i s a d v a n t a g e ，m o d i f i e dg e n e t i ca l g o r i t h m ( m o a ) a d d st h r e eo p e r a t i o n s - - r e s t o r a t i o n ，r e c o n s t r u c t i o na n dr e c o r d i n gt h eb e t t e rt ot h es g at om a k et h ea l g o r i t h mc o n v e r g et oag l o b a lo p t i m u mw i t h o u tt h ec h a n g eo ft h es e a r c hr a n d o m i c i t y t h em a i nc o n t e n to ft h i sp a p e ri sc o n c e r n e da b o u ts o l v i n gt h eg p pp r o b l e mo f a u v 、i mm g a i nt h i sp a p e r , t h ec u r r e n ts i t u a t i o no f a u v sd e v e l o p m e n ta n dt h eb a c k g r o u n da n ds i g n i f i c a n c eo f g ai si n t r o d u c e d , a n da l lt h em e t h o d si ns o l v i n gg a p r o b l e m sa r ed i s c u s s e da sw e l l t h ea u t h o ra l s oi n t r o d u c e st h eb a s i cp r i n c i p l e ，c o n c e p t i o n s ，c h a r a c t e r i s t i c sa n do t h e rc o n t e n t so fg a t h e n , b a s e do ns g am e t h o d 。m g am e t h o dw a si n t r o d u c e d i tw a sa p p l i e di nt h e2 - d i m e n s i o n sg p pp r o b l e ma n di nt h e3 - d i m e n s i o n sg p pp r o b l e m t h e r e i n t o ，2 - d i m e n s i o n se n v i r o n m e n ti sc o n s t r u c t e db yg r i de n v i r o n m e n t a lm o d e l ，a n dt h eg e n e t i co p e r a t o ri sm o d i f i e d ；3 - d i m e n s i o n se n v i r o n m e n ti sc o n s t r u c t e db yh i e r a r c h i c a lm o d e l ，a n dt h ep r o b a b i l i t yo ft h eg e n e t i co p e r a t o ri sc o m p u t e db ys e l f - a d a p t i n gp r o b a b i l i t yf o r m u l a f i n a l l y ，m g am e t h o dw a st e s t e db yt h ej o i n ts i m u l a t i o ne x p e r i m e n ti nt h ea u vs i m u l a t i o ns y s t e m ，t h ev a l i d i t yw a sp r o v e db yt h er e s u l to f s i m u l a t i o n ，a tt h es a m et i m e ，t h ep e r f o r m a n c eo ft h ea l g o r i t h mw a sa n a l y s i z e d ，t h er e s u l t so fs g aa n dm g aw e r ec o m p a r e di nt h es a m ee n v i r o n m e n ta n dc o n d i t i o n ，i tw a sp r o v e dt h a tm g ai sb e t t e rt h a ns g a 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 ；m o d i f i e dg e n e t i ca l g o r i t h m s ；g r i de n v i r o n m e n t 净lm o d e l ；h i e r a r c h i c a lm o d e l哈尔滨工程大学学位论文原创性声明本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的。有关观点、方法、数据和文献的引用己在文中指出，并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任何其他个人或集体己经公开发表的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者( 签字) ：簋盔丞日期：硼年1月l 妒日哈尔滨工程大学硕十学位论文第1 章绪论1 1 引言海洋蕴藏着丰富的资源，同时也是交通要道和兵戎相见的战场，它的战略重要性是不言而喻的。2 1 世纪是人类向海洋进军的世纪。深海作为人类尚未开发的宝地与高技术领域之一，己经成为各国的重要战略目标，也是近些年国际上激烈竞争的焦点之一。自治水下机器人a u v 是英语“自治水下潜器”( 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 s ) 的缩写。a u v 不配备主缆和系缆，因此亦称为无人无缆水下机器人( u n m a n n e du n t e t h e r e dv e h i c l e s 缩写u u v ) 。这类水下机器人携带能源，依靠自身的自治能力来管理自己、控制自己，以完成赋予它的使命，自治水下机器入也就因而得名。作为一种商技术手段，水下机器人在海洋开发与应用领域发挥着重要的作用，受到许多国家的极大关注【1 1 。a u v 本身是一个基本的载体，在进一步发展并扩充各种机载设备和工具以后，a u v 的应用面是很广阔的。海底资源调查的实践表明，a u v 能非常精确地获取海底资料。在海底资源的开采中，a u v 可进行设备的维护和修理，运送必要的器材，进行现场的监视和测量。在未来的水下石油生产系统中a u v将起“操作工人”的作用。在海洋石油平台导管架检查、管道检查及维护力一面也会扮演重要角色。在海洋科学研究领域中，它可以用来进行海洋学的各种测量。a u v 可用于海底火山活动的观察、监视、布放和收回仪器，进行海底采样以及进行各种生物学、水文学的研究等。由于a u v 的活动范围广、体积小、重量轻、噪音低、隐蔽性好，在军事上是一种有效的水中兵器，装载战斗部后可以进行远距离投送；a u v 还可以用来侦察对方的水下设施，监听对方潜艇活动，可以用于反水雷、充当诱饵、配合反潜训练、防险救生等军事活动。所以a u v 无论在海洋科学研究还是在国防军事等方面都有重要价值和特殊意义。1 2 水下机器人的发展现状和研究动态鉴于水下机器人的应用前景和发展潜力，许多国家尤其是发达国家都致力于水下机器人技术研究和产品开发。国外的美国、英国、日本、加拿大、哈尔滨t 程大学硕+ 学位论文俄罗斯等国，都成立了专门的机构或者在高校里成立研究室研究水下机器入技术。如美国的海军研究生院的自主式水下运载器研究中心( c e n t e rf o ra u t o n o m o u su n d e r w a t e rv e h i c l er e s e a r c h ) ，英国的海事技术中心( m a r i n et e c h n o l o g yc e n t e r ) ，日本东京大学的水下机器人应用实验室( u n d e r w a t e rr o b o t i c sa p p l i c a t i o nl a b o r a t o r y ) 等。在国内，中科院沈阳自动化所，哈尔滨工程大学的海洋综合技术研究中心和中国船舶科学研究中心是研究水下机器人的三家主要单位。国际间成立的一些专业协会，如i e e e 海洋工程协会( i e e eo c e a ne n g i n e e r i n gs o c i e t y ) ，i e e e 机器人和自动化协会( i e e er o b o t i c sa n da u t o m a t i o ns o c i e t y ) ，海事技术协会( m a r i n et e c h n o l o g ys o c i e t y ) 等都为推动水下机器人技术的发展做出了应有的贡献。国外比较有代表性的水下机器人有：( 1 ) 冰岛的g a v i ag a v i a 机器人完全采用模块化设计，材质为铝合金，塑料和不锈钢，外形类似小型鱼雷。g a v i a 的主要性能如下：最大潜深2 0 0 0 m ，长度和重量视加装模块而定，最小长度1 7 m ，最小重量4 4l q g ，巡航速度6k n o t s ，回转半径小于3 m 。2 0 0 3 年1 0 月美国军方决定采购该型机器人用于反水雷( m c m ) 试验。图1 1g a v i a 水下机器人系统示意图2哈尔滨工程大学硕+ 学位论文( 2 ) 美国麻省理工学院开发的水下枧器入o d y s s e yi i ( 1 9 9 4 ) 。该水下机器长2 1 5 米、直径0 5 9 米、排水量1 4 0 公斤。肩负两项特殊的科学使命：在b e a u f o r t 海的冰下进行标图作业，以理解北冰洋下的海冰机制以及对中部大洋山脊处火山喷发进行快速反应。( 3 ) 丹麦的m a r t i n 号。目的是为a u v 开发水声导航系统。该a u v 可用于环境研究和海底安装的监视。在这一项目中，开发了基于声呐信号的探测和识别，能够用于避开未知的水下物体图1 2o d y s s e y i i 机器人图1 3m a r t i n 机器人( 4 ) 加拿大的r a y 和s u n f i s h 。r a y 成功地演示了它可以通过在耐压仓内向艏和艉移动重物来实现纵倾控制。s u n f i s h 是一个为特殊的科学目的研制的具有搜索功能的a u v 。图1 4r a y 机器人图1 5s u n f i s h 机器人( 5 ) 日本东京大学的t w i n b u r g e r l 2 、p t e r o a l 5 0 & 2 5 0 等多个型号的观察型自主式水下机器人。东京大学在水下机器人虚拟世界的仿真方面也做了很多工作。t w i n - b u r g e r 2 的硬软件基本上是在仿真环境下调试和开发的嗍。3哈尔滨丁稃大学硕士学位论文图i 6t w i n b u r g e r 2 机器图1 7p t e r o a 2 5 0 机器人我国在水下机器人的研究上，民用方面以“8 6 3 ”项目为代表。中科院沈阳自动化所与哈尔滨工程大学等单位共同研制开发了工作水深1 0 0 0 米的“探索者”号无缆水下机器人，1 9 9 4 年完成海试。后来中科院沈阳自动化研究所又通过与俄罗斯合作，共同开发了观察型、预编程控制的“c r 一0 1 ”无缆水下机器人，工作水深为6 0 0 0 米。该机器人完成了太平洋深海的考察工作，达到了实用水平。图i 8c r - o i 机器人1 3 本课题的研究背景和意义本课题来源于项目“某型a u v 路径规划技术研究”，随着陆地油气资源的日益枯竭，海洋油气开发将从大陆架逐渐延伸至数千米水深的海区，走向深水已是世界海洋石油的发展趋势。中国的油气资源前景寄希望于深水，南4哈尔滨t 程大学硕十学位论文海近岸大气田的水深范围在2 0 0 , - - 3 0 0 米左右，其它近海石油资源丰富的区域水深均在3 0 0 - - - 3 0 0 0 米左右，因此，走向深水也是中国海洋石油的战略目标。油气管道运输是海洋油气集输与储运过程中，密封、连续、快捷的一种安全由靠、运输量大又经济的运输方式。海底管道的损坏会造成油气田的停产、污染海洋环境，给国家带来巨大的经济损失。随着海洋石油开发向深水发展，长输油海底管道的数量将不断增加，长管道比短管道在理论上存在着更大的失效概率。按照现行的国内外海底管道系统规范要求和国际惯例，需要对海底管道进行定期检查( 年度检查) 和特别检查，以保证海底管道安全运行和延长使用期限。某型a u v 主要用于对海底管道的自主检测、水下生产系统运行监视、海底井场调查和指定区域( 特定区域) 自动采集不同深度环境下的水文参数、物理参数、化学参数等。其主要特点是航程远、潜深大，高精度的水下导航和路径规划是一个十分重要的课题。作为一种自主式海洋运载器，自治式水下机器人自主能力的真正含义是具有和外部环境进行交互的能力。这种交互的一个重要方面就是具有全局路径规划以及突发事件下的全局重规划和躲避障碍的能力。要使水下机器人实现在水下的自治航行，机器入的路径规划是一个重要环节。路径规划水平的高低，在一定程度上标志着机器人的工作水平，也是保证机器人安全可靠工作的关键，因此引起了国内外学者的重视。全局路径规划是a u v 应具有的一种智能行为。全局路径规划是根据先验知识( 如给定地图) ，在某些约束条件下，规划出一条从起点到终点的无碰路径。全局规划如果从实质上来说，它是一个有约束的优化问题。一般丽言，机器人完成给定任务可选择的路径有许多条，实际应用中往往要选择一条在一定准则下为最优( 或近最优) 的路径，常有的准则有：路径最短、消耗能量最少或使用时间最短等。1 4 本论文的主要工作本文对a u v 的全局路径规划进行了系统研究。对大量文献进行深入分析的基础上，结合本论文具体问题，着重研究了利用遗传算法进行水下机器人的全局路径规划。分别研究了a u v 在二维和三维环境下的全局路径规划，对传统算法作出改进，并对规划过程进行了仿真模拟。哈尔滨下程大学硕士学位论文本论文共分为以下部分：第一章：简要介绍了智能水下机器人( a u v ) 的有关内容，包括自主式水下机器人的简介、发展动态及本课题的背景及意义，并提到了作者的工作和论文的组织。第二章：讨论了全局路径规划的各种方法，并指出了各自的特点，最后分析了全局路径规划的发展现状和趋势。第三章：改进遗传算法在二维路径规划中的实现，给出了仿真结果并进行了性能分析，证明了改进算法更加优越于标准算法。第四章：改进遗传算法在三维路径规划中的实现，给出了仿真结果并进行了性能分析，证明了改进算法更加优越于标准算法。最后，对所做的工作加以总结，并提出了有待进一步探讨的问题。6哈尔滨丁稃大学硕十学位论文第2 章全局路径规划研究概况2 ：1 路径规划概述随着机器人在工业领域的应用越来越广泛，人们对机器人的“智能”的要求也在提高，要求机器人在运动过程中具有与周围环境交互的能力。其中一个最基本的需求就是能规划出避碰的运动路径，这种需求即为路径规划问题。路径规划技术是智能机器人领域中的核心问题之一，也是机器人学中研究人工智能问题的一个重要方面，在一定程度上标志着水下机器人智能水平的高低。我们希望智能机器人能具有感知、规划和控制等高层能力。它们能从周围的环境中收集知识，构造一个关于环境的符号化的世界模型，并且利用这些模型来规划、执行由应用者下达的高层任务。其中的规划模块能生成大部分的机器人要执行的命令，其目标是实现机器人的使用者在较高层次上给机器人下达一些较宏观的任务，由机器人系统自身来填充那些较低层的细节问题。路径规划技术是智能水下机器人领域中的核心问题之一：水下机器人在远程航行和各种作业过程中，为了安全地执行使命，就必须具备躲避障碍物的能力，而全局路径规划则是路径规划技术中的一个重要组成部分。2 1 1 路径规划的定义路径规划是自治式移动机器人的一个重要组成部分，它的任务就是在具有障碍物的环境内，按照一定的评价标准，寻找一条从起始状态( 包括位置和姿态) 到达目标状态( 位置和姿态) 的无碰路径嘲。通常按照规划的层次，路径规划可以分为全局路径规划和局部路径规划。全局路径规划就是根据先验知识( 如地图) ，在有约束条件下规划出一条从起点到达目标的无碰路径；而局部路径规划是以全局路径规划为指导，利用在线得到的局部环境信息，避开出现的未知障碍物到达子目标的过程。j t s c h w a r t z 和m s h a i r 6 j 在中是这样定义路径规划的：设b 是一个有若干刚体部件( 其中一些可能与其它部分用关节相连，另一些可能会独立的存在) 所组成的机器人系统，它共有k 个方向的自由度，并假设b 在一个充有若干机器人系统已知的障碍物的二维和三维空间v 自由运动。对b 来说，路径规划问题就是给定b 的起始位置s 和一个希望到达的终止位置g ，确定7哈尔滨工程大学硕士学位论文是否存在一条对b 来说从s 到g 的无碰路径，如有，则规划出来。需要指出的是，路径规划( p a t hp l a n n i n g ) 不同于轨迹规划( t r a j e c t o r yp l a n n i n g ) ，路径规划一般只给出机器人在几何意义上的位置和转角的值，而轨迹规划同时还要考虑机器人的线速度和角速度。因此，路径规划问题可以看作是轨迹规划问题的一个子集，它忽略了机器人的动力学特性。机器人路径规划问题在理论上主要存在三个子问题柳：( 1 ) 环境表示问题：指环境中障碍物的表示和自由空问的表示。环境建模就是对机器人活动空间的有效描述。机器人在规划前首先要做的就是将环境的描述由外部的原始形式通过一系列处理转化为适合规划的内部的世界模型，这个过程我们称为环境建模，其中主要是障碍物的表示方法。合理的环境表示才能有利于规划中搜索量的减少，才能有利于时空开销的减少。不同的规划方法是基于各种不同的环境建模来进行的。( 2 ) 寻空间问题：在某个指定区域r 中，确定物体a 的安全位置，使它不与己有的其它物体b j ( j = 1 ，2 ，m ) 相碰。( 3 ) 寻路径问题：在某个指定区域r 中，确定物体a 从初始位置移动到目标位置的安全路径，使得移动过程中不发生a 与b j 的碰撞。一系列安全位置就可以构成安全路径。解决路径规划问题的关键在于设计一种恰当的环境模型表示方法，即一种数据结构。该结构能反映出机器人在某位置上发生碰撞的可能性。然后，按照模型中的连通性构造与之对应的可连通图。该连通图仅抽取环境模型的连通性，忽略掉与路径规划不相干的信息，避免了因无关信息的引入使规划复杂化，这种连通图构成了问题状态空间。在该状态空间内利用搜索技术进行搜索，便求解出一条通路。将通路上的节点转化为实际模型中的表示形式( 如坐标点的序列) ，便得到了机器人的无碰路径。2 1 2 路径规划问题的分类路径规划分为全局路径规划和局部路径规划也是建立在机器人对其环境了解程度的基础上的。全局规划需要运动空间里完全的障碍物信息，而局部规划可以通过当前的声纳信息( 即障碍物相对机器人的位置和方向信息) 实时地规划。全局规划着眼于规划出一条从起始点到目标点的无碰撞路径，而且，3哈尔滨t 程大学硕十学位论文综合考虑任务要求和机器人本身性能，确立某种最优性能函数，通过一定的搜索方式，就能在机器人的运动空间中找到相应的优化路径；局部规划立足于实时性，仅仅根据局部区域内的障碍物信息来规划下一时刻的运动，从而避开障碍物。实际上，全局规划和局部规划之间并没有绝然的界限，而是相通的。一般地，机器人运动空间里的障碍物信息是逐步形成的。当机器人在某一区域里运动或作业对，它不但安全地航行，有效地作业，同时也可以进行标图，通过获取空间障碍物信息，形成一个逐步清晰的世界模型。因而，就有必要将全局规划和局部规划两者结合起来：首先，在现有信息基础上规划全局路径，机器人在航行中不断感知外界环境，遇到新的障碍物时，一边规划局部路径，一边记忆该障碍物信息，并把新的信息融入其世界模型中，这样一来，机器人就能不断地丰富自身的知识，从而更有效地规划路径，完成使命。当环境或障碍物的位置可以发生变化时，称之为”时变”( t i m e v a r y i n g )规划问题，否则称之为“时不变”( t i m e - i n v a r i a n t ) 规划问题。如果机器人可以移动一部分障碍物，又称为“可移障碍物”( m o v a b l e o b j e c t ) 规划问题。路径规划可以是限制性的，( c o n s t r a i n e d ) ，也可以是非限制性的( u n c o n s t r a i n e d ) 。这取决于对机器人的运动除避碰之外还有没有其他的内在的约束条件，如行进中对能量消耗的限制等。另外，根据完整性( c o m p l e t e n e s s ) 还可以把路径规划算法分为确定型( e x a c t ) 和启发型( h e u r i s t i c ) 两类。确定型算法可以找到一个问题的答案，除非它证明问题无解。启发型算法致力于在较短的时间内找出问题的答案，它可能无法解决较困难的问题或无法给出一个闯题的最优解。路径规划问题具有如下特点：( 1 ) 复杂性：在复杂环境尤其是动态时变环境中，机器人路径规划非常复杂，且需要很大的计算量。( 2 ) 随机性：复杂环境的变化往往存在很多随机性和不确定因素。动态障碍物的出现也带有随机性。( 3 ) 多约束：机器人的运动存在几何约束和物理约束。几何约束是指机器人的形状制约，而物理约束是指机器人的速度和能量等。( 4 ) 多目标：机器人运动过程中路径性能要求存在多种目标，如路径最短，时间最优，安全性能最好，能源消耗最小。但这些目标之间往往存在冲突。9哈尔滨工程大学硕士学位论文2 1 3 路径规划问题的实现路径规划的主要环节包括环境建模、路径搜索及生成、路径优化或平滑。在机器人规划静，它首先要做的就是，将机器入活动空间的描述由外部的原始形式通过一系列处理转化为适合规划的内部模型，这个过程我们称为环境建模，其中主要是障碍物的表示方法。简单地说，就是要将物理上的环境描述为计算机可以识别的形式。合理的环境表示有利于减少规划中的搜索量及时空开销。不同的规划方法正是基于不同的环境建模基础之上的。路径搜索算法负责从环境模型中搜索出路径的可行空间，而且，一般都与建模方法有关。路径生成则是从搜索到的路径可行空间中生成一条可行路径。路径优化是在考虑智能机器人自身动力学特性的基础上，为了让路径更有利于机器人的执行而对路径进行的平滑。2 2 全局路径规划方法目前，路径规划的方法有很多，我们可以大致分为两大类：传统方法和智能方法。2 2 1 传统路径规划方法迄今为止，对于路径规划，人们已经探索出了许多有效的求解方法。其中最主要的是拓扑法、几何法、人工势场法、单元分解法和数学分析法等路径规划领域中很多问题都可以用这四种基本方法来解决，也常常联合起来共同地实现路径规划。下面简单地介绍一下这几种方法。2 2 1 1 拓扑法拓扑法根据环境和运动障碍物的几何特点，将组成空间划分成若干拓扑特征一致的区域，根据彼此的连通性建立一个拓扑网，在该图中搜索一条拓扑路径。拓扑法的基本理论是降维法，即将在高维空间中求路径的问题转化成低维拓扑空间中判别连通性的问题。这种方法的优点在于利用拓扑特征大大缩小了搜索空间，其算法复杂性仅仅依赖于障碍物的数目，在理论上是完备的；缺点在于表示的复杂性、特殊性，建立拓扑网的过程是相当复杂而费时的，比较难以实现。但是，针对一种环境拓扑网只需建立一次，因而在实l o哈尔滨下稗大学硕士学位论文际中能提高效率，显示其优越性。( 1 ) 图形法图形解法的基础是生成扩展边界，扩展边界是指将障碍物边向自由空间扩展r 长度后得到的边界。生成扩展边界的复杂性限制了拓扑方法应用的环境范围。用图形法建立拓扑网的过程是：( 1 ) 每个子空间用其序号填充；( 2 ) 逐个跟踪每个子空间的边界，搜索与其相邻的每个子空间，计算彼此的连通分支和通道结构，形成区域节点的连通性网络；( 3 ) 将区域节点的连通性网络分解为区域，分支节点的连通性网络即为拓扑网络。因为拓扑网络的节点是很有限的，所以用任何现有的图搜索策略在该网络图上搜索一条路径都是非常简单的。用图形法实现拓扑路径规划算法，将复杂的几何计算问题转化为图形的一些简单处理问题，直观灵活，适应性强，能够处理比较一般情况下的路径规划问题。这种基于拓扑算法的图形法的突出优点在于它类似于人在迷路的情况下根据地图寻找路径的过程，对障碍边界要求很松，直接利用了拓扑特征。用图形法解决拓扑路径规划算法的实现问题还有许多工作要做，特别是在增加障碍物是如何有效地修正已经存在的拓扑网络这一问题尚需要深入研究。如何提高图形的速度也是一个亟待解决的问题。尽管存在许多问题，但是图形法在解决拓扑路径规划问题时所显示出来的灵活性和适应性是很有吸引力的。( 2 ) 解析法用一个依赖于位形空间参数的不等式组来表示机器人躲避障碍物的要求。路径规划由起始位形到终止位形寻找路径时最小化一个标量函数而转化为一个数学优化问题。由于这种优化是非线性的，并有很多限制条件，故往往使用离散化的方法来找这个最优解。2 2 1 2 几何法几何法抽取环境的几何特征，把自由位姿空间映射到一个加权图上，这样就把原问题转换成了一个简单的图搜索问题，基于几何法的路径规划方法分为三步：哈尔滨 二程大学硕十学位论文a 在搜索图中找到机器人起始位姿所对应的节点；b 同样的在搜索图中找到机器人终止位姿所对应的节点；c 把这两个点用图中的线连接起来，就得到一条无碰路径。搜索图所必须能表示位形空间中所有拓扑独立的不同的可行路径，否则该路径规划算法是不完备的。( 1 ) 可视图法该算法是1 9 7 9 年由l o z a n o 和w e s l e y 提出，其最大的特点是障碍物由多边形或多面体构成。首先将机器人缩为一点，而将相应的障碍物进行扩展，然后在由扩展后的障碍物顶点所构成的网中搜索路径。假设机器人的初始位置为& 目标位置为反我们定义一个图v g ( n ，三) ，节点集n = v u s ，g ，其中矿为所有障碍物的顶点集，连接弧集合为所有弧( ，z ，胛) 的集合，其中连接 r 中第i 和第- ，个元素的线段与任何障碍物均不相交。图v g ( n ，工) 称为的可视图( v g r a p h ) ，因为图中相邻的顶点能相互看到。平面上从s 到占的最短路径为v g r a p h 上从s ng 的几何距离最短的路径。这种在可视图上寻找一条最短无碰路径的方法就是可视图( v g r a p h ) 法。a 的最短安全路径，就是由连接起点、终点以及多边形的若干顶点的直线组成的。即把彼此看得见的多边形的二定点以及起终点用直线连接起来，就得到安全的最短路径。如图2 2 。图2 2 可视图法示意图1 2哈尔滨t 程大学硕十学位论文可视图法对于二维的姿态空间是一种较简单有效的求路径的方法。推广到多维空间去，一般要用到投影，使之能在低维空间中处理，还要做一定的近似，才能用多面体或多边形来表示。这种方法的主要缺点是，所求的无碰路径多数沿障碍的边界走，过分靠近障碍，这样当障碍位置、大小或形状知道的不准确是，运动物体就有可能与障碍相碰。此外，用切块投影方法来处理高维姿态空间的问题，各块上下界大小的选取，虽然可以灵活掌握，但每块毕竟对应一个区间，当要求参数作连续变化时，用切块的方法就不能求解了。( 2 ) 单元细分法b r o o k s 和l o z a n o 在1 9 8 3 年提出了考虑旋转物体的路径规划s u b d i v i s i o n 算法l l o 】【1 1 】，他们讨论的基本问题是具有两个平移和一个旋转自由度的运动物体在多边形障碍物中的运动。算法的基本思想很简单。将姿态空间切分为单元，在所在的单元中，若没有包含障碍，称为空单元，简称为e ；若全部为障碍所充满，为满单元，记为f ；若部分包含障碍，为混合单元，记为m 。如图2 3 所示。把单元视为节点，其间的相邻关系用弧连接起来，得到一个网络，成连通图( c o n n e c t i v i t y6 r a p b ) ，于是寻找安全路径的问题变为图的搜索。如果从开始单元s 能找到一条仅包含所有单元为e 的到达目标g 的路径，该路径为安全路径，若其中有m 单元，则把它们进一步切分成更细的单元，直到找到一条通路位置，或者切分到一定粒度之后，仍找不到安全路径，则认为无碰路径不存在。若无m 单元，则可进一步切分，说明无安全路径。哈尔滨工程大学硕士学位论文图2 3 单元细分法示意图该算法的一大特征是划分空间与搜索是交叉进行的。该算法对各种维数的姿态空间原则上都适用，但它基本上都是盲目的、穷举的方法，对于高维的情况，计算量是很大的。单元切分法所找到的安全路径也比较靠近障碍物，这也是它的缺点之一。( 3 ) v o r o n o id i a g r a m 法c 0 d u n l a i n g 等1 9 8 3 年提出了用r e t r a c t i o n 方法来解决平面上的路径规划问题，而后，0 t a k a h a s h i i ”1 实现了该方法。首先v o r o n o id i a g r a m法的理论：假设s 为多边形障碍物的集合，已知平面上两点x 和y ，d ( x ，y ) 表示它们的欧氏距离，若，为一个非空点集，则h a u s d r o f f 距离d ( x ，】，) 定义为i n f d ( x ，y ) ：j ，e y ，若j 为另一非空集合，d ( x ，y ) = i n f d ( x ，j ，) ：x x 。对每一点善定义c l e a r a n c e ( x ) 为肖到s 的h a u s d r o f f 距离。假设所有障碍物之并为一闭集，用q 表示它的有界补集，由此可知对q 中任何一点x ，存在某个障碍物边界上的一点p ，使得d ( x ，p ) = c l e a r a n c e ( x ) 。如果我们定义1 4哈尔滨工程大学硕十学位论文n e a r ( x ) 为s 中到x 距离为最短距离c l e a r a n c e ( x ) 的点的集合，则n e a r ( x ) 非空。定义2 1 ( 标准) v o r o n o id i a g r a m ( s ) 为妞中的x ：i 胛0 ) 至少包含两点 。定义2 2 对q 中每一点x ，设) ，为n e a r ( x ) 中唯一元素，x 的映象i m ( x )为从j ，到工的射线与v o r o n o id i a g r a m 相交的第一点；对( s ) 上的x ，我们定义h n ( x ) = x 。定理2 1 映射i m 为已定义的从q 到v o r o n o id i a g r a m 圪m ( s ) 上的连续回缩( c o n t i n u o u sr e t r a c t i o n ) 。进一步说，c l e a r a n c e ( * ) 在从x 到i m ( x ) 的射线上的严格递增。定理2 2 从自由位置p 到口存在一条路径当且仅当在( s ) 上存在一条从i m ( p ) 到i m ( q ) 的路径。有关g e n e r a l i z e dy o r o n o id i a g r a m ( g v d ) 问题存在许多算法，设i 7 为障碍物顶点数，则算法复杂性可减少至：l j o ( n l o g n ) ，这就为应用g v d 进行路径规划提供了实用条件。采用g v d 方法规划主要分两步：计算g v d ；在g v d 上搜索路径并判断该路径是否可通过。在路径搜索过程中，t a k a h a s h i 提出了四种启发方法：( 1 ) 宽路法( w i d e p a t hh e u r i s t i c ) ；( 2 ) 紧转弯法( t i g h t b e n dh e u r i s t i c ) ：( 3 ) 狭窄通路法( n a r r o w g a ph e u r i s t i c ) ：( 4 ) 反向法( r e v e r s eh e u r i s t i c ) 。经过大量例子的测试，g v d 方法有较高的效率。许多学者对g v d 方法进行了研究。在h o w i ec h o s e t 等人的研究中3 4 j ，将g v d 方法与基于传感的规划控制方法相结合，使g v a 方法的应用更加广泛。( 4 ) 其它方法其它方法，如广义锥法、顶点图象法、广义v o r o n o i 图像法等。这些方法都是试图克服上述三种方法所求的路径过分靠近障碍的缺点，设法从障哈尔滨下稃大学硕士学位论文碍i b j 通道的中央穿过去。2 2 1 3 人工势场法人工势场法实际是对机器人运行环境的一种抽象描述。势场中包含斥力极和引力极，不希望机器人进入的区域和障碍物属于斥力极，子目标及建议机器人进入的区域为引力极。引力极和斥力极的周围有一定的算法产生相应势，机器人在势场中具有一定的抽象势能，它的负梯度方向表达了机器人系统所受抽象力的方向，正是这种抽象力，促使机器人绕过障碍物，朝目标前进。按势函数的不同选取方法，大概可将人工势场的研究分作下面几类。( 1 ) 普通人工势场法势函数由距离和速度等信息表示，势函数为连续可导函数。在这类方法中，以0 k h a t i b 等人的工作最具有开创性及代表性。在0 k h a t i b 方法中，其引力势函数为：( 加彤巧( 工飞) ：( 2 - 1 )斥力势函数为：u 。，c x ，= ：。7 2 v r 一1 箩：；，?c z z ，式中：x 机器人当前位置x g 目标位置，机器人到障碍物的最短距离势场最大影响距离吒比例因子1 6哈尔滨下程大学硕十学位论文( 2 ) 流体力学的调和函数法这种方法以流体力学中的势流理论为基础，利用极点分布法对流场进行求解。j i n o hk i m 、k e y m e u l e n 、c h r i s t o p h e ri c o n n o l l y 等人在这方面进行了大量的研究工作。j i n o hk i m 等人的工作较为细致，探讨了势流理论在路径规划中的应用，并利用面元法对路径规划问题进行求解。然而势场法存在以下几方面的缺点：一是容易产生局部极点，即所有障碍物与目标在这样的点上形成的抽象力之和为零，造成机器人在这些点上受到零控制而停车，此时机器人并没有达到目标；二是在相近障碍物之间不能发现路径；三是在障碍物前面振荡；四是在狭窄通道中摆动。所以势场法应用于全局路径规划，还要采取一些改进措施来克服该法所产生的缺点。2 2 2 智能路径规划方法近年来，随着遗传算法等智能方法的广泛应用，机器人路径规划方法也有了长足的进展，许多研究者把目光放在了基于智能方法的路径规划研究上。其中，应用较多的算法主要有模糊方法、神经网络和遗传算法。2 2 2 1基于模糊逻辑的机器人路径规划模糊方法是在线规划中通常采用的一种规划方法，包括建模和局部规划。庄晓东等【1 5 1 提出一种基于模糊概念的动态环境模型，参照物体的位置和运动信息构造二维隶属度函数：然后通过模糊综合评价对各个方向进行综合考察得到搜索结果。该方法在移动障碍物和移动目标的环境中能有效地实现机器人避碰和导航。李彩虹等1 1 6 1 提出了一种在未知环境下移动机器人的模糊控制算法，并对此算法进行了推导与仿真，证明该算法鲁棒性强，可消除传统算法中存在的对移动机器人的定位精度敏感、对环境信息依赖性强等缺点，使移动机器人的行为表现出很好的一致性、连续性和稳定性。h a r t m u ts u r m a n n 等 1 7 1 提出一种未知环境下的高级机器人模糊导航方法，由8 个不同的超声传感器来提供环境信息，然后利用基于模糊控制的导航器来计算这些信息，规划机器人路径。其模糊规则建立见表1 。1 7哈尔滨工程大学硕士学侥论文表l基于模糊控制的机器人导航模糊规刚建立命令模糊鎏命令模糊醢停止0 【0 5 。0 面向酶1 【o 5 ，1 5下个命令左转2 f 】5 ，2 。5下个命令右转3 【2 5 ，3 5】立即右转前行转向新：前个命令左转5 6 7 8 ，6 7 ，3 ，9 后退4 【3 5 ，4 5 1 新：前个命令右转1 0 f 9 5 ，1 0 5 1立塑垄蕴5 垂【垒5 。5 ：5 l=该方法在环境未知或发生变化的情况下，能够快速而准确地规划机器人路径，对于要求有较少路径规划时问的机器人是一种很好导航方法。但是，其缺点是当障碍物数目增加时，该方法的计算量会很大，影响规划结果。2 2 2 2 基于神经网络方法的机器人路径规划禹建丽等【1 8 1 提出了一种基于神经网络的机器人路径规划算法，研究了障碍物形状和位置已知情况下的机器人路径规划算法，其能量函数的定义利用了神经网络结构，根据路径点位于障碍物内外的不同位置选取不同的动态运动方程，规划出的路径达到了折线形的最短无碰路径，计算简单。收敛速度快。陈宗海等【l 辨提出了一种在不确定环境中移动机器人的路径规划方法，将全局路径规划分解为局部路径规划的组合，为了提高规划的效率，在避障规划中采用了基于案例的学习方法，以a r t 一2 神经网络实现案例的匹配学习和扩充，满足了规划的实时性要求。为了提高机器入路径规划的速度，禹建丽等i 2 0 】在利用神经网络路径规划方法的基础上，又引进了线性再励的自适应变步长算法。这种方法实现了步长的自适应选择，使路径规划速度比原来的神经网络规划提高了1 0 倍。i s哈尔滨工程大学硕十学位论文2 2 2 3 基于遗传算法的机器人路径规划遗传算法是目前机器人路径规划研究中应用较多的一种方法，无论是单机器人静态工作空间，还是多机器人动态工作空间，遗传算法及其派生算法都取得了良好的路径规划结果。孙树栋等【2 l 】用遗传算法完成了离散空间下机器人的路径规划，并获得了较好的仿真结果。但是，该路径规划是基于确定环境模型的，即工作空间中的障碍物位置是已知的、确定的。k a z u os u g i h a r aa n dj o h ns m i t h l 2 2 】在采用离散空间进行路径规划的同时，将问题更深入化，栅格序号采用二进制编码，统一确定其个体长度，随机产生障碍物位置及数目，并在搜索到最优路径后，再在环境空间中随机插入障碍物，模拟环境变化，通过仿真结果验证了算法的有效性和可行性。但是，规划空间栅格法建模还存在缺陷，即若栅格划分过粗，则规划精度较低：若栅格划分太细，则数据量又会太大。周明等口”提出一种连续空间下基于遗传算法的机器人路径规划方法，该方法在规划空间利用链接图建模的基础上，先使用图论中成熟算法粗略搜索出可选路径，然后再使用遗传算法来调整路径点，逐步得到较优的行走路线。该方法的染色体编码不会产生无效路径，且仅使用基本遗传算法就可以完成路径规划。但是，该方法对于环境复杂、障碍物数目较多的情况，链接图的建立会有一定的困难。在遗传算法的改进上，周明等【2 4