基于空间采样的方法试图通过连接一系列无障碍空间的采样节点，建立一条从初始状态到目标状态的路径。该方法可避免在状态空间中显式地构造障碍物，轨迹的可行性由碰撞检测来验证，节省了大量计算成本。该算法具有概率完备性，这意味着规划算法不能返回解的概率随着样本的数量趋近无穷而衰减到零。
*具代表性的空间采样算法是快速随机扩展树算法(Rapidly-exploring Random Trees, RRT)，1998年由美国的Steven M.LaValle教授提出，该算法由概率路图法PRM发展而来。RRT算法在高维空间中搜索路径的效率较高，基本原理为从根节点（即搜索起点）开始，通过在状态空间中循环地随机采样，逐步增加叶节点，从而生成一个随机扩展树。当随机树扩展到指定终点或已搜索到终点区域，那么通过从终节点开始，一步步查找节点的父节点便可以在随机树中找到一条连接起点和终点的路径。
基础RTT算法由于是在整个采样空间内均匀随机地采样，因此大量的计算被消耗在了无用的采样点上，从而导致了算法的收敛速度慢、效率低。对此，国内外研究者在基础RRT算法上进行了不断地优化。Kuffner J J 提出了Bi-RRT（双向搜索树），该算法以初始点和目标点为根节点，同时进行循环采样生成两棵树，直到两棵树相遇后扩展停止，以此来加快算法的收敛速度。Urmson C提出启发式RRT算法(heuristic RRT，hRRT)，使用启发式函数增加扩展代价低的结点被采样的概率，但在复杂环境中，代价函数的定义往往较困难。Goal-biasing在RRT采样过程中将目标点作为采样点，即进行目标强制扩展，在无障碍碰撞的情况下，就可以结束搜索，返回*终的RRT树。若有碰撞，将进入迭代搜索，根据概率选择进行一般搜索还是进行强制扩展，直至搜索到目标点或者迭代结束。Shkolnik A提出RC-RRT(resolution complete RRT)算法，通过对采样节点增加惩罚值来降低靠近障碍物的节点获得扩展的概率，提高搜索质量。
尽管各种改进措施可以大幅度提高RRT求解的质量，但是仍难以保证获得*优解。针对此问题，研究者提出了各种具有渐进*优性质的改进算法。Karaman S中提出的RRT*算法通过计算代价的方式来使路径渐进于*优路径。随机树在生成新节点前，计算新节点附近节点的代价，选择*低代价，从而使路径趋于*优。但RRT*与标准RRT一样具有盲目探索整个状态空间的特点，其计算效率还有很大的提升空间。Gammell J D提出了Informed RRT*算法，来避免RRT*对整个状态空间的不必要的探索，其思路是先用RRT*找到一个解，然后把采样区域限制到一个以初始、目标状态为焦点并包含当前解的椭球内，继续优化当前解。另外，针对算法的随机性导致生成的路径不平滑的问题，杜明博采用基于*大曲率约束的剪枝函数对部分节点做剔除。当随机树得到的路径曲率不满足边界要求时，则根据曲率约束插入合适的节点，*后利用B样条曲线对*终得到的树做平滑处理。
展开
