New algorithms for multilink robot arms

of 18

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
18 pages
0 downs
New algorithms for multilink robot arms
  JOURNAL OF COMPUTER AND SYSTEM SCIENCES 32, 136153 (1986) New Algorithms for Multilink Robot Arms* V. KANTABUTRA~ AND S. R. KOSARAJU Department of Electrical Engineering and Computer Science, The Johns Hopkins University, Baltimore, Maryland 21218 Received May 14, 1985; revised July 8, 1985 Problems related to the movement of n-link robot arms in two dimensions are considered. We present an algorithm, requiring O(n) computation time, which moves an arm confined in a circular region to any reachable configuration in O(n) moves. Also given is an O(n) com- putation time algorithm that computes all the regions reachable by the joints of such an arm. These results are improvements over the cubic algorithms of Hopcroft, Joseph, and Whitesides (SIAM J. Comput. 14, No. 2 (1985)). We finally show how to plan motion involv- ing the minimum number of moves for an arm in the obstacle-free plane in O(n3) com- putational steps. @’ 1986 Academic Press, Inc 1. INTRODUCTION Two problems of interest in the areas of industrial automation and robotics are the mover’s problem and motion planning. In the mover’s problem, we decide whether an object can be moved from one position in space to another, subject to various constraints. In motion planning, the goal is to plan a feasible, and perhaps optimal, course of motion for the moving object. It was shown in [S] that the mover’s problem for a simple, tree-like hinged object moving in a system of tunnels in 3-dimensional space is PSPACE-complete. In [Z], the PSPACE-hardness of the reachability decision for a joint of a linkage in the unobstructed plane was demonstrated. The NP-hardness of the mover’s problem for a multilink robot arm in a planar region with simple, rectilinear obstacles was shown in [3]. A general algorithm for the Mover’s problem and motion planning was given in [6] for multiple objects moving in multidimensional space, obstructed by various walls. Here the moving objects can be arbitrarily linked together. The time com- plexity, although polynomial in the total number of faces of the walls and of the mving objects, is exponential in the number of degrees of freedom of the system. Researchers then seek for classes of motion problems for which the complexity is a polynomial in the number of degrees of freedom. The movement of multilink robot arms was first investigated in [l, 31. Algorithms were given for an n-link robot arm confined in a circular region of the plane. First, it was shown that the * Supported by NSF Grants DCR-8205167 and DCR-8506361. + Current address: Department of Mathematics and Computer Science, Drexel University, Philadelphia, Pennsylvania 19 104. 136 0022-WOO/86 3.00 Copyright 0 1986 by Academic Press, Inc. All rights of reproduction m any lorm reserved.  MULTILINKROBOTARMS 137 mover’s problem is decidable in O(n) time. An algorithm was then given that plans the motion in O(n3) time, resulting in O(n3) arm moves. Calculating all the regions reachable by the joints of the arm was proven to take polynomial time. A polynomial time algorithm, which is at least quadratic and at most cubic, was presented for the purpose. In addition, if the final position of a joint is given, then in O(n2) steps they can decide if that point can be reached, and compute a reachable arm configuration with the designated joint at the point. In this paper we continue the study of n-link robot arms. For an arm in a circle, we present a motion planning algorithm that runs in O(n) computation time and produces only O(n) moves. Also to be given is a linear-time algorithm that com- putes all the reachable regions of the joints. The latter procedure is then applied to the problem of computing a reachable final configuration in which any subset of joints rest at specified points. This computation is also performed in linear time. All these results appear in Sections 2 and 3. Section 4 deals with the planning of minimal moves of a robot arm in the unobstructed plane, so that the hand reaches a specified point. The number of joint angles that must change is minimized. We show how such scheduling can be done in O(n3) steps. 2. CHANGING ARM CONFIGURATION IN A CIRCLE Here an algorithm that reconfigures a robot arm confined within a circle is developed. The complexity of this algorithm is O(n) computation time and O(n) arm moves. First, some definitions are necessary. An arm (Fig. 2.1) is a sequence of n straight line segments or links of arbitrary finite lengths moving in the euclidean plane. These links are joined end-to-end by freely rotating joints. One end of the arm, the shoulder, is fixed positionwise, but can rotate freely. The other end is called the hand. The joints (including the shoulder and the hand) are denoted by A,, A, ,..., A,. The link between Ai- i and A, is denoted by Li, and its length by Ii. The joint angle at A,, i > 0, is the angle between the links L, and L,, , , and the joint angle at A0 is the angle that L, makes with the horizontal. Every joint of the arm is constrained to be within the region bounded by a circle, C, at all times. The center and the radius of C are denoted by 0 and r, A, (hand) A, (shoulder) FIGURE 2.1  138 KANTABUTRA AND KOSARAJU respectively. A configuration of *an arm is given by the positions of all its joints. Given any initial configuration r,,, a final configuration r, is reachable if there is a way to move the arm to T’ allowing all joint angles to move simultaneously, with arbitrary relationships among the angular rates of change. A unit of arm move, however, is restricted to be any continuous motion in which at most four joint angles change simultaneously, each one monotonely. It was shown in [3] that this definition does not affect the set of reachable configurations. An arm is in normal form if every joint lies as close to C as possible (Fig. 2.2). Let the tail from joint Ai be the part of the arm from A i to A,. This tail is in normal form if the “subarm” A;,..., A, is in normal form. The link Li is of left (right) orien- tation if the center of C lies to the left (to the right) of the Ai to Ai- , line. If Li lies on any diameter of C then L, is of both (left and right) orientations. To reorient link Lj means to move the arm so that this link begins to assume the orientation which is not its present one. In other words, to reorient Li means to move the arm to any configuration in which that link lies on a diameter of C. A link is said to be reorientable if it can be reoriented. The numbers ci and d, denote the minimum and the maximum distances from C that A, can be moved to, respectively. The computation of all the c;s and the d,‘s was shown in [3] to take O(n) time. In [3], it was shown that the reorientability of each link for which the orien- tations in r, and in f,. differ is a necessary and sufficient condition for the reachability of Tr. from f,. It was also demonstrated that the test for the reorien- tability of each link can be performed in constant time after the cI)s and the d,‘s have been computed. It follows that the reachability of r,. can be decided in O(n) time. FIGURE 2.2  MULTILINK ROBOT ARMS 139 The following property was also established: LEMMA 2.1 [3]. Let the arm be in any configuration. The joint A,,, can be moved without obstruction caused by its tail, as long as the distance between A,,, and C remains within the range [c,, d,,,]. Th is motion may require manipulation of the tail. However, if the tail is in normal form, then it can be kept in normal form for the entire duration of the motion. The reversal of any move is the same motion backwards, and the reversal of a sequence of moves M, ,..., Mk is the sequence Mf ,..., MP, where Mf denotes the reversal of the move Mi. We permit the following type of modification of the rever- sal [3]: During the forward sequence of moves, suppose certain links each aligns itself with a diameter of C. Then during the reversal, the members of any subset of those links can each be forced to have the orientation which is opposite to the orientation it had before the forward moves. We do this by forcing the angle that such a link L, makes with the diameter through Ai_ 1 after Li comes to such diameter to be the exact opposite (negative) of the corresponding angle made dur- ing the forward motion. An Outline of the Arm Reconfiguration Algorithm in [3] This algorithm is iterative, in that the arm’s joints are brought one by one, in ascending order of their indices, to their final positions. First we note that since A, is fixed, its initial and its final positions coincide. Now assume that A,, A*,..., Ai have been brought to their final positions. At this stage if Lis orientation differs from its final orientation, then that link can be reoriented in O(n*) arm moves. In another O(n2) moves, the arm can be brought to a new configuration in which Li assumes its final orientation and in which the positions of the joints A,, A2,..., AiP 1 are restored. (Some of these joints may have lost their positions in the process of reorienting Li.) Now with Ai-, fixed, the tail of the arm from Ai can be moved so that Aj comes to its final position, using O(n) arm moves. This algorithm requires O(n3) computation time and O(n’) arm moves. Development of a Linear Algorithm for Arm Reconfiguration The general approach to fast arm reconfiguration is to allow the links for which the orientations in r, and T’ differ to be reoriented in groups instead of individually. Note that A,, can be assumed not to lie at the center, 0, of C, since if A0 does lie at 0, then we can begin the arm reconfiguration by rotating it around A0 until A, comes to its final position. Thereafter, the tail from A, can be considered as an (n - l)-link robot arm to be reconfigured, with the shoulder, A,, not lying at 0.’ ’ That Al need not be moved during the remaining arm motion follows from the symmetry of the cir- cle C. 571/32/l-10  140 KANTABUTRAAND KOSARAJU ALGORITHM 2.1. Moving an arm in a circle from r,, to a reachable con- figuration, Tr: Step 1. Using the algorithm of [3], move the arm from r, to normal form, and denote this normal form by r,. Applying the same algorithm, calculate the sequence of moves needed to reach normal form from r,., and let this normal form be called rn. Step 2. Bring the arm from I-,, to r:,. Step 3. Using the reversal of the sequence of moves needed from T, to r;, move the arm to r,.. Now we develop the details of Step 2. Let .Y = {Li 1 Lis orientation in r, and r, differ}. One way to change r, to r, is to bring each link in 9 to a diameter and reverse its orientation by applying the moves in reverse, suitably modified. This could require O(n) moves for each link in 9, resulting in 0(n2) moves. We improve this by calculating a suitable subset of 9 such that when we successively bring the links of this subset to some suitable diameters, every member of 9 comes to a diameter at least once, but no more than twice. Now let us investigate how a link L, in any subset of 9 can be brought to a diameter. For r, to be reachable from r,, L, must be reorientable, which implies: LEMMA 2.2. For every Li in 9, there exist numbers Xi- I and xi such that (i) ci-l<xi-l<di-1, ci < xi 6 di, and (ii) 2r - xi- 1 xi = li or Ixi- 1 xi1 = Ii. LEMMA 2.3. Suppose we are given any Li in 9 and xi-, , xi satisfying conditions (i) and (ii) of Lemma 2.2. Whenever Ai-, and A, lie at distances x, ~, and xi from C, respectively, Li must lie on a diameter. ProoJ: Elementary argument concerning the length of L,. 1 By Lemma 2.3 we can bring L, to a diameter if we can bring Ai-, and Aj to such distances xi- i and xi, respectively, from C. Let r, denote such a configuration. In r, we will also require that for any j< i- 1, Ais distance from C is di(Aj)=max{ci, d(A,+,)- lj+,}, and for any j> i, that distance Ai is max{O, di(Ajp,)-Zj}. It can be shown that every joint will lie at a distance between ci and dj from C (inclusive of the two extreme distances). When the joints are at such distances from C, certain links adjacent to Li will be on a diameter (Fig. 2.3). Those indexed lower than and greater than i will be called the front and the back covers (F, and Bi) of Li, respectively. The back cover of L, can be thought of as those links that lie on a diameter when the tail from Ai is in normal form. The front cover of Li, except for some cases in which i- 1 is near zero, is intuitively the diametrically aligned links in the “backward tail of Ai-, in normal form,” where the backward tail refers to the links between Ajp, and A,,. It was shown in [3] how to compute x, _ i and xi for each i in constant time, given ciPl, dipI, c,, and di. We will see later on that computing all the necessary
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks