[1]文汉云,刘攀.基于多策略改进的RRT算法[J].长江大学学报(自然科学版),2025,(1):111-118.
点击复制

基于多策略改进的RRT算法
分享到:

长江大学学报(自然科学版)[ISSN:1673-1409/CN:42-1741/N]

卷:
期数:
2025年第1期
页码:
111-118
栏目:
算法研究
出版日期:
2025-01-25

文章信息/Info

文章编号:
1673-1409 (2025) 01-0111-08
作者:
文汉云刘攀
长江大学计算机科学学院, 湖北 荆州 4 3 4 0 2 3
关键词:
路径规划 RRT 算法 RRT - D算法
分类号:
TP 3 0 1 .6
文献标志码:
A
摘要:
针对传统 RRT (r a p i d l ye x p l o r i n gr a n d omt r e e ) 算法在复杂环境下收敛速度慢、 存在重复采样、 缺乏目标导向性和规划的路径质量不高的问题, 提出一种贪婪搜索和目标导向的 RRT 算法 (RRT - D 算法), 在传统 RRT算法的基础上, 改进节点的采样方式和父节点的选取策略, 取消步长限制, 通过贪婪式的搜索方式一次生长1 0个候选节点, 选取符合条件的且距离目标点最近的候选点作为子节点生长到树中, 提高了算法的搜索能力, 降低了路径代价; 用动态减少重复搜索区域的方式减少了无效搜索; 每次采样后判断采样点能否与目标点直接相连,增加了采样的目标导向性, 提高了搜索效率, 遍历全树构成无向图时, 可根据总采样点数量, 通过限制无向图边的长度来减少边的数量, 由 D i j k s t r a算法搜索代价最小的路径; 最后由分段三次 He r m i t e插值函数对路径进行平滑处理。 试验结果表明, 与传统 RRT 算法相比, RRT - D算法不仅大幅缩短了规划时间, 而且得到的路径代价更小、 更加平滑, 节点的利用率更高, 验证了 RRT - D算法在路径规划中的优势。

参考文献/References:


[1] MEGHJAN IM, MAN JANNAS, DUDEK G .Mu l t i - t a r g e tr e n d e z v o u ss e a r c h [C] .2 0 1 6I E E E /R S JI n t e r n a t i o n a lC o n f e r e n c eo nI n t e l l i g e n tR o b o t sa n dS y s t e m s(I ROS) . I E E E,2 0 1 6:2 5 9 6 - 2 6 0 3 .
[2] Y I N H, MELOFS, B I LLARDA,e ta l .B o o s t i n gR o b o tL e a r n i n ga n dC o n t r o lw i t hD oma i nC o n s t r a i n t s [C] .R o b o t i c s: S c i e n c ea n dS y s t ems: RS SP i o n e e rWo r k s h o p .RS S,2 0 1 8(CONF) .
[3] ZAHAFA, BOUOUDENS, CHADL IM,e ta l .R o b u s tf a u l tt o l e r a n to p t i ma lp r e d i c t i v ec o n t r o lo fh y b r i da c t u a t o r sw i t ht i me - v a r y i n gd e l a yf o ri n d u s t r i a lr o b o ta r m [J] .A s i a nJ o u r n a lo fC o n t r o l,2 0 2 2,2 4 (1):1 - 1 5 .
[4] TANGL, SHAOG .D r o n er e mo t es e n s i n gf o rf o r e s t r yr e s e a r c ha n dp r a c t i c e s [J] . J o u r n a lo fF o r e s t r yR e s e a r c h,2 0 1 5,2 6 (4):7 9 1 - 7 9 7 .第2 2卷 第1期 文汉云 等: 基于多策略改进的 RRT 算法 ·1 1 7·
[5] D I JKSTRAE W .An o t eo nt wop r o b l emsi nc o n n e x i o nw i t hg r a p h s [J] .Nume r i s c h ema t h ema t i k,1 9 5 9,1 (1):2 6 9 - 2 7 1 .
[6] 张志文, 张鹏, 毛虎平, 等. 改进 A* 算法的机器人路径规划研究 [J /OL] . 电光与控制, 2 0 2 1 - 0 3 - 2 6 .ZHANGZ W, ZHANGP, MAO HP,e ta l .R e s e a r c ho nr o b o tp a t hp l a n n i n gw i t hi mp r o v e dA* a l g o r i t hm [J /OL] .E l e c t r o - o p t i c a la n dc o n t r o l, 2 0 2 1 - 0 3 - 2 6 .
[7] BOUN I N IF, G I NGRASD, POLLART H,e ta l .Mo d i f i e da r t i f i c i a lp o t e n t i a lf i e l dm e t h o df o ro n l i n ep a t hp l a n n i n ga p p l i c a t i o n s [C] .2 0 1 7I E E EI n t e l l i g e n tV e h i c l e sS y mp o s i um (I V) . I EEE,2 0 1 7:1 8 0 - 1 8 5 .
[8] GERAERTSR, OVERMARSM H .Ac omp a r a t i v es t u d yo fp r o b a b i l i s t i cr o a dma pp l a n n e r s [M] .A l g o r i t hm i cf o u n d a t i o n so fr o b o t i c sV .S p r i n g e r, B e r l i n, He i d e l b e r g,2 0 0 4 .
[9] ZHANGX, ZHU T, XU Y, e ta l .L o c a lP a t hP l a n n i n go ft h eAu t o n omo u sV e h i c l eB a s e do nAd a p t i v eI mp r o v e dRRT A l g o r i t hmi nC e r t a i nL a n eE n v i r o nme n t s [C] / /A c t u a t o r s .MDP I,2 0 2 2,1 1 (4):1 0 9 .
[1 0] SAL ZMAN O, HAL PER I ND .A s ymp t o t i c a l l yn e a r - o p t i ma lRRTf o rf a s t, h i g h - q u a l i t ymo t i o np l a n n i n g [J] . I EEET r a n s a c t i o n so nR o b o t i c s,2 0 1 6,3 2 (3):4 7 3 - 4 8 3 .
[1 1] ZHANGH, WANG Y, ZHENGJ,e ta l .P a t hp l a n n i n go fi n d u s t r i a lr o b o tb a s e do ni m p r o v e dRRTa l g o r i t hmi nc om p l e xe n v i r o nm e n t s [J] .I EEEA c c e s s,2 0 1 8,6:5 3 2 9 6 - 5 3 3 0 6 .
[1 2] KUF FNER J J, LAVALLE S M .RRT - c o n n e c t: A n e f f i c i e n t a p p r o a c h t o s i n g l e - q u e r y p a t h p l a n n i n g [C] .P r o c e e d i n g s 2 0 0 0I CRA .M i l l e n n i umC o n f e r e n c e . I E E EI n t e r n a t i o n a lC o n f e r e n c eo nR o b o t i c sa n dA u t om a t i o n .S y mp o s i aP r o c e e d i n g s(C a t .N o .0 0 CH 3 7 0 6 5)I E E E,2 0 0 0,2:9 9 5 - 1 0 0 1 .
[1 3] BRANDT D .C omp a r i s o no faa n dr r t - c o n n e c tmo t i o np l a n n i n gt e c h n i q u e sf o rs e l f - r e c o n f i g u r a t i o np l a n n i n g [C] .2 0 0 6I EEE /RS JI n t e r n a t i o n a lC o n f e r e n c eo nI n t e l l i g e n tR o b o t sa n dS y s t ems . I EEE,2 0 0 6:8 9 2 - 8 9 7 .
[1 4] KARAMAN S, FRAZ ZOL IE .Op t i ma lk i n o d y n am i cmo t i o np l a n n i n gu s i n gi n c r eme n t a ls amp l i n g - b a s e d me t h o d s [C] .4 9 t hI EEEc o n f e r e n c eo nd e c i s i o na n dc o n t r o l(CDC) . I EEE,2 0 1 0:7 6 8 1 - 7 6 8 7 .
[1 5] NOREENI, KHAN A, HAB I BZ .Op t i ma lp a t hp l a n n i n gu s i n gRRT* b a s e da p p r o a c h e s: as u r v e ya n df u t u r ed i r e c t i o n s [J] . I n tJAd vC omp u tS c iAp p l,2 0 1 6,7 (1 1):9 7 - 1 0 7 .
[1 6] GAMMELLJD, S R I N I VASASS, BARFOOTTD . I n f o r m e dRRT* : O p t i m a ls a mp l i n g - b a s e dp a t hp l a n n i n gf o c u s e dv i ad i r e c ts a mp l i n go fa na dm i s s i b l ee l l i p s o i d a lh e u r i s t i c [C] .2 0 1 4I EEE /RS JI n t e r n a t i o n a lC o n f e r e n c eo nI n t e l l i g e n tR o b o t sa n dS y s t ems . I EEE, 2 0 1 4:2 9 9 7 - 3 0 0 4 .
[1 7] D?NME ZE, KOCAMAZA F, D I R I K M .B i - RRTp a t he x t r a c t i o na n dc u r v ef i t t i n gsmo o t hw i t hv i s u a lb a s e dc o n f i g u r a t i o ns p a c ema p p i n g [C] .2 0 1 7i n t e r n a t i o n a la r t i f i c i a l i n t e l l i g e n c ea n dd a t ap r o c e s s i n gs ymp o s i um (I DAP) . I EEE,2 0 1 7:1 - 5 .
[1 8] JEONGIB, LEESJ, K IMJ H .Q u i c k - RRT* : T r i a n g u l a ri n e q u a l i t y - b a s e di mp l eme n t a t i o no fRRT* w i t hi mp r o v e di n i t i a ls o l u t i o na n dc o n v e r g e n c er a t e [J] .E x p e r tS y s t emsw i t hAp p l i c a t i o n s,2 0 1 9,1 2 3:8 2 - 9 0 .
[1 9] 李金良, 舒翰儒, 刘德建, 等. 基于改进 RRT 路径规划算法 [J] . 组合机床与自动化加工技术, 2 0 2 1 (2): 2 2 - 2 4, 2 9 .L IJL, SHU H R, L I UDJ,e ta l .B a s e do ni mp r o v e dRRTp a t hp l a n n i n ga l g o r i t hm [J] .Mo d u l a rMa c h i n eT o o la n dA u t om a t i cP r o c e s s i n gT e c h n o l o g y,2 0 2 1 (2):2 2 - 2 4, 2 9 .
[2 0] 李兆强, 张时雨. 基于快速 RRT 算法的三维路径规划算法研究 [J /OL] . 系统仿真学报, 2 0 2 1 - 0 3 - 2 6 .L IZQ, ZHANGSY .R e s e a r c ho nt h r e e - d i m e n s i o n a lp a t hp l a n n i n ga l g o r i t hmb a s e do nf a s tRRTa l g o r i t hm [J /OL] . J o u r n a lo fS y s t emS i mu l a t i o n,2 0 2 1 - 0 3 - 2 6 .
[2 1] 张立彬, 林后凯, 谭大鹏. 基于栅格空间的自适应 GB_ RRT* 机械臂路径规划 [J /OL] . 计算机集成制造系统, 2 0 2 1 - 0 4 - 2 5 .ZHANGLB, L I N HK, TANDP .Ad a p t i v eGB_ RRT*r o b o ta r mp a t hp l a n n i n gb a s e do ng r i ds p a c e [J /OL] .C omp u t e r i n t e g r a t e dma n u f a c t u r i n gs y s t em, 2 0 2 1 - 0 4 - 2 5 .

更新日期/Last Update: 2025-01-25