Abstract: In order to solve the problems of long search time, low sampling efficiency and tortuous path planning of RRT* and B-RRT* algorithms in complex environment, a goal biased bidirectional rapidly-exploring random tree algorithm GBB-RRT*（goal biased bidirectional RRT*） is proposed. In each iteration, two random trees are expanded, and two new nodes can be generated in one iteration to speed up the expansion. Then, the goal bias strategy is introduced to optimize the selection of sampling points, so that the two random trees expand towards their respective goal points under a certain probability. According to the obtained planning path, a reverse optimization method combined with corner constraint path simplification is designed, and the smooth executable path is generated by combining with B-spline curve. In the simulation experiment, the algorithm is compared with B-RRT*. The results show that the search time of the proposed algorithm is reduced by about 40%, the expansion node is reduced by about 10%, and the path length is reduced by about 3% combined with the path simplification method.

Key words: path planning, goal bias, RRT* algorithm, bidirectional search, path simplification, B-spline curve

摘要： 针对RRT*和B-RRT*算法在较复杂环境下路径规划时，存在搜索时间长、采样效率低和规划路径曲折的问题，提出一种目标偏置双向快速扩展随机树算法——GBB-RRT*（goal biased bidirectional RRT*）。该算法每次迭代中两棵随机树都进行扩展，一次迭代能生成两个新节点，加快扩展速度。然后引入目标偏置策略来优化采样点的选取，使两棵随机树在一定概率下朝各自的目标点方向扩展。针对得到的规划路径，设计一种逆向寻优结合转角约束路径简化方法，结合B样条曲线生成光滑可执行路径。在仿真实验中将提出的算法与B-RRT*进行对比实验，结果表明所提算法搜索时间缩短40%左右、扩展节点减少10%左右，结合路径简化方法后路径长度缩短3%左右。

关键词: 路径规划, 目标偏置, RRT*算法, 双向搜索, 路径简化, B样条曲线