Robot Arms and Linkages Tidbit (11/18/02)
Department of Mathematics and Computer Science
York College (CUNY)
Jamaica, New York 11451
Email: firstname.lastname@example.org (for additions, suggestions, and corrections)
One of the great adventures of the early 21st century is the International Space Station. This orbiting laboratory stocked with crews from all over the world and launched with American and Russian rockets may not be as flashy as the landing on the moon but it is no less exciting. One of the tools the astronauts use in putting together the station and carrying out the regular scientific experiments going on is a robotic arm provided by Canada. Robot arms are the mechanical equivalent of the human arm. When you or I want to get work done with our arm we just do it! But because robot arms are not volitional the movements that robot arms make must be programmed into the control mechanisms for the arms so that they can work effectively. What is the essence of an arm? It consists of rigid rods (bone equivalents) which are jointed so that they can move with respect to one another. We are on our way to thinking about arms, fingers, robot arms and windshield wipers in mathematical terms.
We will simplify and discover that even the simplest formulations lead to very great complexity. We will assume that we are given a collection of straight line segment rigid rods, confined to a plane but hinged at the points where the rods are connected so that they can move freely with respect to one-another. It is customary to refer to the rigid bars as links and the points where the bars are hinged as vertices. The whole structure is referred to as a linkage. The diagram below shows two simple examples, each consisting of two rods:
Imagine that we have a pen located at A3 and that A1 has been pinned. What are the points that the pen can reach so that they can paint those points in principle? To answer this question we can introduce a coordinate system with the origin at (0, 0) and given the lengths of the linkage rods we want to be able to compute the points that the pen attached to A3 can reach? To do this we need to be able to describe the position of A3 with respect to A2 and A1. One way to do this is to be able to us information about angles. If we adopt a convention about how to measure enough angles between the pinned vertex and the link arms perhaps we can describe the coordinate of the place where vertex A3 will be located.
If we measure angles as positive angles from the horizontal, we can for example describe the linkage in the diagram below:
Think of the point at the bottom being (0, 0) and the links have length 1 and 2. The end of the vertical link is at point (0, 1) and the end of the other link is at (, 1 +). Another approach to seeing what points are reachable using the linkage is to introduce coordinates based on the angles that the links make with the horizontal. Thus, for the linkage position above, the point (, 1 +) corresponds to the point (90º, 45º). Here we are using the convention that the angles are being measured from the horizontal direction. (It is in fact more common to use the angles between the links for all but the first link (which is measured with respect to the horizontal) because at the other vertices of the linkage being able to determine the angle with the horizonal is not that physically easy, but it is easy to measure the angle between the links.) One can construct formulas which tell one in terms of the angle coordinates the (x, y) coordinates. Note that though for a linkage with two links both coordinate systems have two coordinates, when one has a planar linkage of k links the angle representation requires k coordinates. Also, whereas the (x, y) coordinates describe a piece of a plane, the pair of angle coordinates for a linkage with 2 links describes a torus (donut), since each angle can go through a range of values from 0º to 360º. Another problem of interest to people studying robots is to know how to set the angles to get to a particular point. For example, what angles does one set the links at to reach the point (0, 3) or to reach the point (0, -1)? Using a bit of trigonometry one can answer these questions. Also, its convenient to use some simple ideas from linear algebra (matrix algebra) to think about such questions.
A very appealing and simple question concerning chain linkages is due to Sue Whitesides. Suppose one has a chain linkage with links of length 5, 3, 6, 4. What is the smallest case into which the linkage will fit after folding?
We will assume that links have zero height and will fold on top of each other. The general problem is to determine the smallest case for a general linkage.
The problem was originally chosen to be a simplified version of a motion planning problem for a robot arm, which took the form of a chain linkage.
This problem was solved by John Hopcroft, Deborah Joseph, and Sue Whitesides who showed that the problem was NP-complete. This means that the problem belongs to a class of problems whose computational complexity is ambiguous. On the one hand if any NP-complete problem could be solved in polynomial time then all NP-complete problems could be solved in polynomial time. On the other hand, if any NP-complete problem could be shown to require exponential time to solve then all NP-complete problems would also require exponential. Somewhat surprisingly, considering the broad nature and importance of the NP-complete problems, no one knows which of these two possibilities hold!
Straightening chain linkages and convexifying polygons
One of the simplest forms of linkage is a linkage which as a graph forms a path. An example is shown below:
A slightly more complex type of linkage is when the links form a polygon:
For these two particular linkages, it is clear how to manipulate the path linkage to be fully stretched along a straight line, and the polygon linkage to form a convex polygon (e.g. the internal angle between consecutive edges is at most 180º). However, is it clear how to straighten the path linkages below?
Similarly, it may not be clear how to convexify the polygon below:
In attempting to straighten a chain linkage or to convexify a polygonal linkage there are two different sets of rules that might apply:
a. Links are allowed to interpenetrate (even though this is not physically possible - mathematicians have an advantage over engineers!)
b. Links must never interpenetrate.
Not surprisingly, its much easier to work in the situation where links can interpenetrate. But what about the case where links are allowed to touch but not cross each other?
For nearly 30 years mathematicians were unsure of what the situation was in this case. However, in 2000, Robert Connelly (Cornell), Erik Demaine (MIT), and Günter Röte(Berlin) proved that every chain linkage could be straightened and every simple plane polygon could be convexified. Their proof used ideas from linear programming, differential equations, and rigidity theory. Furthermore, shortly thereafter, building on what they had done, Ileana Streinu (Smith College) provided a constructive approach to this problem. Her solution takes advantage of an interesting collection of combinatorial structures called pseudo-triangulations. Here is an example of a pseudo-triangulation.
Each internal face is a pseudo-triangle. A pseudo-triangle is a polygon which has exactly 3 convex vertices.
Alt, H. and C. Yap, Algorithmic aspects of motion planning: a tutorial, Part 1, Algorithms Review, 1 (1990) 43-60.
Alt, H. and C. Yap, Algorithmic aspects of motion planning: a tutorial, Part 2, Algorithms Review, 1 (1990) 61-78.
Biedl, T. and E. Demaine, M. Demaine, S. Lazard. A. Lubiw, J. O'Rourke, M Overmars, S. Robbins, I. Streinu, G. Toussaint, S. Whitesides, Locked and unlocked polygonal chains in 3d. Proc. 10th. ACM-SIAM Symposium on Discrete Algorithms, 1999, p. 866-867.
Borcea, C. and Il Streinu, On the number of embeddings of mini ally rigid graphs, preprint.
Bottema, O. and B. Roth, Theoretical Kinematics, Noth-Holland, Amsterdam, 1979.
Cayley, A. and S. Roberts, On three-bar motion, Proc. London Math. Soc., 7 (1876) 14.
Cayley, A. and S. Roberts, On three-bar motion, Proc. London Math. Soc. 7 (1876) 136.
Connelly, R. and E. Demaine, G. Rote, Straightening polygonal arcs and convexifying polygonal cycles, Discrete and Computational Geometry, to appear.
Connelly, R. and E. Demaine, G. Rote, Infinitesimally locked self-touching linkages with applications to locked trees, preprint.
Gibson,C.G., Marsh,D. and Xiang,Y. An Algorithm to Generate the Transition Curve of the Planar Four-bar Mechanism. Mechanism and Machine Theory. Vol. 31, No.4 (1996) 381--395.
Gibson,C.G. Elementary Geometry of Algebraic Curves, Cambridge University Press, London, 1998.
Graver, J., Rigidity matroids, SIAM J. Discrete Math., 4 (1991) 355-368.
Graver, J. and B. Servatius, H. Servatius, Combinatorial Rigidity, American Mathematical Society, Providence, 1993.
Graver, J., Counting on Frameworks, Mathematical Association of America, Washington, 2001.
Hartenberg, R. and J. Denavit, Kinematic Synthesis of Linkages, McGraw-Hill, New York, 1964.
Hopcroft, J. and D. Joseph, S. Whitesides, Movement problems for 2-dimensional linkages, SIAM J. Computing 13 (1984) 610-629.
Hopcroft, J. and D. Joseph, S. Whitesides, On the movement of robot arms in 2-dimensional bounded region, SIAM J. Computing 14 (1985) 315-333.
Hrones, J. and G. Nelson, Analysis of the Four-bar Linkage, Wiley, New York, 1951.
Jordan, D. and M. Steiner, Configuration spaces of mechanical linkages, Disc. and Comp. Geometry 22 (1999) 297-315.
Jordan, D. and M. Steiner, Compact surfaces as configuration spaces of mechanical linkages, Israel J. Math. 122 (2001) 175-187.
Joseph, D. and W. Plantinga, On the complexity of reachability and motion planning questions, Proc. 1st. ACM Symp. Comp. Geo., 1985, 315-333.
Kantabutra, V., Motions of a short-linked robot arm in a square, Discrete Comput. Geom. 7 (1992) 69-76.
Kantabutra, V. and S. Kosaraju, New algorithms for multilink robot arms, J. Comput. Sys. Sci., 32 (1986) 136-153.
Kapovich, M. and J. Millson, On the moduli space of polygons in the Euclidean plane, J. of Diff. Geo. 42 (1995) 133-164.
Kapovich, M. and J. Millson, Universality theorems for configuration spaces of planar linkages, preprint, 1998.
Kapovich, M. and J. Millson, Moduli spaces of linkages and arrangements, Advances in geometry, Progr. Math. 172, Birkhauser Boston, Boston, 1999, 237-270.
Kempe, A., How To Draw a Straight Line; A Lecture on Linkages, Macmillan, London, 1877.
King, H., Planar linkages and algebraic sets, Turkish J. Math. 23 (1999) 33-56.
Korein, J., A Geometric Investigation of Reach, MIT Press, Cambridge, 1985.
Laman, G., On graphs and rigid plane skeletal structures, J. Engineering Mathematics 4 (1970) 331-340.
LaTombe, J., Robot Motion Planning, Kluwer Publishers, 1991.
Lenhart, W. and S. Whitesides, Turning a polygon inside out, Proc. 3rd Canadian Conf. Comp. Geo., 1991, 66-69.
Lenhart, W. and S. Whitesides, Reconfiguring closed polygonal chains in Euclidean d-space, Disc. Comput. Geo. 13 (1995) 123-140.
Lenhart, W. and S. Whitesides, Reconfiguration using line tracking motions, Proc. 4th Canadian Conf. Compu. Geometry, 1992, 198-203.
Lovasz, L. and Y. Yemini, On generic rigidity in the plane, SIAM J. Alg. Disc. Methods 3 (1982) 91-98.
Mermoud, O. and M. Steiner, Visualization of configuration spaces of polygonal linkages, J. for Geo. and Graphics, 4 (2000) 147-157.
Moukarzerl, C. An efficient algorithm for testing the generic rigidity of graphs in the plane, Preprint.
Rademacher, H. and O. Toeplitz, The Enjoyment of Mathematics, Princeton U. Press, Princeton, 1957, Chapter 18, p. 119-129.
Raghavan, M. and B. Roth, Solving polynomial systems for the kinematic analysis and synthesis of mechanisms and robot manipulators, ASME J. Eng. Industry 85B (1995) 298-306.
Recski, A., Matroid Theory and its Applications in Electrical Theory and in Statics, Springer-Verlag, Berlin, 1989.
Roberts, S., On three-bar motion in plane space, Proc. London Math. Soc. 7 (1975) 14-23.
Schwartz, J. and C. Yap, eds., Algorithmic and Geometric Robotics, Erlbaum, Hillsdale, 1987.
Streinu, I., A combinatorial approach to planar non-colliding robot arm motion planning, Proceedings 41st Annual Symp. Foundations of Computer Science, IEEE Press, Washington, p. 353-370.
Suzuki, I. and M. Yamashita, Designing Multi-Link Robot Arms in a Convex Polygon, Technical Report TR-90-10-01, Department of Electrical Engineering and CS, U. Wisconsin-Milwaukee, 1991.
Toussaint, G., Simple proofs of a geometric property of four-bar linkages, preprint.
Van Kreveld, M. and J. Snoeyink, S. Whitesides, Folding rulers inside triangles, Proc. 5th Canadian Conf. Comp. Geo., Waterloo, 1993, 1-6.
Van Kreveld, J. Snoeyink, S. Whitesides, Folding Rulers Inside Triangles, Discrete Comput. Geom. 15 (1996) 265-285.
Wampler, C. and A. Morgan, A. Sommese, Complete solution of the nine-point path synthesis problem for four-bar linkages, ASME J. Mechanical Design 114 (1992) 153-159.
Whiteley, W., Motions and stresses of projected polyhedra, Structural Topology 7 (1982) 13-38.
Whiteley, W., Matroids and rigid structures, in Matroid Applications, N. White, (ed.), Encyclopedia of Mathematics and Its Applications, Cambridge U. Press, New York, 1992, p. 1-53.
Whiteley, W., Rigidity and polarity. I. Statics of sheet structures, Geometriae Dedicata 22 (1987) 329-362.
Whiteley, W., Infinitesimally rigid polyhedra. II. Modified spherical frameworks, Trans. AMS, 306 (1988) 115-139.
Whitesides, S., Algorithmic issues in the geometry of planar linkage movement, The Australian Computer J., Special Issue on Algorithms, May, 1992, p. 42-50.
Whitesides, S. and N. Pei, On the reconfiguration of chains, in Proceedings of COCOON, 96, Hong Kong, June, 1996, Lecture Notes in Computer Science, Volume 1090, J. Y. Cai and C. K. Kuen, eds., Springer-Verlag.
You may find this additional biblographic information about linkages and rigidity of interest: