（机械制造及其自动化专业论文）path+planning+of+mobile+robot+in+rough+terrain.pdf

摘要 本文对崎岖地面上移动机器人的路径规划问题进行了研究。课题主要研 究内容包括：第一，崎岖地面模型的建立；第二，机器人在崎岖地面上的路 径规划算法的研究。路径规划方案使得机器人在三维崎岖地面上能够有效的 从当前位置规划出一条到达目标点位置的最短、最安全和代价最小的路径。 在三维崎岖地面建模中，引入了d e l a u n a y 三角剖分算法对地面模型进行 剖分，采用b 样条曲线对三维地面进行了光滑处理，从而使模型更加接近 真实崎岖环境在此模型的基础上，本文采用d i j k s 吼算法对三维崎岖地面 上机器人静态导航进行了研究。影响路径规划目标函数的变量主要有三个， 这是个多变量问题，各个变量之间相互独立，分别表征机器人在崎岖地面 上的通过能力。 本文通过仿真对提出的三维地面上机器人路径规划算法进行了验证，仿 真结果表明该算法能够有效的对路径进行优化，其避障能力强、消耗时间 短，同时机器人能量消耗最小 关键词：路径规划，成本函数，三维地形建模：崎岖地形；三角b 样条。 a b s l r a c t t h i st h e s i sp r e s e n t sas t u d yo fa u t o n o m o u sm o b i l er o b o tp a t hp l a n n i n gf o r r o u g ht e r r a i n i tf o c u s e s t e r r a i nm o d e l i n ga n dd e v e l o p m e n to fa l g o r i t h m sf o r d e t m go p t i m a lp a t hf o rar o b o tt on a v i g a t et h r o u g hr o u g ht e r r a i n 。ag o o d p a t hp l 锄p r o v i d e st h er o b o tw i t ht h es h o r t e s t , s a f e s t , a n d 加i n j m 啪c o s tp a t h , i n t e r m so f e n e r g ya n dt i m e ，t or e a c hd e s i r e dg o a lf r o mi t sp r e s e n tp o s i t i o n a d e l a u n a yt r i a n g u l a t i o nm e t h o dw a su s e df o rm o d e l i n gt h et e r r a i ni nt h r e e d i m e n s i o n s i na d d i t i o n , au n o o t h i n gp r o c e s sd e v e l o p e db yt h em e t h o do f t r i a n g u l a rb - s p l i n e st ot h er e a l t e r r a i nm o d e lw a sa p p l i e d d i j k s t r a sa l g o r i t h mw a s s e l e c t e df o rt h ep r o b l e mo fp a t hf m d m gi n3 dt e r r a i nu n d e rc o n d i t i o n so fs t a t i c n a v i g a t i o n t h ec o s tf u n c t i o nd e v e l o p e dc o n s i s t so ft h r e em a i np a r a m e t e r st h a t a f f e c tt h ec a l c u l a t i o n ；a n di tw a st r e a t e da sm u l t i v a r i a b l e t h em a g n i t u d eo fe a c h v a r i a b l ed i f f e r sf r o mo n et oa n o t h e r w ep r o p o s e dam e t h o df o rs e l e c t i n g w e i g h i n gf a c t o r sb o u n dp a r a m e t e r s as i m u l a t i o no ft h ep a t hd e v e l o p e dd e m o n s t r a t et h eo p t i m a l i t yi ns e l e c t i o no f t h e 如。矗m m ，w e ! i g h t m gf a c t o r s , o p t i m a l i t yi np a t hd e v e l o p e d , b i gc a p a c i t yi n o b s t a c l e sa v o i d i n ga n dm i n i m u m 劬ca 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 ；c o s tf u n c t i o n ；w c i g h t m gf a c t o r s ；r o u g ht e r r a i n ； 位i a n s u l a rb - s p l i n e ； 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 l i s to ff i g u r e s h g u r e2 1i n c o m p l e t e n e s so f a p p r o x i m a t ec e l ld e c o m p o s i t i o n 1 0 h g u r e2 2a ) aq u a d t r e e b ) af r a m e do u a d t r e e 1 0 h g u r e2 3p o l y g o n a ld e c o m p o s i t i o n 11 h g u r e2 4av i s i b i l i t yg r a p h 1 3 h g u r e2 5a v i s i b i l i t yg r a p h 1 3 h g u r e2 6v o r o n o id i a g r a m s 1 3 h g u r e2 7p r mw i t hr a n d o m l yc h o s e nn o d e s 1 4 h g u r e2 8ap o o r l yc o v e r e da n daw e l l - c o v e r e dp r m 1 5 h g u r e2 9r a p i d l ye x p l o r i n gr a n d o mt r e e s ( r r t ) 1 6 f i g u r e2 1 0p r o c e s so fd e v e l o p i n go f p a t hp l a n n i n ga l g o r i t h mi nr o u g ht e r r a i n 1 7 f i g u r e2 1 1g r a p hs e a r c h 心r i t h m sm o s tu s e di np a t hp l a n n i n g 1 8 f i g u r e2 1 2a ) t e r r a i ni n c l i n a t i o ni n d e x , b ) t e r r a i nr o u g h n e s s 2 1 f i g u r e 2 1 3 t o p o l o g i c a l a n d g e o m e t r i c r e p r e s e n t a t i o n s 2 3 f i g u r e2 1 4t h r e e d i m e n s i o nt e r r a i nm o d e l i n gc l a s s i f i c a t i o n s 2 6 f i g u r e3 1t h ed e l a u n a yt r i a n g u l a t i o no fas e to fp o i n t sa n d t h ev o r o n o id i a g r a m 2 9 f i g u r e3 2t r i a n g u l a t i o n sg e n e r a lp r o c e s s 2 9 f i g u r e 3 5 t h r e e d i m e n s i o n t e r r a i n s m o d e l u s e d 3 2 f i g u r e3 6t h r e e d i m e n s i o nt e r r a i nm o d e lt r i a n g u l a t i o n 3 3 f i g u r e3 7t h r e e d i m e n s i o nt e r r a i ns m a l lt r i a n g l em o d e l i n g 3 4 f i g u r e 3 8 t r a n s f o r m a t i o n o f t r i a n g l e m o d e l t o t r i a n g u l a r b - s p l i n e m o d e l 3 5 f i g u r e3 9ac h a i no fb s p l i n es e g m e n t s 3 6 f i g u r e3 1 0t h r e e d i m e n s i o nt e r r a i nm o d e l e di nt r i a n g u l a rb - s p l i n em e t h o d 3 7 f i g u r e4 1d i r e c t e dg r a p h 4 0 f i g u r e4 2d i a g r a mo ft h ed u k s t r ag r a p hs e a r c ha l g o r i t h m 4 1 h g u r e4 3s t e pb ys t e po p e r a t i o no fd u k s t r a s 心r i t h m 4 2 f i g u r e4 4p a t hd e v e l o p e db yd i j k s t r a sa i x 3 0 r i t h m 4 3 f i g u r e4 5t e r r a i nr o u g h n e s s 4 4 f i g u r e4 6t e r r a i nr u g g e d n e s sm o v i n gw i n d o w s 4 6 f i g u r e4 7t e r r a i nr u g g e d n e s sc a l c u l a t i o n s 4 6 f i g u r e5 1d i s t a n c e st r a v e r s e df o rd i f f e r e n tv a l u eo fw e i g h t i n gf a c i d r 5 0 f i g u r e5 2r o b o tp a t hd e v e l o p e df o rd i f f e r e n tc o s tf u n c t i o n sa n dd i f f e r e n tt e r r a i n m o d e l s 5 1 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 f i g u r e5 3d i s t a n c e st r a v e r s e df o rd i f f e r e n tv a l u eo fw e i g h t i n gf a c t o r 口2 5 4 f i g u r e5 4r o b o to p t i m u mp a t hd e v e l o p e df o rd i f f e r e n tc o s tf u n c t i o n 5 5 h g u r e5 5r o b o ta v o i d i n go b s t a c l e sa n dc a v i t yw i t ht h eg l o b a lc o s tf u n c t i o n 5 5 l i s to ft a b l e s t a b l e2 1s t r e n g t ha n dw e a k n e s so fa l g o r i t h m su s e dn 、| p a t hp l a n n i n g 2 0 t a b l e2 2p a r a m e t e r sa f f e c t i n gc a l c u l a t i o no fc o s tf u n c t i o n 。2 2 t a b l e3 1r a n d o mt e r r a i nm a t r i xc o o r d i n a t em o d e l 3 3 t a b l e3 2m o d e l i n gt r i a n g i e sa n dp o i n t sn u m b e r 3 4 t a b l e5 1p a t hd e v e l o p e df o rt r i a n g u l a ra n dt r i a n g u l a rb - s p l i n et e r r a i nm o d e l s 5 2 t a b l e5 2v a r i a t i o no fd i s t a n c et r a v e r s e db yt h er o b a t 玎、| 只j n c 玎o no fw e i g h l l n g f a c t o r 2 5 4 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 1 1i n t r o d u c t i o n c h a p t e r ii n t r o d u c t i o n t e c h n o l o g i c a la d v a n c e so ft h el a t et w e n t i e t hc e n t u r yh a v ee n a b l e dr o b o t st o m o v ef r o ms i m p l ea u t o m a t e ds y s t e m st oa m a c h i n e ”i n t e l l i g e n t ”a b i l i t yt oi n t e r a c t w i t ht h e i re n v i r o n m e n ta n dp e r f o r mc o m p l e xt a s k s t h er o b o t sh a v ec a p a b i l i t i e so f p e r c e p t i o na n dr e a s o n i n ga n dt h e f ts c o p ei ss t i l lw i d e r t h i st h e s i sd e a l sw i t hm o b i l er o b o t sd e s i g n e dt op e r f o r mt a s k si nd i f f i c u l ta n d u n f a m i l i a re n v i r o n m e n t si nw h i c hc o m m u n i c a t i o n sw i t ht h ee x t e r n a ld o o r sa l e d i f f i c u l t i nt h i sc o n t e x t ，w ef i n ds o m ea p p l i c a t i o n so fm o b i l er o b o t s ，f o re x a m p l e ： - t h e e x p l o r a t i o no fs p a c e ； - m i n i n gr o b o t s ； - i ns i t e h a z a r d o u s ； - c l e a r a n c e ； ac o m m o nf e a t u r eo ft h e s ea p p l i c a t i o n si st h a tt h er o b o tm o v e si nc o m p l e x t e r r a i nt h a tm a yb cr o u g h ，u n e v e n ，s l i p p e r ya n ds o m e t i m e sn o ta c c e s s i b l et om a i l t os o l v et h i sp r o b l e m ，t h er o b o tm u s tb ee n d o w e dw i t hc a p a c i t i e so fa u t o n o m y a l l o w i n gi tt oa c tw i t h o u tt h ei n t e r v e n t i o no fa no p e r a t o r t h i sl e v e lw h e nt h e r o b o ti sc o n t r o l l e da n dd i r e c t e dt h r o u g has e to fi n s t r u c t i o n s ( ”g ot ot h i sp l a c e ， ”s e a r c ho b j e c t ”e t c ) i sr e f e r r e dt oa sr e m o t e p r o g r a m m i n gt a s kl e v e l i nt h i sw o r k ，w ea r e p a r t i c u l a r l y i n t e r e s t e di nt h ed i s p l a c e m e n t so fa n a u t o n o m o u sm o b i l er o b o to nu n e v e nt e r r a i n t h er o b o tm u s tf u l f i l li t so w n p u r p o s e ss p e c i f i e di nt h ee n v i r o n m e n tb yt h eo p e r a t o ri na v o i d i n gi m p a s s a b l eo r d a n g e r o u sa r e a st h a tw o u l dj e o p a r d i z ei t sm i s s i o n i ti st h e r e f o r en e c e s s a r yt oh a v e ar e p r e s e n t a t i o no ft h ee n v i r o n m e n tt op l a na p a t ht h a ti se x e c u t a b l eb yt h er o b o t a l l o w i n gi tt or e a c hi t sg o a l t h ep r o b l e mo fp a t hp l a n n i n go fm o b i l er o b o t si n r o u g ht e r r a i nc o n s i s t so fs e l e c t i n gt h eg e o m e t r i cp a t ha n dv e h i c l em o d e l ，t oa v o i d o b s t a c l e sa n dt om i n i m i z es o m ec o s tf u n c t i o ns u c ha st i m eo re n e r g yc o n s u m p t i o n w h i l ee x t e n s i v ew o r kf o c u s e do nc o m p u t i n gt h eg e o m e t r i cp a t hf m d i n g f o rt h i s ， w ef i r s tn e e dt om a k ead i f f e r e n c eb e t w e e np a t hp l a n n i n gi nr o u g ht e r r a i na n d 2 p a t hp l a n n i n go fm o b i l er o b o ti nr o u g ht e r r a i n p l a n n i n gi nw e l l s t r u c t u r e de n v i r o n m e n t s i nr o u g ht e r r a i n ，t e r r a i nd a t ac a n n o tb e a s s u m e dt ob ep e r f e c t l yk n o w n ，d u et oe r r o r 8i nr a n g es e n s i n gt e c h n i q u e sa n d s e n s o r sm i s c a l i b r a t i o n t h ep l a n n e dp a t hm a yn o tb ea c c u r a t e l yf o l l o w e db yt h e r o b o td u et os i g n i f i c a n tp a t hf o l l o w i n ga n dl o c a l i z a t i o ne r r o r s i nr o u g ht e r r a i n ，t h e c o n c e p to fa no b s t a c l ei sn o tc l e a r l yd e f i n e d ，a si td e p e n d so na nu n d e r s t a n d i n g o f t h et e r r a i na n dt h em o b i l i t yc h a r a c t e r i s t i c so ft h er o b o t g r o u n de x p l o r a t i o n s y s t e m sw i l lg e n e r a l l yh a v el i m r e dc o m p u t a t i o n a lr e s o u r c e st od e v o t et op a t h p l a n n i n g m o r e o v e r ，i np a t hp l a n n i n gi nr o u g h t e r r a i nw en e e dt oc o n s i d e r ： 1 p a t h p l a n n i n ga l g o r i t h m sf o rm o b i l er o b o t si nr o u g ht e r r a i nm u s te x p l i c i t l y c o n s i d e rt h er o b o tt e r r a i ni n t e r a c t i o n i na d d i t i o n ，t h er o u g ht e r r a i np a t hp l a n n i n g a l g o r i t h m sm u s tc o n s i d e rr e a l - w o r l di m p l e m e n t a t i o ni s s u e 2 r o u g ht e r r a i np a t hp l a n n i n ga l g o r i t h m sm u s tc o n s i d e ru n c e r t a i n t yi n h e r e n t i nt e r r a i ns e n s i n gs y s t e m ss u c ha sr a n g e f i n d e r s 1 2b a c k g r o u n d ，o b j e c t i v ea n ds c o p eo fw o r k p a t hp l a n n i n go fm o b i l er o b o t si nr o u g ht e r r a i ng i v e su sm o r eo p p o r t u n i t yf o r c o n t a c tw i t hn a t u r et h a to b l i g e su st oh a v eg o o dk n o w l e d g ew i t ht h ei n t e r m e d i a r y t or e a c ho u rg o a l r o u g ht e r r a i np a t hp l a n n i n ga l g o r i t h m sm u s tc o n s i d e rr e a l - w o r l di m p l e m e n t a t i o ni s s u e p l a n n i n ga l g o r i t h m sm u s ta c c o u n tf o rt h ef a c tt h a tt h e m o b i l er o b o tc a n n o tp r e c i s e l yt r a c kap l a n n e dp a t hd u et ot h ep a t h - f o l l o w i n g e r r o r s t h eo b j e c t i v e so ft h es t u d ya r e 1 d e v e l o p i n ga3 一dm o d e lo fr o u g ht e r r a i nf o rp l a n n i n gt h ep a t ho ft h e m o b i l er o b o t ( g r o u n dm o d e ls h o u l db et h ec l o s e s tm o d e lt or e a lo n e ) 2 f i n d i n ga n dp l a n n i n gam o b i l er o b o tp a t hi nar o u g ht e r r a i nf r o mag i v e n s t a r tl o c a t i o nt oa g i v e ng o a ll o c a t i o nb a s e do nt h e3 一dt e r r a i nm o d e ld e v e l o p e d 3 d e v e l o p i n ga n dp e r f o r m i n gap a t hp l a n n i n ga l g o r i t h mc o s tf u n c t i o n 4 t oi m p r o v eo u rm e t h o dt oe n s u r eo p t i m a l i t y ：r e q u i r e m e n t sc a nb eb a s e d o nm i n i m u md i s t a n c et r a v e l e d ，t i m et a k e n ，v e h i c l es a f e t ya n de n e r g yc o n s u m e d 3 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 1 3a r r a n g e m e n to ft h et h e s i s t h e r ea r ef i v ec h a p t e r si nt h et h e s i sr e p o r t c h a p t e r2p r o v i d e st h er e v i e wo f l i t e r a t u r eo ng r o u n dm o d e l i n g ，p a t hp l a n n i n g ，g r a p hs e a r c ha l g o r i t h m ss u r v e y ，a n d s o m ec o s t sf u n c t i o n su s e di np a t hp l a n n i n g c h a p t e r3d e a l sw i t hd e v e l o p m e n to f r o u g ht e r r a i ng e o m e t r i cm o d e lb a s e do nd e l a u n a yt r i a n g u l a t i o nm e t h o da n d p e r f o r m i n gt h eg r o u n dm o d e lb yi n t e g r a t i o no fb - s p l i n es m o o t h i n gs u r f a c e si nt h e g r o u n dm o d e l c h a p t e r4 d e s c r i b e st h ed e t a i ls t u d yo fs e l e c t i o na n du s eo fd i j k s t r a p a t hp l a n n i n ga l g o r i t h mt of i n da no p t i m u mp a t hf r o mag i v e ns t a r tl o c a t i o nt oa g i v e ng o a ll o c a t i o n ，t h e nd e v e l o p i n gan e wc o s tf u n c t i o ni n t e g r a t e di nd i j k s t r a a l g o r i t h mt op e r f o r mt h ep a t ha n do b t a i no p t i m u mr e s u l t s c h a p t e r5p r e s e n t s ， m a t l a bs i m u l a t i o na n dr e s u l t so fd i f f e r e n tg r o u n dm o d e l sw i t hp a t ha l g o r i t h m u s i n gd i f f e r e n tf o r m u l ao fc o s tf u n c t i o n i nt h i sc h a p t e r ，w ed i s c u s si n f l u e n c eo f g r o u n dm o d e l i n gi np a t ha l g o r i t h m ，p a t hc o s t sa n di t si n f l u e n c ei no p t i m a l i t y s e c o n d l y ，w ea l s os t u d yt h ei n f l u e n c eo fm o d i f i c a t i o no fc o s tf u n c t i o ni np a t h c h a n g i n g a tt h ee n d ，w ed i s c u s sa b o u tt h er e s u l t so b t a i n e d , c o n c l u s i o n ，f u t u r ew o r k p u b l i c a t i o na n da c k n o w l e d g e m e n t 4 p a t hp l a n n i n go fm o b i l er o b o ti nr o u g ht e r r a i n c h a p t e r2l i t e r a t u r er e v i e w i nt h i sc h a p t e r ，w ep r e s e n tt h ep r o b l e mo fp a t hp l a n n i n gf o ram o b i l er o b o to n a nu n e v e nt e r r a i n t h ef i r s t p a r tr e c a l l st h eb a s i cn o t i o n so fp a t hp l a n n i n ga n d p r e s e n t st h em a i nm e t h o d so fa m o b i l er o b o ti nan a t u r a le n v i r o n m e n ta n dm a k i n g ac o m p a r i s o nb e t w e e nt h e s em e t h o d s s u b s e q u e n t l yw ep r e s e n tt h ep r o b l e mo f s e l e c t i o no ft h eo b j e c t i v ef u n c t i o n ，w h i c ha l s oc o m p a r e d ( c o s tf u n c t i o n s ) t h e nw e p r e s e n tw o r l dr e p r e s e n t a t i o nf o rp l a n n i n ga n dd i f f e r e n tm e t h o d su s e di nr o u g h t e r r a i nm o d e l i n g 2 1p a 恤p l a n n i n ga l g o r i t h m su s e di nr o u g ht e r r a i n t h ep r o b l e mo fp a t hp l a n n i n go fm o b i l e sr o b o t si nr o u g ht e r r a i nc o n s i s t so f s e l e c t i n gt h eg e o m e t r i cp a t ha n dv e h i c l em o d e l 【6 4 5 , 4 6 , 4 8 ，4 9 1 ，t oa v o i do b s t a c l e s a n dt om i n i m i z es o m ec o s tf u n c t i o ns u c ha st i m eo re n e r g yc o n s u m p t i o n w h i l e e x t e n s i v ew o r kf o c u s e do nc o m p u t i n gt h eg e o m e t r i cp a t h f i n d i n g 1 1 2 4 j ，8 ，7 9 1 0 1 1 1 2 ，1 3 1 f o rt h i s ，w ea tf i r s tn e e dm a k ead i f f e r e n c eb e t w e e np a t hp l a n n i n gi n r o u g ht e r r a i na n dp l a n n i n gi nw e l l s t r u c t u r e de n v k o n m e n t s ： 1 i nr o u g ht e r r a i n ，t e r r a i nd a t ac a n n o ta s s u m e dt op e r f e c t l yk n o w n ，d u et o e r r o r si nr a n g es e n s i n gt e c h n i q u e sa n ds e n s o r sm i s c a l i b r a t i o n1 9 1 2 t h er o b o td u et ot h es i g n i f i c a n tp a t h - f o l l o w i n ga n dl o c a l i z a t i o ne r r o r sm a y n o tf o l l o wt h ep l a n n e dp a t h 9 1 3 i nr o u g ht e r r a i n ，t h ec o n c e p to fa no b s t a c l en o tc l e a r l yd e f i n e d ，a si t d e p e n d so na nu n d e r s t a n d i n go ft h et e r r a i na n dt h em o b i l i t yc h a r a c t e r i s t i c so ft h e r o b o t1 9 4 g r o u n de x p l o r a t i o ns y s t e m sw i l lg e n e r a l l yh a v el i m i t e dc o m p u t a t i o n a l r e s o u r c e st od e v o t et op a t hp l a n n i n g 9 1 t h e s ef o u rp o i n t sm a k es o m ec o m p l i c a t i o nf o rp a t hp l a n n i n g m o r e o v e r ，i n p a t h p l a n n i n gi nr o u g ht e r r a i nw en e e dt oc o n s i d e r ： 1 r o u g ht e r r a i np a t hp l a n n i n ga l g o r i t h m sm u s tc o n s i d e ru n c e r t a i n t yi n h e r e n t i nt e r r a i ns e n s i n gs y s t e m ss u c ha sr a n g e f i n d e r s 5 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 2 p a t hp l a