（机械电子工程专业论文）path+planning+for+an+autonomous+underwater+vehicle.pdf

r a t hp l a n n i n gf o ra na u t o n o m o u su n d e r 盯e rv e h i c l e 摘要 在近1 0 年中，各种科研组织和研究人员对在军事、海洋探测等方面具有非凡潜力 的水下环境研究表现出了极大兴趣，其目光已经从最初的近海探测发展到了现在的1 0 0 0 米以下深海资源开发。无人遥控潜器( r o v ) 作为水下环境最初的研究载体一直被人们 所使用并且得到了长足的发展，并且近几年自主式水下机器人( a u v ) 的出现更加丰富 了人们的探测手段。然而，复杂的水下环境以及人们对海洋资源越来越大的研究兴趣对 这些水下机器人的自主航行能力提出了更高的要求，其中如何使a u v 具备自主路径规划 能力从而避开障碍物顺利运行则是如何提高其自主航行能力所面临的首要问题之一。 本文集中讨论a u v 路径规划任务问题，即探讨如何使a u v 能够从当前任意位置顺利 地穿越复杂环境而达到指定目标位置。选择这条路径的目的是使a u v 能够以最佳的操纵 能力并且利用最短、最安全和最少消耗的航程绕过所有障碍物而到达指定位置，简而言 之就是选择一条使机器人拥有最少耗时和最佳效率的最优路径。虽然近几年许多解决路 径规划问题的方法已经提出，可是它们都具有这样或者那样的限制，使a u v 路径规划问 题始终没有一个完善的解决方案。 本文主要针对a u v 的平面路径规划问题。首先，为更加快捷地提取环境变化特征， 我们将障碍物简化为一个个平面上的多边形；接着利用融合了a 木搜寻算法的可视图方 法将a u v 的工作空间转换为行位空间以便产生一条最短的优化路径，使用这种组合方法 的优点是它提供了一个相对快捷和有效的途径来选择避开障碍物的安全路径。但是，由 此产生的机器人最短途径中其连续位置参数是参差不齐的，为减少这种位置跳变，本文 设计了一种针对a u v 的运动轨迹平滑器( 利用数据拟合技术) ，并详细列出了此平滑器 的设计参数。最终，本文综合以上设计步骤，提出了一种针对a u v 的最优路径规划方法。 利用本文所提出的路径规划方法可使a u v 有效达到自主航行的设计目标。为评定本 文路径规划方法的实际性能，本文利用m a t l a b 软件建立多种仿真环境并进行了仿真实 验。在仿真实验中，本文将水下机器人简化为一个多边形，而仿真实验结果也验证了本 文所提出的基于a ，i c 搜寻算法的a u v 路径规划方法在躲避障碍和优化时效等方面的有效 性和实用性。 关键词：路径规划；自主式水下机器人：可视图；胁算法 p a t hp l a n n l n gf o ra na u t o n o m o u su n d e r 岍rv e h l c l e a b s t r a c t i i lt h el a s t d e c a d e ，r e s e a r c h e r sa n do r g a n i z a t i o n sh a v es h o w ng r e a ti n t e r e s ti nt h e i n v e s t i g a t i o n o fu n d e r w a t e re n v i r o n m e n tf o r m a n ya p p l i c a t i o n ss u c ha sm i l i t a r y , o c e a n o g r a p h i cr e s e a r c h ，a n dm o r er e c e n t l yo f f s h o r ew i t ht h ed e s i r et oe x p l o i tn a t u r a l r e s o u r c e sa to v e r1 0 0 0m e t e r sd e e p r e m o t e l yo p e r a t e dv e h i c l e s ( r o v ) h a v el o n gb e e n d e v e l o p e da n dh a v eb e e ni nu s eb u tm o r er e c e n t l ya 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 ) h a v eb e e nd e s i g n e d t h en e e df o rh i g hc a p a c i t ya u t o n o m o u sn a v i g a t i o ni nt h ec l u t t e r e d u n d e r w a t e re n v i r o n m e n th a sn e c e s s i t a t e dt h ei n t e r e s tf o rm o r er e s e a r c hi n t ot h ep r o b l e m s f a c e db yt h e s ev e h i c l e s o n eo fs u c hp r o b l e m sf a c e db ya u v c o n c e r n sh o wt h ev e h i c l e s h o u l dh a v et h ea b i l i t yt op l a np a t h sa r o u n do b s t a c l e si no r d e rt os a f e l yo p e r a t e t h i st h e s i si sf o c u s e do nt h ep a t hp l a n n i n gm i s s i o n t h eo b j e c t i v e sa d d r e s s e dh e r ei st o e n a b l ea u vt ot r a v e r s ei t se n v i r o n m e n tf r o ma n yg i v e nc u r r e n tp o s i t i o nt oad e s i r e dg o a l p o s i t i o n t h ep a t ht ot h i sg o a ll o c a t i o nm u s te n h a n c ev e h i c l em a n e u v e ra r o u n da n yo b s t a c l e t or e a c ht h eg o a lt h r o u g ht h es h o r t e s t ，s a f e s t ，m i n i m a lc o s ta n do p t i m a lp a t hi nt e r m so ft i m e a n de n e r g yc o n s u m p t i o n m a n ya p p r o a c h e st os o l v et h ep a t hp l a n n i n gp r o b l e m sh a v eb e e n p r o p o s e di nr e c e n ty e a r s ，b u ta l lh a v el i m i t a t i o n so fo n ef o r mo rt h eo t h e r t h i st h e s i sf o c u s e so np l a n n i n gp a t h si na p l a n e h e r e ，i no r d e r t oe a s i l yt a k ei n t oa c c o u n t a n ym o d i f i c a t i o n o ft h ee n v i r o n m e n t ；w es i m p l yr e p r e s e n to b s t a c l e sa sp o l y g o n s f o r g e n e r a t i n ga no p t i m a ls h o r t e s tp a t hw eh a v et r a n s f o r m e dt h ew o r k i n gs p a c et ot h e c o n f i g u r a t i o ns p a c e ，u s i n gv i s i b i l i t yg r a p hm e t h o d sc o m b i n e dt oa 宰s e a r c ha l g o r i t h m t h e a d v a n t a g eo fu s i n gt h i sc o m b i n a t i o ni st h a ti to f f e r sar e l a t i v e l yf a s ta n de f f e c t i v ew a yt o s o l v ef o rs a f ep a t h sa r o u n do b s t a c l e s h o w e v e r , t h e r e s u l t i n gs h o r t e s tp a t h sf r o mt h e c o n s e c u t i v ep o s i t i o nt a k e nb yt h ev e h i c l ea r ej a g g e d t os o l v et h ej a g g e dp a t h s ，at r a j e c t o r y s m o o t h i n gc o m p o n e n t ( u s i n gp o l y n o m i a ld a t af i t t i n gt e c h n i q u e s ) i sd e v e l o p e d ；t h ep a r a m e t e r s a r es e ti nt h i st h e s i s t h e nb yc o m b i n i n ga l lt h o s ep r o c e s st h ep a t hp l a n n e ri sc r e a t e d t h er e s u l t i n gp a t hp l a n n e ri n t e g r a t e do n b o a r dt h ea u vi sa b l et oa c h i e v et h ep r o p o s e d m i s s i o n i no r d e rt oc a r r yo u ta na s s e s s m e n to ft h ep a t hp l a n n e r sp e r f o r m a n c e ，d i f f e r e n t v a r i a n t so ft h es i m u l a t i o ne n v i r o n m e n ta r ec r e a t e du s i n gm a t l a b i nt h i ss i m u l a t i o n ，t h e h a r b i ne n g l n e e r i n gu n i v e r s i t y v e h i c l ei sr e p r e s e n t e da sap o l y g o n t h er e s u l t i n gp a t h sg e n e r a t e dd e m o n s t r a t et h ee f f i c i e n c y o ft h ep a t hp l a n n e rb a s e do na 宰s e a r c ha l g o r i t h mf o ro b s t a c l ea v o i d a n c ea n do p t i m i z i n gt h e t i m ea n de n e r g yc o n s u m p t i o n k e y w o r d s ：p a t hp l a n n i n g ；a u t o n o m o u s u n d e r w a t e r v e h i c l e ；v i s i b i l i t yg r a p h ；a 枣 a l g o r i t h m l i s to ff i g u r e s f i g u r e1 1 ：o o d al o o p 4 f i g u r e1 1o o d al o o p 4 f i g u r e1 2p i c t u r eo fs e n t r y 5 f i g u r e2 1t o p o l o g i c a la n dg e o m e t r i cr e p r e s e n t a t i o n s ：】l o f i g u r e2 2v i s i b i l i t yg r a p h 1 1 f i g u r e2 3c o m p u t i n gt h em i n k o w s k is u mo ft w ot r i a n g l e s 1 3 f i g u r e2 4c o n s t r u c t i o no fc o n f i g u r a t i o ns p a c e 1 3 f i g u r e2 5o b t a i n i n gv i s i b i l i t yg r a p hw i t hr o t a t i o n a lp l a n e ss w e e pa l g o r i t h m 1 4 f i g u r e2 8p o t e n t i a lf i e l dm e t h o db e h a v i o r 1 5 f i g u r e2 9 ：p a t hp l a n n i n ga l g o r i t h mm o s tu s e d 1 8 f i g u r e2 9p a t hp l a n n i n ga l g o r i t h mm o s tu s e d 1 9 f i g u r e2 1 0g r e e d ya l g o r i t h m 1 9 f i g u r e2 1 1g r e e d ya l g o r i t h mg e t t i n gs t u c k 2 0 f i g u r e2 1 2d i j k s t r a sa l g o r i t h m 。2 1 f i g u r e2 1 3d i j k s t r a s e a r c hp a t t e r n 。2 2 f i g u r e2 1 4a 枣a l g o r i t h m 2 2 f i g u r e2 1 4a 掌a l g o r i t h m 2 2 f i g u r e2 1 5a 牛s e a r c hp a t t e r n 2 3 f i g u r e2 1 6d 幸a l g o r i t h mm a i nf u n c t i o n 2 5 f i g u r e3 1i n f o r m a t i o nr e q u i r e df o rae f f i c i e n tp a t hp l a n n e r 2 9 f i g u r e3 2p a t hp l a n n e rw o r k i n gp r o c e s s e sd e s c r i p t i o n 2 9 f i g u r e3 3c r e a t i o no ft h es h o r t e s tp a t h 3 0 f i g u r e3 4j a g g e ds h o r t e s tp a t h 3 2 f i g u r e3 5j a g g e dp a t hw i t he x t r ap o i n t s 3 7 f i g u r e3 6t y p i c a ls m o o t h e dp a t h 3 8 f i g u r e3 7 ：c o s tf u n c t i o ng ：l i n e a rc o m b i n a t i o no fta n dp h i t 4 0 f i g u r e3 7c o s tf u n c t i o ng ：l i n e a rc o m b i n a t i o no fta n dp h j tw i t hl t = 2 0 4 0 h a k b l ne n ( j i n e e r l n ou n i v e r s i t y f i g u r e3 8c o s tf u n c t i o ng ：r e s u l t e do fn o n l i n e a rc o m b i n a t i o no fta n dp h i t 4 1 f i g u r e3 9o b s t a c l eg r a p hu s e dt oc o m p u t et h ea 掌h e u r i s t i ch t h er e dp a t hi st h em i n i m u m c o s tr o u t et h o u g ht h eg r a p h 4 2 f i g u r e3 1 0a 木a l g o r i t h mf o rp a t hp l a n n e r 4 3 f i g u r e3 i i ：p a t hp l a n n e ra l g o r i t h md e s c r i p t i o n 4 4 f i g u r e4 1c o m p l e t ep a t hp l a n n i n gp r o c e s s 4 5 f i g u r e4 2g r a p h i c a lu s e ri n t e r f a c e 4 6 f i g u r e4 2g r a p h i c a lu s e ri n t e r f a c e 4 7 f i g u r e4 3s i m u l a t i o nr e s u l tw i t hf o u ro b s t a c l e so nt h ea r e a 4 9 f i g u r e4 4o p t i m a lp a t hr e s u l t e df r o mm i s s i o n 4 9 f i g u r e4 5 ( a ) d i s t a n c ep l o tv e r s u ss t e p s ；( b ) d i s t a n c ep l o tv e r s u st i m e 4 9 f i g u r e4 6 ：s i m u l a t i o nr e s u l tw i t he i g h to b s t a c l e so na r e a 5 0 f i g u r e4 6s i m u l a t i o nr e s u l tw i t he i g h to b s t a c l e so na r e a 5 0 f i g u r e4 7v e h i c l ep o s i t i o nt h r o u g ht h em i s s i o n 5 0 f i g u r e4 8 ( a ) d i s t a n c ep l o tv e r s u ss t e p s ；( b ) d i s t a n c ep l o tv e r s u st i m e 5 1 f i g u r e4 9s i m u l a t i o nr e s u l tw i t hl o n go b s t a c l e 5 1 f i g u r e4 1 0v e h i c l ep o s i t i o nt h r o u g ht h em i s s i o n 5 1 f i g u r e4 1 1 ( a ) d i s t a n c ep l o tv e r s u ss t e p s ；( b ) d i s t a n c ep l o tv e r s u st i m e 5 2 f i g u r e4 1 2 ：s i m u l a t i o nr e s u l to fc o n c a v e o b s t a c l e 5 2 f i g u r e4 1 2s i m u l a t i o nr e s u l to fc o n c a v eo b s t a c l e 5 3 f i g u r e4 1 3 ：p a t hg e n e r a t e df r o mm i s s i o n 5 3 f i g u r e4 1 3p a t hg e n e r a t e df r o mm i s s i o n 5 3 f i g u r e4 1 3 ：( a ) d i s t a n c ep l o tv e r s u ss t e p s ；( b ) d i s t a n c ep l o tv e r s u st i m e 。5 3 c h a p t e r1i n t r o d u c 兀o n c h a p t e r1i n t r o d u c t i o n t h eo b j e c t i v eo ft h i st h e s i si sc o n c e r n e dw i t h d e v e l o p m e n to fp a t hp l a n n i n gf o r 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 i nt h i sc h a p t e r a f t e rm e n t i o n i n gt h ep r o b l e ms t a t e m e n t ， m o t i v a t i o na n dab r i e f d e s c r i p t i o no 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 ，w ew i l l 酉v et h e s o l u t i o no ft h ep r o b l e mi ns u c ho fw a yt h a ta l l o w sas u c c e s s i o no fn e t w o r ks h o r t e s tp a t h st o m e e tt h ed e s i r e dg o a l so ft h ep a t hp l a n n e r 1 1p r o b l e ms t a t e m e n t t h ei n v e s t i g a t i o no ft h eu n d e r w a t e re n v i r o n m e n ti sac a ) n c e mi nm a n ya r e a ss u c ha s o c e a n o g r a p h i cr e s e a r c h ，m i l i t a r ya p p l i c a t i o n s ，a n dm o r er e c e n t l yo f f s h o r ew i t ht h ed e s i r et o e x p l o i tn a t u r a lr e s o u r c e sa to v e r1 , 0 0 0m e t e r sd e e p t h ea u t o m a t i o no fi n s p e c t i o nt a s k s ， r e c o g n i t i o n ，d e t e c t i o no rm e a s u r e m e n to fp h y s i c - c h e m i c a lp a r a m e t e r si sh i g h l yw a r r a n t e di n t h i sv a s te n v i r o n m e n tt o oh o s t i l et oh u m a n s t h eu s eo fr e m o t e l yo p e r a t e dv e h i c l e si nt h e s e a r e a si so l da n dw a st h ef i r s tt e c h n i q u ed e v e l o p e dt oe x t e n tt h a tt h em a ni n v o l v e di nt h e d e c i s i o nc h a i nm a k i n g t h ep r o b l e mt h a tw ea r ef a c i n gi sh o wt or e d u c eh u m a ni n t e r v e n t i o n “i nt h el o o p ”s i n c e t h el a t e8 0 s ，m a n yr e s e a r c hp r o g r a m sh a v ee m e r g e di nt h eu n i t e ds t a t e s ，e u r o p ea n da s i a ，t o p r o v i d eas o l u t i o nb a s e do na u t o n o m o u sv e h i d e s i ti si nt h i sw a yt h a tr e s e a r c h e r sh a v e d e s i g n e d 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 s ) t h i st y p eo fv e h i c l ei sf a c i n gf o u rm a j o rs c i e n t i f i cp r o b l e m sa sf o l l o w s ：e n e r g ya u t o n o m y , n a v i g a t i o nc o u p l e dw i t ht h ep r o b l e mo fp o s i t i o n i n ga n dd e c i s i o n - m a k i n ga u t o n o m y o u r w o r kw i l lb eap a r to ft h ep r o b l e mo fn a v i g a t i o na n dc a nb eb r o k e nd o w ni n t ot h r e em a i n a s p e c t s ：v e h i c l ec o n t r o l ，p a t hp l a n n i n g ，a n do b s t a c l ea v o i d a n c e t h ef i r s tt o p i cw a s e x t e n s i v e l ya d d r e s s e d 【1 1 t h eo t h e rt w ot h e m e sa l et h es u b j e c to fm a n yr e s e a r c h e sa n dt h e r e a r es p e c i f i cp r o b l e m so ft h i st h e s i s 1 2m o t i v a t i o n o c e a nc o v e r sa p p r o x i m a t e l y7 1 o fe a r t h ss u r f a c e ，a n dm o r et h a nh a l fo ft h i sa r e ai s o v e r3 , 0 0 0m e t e r sd e e p i nt h el a s tc e n t u r yt h en e e dt ou n d e r s t a n d i n ga n dm a n a g i n go u r h a r b i ne n g i n e e r i n gu n l v e r s l i 。y p l a n e th a sr e s u l t e d i n u n p r e c e d e n t e di n t e r e s ta n da t t e n t i o nb e i n gf o c u s e do nu n d e r w a t e r r e g i o n n o w a d a y s ，i sn o to n l yt h en e e dt ou n d e r s t a n db u t ，a l s ot oe x p l o r e ，m a p ，s u r v e y , i n s p e c ta n dc o n s t r u c tu n d e r w a t e rs t r u c t u r e st h a tm o t i v a t eu n d e r w a t e re n v i r o n m e n tr e s e a r c h t h u ss e v e r a lm a r i t i m ed i s c i p l i n e sa n da p p l i c a t i o n sh a v ee m e r g e dw i t h i nt h ee n v i r o n m e n t ，t h e m o s tr e l e v a n to n e sa r e ： ( 1 ) c o m m e r c i a l ：t h ec o m m e r c i a l ( o i la n dg a si n d u s t r y ) u s eo fa u v sg e n e r a l l yd e a l w i t hd e t a i l e dm a p p i n go ft h es e a f l o o rf o rb u i l d i n gs u b s e ai n f r a s t r u c t u r e ；p i p e l i n e sa n ds u b s e a c o m p l e t i o n sc a nb ei n s t a l l e di nt h em o s tc o s te f f e c t i v em a n n e rw i t hm i n i m u md i s r u p t i o nt o t h ee n v i r o n m e n t t h ea u va l l o w ss u r v e yc o m p a n i e st oc o n d u c tp r e c i s es u r v e y so ra r e a s w h e r et r a d i t i o n a lb a t h y m e t r i cs u r v e y sw o u l db el e s se f f e c t i v eo rt o oc o s t l y a l s o ，p o s t l a y p i p es u r v e y s a r en o w p o s s i b l e ( 2 ) m i l i t a r ya p p l i c a t i o n ：f o rm i l i t a r y , a u v sa r eg e n e r a l l y u s e dt om a pap a r t i c u l a ra r e a f o rm i n e so ra n yu n i d e n t i f i e do b j e c t a u v sa r ea l s ou s e df o rs u r v e i l l a n c eo fp o r t sa n d c o a s t a l a r e a s t h e ya r ea l s oe m p l o y e df o rd e t e c t i n gs u b m a r i n e sa n d a sa n t i s u b m a r i n ew e a p o n s ( 3 ) m a r i n es c i e n c e ：m a r i n es c i e n c e ，a l s oc a l l e do c e a n o g r a p h yi st h ee a r t hs c i e n c e t h a ts t u d i e st h eo c e a n s c i e n t i s t sa r ef a c e dt of i n di n f o r m a t i o ni nd e e p e s tp a r to fo c e a ni n o r d e rt ob ea b l et ou n d e r s t a n da n dp r e v e n tn a t u r a ld i s a s t e rs u c ha st s u n a m i sa n dc l i m a t e c h a n g e a u v sh a v es e v e r a lt y p e so fs e n s o r s a t t a c h e dt ot h e i rb o d yt h a th e l pi nc o l l e c t i n g d i f f e r e n td e t a i l so ft h eu n d e r w a t e rl i f ea n ds e a b e d u n f o r t u n a t e l y , o c e a n st w ot h i r d so ft h et o t a le a r t h ss u r f a c ei s h o s t i l er e g i o n ，p r o n et o c u l l r e n t s 锄dd i f i c l l nt 0c o m m u i l i c a t eb e c a u s eo fl o wb a n d w i d t hc h a n n e l su n d e r s e a 2 1 t h e a c c e s st ot h e s er e g i o n si sn o ts t r a i g h t f o r w a r da n dv e r yd a n g e r o u sf o rh u m a nb e i n g s t o p r e v e n th u m a n sl i v e ，c u r r e n ts t a t eo ft e c h n o l o g ya l l o w sm a n yl a b o r a t o r i e s t od e v e l o pa n d d e s i g na u t o n o m o u ss y s t e m ，t or e d u c e t h e i rd e p e n d e n c eo nt h e “h u m a ni nt h e l o o p ” 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 l w s ) a t ev e h i c l e st h a tc a np e r f o r md e s i r e dt a s k sw i t h o u t h u m a nb e i n g sh e l p ，a l l o w sf o ra c c e s si nh i g h e rr i s ka r e a s ，l o n g e rt i m eu n d e n a t e r a n dm o r e e f f i c i e n te x p l o r a t i o na sc o m p a r e dt oh u m a no c c u p i e dv e h i c l e ，b u tt h o s e v e h i c l e sh a ss t i l l d e a l i n gw i t hp r o b l e m ss u c h ，p o w e r , p e r c e p t i o n ，n a v i g a t i o na n d d e c i s i o nm a k i n g w ew i l lf o c u si nt h en e x tp a g e st ot h ep r o b l e m so fn a v i g a t i o n ，e s p e c i a l l yt op a t hp l a n n i n g 2 c h a p t e r1l n t r o d u c r i o n p r o b l e m p a t hp l a n n i n gi sa l li m p o r t a n ti s s u ef o ra u t o n o m yo ft h ev e h i c l e s ，b e c a u s e # v e nt h e s t a r tp o s i t i o no ft h ev e h i c l e sa n dg o a lp o s i t i o n ，a u t o n o m o u su n d e r w a t e rv e h i c l en e e d st o d i s c o v e rh o wt ot r a v e r s ei t se n v i r o n m e n t ( w h i c ho n ei sc o m p o s e do fas e to ft h r e a t sa n d o r o b s t a c l e s ) t ot h eg o a lp o s i t i o n t h i sp r o b l e mi st o p o l o g i c a l l yr e l a t e dt ot h es h o r t e s tp a t h p r o b l e mo ff i n d i n gar o u t eb e t w e e nt w on o d e si nag