摘要
最优快速拓展随机树(RRT^(*))是一种渐进最优的移动机器人路径规划方法,Quick-RRT^(*)缩短了RRT^(*)的初始路径长度,提高了路径收敛速度。为进一步提高Quick-RRT^(*)的收敛速度,文中提出了一种双树Quick-RRT^(*)算法。首先,基于Quick-RRT^(*)算法在起点和终点分别生成一棵随机树,起点树和终点树轮流生长,两棵树的连接采用贪婪法;然后,对提出的算法的概率完备性和渐进最优性进行理论分析,证明了算法的概率完备性和渐进最优性;最后,基于Matlab平台,在3种环境下采用双树Quick-RRT^(*)与RRT^(*)、Quick-RRT^(*)和双向RRT^(*)算法进行了对比仿真实验。结果表明,文中改进的算法不仅可以在更短的时间内找到初始路径和次优路径,而且初始路径更短。
The optimal rapid expansion randomized tree(RRT^(*))is an asymptotically optimal path planning method for mobile robots.Quick-RRT^(*)reduces the initial path length of RRT^(*)and increases the path convergence speed.In order to further improve the convergence speed of Quick-RRT^(*),this paper proposed a dual-tree Quick-RRT^(*)(Quick-RRT^(*)-Connect)algorithm.Firstly,two random trees were generated at the start and end points respectively based on the Quick-RRT^(*)algorithm.Two trees grew in turn and they were connected with greedy method.Then,the probability completeness and asymptotic optimality of the proposed algorithm were analyzed and testified.Finally,based on the Matlab platform,Quick-RRT^(*)-Connect was compared with RRT^(*),Quick-RRT^(*)and RRT^(*)-Connect in three environments.The results show that the improved algorithm can not only find initial path and suboptimal path in a shorter time,but also reduce the initial path length.
作者
魏武
韩进
李艳杰
高天啸
WEI Wu;HAN Jin;LI Yanjie;GAO Tianxiao(School of Automation Science and Engineering,South China University of Technology,Guangzhou 510640,Guangdong,China)
出处
《华南理工大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2021年第7期51-58,共8页
Journal of South China University of Technology(Natural Science Edition)
基金
广东省科技计划项目(2019A050520001)。
