Dartmouth CS 54: Configuration space

Configuration space

We will need ways to describe mechanical systems so that we can reason about them, or write algorithms to control them. The word system is used in many ways in the robotics literature, but the definition we will use is

System: A set of particles.

In a physical system, each particle has a location in a plane, described by two real numbers, or in three-dimensional space, described by three real numbers. We say that the particles are embedded in $\mathbf{R}^2$ or $\mathbf{R}^3$ . We define the configuration of the system:

Configuration: The location of every particle in the system.

The particles may be constrained to lie on a curve, or on a surface. There may also be other constraints; for example, the particles might all be part of a rigid body, so that their locations are not independent.

Configuration space: The set of all possible configurations of the system.

Degrees of freedom: The independent ways in which the configurations of a system can change.

This definition of degrees of freedom is accurate, but vague. What does "independent" mean in this context? What does "ways" mean? In some cases a more precise definition is possible; we will see this by the end of the lecture.

Let's look at a concrete example. Consider a single particle in the plane. It takes two numbers to represent the particle's location, so the particle has two degrees of freedom. How about a system of two particles that can move independently? Four numbers are needed, so the system has four degrees of freedom.

What happens if there are constraints on the motion of the particles? Consider a system made up of two particles, constrained so that the distance between the particles is one. (One what? It could be one meter, or one inch, or one micron. Let's agree to always use the same units for everything, so that we can omit writing the units.) We could represent the configuration of the system using four numbers, $(x_1, y_1, x_2, y_2)$ , the Cartesian coordinates of each point.

However, not all choices of four coordinates are consistent with the constraint:

(1)

$(x_2 - x_1)^2 + (y_2 - y_1)^2 = 1$

This constraint removes one degree of freedom, so this system has three degrees of freedom. How can we tell? If you knew three of the values of the coordinates (for example, $x_1, y_1, y2$ ), then the last coordinate ( $x_2$ ) would be almost determined. Notice that although there are actually two possible solutions for $x_2$ , no motion is possible between those points; a set of discrete points has dimension zero. So, since three numbers and the constraint remove the possibility of continuous motion, this system has three degrees of freedom.

Let's imagine that we still use four numbers to represent the configuration of this two-point system. The possible configurations are then a three-dimensional surface embedded in $R^4$ . This surface is smooth everywhere, and local motion on the surface is possible everywhere, while preserving the rigid-body constraint.

Trajectories in configuration space

Every point on the configuration space surface corresponds to a configuration of the system. For example, the coordinate $(0, 0, 1, 0)$ on this surface would indicate that one of the particles in the system is at the origin, and the other is on the positive x axis at distance 1. We could describe a smooth continuous motion of the rigid body by a curve that lies within the configuration space, parameterized by time: $( x_1(t), y_1(t), x_2(t), y_2(t) )$ , with $t \in [0, T]$ , where zero is the start time, and $T$ is the end time.

We distinguish between a path and a trajectory.

Path: A continuous curve on the configuration space.

Trajectory: A continuous curve on the configuration space parameterized by time.

There are some formal mathematical terms to describe the releationship between a path and a trajectory: a trajectory is a parameterization of a path, and the image of a trajectory over time is a path. A path simply tells where the particles of a system might go; a trajectory also tells us infomation about the velocity of the system and the time at which it gets to each point.

Topology of configuration spaces

We have said that the configuration space is a surface. Surfaces may be smooth or nonsmooth, differentiable or not, connected or not. A manifold is a special type of surface that is locally similar to $R^d$ . That is, at every point on the surface, it is possible to attach a local coordinate system with d dimensions. If the configuration space is a manifold, there is a precise way to count the degrees of freedom of a system: the number of degrees of freedom is equal to the dimensionality of the manifold. Most of the configuration spaces we will see will be manifolds, but there will be exceptions.

The surface of a sphere is a 2-manifold; at each point you can attach a local two-dimensional coordinate system. For example, at most places on the sphere you could use latitude and longitude as your coordinates. However, you should choose something else in the neighborhood of the north pole, since all longitudes describe the same point if the latitude is 90. That's why we say "local" two-dimensional coordinate system.

The plane is also a 2-manifold (just choose coordinates x and y everywhere, for example). However, there is an interesting difference between these manifolds: the plane is infinite, while the surface of the sphere is finite. Neither manifold has a boundary. If you "keep going" on the surface of the sphere you might end up somewhere you've been before; this won't happen in the plane. The study of which points are adjacent to other points is called topology. There are a few standard surface shapes that we will see over and over.

First, the one-dimensional surfaces. The real number line ${\bf R}$ is infinite and does not loop back on itself. On the other hand, the unit circle has one loop and is finite; we call the unit circle ${\bf S}^1$ . What about more complicated curves? If the curve is infinite and does not cross itself, then we can establish a one-to-one correspondence between points on the curve and points on the real line ${\bf R}$ ; we say that the curve has the topology of ${\bf R}$ . If the curve has a single loop, and can be continuously deformed into a circle without changing the adjacency relationship between any points, the curve has the topology of a circle, ${\bf S}^1$ . How about a figure-eight? There are two loops. In fact, since the tangent space is not similar to either ${\bf R}^1$ or ${\bf R}^2$ at the junction point, the figure eight is not even a manifold. Maybe there is a standard name for the topology of a figure eight, but I do not know it.

Let's think about two-dimensional manifolds. One example is ${\bf R^2}$ . It is infinite in all directions and contains no holes. Another is ${\bf S^2}$ , the surface of a sphere. How about an infinite cylinder? In one direction, you can move around the outside of the cylinder, coming back to where you started. In another direction, you move off towards infinity. We say that the topology is ${\bf R} \times {\bf S^1}$ . The $\times$ symbol is called the Cartesian product, and it means that for each element from one space, there is associated an entire space of the second type. We are already familiar with the Cartesian product: ${\bf R^3}$ is the same as ${\bf R} \times {\bf R} \times {\bf R}$ .

The d-dimensional unit sphere is given the symbol ${\bf S^d}$ . Remarkably, the topology of ${\bf S^d}$ is NOT ${\bf S^1} \times {\bf S^1} \times {\bf S^1}\ldots {\bf S^1}$ for $d \ge 2$ . Consider ${\bf S}^2$ . You might choose to describe locations on the sphere by latitude and longitude. For most latitudes, there is in fact an entire circle of longitudes, so we might be tempted to say that the topology is ${\bf S^1} \times {\bf S^1}$ . However, at two latitudes (at the north and south poles), there is not an entire ring of longitudes.

So what shape does the topology ${\bf S^1} \times {\bf S^1}$ describe? For each point on a torus, there are two types of circles: one that goes around the rim of the donut, and one that goes all the way around the hole in the center of the donut. There is no degenerate pole, as there is for the unit sphere. In general, the topology of the d-dimensional torus is the Cartesian product of d circles. This is more than a mathematical curiosity — we will see that many robot arms have configuration spaces with the topology of a torus.

Let's return to the example of a 2-particle rod of unit length in the plane. We said that the configuration space was embedded in ${\bf R^4}$ , and there was one constraint, so the dimensionality of the configuration space was 3. Although we have not shown this, it also turns out that the configuration space is a manifold. What is the topology of this manifold? There are two directions of translation, and a rotation. This indicates that the topology of the configuration space is ${\bf R^2} \times {\bf S^1}$ . We will go into more details when we discuss rotations and translations.

Constraint counting

For a complicated system, it can be daunting to count the independent degrees of freedom. The most reliable method is based on the observation that a constraint typically removes a single degree of freedom. For example, our 2-particle rigid body of length one had the constraint

(2)

$(x_2 - x_1)^2 + (y_2 - y_1)^2 = 1.$

If the length of the rod were able to vary freely, then the two particles could move independently. The constraint removes this dimension, length, so the rigid body has three degrees of freedom. What if we added another constraint? For example,

(3)

$x_1= 0$

Then the rigid body could slide along the y axis and rotate, but could not translate in the x direction. We have removed one more degree of freedom. How about one more constraint?

(4)

$y_1= 0$

Now the rod is pinned to the origin, and can only rotate. By adding three constraints, we have reduced the degrees of freedom of the two-particle system from four ( ${\bf R^4}$ ) to one ( ${\bf S^1}$ ). It can be tricky to figure out which degrees of freedom remain after applying several constraints, but counting how many degrees of freedom remain is easy: just subtract one degree of freedom for each independent constraint. (We will see later what is meant by independent.)

Configuration spaces for rigid bodies

Armed with constraint-counting, we are now ready to think about the degrees of freedom for systems that are more complicated than just two points. Many of the objects we study in robots are approximately rigid. Consider a system of n particles in the plane. If unconstrained, each of the n particles has two degrees of freedom, so the system has 2n degrees of freedom in total.

A rigid body has constraints that maintain the distance between each pair of particles. There are n choose 2 pairs of particles, so a naive application of constraint counting would suggest that a rigid body has 2n - choose(n, 2) degrees of freedom. This would imply that a system with 10 particles had 2 * 10 - 45 = -25 degrees of freedom. Something is wrong.

The problem is that many of the constraints in the rigid body are redundant. If we had two particles, and one constraint between them (as in our example system), there would be 2 * 2 - 1 = 3 degrees of freedom, which is what we expect. Since there is only one constraint, it is clearly not redundant. Now imagine adding one additional particle. We need to attach it to each of the previous particles, requiring two additional constraints. So we have three particles and three constraints; 2 * n - 3 = 3 degrees of freedom, still. Now let's add a fourth particle. We want the distance two each of the particles in the triangle already formed to remain constant, but we can do this by adding only two constraints, specifying the distance to only two of the previous particles. We now have n=4 and there are 5 constraints, so we still have three degrees of freedom. Each additional particle requires only two constraints to fix it to the current rigid body, so in general, the rigid body in the plane has three degrees of freedom.

Parameterized configuration space

It would be inconvenient if we had to write down the location of every particle in a rigid body to describe the configuration. Instead, we are likely to choose a reference point on the body, and describe the configuration of the body by stating the location of that coordinate, and the orientation of the body with respect to some initial orientation.

Consider a simple example of a particle in $R^2$ constrained to lie on a unit circle. The configuration space has one dimension; there is one degree of freedom. The topology of the configuration space is $S^1$ . We could express the configuration using two numbers and a constraint:

(5)

${\bf x} = (x_1, x_2) \in {\bf R}^2$

(6)

$x_1^2 + x_2^2 = 1$

or we could use a single number $\theta \in [0, 2\pi)$ to describe the angle of of the particle with respect to the horizontal. The second representation is convenient in that it uses only one number instead of two. This is called a 'reduced-coordinate' description of the configuration. If the number of coordinates matches the number of degrees of freedom (i.e. no additional constraints are needed) then it is a minimal coordinate representation of the system.

Minimal coordinates are not always the best choice. It may be difficult to determine what the minimal coordinates are, and when we are thinking about the motion of the system, we may still need to worry about the fact that the particles are really following a curve, moving along a surface. There are problems both of topology and geometry. For example, think about a point body in $R^3$ constrained to move on a sphere. You could use the latitude and longitude as minimal coordinates: $q = (\theta_1, \theta_2)$ . Let's say you'd like to sample the surface of the sphere. If you sample the latitudes and longitudes, you will get many many more points near the north and south pole than anywhere else, which is probably not what you wanted. The fact that all longitudes are the same at the north and south poles is also going to cause trouble with numerical computations involving velocities near the poles. If you are very close to the north pole, even a slow walk east is going to change your longitude very fast. We will see these problems again when we look at Euler-angle representation of rotations in 3D.

Even so, minimal coordinates are the most typical way to represent the configuration of a mechanical system. We assign one coordinate for each degree of freedom, and use a vector of numbers (by convention, this vector is named $q$ ) to describe the configuration. For example, the configuration space for a rigid body in the plane has the topology ${\bf R^2} \times {\bf S^1}$ , so it is common to take $q = (x, y, \theta)$ , which describes the location and orientation of the body with respect to some world frame. (We will look at frames more closely in the next few lectures.)

A revolute joint allows one degree of rotation, so the configuration of a joint might be represented by an angle $\theta$ . A planar robot arm with three revolute joints connected serially might have the configuration described by $q = (\theta_1, \theta_2, \theta_3)$ ; the topology of the configuration space is ${\bf S^1} \times \bf S^1} \times \bf S^1}$ .

The minimal coordinates are parameters that describe a location in configuration space: that is, the coordinates can be used to determine the location of every particle in the system. As the parameters change, the configuration of the system changes. There may be many different possible choices of coordinate systems to describe the same configuration space; we call such a choice a "parameterization" of the space.

Parameterized configuration space for rigid bodies

First consider a rigid body in the plane. As we've seen from constraint counting, we expect to need three numbers to represent the configuration. A typical choice is to choose a reference point rigidly attached to the body, and use two of the numbers to describe the location of that point. This does not specifiy the orientation of the body, however, so we attach a rigid frame to the reference point, and a rigid frame to the world, and use a third number to describe the angle between these two frames. We take $q = (x, y, \theta)$ .

Rigid bodies in 3D space are trickier. Constraint counting indicates that the configuration space has six dimensions, so we might think that six numbers are enough. They are, sort of. We use the first three numbers to represent the location of one point on the body. Representing the orientation of the body is harder. We might use "airplane coordinates": three angles that give the roll, pitch, and yaw of the body frame with respect to the world frame. As pointed out above, however, this representation is inconvenient in many ways, particularly if we would like to do something like uniformly sample the configuration space, or come up with some idea of the "distance" between two points on the configuration space. Often, we will use four numbers or more to represent the rotation of the rigid body frame, and this will be the topic of an upcoming lecture.

Parameterized configuration space for linkages

Let's return to the planar case, but with more than one rigid body in the system. Consider a planar robot arm with two links and two joints, intended to move a hand (shown as the point $(x, y)$ in the plane. We might use three numbers (two for position and one for orientation) to represent the configuration of the first link, and three numbers to represent the second link, for a total of six numbers. However, it is usually more convenient to just use two numbers to describe the configuration: a value for each of the angles at the joints. We have $q = (\theta_1, \theta_2)$ .

Obstacles

A point in the configuration space corresponds to a particular configuration of the system. If there are obstacles, some configurations of the system will not be possible. We call the space of configurations that do not collide with obstacles the free configuration space; we call the space of points in configuration space that cause collisions the "configuration space obstacles". Every continuous trajectory that lies within the free configuration space corresponds to a motion of the robot that will not cause a collision; writing algorithms to find such trajectories is a central problem in the robotics literature.

Visualizing configuration spaces

Paramaterizations sometimes allow us to visualize configuration spaces. For example, consider a 2R planar arm with no joint limits. We might use the angles $\theta_1$ and $theta_2$ to represent configurations. We could then graph of $\theta_1$ vs $theta_2$ . Each point on the graph represents a unique configuration of the arm. A path would represent a connected set of configurations that can be reached by continuous motions of the joints. Notice that the graph "wraps around" — a path that goes off the graph at $2\pi$ wraps to zero, and should be considered connected. (Remember that the topology of the configuration space for a 2R arm is actually a torus — we can visualize this by thinking of the graph on a piece of paper, rolling the paper into a tube to glue the top and bottom edges of the paper together, and then curving the tube into a donut to glue the left and right edges of the paper together.)

Some points in the configuration space will correspond to cases where the arm collides with an obstacle. The set of points in the configuration space that do not collide with any obstacle is called the free configuration space. The set of points that do cause collisions are called the configuration space obstacles.

Planning a collision free motion for the robot (which might be very complicated — imagine a snake robot, for example!) then can be abstractly formulated as the problem of planning a path for a point robot among obstacles in the configuration space.

It is very convenient to always be able to think about motion planning problems as planning paths for a point, but there is a problem: finding the locations of the configuration-space obstacles is usually hard. There are a few special cases that we will examine: 2R planar arms, and rigid bodies in the plane.

Obstacles for 2R planar arms

Here is a 2R planar arm, with one point obstacle in the physical space:

The location of the obstacle is such that only the first link can collide with it, and that link collides at about $\theta_1= \pi/4$ . Since the collision happens for every value of $\theta_2$ , the configuration space obstacle looks like a line in the graph of the configuration space the right.

What would happen if the placement of the obstacle was such that link 2 could collide with it? The situation would be much more complicated. The cspace obstacle is the set of configurations where there is a collision, so you could imagine sliding link 2 along the obstacle, while causing link 1 to comply with that motion.

Planar translation of rigid bodies

Here is a triangular planar robot that can only translate, and some polygonal obstacles:

