改进型RRT^(*)算法的水下机器人三维全局路径规划

An Improved RRT^(*) Algorithm for 3D Global Path Planning of Underwater Vehicles

由于传统快速扩展随机树的改进算法(RRT^(*))在处理自主式水下机器人三维路径规划问题时存在算法收敛速度慢、规划出的路径不平滑等问题,提出一种改进型NT-RRT^(*)算法(正态采样、三角裁剪的快速扩展随机树改进算法),利用正态分布的空间采样策略来代替RRT^(*)算法中的全局均匀随机采样,用来提高算法的收敛速度。此外,引入基于三角不等式的几何修剪算法,减少了随机树扩展过程中的节点和路径长度。在有地形障碍物和漂浮障碍物的三维水下环境进行仿真,仿真结果表明,改进后的算法在随机扩展中的节点数减少为原来的15%,算法规划时间缩短为原来的20%,规划出的路线长度约为原来的一半并且路径光滑、曲折性小,说明改进后的NT-RRT^(*)算法在收敛速度和路径长度上明显优于RRT^(*)算法。

Due to the expansion of the traditional rapid improved algorithm of random tree(RRT^(*))in the treatment of the autonomous underwater robot AUV(Autonomous Underwater Vehicle)three-dimensional path planning problem of the existed algorithms of slow convergence speed,rough planning path,propose a modified NT-RRT^(*) algorithm(normal sampling,triangle cut the rapid expansion of random tree algorithm). In order to improve the convergence speed of the algorithm,a spatial sampling strategy based on normal distribution is proposed to replace the global uniform random sampling in RRT^(*) algorithm. In addition,a geometric pruning algorithm based on triangle inequality is introduced. It reduces the length of nodes and paths in the process of random tree expansion. Finally,the simulation is carried out in a three-dimensional underwater environment with terrain obstacles and floating obstacles. The simulation results show that the number of nodes in random expansion of the improved algorithm is reduced to 15%,the algorithm planning time is shortened to 20% of the original,the planned route length is about half of the original,and the path is smooth and the curvature is small,which shows that the improved NT-RRT^(*) algorithm is obviously better than the RRT^(*) algorithm in terms of convergence speed and path length.