M1-T5 — Configuration Space

Learning objectives

After this lesson, you should be able to:

• Define a robot’s configuration and its configuration space, and say what dimension it has for common robots.
• Grow obstacles by a circular robot’s radius, and by a general footprint with a Minkowski sum.
• Decide whether a robot fits through a gap, a doorway or a corridor, with and without allowing it to rotate.
• Explain why a planner using a circular footprint is conservative, and what a heading-aware check gains.

The intuition

You are carrying a wide sofa through a house. You do not think about the sofa’s corners at every step. You think about whether the doorway is wide enough for the sofa, which is a statement about the doorway: it must be at least as wide as the sofa’s narrowest turn. In effect you have shrunk the sofa to a point and narrowed the doorway by the sofa’s width.

That is configuration space. A configuration is a complete description of where the robot is: for a robot on a floor, its x, y and heading θ. The configuration space (C-space) is the set of all such configurations. Each obstacle in the room becomes a C-obstacle: the set of configurations in which the robot would overlap it. What remains is the free space, and planning means finding a continuous path through it.

The mathematics

Write A(q) for the region of space the robot occupies when it is in configuration q, and O for an obstacle. The C-obstacle is every configuration where they overlap, and the free space is everything else.

A round robot

If the robot is a disc of radius r and its configuration is the position of its centre, the C-obstacle is the obstacle grown by r in every direction. Straight edges move out by r and convex corners become circular arcs of radius r.

A general footprint

For a robot that does not rotate, the C-obstacle is the Minkowski sum of the obstacle with the robot’s shape reflected through its reference point:

O

the obstacle region in the workspace.

A

the robot’s shape placed with its reference point at the origin.

−A

the shape reflected through the origin (every point p becomes −p).

⊕

the Minkowski sum: adding every point of one set to every point of the other.

For a symmetric footprint, −A is the same as A, so the C-obstacle is simply the obstacle grown by the footprint. For a rectangle it grows a rectangle into a bigger one with the same orientation and rounded or squared corners.

Adding the heading

A rectangle that can rotate has a different C-obstacle for every heading, so C-space is three-dimensional and the C-obstacle is a solid stack of those slices. Checking all of it is expensive, so planners usually pick one of three simplifications:

• Circumscribed circle: treat the robot as a disc of radius r_circ. It is safe for every heading and often too conservative.
• Inscribed circle: use r_in. It is optimistic: it may allow gaps the robot’s corners cannot clear, so it needs a heading check afterwards.
• Full footprint check: check the polygon at the planned heading, as Hybrid A* does (module 4). Exact, and more expensive.

Gaps and doorways

For a disc, a gap between two obstacles is passable exactly when its width is at least 2r. For a rectangle that is not allowed to rotate inside the gap, the gap must be at least as wide as the rectangle’s width. If it must also be able to turn inside, it needs the circumscribed diameter 2r_circ.

A worked example

A doorway, three ways. Scout is 0.6 m long and 0.4 m wide. The doorway is 0.90 m wide. Which footprints allow the planner to route Scout through it?

With the circumscribed radius the doorway is open: it leaves 0.90 − 0.72 = 0.18 m of room. If someone also adds a 0.30 m safety padding to that radius, the planner sees a 1.32 m gap requirement and refuses a door the robot could comfortably pass. This is the situation in lab M1-L1, where a robot that “cannot see the door” is actually being blocked by its own inflation.

A long robot in a narrow corridor. A robot 0.8 m long and 0.4 m wide meets a corridor 0.5 m wide. Its circumscribed radius is √(0.4² + 0.2²) = 0.447 m, so the circumscribed test needs 0.894 m and rejects the corridor. But the corridor is wider than the robot (0.5 > 0.4), so it can drive down it lengthwise. A planner that checks only the circumscribed circle never finds the route. A planner that checks the real rectangle at the planned heading does, at the cost of planning in (x, y, θ) rather than (x, y). It cannot turn around inside, because a turn needs a 0.894 m wide space.

Corner rounding. A 1 m × 1 m square obstacle and a robot of radius 0.3 m give a C-obstacle with straight sides 0.3 m out from the original, so the half-width is 0.5 + 0.3 = 0.8 m, and corners rounded with radius 0.3 m. Replacing the rounded corners with square ones, as a simple rectangular inflation does, blocks 4 × (0.3² − π × 0.3² / 4) = 0.077 m² of free space in total (0.019 m² per corner), a small loss that conservative planners accept.

Engineering implications and limitations

Inflation is C-space in disguise

The inflation layer of a costmap (lesson M2-T2) is exactly the C-obstacle computation for a circular robot, plus a gradient that makes planners prefer to stay further away. Setting its radius is therefore a geometric statement about the robot, not only a safety margin.

Do not count the margin twice

If the footprint already includes the full body and the inflation adds the circumscribed radius and then a further padding, the robot may never fit through anything it should. Decide where the margin lives, write it down, and check the smallest gap in the environment against the total.

Mind the dimension

Adding heading to the search space multiplies the number of states by the number of headings, often by 16 to 72. That is why many systems plan in two dimensions with a circle and only check the real footprint along the final path.

Other robots

An arm’s configuration space is its joint space, where C-obstacles have curved and twisting shapes that cannot be drawn but can be sampled. That is the setting for sampling-based planners in module 4.

Common misconceptions

Engineering takeaways

1. Configuration space makes the robot a point and grows the obstacles by the robot’s shape.
2. For a disc of radius r, grow obstacles by r; a gap is passable if it is at least 2r wide.
3. A general footprint uses a Minkowski sum, and adding heading raises the dimension of the space.
4. The circumscribed circle is safe but conservative; a heading-aware footprint check finds routes it rejects.
5. Decide once where the safety margin lives, and check that the narrowest real gap still passes.

References and further reading

The original paper and standard planning textbooks.

• T. Lozano-Pérez, “Spatial Planning: A Configuration Space Approach”, IEEE Transactions on Computers, C-32(2), 1983.
• S. LaValle, Planning Algorithms, Cambridge University Press, 2006, chapters 3 and 4.
• H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki and S. Thrun, Principles of Robot Motion, MIT Press, 2005, chapter 3.
• Nav2 documentation, “Costmap 2D: Inflation Layer”, docs.nav2.org.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: how to tell whether a navigation run was good, with numbers rather than impressions.

Related content

Nothing below is required to finish this lesson.

• Before
  M1-T4: Frames, Poses and Footprints

  Use the map, odom and base frames correctly, and describe a robot by a footprint that planners and costmaps can use.

• Lab
  M1-L3: Score a Navigation Run

  Compute success, SPL, clearance and jerk for a logged run, and catch the metric that hides a near miss.