Motion Planning
RRT and its optimal variants, trajectory optimization, and CHOMP/TrajOpt.
- Last reviewed
- Reading time
- 20 min
- Citations
- 10
Motion planning answers a deceptively simple question: given where the robot is and where it needs to be, what motion gets it there without hitting anything? Kinematics tells you where the arm is for a given set of joint angles; planning finds the sequence of joint angles worth executing. It is the layer where geometry becomes a decision, and it is the layer most learned policies quietly replace or lean on, depending on whom you ask.
Sampling-based planning and trajectory optimization start differently. A sampling planner explores configurations and connections; an optimizer starts with a complete candidate trajectory and improves an objective. Neither a smoothness objective nor an initial guess guarantees that local optimization will find a collision-free motion. CHOMP and TrajOpt both examine planning from infeasible guesses as well as refining existing trajectories Ratliff 2009Schulman 2013.
The sampling family is below, running for real: a 2D world, five obstacles between start and goal, one accepted extension per iteration from a fixed seed. Press Run, or drag the exploration iteration slider, and watch the tree flood open space, leak through the gap above the wall, and only then stumble into the goal region. Sampling is mostly uniform, with a small bias toward the known goal.
iteration 0 / 288 nodes 1 tree not started path length n/a
The RRT tree is at iteration 0 of 288 with 1 node and status tree not started; path length is n/a until a branch first reaches the goal.
Current RRT tree state
- iteration
- 0 / 288
- nodes
- 1
- status
- tree not started
- path length
- n/a
One accepted extension per iteration from a fixed seed, so the growth is identical on every load. Each step samples a random point (1.5% of the time the goal itself), finds the nearest tree node, and extends a fixed length toward it, keeping the branch only when the segment stays clear of the obstacles. The bias toward unexplored space is why the canopy spreads first and the goal connection arrives late.
Configuration space
Planning in the physical workspace is awkward because the robot has extent: every link sweeps volume, and collision is a statement about whole bodies. The standard reformulation, due to Lozano-Pérez in 1983, moves the problem into configuration space Lozano-Pérez 1983. A configuration is one complete specification of the robot's posture, the vector of its joint values, and the configuration space is the set of all of them. A point robot in the plane has a 2D configuration space; a 7-DoF arm has a 7-dimensional one, one axis per joint.
Obstacles lift into this space too. The configuration-space obstacle is the set of configurations where any part of the robot intersects anything it should not, and the rest is free space:
The classical construction shrinks the robot to a point and grows each obstacle by the robot's shape, so collision checking reduces to point membership Lozano-Pérez 1983. Planning is then a clean statement: find a continuous curve in from to . The difficulty is constructing the collision-constrained space, not a universal cutoff at a few dimensions. LaValle describes explicit boundary or solid representations as difficult, but also gives constructive translational cases and explains that semi-algebraic models for chains and trees can be generated automatically. His PSPACE-hardness statement concerns the basic semi-algebraic mover problem when the number of degrees of freedom is unbounded; it is not an impossibility result for every seven-joint arm LaValle 2006. Sampling-based methods avoid explicit obstacle construction by probing a collision module, while still needing to validate entire local paths. Closed-chain constraints can also make efficient sampling difficult LaValle 2006.
Sampling-based planning
Sampling-based planning can avoid an explicit configuration-space obstacle model by querying a collision-detection module for candidate configurations and validating local paths LaValle 2006. The probabilistic roadmap (PRM) of Kavraki, Svestka, Latombe, and Overmars samples configurations uniformly at random, keeps the collision-free ones as milestones, connects nearby milestones with a local planner, and answers queries by searching the resulting graph Kavraki 1996. It is a multi-query method: build the roadmap once, plan many start-goal pairs against it.
LaValle's report introduces the rapidly-exploring random tree at Iowa State University LaValle 1998. His textbook bibliography identifies it as Computer Science Technical Report 98-11, October 1998 LaValle 2006. The report starts a tree at an initial state. Each iteration samples a state in a bounded space, finds the nearest tree vertex under the chosen metric, selects a control input, and integrates the system over a fixed time interval. The vertices and the entire local paths represented by edges must remain in free state space LaValle 1998.
For dynamics , the report gives the Euler approximation
where is the starting state and is the chosen input. The report says a higher-order integrator such as Runge-Kutta is usually preferable. A fixed integration interval does not impose a fixed geometric extension distance for arbitrary dynamics LaValle 1998.
LaValle's 2006 Section 5.5 explicitly removes the original step-size parameter. Its initial obstacle-free construction connects each sample to the nearest point in the tree's swath, the union of its edge paths. That point can lie inside an edge; Figure 5.18 splits the edge and inserts a vertex there. This construction is distinct from the original fixed-time control-integration rule LaValle 2006.
Nearest-neighbor selection gives RRT an exploration bias. In the report's planar holonomic example, frontier vertices have larger Voronoi regions and are more likely to be selected for expansion LaValle 1998. The book's step-size-free dense-tree construction assumes an infinite dense sample sequence; a random sequence, including a biased one, must be dense with probability one. Its obstacle-free construction reaches each sample, while collision checking limits extensions when obstacles are present. This is not a guarantee of fast coverage on every problem: the report leaves convergence-rate analysis open, and the book distinguishes exploring free space from solving a start-goal query LaValle 1998LaValle 2006. The same construction handles dynamics by steering with controls instead of straight lines, which is the kinodynamic version LaValle and Kuffner developed LaValle 2001. Probabilistic completeness is a limiting-probability property, not an assurance that an arbitrary existing path will be found LaValle 2006. For a precise example, Karaman and Frazzoli state it for simplified PRM (sPRM) and their geometric RRT under the Euclidean model , , an open goal region, and robust feasibility: a solution path must have some positive clearance . Their algorithms use independent uniform free-space samples, a fixed positive connection radius for sPRM, RRT steering capped by a positive distance parameter, and collision tests over entire straight-line connections. Under those assumptions the probability of finding a solution tends to one. The result does not automatically extend to implementation heuristics; their 1-nearest sPRM counterexample is not probabilistically complete Karaman 2011.
The Voronoi bias is what the scene at the top of this module is showing: the tree spreads because unexplored space claims more of the frontier, and the start-to-goal path lights up only once the goal region is reached.
Optimality: RRT*
Karaman and Frazzoli's 2011 analysis separates finding a feasible path from improving its cost. Their RRT non-optimality proof includes an obstacle-free Euclidean example with a steering distance at least the domain diameter in which the best path cost converges almost surely to a suboptimal value. Their PRM result concerns the forest-building version that rejects connections within an already connected component; it is not a result about every roadmap planner. The same paper proves asymptotic optimality for fixed-radius simplified PRM, which allows those connections, at greater computational cost Karaman 2011.
RRT* adds least-cost parent selection and rewiring; Algorithm 6 writes these costs additively. A new vertex keeps its feasible nearest parent unless a collision-free connection through a nearby vertex gives a cheaper path from the root. Neighbors are reattached only when a collision-free route through the new vertex lowers their cost. With vertices, Algorithm 6 uses
where caps the local steering distance and is the Euclidean space dimension. The coefficient must be sufficiently large for the problem: Theorem 38 and Appendix G's Lemma 71 print different sufficient bounds. The latter's conservative condition is , where is free-space volume and is unit-ball volume; this is not a claim that the coefficient is minimal Karaman 2011.
The convergence statement is conditional and concerns a bounded Euclidean domain. The paper uses independent uniform free-space samples, Euclidean distance and straight-line collision checking, not differential constraints. Its cost is positive on nontrivial paths, monotone under concatenation and bounded by a constant times path length. A finite-cost optimum must be robust: it has weak clearance, meaning it can be continuously deformed into paths with positive clearance, and the cost must be continuous for paths approaching that optimum in the paper's bounded-variation norm. Under this setup, its RRT* result is
Here is the best feasible solution cost after iterations. This is an asymptotic cost guarantee, not a promise of an exact optimum after a finite budget. The non-optimality analysis also assumes that the set of states traversed by optimal paths has measure zero Karaman 2011.
The computational comparison is narrower than a runtime promise: for fixed dimension and environment, the paper's efficient spatial-search model gives expected asymptotic processing work of order for RRT*, within a constant factor of RRT's processing order. It does not bound every iteration's elapsed time by the same factor. In particular, its collision-check count grows as per iteration, while plain RRT makes one such check Karaman 2011.
RRT* with global sampling also improves routes to states irrelevant to a particular start-goal query. Informed RRT* addresses that work after a first solution is found. For Euclidean path length in with fixed start and goal, it samples directly from the planning domain's intersection with
This is a prolate hyperspheroid with start and goal as its foci and current best path length as its transverse diameter. Writing for the optimal start-goal cost constrained through , the true improving set is . The distance sum is an admissible lower bound: the region contains every state on a strictly improving feasible path, but a state inside it need not be collision-free or belong to any improving path. The planner still performs collision checks. Before the first finite-cost solution, it samples globally like RRT* Gammell 2014.
The paper reports the underlying RRT* completeness and optimality guarantees, not a universal speedup. Its linear expected-cost convergence calculation assumes no obstacles and a rewiring radius larger than the informed subset's diameter. Its simulation comparisons used common unoptimized code and 100 runs per variation on shared maps and seeds, with random-world refinement measured for 60 seconds after an initial solution. Those experiments found faster refinement than RRT*; when the informed set covers the planning domain, the heuristic supplies no focusing advantage Gammell 2014.
Section V describes the Sample routine more strongly, as if every sampled state admits an improving path. That wording exceeds the admissible-superset construction in Section III and Algorithm 2; geometric membership alone does not establish it. Section V-A also leaves the exact informed rewiring-radius expression as ongoing work, so the paper does not supply a settled new threshold here Gammell 2014. The Open Motion Planning Library's project documentation lists implementations of PRM and RRT, along with benchmarking tools for comparing planners. The core library is designed to integrate with external collision-checking and visualization components Șucan 2012.
Trajectory optimization
Trajectory optimization makes the trajectory the decision variable. Smoothness, obstacle clearance, and task requirements enter an objective or constraints; solving the local optimization problem is not the same as guaranteeing a feasible global route.
CHOMP: a smoothness metric, not a local step-size rule
CHOMP combines an obstacle cost with an environment-independent prior on trajectory dynamics. In the paper's discrete formulation, contains the interior waypoints, computes finite differences, and accounts for the fixed endpoints:
The retained CHOMP body is an eight-page preprint, distinct from the landing page's six-page ICRA publication. The first derivative term penalizes squared velocity; higher-order terms can penalize other dynamics. This discrete expression is the source's explicit half-weighted formula, rather than an assertion that its continuous prior is printed with the same normalization Ratliff 2009.
The obstacle cost integrates over the robot's body elements and their arc length through the workspace. A workspace signed-distance field is negative inside an obstacle and positive outside; its penalty discourages low clearance. Arc-length weighting prevents merely moving faster through a costly region from reducing that obstacle cost. Covariant descent uses the inverse of a smoothness metric to distribute a gradient update along the trajectory while retaining smoothness. It is not a rule that selects large steps at cheap locations and small steps at expensive ones Ratliff 2009.
The arm experiment used the first six joints of a seven-DoF Barrett WAM. Its 15 endpoint configurations yielded 105 planning problems, of which CHOMP solved 99. The reported implementation used a voxel grid and Matlab distance-field computation; 400 optimization iterations took approximately 12 seconds, with the core optimization usually completed in the first 100 iterations, approximately 3 seconds. The inspected body does not name the processor. Those are setup-specific timings, not a processor-independent real-time claim. In the LittleDog experiment, CHOMP instead operated inside a footstep controller informed by a separate footstep planner. Trunk motion was initialized with a ZMP preview controller and swing-foot motion by interpolation, with stability and reachability criteria added. Its trajectories were generated before execution because worst-case optimization could take longer than the motion Ratliff 2009.
CHOMP can turn an infeasible initial guess into a useful trajectory without a separate motion planner on many queries. But the paper also implements a Hamiltonian Monte Carlo variant and records finite-time local-minimum failures. Neither “no samples” nor “no search” describes every variant or guarantees success Ratliff 2009.
TrajOpt: penalties, trust regions, and collision limits
TrajOpt solves a sequence of convex subproblems. Its kinematic objective sums squared displacements between successive waypoints. Nonlinear constraints enter an penalty method, with penalty coefficients increased in an outer loop as necessary; linear constraints are imposed directly. This does not eliminate soft penalties in favor of hard constraints from the first iteration. For a signed distance that is positive when objects are separated, the collision penalty is
It is active below the safety margin. The collision checker considers nearby pairs out to , so the linearized subproblem can also account for some pairs that currently have zero penalty. A box trust region limits each proposed update; it expands when actual improvement sufficiently agrees with the local model and shrinks otherwise Schulman 2013.
Checking only waypoints can miss a collision in the motion between them. TrajOpt therefore considers a modeled swept volume. For the translational case its construction uses the convex hull of endpoint shapes; rotations require additional inflation. The paper states a bound with added to the safety margin, but omitted this correction in its experiments because it was well under 1 cm. It also notes that its swept-volume gradient approximation is not guaranteed accurate in 3D. The implementation used Bullet and convex hulls of robot meshes, and its continuous-time collision cost did not cover self-collisions: those were penalized at discrete times. These qualifications rule out an unconditional claim that thin obstacles can never be missed, especially for an arbitrary interpolation executed by a controller Schulman 2013.
What the TrajOpt benchmark measured
The benchmark used four simulated MoveIt scenes with fixed start and goal configurations: 198 seven-DoF PR2 arm problems and 96 eighteen-DoF full-body problems. The arm trajectories had 11 timesteps and the full-body trajectories 41. A single initialization was a straight line; the arm multi-initialization condition used four manually selected intermediate configurations, while full-body planning used up to five collision-free base configurations sampled with the arms tucked. OMPL methods used default parameters and MoveIt's default smoother. Path length was normalized by the shortest path found for that problem across the compared planners; it was not a separate smoothness measurement Schulman 2013.
| Arm method | Success fraction | Average time (s) | Average normalized length |
|---|---|---|---|
| TrajOpt | 0.84 | 0.20 | 1.2 |
| TrajOpt, multiple initializations | 0.99 | 0.32 | 1.2 |
| OMPL RRTConnect | 0.97 | 1.2 | 1.6 |
| OMPL LBKPIECE | 0.96 | 3.1 | 1.7 |
| CHOMP | 0.66 | 3.1 | 2.4 |
| CHOMP, multiple initializations | 0.85 | 6.0 | 2.6 |
These are Table I's arm results. In particular, single-initialization TrajOpt solved a smaller fraction than either OMPL comparator; the multi-initialization result supports the stronger success comparison. The tested CHOMP implementation was supplied by its authors and is not established as identical to the earlier 2009 preprint Schulman 2013.
| Full-body method | Success fraction | Average time (s) | Average normalized length |
|---|---|---|---|
| TrajOpt | 0.63 | 2.1 | 1.08 |
| TrajOpt, multiple initializations | 0.84 | 7.6 | 1.09 |
| OMPL RRTConnect | 0.53 | 18.0 | 1.5 |
| OMPL LBKPIECE | 0.50 | 18.7 | 1.5 |
Table II contains no CHOMP full-body result: the authors lacked the documentation or data needed to run that comparison. Its measured full-body times also qualify the introduction's subsecond characterization. The introduction says all planners had ten seconds, while the experimental section specifies three seconds per CHOMP initialization and a thirty-second full-body OMPL limit. Those statements should not be collapsed into a single matched-budget protocol. The inspected paper does not identify the processor used for these benchmark timings Schulman 2013.
Initial guesses and the two-stage pattern
Both methods need an initial trajectory and can remain trapped in a bad local minimum. That does not make a sampling-based preplanner mandatory. CHOMP compared straight-line and RRT initializations; among queries where collision removal succeeded, straight-line initialization often produced the better objective. TrajOpt likewise evaluated planning from infeasible seeds and found that multiple initializations changed success rates Ratliff 2009Schulman 2013.
Ratliff and colleagues describe PRM and RRT as typically used in a two-phase process: first find a feasible path, then remove redundant or jerky motion. Schulman and colleagues distinguish two roles for trajectory optimization: refining a trajectory generated by another method, or planning from scratch. Those are the papers' accounts, not evidence that sampling followed by refinement is the standard industrial pipeline today Ratliff 2009Schulman 2013.
Where this meets the learned stack
Classical planning did not disappear when learned policies arrived; it changed jobs. Sampling planners label demonstration data, verify that a proposed motion is feasible, and generate the diverse training scenes that generative simulation pipelines rely on. Optimization survives inside model-predictive control, which replans a short horizon at every control cycle, a design whose tradeoffs against learned policies have their own module in reward design and the MPC debate. And the hierarchical school of robot learning, from SayCan onward, is precisely the bet that a learned system should emit goals for a classical planner to execute, a bet the end-to-end camp answers by training the planning in.
What end-to-end policies do not escape is the geometry. A diffusion policy's action chunk is a trajectory in configuration space; an RRT's path is a trajectory in configuration space. The difference is who computed it, a planner with an explicit collision model or a network with an implicit one. The modules that follow, control and state estimation, assume some such trajectory exists and ask how to track it and where the robot actually is while doing so.
The runtime handoff contract
A deployable planner consumes more than a start and goal. It needs the robot model, current state, collision geometry, allowed contacts, attached objects, joint limits, timing limits and a controller capable of executing the returned trajectory. Give each input a freshness rule. A collision-free path against a stale scene is not a safe path, and a valid geometric path can still violate velocity or torque limits after time parameterization.
The ROS 2 guide locates these artifacts in the runtime graph. For hybrid systems, keep the handoff explicit: a learned component may propose a goal, cost, waypoint or whole action chunk, while a planner or command gate checks the constraints the model cannot certify. Log the scene version and planning request with every execution. That record distinguishes planning failure, world-state failure and tracking failure instead of collapsing all three into “the robot missed.”
See also
- Kinematics
Forward and inverse kinematics, DH parameters, and the Jacobian; the theory behind the 3D playground.
- Control
PID, LQR, MPC, and whole-body QP: the classical stack under every learned policy.
- ROS 2 for Machine Learning Engineers
Topics, services, actions, QoS, tf2, rosbag2 and MoveIt explained as the production boundary around a learned policy.
- Hierarchical Approaches
SayCan, code-as-policies, and keypoint affordances; why separate planners gave way to internalized hierarchy.
Linked from
- Kinematics
Forward and inverse kinematics, DH parameters, and the Jacobian; the theory behind the 3D playground.
- Control
PID, LQR, MPC, and whole-body QP: the classical stack under every learned policy.
- State Estimation
Kalman filters, factor graphs, and pose estimation from noisy sensors.
- Grasp Planning
Contact mechanics, grasp quality metrics, and force closure.
- Scene Representation and Mapping
What a robot remembers about the space around it, and why the map that renders best is not the map a planner can use.
- Space Robotics
NASA/JPL systems, orbital servicing, and ISRU: robotics where repair is impossible.
References
Tomás Lozano-Pérez, IEEE Trans. Computers, 1983.
https://doi.org/10.1109/TC.1983.1676196
Lydia E. Kavraki, P. Švestka, J.-C. Latombe, M. H. Overmars, IEEE Trans. Robotics and Automation, 1996.
https://doi.org/10.1109/70.508439
Steven M. LaValle, Iowa State University TR 98-11, 1998.
https://lavalle.pl/papers/Lav98c.pdf
Steven M. LaValle, James J. Kuffner, Int. J. Robotics Research, 2001.
https://lavalle.pl/papers/LavKuf01b.pdf
Sertac Karaman, Emilio Frazzoli, arXiv preprint, 2011.
https://arxiv.org/abs/1105.1186
Jonathan D. Gammell, Siddhartha S. Srinivasa, Timothy D. Barfoot, IROS 2014.
https://arxiv.org/abs/1404.2334
Nathan Ratliff, Matthew Zucker, J. Andrew Bagnell, Siddhartha Srinivasa, ICRA 2009.
https://www.ri.cmu.edu/publications/chomp-gradient-optimization-techniques-for-efficient-motion-planning/
John Schulman, Jonathan Ho, Alex Lee, Ibrahim Awwal, Henry Bradlow, Pieter Abbeel, RSS 2013.
https://www.roboticsproceedings.org/rss09/p31.pdf
Ioan A. Șucan, Mark Moll, Lydia E. Kavraki, IEEE Robotics & Automation Magazine, 2012.
https://ompl.kavrakilab.org/
Spot a factual error or missing qualification? Report a content correction.