Sampling-Based Planning

A family of motion-planning methods that randomly sample points in configuration space and connect the collision-free ones into a path.

Sampling-based planning is one of the dominant approaches to motion planning (finding a collision-free path from start to goal). Steven LaValle's textbook Planning Algorithms frames the idea as: rather than explicitly building the set of configurations that collide, randomly sample points in configuration space (the space of all possible joint angles) and hand each point and each connecting segment to a collision-checking module as a black box. Representative algorithms include the probabilistic roadmap (PRM), which builds a reusable, multi-query road network; the rapidly-exploring random tree (RRT), which grows a tree from the start for single-query use; and the asymptotically optimal RRT* and PRM*. It excels at high-dimensional problems such as 6–7 degree-of-freedom arms, but only offers probabilistic completeness (the probability of finding a solution approaches 1 as samples grow), and paths are often jagged, needing further smoothing and time parameterization. The open-source library OMPL implements most of these algorithms.

ExampleTo reach a 7-DOF arm's hand from above a table into a cabinet, RRT-Connect grows one random tree from the start and one from the goal; once the trees connect, a collision-free path results, which path smoothing then cleans up by removing unnecessary turns before execution.

Also called

Sampling-Based Motion Planning

Related

Motion Planning · Rapidly-exploring Random Tree · Probabilistic Roadmap · Probabilistic Completeness · Configuration Space (C-Space) · Open Motion Planning Library (OMPL)

Sources

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