Nonrigid Transformations

One can easily imagine motion planning for nonrigid bodies. This falls outside of the families of transformations studied so far in this chapter. Several kinds of nonrigid transformations are briefly surveyed here.

Linear transformations A rotation is a special case of a linear transformation, which is generally expressed by an n× n matrix, M, assuming the transformations are performed over Rn. Consider transforming a point (x, y) in a 2D robot, A, as

（m11 m12＼ （x＼ . (3.82)

m21 m22

y

If M is a rotation matrix, then the size and shape of will remain the same. In some applications, however, it may be desirable to distort these. The robot can

A

Figure 3.28: Shearing transformations may be performed.

be scaled by m11 along the x-axis and m22 along the y-axis by applying

m11 0

（

0 m22

＼ （x＼ , (3.83)

for positive real values m11 and m22. If one of them is negated, then a mirror image of A is obtained. In addition to scaling, A can be sheared by applying

y

（1 m12＼ （x＼ (3.84)

0 1

y

for m12 = 0. The case of m12 = 1 is shown in Figure 3.28.

/

The scaling, shearing, and rotation matrices may be multiplied together to yield a general transformation matrix that explicitly parameterizes each effect. It is also possible to extend the M from n n to (n + 1) (n + 1) to obtain a

× ×

homogeneous transformation matrix that includes translation. Also, the concepts extend in a straightforward way to R3 and beyond. This enables the additional effects of scaling and shearing to be incorporated directly into the concepts from

Sections 3.2-3.4.

Flexible materials In some applications there is motivation to move beyond linear transformations. Imagine trying to warp a flexible material, such as a mat- tress, through a doorway. The mattress could be approximated by a 2D array of links; however, the complexity and degrees of freedom would be too cumbersome. For another example, suppose that a snake-like robot is designed by connecting 100 revolute joints together in a chain. The tools from Section 3.3 may be used to transform it with 100 rotation parameters, θ1, . . ., θ100, but this may become unwieldy for use in a planning algorithm. An alternative is to approximate the snake with a deformable curve or shape.

For problems such as these, it is desirable to use a parameterized family of curves or surfaces. Spline models are often most appropriate because they are de- signed to provide easy control over the shape of a curve through the adjustment of a small number of parameters. Other possibilities include the generalized-cylinder and superquadric models that were mentioned in Section 3.1.3.

One complication is that complicated constraints may be imposed on the space of allowable parameters. For example, each joint of a snake-like robot could have a

small range of rotation. This would be easy to model using a kinematic chain; how- ever, determining which splines from a spline family satisfy this extra constraint may be difficult. Likewise, for manipulating flexible materials, there are usually complicated constraints based on the elasticity of the material. Even determining its correct shape under the application of some forces requires integration of an elastic energy function over the material [577].

Further Reading

Section 3.1 barely scratches the surface of geometric modeling. Most literature focuses on parametric curves and surfaces [376, 718, 788]. These models are not as popular for motion planning because obtaining efficient collision detection is most important in practice, and processing implicit algebraic surfaces is most important in theoretical methods. A thorough coverage of solid and boundary representations, including semi- algebraic models, can be found in [454]. Theoretical algorithm issues regarding semi- algebraic models are covered in [704, 705]. For a comparison of the doubly connected edge list to its variants, see [522].

The material of Section 3.2 appears in virtually any book on robotics, computer vi- sion, or computer graphics. Consulting linear algebra texts may be helpful to gain more insight into rotations. There are many ways to parameterize the set of all 3D rotation matrices. The yaw-pitch-roll formulation was selected because it is the easiest to under- stand. There are generally 12 different variants of the yaw-pitch-roll formulation (also

called Euler angles) based on different rotation orderings and axis selections. This for-

mulation, however, is not well suited for the development of motion planning algorithms.

It is easy (and safe) to use for making quick 3D animations of motion planning output, but it incorrectly captures the structure of the state space for planning algorithms. Sec- tion 4.2 introduces the quaternion parameterization, which correctly captures this state space; however, it is harder to interpret when constructing examples. Therefore, it is helpful to understand both. In addition to Euler angles and quaternions, there is still motivation for using many other parameterizations of rotations, such as spherical coor- dinates, Cayley-Rodrigues parameters, and stereographic projection. Chapter 5 of [210] provides extensive coverage of 3D rotations and different parameterizations.

The coverage in Section 3.3 of transformations of chains of bodies was heavily influ- enced by two classic robotics texts [252, 775]. The DH parameters were introduced in

[434] and later extended to trees and loops in [524]. An alternative to DH parameters is exponential coordinates [725], which simplify some computations; however, determining the parameters in the modeling stage may be less intuitive. A fascinating history of mechanisms appears in [435]. Other texts on kinematics include [29, 310, 531, 689]. The standard approach in many robotics books [366, 856, 907, 994] is to introduce the kinematic chain formulations and DH parameters in the first couple of chapters, and then move on to topics that are crucial for controlling robot manipulators, including dy- namics modeling, singularities, manipulability, and control. Since this book is concerned instead with planning algorithms, we depart at the point where dynamics would usually be covered and move into a careful study of the configuration space in Chapter 4.

Exercises

1. Define a semi-algebraic model that removes a triangular “nose” from the region shown in Figure 3.4.
2. For distinct values of yaw, pitch, and roll, it is possible to generate the same rotation. In other words, R(α, β, γ) = R(α′, β′, γ′) for some cases in which at least

α /= α, β /= β′, or γ /= γ′. Characterize the sets of angles for which this occurs.

