Motion planning is the computational problem of finding a sequence of valid movements that takes a robot or vehicle from a starting state to a goal while avoiding collisions and respecting constraints such as joint limits, speed and acceleration. It answers the question of how a robot arm should move to reach a part without hitting the table, or how a car should steer around a parked truck. Motion planning is a basic building block of AI robotics and is used by industrial robots, autonomous robots, self-driving cars and drones.
Overview
The classic form of the problem is called the piano mover’s problem: given a rigid object, such as a piano, and a space with obstacles, find a way to move it from one place to another. The general version of this problem is computationally hard [1]. Robots add complications, such as many joints, movement limits, moving obstacles and the need to plan quickly.
Motion planning is related to, but distinct from, several other terms.
- Path planning. Finding a geometric route with no regard for timing, such as the line a robot follows through a map.
- Trajectory planning. Specifying how the robot moves along a path over time, with velocities and accelerations.
- Task planning. Deciding what actions to take at a symbolic level, such as picking up a block and then stacking it. Motion planning executes the geometric parts. See autonomous planning.
- Control. Following the planned motion accurately through feedback.
Key concepts
### Configuration space
A robot’s configuration is a complete description of its position, for example the angles of every joint of an arm, or the position and heading of a mobile robot. The set of all configurations is the configuration space. Obstacles in the workspace become forbidden regions in this space. Planning then becomes finding a continuous curve through the free part of configuration space from a start point to a goal point. A robot arm with six joints has a six-dimensional configuration space, which is why exact methods become impractical.
### Constraints
Plans must satisfy several kinds of limits.
- Kinematic constraints. Joint ranges and the geometry of the machine.
- Nonholonomic constraints. A car cannot move sideways, so its paths must respect steering limits.
- Dynamic constraints. Limits on speed, acceleration, torque and stability.
- Task constraints. For example, keeping a cup upright while moving it.
### Completeness and optimality
A planner is complete if it always finds a solution when one exists, and reports failure otherwise. Many practical planners are probabilistically complete, meaning the chance of finding a solution approaches one as running time grows. A planner is optimal if it returns the best solution by some measure, such as shortest length or lowest energy, and asymptotically optimal if the solution converges to the best as it runs longer.
Major approaches
### Graph search
The environment is divided into a grid or graph, and a search algorithm finds the best route. Dijkstra’s algorithm finds shortest paths, and A* uses a heuristic estimate of remaining distance to find them faster [2]. These methods work well in low-dimensional spaces, such as a map for a mobile robot, and are widely used in games and navigation software.
### Sampling-based planning
For high-dimensional spaces, planners sample configurations at random and check them for collisions, building a structure of connections.
- Probabilistic roadmaps (PRM). Sample many points, connect nearby free ones into a graph and then search the graph. Good for repeated queries in a fixed environment.
- Rapidly exploring random trees (RRT). Grow a tree from the start by sampling random points and extending the tree toward them [3]. Efficient for single queries and for systems with dynamics.
- Optimizing variants. RRT* and PRM* refine solutions toward optimal paths as they run.
Sampling methods handle robot arms with many joints well, but their paths can be jerky and need smoothing.
### Optimization-based planning
These methods treat a trajectory as a variable and minimize a cost, such as smoothness, length and distance from obstacles, subject to constraints. Methods include CHOMP, TrajOpt and model predictive control, which solves a short-horizon optimization repeatedly as the robot moves. They give smooth paths and can enforce dynamics, but may get stuck in poor local solutions.
### Potential fields and reactive methods
Potential fields treat the goal as attractive and obstacles as repulsive and move the robot along the resulting force. They are simple and fast but can trap the robot in local minima. Related reactive methods, such as the dynamic window approach, choose velocities quickly to avoid nearby obstacles.
### Learning-based planning
Neural networks can speed up planning by suggesting where to sample, predicting collision risk or producing trajectories directly. Imitation learning from expert plans and reinforcement learning give policies that act quickly, though guarantees are weaker than for classical planners, so hybrid designs that check learned proposals with a classical collision checker are common.
Planning with changing and uncertain worlds
Real environments contain moving people and objects, and sensors are noisy. Systems therefore replan frequently, use predictions of other agents’ motion and keep safety margins. Planning under uncertainty is formalized with models such as partially observable Markov decision processes, which are computationally demanding, so practical systems use approximations. Perception feeds planning through maps and obstacle tracking, as described under robotic perception, object tracking and simultaneous localization and mapping.
Applications
- Robot arms. Moving tools around fixtures and parts, including bin picking and assembly.
- Mobile robots and warehouses. Routing fleets and avoiding people and other robots.
- Autonomous vehicles. Planning lane changes, turns and stops in traffic.
- Drones. Flying through three-dimensional spaces.
- Surgery and medicine. Planning needle paths and instrument motion that avoid sensitive tissue.
- Animation and games. Moving characters through virtual worlds.
- Molecular and computational biology. Studying how molecules can move through structures, using planning algorithms.
- Space robotics. Moving arms and rovers under tight constraints.
Challenges
- High dimensionality. Planning grows harder with more joints.
- Real-time requirements. Moving obstacles demand rapid replanning.
- Narrow passages. Tight gaps are hard for random sampling to find.
- Collision checking cost. Testing configurations for collisions dominates running time, so efficient geometry is key.
- Uncertainty. Imperfect maps, sensing and control must be handled safely.
- Safety and verification. Safety-critical systems need predictable, testable behavior.
- Human-aware planning. Motion near people must be safe, legible and comfortable, an issue for collaborative robots.
FAQs
What is motion planning? It is the computation of collision-free movements that take a robot from a start to a goal while obeying its limits.
What is configuration space? It is the space of all possible configurations of a robot, such as all joint angles, in which obstacles become forbidden regions.
What is the difference between path planning and trajectory planning? A path is a geometric route. A trajectory adds timing, with velocities and accelerations along the path.
What are RRT and PRM? They are sampling-based algorithms that explore a robot’s configuration space by random sampling, either growing a tree (RRT) or building a roadmap graph (PRM).
Is motion planning solved? For many tasks yes, but high dimensions, moving obstacles, uncertainty and safety around people remain active research areas.
More in Robotics and Autonomous Technology
Key facts
- The piano mover's problem, which asks how to move a rigid object through a space with obstacles, was a founding problem of motion planning and is PSPACE-hard in its general form1.
- The A* search algorithm was published in 1968 by Hart, Nilsson and Raphael and finds least-cost paths using a heuristic estimate of the remaining distance2.
- The Rapidly-exploring Random Tree (RRT) algorithm, introduced by LaValle in 1998, grows a tree of random samples to explore high-dimensional spaces quickly3.
Related concepts
Quick checkWhat is motion planning?Show answer
Motion planning is the problem of computing a movement for a robot, such as a path or a timed trajectory, that goes from a start to a goal without hitting obstacles and while obeying limits on the robot's shape, speed and dynamics.
Sources
- John Reif, Complexity of the Mover's Problem and Generalizations, 20th Annual Symposium on Foundations of Computer Science, https://doi.org/10.1109/SFCS.1979.10
- Peter Hart, Nils Nilsson and Bertram Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics, https://doi.org/10.1109/TSSC.1968.300136
- Steven LaValle, Rapidly-Exploring Random Trees: A New Tool for Path Planning, Iowa State University Technical Report, https://msl.cs.illinois.edu/~lavalle/papers/Lav98c.pdf
Editorially reviewed by Specialty Digest Editorial TeamLast reviewed November 17, 2026Researched and drafted with AI assistanceReport an issue
