4. The Configuration Space

Chapter 3 only covered how to model and transform a
collection of bodies; however, for the purposes of planning it is
important to define the state space. The state space for motion
planning is a set of possible transformations that could be applied to
the robot. This will be referred to as the *configuration
space*, based on Lagrangian
mechanics and the seminal work of Lozano-Pérez
[656,660,657], who extensively utilized this notion in
the context of planning (the idea was also used in early collision
avoidance work by Udupa [947]). The motion planning
literature was further unified around this concept by
Latombe's book [588]. Once the configuration
space is clearly understood, many motion planning problems that appear
different in terms of geometry and kinematics can be solved by the
same planning algorithms. This level of abstraction is therefore very
important.

This chapter provides important foundational material that will be very useful in Chapters 5 to 8 and other places where planning over continuous state spaces occurs. Many concepts introduced in this chapter come directly from mathematics, particularly from topology. Therefore, Section 4.1 gives a basic overview of topological concepts. Section 4.2 uses the concepts from Chapter 3 to define the configuration space. After reading this, you should be able to precisely characterize the configuration space of a robot and understand its structure. In Section 4.3, obstacles in the world are transformed into obstacles in the configuration space, but it is important to understand that this transformation may not be explicitly constructed. The implicit representation of the state space is a recurring theme throughout planning. Section 4.4 covers the important case of kinematic chains that have loops, which was mentioned in Section 3.4. This case is so difficult that even the space of transformations usually cannot be explicitly characterized (i.e., parameterized).

- 4.1 Basic Topological Concepts

- 4.2 Defining the Configuration Space

- 4.3 Configuration Space Obstacles
- 4.3.1 Definition of the Basic Motion Planning Problem
- 4.3.2 Explicitly Modeling : The Translational Case
- 4.3.3 Explicitly Modeling : The General Case

- 4.4 Closed Kinematic Chains