针对仅有一个起始-目标构型对的单疑问（Single-Query）运动规划问题，仅需覆盖与构型对相关的部分即可，预计算不能带来任何好处。大多数基于采样的单疑问规划算法都选择以逐步构建稠密搜索树的方式来探索C-space，而不用提前设定采样点数量。只要算法构建的路径集足够丰富，那么将找到一个解，该特点使其适合于在线执行。基于采样的单疑问运动规划算法可被统一至递增采样与搜索（Incremental Sampling and Searching）的框架下：

步骤1初始化，无向拓扑图的节点集初始时一般包含起始构型和 目标构型。步骤2节点选择方法（Node Selection Method，NSM），选择一个节点进行扩展。步骤3局部规划方法（Local Planning Method，LPM），选择新的构型点，试图构造路径，使得且。用碰撞检测算法确保，否则返回步骤2。步骤4在图中插入一条边，将作为连接和的边插入中。若 不在中，也将其插入。步骤5对解进行检验，确定是否已经编码了一条解路径。步骤6返回步骤2。步骤2中的NSM类似于图搜索算法中的优先队列（Priority Queue），而步骤3中的 LPM之所以称为局部的，是因为其并不尝试解决整个规划问题，而是每次仅产生较短且简单的无碰路径段。对于非完整系统，LPM也可称为Steering方法。现有算法大多都是步骤2和步骤3有所不同，其中最著名的应是扩张空间树（Expansive Spaces Tree，EST）和快速扩展随机树（Rap⁃idly Exploring Random Tree，RRT）。前者将待扩展节点被选择的概率设置为关于树上节点分布密度的反比例函数，并在该节点周围一定范围内随机选择新的构型点进行扩展，从而保障了采样树的稠密生长。后者则通过定义一个无穷、稠密采样序列，并利用 NEAREST函数为每个采样点选择其在中的最近点来迭代生长（参见图4）。图4 RRT算法流程正是因为每个节点被选择的概率与其对应Voronoi区域的测度成正比，才保证了算法的快速扩展特性。两种方法的概率完备性也已在原文中得到证明。值得一提的是，PRM算法的变体也可用于单疑问运动规划问题：其先在忽略障碍物的情况下构建概率路图，待找到可行路径时仅对该路径进行碰撞检测。若某条边或节点发生碰撞，则将其移除并重新增强路图进行路径搜索和碰撞检测。Lazy PRM的思想来源是碰撞检测耗费了算法90%以上的时间，且对单疑问运动规划问题来说大部分边的碰撞检测是无用的。在大多数应用中，解路径的品质亦十分重要，一般除可行性外还存在最优性要求，如最短长度路径、最短时间路径等。但可以证明，标准的PRM算法和RRT算法均不具 备渐进最优性。经典方法是利用启发式图搜索算法提供最优性保证，不过这种最优性受限于网格分辨率，且最坏情况下的运行时间随空间维数呈指数增长。Karaman和Frazzoli通过修改邻近点选取方法和局部节点连接方式（在文章中分别对应Near Vertices和Rewire），提出了概率完备的渐进最优算法—PRM*、快速扩展随机图（Rapidlyexploring Random Graph，RRG）和RRT*（算法流程参见图5和图6），且后两种算法具有Anytime特性。其虽不能完全克服经典方法的缺点，但的确在当时提供了一个保证算法渐进最优性的新视角。以RRT*为例，算法在Near verti⁃ces步骤中用变化球半径的方式选择的邻近采样点，其中半径为图5 PRM*算法流程式（3）是采样离散度的函数，并随采样点数量的增加而减小，为构型空间维数，是与环境相关的参数。在Rewire步骤中，首先将qnew连接至能为其提供更低代价的邻近节点上，其次若能为剩余某些邻近节点提供更低的代价，则将该邻近节点的父节点设置为。一些关于PRM*和RRT*理论分析的改进近来也已被提出。上面的论述详细探究了SBMP的思想内涵，列举了几种经典的SBMP 算法以及它们的优缺点和适用场景。至于该算法框架中最近点函数、距离度量、局部规划器、碰撞检测模块的选择，在此不过多赘述。另外在经典SBMP算法的基础上，目前也已产生了许多算法加速策略，本节余下部分将围绕这一主题展开。图6 RRT*算法流程
1.2.1 利用确定性采样方式提升算法性能
SBMP算法最初都使用了随机采样方式，那么一个问题是：如果以确定性方式进行采样，相关的理论保证和实际性能还会成立吗？答案是肯定的，确定性规划器可以简化证明过程，可以将一部分在线计算量变为离线计算（这对考虑微分约束的规 划和高维空间中的规划尤其有意义）。另外对于栅格序列，亦可简化操作量（如定位相邻点）。以PRM为例，实质上“概率性”对其是不重要的，反而会导致采样点的不规则分布，使连通性信息的捕捉变得更加复杂。Lavalle等将局部规划器引入经典网格搜索，发展了子采样网格搜索（Subsampled Grid Search，SGS）算法，并将确定性的低差异度采样技术引入PRM，发展了 拟随机路图算法（Quasi-Random Roadmap）和栅格路图（Lattice Roadmap）算法，进行对比实验后发现：相较于分辨率完备的确定性采样方法（包括网格搜索），原始的PRM算法并没有体现出优势。故文章对“随机性是打破高维空间维数诅咒的必要分量”这一说法进行了驳斥，事实上为了维持固定的离散度，任何采样 方案都需要与维数成指数关系的采样点数量。但Lavalle等的工作仅限于讨论可行路径，就收敛到最优路径而言，独立同分布采样是否还有优势？Jason等针对 PRM算法进行了讨论（设为从自然数集到实数集的映射，约定表示存在某个自然数和正实数，使得对于所有，；表示存在某个自然数和正实数，使得对于所有，；表示:1）确定性渐进最优性，在维空间中，使用离散度的上界为，连接半径的确定性采样序列的PRM算法是确定性渐进最优的。而使用独立同分布随机采样序列的PRM*算法是概率性渐进最优的，且需要更大的连接半径。2）收敛率，在没有障碍物的情况下，采用确定性采样序列的PRM的次优因子上界为，其中是采样序列的离散度（存在障碍物时的结果更复杂一点）。而采用独立同分布采样的类似结果仅是概率成立，且更加繁琐和难以理解。3）计算复杂度和空间复杂度，在低离散度栅格上运行PRM的计算复杂度和空间 复杂度为。由于可以用来获得渐近最优性，故PRM存在一个计算复杂度和空间复杂度为的渐近最优版本。而使用独立同分布采样的复杂度结果为量级。可以看出确定性方法在需要更小的连接半径的同时，具有更好的计算复杂度和时间复杂度。本质原因在于确定性低离散度序列和独立同分布序列间离散度的差异，二者分别为和。另外，从使用低离散度栅格的PRM中得到的结果在其他一些情况下也精确或近似地成立，如k-nearest-neighbor算法、批处理算法、非栅格的低离散度采样序列（如Halton序列）、非均匀采样和含微分约束的规划等。多类实验结果表明：对于给定数量的采样点，确定性低离散度采样不会差于独立同分布采样。因而结合Lavalle的结论，Jason等建议基于SBMP算法都应使用非独立同分布的低离散度采样序列。1.2.2 利用收集到的形状信息改善采样分布事实上中的可视特性并非均匀分布，且描述整个可视特性的取决于其中最差的构型和lookouts。当含有狭窄通道时，以上3个参数就会减小。而为了保证算法的失败概率不超过，由式（2）可知所需的均匀采样点数量随即大幅增加。如果规划器能根据已有的或运行过程中收集到的信息对的形状做出概率上的推测，则可以此推测来偏置采样点分布，使其能更好地捕捉C-space的连通特性，从而减少所需的采样点数量，提高算法效率。但显式维持该概率模型的代价很高，因此早期研究仅是用启发式来近似最优采样策略，其本质上是一种离线方法。包括基于工作空间的策略、基于障碍物的策略、基于可视性的策略、Bridgetest采样策略等。但由于基于可视性的策略采用的是拒绝采样方式，故实际使用中的效果不太理想。自适应采样则在线调整采样点的分布。Hsu等将以上离线偏置采样方法线性加权，并在每次采样后调整权重，称为混合PRM采样策略。由于“边界点”一般有更大的Voronoi偏置却不能被成功扩展，Yershova等针对含有复杂几何的运动规划问题，提出了将“边界点”采样域限制在以预设值为半径的球内的Dynamic Domain RRT（DD-RRT）方法。Jaillet等则根据“边界点”成功扩展的概率来调整边界域半径，实验结果表明Adaptive Dynamic-Domain RRT（ADD-RRT）在大多数实验场景下都比原始RRT的性能高出数个量级。对于多疑问运动规划问题，Burns和Brock建立了表示形状的混合高斯模型和k-nearest-neighbor模型］，并用采样信息更新该模型。前者最大程度地减小模型方差，后者则用期望效用来引导采样。相应结果同样被扩展至单疑问运动规划问题，在提升计算效率的同时也增强了规划器的鲁棒性。1.2.3 利用解路径代价和尚需代价的估值导引采样分布随着采样点数量趋于无穷，虽然RRT*可以保证渐进收敛到最优解，但这种按照随机次序进行搜索的方式在无用状态上浪费了大量计算时间，降低了算法效率，使其难以应用到一些实际问题中，如****空间（即室外环境中的规划）和高维空间（即机械臂的规划）。因而启发式被用来或缩小搜索区域，或安排搜索次序。heuristically-guided RRT（hRRT）算法以与启发代价成反比的概率选择采样点，使采样树朝着低代价区域生长，从而得到质量更好的次优路径。Anytime RRT迭代地用前次的解来界定本次的搜索范围，用与hRRT类似的思路选择待扩展节点，使解路径的代价随运行次数不断下降，但并未提供最优性保证，且前次采样点被不断丢弃 ，信息复用率不高。Transition-based RRT将构型空间代价地图与规划问题作为输入，用随机优化方法决定是否保留新的采样点，以使RRT朝着构型空间代价地图的谷地和鞍点进行扩展。Karaman等通过“图修剪”技术，周期性地移除那些当前代价与启发式代价之和大于已有最路径代价的顶点，发展了RRT*的Anytime版本。Hauser则在“图修剪”技术的基础上结合Lazy检测，提出了Lazy-PRM*算法和Lazy-RRG*算法。Akgun和Stilman、Islam等均采用了路径偏置方法，即通过增加当前解路径节点邻域的采样频率来加速RRT*的收敛，但该方法基于不切实际的同伦假设且需持续全局采样以规避局部极小值。除此之外，前者还用到了双向搜索和采样点拒绝（Sample-Rejection）技术，虽然一次采样迭代消耗的时间极短，但随着关注区域与间体积比率的减小，找到一个可接受的采样点所需的迭代次数也会增加，此时的计算量便再不容忽视。RRT#利用启发式在由RRG递增建立的图上寻找并更新树，并通过LPA*将变化传播到整个图中，从而有效维持了到每个顶点的最优连接。虽然用启发式缩小搜索区域的方法带来了一定的性能提升，但其仍采用了与RRT*类似的扩展次序，使得重要的、难以采样的状态由于目前不能连接到树而被简单丢弃，同时还可能浪费计算 时间。Informed RRT*首先运行原始的RRT*算法，待找到解后再直接在不断缩小的椭球形信息集内进行采样（参见图7）。相比于RRT#，Informed RRT*在椭球体积减少时，仍能有效提高收敛率和解路径质量。图7 Informed RRT*算法流程至此所述方法虽然均在最优解的收敛速度上有所改进，但本质上其生长树的方式都是无序的。Jason等用一种Marching方法，按Costto-Come递增的次序（类似于 Dijkstra算法）搜索一批采样点。其中空间近似和搜索的分离使得搜索次序独立于采样次序，但却牺牲了Any⁃time特性。在搜索完成之前，FMT*不会返回解路径。另外也与其它先验离散方法一样，如果解不存在，则搜索必须重新开始。Gammell等试图将有信息的图搜索算法和具有Anytime特性的RRT*算法统一至同一框架下，从而发展了一种可以有效解决连续空间路径规划问题的有信息、有 Anytime特性、有渐进最优保证且避免大量计算无用状态的基于采样的运动规划算法—Batch Informed Trees（BIT*），该方法的主要贡献在于维持潜在解路径质量的优先级序列的同时利用分批采样技术，使空间近似和空间搜索得以交替进行。一些BIT*的改进算法也已被提出：Advanced BIT*（ABIT*）使用类似于ARA*的次优启发式因子快速找到初始解路径，再以Anytime形式向最优解路径收敛。Adaptively Informed Trees （AIT*）通过对称双向搜索来同时估计并使用一个精确的、针对特定问题的启发式，可较好地适用于局部路径评估较昂贵的情况。Regionally Accelerated BIT*（RABIT*）利用局部优化器来解决不能通过直线连接的状态之间的连接问题，有助于在难以采样的同伦类中找到路径。除上述算法之外，为平衡最优性与计算效率间的矛盾，一些文章也通过放松关于最优性的要求，对渐近近优（Asymptotically Near Optimal）算法进行了讨论。

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。