路径规划算法1.3抽样算法——PRM和RRT算法
前言抽样算法的完备性PRM概率路图思想方法RRT快速扩展随机树思想基本方法改进随机搜索策略其他改进后记前言
由于图搜索算法在三维空间中的计算量陡增，因此抽样算法（sample based planning）更适合在三维中使用。最经典的两个算法是PRM（Probabilistic Road Map）概率路图法，RRT（Rapidly-explorring Random Tree）快速扩展随机树法，及其优化方法RRT*。
抽样算法的完备性
基于图搜索的方法，只要规划时间充足就肯定能找到路径，因此是完备的。
基于抽样的算法，由于采样数量是一定的，因此当采样次数越多，找到解的概率越大，但寻路时间越长；采样点少就可能找不到路径，是概率完备的
PRM概率路图
思想
寻路空间中随机采样，形成路图，搜索路径。
方法
在寻路空间中随机撒点，剔除落在障碍物上的采样点。将每个采样点与其附近一定距离内的采样点连接，剔除与障碍物碰撞的边，形成路图。采用图搜索算法（如A*）寻找最优路径。PRM是概率完备的，但碰撞检测耗时较长，效率低。
RRT快速扩展随机树
思想
通过抽样点引导路径树在寻路空间中生长，形成路径（有增量式搜索的意味）。
基本方法
初始化起点，终点，路径树T={起点}。在寻路空间中随机抽样一个点R，从路径树T中找到距离点R最近的节点N。由N向R扩展一段距离到达点S，如果边NS无碰撞，则将S加入路径树T中。循环步骤2和3，直到加入路径树的点S与终点间的距离小于一定阈值。这就是最简单的RRT算法，但是由于搜素策略是随机抽样，因此搜索效率不高。
另外，抽样算法获得的路径大多都不是最优的。
改进随机搜索策略
将基本方法步骤2进行修改：
随机抽取q∈(0,1)q\in(0, 1)q∈(0,1)，当q<thresholdq<thresholdq<threshold时，从路径树T中找到距离终点最近的节点N；当q>thresholdq>thresholdq>threshold时，在寻路空间中随机抽样一个点R，从路径树T中找到距离R最近的节点N。
thresholdthresholdthreshold靠近1时，路径树偏好向终点生长，但容易被障碍物阻挡；thresholdthresholdthreshold靠近0时，路径树类似于随机生长，容易越障但效率低。
这种搜索策略的改进提升了搜索策略的目的性（朝向终点），也保持了一定的越障能力。
其他改进
RRT能够改进的地方有：
随机搜索策略扩展树的方法近邻节点的定义双向树生长（bidirectional RRT）
后记
下一次会再总结RRT*等sample based算法。
