基于采样的规划

在构型空间里随机撒点、用碰撞检测筛选后连成无碰路径的一类运动规划方法。

基于采样的规划是运动规划（找一条从起点到终点且不碰撞的运动）中的主流方法之一。LaValle 的教材《Planning Algorithms》把它的思路概括为：不显式构造会碰撞的构型集合，而是在构型空间（所有关节角组成的空间）里随机采样，把每个点和每段连线交给碰撞检测模块当黑箱判断。代表算法有先建路网、可反复查询的概率路线图 PRM，从起点长树、单次查询的快速扩展随机树 RRT，以及渐近最优的 RRT*、PRM*。它擅长 6–7 自由度机械臂这类高维问题，但只有概率完备性（采样足够多时找到解的概率趋于 1），路径往往曲折，需要再做平滑和时间参数化。开源库 OMPL 实现了其中大部分算法。

例子让 7 自由度机械臂把手从桌面上方伸进柜子：RRT-Connect 从起点和终点各长一棵随机树，两棵树接上即得到一条无碰路径，再经路径平滑去掉多余拐弯后执行。

也叫

采样式规划、基于采样的运动规划

相关

运动规划、快速扩展随机树、概率路线图、概率完备性、构型空间、OMPL

来源

LaValle, Planning Algorithms, Chapter 5: Sampling-Based Motion Planning
OMPL: Available Planners