梁永豪，陈秋莲，王成栋

(广西大学 计算机与电子信息学院，广西 南宁 530004)

0 引 言

机器人路径规划，是通过算法在有障碍物的环境中找到一条从起点到目标点的无碰撞路径。路径规划算法作为移动机器人的关键技术之一，受到国内外学者的广泛关注。

目前，路径规划算法主要包括遗传算法[1]、粒子群算法[2]、人工势场法[3]、基于网格的算法[4]和基于采样的算法[5，6]。基于采样的算法通用性比较强，受环境维度和复杂度的约束较小[7]，是当前最流行的路径规划算法之一。快速扩展随机树(RRT)[8]是基于采样算法的典型代表，依靠随机采样和碰撞检测模块，在给定的空间内生成一组离散的点。虽然RRT可以快速找到路径，但它不能确保找到的路径是最优的。RRT*[9]是RRT算法的变体，在添加新节点时引入两个优化模块：重选父节点和重布线。优化模块确保在采样点趋于无穷时，RRT*算法找到最优解。

RRT*是RRT算法发展的一个里程碑，吸引了很多学者，主要从两个方面对算法的性能进行改进：采样策略和树扩展策略。采样策略主要是通过优化采样点，加速算法收敛。如知情采样Informed-RRT*[10]限制采样点在椭圆形采样区域内；目标偏置[11]和人工势场法[12]利用目标点的信息来指导新节点生成方向；Bi-RRT*[13]则采用双树拓展的同时引入启发式思想，加快收敛速度。树扩展策略则是对扩展树本身的结构进行优化，使路径长度尽可能短。如Quick-RRT*[14]使用三角不等式来优化重选父节点和重布线模块，缩短路径长度；F-RRT*[15]在Quick-RRT*的基础上以创造父节点替代重选父节点；……