DIMACS

Center for Discrete Mathematics & Theoretical Computer Science

DIMACS EDUCATIONAL MODULE SERIES

MODULE 03-4 Planar Linkages: Robot Arms and Carpenters’ Rulers

Date prepared: July 20, 2004

Nancy Lineken Hagelgans Department of Mathematics and Computer Science Ursinus College Collegeville, PA 19426 email: NHagelgans@Ursinus.edu

DIMACS Center, CoRE Bldg., Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ 08854-8018

TEL: 732-445-5928 • FAX: 732-445-5932 • EMAIL: center@dimacs.rutgers.edu

                         Web: http://dimacs.rutgers.edu/

Founded as a National Science Foundation Science and Technology Center and a Joint Project of Rutgers University, Princeton University, AT&T Labs - Research, Bell Labs, NEC Laboratories America and Telcordia Technologies with affiliated members Avaya Labs, HP Labs, IBM Research, Microsoft Research.

Module Description Information

• Title:

Planar Linkages: Robot Arms and Carpenters’ Rulers

• Author(s):

Nancy Lineken Hagelgans

• Abstract:

A robot arm in the plane is defined as a planar linkage with links connected to form a chain and with one end in a fixed position. We address questions related to the region in the plane that the arm’s other end can reach either with or without obstructions to the arm’s movement. A carpenters’ ruler is another planar linkage in the form of a chain, but a ruler has no fixed end. The question investigated is the minimal folding length of a ruler that has links of different lengths.

Exercises throughout the module should be completed as they appear in the module. These exercises introduce students to the main ideas through specific examples. More challenging problems appear at the ends of Sections 3, 4, and 5.

• Target Audience:

This module is suitable for mathematically advanced high school students as well as college mathematics students.

• Prerequisites:

The prerequisite knowledge is high school geometry, sigma notation, and proof by mathematical induction.

• Topics and Goals:

The topics are two problems involving planar linkages: the reachability region of a robot arm in the plane and the minimal folding of a carpenters’ ruler. The goals are to introduce the concepts of planar linkages and to illustrate proof by mathematical induction in a geometric context.

• Anticipated Number of Class Meetings:

The entire module would take six class meetings. Sections 1 through 3 could be used alone for two class meetings. The first three sections could be followed by either Section 4 or Section 5, each of which would involve two class meetings. On the other hand, the module is suitable for independent student projects with little or no class time devoted to the material.

• Contact Information: Nancy Lineken Hagelgans Department of Mathematics and Computer Science Ursinus College Collegeville, PA 19426 email: NHagelgans@Ursinus.edu

• Other DIMACS modules related to this module:

None at this time

TABLE OF CONTENTS

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Jointless Robot Arms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Robot Arms with Two Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 Multi-link Robot Arms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5 Carpenters’ Rulers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

ABSTRACT

A robot arm in the plane is defined as a planar linkage with links connected to form a chain and with one end in a fixed position. We address questions related to the region in the plane that the arm’s other end can reach either with or without obstructions to the arm’s movement. A carpenters’ ruler is another planar linkage in the form of a chain, but a ruler has no fixed end. The question investigated is the minimal folding length of a ruler that has links of different lengths.

Exercises throughout the module should be completed as they appear in the module. These exercises introduce students to the main ideas through specific examples. More challenging problems appear at the ends of Sections 3, 4, and 5.

1 Introduction

Robot arms are pervasive in the scientific and manufacturing world of today. They perform feats that would be impossible or impractical without their help. Robot arms have retrieved material and taken pictures under the oceans as well as on the moon and on Mars. A robot arm can work with radioactive materials while people stand behind protective shields. In this module, we will explore the extent of a robot arm restricted to the plane. This is known as the reachability problem.

Carpenters’ rulers are devices used to measure lengths. The real rulers have hinged parts all of the same length. These rulers can be folded to the length of just one part, and then they can be partially or totally unfolded according to the length to be measured. Thus a carpenter can carry a relatively small tool that can be expanded to measure much greater lengths, such as the length of a wall of a room. We extend the definition of such a ruler to address rulers whose parts vary in length. For these rulers, we explore the folding problem: the problem of folding the ruler to as small a length as possible.

The two devices we study are examples of planar linkages. They comprise rigid rods linked together to form a chain. In the study of robot arms, we assume that one end of the arm is in a fixed position, and we are interested in finding all points in the plane that the other end can reach. We first consider an arm with only one link, and then we go on to discuss robot arms with joints. Finally, we examine carpenters’ rulers, chains of rigid rods with no fixed joints.

2 Jointless Robot Arms

Suppose that a robot arm has no joints. We can consider this arm to be a rigid rod with a fixed end J_{0}, which is called the shoulder. The other end, J_{1}, moves freely only in a plane. Intuitively, we think of the end J_{1} having an attached pen to put a mark or a tool to do some work. The robot arm’s length is L, and the counterclockwise angle at J_{0} from the horizontal line through J_{0} to the arm is angle A.

Figure 2.1

Exercises

2.1 Estimate the size of angle A in Figure 2.1.

2.2 Sketch a jointless arm with length L of 2 inches and angle A of 135 degrees. Label the angle A and points J_{0} and J_{1}.

2.3 Now suppose that the 2-inch robot arm has its shoulder placed at the origin of a coordinate system in the plane and that the arm can freely rotate about this fixed point. Which of the following points can the robot arm reach, i.e., which points can the end J_{1} reach? If the point can be reached, what is the angle A?

