Transforming Kinematic Trees
Motivation For many interesting problems, the linkage is arranged in a “tree” as shown in Figure 3.21a. Assume here that the links are not attached in ways
- (b)
Figure 3.21: General linkages: (a) Instead of a chain of rigid bodies, a “tree” of rigid bodies can be considered. (b) If there are loops, then parameters must be carefully assigned to ensure that the loops are closed.
that form loops (i.e., Figure 3.21b); that case is deferred until Section 4.4, although some comments are also made at the end of this section. The human body, with its joints and limbs attached to the torso, is an example that can be modeled as a tree of rigid links. Joints such as knees and elbows are considered as revolute joints. A shoulder joint is an example of a spherical joint, although it cannot achieve any orientation (without a visit to the emergency room!). As mentioned in Section 1.4, there is widespread interest in animating humans in virtual environments and also in developing humanoid robots. Both of these cases rely on formulations of kinematics that mimic the human body.
Another problem that involves kinematic trees is the conformational analysis of molecules. Example 3.5 involved a single chain; however, most organic molecules are more complicated, as in the familiar drugs shown in Figure 1.14a (Section 1.2). The bonds may twist to give degrees of freedom to the molecule. Moving through the space of conformations requires the formulation of a kinematic tree. Studying these conformations is important because scientists need to determine for some candidate drug whether the molecule can twist the right way so that it docks nicely (i.e., requires low energy) with a protein cavity; this induces a phar- macological effect, which hopefully is the desired one. Another important problem is determining how complicated protein molecules fold into certain configurations. These molecules are orders of magnitude larger (in terms of numbers of atoms and degrees of freedom) than typical drug molecules. For more information, see Section 7.5.
Figure 3.22: Now it is possible for a link to have more than two joints, as in A7.
Common joints for = R2 First consider the simplest case in which there is a 2D tree of links for which every link has only two points at which revolute joints may be attached. This corresponds to Figure 3.21a. A single link is designated as the root, 1, of the tree. To determine the transformation of a body, i, in the tree, the tools from Section 3.3.1 are directly applied to the chain of bodies that connects i to 1 while ignoring all other bodies. Each link contributes a θi to the total degrees of freedom of the tree. This case seems quite straightforward; unfortunately, it is not this easy in general.
W
A A
A A
Junctions with more than two rotation axes Now consider modeling a more complicated collection of attached links. The main novelty is that one link may have joints attached to it in more than two locations, as in 7 in Figure 3.22. A link with more than two joints will be referred to as a junction.
A
If there is only one junction, then most of the complications arising from junc- tions can be avoided by choosing the junction as the root. For example, for a simple humanoid model, the torso would be a junction. It would be sensible to make this the root of the tree, as opposed to the right foot. The legs, arms, and head could all be modeled as independent chains. In each chain, the only concern is that the first link of each chain does not attach to the same point on the torso. This can be solved by inserting a fixed, fictitious link that connects from the origin of the torso to the attachment point of the limb.
The situation is more interesting if there are multiple junctions. Suppose that Figure 3.22 represents part of a 2D system of links for which the root, A1, is attached via a chain of links to A5. To transform link A9, the tools from Section
Figure 3.23: The junction is assigned two different frames, depending on which chain was followed. The solid axes were obtained from transforming A9, and the dashed axes were obtained from transforming A13.
3.3.1 may be directly applied to yield a sequence of transformations,
x
y
T1 · · · T5T6T7T8T9
1
, (3.68)
for a point (x, y) ∈ A9. Likewise, to transform T13, the sequence
x
y
T1 · · · T5T6T7T12T13
1
(3.69)
can be used by ignoring the chain formed by A8 and A9. So far everything seems to work well, but take a close look at 7. As shown in Figure 3.23, its body frame was defined in two different ways, one for each chain. If both are forced to use the same frame, then at least one must abandon the nice conventions of Section
A
3.3.1 for choosing frames. This situation becomes worse for 3D trees because this would suggest abandoning the DH parameterization. The Khalil-Kleinfinger parameterization is an elegant extension of the DH parameterization and solves these frame assignment issues [524].
Constraining parameters Fortunately, it is fine to use different frames when following different chains; however, one extra piece of information is needed. Imag- ine transforming the whole tree. The variable θ7 will appear twice, once from each
of the upper and lower chains. Let θ7u and θ7l denote these θ’s. Can θ really be
chosen two different ways? This would imply that the tree is instead as pictured in Figure 3.24, in which there are two independently moving links, A7u and A7l.
To fix this problem, a constraint must be imposed. Suppose that θ7l is treated as
Figure 3.24: Choosing each θ7 independently would result in a tree that ignores that fact that A7 is rigid.
an independent variable. The parameter θ7u must then be chosen as θ7l + φ, in which φ is as shown in Figure 3.23.
Example 3.6 (A 2D Tree of Bodies) Figure 3.25 shows a 2D example that involves six links. To transform (x, y) ∈ A6, the only relevant links are A5, A2, and A1. The chain of transformations is
T T T T
x
y
, (3.70)
1 2l
5 6
1
in which
cos θ1 − sin θ1 xt cos θ1 − sin θ1 0
y
=
0
T1 =
sin θ1 cos θ1 t sin θ1 cos θ1 , (3.71)
0 0 1 0 0 1
cos θ2l − sin θ2l a1 cos θ2 − sin θ2 1
=
0
=
T2l
sin θ2l
cos θ2l
sin θ2
cos θ
2 0
, (3.72)
0 0 1 0 0 1
cos θ5 − sin θ5 a2 cos θ5 − sin θ5 √2
0
=
0
T5 =
sin θ5 cos θ5 sin θ5
0 0 1
cos θ5
, (3.73)
0 0 1
0 0 1
Figure 3.25: A tree of bodies in which the joints are attached in different places.
and
cos θ6 − sin θ6 a5 cos θ6 − sin θ6 1
0
=
0
T6 = sin θ6 cos θ6 sin θ6 cos θ6 . (3.74)
0 0 1
0 0 1
0 0 1
0 0 1
The matrix T2l in (3.72) denotes the fact that the lower chain was followed. The transformation for points in A4 is
T T T T
x
y
, (3.75)
1 2u 4 5
1
in which T1 is the same as in (3.71), and
cos θ3 − sin θ3 a2 cos θ3 − sin θ3 √2
0
=
0
T3 = sin θ3 cos θ3 sin θ3 cos θ3 , (3.76)
and
0 0 1 0 0 1
cos θ4 − sin θ4 a4 cos θ4 − sin θ4 0
0
=
0
T4 = sin θ4 cos θ4 sin θ4 cos θ4 . (3.77)
The interesting case is
0 0 1
0 0 1
cos θ2u − sin θ2u a1 cos(θ2l + π/4) − sin(θ2l + π/4) a1
=
0
=
,
T2u
sin θ2u cos θ2u sin(θ2l + π/4) cos(θ2l + π/4) 0
0 0 1
0 0 1
(3.78)
(0,0)
(1,0)
(3,0)
(4,0)
(0,−1)
(3.78)
0 0 1
0 0 1
Figure 3.26: There are ten links and ten revolute joints arranged in a loop. This is an example of a closed kinematic chain.
in which the constraint θ2u = θ2l + π/4 is imposed to enforce the fact that 2 is a junction. ．
A
For a 3D tree of bodies the same general principles may be followed. In some cases, there will not be any complications that involve special considerations of junctions and constraints. One example of this is the transformation of flexible molecules because all consecutive rotation axes intersect, and junctions occur di- rectly at these points of intersection. In general, however, the DH parameter technique may be applied for each chain, and then the appropriate constraints have to be determined and applied to represent the true degrees of freedom of the tree. The Khalil-Kleinfinger parameterization conveniently captures the resulting solution [524].
What if there are loops? The most general case includes links that are con- nected in loops, as shown in Figure 3.26. These are generally referred to as closed kinematic chains. This arises in many applications. For example, with humanoid robotics or digital actors, a loop is formed when both feet touch the ground. As another example, suppose that two robot manipulators, such as the Puma 560 from Example 3.4, cooperate together to carry an object. If each robot grasps the same object with its hand, then a loop will be formed. A complicated example of this was shown in Figure 1.5, in which mobile robots moved a piano. Outside of robotics, a large fraction of organic molecules have flexible loops. Exploring the space of their conformations requires careful consideration of the difficulties imposed by these loops.
The main difficulty of working with closed kinematic chains is that it is hard to determine which parameter values are within an acceptable range to ensure closure. If these values are given, then the transformations are handled in the
Figure 3.27: Loops may be opened to enable tree-based transformations to be applied; however, a closure constraint must still be satisfied.
same way as the case of trees. For example, the links in Figure 3.26 may be transformed by breaking the loop into two different chains. Suppose we forget that the joint between 5 and 6 exists, as shown in Figure 3.27. Consider two different kinematic chains that start at the joint on the extreme left. There is an upper chain from 1 to 5 and a lower chain from 10 to 6. The transformations for any of these bodies can be obtained directly from the techniques of Section
A A
A A A A
3.3.1. Thus, it is easy to transform the bodies, but how do we choose parameter values that ensure 5 and 6 are connected at their common joint? Using the upper chain, the position of this joint may be expressed as
A A
a5
T (θ )T (θ )T (θ )T (θ )T (θ )
0
, (3.79)
1 1 2 2 3 3 4 4 5 5
1
in which (a5, 0) ∈ A5 is the location of the joint of A5 that is supposed to connect to A6. The position of this joint may also be expressed using the lower chain as
a6
T
(θ
)T (θ )T (θ )T (θ )T (θ )
0
, (3.80)
10 10 9 9 8 8 7 7 6 6
1
with (a6, 0) representing the position of the joint in the body frame of A6. If
the loop does not have to be maintained, then any values for θ1, . . ., θ10 may be selected, resulting in ten degrees of freedom. However, if a loop must maintained,
then (3.79) and (3.80) must be equal,
a5
= T
T (θ )T (θ )T (θ )T (θ )T (θ )
0
a6
0
,
1 1 2 2 3 3 4 4 5 5
1
10 10
9 9 8 8 7 7
6 6
1
)T (θ )T (θ )T (θ )T (θ )
(3.81)
(θ
which is quite a mess of nonlinear, trigonometric equations that must be solved. The set of solutions to (3.81) could be very complicated. For the example, the true degrees of freedom is eight because two were removed by making the joint common. Since the common joint allows the links to rotate, exactly two degrees of freedom are lost. If 5 and 6 had to be rigidly attached, then the total degrees of freedom would be only seven. For most problems that involve loops, it will not be possible to obtain a nice parameterization of the set of solutions. This a form of the well-known inverse kinematics problem [252, 693, 775, 994].
A A
In general, a complicated arrangement of links can be imagined in which there are many loops. Each time a joint along a loop is “ignored,” as in the procedure just described, then one less loop exists. This process can be repeated iteratively until there are no more loops in the graph. The resulting arrangement of links will be a tree for which the previous techniques of this section may be applied. However, for each joint that was “ignored” an equation similar to (3.81) must be introduced. All of these equations must be satisfied simultaneously to respect the original loop constraints. Suppose that a set of value parameters is already given. This could happen, for example, using motion capture technology to measure the position and orientation of every part of a human body in contact with the ground. From this the solution parameters could be computed, and all of the transformations are easy to represent. However, as soon as the model moves, it is difficult to ensure that the new transformations respect the closure constraints. The foot of the digital actor may push through the floor, for example. Further information on this problem appears in Section 4.4.