王坤 曾国辉 鲁敦科 黄勃 李晓斌

摘 要：针对带启发式的快速扩展随机树（RRTConnect）算法路径生成的随机性以及渐进最优的双向快速扩展随机树（BRRT*）算法收敛速度的缓慢性，提出了一种基于BRRT*改进的高效路径规划算法（EBRRT*）。首先引入一种智能采样函数，使随机树的扩展更具方向性，从而减少寻路时间，并提高路径的平滑性;其次在BRRT*算法的基础上，在EBRRT*算法中加入了一种快速扩展策略，使改进后的算法在自由空间中使用RRTConnect算法的扩展方式进行快速扩展，而在障碍物空间则使用改进的渐进最优的快速扩展随机树（RRT*）算法进行扩展，在提高扩展效率的同时避免算法陷入局部最优。将EBRRT*算法分别与快速扩展随机树（RRT）、RRTConnect、RRT* 和BRRT*算法进行仿真对比，仿真结果表明，改进后的算法在路径规划效率及路径平滑性方面均明显优于其他算法;且相对于BRRT*算法，其在路径规划时间上降低了68.3%，在迭代次数上减少了48.6%。

关键词：移动机器人;路径规划;快速扩展随机树;带启发式的快速扩展随机树算法;渐进最优的双向快速扩展随机树算法

中图分类号：TP242.6

文献标志码：A

Abstract： To overcome the randomness of RRTConnect and slow convergence of BRRT*（asymptoticallyoptimal Bidirectional Rapidlyexploring Random Tree） in path generation， an efficient path planning algorithm based on BRRT*， abbreviated as EBRRT*， was proposed. Firstly， an intelligent sampling function was intriduced to achieve more directional expansion of random tree， which could improve the smoothness of path and reduce the seek time. A rapidlyexploring strategy was also added in EBRRT* by which RRTConnect exploration mode was adopted to ensure rapidly expanding in the free space and improved asymptoticallyoptimal Rapidlyexploring Random Tree （RRT*） algorithm was adopted to prevent trapped in local optimum in the obstacle space. Finally， EBRRT* algorithm was compared with Rapidlyexploring Random Tree （RRT）， RRTConnect， RRT* and BRRT* algorithms. The simulation results show that the improved algorithm is superior to other algorithms in the efficiency and smoothness of path planning. It reduced the path planning time by 68.3% and the number of iterations by 48.6% compared with BRRT* algorithm.

英文關键词Key words： mobile robot; path planning; Rapidlyexploring Random Tree （RRT）; RRTConnect algorithm; asymptoticallyoptimal Bidirectional Rapidlyexploring Random Tree （BRRT*） algorithm

0 引言

随着人工智能等新兴领域的不断崛起，移动机器人的发展速度也获得飞速提升。目前，诸如家庭、工厂以及医院等公共场所对移动机器人的需求正在不断增加，而移动机器人作为生产工具，需要经常从一个位置移动至另一个位置，所以如何规划出一条即无障碍物又可以最小化消耗的路径成为了该领域的一项热门研究。……