Ren Zhigang, Cai Anjiang, Xu Feilong
School of Mechanical and Electrical Engineering, Xi'an University of Architecture and Technology, Xi'an, China.
Xi'an Huayun Wisdom Information Technology Co., Ltd., Xi'an, China.
PeerJ Comput Sci. 2025 Jun 18;11:e2915. doi: 10.7717/peerj-cs.2915. eCollection 2025.
In response to the issues of low computational efficiency, slow convergence speed, curvy paths, and the tendency to fall into local optima in rapidly-exploring random tree (RRT) algorithms for automated guided vehicle (AGV) path planning, this article proposes an improved RRT algorithm that combines adaptive step-size optimization with K-dimensional tree (KD-Tree) based fast nearest neighbor search. Firstly, an adaptive step-size optimization strategy is introduced to dynamically adjust the step size during node searches, improving both the planning quality and computational efficiency of the algorithm. Secondly, the KD-Tree nearest neighbor search method is employed to accelerate node searching and reduce the time cost of path planning. Finally, a cubic spline interpolation function is applied to smooth the optimal path, further enhancing the planning quality. Experimental results show that the improved RRT algorithm significantly outperforms traditional RRT, RRT*, and Informed-RRT* in terms of path length, planning time, and path smoothness. Specifically, the average path length is reduced by 164.33 m, and the average search time is shortened by 3.3 s, making it more suitable for AGV path planning in practical applications.
针对自动导引车（AGV）路径规划的快速探索随机树（RRT）算法存在计算效率低、收敛速度慢、路径弯曲以及易陷入局部最优等问题，本文提出一种改进的RRT算法，该算法将自适应步长优化与基于K维树（KD-Tree）的快速最近邻搜索相结合。首先，引入自适应步长优化策略，在节点搜索过程中动态调整步长，提高算法的规划质量和计算效率。其次，采用KD-Tree最近邻搜索方法加速节点搜索，降低路径规划的时间成本。最后，应用三次样条插值函数对最优路径进行平滑处理，进一步提高规划质量。实验结果表明，改进的RRT算法在路径长度、规划时间和路径平滑度方面明显优于传统的RRT、RRT和Informed-RRT算法。具体而言，平均路径长度减少了164.33米，平均搜索时间缩短了3.3秒，使其更适合实际应用中的AGV路径规划。
