算法描述

20世纪90年代以来，使用随机化方法的路径规划算法逐渐增多，因为这种方法可以适用于不确定环境中的高维度空间，并且也曾被用来解决人工势场法中的局部极小问题。近年来这方面研究的发展可以快速扩展随机树作为代表，其本质上为一种高效的数据结构，可以被用来解决不确定环境下的完整性规划、非完整性规划以及运动动力学的问题。

快速扩展随机树，简称RRT，是一种数据结构和算法，其设计用途是用来有效搜索高维非凸空间，可应用于路径规划、虚拟现实等研究。快速扩展随机树采用一种特殊的增量方式进行构造，这种方式能‘迅速缩短一个随机状态点与树的期望距离。快速扩展随机树特别适合包括障碍物和微分约束(非完整性或运动动力学)的路径规划问题。快速扩展随机树可以被视为一种处理非线性系统的技术，产生针对状态约束的非线性系统的开环轨迹。一棵快速扩展随机树其实可被视为一个倾向于搜索最大Voronoi区域的Monte-Carlo方法。因此，快速扩展随机树在应用于路径规划方面前景广阔。

算法

图1

算法如图1：

算法实现

快速扩展随机树采用Borland公司的C++Builder5.0开发完成。并且为了快速而高效的实现算法，特别采用了C++ STL(Standard Template Library)标准模板库技术以继承经典的数据结构和算法，实现软件复用，降低开发强度。在开发的过程中针对所使用的特殊的数据结构对标准快速扩展随机树的局部算法做了相应的改动，使得整个系统的结构更为简洁和优化。