Robot Motion Planning

Robot motion planning is the part of robotics that decides where a robot should go: how to get an arm, a rover, or a drone from where it is to where it needs to be without hitting anything, and how to do so efficiently, safely, and in the face of a world that is only partly known.

7 frameworks, from 1978 to today · Robotics · Engineering

still a working view ended · each leads to its entry below

Overview

Robot motion planning is the part of robotics that decides where a robot should go: how to get an arm, a rover, or a drone from where it is to where it needs to be without hitting anything, and how to do so efficiently, safely, and in the face of a world that is only partly known1. It sits between perception (what the robot knows about the world) and control (how its motors execute a command). Its central object is the path or trajectory—a curve through space, possibly with timing and velocities attached—and its central difficulty is that the space of possible motions is enormous, while the obstacles inside it make the problem combinatorially hard1. Over roughly five decades the field has moved through geometric exactness, artificial forces, random sampling, numerical optimization, and, most recently, learning. Each turn answered a problem the previous one could not.

Configuration Space: Turning a Robot into a Point

The founding move of the field was a change of representation. In the late 1970s and early 1980s, Tomás Lozano-Pérez, working at MIT, formalized the idea of configuration space (often abbreviated C-space): the set of all possible positions of the robot, one coordinate per degree of freedom. A six-joint arm becomes a point in a six-dimensional space; a wheeled robot becomes a point in a three-dimensional one (two position coordinates plus heading)1. The robot's body is then "shrunk" to that point, and every obstacle is "grown" by the robot's shape into a C-obstacle. Planning becomes the problem of finding a curve from a start point to a goal point that avoids the grown obstacles1.

This was powerful because it converted a problem about a complicated physical body into a problem about a single point in a high-dimensional space. It also made the difficulty visible: the C-space of a real arm has six or more dimensions, and the grown obstacles can have intricate shapes. Lozano-Pérez's work, together with that of Rodney Brooks and others in the same period, established the geometric framing that still underlies almost everything that follows. Exact methods—cell decomposition, which chops free space into simple cells and searches a graph of them, and the visibility graph, which connects obstacle corners with straight lines—could solve low-dimensional problems completely1. But their cost grows explosively with dimension, and by the late 1980s it was clear that exact geometric planning would not scale to real arms and mobile robots.

Potential Fields and the Reactive Turn

A different answer came from physics rather than geometry. In the mid-1980s Oussama Khatib proposed artificial potential fields: treat the goal as an attractive force and obstacles as repulsive ones, and let the robot roll "downhill" toward the goal like a ball on a landscape. The appeal was speed and elegance—the robot needs only local information about nearby obstacles, and the method produces smooth motions in real time1. It became a foundation of real-time obstacle avoidance and influenced the force-control tradition in manipulation.

Its weakness is equally instructive. A potential field can trap the robot in a local minimum—a dip in the landscape that is not the goal, such as the pocket between two obstacles directly on the line to the target1. The robot stalls, convinced it has nowhere better to go. This failure, and the desire for robots that react to a changing world rather than execute a precomputed plan, fed the reactive and behavior-based current of the late 1980s and 1990s, associated above all with Rodney Brooks at MIT. Brooks argued that intelligence could emerge from layered reactive behaviors—"avoid obstacles," "wander," "follow"—without a central world model. For motion, this meant planners that continuously re-decide from sensor readings. The approach gave robots impressive real-time agility but no guarantee of reaching a goal in a cluttered environment, and the tension between guaranteed completeness and real-time reactivity became a defining theme.

Sampling: Randomness as a Strategy

The decisive break came in the late 1990s, when researchers stopped trying to describe free space exactly and instead sampled it. The key insight: in a high-dimensional C-space you cannot build the obstacles, but you can cheaply test whether a single configuration is collision-free1. So generate random configurations, keep the free ones, and connect nearby ones into a graph or tree1.

Two families emerged. Probabilistic roadmaps (PRMs), introduced by Lydia Kavraki and colleagues in the mid-1990s, build a reusable network of free-space samples once and then answer many start–goal queries on it—well suited to a fixed workspace such as a factory cell. Rapidly-exploring random trees (RRTs), introduced by Steven LaValle in the late 1990s, grow a tree outward from the start by repeatedly sampling a random target and extending toward it; the randomness makes the tree spread quickly into unexplored space. A widely used variant, RRT, later showed that with enough samples these trees converge toward optimal paths. Around the same time, the probabilistic completeness* guarantee was articulated: a sampling planner will find a path if one exists, with probability approaching one as sampling continues—a weaker but far more practical promise than exact completeness1.

Sampling planners made real, high-dimensional problems tractable for the first time: seven-degree-of-freedom arms in cluttered kitchens, humanoid robots, and mobile manipulators. They remain the workhorses of the field1. Their costs are also well known—paths are often jerky and far from optimal, and performance varies run to run—which set up the next turn.

Trajectory Optimization: Planning as a Numerical Problem

Where sampling treats planning as search, trajectory optimization treats it as continuous optimization: define a cost (say, effort, time, or smoothness), impose constraints (collision-free, within joint limits, obeying dynamics), and solve numerically for a whole trajectory at once2. The lineage runs through optimal control—the calculus-of-variations and dynamic-programming traditions of the mid-twentieth century—and through numerical optimal-control methods developed for aerospace and process engineering23. In robotics it matured in the 2000s and 2010s into methods that produce smooth, dynamically feasible, often near-optimal motions, and it is now the standard approach for legged locomotion, drone flight, and aggressive arm maneuvers.