We will describe the configuration of the robot by the location of a reference point attached to the robot. The configuration space is therefore $\mathbf R^2$ . As we drag the robot around by its reference point, there will be intersections between the robot and the obstacles. We mark those $(x, y)$ configurations as collisions in the configuration space, as shown in pink below.

There's a pattern to the set of points where there are collisions, and we can use this pattern to derive a graphical method for constructing the configuration space obstacles. Imagine an obstacle that is just a point. For what configurations of the robot does that particular point collide with the robot? Slide the robot edges around the point, marking the location of the reference point as you slide. You'll find that you get a shape in configuration space that looks like a flipped version of the robot — a reflection of the robot in x and y across horizontal and vertical lines through the reference point.

Notice that the boundaries of the polygonal obstacles are unions of point obstacles. The configuration space obstacles are therefore unions of flipped robots. So, to construct the configuration space obstacles, flip the robot, drag it around the boundary of all the physical obstacles, and that will give you the shapes of the configuration space obstacles.

It's not surprising that the c-space obstacles are larger than the original physical obstacles — the robot has 'shrunk' to a point.

Translations and rotations of rigid bodies in the plane

What if the rigid body can rotate as well as translate? We might describe the configurations using the location of the reference point, together with an angle describing how far the robot has rotated from some base configuration. We parameterize the configuration space by three numbers: $(x, y, \theta)$ . We can graph $\theta$ on the z axis, so long as we remember that it wraps from 0 to $2\pi$ .

Obstacles will then be volumes in the configuration space. It's harder to visualize the boundaries of cspace obstacles, but we can use the trick from the previous section to visualize slices of obstacles. Choose $\theta = 0$ . This is a robot that can only translate, and we can draw this slice of the cspace by flipping the robot and dragging around the boundaries of obstacles. Now choose some other value of $\theta$ . The robot has rotated, but as long as we maintain that value of $\theta$ , the rotated robot only translates. So flip the rotated robot, and drag along the boundaries.

If we choose all values of $\theta$ (or more practically, choose some discrete sampling), we can construct the cspace obstacles in slices.

You can imagine that it is possible to analytically construct the boundaries of obstacles for planar rigid bodies. This is correct, but harder than you might think. See Randy Brosts's Ph.D. thesis, or more recent work by Elisha Sacks, for details.

Other abstract spaces

The state of a system is the set of quantities that we are interested in. For physical systems, we are often interested in the location of all the particles, so the state of the system is its configuration. A configuration space is therefore a special case of a state space.

In other disciplines, we might be interested in other quantities, but the idea of thinking about associating a point in a space with each state in the system is common. For example, in physics, it is typical to be interested in the motion of particles or rigid bodies together with their momenta, since Hamiltonian formulation of the dynamics equations are expressed in terms of momenta. The phase space of a system is the set of configurations of the particles and their momenta. That is, the phase space is the cartesian product of the configuration space with the momentum space.

In control theory or the study of systems of differential equations, we are interested in both variables and derivatives of those variables. If those variables describe a phsyical system, they might describe a configuration of the system. Derivatives would then correspond to velocities of the physical system. A point in the state space of the dynamic system assigns a value to each variable and its derivative.

In computer science, the states of a system are often discrete. The discrete state space of the system can therefore be represented by a graph showing the connectivity of the different states. Consider a chess board, for example. An AI to play chess would consider the state of a single piece to be its location on the board, and the state of the entire game to be the location of every piece on the board. Each individual chess piece is analogous to a particle, and the set of chess pieces is analogous to a system of particles.

page_revision: 75, last_edited: 1231772263|%e %b %Y, %H:%M %Z (%O ago)

Edit Tags History Files Print Site tools + Options

Dartmouth CS 54

Introduction to Robotics

Course

Links

Wiki