Probabilistic Completeness

A planner property: whenever a solution exists, the chance of finding a feasible path approaches 1 as sampling increases.

In motion planning, an algorithm is ‘complete’ if it finds a solution in finite time whenever one exists, and correctly reports failure when none does — only exact, combinatorial planners achieve this. Sampling-based planners like PRM and RRT can't, so they settle for the weaker guarantee of probabilistic completeness: as Steven LaValle's textbook Planning Algorithms puts it, as long as a solution exists, the probability of finding it converges to 1 as the number of samples grows. Sertac Karaman and Emilio Frazzoli gave a rigorous definition in 2011 and showed that the probability RRT or PRM fail to find an existing solution decays exponentially with the number of samples. It has two practical limits: a feasible path needs some clearance from obstacles, so very narrow passages are almost never sampled; and when no solution exists, the algorithm just keeps running rather than ever declaring failure. It is often mentioned alongside the stronger property of asymptotic optimality, where path cost converges almost surely to the optimum as samples grow — plain RRT has only probabilistic completeness, while RRT* has both.

ExampleWhen MoveIt calls an OMPL planner, you set a planning time limit: a probabilistically complete algorithm is more likely to find a solution the more time it is given. But if the goal pose is completely boxed in by obstacles, it won't report 'no solution' — it will just run until the timeout and return failure.

Also called

Probabilistically Complete

Related

Sampling-Based Planning · Rapidly-exploring Random Tree · Rapidly-exploring Random Tree · Probabilistic Roadmap · Configuration Space (C-Space) · Motion Planning

Sources

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)