The catch is that optimization finds local optima and is sensitive to its starting guess; a bad initialization can send the solver into a collision or a poor solution. In practice, the field often combines the two ideas: use a sampling planner to find a rough feasible path, then optimize it into a smooth trajectory. This hybrid—sometimes called "sample, then optimize"—is one of the most common patterns in modern motion planning.

Planning Under Uncertainty

All of the above assumes the robot knows where it is and where the obstacles are. Real robots do not. Planning under uncertainty asks how to act when positions, maps, and the effects of actions are only probabilistically known. The intellectual foundation is the partially observable Markov decision process (POMDP), a formal model in which the robot maintains a belief—a probability distribution over possible states—and chooses actions to reduce uncertainty and reach the goal4. Exact POMDP solutions are intractable for realistic problems, so the field developed approximations, and in mobile robotics the practical form became belief-space planning: plan over distributions rather than single states, so that the robot deliberately moves to gather information (for example, toward a landmark to localize itself) as well as toward its goal.

A parallel strand, developed in the 2000s and 2010s, is planning that explicitly accounts for collision probability and for the uncertainty of moving obstacles, producing paths that keep a safety margin rather than threading gaps that are only probably clear. This work connects motion planning tightly to probabilistic robotics and to the perception and SLAM traditions that estimate the robot's state5.

Learning to Plan

The most recent turn brings machine learning into the planner itself. Learning-based motion planning covers several distinct ideas. One is to learn a policy—a mapping from sensor input directly to motion—by reinforcement learning or imitation, so that the robot reacts without solving a planning problem online; this has produced impressive results in locomotion and in manipulation from raw images. Another is to learn to accelerate classical planners: neural networks trained to propose good samples, good heuristics, or good initial trajectories for sampling and optimization methods, cutting the time they need. A third is to learn models of dynamics or of collision from data, which planners then use.

The appeal is clear—learned planners can exploit patterns in the environment and run fast—but so are the open problems: guarantees of safety and completeness are hard to obtain, and learned policies can fail unpredictably outside their training distribution. Much current work tries to combine learned components with the formal guarantees of classical methods rather than replace them.

Where the Field Stands

Today the main approaches coexist and are routinely combined. Sampling-based planners (RRTs, PRMs and their variants) remain the default for high-dimensional, cluttered problems where completeness matters. Trajectory optimization supplies smooth, dynamically feasible motion and dominates legged and aerial robotics. Reactive and potential-field methods survive as fast local layers inside larger systems. Belief-space and chance-constrained planning handle uncertainty, and learning increasingly accelerates or replaces parts of the pipeline. The open questions are the old ones in new form: how to guarantee safety when the world is only partly known and the planner is partly learned; how to plan in real time for robots with many degrees of freedom in dynamic environments shared with people; and how to make the guarantees of classical planning survive contact with data-driven components. The history of the field is, in large part, a history of trading one kind of guarantee for another kind of capability—and then working to get the guarantee back.

References

  1. Motion planning (introduction, Concepts, Free space, Configuration space, Algorithms, Geometric algorithms, Artificial potential fields, Sampling-based algorithms, Completeness and performance), Wikipedia
  2. Trajectory optimization (introduction, History), Wikipedia
  3. Optimal control, Wikipedia
  4. Partially observable Markov decision process, Wikipedia
  5. Simultaneous localization and mapping, Wikipedia

The frameworks of Robot Motion Planning

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1978-1995

    Configuration Space Planning

    How can a robot's motion be reduced to a point in a space?

    Fly to its tower in Nousfarer

  2. 1985-2000

    Artificial Potential Fields

    How can forces guide a robot around obstacles in real time?

    Fly to its tower in Nousfarer

  3. 1986-2000

    Reactive planning

    How can a robot react to its surroundings without a full plan?

    Fly to its tower in Nousfarer

  4. 1994-Present

    Sampling-Based Planning

    How can randomness make high-dimensional planning tractable?

    Fly to its tower in Nousfarer

  5. 1998-Present

    Planning Under Uncertainty

    How should a robot act when it does not know exactly where it is?

    Fly to its tower in Nousfarer

  6. 2000-Present

    Trajectory Optimization

    How can a whole trajectory be computed as an optimization problem?

    Fly to its tower in Nousfarer

  7. 2010-Present

    Learning-Based Motion Planning

    How can a robot learn to plan from experience?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Configuration Space PlanningArtificial Potential FieldsReactive planningSampling-Based PlanningPlanning Under UncertaintyTrajectory OptimizationLearning-Based Motion Planning

Beyond the field

Where Robot Motion Planning's ideas came from in other fields, and what they led to there: the strongest 12 of 37 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Robot Motion Planning is a planet in Nousfarer

Its city has a tower for each of these 7 frameworks. Land, walk in, and climb one concept at a time.

Land on Robot Motion Planning

Related fields

Fields its ideas are linked to

More in Robotics

See where Robot Motion Planning sits on the Map of Human Knowledge