Robot Software
RRT, PRM, CHOMP: Motion Planners Compared
Sampling planners find a path in seconds but produce ugly ones. Optimisation planners produce smooth paths but get stuck. Which to use for which robot task, and why most stacks use both.
Sampling-based planners such as RRT and PRM find a collision-free path in a high-dimensional space quickly, typically in 10 to 500 milliseconds for a 6-axis arm, and the path they return is jagged. Optimisation planners such as CHOMP and its successors produce smooth, short paths but can fail entirely in cluttered scenes. Production stacks use a sampling planner to find a path and an optimiser to clean it up.
Why this is hard at all
Motion planning searches the configuration space, which has one dimension per joint. A six-axis arm plans in six dimensions, a dual-arm humanoid with a torso in twenty or more. Obstacles in the workspace become complicated regions in configuration space that cannot be computed explicitly, which is why planners sample or optimise rather than search exhaustively. The volume of the space grows exponentially with dimension, and that single fact explains the design of every algorithm below.
| Planner | Type | Typical solve time | Produces | Fails when |
|---|---|---|---|---|
| RRT | Sampling, single query | 10 to 200 ms | A valid path, jagged | Narrow passages |
| RRT-Connect | Sampling, bidirectional | 5 to 100 ms | A valid path, faster | Narrow passages |
| RRT* | Sampling, asymptotically optimal | 100 ms to seconds | Improving path over time | Time budget too short |
| PRM | Sampling, multi-query roadmap | seconds to build, ms to query | Reusable roadmap | Environment changes |
| CHOMP | Trajectory optimisation | 50 to 500 ms | Smooth path | Local minimum in clutter |
| STOMP | Stochastic optimisation | 100 ms to seconds | Smooth path, no gradients needed | Cluttered scenes |
| TrajOpt | Sequential convex optimisation | 50 to 400 ms | Smooth path with constraints | Poor initial guess |
| Learned planners | Neural | 1 to 50 ms | Fast proposals | Out-of-distribution scenes |
Sampling planners, and the narrow passage problem
A rapidly exploring random tree grows from the start configuration toward random samples, checking each extension for collision. It is probabilistically complete, meaning that given enough time it finds a path if one exists, and it is fast in open spaces. Its weakness is a narrow passage: a region where valid configurations occupy a tiny fraction of the sampled volume, so random sampling almost never lands in it.
The practical form of that weakness is recognisable. A robot that plans instantly to a point in free space but takes seconds to plan into a machine through an open door is meeting a narrow passage, and the remedies are biasing samples toward the passage, planning in stages through an intermediate waypoint, or widening the passage physically.
What production stacks actually run
- Try a cached or taught path first. Most industrial motions repeat. Planning a fresh path for a motion performed 4,000 times a day is wasted computation and unpredictable timing.
- Plan with a bidirectional sampling planner when the scene has changed, with a hard time budget.
- Shortcut and smooth the result, which is cheap and improves cycle time materially.
- Time-parameterise against the robot's real velocity, acceleration and jerk limits. This step, not the planner, determines cycle time.
- Fall back deterministically. If planning exceeds its budget, retreat to a known safe path rather than continuing to search while the line waits.
Point five separates laboratory code from production code. A planner without a bounded failure behaviour will eventually stall a cell, and the operator will not care which algorithm was responsible.
Collision checking is where the time goes
Planners are usually described by their search strategy, but 80 % to 95 % of their runtime is spent answering one question repeatedly: is this configuration in collision. Making that question cheaper speeds up every planner at once.
| Representation | Check cost | Fidelity | Use |
|---|---|---|---|
| Bounding spheres | 1x | coarse | Broad phase rejection |
| Capsules on links | 2 to 4x | good for arms | Standard for manipulators |
| Convex hulls | 5 to 15x | good | Tooling and fixtures |
| Full mesh | 50 to 500x | exact | Final verification only |
| Voxel or octree of sensor data | 3 to 20x | depends on resolution | Unknown or changing environments |
The practical recipe is a two-phase check: reject most configurations with spheres or capsules in a fraction of a microsecond, and only run the expensive representation on the few that survive. Teams that plan directly against full meshes usually find their planner ten to fifty times slower than it needs to be.
Frequently asked questions
Which motion planner should I use?
A bidirectional sampling planner such as RRT-Connect to find a path, followed by shortcutting and smoothing. Add a trajectory optimiser where path quality matters, and cache repeated motions rather than replanning them.
Why does planning sometimes take seconds?
Almost always a narrow passage, where valid configurations occupy a tiny fraction of the sampled space, such as reaching through a machine door. Sample biasing, an intermediate waypoint or a physically wider opening are the fixes.
What is the difference between sampling and optimisation planners?
Sampling planners search randomly for any collision-free path and are robust in clutter but produce jagged results. Optimisation planners refine a trajectory against a cost function and produce smooth paths but can stall in local minima in cluttered scenes.
Does the planner determine cycle time?
No, time parameterisation does. The planner produces a geometric path; converting it into a timed trajectory against velocity, acceleration and jerk limits is what sets how long the motion takes.
Are learned planners usable in production?
As fast proposal generators inside a stack that still verifies collisions and has a classical fallback. Used alone they fail unpredictably on scenes outside their training distribution, which is unacceptable in a cell.
Sources
- Open Motion Planning Library documentationReference implementations and characteristics of the sampling planners described
- arXiv robotics preprints, motion planningPrimary literature on sampling and optimisation-based planning
- ISO 8373, robotics vocabularyInternational Organization for Standardization, definitions of path, trajectory and pose