a. (2, 0) b. (0, 2)

c. (−1.5, 0)

d. (\sqrt{2}, −\sqrt{2})

2.4 A one-link arm of length 2 has its shoulder J_{0} placed at the origin of its plane. Find the location of its other end J_{1} given each of the following angles A.

a. A = 90^{∘}

b. A = 270^{∘}

a. A = 135^{∘}

2.5 Sketch and describe the set of points in the plane that the 2-inch arm can reach.

Exercise 2.3 above gives examples of the reachability problem for a robot arm of one link: given the length L, the position of the shoulder J_{0}, and a point P in the plane, can the arm reach the point P, and if so, what is the angle A? In Exercise 2.5, you found the arm’s reachability region, the set of points reachable by the arm. The theorem below describes this reachability region for a given one-link arm.

Theorem 2.1 The reachability region of a one-link arm is the circle with radius the length L and with center the shoulder J_{0}.

Now we assume that there are obstructions in the plane that may prevent free movement of the arm.

Exercises

2.6 Let R be a one-link arm of length 2 with the shoulder J_{0} at the origin and with the other end J_{1} initially at the point (2, 0). Find and sketch the reachability region if poles or pegs perpendicular to the arm’s plane are located at the indicated points and obstruct the arm’s motion in the plane. In particular, assume that the arm cannot move through a pole located in its reachability region.

a. (0, −2)

b. (\sqrt{2}, \sqrt{2}) and (−2, 0)

c. (0, 2), (−2, 0), and (0, −2)

d. (1, 1) and (\sqrt{3}, −\sqrt{3})

2.7 What effect does the addition of obstructing poles have on the reachability region? What is the shape of the reachability region when one or more poles obstruct the motion of the arm?

2.8 The reachability region of a one-link arm of length 3 is an open semicircle with endpoints at the points (1, 3) and (1, −3). Where is the arm’s shoulder located? Find an initial position and a smallest set of obstructing poles within the reachability region of a freely moving arm.

In the next two sections we go on to discuss the reachability region in the plane of robot arms with more than one link. We keep in mind that, with one end of a link fixed, the other end of the link moves to any point in a specific circle if the motion is unobstructed.

3 Robot Arms with Two Links

Now we consider robot arms of two rigid links. An end of one link is attached to an end of the other link at the joint J_{1} as shown in Figure 3.1. The shoulder J_{0} of a robot arm is fixed, and otherwise the entire arm can move freely in a plane. The links are allowed to pass over each other.

Figure 3.1

Exercises

3.1 Suppose that R is a 2-link robot arm, and that R′ is another 2-link robot arm with the same shoulder but with the links interchanged. Explain how the parallelogram of Figure 3.2 shows that a point P in the plane is reachable by arm R if and only if it is reachable by arm R′.

Figure 3.2

You have just proved the following theorem.

Theorem 3.1 Two-link robot arms with the same shoulder and same link lengths (in either order) have the same reachability region.

The lengths of the links of a two-link arm are called L_{1} and L_{2} so that L_{1} is the length of the link with joints J_{0} and J_{1}, and L_{2} is the length of the link with joints J_{1} and J_{2}. The angles involved are the counterclockwise angle A_{1} at J_{0} from the horizontal line through J_{0} to the first link, and the counterclockwise angle A_{2} at J_{1} from the first link to the second link. These lengths and angles are shown in Figure 3.3.

Figure 3.3

The reachability problem for 2-link robot arms can be stated as follows: given the lengths L_{1} and L_{2}, the shoulder J_{0}, and a point P (x_{0}, y_{0}) in the plane, can the robot arm reach the point P, and if so, which counterclockwise angles A_{1} and A_{2} allow P to be reached?

Exercises

3.2 Suppose that a 2-link arm R with link lengths L_{1} = 2 and L_{2} = 1 has shoulder at the origin.

a. Solve the reachability problem given the arm R and each of the following points. Plot on one graph and label those points that are reachable.

i. (3, 0)

ii. (1, 0) iii. (0, 1/2) iv. (0, 4) v. (\sqrt{2}, \sqrt{2})

b. Plot and label at least five additional points in the reachability region on the graph of part a. For each point, give the two angles A_{1} and A_{2}.

c. Suppose that not only is the shoulder fixed at the origin but that also the joint J_{1} is fixed at the point with x-coordinate 1. Then what is the reachability region? Sketch the arm and the reachability region.

d. On the same graph sketch the different reachability regions when the joint J_{1} is fixed at each of five different points.

e. On a new graph sketch the reachability region of the arm R when J_{1} is free to move and only the shoulder J_{0} is fixed.

3.3 Suppose that a 2-link arm R with link lengths L_{1} = 1 and L_{2} = 2 has shoulder at the origin. Sketch and describe R’s reachability region. Hint: Review Theorem 3.1.

3.4 Suppose that a 2-link arm R with link lengths L_{1} = 2 and L_{2} = 3 has shoulder at the origin. Find the point reached with each pair of given angles. Sketch.

a. A_{1} = 90^{∘} and A_{2} = 90^{∘}

b. A_{1} = 180^{∘} and A_{2} = 90^{∘}

c. A_{1} = 90^{∘} and A_{2} = 180^{∘}

d. A_{1} = 90^{∘} and A_{2} = 0^{∘}

e. A_{1} = 45^{∘} and A_{2} = 180^{∘} 3.5 Is it ever possible for a 2-link arm R to reach a point in more than one way, i.e., with different

angles A_{1} and A_{2}? Explain and give specific examples.

3.6 Describe all 2-link robot arms with the reachability region shown in Figure 3.4. (The description of an arm consists of the position of the shoulder and the lengths of the links listed in order.) The inner circle has radius 1 and center at the origin.

Figure 3.4

3.7 Suppose that you are given a circle C of radius 1 and a circle C′ of radius 3.

a. How many intersection points of these two circles could occur when the circles are placed at various positions in the plane?

b. Sketch the two circles in various relative positions in the plane to illustrate all the possible cases (for 0, 1, 2, or possibly more intersection points).

c. Let A be the region in the plane bounded by the two circles with centers at the center of C′ and with radii 2 and 4, respectively. (The region A is an open annulus with inner radius 2 and outer radius 4.)

i. In which of your illustrations in part b. does the center of the circle C lie on the circle

with radius 2? Explain. ii. In which of your illustrations in part b. does the center of the circle C lie on the circle

with radius 4? Explain. iii. In which of your illustrations in part b. does the center of the circle C lie within the

annulus A? Explain.

The examples that you have explored in the exercises illustrate the reachability region of a 2-link robot arm. As we see in Figure 3.4, this region is a closed annulus, two concentric circles and the region between these circles. The common center is the position of the arm’s shoulder. The smaller radius (inner radius ri), is the absolute value of the difference L_{1} − L_{2}, and the larger radius (outer radius ro) is the sum of these lengths:

ri = |L_{1} − L_{2}|, and ro = L_{1} + L_{2}.

We will consider a disk to be a degenerate annulus with ri = 0 so that the case where L_{1} = L_{2} does not need to be treated separately.

The proof of Theorem 3.2 justifies these statements.

Theorem 3.2 The reachability region of a 2-link robot arm is a closed annulus centered at the shoulder. The inner radius ri = |L_{1} − L_{2}|, and the outer radius ro = L_{1} + L_{2}.

Proof We can assume that L_{1} ≥ L_{2} without loss of generality by Theorem 3.1. In this case we want to show that the inner radius ri = L_{1} − L_{2}.

Let P be a point in the plane. Let C be the circle with radius L_{2} and center P, and let C′ be the circle with radius L_{1} and center J_{0}. See Figure 3.5. Because the arm’s first link has length L_{1}, the joint J_{1} must lie on the circle C′. Since the arm’s second link has length L_{2}, the arm reaches the point P only when J_{1} lies on the circle C. Thus, the point P is reached if and only if J_{1} lies on both circles, i.e., if and only if the two circles intersect (at a point where J_{1} can be placed, as shown in Figure 3.6). The two circles intersect if and only if P lies in the required closed annulus. Therefore, P is reachable if and only if P lies within this annulus. ◇

Figure 3.5

Figure 3.6

When a 2-link arm moves without obstructions in the plane and without constraints on the angles, all points of the outer circle of the annular reachability region are reached by extending the arm fully, i.e., with angle A_{2} equal to 180^{∘}. Similarly, all points of the inner circle are reached by folding the second link back over the first link, i.e., with zero angle A_{2}.

In the next exercises we will impose conditions that may reduce the reachability region.

Exercises

3.8 A 2-link robot arm has shoulder at the origin. Its link lengths are L_{1} = 5 and L_{2} = 2.

a. Describe the reachability region if there are no obstructions to movement in the plane.

b. Describe the reachability regions when obstructing poles are placed at the following points. Answer the question for different initial positions of the arm.

i. (0, 2) ii. (0, 4)

iii. (0, 8)

iv. (0, 4) and (0, 7)

v. (0, 4) and (−4, 0)

c. Describe the reachability regions when the following restrictions are placed on the arm’s joint angles.

i. 0 ≤ A_{1} ≤ 180^{∘}

ii. 90^{∘} ≤ A_{2} ≤ 180^{∘}

Problems

3.1 Sketch and describe the reachability region of a 2-link robot arm when one, two, or more obstructing poles are placed at various points in the plane.

3.2 Sketch and describe the reachability region of a 2-link arm when one or both of its joint angles are restricted to intervals with endpoints a and b, where 0 ≤ a < b < 360 degrees.

3.3 A 2-link arm has reachability region shown in Figure 3.7. The inner circle has radius 1 and center at the origin. Suppose that only part of this annulus (as described below) is wanted for the reachability region. With this robot arm, describe a minimal set of obstructing poles that yields each reachability region listed below (whenever possible). Also state restrictions on the joint angles that yield these regions (whenever possible). Explain and justify your answers.

Figure 3.7

a. the upper half of the annulus, and the lower halves of the two disks with radii 2 and centers (±3, 0)

b. the part of the annulus of at most distance 3 from the origin

c. the part of the annulus of at least distance \sqrt{13} from the origin

d. the part of the annulus in the first and third quadrants

e. some other regions of different types

4 Multi-link Robot Arms

Now that we have investigated the properties of robot arms with either one link or two links, we move on to consider arms with any number of links. We assume that each arm has n links, where n ≥ 1, and that the shoulder J_{0} is fixed at the origin. Except for the shoulder, we assume that the arm moves freely in the plane, and the links may pass over each other. Later we will restrict the motion in various ways. Our main concern is the reachability region.

We will use the following notation for n-link robot arms:

1. The ends of the links (the joints): J_{0}, J_{1}, …, J_{n}

2. The counterclockwise angles: A_{1} from the horizontal to the first link, and A_{i} from the (i−1)^{st} link to the i^{th} link for i = 2, 3, …, n

3. The length of the i^{th} link: L_{i}

A 4-link arm is shown in Figure 4.1.

Figure 4.1

Exercises

4.1 Suppose that the link lengths of a 3-link arm are 1, 2, and 3.

a. In how many different ways can an arm be constructed with these links?

b. Consider the arms with link lengths shown in the table below.

\begin{matrix}Arm & L_{1} & L_{2} & L_{3} \\ R_{1} & 1 & 2 & 3 \\ R_{2} & 1 & 3 & 2 \\ R_{3} & 3 & 2 & 1 \end{matrix}

Sketch diagrams to show that a point P in the plane is either reachable by all three arms or by none of these three arms. Hint: Review Figure 3.2 and Theorem 3.1.

4.2 Now suppose that the link lengths of a 4-link arm are 1, 2, 4, and 5. Suppose that R is an arm in which the link lengths occur in ascending order, and suppose that R′ is an arm for which these lengths occur in descending order. Let P be a point reachable by R. Construct a sequence of arms with these lengths that all reach P. The first arm in the sequence is R, and the last arm is R′. In addition, the next arm is obtained at each step by interchanging only two adjacent link lengths. For example, the second arm could have link lengths 1, 2, 5, 4 in that order by interchanging only the last two links. Explain why P is reachable by each arm in the sequence and sketch supporting diagrams.

In the preceding exercises, different arrangements of given links form robot arms with the same reachability regions. We will show rather remarkably that the link lengths rather than the order in which the links are assembled determine the reachability region of any n-link arm. Later we will find it useful to consider those robot arms that have the longest link first.

Theorem 4.1 Any two n-link robot arms with the same set of link lengths have identical reachability regions. [OR, page 325]

Proof Recall that consideration of a parallelogram led to the conclusion that two 2-link arms with the same link lengths have the same reachability region (Exercise 3.1). We apply this idea to see that any two links of a robot arm can be interchanged without affecting the reachability region. Let R and R′ be any two n-link arms with the same set of link lengths. Then there is a sequence of arms starting with R and ending with R′ such that a new arm in the sequence is obtained from the previous arm by interchanging the order of exactly two adjacent link lengths. Thus R and R′ have the same reachability region. ♢

Exercises

4.3 A 3-link robot arm R has link lengths L_{1} = 5, L_{2} = 2, and L_{3} = 1.

a. Describe and sketch the reachability region of the 2-link arm formed from the first two links of R.

b. Choose 10 points P within the reachability region (of the 2-link arm of part a.) and 5 points P on the boundary of this reachability region. For each of these 15 points P, sketch a circle of center P and radius 1. How are these circles related to the 3-link arm R?

c. Describe and sketch the reachability region of the arm R.

4.4 Answer the questions of Exercise 4.3 for a 3-link robot arm with link lengths L_{1} = 4, L_{2} = 3, and L_{3} = 3.

4.5 Why do you obtain different results for the two 3-link robot arms of the preceding exercises?

Notice that the longest link is the first link in the arms investigated in the Exercises 4.3 and 4.4. The next theorem explicitly states the conditions that determine whether the reachability region is an annulus with ri > 0 or a disk (an annulus with ri = 0). The theorem relates the radii ri and ro to the link lengths.

Theorem 4.2 The reachability region of a robot arm with n links, where n > 1, is an annulus centered at the origin with the following properties:

1. the outer radius ro equals the sum of the link lengths: ro = ∑_{i=1}^{n} L_{i}, and

2. the inner radius ri equals the largest link length L_{M} less the sum of the other link lengths if this difference is not negative, and otherwise ri equals zero:

ri = max{0, L_{M} − ∑_{i≠M} L_{i}}. [OR, page 326; HJW85, page 318]

Proof (by induction on n) The theorem holds for any 2-link arm by Theorem 3.2 . Let n > 1, and assume that the theorem holds for any n-link arm. Let R be an (n + 1)-link arm with link lengths L_{1}, L_{2}, …, L_{n}, L_{n+1}. Without loss of generality, by Theorem 4.1, we can assume that the link lengths occur in descending order. Then the longest link is the first link. Let R′ be the n-link arm constructed by deleting the last (and smallest) link from the arm R. Then, by the inductive hypothesis, the reachability region of R′ is an annulus centered at the origin such that:

1. the outer radius ro = ∑_{i=1}^{n} L_{i} , and

2. the inner radius ri = max{0, L_{1} − ∑_{i=2}^{n} L_{i}}.

Let P be a point in the plane, and denote P ’s distance from the origin by |P |. Then P is not reachable by the arm R if |P | > ∑_{i=1}^{n+1} L_{i} since R can reach only the distance L_{n+1} from the reachable points of R′ of greatest distance from the origin. Similarly, P is not reachable by the arm R if |P | < L_{1} − ∑_{i=2}^{n+1} L_{i} since R can reach only the distance L_{n+1} from the reachable points of R′ closest to the origin. For P at any other location in the plane, the circle with center at P and with radius L_{n+1} has at least one intersection point with the reachability region of R′. Therefore, the reachability region of R is the required annulus. ♢

