李晓伟，于会山

（聊城大学物理科学与信息工程学院，聊城252059）

0 引言

在移动机器人的研究领域中，路径规划算法是最为重要而且不可缺少的组成部分，是移动机器人在障碍物环境下实现自主移动导航的基础。随着路径规划算法研究的不断深入，研究人员已经改善并优化了很多传统的路径规划算法，并不断提出了很多新的路径规划算法，使得路径规划算法的研究趋势已经逐步偏向复杂化和智能化[1]。常用的路径规划算法包括A*、人工势场法、概率路线图（PRM）算法、蚁群算法、遗传算法以及诸多启发式算法等[2]。这些算法的收敛速度过于缓慢，需要提前对未知的障碍物空间环境进行建模，当环境改变时无法在未知的障碍空间中使用。

快速扩展随机树算法由Steven M.LaValle 于1998年首次提出来[3]。RRT（快速探索随机树）算法能有效解决这些传统路径规划算法存在的问题。与其他传统路径规划算法相比，RRT 算法不仅具有快速、高效的特点，而且不需要依赖于环境建模就能够有效地解决未知复杂障碍物空间和高维动态环境的路径规划问题。RRT 是基于空间中树木分支的创建，它迭代地对新的状态进行采样，然后将离每个样本更近的现有节点指向一个新的样本，从而形成一个具有分支的树。即在空间里，从根节点开始，进行任意采样，当采样形成的新点为目标点或新点与目标点的距离小于一定步长时，则形成一条由根节点至目标点的路径[4]。

1 RRT算法

在快速扩展随机树中，qinit为树的根节点（起始点），qgoal为目标点，qrand为任意扩展的随机节点，qnear为每次扩展时距离qrand最近的节点，qnew为新节点[5]。……