基于多策略改进的RRT算法  

Improved RRT algorithm based on multi-strategy

作　　者：文汉云[1] 刘攀 WEN Hanyun;LIU Pan(School of Computer Science Yangtze University,Jingzhou 434023,Hubei)

机构地区：[1]长江大学计算机科学学院,湖北荆州434023

出　　处：《长江大学学报(自然科学版)》2025年第1期111-118,共8页Journal of Yangtze University(Natural Science Edition)

基　　金：国家自然科学基金项目“随钻测量井下网络化光纤传感器及信息传输关键技术研究”(41372155)。

摘　　要：针对传统RRT(rapidly exploring random tree)算法在复杂环境下收敛速度慢、存在重复采样、缺乏目标导向性和规划的路径质量不高的问题,提出一种贪婪搜索和目标导向的RRT算法(RRT-D算法),在传统RRT算法的基础上,改进节点的采样方式和父节点的选取策略,取消步长限制,通过贪婪式的搜索方式一次生长10个候选节点,选取符合条件的且距离目标点最近的候选点作为子节点生长到树中,提高了算法的搜索能力,降低了路径代价;用动态减少重复搜索区域的方式减少了无效搜索;每次采样后判断采样点能否与目标点直接相连,增加了采样的目标导向性,提高了搜索效率,遍历全树构成无向图时,可根据总采样点数量,通过限制无向图边的长度来减少边的数量,由Dijkstra算法搜索代价最小的路径;最后由分段三次Hermite插值函数对路径进行平滑处理。试验结果表明,与传统RRT算法相比,RRT-D算法不仅大幅缩短了规划时间,而且得到的路径代价更小、更加平滑,节点的利用率更高,验证了RRT-D算法在路径规划中的优势。A greedy RRT algorithm(RRT-D algorithm)oriented at search and goal is proposed to address the problem of a slow rate of convergence,repeated sampling,lack of goal orientation and undergrade path planning under the complex surroundings of the traditional RRT algorithm(rapidly exploring random tree),through which,improve the sampling method of nodes and the strategy of selecting parent nodes,cancel the step size limit,ten candidate nodes can be generated at a time.And the eligible one closest to the target point is added to the search tree as a child node,improved the search ability of the algorithm and reduced path cost.Reduced invalid searches by dynamically reducing duplicate search areas,forming an undirected graph.Judge whether to connect directly to the target node after each sampling,which increases the target orientation of sampling and improves the search efficiency.When traversing the whole tree to form an andirected graph,the number of edges can be reduced by limiting the length of edges of the undirected graph according to the total number of sampling points,and the Dijkstra algorithm can search the path with the lowest cost.Finally,the path is smoothed by the piecewise cubic Hermite interpolation function.The proposed RRT-D algorithm is superior to the traditional RRT algorithm for its significant reduction in planning,lower and smoother path obtained as well as high utilization of nodes,according to the experiment result.These strengths of the RRT-D algorithm have been verified in path planning.

关 键 词：路径规划 RRT算法 RRT-D算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]