Corollary 4.3 The following three conditions on an n-link arm R are equivalent:

1. R’s reachability region has inner radius ri = 0,

2. L_{M} ≤ ∑_{i≠M} L_{i} , where L_{M} is R’s largest link length, and

3. L_{M} ≤ L/2, where L = ∑_{i=1}^{n} L_{i}.

Proof The equivalence of the first two conditions follows immediately from the expression of ri as a maximum. To show that the second and third condition are equivalent, add L_{M} to both sides of the inequality of the second condition, and then divide by 2. ♢

Once we know that a point is reachable by a robot arm, we would like to consider different configurations of the arm that allow the arm to reach that point. In particular, we know that any point of the outer bounding circle can be reached in only one way, and all the joint angles except the one at the shoulder are 180 degrees in this solution. On the other hand, if the link of maximum length is the first link and r_{i} > 0, a point of the inner bounding circle is reached with the joint angle J_{1} equal to 0 degrees and the other joint angles, except the shoulder angle, equal to 180 degrees. We are especially interested in 180 degree joint angles because the two links meeting at these joints can be considered to be only one link rather than two links.

Exercises

4.6 Consider a 7-link robot arm R with link lengths 3, 6, 5, 2, 2, 4, and 2 in that order.

a. Sketch the reachability region of the arm R.

b. Compute the sum L of R’s link lengths. How is this sum related to the reachability region?

c. We want to find a particular link called the median link (of length L_{m}). Begin adding the link lengths starting at the shoulder (3 + 6 + …), and stop adding when this sum is greater than L/2, where L is the total length found in part b. The link whose length puts the cumulative sum greater than L/2 is the median link. What is its length?

d. Sketch a horizontal line segment of length 6 inches. Consider this line to represent the arm fully extended, i.e., with 180 degree joint angles. What is the length on the line that represents one unit in the measurement of the robot arm? Sketch a vertical line segment at

�

the midpoint of the 6-inch line segment. How is this vertical line related to the median link? Explain.

e. Let R′ be the 3-link robot arm obtained from R by fixing R’s joint angles at 180 degrees with the exception of angles A_{1}, A_{m−1}, and A_{m}. Then only three joints can be varied: the shoulder joint J_{0} and the two joints at the ends of the median link.

i. What are the three link lengths of the arm R′?

ii. Sketch the reachability region of R′. How is this region related to the reachability region of the arm R?

4.7 Let R be a 6-link robot arm with link lengths 3, 2, 2, 1, 10, and 1 in that order.

a. Sketch the reachability region of the arm R.

b. Compute the sum L of R’s link lengths. How is this sum related to the reachability region?

c. Find the length L_{m} of the median link.

d. How is L_{m} related to L_{M}?

e. Let R′ be the 3-link robot arm obtained from R by fixing R’s joint angles at 180 degrees with the exception of angles A_{1}, A_{m−1}, and A_{m}. Then only three joints can be varied: the shoulder joint J_{0} and the two joints at the ends of the median link.

i. What are the three link lengths of the arm R′?

ii. Sketch the reachability region of R′. How is this region related to the reachability region of the arm R?

The two multi-link arms of the preceding exercises illustrate the two cases: zero and nonzero inner radius of the reachability region. In both examples, you were able to find a 3-link robot arm with the same reachability region as that of the given arm. In fact, we will show (in the next theorem) that every robot arm has the same reachability region as an arm with only 2 or 3 links. First we consider some useful relations involving the link lengths L_{m} and L_{M}.

Lemma 4.4 Let L_{m} be the median link length and L_{M} the maximum link length of a robot arm. If ri > 0, then M = m.

Proof Suppose that ri > 0. Then, by Corollary 4.3, L_{M} > L/2. Thus the longest link cannot be any link other than the median link, i.e., M = m. ♢

Theorem 4.5 Suppose that n > 1 and that R is an n-link robot arm with link lengths L_{1}, L_{2}, …, L_{n}.

1. If the median link is not the first link or last link, then R has the same reachability region as a 3-link arm R′ with link lengths ∑_{i=1}^{m−1} L_{i}, L_{m}, and ∑_{i=m+1}^{n} L_{i}.

2. If the median link is either the first link or the last link, then R has the same reachability region as a 2-link arm R′ with link lengths L_{m} and ∑_{i≠m} L_{i}. [OR, page 329]

Proof The reachability region of each robot arm mentioned is an annulus centered at the origin with outer radius ro = ∑_{i=1}^{n} L_{i}. Thus it remains to check only the inner radii. Let ri be the inner radius of the reachability region of the n-link arm R. We consider the two possible cases: positive and zero inner radius ri.

Suppose that ri > 0. Then M = m by Lemma 4.4. So the robot arm constructed from R by fixing all but the required two or three joints to 180 degrees, has the maximum link length L_{M} and thus the same inner radius,

L_{M} − ∑_{i≠M} L_{i},

of its reachability region.

Now suppose that ri = 0. Then L_{M} ≤ L/2 by Corollary 4.3. Also, by definition of the median link, ∑_{i=1}^{m−1} L_{i} < L/2 and ∑_{i=m+1}^{n} L_{i} < L/2. Therefore, whether or not the longest link length of R′ is L_{M}, the longest length of R′ is less than or equal to L/2. So, by Corollary 4.3 applied to R′, the inner radius for R′ is zero.

