← Roadmap/Control & Motion

Motion Planning

Getting from A to B without hitting things.

Progress0/10 questions

mediumControl & MotionSkip to practice questions ↓

Prerequisites

Calculus & Optimization Kinematics (FK / IK)

Why it matters in robotics

Motion planning finds a feasible, safe path for a mobile robot, manipulator, drone, or self-driving stack, and it comes in three families of approaches. Some methods search a map of possible poses directly and guarantee the best route but only in low-dimensional spaces; others explore that space randomly and scale to arms with many joints and complex dynamics, though the raw paths come out jerky and need smoothing; and others start from a rough path and refine it by directly minimizing a cost for smoothness and obstacle clearance, producing efficient trajectories with no guarantee they'll find the best one, or any valid one at all, from a bad starting guess. The choice turns on dimensionality, guarantees needed, smoothness, and replanning cost — and shipped systems are usually a hybrid: one approach finds a rough route, then another smooths it into an executable trajectory.

What to study

✓Configuration space (C-space): map robot and obstacles into the space of all poses, why planning happens here, and why its dimension (low-DOF discretizable vs high-DOF) is the first axis that picks a family
✓**Search / grid-based (Dijkstra, A*, D* Lite, hybrid-A*):** admissible/consistent heuristics for optimality, weighted A* to trade optimality for speed, D*/D* Lite for incremental replanning, hybrid-A* and lattice planners for car-like kinodynamic constraints; resolution-complete and optimal but scales poorly past low dimensions
✓**Sampling-based (PRM, RRT/RRT-Connect, RRT*/informed-RRT*/BIT*):** PRM for multi-query roadmaps, RRT/RRT-Connect for fast single-query feasibility, RRT*/informed-RRT*/BIT* for asymptotic optimality; probabilistically complete and the go-to for high-DOF arms, but raw paths are jerky and need smoothing
✓Optimization-based (CHOMP, STOMP, TrajOpt, KOMO): plan the trajectory DIRECTLY by minimizing a smooth cost (smoothness + obstacle/signed-distance penalty) under collision and dynamic constraints, not just post-hoc smoothing; CHOMP uses covariant gradient descent, STOMP is gradient-free stochastic, TrajOpt/KOMO use sequential convex / nonlinear programming; only locally optimal with NO completeness guarantee, so from a bad seed they can stick in a high-cost local minimum or return an infeasible/in-collision trajectory
✓When to use which: weigh dimensionality, completeness vs optimality guarantees (resolution-complete+optimal vs probabilistically-complete vs locally-optimal-only), smoothness/kinodynamic feasibility, dependence on an initial guess and local-minima risk, and replanning rate
✓Hybrid front-end / back-end pipeline: use a search or sampling front-end for a feasible, topology-correct route, then hand it to an optimization back-end (CHOMP/TrajOpt) as the initial guess to refine into a dynamically feasible trajectory, pairing global feasibility with local smoothness and dodging the optimizer's local-minima failure
✓Kinodynamic feasibility: differential constraints, Dubins/Reeds-Shepp curves, and time-parameterization, so the path respects velocity, curvature, and acceleration limits and is actually trackable by the controller

Where to study

Cheatsheet

Symbols used below

g(n)

cost so far from the start to node

n

h(n)

heuristic estimate of cost from

n

to the goal

f(n)

g(n) + h(n)

, A*'s priority for expanding node

n

C

configuration space (C-space)

Configuration space

Planning happens in $C$ -space: the space of all robot poses (joint angles, or position+heading), not the physical workspace.

Obstacles get mapped into $C$ -space too (a point robot in $C$ -space, obstacles grown by the robot's shape). $C$ -space's dimension — low and discretizable vs. high-DOF — is the first thing that picks a planner family.

A* expansion rule

A* repeatedly expands the frontier node with the lowest $f(n) = g(n) + h(n)$ .

If $h$ never overestimates true cost-to-goal (admissible), A* is guaranteed to return the optimal path. Weighted A* inflates $h$ to trade optimality for speed; D*/D* Lite reuse prior search effort for fast incremental replanning.

Sampling-based planners

RRT grows a tree by sampling random configurations and extending the nearest tree node toward each sample, quickly exploring free space without discretizing it.

RRT* additionally rewires nearby nodes when a shorter connection is found, so the tree asymptotically converges toward the optimal path. PRM instead builds a reusable roadmap for answering many queries in a static environment.

Optimization-based planners

CHOMP, STOMP, TrajOpt, and KOMO start from an initial trajectory guess and directly minimize a cost combining smoothness and obstacle/signed-distance penalties, subject to collision and dynamic constraints.

They produce smooth, efficient trajectories but are only locally optimal — a bad initial guess can converge to a high-cost local minimum or an infeasible trajectory, with no completeness guarantee.

Completeness vs optimality by family

Search (grid) methods: resolution-complete and optimal, but scale poorly beyond a few dimensions.

Sampling methods: probabilistically complete (find a solution eventually if one exists), only asymptotically optimal (RRT*-family). Optimization methods: no completeness guarantee, purely local optimality — they refine, they don't search.

Hybrid pipeline & kinodynamic feasibility

Shipped planners commonly chain a search or sampling front-end (fast, feasible, topology-correct route) into an optimization back-end (CHOMP/TrajOpt) that refines it into a smooth, dynamically feasible trajectory.

Kinodynamic constraints — velocity, curvature (Dubins/Reeds-Shepp for car-like robots), acceleration limits — are enforced via time-parameterization so the final path is actually trackable by the controller.

A* expands the frontier cell with the lowest f = g + h (cost-so-far + admissible estimate-to-goal), returning the optimal path when h never overestimates.

	Search (A, D Lite)	Sampling (RRT, PRM)	Optimization (CHOMP, TrajOpt)
Guarantee	Resolution-complete, optimal	Probabilistically complete	None — locally optimal only
Scales to	Low-DOF, discretizable spaces	High-DOF arms, complex dynamics	Refining an existing trajectory
Output quality	Optimal but grid-resolution limited	Feasible but jerky, needs smoothing	Smooth, but can get stuck or infeasible
Replanning cost	Cheap with D/D Lite reuse	Often needs a fresh tree	Cheap if warm-started nearby

An RRT grows a tree by sampling random points and extending toward them, rapidly exploring free space around obstacles. RRT* additionally rewires nearby nodes to shorten paths, converging toward the optimum.

Application focus

Select an application above.