Loading field map
Robot motion planning is the branch of robotics concerned with the question: how can a robot decide a sequence of movements that takes it from a starting configuration to a goal configuration, while avoiding collisions and respecting the robot's physical limits? Though the phrase sounds simple, the problem is surprisingly deep. The robot's body may have many joints, each contributing to a high-dimensional space of possible states; obstacles may be irregular and unknown; and the robot must often decide quickly enough to act in a changing world. Motion planning is the study of algorithms and representations for making these decisions, and of the mathematical guarantees—or practical heuristics—that come with them.
The central abstraction of motion planning is the configuration space (or C-space). A configuration is a complete specification of the position and orientation of every part of the robot. For a mobile robot moving on a flat floor, a configuration might be its (x, y) position and heading angle. For an articulated arm with six rotational joints, a configuration is the six joint angles. The set of all possible configurations forms a space whose dimension equals the number of degrees of freedom of the robot.
The crucial move is to transfer the problem from the physical world into this abstract space. If the robot at a given configuration would collide with an obstacle, that configuration is said to be in the obstacle region of C-space. The remaining configurations form the free space. The motion planning problem then becomes: find a continuous path through free space from the start configuration to the goal configuration. This reformulation, developed in the late 1970s and early 1980s, turned a messy geometric problem into a cleaner topological one. It also revealed why the problem is hard: the dimension of C-space grows with the number of joints, and the free space can have extremely complicated geometry even for simple robots.
Three questions organize the field. First, existence: given a start and goal, does a collision-free path exist at all? Second, construction: if one exists, how can an algorithm find it, and how efficiently? Third, quality: among the many possible paths, how should the robot choose one that is short, smooth, energy-efficient, or otherwise desirable?
A fourth question has grown in importance: execution. A path computed offline may fail in the real world because of uncertainty in sensing, control error, or moving obstacles. Modern motion planning often addresses not just geometric paths but trajectories—paths parameterized by time—that respect velocity and acceleration limits, and that can be replanned as new information arrives.
The earliest systematic work on motion planning came from two directions. One was computational geometry, which asked whether exact, complete algorithms could be designed: algorithms that always find a path if one exists, and correctly report failure otherwise. The most famous result is the visibility graph method for a point robot among polygonal obstacles, which connects obstacle vertices with straight lines and searches the resulting graph. Another is cell decomposition, which partitions free space into simple regions (cells) and builds a connectivity graph between them. These methods are complete—they give guaranteed answers—but their running time grows rapidly with the number of obstacles and the dimension of C-space. For robots with more than a few degrees of freedom, exact methods become computationally intractable.
The other direction was potential fields, introduced in the mid-1980s. Here the robot is treated as a particle in a field: the goal exerts an attractive force, obstacles exert repulsive forces, and the robot follows the gradient of the resulting potential. This approach is fast and intuitive, and it works well in practice for many low-dimensional problems. But it suffers from a well-known failure mode: the robot can get trapped in local minima—positions where the forces balance but which are not the goal. Potential fields are therefore not complete; they provide no guarantee of finding a path. They remain influential, however, as a reactive method for local obstacle avoidance, often layered on top of a global planner.
The dominant modern approach, developed from the mid-1990s onward, is sampling-based motion planning. The key insight is to abandon the attempt to represent free space exactly. Instead, the algorithm randomly samples configurations, checks whether they are collision-free, and attempts to connect nearby samples with simple paths (usually straight lines in C-space). The result is a graph or tree embedded in free space, which can be searched for a path.
Two families of algorithms dominate. Probabilistic roadmaps (PRMs) sample configurations across the whole C-space and connect them into a graph, which can then be queried for multiple start–goal pairs. Rapidly-exploring random trees (RRTs) grow a single tree outward from the start, biasing growth toward unexplored regions and toward the goal. Both are probabilistically complete: as the number of samples goes to infinity, the probability of finding a path (if one exists) goes to one. This is a weaker guarantee than classical completeness, but it comes with enormous practical power. Sampling-based planners routinely handle robots with dozens of degrees of freedom, which classical methods cannot.
The success of sampling-based methods rests on a subtle observation about high-dimensional spaces: although the free space may be complex, it often has a "good" connectivity structure that random sampling can capture quickly. The field has produced many refinements: RRT and PRM, which add optimality guarantees (they converge to the shortest path as sampling increases); informed sampling, which concentrates samples in regions likely to contain good paths; and kinodynamic planning, which extends sampling to respect dynamics and time. These methods are not a single school but a family of techniques sharing a common probabilistic philosophy.
A different tradition treats motion planning as a search problem on a discretized grid or lattice. The robot's C-space is overlaid with a grid, and standard graph-search algorithms—A, Dijkstra's algorithm, and their variants—find the shortest path through the grid cells. These methods are resolution complete*: they guarantee a solution if one exists at the chosen grid resolution, but they may miss paths that pass through gaps smaller than the grid spacing. Their advantage is that they produce paths with clear optimality properties (shortest in the discretized space) and can incorporate costs beyond collision, such as terrain difficulty or energy use. They are widely used in mobile robotics, especially for ground vehicles, where the state space is low-dimensional.
A more recent approach frames planning as trajectory optimization. Here the planner defines a cost function—penalizing collision, length, jerk, or deviation from a reference—and uses numerical optimization to find a trajectory that minimizes it. Methods like CHOMP (Covariant Hamiltonian Optimization for Motion Planning) and TrajOpt have proven effective in practice, especially for manipulation. Optimization-based planners can produce smooth, dynamically feasible trajectories, but they are local methods: they find a nearby optimum, not necessarily a global one, and they require a reasonable initial guess. In practice, they are often combined with sampling-based planners, which provide a coarse global path that optimization then refines.
These approaches are not rival schools that displaced one another; they are complementary tools suited to different problems. Classical complete methods remain valuable for low-dimensional problems where guarantees matter, such as the motion of a single mobile robot in a known environment. Sampling-based methods are the workhorse for high-dimensional problems, especially manipulation and humanoid motion. Search-based methods excel when optimality in a discretized space is desired and the state space is small. Optimization methods provide the final polish—smooth, executable trajectories—that raw sampling or search methods lack.
Modern systems routinely combine them. A typical pipeline for a robot arm might use a sampling-based planner to find a collision-free path, then a trajectory optimizer to smooth it and make it dynamically feasible, then a reactive potential-field method for the final approach to a moving target. The field has also absorbed ideas from control theory, particularly for kinodynamic planning, where the planner must respect the robot's dynamics (e.g., a car cannot turn in place, a quadrotor cannot stop instantly). Here the distinction between planning and control blurs, and planners must work in the state space of positions and velocities rather than configurations alone.
The current landscape of motion planning is characterized by several durable features. First, sampling-based methods remain the default for high-dimensional problems, but they are no longer the only serious option; optimization and search methods have matured and are often faster for specific problem classes. Second, uncertainty is now central. Classical planning assumed perfect knowledge of the robot and environment; modern planning must handle sensor noise, imperfect actuation, and moving or unknown obstacles. This has given rise to belief-space planning, where the planner maintains a probability distribution over possible states and plans actions that reduce uncertainty while achieving the goal.
Third, learning-based methods have entered the field. Neural networks can learn cost functions, generate motion priors, or directly predict good paths, often speeding up planning in repetitive tasks. These methods are not yet a replacement for classical planners—they lack guarantees and can fail unpredictably—but they are increasingly used to accelerate or guide traditional algorithms. The relationship between learned and classical methods is an active area of research, not a settled succession.
Fourth, the field has expanded from single robots to multi-robot systems, where multiple agents must plan motions that avoid each other as well as static obstacles. This introduces combinatorial complexity, and methods range from centralized planning (treating all robots as one composite robot) to decentralized approaches where each robot plans independently and coordinates through communication or rules of priority.
Finally, real-time performance has become a practical requirement. Robots that operate in human environments—warehouse robots, autonomous vehicles, assistive arms—must replan continuously as the world changes. This has driven research into anytime algorithms (which return a feasible path quickly and improve it as time allows), incremental replanning, and the integration of planning with perception in a closed loop.
Motion planning is thus not a single solved problem but a family of problems united by a common abstraction—the configuration space—and a common goal: enabling a physical system to move purposefully through a world it only partially knows. The field's history is one of successive abstractions and relaxations: from exact geometry to probabilistic sampling, from static worlds to dynamic and uncertain ones, from single agents to fleets. Each relaxation bought practical power at the cost of guarantees, and the field's enduring challenge is to find the right trade-off for each new application.