Thus, in both cases, the reachability regions of the robot arms R and R′ are identical. ♢

We will find that the arms with 2 or 3 links help us to determine reachability regions when the other arms are unable to move freely.

Exercises

4.8 A 3-link robot arm R has link lengths L_{1} = 3, L_{2} = 7, and L_{3} = 2. Sketch and describe its reachability region when obstructing poles occur at the following points. There may be several regions determined by different initial positions of the arm.

a. (1, 0)

b. (3, 0)

c. (5, 0)

d. (1, 0) and (0, 5)

e. (1, 0), (0, 5), and (−3, 0)

4.9 A 5-link robot arm has link lengths 2, 1, 6, 1, and 1 in that order. Sketch and describe its reachability region when obstructing poles occur at the points given in the preceding problem.

4.10 A 3-link robot arm has link lengths L_{1} = 3, L_{2} = 7, and L_{3} = 5. Sketch and describe its reachability region when obstructing poles occur at the following points.

a. (1, 0)

b. (4, 0)

c. (1, 0) and (0, 4)

Problems

4.1 Let R be a 3-link robot arm with link lengths L_{1}, L_{2}, and L_{3} and with reachability region the closed annulus A.

a. Sketch and describe the annulus A. Indicate L_{1}, L_{2}, and L_{3}. On this sketch indicate the region reached when the joint J_{1} is in a fixed position. Hint: There are several cases.

b. In how many different configurations can the arm R reach a point P on the boundary of A? Explain.

c. In how many different configurations can the arm R reach a point P in the interior of A? Describe the joint angles A_{1} that make it possible for the arm R to reach P.

4.2 Sketch and describe the reachability region of a 3-link robot arm when one or two obstructing poles are placed at various positions in the plane.

4.3 Sketch or describe the reachability region of a 3-link robot arm when its joint angles are restricted to certain intervals.

We return to the reachability problem, and now we consider robot arms with any number of links. The general problem can be stated as follows: given the link lengths of a robot arm, the shoulder J_{0}, and a point P (x_{0}, y_{0}) in the plane, can the robot arm reach the point P, and if so, which joint angles allow P to be reached? Since we know that the reachability region of a robot arm is a closed annulus centered at the shoulder (by Theorem 4.2), we can readily determine whether or not the point P is reachable by computing its distance from the shoulder. We also know the unique angles when the point P lies on the boundary of the annulus. In general, the number of sets of joint angles that allow an arm to reach a point P in the interior of the annulus is larger for a larger number of links, i.e., there are more configurations possible. Some of these angles can be found by applying Theorem 4.6 and its proof.

Problems

4.4 A 3-link robot arm R has link lengths 10, 4, and 2 in that order. Its shoulder lies at the origin. Solve the reachability problem for the following points. Certain angles may be found by measuring them with a protractor in your carefully drawn diagram or by using trigonometry. You may use diagrams to indicate angles when P lies in the interior of the reachability region. Hint: Review Figures 3.5 and 3.6 to help you find the configurations when P lies in the interior of the reachability region. a. (1, 0) b. (6, 0) c. (8, 0) d. (0, 16) e. (0, 20) f. (5\sqrt{2}, 6 − 5\sqrt{2})

4.5 How would your answers to the questions of Problem 4.4 change for an arm with link lengths 10, 2, 2, and 2 in that order?

When we considered robot arms of 2 links, we saw that each point in the interior of the reachability region could be reached in two ways, with two different sets of joint angles. These problems show us that there are many ways for a robot arm of more than 2 links to reach a point in the interior of its reachability region.

5 Carpenters’ Rulers

A carpenters’ ruler consists of rigid links joined end to end to form a chain. The links may cross over each other as they rotate about their endpoints, which are called the joints. These rulers are used to measure lengths, such as the dimensions of a room. Although a real carpenters’ ruler has links all of the same length, we consider rulers where the links may differ in length.

We will adopt the notation used earlier for robot arms. In fact, the main difference between a robot arm and a carpenters’ ruler is that, unlike the robot arm, a ruler has no fixed end such as the shoulder of a robot arm.

Let L_{1}, L_{2}, …, L_{n} be the link lengths, and let J_{0}, J_{1}, J_{2}, …, J_{n} be the joints. As for robot arms, J_{0} and J_{n} are the ends of the device. A carpenters’ ruler with four links is shown in Figure 5.1.

A ruler’s greatest length is achieved when all the joint angles equal 180^{∘}. We will investigate the ruler when folded, that is when each joint angle is either 0^{∘} or 180^{∘}. A folded 6-link ruler is indicated in Figure 5.2. The angle at the joint J_{4} is 180^{∘}, and the other joint angles are 0^{∘}. The folded length of the ruler is approximately L, as shown in Figure 5.2.

Figure 5.2

Exercises

5.1 A carpenters’ ruler is to be assembled with links of lengths 6, 7, and 8 inches.

a. What is its maximum length? What joint angles yield this maximum length?

b. How many different rulers can be made by joining the links in different orders?

c. Fold each ruler (of part b.) so that its folded length is as small as possible. Sketch the folded rulers and indicate the smallest folded length on the sketch.

d. Are the minimal folded lengths the same for the different rulers (of part b.)?

5.2 A carpenters’ ruler R has link lengths L_{1} = 2, L_{2} = 3, L_{3} = 5, and L_{4} = 1.

