（计算机应用技术专业论文）水下机器人路径规划问题的关键技术研究.pdf

水下机器人路径规划问题的关键技术研究 摘要 自主式水下机器人自主能力的真正含义是具有和外部环境进行交互的 能力，这种交互的一个重要方面就是具有全局路径规划以及突发事件下的动 态重规划和躲避障碍的能力。要实现水下机器人的自主航行和自主作业，机 器人的路径规划是一个重要环节，研究水下机器人的路径规划技术对于提高 其智能化水平和加快工程化应用进程具有重要的意义。本文以“十五”国防预 研项目( 4 1 3 1 6 0 7 ) 和“十一五”国防预研项目( 5 1 3 1 6 0 8 0 2 0 2 ) 为背景，对自 主式水下机器人在海洋环境下的全局路径规划技术、局部路径规划技术、避 碰规划技术、区域探测路径规划技术进行了深入的研究。 首先，介绍了水下机器人动力学模型，以及水下机器人的系统组成，概 述了水下机器人体系结构的研究现状，并按照精度随智能降低而提高的原理 ( i p d i ) 为某型水下机器人设计了分层递阶控制体系结构，它分为六层三列， 按照这个体系结构实现的自主控制可以满足任务的需要。 提出了海洋环境下的全局路径规划方法。针对海洋环境障碍物分布稀疏 的特点，提出了用于小范围区域全局路径规划的最短切线路径算法，它计算 简单、运行效率高。针对大范围海洋区域，提出了基于v c f 电子海图的多 目标优化遗传算法。算法采用可变长的实数坐标的染色体编码方式，在适应 度评价函数的设计中综合考虑了多个影响因素，不可行路径被加以惩罚值也 参与了种群进化。设计了选择、交叉、变异、修补和删除等五类遗传算子， 在生成初始种群和设计遗传算子时引入领域知识，以实现所生成路径尽量不 穿越障碍区域的目的，有效地提高了算法的收敛速度。该算法实现了用尽量 短的时间在大范围海洋区域规划出一条近似最优路径的研究目标，规划路径 合理可行。 提出了基于模糊逻辑的局部路径规划方法。在复杂的海洋条件下，导航、 传感等数据本身就存在着巨大的不确定性和不准确性，此方法可用来处理这 些近似信息。在分析了海流、障碍物和机器人三者之间的关系后，得出相应 的模糊规则表作为局部路径规划的依据。该方法综合考虑了海流的影响和机 器人平台的运动特性，以相对简单的形式较好地解决了考虑海流影响的水下 哈尔滨工程大学博士学位论文 机器人局部路径规划问题。模糊控制理论用于机器人路径规划同样会出现局 部最小问题。提出了基于传感信息的实时路径规划方法，通过设置虚拟目标 点以及f o l l o w - l e f t w a l l 行为和f o l l o w r i 曲t w a l l 行为的激活和退出条件，使水 下机器人能够脱离局部极小状态从而达到目标位置。 提出了基于传感信息的反应式行为自动设计方法，将避碰路径规划行为 当成一个整体进行设计，不必考虑如何分解行为，采用q 学习对机器人反应 式行为进行自主学习，以产生期望的优化行为。学习结束后抽取的控制规则 作为反应式行为去执行，这样产生的行为不仅更具目的性和适应性，而且具 有反应式行为的较高的反应速度。另外，针对学习系统的输入输出空间是连 续变化的要求，提出了一种f u z z yq 伉) 学习算法，它将模糊理论与q 学习相 结合，采用q 学习算法不断更新模糊规则库中的结果向量权值直至其收 敛，从而得到一个完整的模糊规则库。 提出了基于区域探测作业任务的全覆盖路径规划算法。对基本区域设计 了权值梯度法和单元分解法，对含有障碍的一般区域，将整个区域划分为若 干个子区域，设计了基于关键点的单元分解策略，针对邻接图构造过程中出 现的问题，提出了一种i n o u t 关键点匹配算法，可以保证无遗漏地搜索区 域内的所有子区域单元。为跟踪所规划的目标路径，设计了水下机器人的路 径跟踪控制策略，综合考虑到任务需要及艇体的运动能力来获得机器人在移 动过程中的目标指令。机器人执行区域探测作业任务的仿真试验结果验证了 算法的有效性，算法可以满足实际应用的需要。 关键词：a u v ，路径规划，遗传算法，模糊逻辑，q 学习，覆盖路径规划， 路径跟踪 n 水下机器人路径规划问题的关键技术研究 a b s t r a c t i k g e n u i n em e a n i n go fa u t o n o m yc a p a b i l i t y o fa uv ( a 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 、i st o p r o c e s s t h e a b i l i t y t oi n t e r a c t 、析t he x t e r n a l e n v i r o n m e n t , o n em a j o rr e s p e c to ft h i si n t e r a c t i o ni sf o r vt ob ec a p a b l eo f g l o b a lp a t hp l a n n i n g ，d y n a m i cr e - p l a n n i n gw h e ne n c o u n t e r i n ga b r u p te v e n t s ，a n d o b s t a c l e sa v o i d i n g f o ra u vt 0f | u l f i l la u t o n o m o u sv o y a g ea n dt a s ke x e c u t i o n ， p a t h p l a n n i n g i sa n i m p o r t a n ts e c t o r ，t h e r e f o r e ，r e s e a r c h o np a t h p l a n n i n g t e c h n o l o g yo fa u vp l a y sa ni m p o r t a n tr o l ei ni m p r o v i n g i t si n t e l l i g e n tl e v e la n d a c c e l e r a t i n g i t se n g i n e e r i n ga p p l i c a t i o n w i t l lt h es u p p o r to ft h ek e yr e s e a r c h p r o j e c t ( 4 1316 0 7 ) o ft h elo t hf i v e y e a rp l a na n dp r o j e c t ( 51316 0 8 0 2 0 2 ) o ft h e 1 lt hf i v e y e a rp l a n ，t h et h e s i sd e e p l ys t u d i e da u v sg l o b a lp a t hp l a n n i n g ，l o c a l p a t h p l a n n i n g ，o b s t a c l e a v o i d a n c e p l a n n i n g a n dp a t h p l a n n i n g f o r r e g i o n r e c o n n a i s s a n c ei nt h eo c e a n f i r s t l y 、t h ek i n e t i c sm o d e la n ds y s t e mc o m p o n e n t so f 心na r ei n t r o d u c e d ， a n dt h ec u r r e n tr e s e a r c hs i t u a t i o na b o u ta u va r c h i t e c t u r ei ss u m m a r i z e d t h e h i e r a r c h i c a lc o n t r o la r c h i t e c t u r ei sd e s i g n e df o rc e r t a i n n ，a c c o r d i n gt ot h e l a w so fi n c r e a s i n gp r e c i s i o n 、访吐ld e c r e a s i n gi n t e l l i g e n c e ( i p d i ) t h ea r c h i t e c t u r e c o n s i s t so fs i xl a y e r sa n dt h r e el i s t s ，a n dt h ea u t o n o m o u sc o n t r o lr e a l i z e db yt h e a r c h i t e c t u r ec a ns a t i s f yt h en e e d so fa u vt a s k s e c o n d l y ，w eb r i n gf o r w a r dt h em e t h o d sf o ra u vg l o b a lp a t hp l a n n i n g w e d e v i s e ss h o r t e s tt a n g e n tp a t ha l g o r i t h mu s e df o rs m a l lr e g i o np a t hp l a n n i n gt h a t c o m p u t e ss i m p l ya n dr u n se f f i c i e n t l y a st ol a r g es c o p eo c e a na r e a , w ed e s i g na m u l t i o b j e c t i v eo p t i m i z a t i o ng e n e t i ca l g o r i t h mb a s e do nv c fe l e c t r o n i cc h a r t s 1 1 l i sa l g o r i t h me n c o d e sc h r o m o s o m ei n t or e a l n u m b e rc o o r d i n a t e so fv a r i a b l e l e n g t h , a n dt a k e s s e v e r a li n f l u e n c ef a c t o r si 1 1 t oa c c o u n tw h e nd e s i g n i n g e v a l u a t i o nf u n c t i o n s i n f e a s i b l ep a t hi sg i v e na na d d i t i o n a lp u n i s h m e n ta n dt h e n p a r t i c i p a t e si np o p u l a t i o ne v o l u t i o n f i v eg e n e t i co p e r a t o r ss u c ha ss e l e c t i o n , c r o s s o v e r , m u t a t i o n r e p a i ra n dd e l e t i o no p e r a t o r s a r e d e s i g n e d d o m a i n k n o w l e d g ei si n t r o d u c e di nt h ep r o c e s so fi n i t i a lp o p u l a t i o ng e n e r a t i o na n d g e n e t i co p e r a t o rd e s i g n ，i no r d e rt oa c h i e v et h eg o a lt h a tt h eg e n e r a t e dp a t h sd o n o tc r o s so v e ro b s t a c l ea r e at ot h eg r e a t e s te x t e n t c o n v e r g e n c es p e e do ft h i s a l g o r i t h mi sg r e a t l yi m p r o v e da sa r e s u l t s oa na p p r o x i m a t eo p t i m a lf e a s i b l ep a t h i nl a r g ea r e ac a l lb eg e n e r a t e da sq u i c k l ya sp o s s i b l eu s i n gt h i sa l g o r i t h m t l l i r d l y ，w ep u tf o r w a r dl o c a lp a t hp l a n n i n gm e t h o d sb a s e do nf u z z yl o g i c c o n s i d e r i n gt h eh u g ei n d e t e r m i n a c ya n di n a c c u r a c yo fd a t af r o mn a v i g a t i o n s y s t e ma n ds e n s o r su n d e rc o m p l e xo c e a nc o n d i t i o n ，t h i sm e t h o dc a nb eu s e dt o 哈尔滨工程大学博士学位论文 d e a l 、订t ht h ea p p r o x i m a t ei n f o r m a t i o n a f t e ra n a l y s i so ft h er e l a t i o n s h i pa m o n g o c e a nc u r r e n t o b s t a c l e sa n da u v ，t h ed e r i v e df u z z yr u l e st a b l e sa r eu s e da sb a s i s o fl o c a lp a t hp l a n n i n g 删sm e t h o dc o n s i d e r sb o t ho c e a nc u r r e n te f f e c ta n d m o t i o nc h a r a c t e r i s t i c so fa u vp l a t f o r i l l t h u si tc a nw e l ls o l v et h el o c a lp a t h p l a n n i n gp r o b l e mc o n s i d e r i n go c e a nc u r r e n te f f e c ti nar e l a t i v e l ys i m p l ef o r m l o c a lm i n i m u mp r o b l e ma l s oa r i s e si nt h ea p p l i c a t i o no ff u z z yc o n t r o lt h e o r yt o a u vp a t hp l a n n i n g s oar e a l t i m ep a t hp l a n n i n gm e t h o db a s e do ns e n s o r i n f o r m a t i o ni sp r o p o s e d a n di te n a b l e sa u vt oe s c a p ef r o ml o c a lm i n i m u ms t a t e a n dc o n s e q u e n t l ya r r i v ea tt a r g e tp o s i t i o nb ys e t t i n gu pv i r t u a lt a r g e tp o i n t t o g e t h e rw i t ha c t i v a t i o na n de x i tc o n d i t i o no ff o l l o w - l e f t w a l lb e h a v i o ra n d f o l l o w - f i g h t - w a l lb e h a v i o r f o u r t h l y ，w ep r e s e n tam e t h o df o ra u t o m a t i cd e s i g no fr e a c t i v eb e h a v i o r b a s e do ns e n s o ri n f o r m a t i o n w h i c hr e g a r d sc o l l i s i o na v o i d a n c ep l a n n i n ga sa n i n t e g r a t e db e h a v i o rw i t h o u tt h en e e dt oc o n s i d e rh o wt od e c o m p o s eb e h a v i o r s q l e a r n i n gi su t i l i z e di nt h ei n d e p e n d e n tl e a r n i n ga b o u ta u v r e a c t i v eb e h a v i o rs 0 a st oo b t a i nt h ea n t i c i p a n to p t i m a lb e h a v i o r 砀ec o n t r o lr u l e se x t r a c t e da f t e r l e a r n i n gp r o c e s sc o m p l e t i o nc a nb ea p p l i e dt od i r e c tr e a c t i v eb e h a v i o r s i n a d d i t i o n ，af u z z yq ( 九) a l g o r i t h mi sp r e s e n t e do ns y s t e m sr e q u e s to fc o n t i n u o u s i n p u ta n do u t p u ts p a c e i tc o m b i n e sf u z z yt h e o r yw i t hql e a n i n g ，u t i l i z e sq ( a l g o r i t h mt ou p d a t er e s u l tv e c t o rw e i g h t sc o n t i n u o u s l yu n t i lt h e ya r ec o n v e r g e d ， t h e r e b y ac o m p l e t ef u z z yr u l eb a s ei sp r o d u c e d l a s t ，w ep u tf o r w a r dc o m p l e t ec o v e r a g ep a t hp l a n n i n ga l g o r i t h m s w e i g h t g r a d i e n tm e t h o da n de e l ld e c o m p o s i t i o nm e t h o da r ed e v i s e df o rb a s i cr e g i o n a s f o rc o m m o nr e g i o nt h a tc o n t a i n so b s t a c l e s ，t h ew h o l er e g i o ni sd i v i d e di n t o s e v e r a ls u b r e g i o n s a n dc e l ld e c o m p o s i t i o ns t r a t e g yb a s e do nc r i t i c a lp o i n t si s p r e s e n t e d a ni n o u tc r i t i c a lp o i n t sm a t c h i n ga l g o r i t h mi sp r o p o s e dt o t a c k l e t h ep r o b l e m sa r i s e nd u r i n ga d j a c e n c yg r a p hc o n s t r u c t i o n , w h i c hg u a r a n t e e st h e e n t i r es e a r c hf o ra l ls u b r e g i o n s i no r d e rt of o l l o wt h ep l a n n e dp a t h ap a t h f o l l o w i n gs t r a t e g yf o ra u vi sd e s i g n e dw h i c hc o n s i d e r sb c l t ht a s kr e q u i r e m e n t s a n da u vk i n e m a t i ca b i l i t yt oa c q u i r eo b j e c t i v ei n s t r u c t i o n so na u vm o v e m e n t e x p e f i m e n tr e s u l t so fa u ve x e c u t i o no fr e g i o nr e c o n n a i s s a n c et a s kv e r i f yt h e p r o p o s e da l g o r i t h mw h i c hm e e t st h er e q u i r e m e n t so fp r a c t i c a la p p l i c a t i o n k e y w o r d s ：a u v , p 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 , f u z z yl o g i c ，ql e a r n i n g ， c o v e r a g ep a t hp l a n n i n g ，p a t hf o l l o w i n g n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：嚎钿 日期：动7 年b 月占日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 回在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：移莉 日期：劢口9 年6 月t 6 日 导师( 签字) ： 拂试 协7 年俐日 第一章绪论 第一章绪论 作为人类探索海洋的工具，水下机器人是先进机器人技术在水下的特殊 应用，是机械学科与信息学科相结合的前沿技术领域。水下机器人的研究和 广泛应用对于充分利用自然资源，发展国民经济具有十分重要的现实意义。 水下机器人可以用于科学考察、深海探测、打捞沉船、旅游探险等，对海军 来讲，它最主要的任务是发现及排除水雷【l 】。当前水下机器人的种类很多， 其中遥控式水下机器人( r o y , r e m o t e l yo p e r a t e dv e h i c l e ) 、无人无缆水下机器 人删u n m a n n e du n d e r w a t e rv e h i c l e ) 、自主式水下机器人( a 吣 a u t o n o m o u su n d e r w a t e rv e k c l e l 是三类最重要的水下机器人1 2 3 】。 自主式水下机器人拥有多种感觉装置，具有自主导航和避障能力，并能 自主地完成某些特定的水下作业任务。它是含机械学、电子学、自动控制、 模式识别、计算机及人工智能等多种高技术的集成体。该领域的专家将体系 结构、任务规划、定位和导航、自主式作业、用户与机器人系统的接口、知 识表示和获取、传感器及传感器处理、三维图像感知等方面列为当前研究的 重点和热点。 1 1 研究背景 智能水下机器人技术是集水动力、系统集成与设计、仿真技术、智能控 制、声视觉和光视觉技术、信息融合与信息综合理解技术、导航技术、通信 技术等多学科于一体的新兴高科技项目。作为一种自主式海洋运载器，智能 水下机器人自主能力的真正含义是具有和外部环境进行交互的能力。这种交 互的一个重要方面就是具有全局路径规划以及突发事件下的动态重规划和 躲避障碍的能力。要实现水下机器人在水下的自主航行和自主作业，机器人 的路径规划是一个重要环节，路径规划水平的高低，在一定程度上标志着机 器人的智能水平，也是保证机器人安全可靠工作的关键。因此研究水下机器 人的路径规划技术对于提高水下机器人的智能化水平和加快工程化应用进 程具有重要的意义。本文以“十五”国防预研项目( 4 1 3 1 6 0 7 ) 和“十一五” 国防预研项目( 5 1 3 1 6 0 8 0 2 0 2 ) 为背景，对自主式水下机器人在海洋环境下 的全局路径规划技术、局部路径规划技术、避碰规划技术、区域探测路径规 哈尔滨工程大学博士学位论文 划技术进行了深入的研究，其研究成果直接应用于水下机器人的智能决策与 规划系统设计。 1 2 水下机器人研究现状 水下机器人的研究已经有二十多年的历史，许多沿海国家尤其是发达国 家都致力于水下机器人技术研究和产品开发。美国、加拿大、英国、日本、 俄罗斯以及中国等国家，都成立了专门的机构或者在高校里成立实验室研究 水下机器人技术。如美国的海军研究生院的自主式水下运载器研究中心、缅 因州立大学的海洋系统工程实验室和自治海下系统学院( a u t o n o m o u s u n d e r s e as y s t e m si n s t i t u t e ) ，英国的海事技术中，凸, ( 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 n l a b o r a t o r y ) ，我国的沈阳自动化研究所和哈尔滨工程大学水下机器人国防科 技重点实验室等。国际间成立的一些专业协会，如i e e e 海洋工程协会( i e e e o 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 d a 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 ) 美国海军研究生院自行设计和制造的a r i e s 水下机器人。它不仅具 有探测和识别水下目标的功能，还能够作为多水下机器人系统的协调控制中 心和网络数据的通讯站。 ( 2 ) 美国麻省理工学院开发的水下机器人o d y s s e yi i x 。它搭载有1 3 0 万 像素的摄像机和6 0 0 k h z 的侧扫声纳，主要用于海底地形测绘、海洋学研究。 ( 3 ) 美国n e wh a m p s h i r 大学研制的e a v e e a s t 自主式水下机器人。其 基于知识的系统分为高级与低级两部分，高级部分处理数据评价、状态评价、 监控和引导，低级部分实施管理、传感器管理和系统监视。 ( 4 ) 由美国w h o l ( w o o d sh o l eo c e a n o g r a h p h i ci n s t i t u t i o n ) 开发研制的 a b e 水下机器人能够在没有支持母船的情况，能较长时间地执行海底科学考 察任务，它与潜艇和r o v 一起，构成科学的深海考察综合体系。该深潜器 的最大潜深为6 0 0 0 米，最长考察距离约3 0 公里。 ( 5 ) 由美国w h o i 研发并由h y d r o i d 公司制造的r e m u s ( r e m o t e 2 第一章绪论 e n v i r o n m e n tm o n i t o r i n gu n i t s ) 水下机器人是商业化程度很高的水下机器人， 该系列包括r e m u s l 0 0 、r e m u $ 6 0 0 、r e m u $ 6 0 0 0 这3 种水下机器人，其 系列号分别代表其最大潜深。r e m u s 6 0 0 0 巡航速度续航能力2 2 小时，搭载 有a d c p 、c t d 、侧扫声纳、静物照相机等。 ( 6 ) 俄罗斯的m t - 8 8 是可以下潜6 0 0 0 米的预编程式水下机器人。它装 备的测量仪器有t v 和静物照相机。m t - 8 8 在海洋技术领域被赋予了很多的 工作。它是可预编程的，程序在水下机器人投放以前输入而且有声通讯校正。 ( 7 ) 日本东京大学浦环实验室开发的r z d 4 水下机器人。该水下机器入 作为r - o n e 系列水下机器人的后继机型，搭载有各种化学分析仪器，主要 用于深海以及热带海区矿藏的观测调查。 ( 8 ) 中国科学院沈阳自动化研究所与俄罗斯共同研制的“c r 0 1 ”水下机 器人在1 9 9 5 年和1 9 9 7 年两次在东太平洋的洋底，调查了大洋底部的锰结核 的分布与丰度情况，拍摄了大量的照片，获得了大量的洋底地形、地貌、地 质数据。“c r - 0 1 ”潜水器与俄罗斯的“m t - 8 8 ”潜水器在主尺度和外形上基本相 近，续航力也相近。 ( 9 ) 哈尔滨工程大学水下机器人实验室也正积极从事水下机器人的研发 工作。其研究工作主要包括水下机器人总体设计、水下机器人的智能规划算 法研究、水下机器人运动控制系统开发以及多水下机器人系统协调与控制 等，设计完成了多台水下机器人系统，成功地完成了多项海上试验。 水下机器人技术发展的总体趋向是提高自主能力，拥有较大的航程与续 航力，增加负载能力。在水下机器人系统硬件水平不断发展提高的同时，其 所赋予的使命任务对智能决策与规划技术提出更高的要求。 1 3 路径规划技术研究概况 路径规划自主式移动机器人的一个重要组成部分，它的任务就是在具有 障碍物的环境内，按照一定的评价标准，寻找一条从起始状态( 包括位置和 姿态) 到达目标状态( 包括位置和姿态) 的无碰路径1 4 。自2 0 世纪7 0 年代 以来，已相继提出了多种方法。无论采用何种方法，基本上都要遵循以下步 骤：建立环境模型，即将现实世界的问题进行抽象后建立相关的模型；全局 路径搜索方法研究，即寻找合乎条件的路径的算法；局部路径规划方法研究， 哈尔滨工程大学博士学位论文 即设计在线路径协调和避障的方法。 全局路径规划需要知道关于环境的所有信息，并产生一系列关键点作为 子目标点下达给局部路径规划系统，其规划路径的精确程度取决于获取环境 信息的准确程度。机器人在行走过程中，根据传感器的信息不断更新其内部 的环境信息，从而确定出机器人的当前位置及周围局部范围内的障碍物分布 情况，并在此基础上，规划出一条从当前点或某一子目标点到下一子目标点 的优选路径。 路径规划可以分为三种类型：基于环境先验完全信息的路径规划；基 于传感器信息的不确定环境的路径规划；基于行为的路径规划。 ( 1 ) 基于环境先验完全信息的路径规划 该方法也被称为全局路径规划，它能够处理完全已知环境中的移动机器 人路径规划。当环境发生变化，如出现未知障碍物时，该方法就不起作用了。 这种方法主要包括以下几种： 自由空间法 采用预先定义的如凸区法【5 1 、三角形法 6 1 、广义锥法【7 】等基本形状构造自 由空间，并将自由空间表示为连通图，通过搜索连通图来进行路径规划。该 方法比较灵活，起始点和目标点的改变不会造成连通图的重构，但算法的复 杂程度与障碍物的多少成正比，且不是任何情况下都能获得最短路径。为了 提高表示的效率，人们采用层次结构表示。自由空间法的另外一个缺点就是 只在二维空间下性能好，很难扩展到三维的工作环境，一旦扩展到三维的工 作环境，其复杂度和计算时间都会大为增加。 可视图法j 将移动机器人视为一点，把机器人、目标点和多边形障碍物的各个顶点 进行连接，要求机器人和障碍物各项点之间、目标点和障碍物各顶点之间以 及各障碍物顶点与顶点之间的连线，都不能穿越障碍物，这样就形成了一张 图，称之为可视图。由于任意两直线的顶点都是可视的，显然移动机器人从 起点沿着这些连线到达目标点的所有路径均是无碰路径。对可视图进行搜 索，并利用优化算法删除一些不必要的连线以简化可视图，最终可以寻找到 一条无碰最优路径。可视图法在障碍物比较密集的环境搜索时间长，虽然可 以求得最短路径，但缺乏灵活性。 结构空间法【l o 1 1 l 4 第一章绪论 结构空间是一种数据结构，移动机器人通过该数据结构来确定物体或自 身的位姿。结构空间表示法有许多种，最具代表性的是v o r o n o i 图法【1 2 l 和四 叉树及其扩展算法【1 4 】。v o r o n o i 图法的基本思想是：首先产生与环境障碍 物中所有边界点等距离的v o r o n o i 边，v o r o n o i 边之间的交点称之为v o r o n o i 项点。然后，移动机器人沿着这些v o r o n o i 边行走，不仅不会与障碍物相碰 撞，而且一定是在任意两个障碍物的中间。四叉树是一种递归网格，首先在 移动机器人所处环境上建立一个直角坐标网格，然后用大的网格单元对机器 人所处环境进行划分。倘若障碍物占用了网格单元的一个元素，则就把这部 分分割成四个网格( 四叉树) 。如果这四个网格中还有被占据的单元，则递 归地对该单元再分割成更小的四个子网格。 栅格法 栅格法将移动机器人工作环境分解成一系列具有二值信息的网格单元， 多采用二维笛卡尔矩阵栅格表示工作环境1 1 5 1 。每一个矩形栅格都有一个累积 值c v ，表示在此方位中存在障碍物的可信度，c v 值越高，表示存在障碍物 的可能性越高。用栅格法表示格子环境模型中存在障碍物可能性的方法起源 于美国的c m u 大学，通过优化算法在单元中搜索最优路径。由于该方法以 栅格为单位记录环境信息，环境被量化成具有一定分辨率的栅格。因为栅格 的大小直接影响着环境信息存储量的大小以及路径搜索的时间，所以在实用 上具有一定的局限性。 拓扑法 拓扑法是根据环境信息和运动物体的几何特点，将环境空间划分成若干 具有一致拓扑特征的自由空间。根据彼此间的连通性建立拓扑网，从该网中 搜索一条拓扑路径，即完成了路径规划的任务。该方法的优点在于因为利用 了拓扑特征而大大缩小了搜索空间，其算法复杂性只与障碍物的数目有关， 在理论上是完备的。但是，建立拓扑网的过程是相当复杂而费时的，特别是 当增加或减少障碍物时如何有效地修正已经存在的拓扑网络以及如何提高 图形搜索速度是目前亟待待解决的问题【l q 。但是针对一种环境，拓扑网只需 建立一次，因而在其上进行多次路径规划就可期望获得较高的效率。 动态规划法 动态规划法是解决多阶段决策优化问题的一种数值方法，它将复杂的多 变量决策问题进行分段决策，从而将其转化为多个单变量的决策问题。动态 哈尔滨工程大学博士学位论文 规划的基本原理为：作为整个过程的最优决策应该具有这样的性质，即无论 过去的状态或决策如何，对于当前的决策所形成的状态而言，后续的决策必 定构成最优策略。动态规划算法非常适合于机器人的全局路径规划。如何改 进动态规划的算法，以提高计算效率，是当前动态规划研究的一项重要内容。 神经网络 神经网络作为一个高度并行的分布式系统，具有很强的学习能力、非线 性映射能力和很高的自适应性、鲁棒性和容错性，被广泛应用于机器人导航 与路径规划等方面。可以利用神经网络来描述环境约束并计算碰撞能量函 数，将迭代路径点集的碰撞能量函数与距离函数的和作为优化目标函数，通 过寻优得出无碰撞路径【l 7 1 。基于神经网络和模拟退火算法( s i m u l a t e d a n n e a l i n ga l g o r i t h m ，s a a ) 的移动机器人全局路径规划方法，已有许多文献 提及1 8 , 1 9 ) 0 1 。引入s a a ，计算简单且能够避免局部极值的产生。但是，s a a 收敛速度相当慢，尤其是在普通p c 上运行时需花费大量机时。而基于自然 机理来提出新的优化思想是件极其困难的事情，因此围绕提高s a a 的收 敛速度，将s a a 与它算法混合的思想已发展成为提高s a a 优化性能的一个 重要而且有效的途径，其出发点就是使各种单一算法相互取长补短而产生较 好的优化效果，目前已经成为众多学研究的热点【2 l ，2 2 】。 遗传算法 遗传算法是目前机器人路径规划研究中应用较多的一种方法。孙树栋等 【2 3 】用遗传算法完成了离散空间下机器人的路径规划，并获得了较好的仿真结 果，但该路径规划是基于确定环境模型的。周明等【2 3 】提出一种连续空间下基 于遗传算法的机器人路径规划方法，该方法在规划空间利用链接图建模的基 础上，先使用图论中成熟算法粗略搜索出可选路径，然后再使用遗传算法来 调整路径点，逐步得到较优的行走路线。该方法的染色体编码不会产生无效 路径，但是该方法对于环境复杂、障碍物数目较多的情况，链接图的建立会 有一定的困难。后又对其改进提出一种遗传模拟退火算法，利用遗传算法与 模拟退火算法相结合来解决机器人路径规划问题。有效地提高了路径规划的 计算速度，保证了路径规划的质量。 ( 2 ) 基于传感器信息的局部路径规划 在多数情况下，局部路径规划的目的是要快速避开先前未知的障碍物， 在这方面，比较典型和有效的办法是人工势场法及从它衍生的雷达法等。很 6 第一章绪论 多研究人员都把各种含有学习的算法引入局部路径规划，如动态二叉树法 2 4 1 、遗传算法【2 3 1 、强化学习【2 5 1 等。从某种角度看，蚁群算法1 2 6 】也是一个具 有学习特性的算法。但带有学习性质的算法有些收敛速度慢，有些需进行多 次训练才能较好地解决路径规划问题。基于传感器的模糊控制方法与神经网 络控制方法，因其对硬件要求比较高，简单的配置不易使移动机器人实现快 速实时的运动规划1 2 7 。 人工势场法( a r t i f i c i a lp o t e n t i a lf i e l d ) 最初由k h a t i b 提出，这种方法由于它的简单性和优美性而被广泛采用。 其基本思想是把移动机器人在已知全局环境中的运动看作一种虚拟的人工 受力场中的运动。目标点对机器人产生引力作用，而障碍物对机器人产生斥 力作用，引力和斥力的合力控制机器人的运动。该方法结构简单，易于实现， 但是这种方法也存在着一些缺点，如：存在陷阱区、在相近的障碍物前不能 发现路径、在障碍物前产生振荡以及在狭窄通道中摆动等缺点【2 8 , 2 9 , 3 0 。针对 人工势场法的缺陷，国内外许多专家学者不断寻找新的途径，以克服该方法 所存在的弊端，如文献【3 l 】结合栅型声纳测试，试图建立一种新类型的势场 函数，为距离转换路径寻找算法。文献【3 2 】采用预测与势场法相结合的算法 解决移动机器人的导航问题，取得了良好效果。文献【3 3 】通过引入虚拟障碍 物使搜索过程跳出局部最优的陷阱，但引入虚拟障碍物可能会产生新的局部 极小点，同时也增加了算法的复杂度。文献【3 4 】提出了一种新的a p f 方法， 沿障碍物轮廓建立势场密度并设计q u a s i g e o d e s i c 方法用于静态或动态环境 下的避障，效果良好。 模糊逻辑算法 采用模糊控制方法建立规则，机器人直接由传感器得到的有限环境障碍 信息，根据预先建立的一些规则做出反应【3 5 1 。用这种方法实现的自主机器人 虽然智能程度较低，但具有很大的实用性，工程可实现性也较强。基于环境 反应的方法【3 6 1 ，不需要环境的数学模型来处理各种情况。该方法最大的特点 是参考人的驾驶经验，计算量不大，易做到边运动边规划，能够满足实时性 要求，克服势场法易产生的局部极点问题，效果比较理想。利用模糊逻辑解 决局部规划问题其原理就是根据总结的规则确定输出值。但该方法在复杂环 境中难构造出比较全面的规则库，且环境变化较大时，需耍花费大量时间来 调整和修改已构成的规则库，不具备适应能力1 3 。 7 哈尔滨工程大学博士学位论文 ( 3 ) 基于行为的路径规划方法