Abstract: In the complex environment, the path planning modular needs to generate a suitable path for unmanned vehicle to track. Two aspects are considered in the generated path. Firstly, the algorithm can search out a safe path, in real time. Secondly the planed path can satisfy the constraints of the vehicle model, that is kinematic constraints. However, the rapidly exploring random tree algorithm has the disadvantages of slow convergence and too large twists turns in planed path, which is not suitable for unmanned vehicle path tracking. To address these problems mentioned about, the improved algorithm TSRRT（Two-Stage RRT） uses the Bezier curve to combine with the maximum steering angle to optimize the upper boundary curvature, so that the planned path can meet the maximum steering angle of vehicle movement. At the same time, in order to speed up the convergence speed of the algorithm, the heuristic function sampling search in the first stage and the Dubins curve in the second stage are used to directly connect the end point and the search end point in the first stage, which can effectively improve the overall search efficiency of the algorithm. Compared with the original RRT algorithm, the search time and path length of the proposed algorithm are reduced by 43% and 25%, respectively. Meanwhile, the smoothness of the path is improved, and the curvature of the searched path can be continuous, so that the vehicle can track the path better.

Key words: rapidly exploring random tree, two-stage rapidly-exploring random trees（TSRRT） algorithm, search time, smoothness, heuristic function, Bezier curve, Dubins curve

摘要： 在复杂的环境当中，智能车辆路径规划模块的职能是产生一条合适的路径让智能车路径跟踪模块进行跟踪。在路径规划模块中要考虑两个方面：第一个方面是算法能够快速地搜索出一条安全的路径；第二个方面是算法进行路径规划的同时能够考虑车辆自身模型的约束，即运动学约束限制。然而快速搜索随机树RRT算法进行大范围路径搜索的过程中存在收敛速度较慢、搜索路径曲折角度过大的问题，导致车辆跟随时转弯角度过大、转向不连续，不满足车辆运动学模型。二阶段RRT算法TSRRT（Two-Stage RRT）采用融合最大转向角度的三次Bezier曲线进行上边界曲率优化，使规划路径能够满足车辆运动的转向角度，让车辆在行驶过程中能够以不停车的方式进行连续平稳转向；同时为了加快算法的收敛速度，通过第一阶段的启发式函数采样搜索以及第二阶段Dubins曲线直接连接最终终点和第一阶段搜索终点，能够有效地提高算法的整体搜索效率。通过实验验证，改进的RRT算法TSRRT，相比于传统RRT算法搜索时间减少近43%，路径长度减少近25%，同时提高了路径的平滑性，使已搜索路径曲率能够满足连续，能够让车辆在不停止的情况下连续平稳转弯，以便车辆后续更好地进行路径跟踪。

关键词: 快速搜索随机树, TSRRT算法, 搜索时间, 平滑性, 启发式函数, Bezier曲线, Dubins曲线