1. Using rotation matrices, prove that 2D rotation is commutative but 3D rotation is not.
2. An alternative to the yaw-pitch-roll formulation from Section 3.2.3 is considered here. Consider the following Euler angle representation of rotation (there are many other variants). The first rotation is Rz (γ), which is just (3.39) with α replaced by γ. The next two rotations are identical to the yaw-pitch-roll formulation: Ry (β) is applied, followed by Rz (α). This yields Reuler(α, β, γ) = Rz (α)Ry (β)Rz (γ).
   1. Determine the matrix Reuler.
   2. Show that Reuler(α, β, γ) = Reuler(α − π, −β, γ − π).
   3. Suppose that a rotation matrix is given as shown in (3.43). Show that the Euler angles are

and

α = atan2(r23, r13), (3.85)

β = atan2(/1 − r2 , r33), (3.86)

33

γ = atan2(r32, −r31). (3.87)

1. There are 12 different variants of yaw-pitch-roll (or Euler angles), depending on which axes are used and the order of these axes. Determine all of the possibilities, using only notation such as Rz (α)Ry (β)Rz (γ) for each one. Give brief arguments that support why or why not specific combinations of rotations are included in your list of 12.
2. Let A be a unit disc, centered at the origin, and W = R2. Assume that A is represented by a single, algebraic primitive, H = {(x, y) | x2 + y2 ≤ 1}. Show that

the transformed primitive is unchanged after any rotation is applied.

1. Consider the articulated chain of bodies shown in Figure 3.29. There are three identical rectangular bars in the plane, called A1, A2, A3. Each bar has width 2

and length 12. The distance between the two points of attachment is 10. The first bar, A1, is attached to the origin. The second bar, A2, is attached to A1, and A3 is attached to A2. Each bar is allowed to rotate about its point of attachment. The

configuration of the chain can be expressed with three angles, (θ1, θ2, θ3). The first

angle, θ1, represents the angle between the segment drawn between the two points of attachment of A1 and the x-axis. The second angle, θ2, represents the angle

c

10

12

Figure 3.29: A chain of three bodies.

Figure 3.30: Another exercise involving a chain of bodies.

between A2 and A1 (θ2 = 0 when they are parallel). The third angle, θ3, represents the angle between A3 and A2. Suppose the configuration is (π/4, π/2, −π/4).

• 1. Use the homogeneous transformation matrices to determine the locations of points a, b, and c.
  2. Characterize the set of all configurations for which the final point of attach- ment (near the end of A3) is at (0, 0) (you should be able to figure this out

without using the matrices).

1. A three-link chain of bodies that moves in a 2D world is shown Figure 3.30. The first link, A1, is attached at (0, 0) but can rotate. Each remaining link is attached to another link with a revolute joint. The second link, A2, is a rigid ring, and the

other two links are rectangular bars.

Assume that the structure is shown in the zero configuration. Suppose that the linkage is moved to the configuration (θ1, θ2, θ3) = ( π , π , π ), in which θ1 is

4 2 4

the angle of A1, θ2 is the angle of A2 with respect to A1, and θ3 is the angle of

A3 with respect to A2. Using homogeneous transformation matrices, compute the

position of the point at (4, 0) in Figure 3.30, when the linkage is at configuration ( π , π , π ) (the point is attached to A3).

4

2

4

1. Approximate a spherical joint as a chain of three short, perpendicular links that are attached by revolute joints and give the sequence of transformation matrices. Show that as the link lengths approach zero, the resulting sequence of transforma- tion matrices converges to exactly representing the freedom of a spherical joint.

Compare this approach to directly using a full rotation matrix, (3.42), to represent the joint in the homogeneous transformation matrix.

1. Figure 3.12 showed six different ways in which 2D surfaces can slide with respect to each other to produce a joint.
   1. Suppose that two bodies contact each other along a one-dimensional curve. Characterize as many different kinds of “joints” as possible, and indicate the degrees of freedom of each.
   2. Suppose that the two bodies contact each other at a point. Indicate the types of rolling and sliding that are possible, and their corresponding degrees of freedom.
2. Suppose that two bodies form a screw joint in which the axis of the central axis of the screw aligns with the x-axis of the first body. Determine an appropriate homo- geneous transformation matrix to use in place of the DH matrix. Define the matrix with the screw radius, r, and displacement-per-revolution, d, as parameters.
3. Recall Example 3.6. How should the transformations be modified so that the links are in the positions shown in Figure 3.25 at the zero configuration (θi = 0 for every revolute joint whose angle can be independently chosen)?
4. Generalize the shearing transformation of (3.84) to enable shearing of 3D models.

Implementations

1. Develop and implement a kinematic model for 2D linkages. Enable the user to display the arrangement of links in the plane.
2. Implement the kinematics of molecules that do not have loops and show them graphically as a “ball and stick” model. The user should be able to input the atomic radii, bond connections, bond lengths, and rotation ranges for each bond.
3. Design and implement a software system in which the user can interactively attach various links to make linkages that resemble those possible from using Tinkertoys (or another popular construction set that allows pieces to move). There are several rods of various lengths, which fit into holes in the center and around the edge of several coin-shaped pieces. Assume that all joints are revolute. The user should be allowed to change parameters and see the resulting positions of all of the links.
4. Construct a model of the human body as a tree of links in a 3D world. For simplicity, the geometric model may be limited to spheres and cylinders. Design and implement a system that displays the virtual human and allows the user to click on joints of the body to enable them to rotate.
5. Develop a simulator with 3D graphics for the Puma 560 model shown in Figure 3.4.