Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 38 ยท Path Planning

Configuration Space and the Planning Problem

Learn what motion planning solves, how configuration space turns a robot into a point, and how obstacles grow in C-space, with runnable Python examples.

A robot that knows where it is and where it wants to go still has to answer one question: how do I get there without hitting anything? That question is motion planning. A mobile robot plans a route across a warehouse, an arm plans a way to reach into a bin, a drone plans a path between trees. The shapes differ, but the problem is the same.

Planning algorithms are easier to design when the robot is a single point moving through an empty-looking space. Configuration space (C-space) is the trick that makes this possible. In this lesson you will define it, see how obstacles change shape inside it, and compute a C-space map for a two-link arm.

Planning, path and trajectory

Three words are often mixed up. Use them precisely.

Term What it is Example
Path A geometric curve with no timing A list of waypoints from A to B
Trajectory A path plus time: position, velocity, acceleration at each moment The waypoints with a speed profile
Plan The whole decision: which path (or policy) to follow "Go through door 2, then turn left"

This chapter first finds paths. The last lesson, Trajectory Generation and Smoothing, adds time.

A planner is complete if it always finds a path when one exists (and reports failure otherwise). It is optimal if the path it returns is the best by some cost, such as length. Many practical planners give up one of these for speed. Sampling-based planners, for example, are only probabilistically complete.

Configuration: one number per degree of freedom

A configuration is the smallest set of numbers that fixes where every part of the robot is. The number of independent values is the robot's degrees of freedom (DOF).

  • A point robot on a floor: (x, y), 2 DOF.
  • A car-like robot: (x, y, heading), 3 DOF.
  • A two-link arm fixed at its base: (theta1, theta2), 2 DOF.
  • A six-joint industrial arm: six joint angles, 6 DOF.

The configuration space is the set of all possible configurations. A configuration is one point in it. Moving the robot is moving a point along a curve in C-space.

Workspace versus C-space

Workspace The real world the robot moves in.
Configuration One number per degree of freedom.
C-space Every configuration. The robot is a point.

Planning in C-space turns a body into a point.

1 / 2

Growing obstacles for a round robot

For a circular robot of radius r driving on a plane, there is a neat shortcut. Instead of testing the whole disc against every obstacle, shrink the robot to its center point and grow every obstacle by r. The center is safe exactly when it stays outside the grown obstacles. This operation is a Minkowski sum (or "inflation" in ROS navigation).

Python Inflating obstacles by the robot radius

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The + ring is the margin the center must respect. Planning a path for the center in the second picture automatically keeps the whole disc clear in the first.

Real robots are rarely circles. Planners often use a circle that encloses the robot (the "circumscribed radius") for a fast check, then a precise footprint check near obstacles. Inflation also makes a convenient safety margin: add extra centimeters on purpose.

Obstacles in C-space can look strange

For a mobile disc, obstacles stay simple. For an arm, they do not. A small box in the workspace turns into a curved blob in joint-angle space, because the arm touches it at different angle combinations along its whole length.

Let us compute that blob. The arm has two links of length 1.0 and 0.8, a base at the origin and a round obstacle. For each pair of angles we place a few sample points along both links and test them against the obstacle.

Python C-space map of a two-link arm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A single round obstacle became a diagonal band of blocked cells. A planner working in this picture needs a free path between two dots; it never has to think about links, only about points and an "is this cell free?" test. That separation is the whole value of C-space.

Choosing a representation

How you store free space decides which algorithms you can use.

Representation Idea Good for
Grid Cells marked free or blocked 2D navigation; the next lessons
Roadmap Graph of free configurations joined by safe edges Many queries in one map
Tree Branches grown from the start High-DOF arms
Implicit Only an is_free(q) function Sampling-based planners

High-DOF robots cannot use grids: a 6-DOF arm with 100 values per joint would need 100^6 = 10^12 cells. This growth is the curse of dimensionality, and it is why sampling-based planners exist.

flowchart LR
  A["Robot + obstacles in the workspace"] --> B["Choose configuration variables"]
  B --> C["Map obstacles to C-space"]
  C --> D["Search free space for a path"]
  D --> E["Smooth and time the path"]
  E --> F["Controller follows the trajectory"]

A typical planning pipeline, from the real world to motor commands.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A planar arm has three revolute joints. How many dimensions does its configuration space have?

    C-space has one dimension per degree of freedom. Three independent joint angles give a 3D C-space, whatever the link lengths are.
  2. 2. A disc-shaped robot with radius 0.4 m must keep 0.1 m extra clearance. By how much do you inflate each obstacle when planning for its center?

    Inflate by the robot radius plus the margin: 0.4 + 0.1 = 0.5 m. The center point then only has to avoid the grown obstacle.
  3. 3. What is the difference between a path and a trajectory?

    A path is purely geometric. A trajectory says when the robot is where, including its speed profile.
  4. 4. Why can't a 6-joint arm use a fine grid over its C-space?

    With k cells per axis a 6D grid has k^6 cells, which is far too many to store or search.

Summary

  • Motion planning finds a collision-free path (then a timed trajectory) from start to goal.
  • A configuration has one value per degree of freedom; C-space is the set of all configurations.
  • In C-space the robot is a point and obstacles become C-obstacles; a round mobile robot just inflates obstacles by its radius.
  • Arm obstacles become curved bands in joint space.
  • Grids work for 2D or 3D; high-DOF robots need roadmaps or sampling.

Next: Grid Search: BFS and Dijkstra