Loading field map
Imagine a six-jointed robot arm reaching into a cluttered cabinet to grasp a cup. The arm must avoid the cabinet walls, the cup itself, and any obstacles inside, while also respecting its own joint limits. The space of all possible arm configurations is six-dimensional—far beyond what human intuition can visualize. The central challenge of robot motion planning is to find a continuous, collision-free path through such high-dimensional spaces, and the history of the field is a story of escalating ambition: each new framework tackled a limitation of its predecessors, accepting new trade-offs in return.
Before 1979, motion planning was often done by manually guiding a robot through a sequence of poses or by solving geometric problems in the robot's three-dimensional workspace. The breakthrough came when Tomás Lozano-Pérez and others realized that the problem could be reformulated in the robot's own coordinate space. In Configuration Space Planning (1979–1995), every possible position and orientation of the robot becomes a single point in a high-dimensional space, and obstacles in the workspace map to forbidden regions in this space. The planning problem then reduces to finding a continuous curve through the allowed region—the free space—from a start point to a goal point. This abstraction became the foundation for nearly all subsequent frameworks, because it separated the kinematics of the robot from the geometry of the environment. The cost was that the configuration space itself could be extremely complex and expensive to compute explicitly for robots with many degrees of freedom.
Once the configuration space abstraction was in place, researchers developed three distinct strategies for representing the free space, all sharing the assumption that an explicit geometric model could be built. These three frameworks—Visibility Graph (1979–1995), Cell Decomposition (1985–2000), and Voronoi Diagram Methods (1985–2000)—coexisted as competing approaches within the classical paradigm.
The Visibility Graph method constructs a roadmap of straight-line connections between obstacle vertices, the start, and the goal. The shortest path through this graph is guaranteed to be the shortest collision-free path in the plane, but the method scales poorly with the number of obstacle vertices and only works for polygonal obstacles. It was deterministic and complete—if a path existed, the algorithm would find it—but it was limited to low-dimensional configuration spaces and produced paths that grazed obstacles, which is dangerous for real robots.
Cell Decomposition took a different approach: it divided the free space into a set of simple, non-overlapping regions (cells) and then searched the adjacency graph of these cells. Exact cell decomposition could be complete, but it suffered from exponential blowup in the number of cells as the dimensionality of the configuration space increased. For a robot with six degrees of freedom, the number of cells could become astronomical. Approximate cell decomposition, which used a fixed-resolution grid, traded completeness for tractability but could miss narrow passages or report false paths.
Voronoi Diagram Methods offered a third alternative: instead of connecting obstacle vertices or decomposing free space, they constructed a roadmap of curves that maximized clearance from obstacles. The Voronoi diagram of the free space consists of points equidistant from the two nearest obstacles, producing paths that stay as far from obstacles as possible. This was attractive for robots that needed safety margins, but computing the Voronoi diagram in high-dimensional configuration spaces was even more expensive than cell decomposition, limiting its use to low-dimensional problems.
All three frameworks were deterministic and complete in principle, but they shared a fatal weakness: they required an explicit, global representation of the configuration space, which became intractable for robots with more than a few degrees of freedom.
Potential Fields (1985–2000) broke sharply from the roadmap and decomposition paradigm. Instead of building an explicit model of free space, it treated the robot as a particle moving under the influence of an artificial potential field: attractive forces pull it toward the goal, while repulsive forces push it away from obstacles. The path is generated by following the gradient of this combined field. This approach was extremely fast and could run in real time, making it attractive for reactive control. However, it sacrificed completeness entirely: the robot could get stuck in local minima of the potential field, where attractive and repulsive forces balanced, leaving it stranded before reaching the goal. Because of this fundamental limitation, potential fields were gradually narrowed in scope from a global planning method to a local reactive layer—used for obstacle avoidance during execution rather than for finding a complete path from start to goal. They remain in use today as a low-level component in hybrid systems, but they no longer serve as a standalone global planner.
By the mid-1990s, the classical methods had hit a wall: they could not scale beyond about four or five degrees of freedom. The breakthrough came from abandoning the goal of deterministic completeness. Sampling-Based Planning (1996–Present) replaced exhaustive geometric construction with random sampling of the configuration space. Instead of building the entire free space, these algorithms probe it with random configurations and connect nearby samples to build a roadmap or a tree.
The two most influential variants are the Probabilistic Roadmap Method (PRM), which builds a graph offline by sampling configurations and connecting them with local planners, and the Rapidly-exploring Random Tree (RRT), which grows a tree from the start toward the goal online. Both methods are probabilistically complete: as the number of samples approaches infinity, the probability of finding a path (if one exists) approaches one. In practice, they succeed in high-dimensional spaces—dozens of degrees of freedom—where classical methods fail entirely. The trade-off is that they sacrifice deterministic guarantees: a sampling-based planner might fail to find a path even when one exists, especially through narrow passages, and the paths it produces are often jerky, suboptimal, and far from the shortest possible.
Sampling-based planning became the dominant workhorse of the field because it was the first framework that could handle realistic robots with many joints. It did not replace the classical methods so much as render them obsolete for high-dimensional problems, while absorbing their insights: PRM borrowed the roadmap idea from visibility graphs and Voronoi diagrams, and RRT borrowed the tree-growing idea from earlier search algorithms.
Sampling-based planners solved the scalability problem, but they introduced a new one: path quality. The random paths they produced were often jagged, wasteful, and difficult for a robot to execute smoothly. Optimization-Based Motion Planning (2005–Present) addressed this limitation by treating path planning as a continuous optimization problem. Starting from an initial trajectory—often provided by a sampling-based planner—it iteratively adjusts the path to minimize a cost function (such as path length, jerk, or time) while respecting constraints (collision avoidance, joint limits, dynamics).
This framework did not replace sampling-based planning; instead, it complemented it. In practice, the two are frequently hybridized: a sampling-based planner finds a coarse, collision-free path, and an optimization-based planner refines it into a smooth, executable trajectory. Optimization-based methods are sensitive to local optima—they can get stuck in poor solutions if the initial seed is bad—but they produce far higher-quality paths than sampling alone. They also introduced formal concepts like asymptotic optimality: some sampling-based planners (e.g., RRT*) were later modified to guarantee convergence to the optimal path as samples increase, blurring the boundary between the two frameworks.
The most recent framework, Learning-Based Motion Planning (2015–Present), shifts the computational burden from query time to training time. Instead of searching or optimizing from scratch for each new planning problem, a neural network is trained on a dataset of planning problems and their solutions. At runtime, the network can predict a good path or a useful heuristic (such as a sampling distribution) almost instantly.
Learning-based methods are still maturing. They excel in repetitive tasks where the environment and robot kinematics are consistent, enabling real-time planning that would be too slow with sampling or optimization alone. However, they trade away the formal guarantees of earlier frameworks: neural networks can fail unpredictably on novel scenarios, and they lack the probabilistic completeness of sampling-based methods or the constraint satisfaction of optimization-based methods. For safety-critical applications, learning-based planners are often used as a fast initial guess that is then verified or refined by a sampling-based or optimization-based planner.
Today, no single framework dominates. Sampling-based planning remains the most widely used general-purpose approach, especially for high-dimensional problems where completeness guarantees matter. Optimization-based planning is the standard choice when path quality is critical, such as in manipulation and autonomous driving. Learning-based planning is gaining ground in applications where speed is paramount and the task is well-characterized, but it has not replaced the older frameworks in safety-critical roles.
The leading frameworks agree on the configuration space abstraction as the foundational representation, and they agree that no single method is optimal for all problems. They disagree on what trade-offs to prioritize: completeness versus speed, global optimality versus local reactivity, geometric modeling versus learned heuristics. The most successful practical systems are hybrid pipelines that combine multiple frameworks—for example, a learning-based module to predict a warm-start trajectory, a sampling-based module to ensure collision-free connectivity, and an optimization-based module to smooth the final path. This pluralism is not a sign of fragmentation but of maturity: the field now has a toolkit of methods, each suited to a different regime of the motion planning problem.
Despite decades of progress, fundamental tensions remain. The trade-off between completeness and scalability is still unresolved: sampling-based methods are probabilistically complete but can miss narrow passages, while learning-based methods offer no formal guarantees at all. The gap between global planning and local reactivity persists: potential fields and their descendants handle local avoidance well, but integrating them with global planners without losing guarantees is an ongoing challenge. And the dream of a single, universal planner that works for any robot, any environment, and any task remains out of reach. The history of robot motion planning is not a story of one framework defeating all others, but of a steadily expanding toolkit, where each new method addresses a limitation of its predecessors while accepting new trade-offs of its own.