Motion Planning
A controller is told 'move to position X.' But it is not told how to get there. Motion planning is the problem of finding a path through space that reaches the goal while avoiding obstacles, respecting joint limits, and satisfying other constraints. For a robot arm in a cluttered factory, for a drone navigating a building, or for a self-driving car threading through traffic, planning the motion is a distinct and challenging problem that must be solved before any controller can execute it.
Configuration Space: The Right Representation
The most important insight in motion planning is that the right space to plan in is not physical 3D space, but configuration space (C-space). C-space has one dimension per degree of freedom. For a 6-DOF robot arm, C-space is 6-dimensional: a single point in C-space completely specifies the robot's entire posture. Every physical obstacle in the workspace corresponds to a forbidden region in C-space — the set of configurations where some part of the robot would be in collision. These forbidden regions are called C-space obstacles or C-obstacles. The motion planning problem becomes: find a path from the start point to the goal point in C-space that does not pass through any C-obstacle. This reformulation is powerful. No matter how geometrically complex the physical obstacles, planning reduces to finding a path in C-space between two points while avoiding certain regions. The 'robot' in C-space is always a single point — there is no shape, no extent, just a point moving through a high-dimensional space. The catch: for a 6-DOF robot, C-space is 6-dimensional and C-obstacles have complex, curved boundaries that are expensive to compute exactly. This is why most practical motion planners use sampling-based methods rather than computing the full C-obstacle geometry.
In physical space, checking if a path is collision-free requires checking every point along every link of the robot against every obstacle — a complex geometric computation. In C-space, the robot is a point. A path is collision-free if and only if every configuration along the path is collision-free, which reduces to a point-in-obstacle test. Sampling methods exploit this by checking many random configurations cheaply.
The Rapidly-exploring Random Tree (RRT) algorithm is among the most widely used sampling-based motion planners. Its logic is elegant and intuitive. RRT builds a tree rooted at the start configuration. At each iteration: 1. Sample a random configuration q_rand uniformly from C-space. 2. Find the nearest node q_near in the current tree. 3. Try to extend the tree from q_near toward q_rand by a small step delta. 4. Check if the new configuration q_new is collision-free. 5. If collision-free, add q_new to the tree. 6. Check if q_new is close enough to the goal. Repeat until the goal is reached or the iteration budget is exhausted. RRT is probabilistically complete: if a solution exists, it will be found with probability 1 as the number of samples approaches infinity. Its exploration is naturally biased toward unexplored regions of C-space, making it efficient in practice. Its main weakness is that it does not produce optimal paths — the resulting trajectory is often jagged and longer than necessary. RRT* (RRT-star) is a variant that rewires the tree as it grows, converging to optimal paths given enough time.
Probabilistic Roadmaps (PRM) take a different approach. Instead of building a tree toward one goal, PRM first builds a roadmap — a graph of collision-free configurations — that can be reused for many queries. Phase 1 (offline, precomputation): Sample many random collision-free configurations. Connect nearby configurations if the straight-line path between them in C-space is also collision-free. The result is a graph (roadmap) that covers the free configuration space. Phase 2 (online, query): Given a start and goal, connect them to the roadmap, then find the shortest path through the graph using Dijkstra's or A* search. PRM is ideal when the environment is static (the roadmap can be built once and reused) and multiple queries are needed. It is poorly suited to dynamic environments where obstacles move, because the roadmap must be rebuilt. For dynamic environments, real-time motion planners like RRT with time limits, or Model Predictive Control (MPC) that replans at each timestep over a short horizon, are used instead. Autonomous vehicles typically run some form of real-time replanning at 10-100 Hz, rebuilding their planned trajectory as sensor data reveals new obstacles.
Match each motion planning concept to its defining characteristic.
Terms
Definitions
Drag terms onto their definitions, or click a term then click a definition to match.
From Path to Trajectory
A planner produces a path: a sequence of configurations from start to goal. A path has no time component — it does not specify how fast the robot should move along it. Generating a trajectory means parameterizing the path with time, specifying the velocity and acceleration profile the robot follows. Trajectory generation must respect kinematic and dynamic constraints: maximum joint velocities, maximum accelerations (limited by motor torques), and jerk limits (limits on rate of change of acceleration, which matter for mechanical longevity and smooth motion). The simplest trajectory profile is trapezoidal velocity: accelerate at maximum acceleration to a cruise velocity, hold that velocity, then decelerate to zero at the goal. This minimizes travel time subject to velocity and acceleration limits. More sophisticated planners use polynomial splines — piecewise cubic or quintic polynomials — that guarantee smooth velocity and acceleration (and sometimes jerk) profiles at waypoints. Minimum-jerk trajectories, popular in manipulation, produce motion that looks natural and imposes less mechanical stress. Once a trajectory is generated, the controller's job is to follow it precisely — which is where PID, feedforward, and the dynamics from the previous lessons take over.
An RRT planner builds a tree in the 6-dimensional C-space of a robot arm. It successfully finds a path from the start to the goal. Why is this path likely not optimal, and what variant of RRT addresses this?
A robot arm operates in a static factory cell where the obstacles never move. Which motion planning approach is most efficient for handling hundreds of pick-and-place queries per day?
Plan a Path in 2D C-Space
- This activity simulates motion planning in a 2-dimensional configuration space for a robot with two joints.
- Setup: Draw a 10x10 grid on graph paper. Label the x-axis 'Joint 1 angle (0 to 180 degrees)' and the y-axis 'Joint 2 angle (0 to 180 degrees)'. Each cell is 18 degrees per tick. This is your 2D C-space.
- Obstacles: Shade the following C-space obstacle regions (configurations where the robot would collide):
- Region A: x from 40 to 80, y from 20 to 60 (a central obstacle)
- Region B: x from 100 to 140, y from 80 to 140 (upper-right obstacle)
- Task 1 — Greedy path: Start at (20, 10). Goal at (150, 150). Draw a straight-line path. Does it pass through an obstacle?
- Task 2 — Manual RRT (5 iterations): Mark the start node. For each iteration: pick a random point in the grid (use dice or random numbers), draw an arrow from the nearest existing node toward that point (step size: 20 units), check if the new node lands in an obstacle (if so, discard). After 5 iterations, show your partial tree.
- Task 3 — Find a valid path: By inspection, draw any collision-free path from (20, 10) to (150, 150). How does your path compare to the straight-line path from Task 1?
- Reflection: In a 6-DOF robot, C-space is 6-dimensional and impossible to draw. Why does this make the RRT approach (random sampling + tree growth) more practical than an exhaustive grid search?