李 伟，金世俊

（东南大学仪器科学与工程学院，南京 210096）

0 引言

路径规划是移动机器人导航的关键问题之一，目前移动机器人的路径规划算法主要分为两类：基于地图的全局路径规划和基于传感器未知环境的局部路径规划。

全局路径规划有A*算法、D*算法、快速搜索随机树（Rapidly exploring Random Tree，RRT）算法等。A*算法、D*算法基于栅格地图环境，可以获取最优路径，但是算法的表现受地图分辨率影响：地图分辨率较小时，算法速度较快，但是对于环境信息无法完全表现；地图分辨率较大时，对环境的模拟效果提高，但是算法运行时间极大增加。

局部路径规划有传统的人工势场（Artificial Potential Field，APF）法、粒子群算法、蚁群算法和遗传算法等。人工势场法容易实现，计算量小，路径规划实时性高，但存在局部最小值；粒子群算法智能的精度高、收敛快但易于陷入局部最优；蚁群算法和遗传算法易于获取最优路径，不易陷入局部最优但受初始条件影响较大。

RRT 算法［1］是众多路径规划算法中一种基于采样的算法，相较于A*算法、D*算法基于栅格地图且地图分辨率对于算法表现有较大的影响，它无需对环境进行结构化建模，同时RRT 算法在高维空间路径规划也有出色的表现［2-3］。RRT 算法具有概率完备性的特征，无论在多么复杂的环境下，只要有路径存在，在不限制采样次数的条件下，RRT算法最终都会找到一条可行路径。

RRT 将起点作为扩展树的根节点，利用随机采样的方式扩展树，一旦随机树触及目标点或者随机树的某一叶子节点进入目标点一定范围，则随机树立刻停止扩展，返回由起点到目标点的一条路径。……