Closed Kinematic Chains
This section continues the discussion from Section 3.4. Suppose that a collection of links is arranged in a way that forms loops. In this case, the C-space becomes much more complicated because the joint angles must be chosen to ensure that the loops remain closed. This leads to constraints such as that shown in (3.80) and Figure 3.26, in which some links must maintain specified positions relative to each other. Consider the set of all configurations that satisfy such constraints. Is this a manifold? It turns out, unfortunately, that the answer is generally no. However, the C-space belongs to a nice family of spaces from algebraic geometry
called varieties. Algebraic geometry deals with characterizing the solution sets of polynomials. As seen so far in this chapter, all of the kinematics can be expressed as polynomials. Therefore, it may not be surprising that the resulting constraints are a system of polynomials whose solution set represents the C-space for closed kinematic linkages. Although the algebraic varieties considered here need not be manifolds, they can be decomposed into a finite collection of manifolds that fit together nicely.11
Unfortunately, a parameterization of the variety that arises from closed chains is available in only a few simple cases. Even the topology of the variety is extremely difficult to characterize. To make matters worse, it was proved in [489] that for every closed, bounded real algebraic variety that can be embedded in Rn, there exists a linkage whose C-space is homeomorphic to it. These troubles imply that most of the time, motion planning algorithms need to work directly with implicit polynomials. For the algebraic methods of Section 6.4.2, this does not pose any
conceptual difficulty because the methods already work directly with polynomials. Sampling-based methods usually rely on the ability to efficiently sample configu- rations, which cannot be easily adapted to a variety without a parameterization. Section 7.4 covers recent methods that extend sampling-based planning algorithms to work for varieties that arise from closed chains.
- Mathematical Concepts
To understand varieties, it will be helpful to have definitions of polynomials and their solutions that are more formal than the presentation in Chapter 3.
Fields Polynomials are usually defined over a field, which is another object from algebra. A field is similar to a group, but it has more operations and axioms. The definition is given below, and while reading it, keep in mind several familiar examples of fields: the rationals, Q; the reals, R; and the complex plane, C. You may verify that these fields satisfy the following six axioms.
A field is a set F that has two binary operations, : F F F (called multiplication) and + : F F F (called addition), for which the following axioms are satisfied:
× →
· × →
- (Associativity) For all a, b, c ∈ F, (a+b)+c = a+(b+c) and (a·b)·c = a·(b·c).
- (Commutativity) For all a, b ∈ F, a + b = b + a and a · b = b · a.
- (Distributivity) For all a, b, c ∈ F, a · (b + c) = a · b + a · c.
- (Identities) There exist 0, 1 ∈ F, such that a + 0 = a · 1 = a for all a ∈ F.
- (Additive Inverses) For every a F, there exists some b F such that
∈ ∈
a + b = 0.
11This is called a Whitney stratification [173, 968].
- (Multiplicative Inverses) For every a ∈ F, except a = 0, there exists some c ∈ F such that a · c = 1.
Compare these axioms to the group definition from Section 4.2.1. Note that a field can be considered as two different kinds of groups, one with respect to mul- tiplication and the other with respect to addition. Fields additionally require commutativity; hence, we cannot, for example, build a field from quaternions. The distributivity axiom appears because there is now an interaction between two different operations, which was not possible with groups.
Polynomials Suppose there are n variables, x1, x2, . . . , xn. A monomial over a field F is a product of the form
xd_1 · x_d_2 · · · · x_dn , (4.47)
1
2
n
in which all of the exponents d1, d2, . . ., dn are positive integers. The total degree
of the monomial is d1 + · · · + dn.
A polynomial f in variables x1, . . . , xn with coefficients in F is a finite lin- ear combination of monomials that have coefficients in F. A polynomial can be expressed as
m
-
ci_m_i, (4.48)
i=1
in which mi is a monomial as shown in (4.47), and ci ∈ F is a coefficient. If ci /= 0, then each ci_m_i is called a term. Note that the exponents di may be different for every term of f. The total degree of f is the maximum total degree among the monomials of the terms of f. The set of all polynomials in x1, . . . , xn with coefficients in F is denoted by F[x1, . . . , xn].
Example 4.17 (Polynomials) The definitions correspond exactly to our intu- itive notion of a polynomial. For example, suppose F = Q. An example of a polynomial in Q[x1, x2, x3] is
x4 − 1 x1x2x3 + x2x2 + 4. (4.49)
1
2
3
1
2
Note that 1 is a valid monomial; hence, any element of F may appear alone as a term, such as the 4 Q in the polynomial above. The total degree of (4.49) is 5 due to the second term. An equivalent polynomial may be written using nicer
∈
variables. Using x, y, and z as variables yields
x4 − 1 xyz3 + x2y2 + 4, (4.50)
2
which belongs to Q[x, y, z]. ．
The set F[x1, . . . , xn] of polynomials is actually a group with respect to addition; however, it is not a field. Even though polynomials can be multiplied, some polynomials do not have a multiplicative inverse. Therefore, the set F[x1, . . . , xn] is often referred to as a commutative ring of polynomials. A commutative ring is
a set with two operations for which every axiom for fields is satisfied except the last one, which would require a multiplicative inverse.
Varieties For a given field F and positive integer n, the n-dimensional affine space over F is the set
Fn = {(c1, . . . , cn) | c1, . . . , cn ∈ F}. (4.51)
For our purposes in this section, an affine space can be considered as a vector space (for an exact definition, see [438]). Thus, Fn is like a vector version of the scalar field F. Familiar examples of this are Qn, Rn, and Cn.
A polynomial in f ∈ F[x1, . . . , xn] can be converted into a function,
f : Fn → F, (4.52)
by substituting elements of F for each variable and evaluating the expression using the field operations. This can be written as f(a1, . . . , an) F, in which each ai denotes an element of F that is substituted for the variable xi.
∈
We now arrive at an interesting question. For a given f, what are the elements of Fn such that f(a1, . . . , an) = 0? We could also ask the question for some nonzero element, but notice that this is not necessary because the polynomial may be
redefined to formulate the question using 0. For example, what are the elements of R2 such that x2 + y2 = 1? This familiar equation for S1 can be reformulated to yield: What are the elements of R2 such that x2 + y2 1 = 0?
−
Let F be a field and let f1, . . . , fk be a set of polynomials in F[x1, . . . , xn].
{ }
The set
V (f1, . . . , fk) = {(a1, . . . , an) ∈ F | fi(a1, . . . , an) = 0 for all 1 ≤ i ≤ k} (4.53)
is called the (affine) variety defined by f1, . . . , fk. One interesting fact is that unions and intersections of varieties are varieties. Therefore, they behave like the semi-algebraic sets from Section 3.1.2, but for varieties only equality constraints are allowed. Consider the varieties V (f1, . . . , fk) and V (g1, . . . , gl). Their intersection is given by
V (f1, . . . , fk) ∩ V (g1, . . . , gl) = V (f1, . . . , fk, g1, . . . , gl), (4.54)
because each element of Fn must produce a 0 value for each of the polynomials in
f1, . . . , fk, g1, . . . , gl .
{ }
To obtain unions, the polynomials simply need to be multiplied. For example, consider the varieties V1, V2 ⊂ F defined as
V1 = {(a1, . . . , an) ∈ F | f1(a1, . . . , an) = 0} (4.55)
and
V2 = {(a1, . . . , an) ∈ F | f2(a1, . . . , an) = 0}. (4.56)
The set V1 ∪ V2 ⊂ F is obtained by forming the polynomial f = f1f2. Note that f(a1, . . . , an) = 0 if either f1(a1, . . . , an) = 0 or f2(a1, . . . , an) = 0. Therefore,
V1 ∪V2 is a variety. The varieties V1 and V2 were defined using a single polynomial,
but the same idea applies to any variety. All pairs of the form fi_g_j must appear in the argument of V (·) if there are multiple polynomials.
- Kinematic Chains in R2
To illustrate the concepts it will be helpful to study a simple case in detail. Let
= R , and suppose there is a chain of links, 1, . . ., n, as considered in Example 3.3 for n = 3. Suppose that the first link is attached at the origin of by a revolute joint, and every other link, i is attached to i−1 by a revolute
2
W A A
W A A
joint. This yields the C-space
C = S × S × · · · × S = T , (4.57)
1 1 1 n
which is the n-dimensional torus.
Two links If there are two links, A1 and A2, then the C-space can be nicely
visualized as a square with opposite faces identified. Each coordinate, θ1 and θ2, ranges from 0 to 2π, for which 0 ∼ 2π. Suppose that each link has length 1. This
yields a1 = 1. A point (x, y) ∈ A2 is transformed as
cos θ1 − sin θ1 0 cos θ2 − sin θ2 1 x
0
0
y
sin θ1
cos θ1
sin θ2
cos θ2
1
. (4.58)
0 0 1
0 0 1
1
To obtain polynomials, the technique from Section 4.2.2 is applied to replace the trigonometric functions using ai = cos θi and bi = sin θi, subject to the con- straint a2 + b2 = 1. This results in
i i
a1 −b1 0 a2 −b2 1 x
b
a
0
b
1 1
2
a2 0 y
1
, (4.59)
0 0 1
0 0 1
1
for which the constraints a2 + b2 = 1 for i = 1, 2 must be satisfied. This preserves
i i
the torus topology of C, but now the C-space is embedded in R4. The coordinates of each point are (a1, b1, a2, b2) ∈ R4; however, there are only two degrees of freedom
because each ai, bi pair must lie on a unit circle.
Multiplying the matrices in (4.59) yields the polynomials, f1, f2 ∈ R[a1, b1, a2, b2],
f1 = xa1a2 − ya1b2 − xb1b2 + ya2b1 + a1 (4.60)
Figure 4.22: Two configurations hold the point p at (1, 1).
and
f2 = −ya1a2 + xa1b2 + xa2b1 − yb1b2 + b1, (4.61)
for the x and y coordinates, respectively. Note that the polynomial variables are configuration parameters; x and y are not polynomial variables. For a given point
(x, y) ∈ A2, all coefficients are determined.
A zero-dimensional variety Now a kinematic closure constraint will be im- posed. Fix the point (1, 0) in the body frame of 2 at (1, 1) in . This yields the constraints
A W
and
f1 = a1a2 − b1b2 + a1 = 1 (4.62)
f2 = a1b2 + a2b1 + b1 = 1, (4.63)
by substituting x = 1 and y = 0 into (4.60) and (4.61). This yields the variety
V (a1a2 − b1b2 + a1 − 1, a1b2 + a2b1 + b1 − 1, a + b − 1, a + b − 1), (4.64)
2 2 2 2
1
1
2
2
which is a subset of R4. The polynomials are slightly modified because each constraint must be written in the form f = 0.
Although (4.64) represents the constrained configuration space for the chain of two links, it is not very explicit. Without an explicit characterization (i.e., a parameterization), it complicates motion planning. From Figure 4.22 it can be seen that there are only two solutions. These occur for θ1 = 0, θ2 = π/2 and θ1 = π/2, θ2 = π/2. In terms of the polynomial variables, (a1, b1, a2, b2), the two solutions are (1, 0, 0, 1) and (0, 1, 0, 1). These may be substituted into each polynomial in (4.64) to verify that 0 is obtained. Thus, the variety represents two
−
−
points in R4. This can also be interpreted as two points on the torus, S1 × S1.
It might not be surprising that the set of solutions has dimension zero because there are four independent constraints, shown in (4.64), and four variables. De- pending on the choices, the variety may be empty. For example, it is physically
impossible to bring the point (1, 0) ∈ A2 to (1000, 0) ∈ W.
A one-dimensional variety The most interesting and complicated situations occur when there is a continuum of solutions. For example, if one of the constraints is removed, then a one-dimensional set of solutions can be obtained. Suppose only one variable is constrained for the example in Figure 4.22. Intuitively, this should yield a one-dimensional variety. Set the x coordinate to 0, which yields
a1a2 − b1b2 + a1 = 0, (4.65)
and allow any possible value for y. As shown in Figure 4.23a, the point p must fol- low the y-axis. (This is equivalent to a three-bar linkage that can be constructed by making a third joint that is prismatic and forced to stay along the y-axis.) Figure 4.23b shows the resulting variety V (a1a2 b1b2 + a1) but plotted in θ1 θ2 coordinates to reduce the dimension from 4 to 2 for visualization purposes. To cor- rectly interpret the figures in Figure 4.23, recall that the topology is S1 S1, which means that the top and bottom are identified, and also the sides are identified. The center of Figure 4.23b, which corresponds to (θ1, θ2) = (π, π), prevents the variety from being a manifold. The resulting space is actually homeomorphic to two circles that touch at a point. Thus, even with such a simple example, the nice manifold structure may disappear. Observe that at (π, π) the links are completely overlapped, and the point p of 2 is placed at (0, 0) in . The horizontal line in Figure 4.23b corresponds to keeping the two links overlapping and swinging them around together by varying θ1. The diagonal lines correspond to moving along configurations such as the one shown in Figure 4.23a. Note that the links and the y-axis always form an isosceles triangle, which can be used to show that the
×
− −
A W
solution set is any pair of angles, θ1, θ2 for which θ2 = π θ1. This is the reason why the diagonal curves in Figure 4.23b are linear. Figures 4.23c and 4.23d show the varieties for the constraints
−
a1a2 − b1b2 + a1 = 8 , (4.66)
1
and
a1a2 − b1b2 + a1 = 1, (4.67)
respectively. In these cases, the point (0, 1) in 2 must follow the x = 1/8 and x = 1 axes, respectively. The varieties are manifolds, which are homeomorphic to S1. The sequence from Figure 4.23b to 4.23d can be imagined as part of an animation in which the variety shrinks into a small circle. Eventually, it shrinks
A
to a point for the case a1a2 − b1b2 + a1 = 2, because the only solution is when
θ1 = θ2 = 0. Beyond this, the variety is the empty set because there are no solutions. Thus, by allowing one constraint to vary, four different topologies are obtained: 1) two circles joined at a point, 2) a circle, 3) a point, and 4) the empty set.
6
5
4
θ1 3
theta2
2
1
0
0 1 2
3 4 5 6
θ2
theta1
- (b)
6 6
5 5
4
θ13
theta2
4
θ1 3
theta2
2 2
1 1
0
0 1 2 3 4 5 6
θ2
theta1
0
0 1 2 3 4 5 6
θ2
theta1
(c) (d)
Figure 4.23: A single constraint was added to the point p on A2, as shown in (a). The curves in (b), (c), and (d) depict the variety for the cases of f1 = 0, f1 = 1/8, and f1 = 1, respectively.
Three links Since visualization is still possible with one more dimension, sup- pose there are three links, A1, A2, and A3. The C-space can be visualized as a
3D cube with opposite faces identified. Each coordinate θi ranges from 0 to 2π, for which 0 ∼ 2π. Suppose that each link has length 1 to obtain a1 = a2 = 1. A
point (x, y) ∈ A3 is transformed as
cos θ1 − sin θ1 0 cos θ2 − sin θ2 10 cos θ3 − sin θ3 10 x
0
0
0
y
.
sin θ1
cos θ1
sin θ2
cos θ2
sin θ3
cos θ3
1
(4.68)
0 0 1
0 0 1
0 0 1
1
(4.68)
To obtain polynomials, let ai = cos θi and bi = sin θi, which results in
a1 −b1 0 a2 −b2 1 a3 −b3 1 x
b
a
0
b
1 1
2
a2 0 b3
a3 0 y
1
, (4.69)
0 0 1
0 0 1
0 0 1
1
for which the constraints a2 + b2 = 1 for i = 1, 2, 3 must also be satisfied. This
i i
preserves the torus topology of C, but now it is embedded in R6. Multiplying the matrices yields the polynomials f1, f2 ∈ R[a1, b1, a2, b2, a3, b3], defined as
f1 = 2a1a2a3 − a1b2b3 + a1a2 − 2b1b2a3 − b1a2b3 + a1, (4.70)
and
f2 = 2b1a2a3 − b1b2b3 + b1a2 + 2a1b2a3 + a1a2b3, (4.71)
for the x and y coordinates, respectively.
Again, consider imposing a single constraint,
2a1a2a3 − a1b2b3 + a1a2 − 2b1b2a3 − b1a2b3 + a1 = 0, (4.72)
which constrains the point (1, 0) 3 to traverse the y-axis. The resulting variety is an interesting manifold, depicted in Figure 4.24 (remember that the sides of the cube are identified).
∈ A
Increasing the required f1 value for the constraint on the final point causes the variety to shrink. Snapshots for f1 = 7/8 and f1 = 2 are shown in Figure 4.25. At f1 = 1, the variety is not a manifold, but it then changes to S2. Eventually, this sphere is reduced to a point at f1 = 3, and then for f1 > 3 the variety is empty.
Instead of the constraint f1 = 0, we could instead constrain the y coordinate of p to obtain f2 = 0. This yields another 2D variety. If both constraints are enforced simultaneously, then the result is the intersection of the two original varieties. For example, suppose f1 = 1 and f2 = 0. This is equivalent to a kind of four-bar mechanism [310], in which the fourth link, 4, is fixed along the x-axis from 0 to
A
1. The resulting variety,
V (2a1a2a3 − a1b2b3 + a1a2 − 2b1b2a3 − b1a2b3 + a1 − 1,
2b1a2a3 − b1b2b3 + b1a2 + 2a1b2a3 + a1a2b3),
(4.73)
θ3
θ1 θ2
Figure 4.24: The variety for the three-link chain with f1 = 0 is a 2D manifold.
is depicted in Figure 4.26. Using the θ1, θ2, θ3 coordinates, the solution may be easily parameterized as a collection of line segments. For all t [0, π], there exist solution points at (0, 2t, π), (t, 2π t, π + t), (2π t, t, π t), (2π t, π, π + t), and (t, π, π t). Note that once again the variety is not a manifold. A family of interesting varieties can be generated for the four-bar mechanism by selecting different lengths for the links. The topologies of these mechanisms have been determined for 2D and a 3D extension that uses spherical joints (see [698]).
−
− − − −
∈
- Defining the Variety for General Linkages
We now describe a general methodology for defining the variety. Keeping the previous examples in mind will help in understanding the formulation. In the general case, each constraint can be thought of as a statement of the form:
The ith coordinate of a point p ∈ Aj needs to be held at the value x in the body frame of Ak.
For the variety in Figure 4.23b, the first coordinate of a point p ∈ A2 was held at the value 0 in W in the body frame of A1. The general form must also allow a
point to be fixed with respect to the body frames of links other than 1; this did not occur for the example in Section 4.4.2
A
Suppose that n links, 1,. . ., n, move in = R2 or = R3. One link, 1
A A W W A
for convenience, is designated as the root as defined in Section 3.4. Some links
θ3
θ2
θ1
f1 = 7/8 f1 = 2
Figure 4.25: If f1 > 0, then the variety shrinks. If 1 < p < 3, the variety is a sphere. At f1 = 0 it is a point, and for f1 > 3 it completely vanishes.
are attached in pairs to form joints. A linkage graph, (V, E), is constructed from the links and joints. Each vertex of represents a link in L. Each edge in represents a joint. This definition may seem somewhat backward, especially in the plane because links often look like edges and joints look like vertices. This alternative assignment is also possible, but it is not easy to generalize to the case of a single link that has more than two joints. If more than two links are attached at the same point, each generates an edge of .
G
G G
G
The steps to determine the polynomial constraints that express the variety are as follows:
- Define the linkage graph with one vertex per link and one edge per joint. If a joint connects more than two bodies, then one body must be designated as a junction. See Figures 4.27 and 4.28a. In Figure 4.28, links 4, 13, and 23 are designated as junctions in this way.
G
- Designate one link as the root, 1. This link may either be fixed in , or transformations may be applied. In the latter case, the set of transformations could be SE(2) or SE(3), depending on the dimension of . This enables the entire linkage to move independently of its internal motions.
W
A W
- Eliminate the loops by constructing a spanning tree T of the linkage graph,
. This implies that every vertex (or link) is reachable by a path from the root). Any spanning tree may be used. Figure 4.28b shows a resulting spanning tree after deleting the edges shown with dashed lines.
G
- Apply the techniques of Section 3.4 to assign body frames and transforma- tions to the resulting tree of links.
Figure 4.26: If two constraints, f1 = 1 and f2 = 0, are imposed, then the varieties are intersected to obtain a 1D set of solutions. The example is equivalent to a well-studied four-bar mechanism.
- For each edge of that does not appear in T , write a set of constraints between the two corresponding links. In Figure 4.28b, it can be seen that constraints are needed between four pairs of links: 14–15, 21–22, 23–24, and 19–23.
G
This is perhaps the trickiest part. For examples like the one shown in Fig- ure 3.27, the constraint may be formulated as in (3.81). This is equivalent to what was done to obtain the example in Figure 4.26, which means that there are actually two constraints, one for each of the x and y coordinates. This will also work for the example shown in Figure 4.27 if all joints are revolute. Suppose instead that two bodies, j and k, must be rigidly attached. This requires adding one more constraint that prevents mutual rotation. This
A A
could be achieved by selecting another point on Aj and ensuring that one
of its coordinates is in the correct position in the body frame of k. If four
A
equations are added, two from each point, then one of them would be redun- dant because there are only three degrees of freedom possible for Aj relative to Ak (which comes from the dimension of SE(2)).
A similar but more complicated situation occurs for = R3. Holding a
W
single point fixed produces three constraints. If a single point is held fixed, then Aj may achieve any rotation in SO(3) with respect to Ak. This implies
that j and k are attached by a spherical joint. If they are attached by a revolute joint, then two more constraints are needed, which can be chosen from the coordinates of a second point. If j and k are rigidly attached, then one constraint from a third point is needed. In total, however, there can
A A
A A
Figure 4.27: A complicated linkage that has 29 links, several loops, links with more
than two bodies, and bodies with more than two links. Each integer i indicates link Ai.
be no more than six independent constraints because this is the dimension of SE(3).
- Convert the trigonometric functions to polynomials. For any 2D transforma- tion, the familiar substitution of complex numbers may be made. If the DH parameterization is used for the 3D case, then each of the cos θi, sin θi expres- sions can be parameterized with one complex number, and each of the cos αi, sin αi expressions can be parameterized with another. If the rotation matrix for SO(3) is directly used in the parameterization, then the quaternion pa- rameterization should be used. In all of these cases, polynomial expressions are obtained.
- List the constraints as polynomial equations of the form f = 0. To write the description of the variety, all of the polynomials must be set equal to zero, as was done for the examples in Section 4.4.2.
28 28
29 12 29 12
11 11
- (b)
Figure 4.28: (a) One way to make the linkage graph that corresponds to the linkage in Figure 4.27. (b) A spanning tree is indicated by showing the removed edges with dashed lines.
Is it possible to determine the dimension of the variety from the number of independent constraints? The answer is generally no, which can be easily seen from the chains of links in Section 4.4.2; they produced varieties of various dimensions, depending on the particular equations. Techniques for computing the dimension exist but require much more machinery than is presented here (see the literature overview at the end of the chapter). However, there is a way to provide a simple upper bound on the number of degrees of freedom. Suppose the total degrees of freedom of the linkage in spanning tree form is m. Each independent constraint can remove at most one degree of freedom. Thus, if there are l independent constraints, then the variety can have no more than m l dimensions. One expression of this for a general class of mechanisms is the Kutzbach criterion; the planar version of this is called Gru¨bler’s formula [310].
−
One final concern is the obstacle region, obs. Once the variety has been identi- fied, the obstacle region and motion planning definitions in (4.34) and Formulation
C
- do not need to be changed. The configuration space must be redefined, how- ever, to be the set of configurations that satisfy the closure constraints.
C
Further Reading
Section 4.1 introduced the basic definitions and concepts of topology. Further study of this fascinating subject can provide a much deeper understanding of configuration spaces. There are many books on topology, some of which may be intimidating, de- pending on your level of math training. For a heavily illustrated, gentle introduction to topology, see [535]. Another gentle introduction appears in [496]. An excellent text at the graduate level is available on-line: [439]. Other sources include [38, 451]. To understand the motivation for many technical definitions in topology, [911] is helpful. The manifold coverage in Section 4.1.2 was simpler than that found in most sources
because most sources introduce smooth manifolds, which are complicated by differentia- bility requirements (these were not needed in this chapter); see Section 8.3.2 for smooth
manifolds. For the configuration spaces of points moving on a topological graph, see [5]. Section 4.2 provided basic C-space definitions. For further reading on matrix groups and their topological properties, see [63], which provides a transition into more advanced material on Lie group theory. For more about quaternions in engineering, see [210, 563]. The remainder of Section 4.2 and most of Section 4.3 were inspired by the coverage in
[588]. C-spaces are also covered in [220]. For further reading on computing represen- tations of Cobs, see [513, 736] for bitmaps, and Chapter 6 and [865] for combinatorial
approaches.
Much of the presentation in Section 4.4 was inspired by the nice introduction to alge- braic varieties in [250], which even includes robotics examples; methods for determining the dimension of a variety are also covered. More algorithmic coverage appears in [704]. See [693] for detailed coverage of robots that are designed with closed kinematic chains.
Exercises
1. Consider the set X = {1, 2, 3, 4, 5}. Let X, ∅, {1, 3}, {1, 2}, {2, 3}, {1}, {2}, and
{3} be the collection of all subsets of X that are designated as open sets.
- Is X a topological space?
- Is it a topological space if {1, 2, 3} is added to the collection of open sets? Explain.
- What are the closed sets (assuming {1, 2, 3} is included as an open set)?
- Are any subsets of X neither open nor closed?
Continuous functions for the strange topology:
- Give an example of a continuous function, f : X → X, for the strange topology in Example 4.4.
- Characterize the set of all possible continuous functions.
- For the letters of the Russian alphabet, A, B, V, G, D, E, E¨, Ж, Z, I, I , K, L, M, N, O, P, R, S, T, U, F, H, C, Q, X, W, Ъ, Y, Ь, З, IO, JI, determine which pairs are homeomorphic. Imagine each as a 1D subset of R2 and draw them accordingly before solving the problem.
- Prove that homeomorphisms yield an equivalence relation on the collection of all topological spaces.
- What is the dimension of the C-space for a cylindrical rod that can translate and rotate in R3? If the rod is rotated about its central axis, it is assumed that the rod’s position and orientation are not changed in any detectable way. Express the C-space of the rod in terms of a Cartesian product of simpler spaces (such as S1, S2, Rn, P 2, etc.). What is your reasoning?
- Let τ1 : [0, 1] → R2 be a loop path that traverses the unit circle in the plane, defined as τ1(s) = (cos(2πs), sin(2πs)). Let τ2 : [0, 1] → R2 be another loop path: τ1(s) = (−2 + 3 cos(2πs), 2 sin(2πs)). This path traverses an ellipse that is centered at (−2, 0). Show that τ1 and τ2 are homotopic (by constructing a
1
continuous function with an additional parameter that “morphs” τ1 into τ2).
- Prove that homotopy yields an equivalence relation on the set of all paths from some x1 ∈ X to some x2 ∈ X, in which x1 and x2 may be chosen arbitrarily.
- Determine the C-space for a spacecraft that can translate and rotate in a 2D Asteroids-style video game. The sides of the screen are identified. The top and bottom are also identified. There are no “twists” in the identifications.
- Repeat the derivation of HA from Section 4.3.3, but instead consider Type VE contacts.
- Determine the C-space for a car that drives around on a huge sphere (such as the earth with no mountains or oceans). Assume the sphere is big enough so that its curvature may be neglected (e.g., the car rests flatly on the earth without
wobbling). [Hint: It is not S2 × S1.]
- Suppose that A and√O are each defined as equilateral triangles, with coordinates
(0, 0), (2, 0), and (1, 3). Determine the C-space obstacle. Specify the coordinates
of all of its vertices and indicate the corresponding contact type for each edge.
- Show that (4.20) is a valid rotation matrix for all unit quaternions.
- Show that F[x1, . . . , xn], the set of polynomials over a field F with variables
x1, . . . , xn, is a group with respect to addition.
- Quaternions:
- Define a unit quaternion h1 that expresses a rotation of − 2 around the axis
π
given by the vector [ 1
√
√
√
3
1 1 ].
3 3
- Define a unit quaternion h2 that expresses a rotation of π around the axis given by the vector [0 1 0].
- Suppose the rotation represented by h1 is performed, followed by the rotation represented by h2. This combination of rotations can be represented as a single rotation around an axis given by a vector. Find this axis and the angle of rotation about this axis.
What topological space is contributed to the C-space by a spherical joint that achieves any orientation except the identity?
- Suppose five polyhedral bodies float freely in a 3D world. They are each capable of rotating and translating. If these are treated as “one” composite robot, what is the topology of the resulting C-space (assume that the bodies are not attached
to each other)? What is its dimension?
1
2/3
1/3
0
0 1
- (b)
Figure 4.29: (a) What topological space is obtained after slicing the M¨obius band?
- Is a manifold obtained after tearing holes out of the plane?
Suppose a goal region G ⊆ W is defined in the C-space by requiring that the entire robot is contained in G. For example, a car may have to be parked entirely within a space in a parking lot.
- Give a definition of Cgoal that is similar to (4.34) but pertains to containment of A inside of G.
- For the case in which A and G are convex and polygonal, develop an algo- rithm for efficiently computing Cgoal.
- Figure 4.29a shows the Mo¨bius band defined by identification of sides of the unit square. Imagine that scissors are used to cut the band along the two dashed lines. Describe the resulting topological space. Is it a manifold? Explain.
- Consider Figure 4.29b, which shows the set of points in R2 that are remaining after a closed disc of radius 1/4 with center (x, y) is removed for every value of (x, y) such that x and y are both integers.
- Is the remaining set of points a manifold? Explain.
- Now remove discs of radius 1/2 instead of 1/4. Is a manifold obtained?
- Finally, remove disks of radius 2/3. Is a manifold obtained?
- Show that the solution curves shown in Figure 4.26 correctly illustrate the variety given in (4.73).
- Find the number of faces of Cobs for a cube and regular tetrahedron, assuming C
is SE(3). How many faces of each contact type are obtained?
- Following the analysis matrix subgroups from Section 4.2, determine the dimen- sion of SO(4), the group of 4 × 4 rotation matrices. Can you characterize this
topological space?
- Suppose that a kinematic chain of spherical joints is given. Show how to use (4.20) as the rotation part in each homogeneous transformation matrix, as opposed to
using the DH parameterization. Explain why using (4.20) would be preferable for motion planning applications.
- Suppose that the constraint that c is held to position (10, 10) is imposed on the mechanism shown in Figure 3.29. Using complex numbers to represent rotation, express this constraint using polynomial equations.
- The Tangle toy is made of 18 pieces of macaroni-shaped joints that are attached together to form a loop. Each attachment between joints forms a revolute joint. Each link is a curved tube that extends around 1/4 of a circle. What is the dimension of the variety that results from maintaining the loop? What is its configuration space (accounting for internal degrees of freedom), assuming the toy can be placed anywhere in R3?
Implementations
- Computing C-space obstacles:
- Implement the algorithm from Section 4.3.2 to construct a convex, polygonal C-space obstacle.
- Now allow the robot to rotate in the plane. For any convex robot and obsta- cle, compute the orientations at which the C-space obstacle fundamentally changes due to different Type EV and Type VE contacts becoming active.
- Animate the changing C-space obstacle by using the robot orientation as the time axis in the animation.
- Consider “straight-line” paths that start at the origin (lower left corner) of the manifolds shown in Figure 4.5 and leave at a particular angle, which is input to the program. The lines must respect identifications; thus, as the line hits the edge of the square, it may continue onward. Study the conditions under which the lines fill the entire space versus forming a finite pattern (i.e., a segment, stripes, or a tiling).