CtrlK
Motion planning is the computational problem of finding a sequence of valid configurations or controls that move a robot, or another articulated or dynamical system, from a start state to a goal state while respecting constraints such as collision avoidance, joint limits, and dynamic feasibility. The field grew out of computational geometry, control theory, and artificial intelligence, and it underpins almost every autonomous behaviour produced by a modern robot, whether an industrial arm welding a chassis, a quadruped trotting across a slope, a self-driving car merging onto a highway, or a surgical instrument threading through tissue. Together with robotics, perception, and control, motion planning is one of the three classical pillars of autonomy.
The canonical reference is Steven M. LaValle's 2006 Planning Algorithms (Cambridge University Press); most of the algorithmic vocabulary used in industry today comes from that book or the foundational papers it surveys. LaValle is the author of the Rapidly-exploring Random Tree (RRT), one of the two algorithms that, alongside the Probabilistic Roadmap (PRM) of Lydia Kavraki and colleagues, defines sampling-based motion planning.
The foundational reduction underlying nearly all motion-planning algorithms is the move from workspace, where a robot has a complicated geometric shape, to configuration space (C-space), where the robot is represented as a single point. Each point in C-space corresponds to a complete specification of the robot's joint angles, base pose, or other kinematic variables. The subset of the workspace that the robot would collide with maps to a region of C-space called C-obstacle, and the complement, C-free, is the open set of valid configurations. The motion-planning problem then becomes: find a continuous path in C-free from the start point to the goal point. Lozano-Pérez introduced this formulation in 1983.
Jacob T. Schwartz and Micha Sharir formalised this point of view through their multi-part "piano mover's problem" series in 1983. Part I (Communications on Pure and Applied Mathematics, vol. 36, pp. 345-398) produced an exact algorithm running in O(n^5) for a 2D rigid polygon. Part II (Advances in Applied Mathematics, vol. 4, pp. 298-351) generalised the technique to compute topological properties of real algebraic manifolds. Part III addressed coordinated motion of several circular bodies among polygonal barriers. The series established that exact motion planning is, in principle, decidable for any finite-DoF problem, but it also exposed the brutal cost of generality.
The complexity story has two anchor points. John Reif proved in 1979 (FOCS, Complexity of the Mover's Problem and Generalizations) that motion planning for an n-link robot among polyhedral obstacles is PSPACE-hard, encoding any polynomial-space Turing machine into the geometry of an articulated body. John Canny matched the lower bound in his 1988 thesis The Complexity of Robot Motion Planning with a singly exponential, polynomial-space roadmap algorithm, proving the problem PSPACE-complete. These results explain why complete combinatorial planners scale badly and why practical planners settle for resolution or probabilistic completeness.
The phrase "motion planning" is an umbrella term; the literature distinguishes several related problems.
| Variant | What it solves | Typical method |
|---|---|---|
| Path planning | Geometric path in C-free, no time, no dynamics | Visibility graph, A*, PRM |
| Motion planning | Path with constraints; sometimes kinodynamic (control inputs respecting differential constraints) | RRT, kinodynamic RRT, lattice search |
| Trajectory planning | Time-parameterised, smooth, dynamically feasible curve | Spline fitting, time-optimal scaling, optimisation |
| Manipulation planning | Plans that include grasping and contact between robot and objects | Task and Motion Planning, contact-implicit optimisation |
| Multi-agent / multi-robot planning | Coordinated motion of several robots sharing a workspace | Conflict-based search, decoupled planning, multi-agent RRT |
The distinction matters: a path is a curve in C-space; a trajectory is parameterised by time. An RRT returns a path, which a time-scaling step or trajectory optimiser then converts into something a real motor can track.
Motion-planning algorithms split into roughly four families: combinatorial (exact), search-based, sampling-based, and optimisation-based. Reactive methods (potential fields, velocity obstacles) and predictive methods (MPC) sit alongside these as either special cases or hybrids.
| Family | Representative algorithms | Strengths | Weaknesses |
|---|---|---|---|
| Combinatorial / exact | Cell decomposition, visibility graph, Voronoi diagram, Canny's roadmap | Complete; geometric guarantees | Exponential in DoF |
| Search-based on lattices | A*, weighted A*, ARA*, D*, AD*, JPS, hybrid A* | Fast in low-D; resolution complete | Curse of dimensionality |
| Sampling-based | PRM, RRT, RRT-Connect, RRT*, PRM*, FMT*, BIT*, AIT*, SBL, EST | Probabilistically complete; scales to high DoF | Stochastic; narrow passages hurt |
| Optimisation-based | CHOMP, STOMP, TrajOpt, GPMP2, direct collocation, iLQR, DDP | Smooth, dynamics-aware trajectories | Local minima; needs initialisation |
| Reactive / online | Artificial potential fields, dynamic window, velocity obstacles | Real-time; sensor-driven | Local minima; no global guarantees |
| Predictive control | Linear MPC, nonlinear MPC, hierarchical QP | Handles dynamics and constraints in one loop | Solver speed; horizon length |
Cell decomposition partitions C-free into simple cells, builds a connectivity graph, and searches it. Visibility graphs connect mutually visible obstacle vertices, optimal in 2D among polygonal obstacles. Voronoi diagrams maximise clearance and were used in early mobile robotics. Canny's 1988 roadmap algorithm extended these ideas to give the first singly exponential complete planner. These approaches are complete but confined to low dimensions: the combinatorial structure of C-free explodes with DoF.
The A* algorithm of Peter Hart, Nils Nilsson, and Bertram Raphael (A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Trans. SSC, 1968) is the workhorse of grid- and lattice-based planning. Given an admissible heuristic, A* returns optimal paths and is optimally efficient among admissible algorithms. Planners commonly run A* on motion-primitive lattices for nonholonomic vehicles, on costmaps for ground robots, or on state lattices for aerial vehicles.
Anytime and incremental variants matter when planning interacts with sensing. Likhachev, Gordon, and Thrun introduced ARA* (NeurIPS 2003), which inflates the heuristic to find a quick suboptimal solution then tightens the bound while reusing prior search effort. Anthony Stentz's D* (1994) and its successors D* Lite and Anytime Dynamic A* (Likhachev et al. 2005) repair previous solutions when the graph changes, critical for robots discovering obstacles online.
Dolgov, Thrun, Montemerlo, and Diebel introduced hybrid A* (IJRR 2010) for the Stanford Junior entry in the 2007 DARPA Urban Challenge. Hybrid A* associates each grid cell with a continuous 3D vehicle state, keeping the path kinematically feasible. The hybrid A* family is now standard in self-driving stacks for parking and unstructured environments.
Sampling-based planners broke the curse of dimensionality by trading completeness for probabilistic completeness. Instead of building an exact representation of C-free, they sample configurations, collision-check, and connect nearby pairs. Two algorithms launched the family.
Lydia Kavraki, Petr Svestka, Jean-Claude Latombe, and Mark Overmars introduced the Probabilistic Roadmap (PRM) in IEEE Trans. Robotics and Automation, vol. 12, no. 4, pp. 566-580 (1996). PRM is multi-query: a learning phase samples random valid configurations and connects nearby pairs with a local planner; a query phase connects start and goal to the roadmap and searches. PRM is probabilistically complete: the probability of finding a solution, if one exists, tends to 1 as samples grow.
Steven LaValle introduced the Rapidly-exploring Random Tree in his 1998 Iowa State technical report, with the journal version Randomized Kinodynamic Planning by LaValle and James Kuffner appearing in IJRR (May 2001). RRT is single-query: a tree rooted at the start grows by sampling a random configuration, finding the nearest tree node, and extending toward the sample. The Voronoi bias of nearest-neighbour selection causes the tree to fill space rapidly. RRT-Connect (Kuffner and LaValle, ICRA 2000) grows two trees from start and goal simultaneously, dramatically faster than the unidirectional version on most problems.
The key bottleneck of sampling planners is collision checking, which is typically called millions of times per planning query. Narrow passages are also a chronic difficulty: the probability of randomly sampling a configuration inside a long thin corridor falls with the corridor's volume, so PRM and RRT both struggle on benchmarks with maze-like geometry.
Sertac Karaman and Emilio Frazzoli proved that the cost of the best path returned by RRT or PRM does not converge to the optimum (Sampling-based Algorithms for Optimal Motion Planning, IJRR 2011, arXiv:1105.1186). They introduced PRM* and RRT*, with a logarithmically scaled connection radius and a rewiring step so the returned cost converges almost surely to the optimum. RRT* preserves a tree (single-query), but each new sample can rewire its neighbours to shorten paths. Their analysis links sampling-based planning to random geometric graphs and has been highly influential.
Follow-up algorithms include FMT* (Janson, Schmerling, Clark, Pavone, IJRR 2015), which expands a batch of samples in cost-to-come order, BIT* (Gammell, Srinivasa, Barfoot, IJRR 2020), which combines informed sampling with A*-style heuristic search over implicit random geometric graphs, and the AIT* and ABIT* variants with adaptive heuristics and asymmetric forward-reverse search.
When good initialisations are available, treating motion planning as a continuous optimisation problem produces smooth, dynamics-aware trajectories that sampling planners cannot easily match.
Nathan Ratliff, Matt Zucker, J. Andrew Bagnell, and Siddhartha Srinivasa introduced CHOMP (ICRA 2009), with the extended journal version by Zucker et al. (IJRR 2013). CHOMP performs covariant gradient descent on a functional trading off smoothness against an obstacle-cost field; the gradient is taken with respect to a Riemannian metric on the trajectory space, so the update is invariant to reparametrisation.
Mrinal Kalakrishnan, Sachin Chitta, Evangelos Theodorou, Peter Pastor, and Stefan Schaal proposed STOMP (ICRA 2011), which samples noisy trajectories around the current iterate and combines them by cost. No gradient is required, so non-differentiable cost terms such as motor torque limits fit naturally.
John Schulman and colleagues at UC Berkeley introduced TrajOpt (IJRR 2014), using sequential quadratic programming with a hinge-loss penalty for collisions and a continuous-time no-collisions formulation. The paper reports faster planning than CHOMP and OMPL planners on 7-DoF arms, the 18-DoF PR2, the 34-DoF Atlas humanoid, and steerable needles.
Mustafa Mukadam, Jing Dong, Xinyan Yan, Frank Dellaert, and Byron Boots cast motion planning as probabilistic inference on a factor graph in GPMP2 (Continuous-time Gaussian Process Motion Planning via Probabilistic Inference, IJRR 2018). The Gaussian-process prior over trajectories yields a sparse precision matrix, so MAP inference reduces to a sparse nonlinear least-squares problem solvable with Levenberg-Marquardt or Gauss-Newton.
For systems that make and break contact, Michael Posa, Cecilia Cantu, and Russ Tedrake introduced contact-implicit trajectory optimisation in A Direct Method for Trajectory Optimization of Rigid Bodies through Contact (IJRR 2014). The method poses the optimisation as a Mathematical Program with Complementarity Constraints, which represents the contact dynamics as a Linear Complementarity Problem. This avoids needing to specify a contact mode sequence in advance, an enormous advantage for legged and manipulation problems.
Direct collocation, direct shooting, Differential Dynamic Programming (DDP, Mayne 1966), and the iterative LQR variant (iLQR, Tassa et al. 2012) are the standard numerical methods for trajectory optimisation. Drake, the open-source toolbox developed at the Toyota Research Institute under Russ Tedrake's group, packages many of these methods alongside contact-implicit transcription.
Oussama Khatib's 1986 paper Real-Time Obstacle Avoidance for Manipulators and Mobile Robots (IJRR vol. 5, no. 1) introduced artificial potential fields, treating the robot as a particle moving under an attractive potential pulling toward the goal and repulsive potentials pushing away from obstacles. Potential fields run at servo rates but suffer from local minima where forces cancel.
Velocity obstacles (Fiorini and Shiller 1998) and reciprocal velocity obstacles (van den Berg, Lin, Manocha 2008) compute, in velocity space, the set of velocities that would cause a near-future collision, and they underpin crowd simulation and many multi-robot planners.
Model-predictive control (MPC) treats motion planning as a receding-horizon optimisation. At every control tick, the planner solves a finite-horizon optimal control problem, applies the first control input, and re-plans. MPC is the dominant control law for legged robots (Spot, ANYmal, MIT Mini Cheetah) and is widely used in self-driving stacks. Kuindersma, Deits, Fallon, and colleagues' Atlas controller (Autonomous Robots 2016) solves a quadratic program at each control step capturing instantaneous dynamics, input, and contact constraints; it was used by MIT in the DARPA Robotics Challenge Finals.
For high-DoF manipulation, sampling-based planning is the dominant family. The recipe is straightforward: draw random samples from C-space (uniformly, or from a learned distribution); collision-check each sample; connect nearby samples with a steering function (a straight line for holonomic systems, or a Reeds-Shepp curve, Dubins path, or numerical optimisation for nonholonomic ones); search the resulting graph or tree.
Probabilistic completeness means the failure probability tends to zero as samples grow. Asymptotic optimality, achieved by RRT*, PRM*, FMT*, and BIT*, additionally guarantees the solution cost converges to the optimum. Convergence depends on clearance, however, and narrow passages can force arbitrarily long planning times. Collision checking dominates runtime, often 90%+, and the Flexible Collision Library (FCL) and Bullet are common choices.
| Method | Variables | Characteristics |
|---|---|---|
| Direct collocation | States and controls at knot points | Constraints couple adjacent knots; well-conditioned for stiff systems |
| Direct shooting | Initial state and control sequence | Few variables; long horizons make the gradient ill-conditioned |
| DDP | Local quadratic models of cost-to-go | Quadratic convergence; needs second derivatives |
| iLQR | Linearised dynamics around a nominal trajectory | First-order DDP; widely used in robot learning |
| Contact-implicit | States, controls, contact forces, slacks | No mode sequence needed (Posa, Cantu, Tedrake 2014) |
The choice of method depends on the system. Direct collocation is the workhorse for legged robots and aerial vehicles in academic codebases such as Drake. iLQR underlies MuJoCo MPC and several reinforcement-learning baselines.
A real motion planner must respect a long list of constraints in addition to collision-free geometry.
| Constraint | Source | Examples |
|---|---|---|
| Workspace and self-collision | Robot and environment geometry | Arm avoiding a wall and itself |
| Joint limits | Mechanical stops | KUKA LBR's 170-degree limits |
| Velocity, acceleration, jerk bounds | Actuator limits, comfort | Industrial trajectory generation |
| Dynamic feasibility | Equations of motion | Torque, friction, momentum constraints |
| Stability constraints | Balance | Zero-Moment Point for biped walking |
| Visibility constraints | Sensors | Inspection robots, cinematography |
| Time constraints | Mission requirements | Conveyor synchronisation, pursuit |
The Zero-Moment Point (ZMP), introduced by Vukobratović and Stepanenko in 1972, is the canonical legged-robot stability constraint and remains a building block of bipedal walking pattern generators.
Motion planning is deployed across most categories of robot. The table below summarises representative platforms and the kinds of planners they use.
| Domain | Representative platforms | Typical planning approach |
|---|---|---|
| Industrial manipulators | KUKA LBR iiwa, ABB IRB, FANUC, Yaskawa Motoman | Cartesian/joint splines, OMPL via MoveIt for novel tasks |
| Mobile robots | TurtleBot, Boston Dynamics Spot, ANYbotics ANYmal, Clearpath Husky | A* on costmaps with local DWA or TEB; ROS Navigation Stack global plus local planner |
| Self-driving cars | Waymo Driver, Cruise, Zoox, Tesla Autopilot | Lattice planners, hybrid A*, MPC, sampling-based hybrids |
| Surgical robots | Intuitive da Vinci, Stryker Mako, Medtronic Hugo | Constrained Cartesian planning, RCM-aware planners |
| Drones | PX4 Autopilot, MAVROS-based stacks | Mostly trajectory optimisation; minimum-snap polynomial planners |
| Humanoids | Boston Dynamics Atlas, Honda ASIMO, Toyota T-HR3 | Mixed: footstep planning plus whole-body QP MPC |
| Space robots | Mars rovers (Curiosity, Perseverance), Robonaut | A* with terrain costmaps and rover-specific kinematics |
The DARPA Grand Challenge in 2005 was won by Stanley, the Stanford entry led by Sebastian Thrun (Journal of Field Robotics 2006); its successor Junior used hybrid A* in the 2007 DARPA Urban Challenge. The DARPA Robotics Challenge in 2015 saw teams run heterogeneous mixes of footstep planners, RRT-Connect for arms, and TrajOpt-style optimisers on Atlas.
Industrial arm vendors historically used proprietary Cartesian and joint-space splines for taught paths and increasingly add sampling-based planners via integration with MoveIt and OMPL. Self-driving stacks layer planners hierarchically: a route planner produces a lane sequence, a behaviour planner decides on manoeuvres, and a trajectory planner returns the smooth, dynamically feasible curve the controller tracks.
| Software | What it provides | Maintained by |
|---|---|---|
| OMPL (Open Motion Planning Library) | Sampling-based planners (PRM, RRT, RRT*, FMT*, BIT*, KPIECE, EST, SBL) | Kavraki Lab at Rice University |
| MoveIt | ROS motion-planning framework integrating OMPL, kinematics, collision, control | MoveIt community (originally Willow Garage / PickNik) |
| Drake | Trajectory optimisation, contact-implicit, model-based control | Toyota Research Institute / MIT |
| Pinocchio | Rigid-body dynamics and kinematics | LAAS-CNRS / INRIA |
| OpenRAVE | Older planning and simulation environment | Carnegie Mellon University, now legacy |
| MuJoCo | Physics simulation, MuJoCo MPC for control and trajectory optimisation | DeepMind |
| Bullet, FCL | Collision detection and physics | Open source |
| PyBullet | Python bindings for Bullet, common for robot learning | Erwin Coumans and contributors |
| Isaac Sim | NVIDIA simulation with built-in motion-planning APIs | NVIDIA |
OMPL is the de facto open-source standard for sampling-based planning. It deliberately omits collision detection or world representation; users plug it into MoveIt or their own stack. The library is documented at ompl.kavrakilab.org and is used by hundreds of academic groups and many companies.
Machine learning has become an active part of motion planning, both as a way to accelerate classical planners and as a way to learn policies end-to-end.
Brian Ichter, James Harrison, and Marco Pavone introduced learned sampling distributions (ICRA 2018, arXiv:1709.05448). A conditional variational autoencoder learns to sample in regions where the optimal solution likely lies, conditioned on start, goal, and obstacles. Reported results show order-of-magnitude improvements in success rate and path quality on hard problems.
Neural collision predictors learn fast surrogates for collision checking. Das and Yip's Learning-Based Proxy Collision Detection for Robot Motion Planning Applications (T-RO 2020) showed that neural networks can be faster than geometric checkers, although completeness still requires a real checker as fallback.
Michael Janner, Yilun Du, Joshua Tenenbaum, and Sergey Levine introduced Diffuser (Planning with Diffusion for Flexible Behavior Synthesis, ICML 2022, arXiv:2205.09991), training a denoising diffusion model over trajectories that can be conditioned on rewards or goals at test time. The approach blurs the line between dynamics modelling, policy learning, and planning.
Large language models are increasingly used as task planners that emit symbolic plans, which classical motion planners then refine. SayCan (Ahn et al. 2022), Code as Policies (Liang et al. 2022), and ProgPrompt (Singh et al. 2023) combine agent planning at the symbolic level with sampling-based or optimisation-based motion planning at the geometric level. Diffusion policies (Chi and Song, RSS 2023) replace explicit motion planning with a learned conditional generative model over short action sequences, popular for imitation learning on manipulation tasks.
Fast replanning under uncertainty remains hard: noisy observations and dynamic constraints make online plan updates difficult, especially for high-DoF systems. Manipulation in clutter, where the robot interacts with movable objects, blurs the line between geometric planning and physics-based reasoning, and contact-implicit methods are still mostly offline. Multi-agent planners scale exponentially in the number of agents, and decoupled planners can deadlock. Real-time planning on embedded compute pushes solvers to the limit at kHz rates. Generalisation across robots and tasks remains unsolved; today's planners are tuned for a specific platform, and transfer requires substantial engineering.