a. Is it possible to fold the ruler R with folded length L = 4? Explain.

b. What is the smallest folding length possible? Sketch all the ways that R can be folded with the smallest folding length.

The exercises above have shown two properties of carpenters’ rulers:

1. Rulers with the same link lengths but with links assembled in different order may have different shortest folding length.

2. The shortest folding length of a ruler may be achieved in more than one way.

We are mainly interested in solving the minimum length folding problem: given a carpenters’ ruler, find its minimum folding length and state the joint angles that achieve this length.

The next exercises involve carpenters’ rulers with more than three links.

Exercises

5.3 A carpenters’ ruler R has link lengths L_{1} = 3, L_{2} = 4, L_{3} = 7, L_{4} = 4, and L_{5} = 2.

a. What is the longest length of a link? We will call this maximum length L_{M}.

b. Sketch the ruler R folded using the following method:

i. Sketch a horizontal line segment S of length twice L_{M}. Assume the units are inches.

ii. Place R’s first link on the segment S as far left as possible, so J_{0} is placed on the left endpoint of S.

iii. Place the other links in order according to the following directions: place the joint J_{i} to the right of J_{i−1} if the i^{th} link would still be within the segment S; otherwise place J_{i} to the left of J_{i−1}.

What is the folding length L of the ruler folded in this manner? Is L < 2L_{M}? Is L = 2L_{M}?

5.4 Answer the questions of Exercise 5.3 for a carpenters’ ruler with link lengths L_{1} = 4, L_{2} = 4, L_{3} = 7, L_{4} = 3, L_{5} = 2. (Note that the rulers of Exercises 5.3 and 5.4 have the same link lengths, but these lengths occur in different orders.)

The folding method described in Exercise 5.3 works for any ruler, and it gives us an upper bound on the minimal folding length that depends only on the length of the longest link.

Theorem 5.1 If a carpenters’ ruler R has longest link length L_{M}, then the ruler can be folded with folding length less than twice L_{M}. [HJW85, page 316]

Proof (by induction on the number of links) Suppose that the ruler R has 1 link. Then, since L_{1} = L_{M} < 2L_{M}, the ruler is “folded” with folding length L < 2L_{M}.

Now let n ≥ 1, and suppose that every ruler of n links can be folded as required. Let R be a ruler of n + 1 links. Then the ruler R′ obtained by removing the last link from R can be folded with folding length < 2L′_{M}, where L′_{M} is the length of the longest link of R′. Then R′ is folded with folding length < 2L_{M}. Use this folding for the ruler R for all but the last joint angle, and choose the remaining joint angle (at J_{n}) to be 180^{∘} if the distance between the end J_{0} and the joint J_{n} ≤ L_{M} and to be 0^{∘} otherwise. Then R is folded with folding length < 2L_{M}. ♢

This theorem helps us to find a ruler’s minimum folding length because we know that we do not have to consider any folding length greater than or equal to 2L_{M}. This means that we have to consider only some of the possible ways of folding the ruler. The example below illustrates how these possible ways to fold can be organized in a tree structure.

Example 5.1 Suppose that a carpenters’ ruler R has link lengths L_{1} = 2, L_{2} = 3, L_{3} = 3, and L_{4} = 2. We know that the minimal folding length is less than 2L_{M} = 2 × 3 = 6. Thus, as we consider the joints in order, we can ignore any placement of a joint that guarantees a folding length greater than or equal to 6. We start building a tree of possible ways to fold the ruler by considering joint J_{0} placed at the number 0 on the real number line. We write (0, 0) at the root of the tree; the first 0 means that J_{0} is placed at 0, and the second 0 means that the folding length so far is 0. Next we place the joint J_{1} at 2 on the number line. Then, since J_{1} lies to the right of J_{0}, we write a right child (2, 2) of the root to construct the tree of Figure 5.3.

We continue to construct the tree with joint J_{2}, which may be placed either 3 units to the left of J_{1} or 3 units to the right of J_{1}. Figure 5.4 shows the tree with level 2 added.

Figure 5.4

The new positions are obtained by subtracting the link length 3 from the position of the joint J_{1} for the left child and by adding the link length 3 to the position of the joint J_{1} for the right child. We compute the folding length so far by looking at all the joint positions along the path from the root to the current node, and then subtracting the smallest number from the largest. For example, when constructing the left child at level 2, we consider the positions 0, 2, and −1, and we find the folding length so far to be 2 − (−1) = 3.

The complete tree is shown in Figure 5.5. We write no children when we would overstep or equal the upper bound of 6 on the minimum folding length of the ruler. At the next level, we get folding lengths 5 and 3 for the two possible angles at joint J_{1}. Then at the third level, we have to consider the four possibilities for the third link, which has length 1.

Figure 5.5

The tree in Figure 5.5 shows that there are 4 ways to fold the ruler to obtain folding length < 6 and that the minimal folding length is 3. Notice that this minimal folding length is obtained in only one way, when every joint angle is 180^{∘}. Other rulers can be folded in several different ways to obtain the minimum folding length.

Exercises

5.5 Sketch the tree diagram of Example 5.1 when the joint J_{1} is placed at the point −2 instead of at the point 2. Why do you obtain the same result?

