Configuration space

The single most useful idea in motion planning is to stop thinking about the robot as a shape moving among shapes and to think of it instead as a point moving through a space of configurations. This space, the configuration space or C-space, was introduced to robotics by Tomás Lozano-Pérez in 1979 and 1983. Each point in it is one complete placement of the robot. Some points correspond to placements where the robot overlaps an obstacle; together these form the C-space obstacle. The rest is free space. Planning a motion for a complicated robot among complicated obstacles becomes planning a path for a point through free space, and every search method in later lessons works on this formulation.

This lesson builds C-space step by step: for a point robot, for a disc, for a polygon that can rotate, and for a two-link arm. It shows how obstacles in the workspace map into C-space, introduces the Minkowski sum that makes this mapping exact for translating robots, discusses the shape and topology of C-space, and closes with the exact planning methods, visibility graphs and cell decompositions, that work directly on a polygonal free space.

Workspace and configuration space

The workspace is the physical space the robot moves in, usually the plane \( \mathbb{R}^2 \) or three-dimensional space \( \mathbb{R}^3 \). The configuration space is the set of all configurations q. For a robot whose configuration is n numbers, C-space has dimension n. A point robot in the plane has C-space equal to the plane itself, so its C-space obstacles are just the workspace obstacles. As soon as the robot has size or shape, the two spaces differ, and the difference is what makes C-space useful.

Formally, if \( A(q) \) is the set of workspace points occupied by the robot at configuration q and \( \mathcal{O} \) is the set of obstacle points, the C-space obstacle and free space are

A collision-free path is a continuous curve \( \tau : [0, 1] \to \mathcal{C}_{\text{free}} \) with \( \tau(0) = q_{\text{start}} \) and \( \tau(1) = q_{\text{goal}} \). Planners rarely compute \( \mathcal{C}_{\text{obs}} \) explicitly in high dimensions; instead they ask a collision checker, configuration by configuration, whether \( q \) is free. But understanding its shape explains why some problems are easy and others hard.

Discs and inflation

For a disc-shaped robot of radius r that translates without caring about orientation, the C-space obstacle is the workspace obstacle grown by r in every direction. A wall becomes a thicker wall; a square pillar becomes a square with rounded corners. This is the familiar 'inflation' step in mobile robot cost maps: every occupied cell is surrounded by a band of cells marked as untouchable, and the robot's centre is then planned as a point. Inflation is exact for a disc. For a robot that is not round, using the radius of its circumscribed circle is conservative (it never allows a collision) but may block gaps the robot could actually fit through sideways; using the inscribed radius is optimistic and may allow collisions. Practical mobile planners therefore inflate by the inscribed radius to forbid certain collisions and check the full footprint only for poses near obstacles.

Minkowski sums

For a robot that translates without rotating, there is an exact construction. Place a reference point on the robot and let \( -A \) be the robot's shape reflected through that point. Then the C-space obstacle of an obstacle \( \mathcal{O} \) is the Minkowski sum

Intuitively, slide the reflected robot around the boundary of the obstacle, keeping it touching; the reference point traces the boundary of the C-space obstacle. For convex polygons the sum is itself a convex polygon whose edges are the edges of both shapes sorted by angle, so it can be computed in time proportional to the total number of vertices. A square robot of side s moving among square obstacles of side d produces square C-obstacles of side \( s + d \). Non-convex shapes are handled by splitting them into convex pieces and taking the union of the pairwise sums.

Rotation adds a dimension

When the robot can rotate, its configuration is \( (x, y, \theta) \) and C-space is three-dimensional. For each fixed heading θ, the slice of the C-obstacle is the Minkowski sum for the robot rotated to θ. Stacking these slices gives a twisted solid. A long, thin robot produces C-obstacles that are long in the direction perpendicular to its length for one heading and short for another, which is exactly why it can pass through a narrow gap when it is aligned with the gap. The heading dimension also wraps around: θ = 0 and θ = 2π are the same configuration, so C-space for a planar rigid body is not a box but \( \mathbb{R}^2 \times S^1 \), a plane times a circle.

Arms add their own geometry. A two-link planar arm with joint angles \( (\theta_1, \theta_2) \) has a C-space in which each angle wraps around, so it is a torus \( S^1 \times S^1 \) if the joints rotate fully, or a rectangle if joint limits stop them. A workspace obstacle produces a C-obstacle that can look nothing like it: a small block beside the arm may become a large curved band in the \( (\theta_1, \theta_2) \) plane, because many combinations of angles bring some part of the arm into contact. The figure shows such a mapping.

import numpy as np
# Two-link planar arm, links 1.0 m and 0.8 m; obstacle is a disc at (0.7, 0.3) radius 0.2, close to the base
L1, L2, ox, oy, R = 1.0, 0.8, 0.7, 0.3, 0.2
def seg_dist(ax, ay, bx, by):
    vx, vy = bx - ax, by - ay
    t = np.clip(((ox - ax) * vx + (oy - ay) * vy) / (vx * vx + vy * vy), 0, 1)
    return np.hypot(ax + t * vx - ox, ay + t * vy - oy)
n = 180                                   # 2-degree steps
th = np.radians(np.arange(n) * 2.0)
blocked = 0
for a in th:
    ex, ey = L1 * np.cos(a), L1 * np.sin(a)
    d1 = seg_dist(0, 0, ex, ey)
    for b in th - np.pi:
        fx, fy = ex + L2 * np.cos(a + b), ey + L2 * np.sin(a + b)
        if d1 < R or seg_dist(ex, ey, fx, fy) < R:
            blocked += 1
print("C-space cells:", n * n)
print("cells in collision: %d (%.1f %% of C-space)" % (blocked, 100 * blocked / n / n))
print("obstacle area / reachable workspace area: %.1f %%" % (100 * np.pi * R**2 / (np.pi * (L1 + L2)**2)))

C-space cells: 32400
cells in collision: 3849 (11.9 % of C-space)
obstacle area / reachable workspace area: 1.2 %

Topology and connectivity

Free space may be split into separate connected components. If the start and goal lie in different components, no path exists, however clever the planner. Determining connectivity is exactly what complete planners do; resolution-complete and sampling planners approximate it. The topology of C-space also creates traps for naive planners. Because θ wraps around, the shortest rotation from 350° to 10° is 20°, not 340°, and a planner that treats θ as an ordinary interval will produce wasteful spins. Distances on C-space must respect this wrap-around: for headings, use the angular difference wrapped into \( (-\pi, \pi] \); for arms with full-rotation joints, do the same per joint. Mixed spaces also need a weighting between translation and rotation, since one metre and one radian are not comparable without a choice of scale, often the robot's radius.

Exact methods in the plane

For a point (or inflated disc) robot among polygonal obstacles, the shortest path is made of straight segments between obstacle vertices. A visibility graph joins every pair of vertices, plus the start and goal, that can see each other without crossing an obstacle; the shortest path in this graph, found with Dijkstra's algorithm, is the true shortest path. It touches obstacles at their corners, which is optimal but unsafe for a real robot, so it is usually computed on obstacles inflated beyond the robot's size. Cell decomposition takes a different approach: split free space into simple cells, such as trapezoids by sweeping a vertical line across the obstacles' vertices, build a graph of adjacent cells, and search it. A generalized Voronoi diagram, the set of points equidistant from the two nearest obstacles, gives paths that maximize clearance and is the basis of some safe navigation methods. All three are exact and complete for polygonal problems in the plane, and all three are rarely used beyond it.