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

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