概率完备性

只要解存在，采样越多、找到可行路径的概率就越趋近 1 的算法性质。

运动规划里的「完备」指：有解就在有限时间内找到，无解就报告无解，只有组合式的精确规划能做到。PRM、RRT 这类基于随机采样的规划器做不到，退而保证概率完备：LaValle《Planning Algorithms》的说法是，只要解存在，随着采样点增多，找到解的概率收敛到 1。Karaman 与 Frazzoli 2011 年给出严格定义，并指出 RRT、PRM 找不到解的概率随样本数指数下降。它有两个局限：可行路径得离障碍留出一点余量，极窄的通道几乎采不到；无解时算法会一直跑，无法宣布无解。它常和「渐近最优性」一起出现，后者更强：样本无限增多时路径代价几乎必然收敛到最优。RRT 只有前者，RRT* 两者都有。

例子MoveIt 调用 OMPL 规划器时要设规划时限：概率完备的算法给的时间越多越可能找到解；但如果目标位姿被障碍物完全包住，它不会报告「无解」，只会跑到超时返回失败。

也叫

概率完备、Probabilistically Complete

相关

基于采样的规划、快速扩展随机树、快速扩展随机树、概率路线图、构型空间、运动规划

来源

S. M. LaValle, Planning Algorithms, Chapter 5: Sampling-Based Motion Planning
Karaman & Frazzoli, Sampling-based Algorithms for Optimal Motion Planning (arXiv:1105.1186, IJRR 2011)