5.6 Suppose that a 5-link ruler R has the same first four link lengths as the ruler of Example 5.1 and link length L_{5} = 3. Add the fifth level to the tree diagram of Figure 5.5. What is the minimal folding length of the ruler R?

5.7 Part of the tree diagram to determine minimal length of a carpenters’ ruler R is shown in Figure 5.6. Some information is given at every level of this tree.

a. How many links does the ruler R have?

b. What are R’s link lengths?

c. Complete the tree.

d. What is the minimal folding length of R?

e. List the joint angles that achieve this minimal folding length.

Figure 5.6

Now we know that any carpenters’ ruler can be folded with folding length < 2L_{M}. The next question to ask is whether or not we can find a better (a lower) upper bound on the minimal folding length. The next theorem states that 2L_{M} is a tight bound, i.e., the best there is. The next exercise illustrates the type of ruler defined in the proof of the theorem.

5.8 A 7-link carpenters’ ruler R has link lengths L_{1} = L_{3} = L_{5} = L_{7} = 1 and L_{2} = L_{4} = L_{6} = 0.99 so that all the links with odd subscripts have the same length, and all the links with even subscripts have the same somewhat shorter length.

a. Use a tree diagram to determine the minimal folding length of the ruler R.

b. What are the joint angles when the minimal folding length is achieved?

Theorem 5.2 The upper bound 2L_{M} on the minimal folding length of a carpenters’ ruler is tight, i.e., there is no smaller upper bound. [HJW85, page 317]

Proof Let L_{M} be a positive number. We want to consider the set of carpenters’ rulers with maximum link length equal to L_{M}. We ask ourselves if all these rulers have minimal folding length less than or equal to some number X, where X < 2L_{M}.

Suppose that the number X is a candidate for a smaller upper bound so that

L_{M} ≤ X < 2L_{M}.

Let Y be the average of X and 2L_{M}:

Y = \frac{X + 2L_{M}}{2}

Figure 5.7

We will construct a ruler that has maximum link length L_{M} and minimum folding length Y. Let k be the smallest integer that is ≥ \frac{L_{M}}{2L_{M} −Y} , i.e.,

k = ⌈\frac{L_{M}}{2L_{M} − Y} ⌉

Let n = 2k − 1. Consider an n-link carpenters’ ruler R with link lengths: L_{1} = L_{3} = … = L_{n} = L_{M} and L_{2} = L_{4} = … = L_{n−1} = Y − L_{M}.

The minimal folding length L is achieved when every joint angle is 0^{∘}. The first link has length L_{M}. If we go through the links in order after this first link, we can think of a link with an even subscript along with the next link. Figure 5.8 illustrates the first link as well as the pair composed of the second and third links.

Figure 5.8

We see that the pair of links increases the folded length so far by the difference of the link lengths:

L_{M} − (Y − L_{M}) = 2L_{M} − Y.

Since the first link has length L_{M} and since there are k − 1 pairs of other links, the minimal folding length is:

L_{M} + (k − 1)(2L_{M} − Y) = L_{M} + k(2L_{M} − Y) − (2L_{M} − Y)
= Y − L_{M} + ⌈\frac{L_{M}}{2L_{M} − Y} ⌉(2L_{M} − Y)
≥ Y − L_{M} + L_{M} = Y > X.

The carpenters’ ruler that we have described has minimal folding length > X. Thus X is not an upper bound on the set of minimal folding lengths. Therefore the upper bound 2L_{M} is tight. ♢

Problems

5.1 Suppose we consider only those rulers whose link lengths are integers. Is the upper bound 2L_{M} on the minimal folding length tight for these rulers? Justify your answer.

5.2 Describe the reachability region of a robot arm that is folded (in all possible ways), i.e., all the joint angles except the shoulder angle are constrained to be either 0^{∘} or 180^{∘}.

5.3 Suppose that a ruler R has integer link lengths 2L, L, L_{1}, L_{2},…,L_{n}, L, and 2L in that order, where L is the sum of the integers L_{1}, L_{2},…,L_{n}. Further assume that the ruler R can be folded with folding length 2L. Show that the integers L_{1}, L_{2},…,L_{n} can be placed in two sets so that the sum of the integers in one set equals the sum of integers in the other set. [HJW85, page 316]

References

[HJW84] Hopcroft, John; Joseph, Deborah; Whitesides, Sue. “Movement problems for 2dimensional linkages.” SIAM J. Computing 13(3), 1984, 610 - 629.

[HJW85] Hopcroft, John; Joseph, Deborah; Whitesides, Sue. “On the movement of robot arms in 2-dimensional bounded regions.” SIAM J. Computing 14(2), 1985, 315 - 333.

[K86] Kantabutra, V. “New Algorithms for Multilink Robot Arms.” Journal of Computer and System Sciences 32(1), 1986, 136 - 153.

[K92] Kantabutra, V. “Motions of a Short-Linked Robot Arm in a Square.” Discrete and Computational Geometry 7, 1992, 69 -76.

[OR] O’Rourke, Joseph. Computational Geometry in C, Second Edition. Cambridge University Press, 1998.

[SY] Suzuki, Ichiro; Yamashita, Masafumi. “Designing Multi-link Robot Arms in a Convex Polygon.” International Journal of Computational Geometry and Applications 6(4), 1996, 461 - 486.

[W] Whitesides, Sue. “Algorithmic issues in the geometry of planar linkages.” The Australian Computer Journal 24(2), 1992, 42 - 51.