冯 蕊，杨雪锋，2

（1.重庆交通大学 航运与船舶工程学院，重庆 400074；2.交通安全应急信息技术国家工程实验室，北京 100011）

0 引言

随着移动机器人技术的发展，路径规划算法得到深入研究和广泛应用［1-2］。遗传算法、模拟退火算法等传统路径规划算法需要对障碍物进行精确的数学建模，对于复杂环境中的规划问题处理效果较差［3］，且多数算法未考虑移动机器人的非完整性约束限制［4］，使得规划路径不一定可执行。

针对复杂空间建模困难和非完整性约束考虑不足问题，1998 年LaValle 等［5］、唐华斌等［6］提出快速搜索随机树（Rapidly-exploring Random Tree，RRT）算法，该算法采用随机采样方法，不需要对状态空间进行预处理和建模，而且在搜索过程中还考虑了机器人客观存在的约束条件，如非完整性约束、动力学约束、运动学约束等，从而能有效解决复杂环境问题，得到越来越多研究人员的关注。

RRT 算法通过随机采样以逐步迭代的方式进行随机树构造，通过从根节点以步长λ不断扩展出叶子节点的方式构建随机树［7］。由于采用随机采样的方式进行路径规划，RRT 算法中随机树的指向性较差，导致收敛速度较慢且规划结果通常不是最优。针对此问题，2000 年Kuffner等［8］又对随机树生长策略进行改进，在生长过程中以一定的概率将目标点直接作为随机采样点（以下简称偏置概率Pg），这既能提升收敛速度，也能降低规划路径长度，大大提高了RRT 算法效率。可见，步长λ和偏置概率Pg这两个初始化参数与RRT 算法性能密切相关，选择合理的初始化参数能够提升收敛速度，优化路径规划结果；……