Closed form forward kinematics solution to a class of hexapod robots

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 14, NO. 3, JUNE 1998 503 shape and the relative costs with respect to its surrounding regions. The decision algorithm presented here works only for convex objects, but it is hoped that an algorithmic solution in the general nonconvex case can be found soon. Even otherwise, an approach based on Genetic Algorithms has been outlined which will work in practice, but the population size and chromosome lengths may be dauntingly large for complex workspaces. As conjectured earlier, this problem may be solvable algorithmically by generating further local minima candidates at the reflex vertices. What if some regions have finite cost, and some are perfect obsta- cles? This problem has been handled by discrete wave-propagation (grid-based) and by continuum methods, which appear to be better both in the quality of the path generated, and also from a compu- tational point of view, especially in more complex scenarios [2]. However, since the refracted rays repeatedly fragment at each cost- transition, the algorithm is exponential in the number of such cost gradations. Thus, whenever possible, it becomes computationally meaningful to adopt the perfect obstacle assumption, and the Ob- stacleness measure outlined above provides a quick measure for the validity of this assumption. Furthermore, as illustrated in the watery patch example of Section I, the algorithmic method presented here, or similar approaches, may be programmed directly as a visual behavior, so that the perfectness of the obstacle can be computed directly in the image space itself. As we progressed in this work, we realized that this approach opens up a host of options for investigating more general path planning problems. An important efficiency issue in terrain navigation is the extent to which imperfect “obstacleness” can be accommodated by perturbations in the path found by the perfect-obstacle assumption—a first round path skirts all obstacles; subsequently, some of the path segments can be perturbed to go through the low-obstaclehood obstacles. In potential field models of robot navigation, the cost of the field can be adjusted based on the degree of “obstacleness,” and in partially sensed domains, a cost of sensing can be combined with the best expected cost and factored into the field strength. Also, it may be a good heuristic to model nearly perfect obstacles as perfect when the path to it starts some distance from the boundary. ACKNOWLEDGMENT The authors would like to thank K. Deb, Department of Mechanical Engineering, IIT Kanpur, for discussions about the genetic algorithms which form the basis of the continuous domain GA model [7]. REFERENCES [1] J. C. Latombe, Robot Motion Planning. Boston, MA: Kluwer, 1991. [2] N. C. Rowe and R. F. Richbourg, “An efficient Snell’s Law method for optimal-path planning across multiple two-dimensional, irregular, homogeneous-cost regions,” Int. J. Robot. Res., vol. 9, no. 6, pp. 48–66, 1990. [3] J. S. B. Mitchell, “An algorithmic approach to some problems in terrain navigation,” Artif. Intell., vol. 37, pp. 171–201, 1988. [4] N. C. Rowe and R. S. Ross, “Optimal grid-free path planning across arbitrarily-contoured terrain with anisotropic friction and gravity ef- fects,” IEEE Trans. Robot. Automat., vol. 6, pp. 540–553, 1987. [5] S. P. Sharma, “Aspects of path planning with Snell’s Law,” M.Tech. thesis, Ctr. Robotics, Indian Inst. Technol., Kanpur, 1994. [6] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Ma- chine Learning. Reading, MA: Addison-Wesley, 1989, p. 412. [7] K. Deb and R. B. Agrawal, “Simulated binary cross-over for continuous search space,” Complex Syst., vol. 9, pp. 15–148, 1998. Closed Form Forward Kinematics Solution to a Class of Hexapod Robots Jun Yang and Z. Jason Geng Abstract—We present a class of hexapod robots for which we are able to provide true closed-form (non-numerical) solutions. The class studied in the paper is close to being a general hexapod robot and its engineering implementation can be carried out without any problem. Our method has been implemented using Maple. The algorithm of our methods is very simple and therefore suitable for real time applications. Another interesting result that comes out of our study is that we proved mathematically that the number of distinct physically possible solutions for the class we considered is at most eight for a given set of leg lengths. This represents the first time such an assertion is proved in the literature. Index Terms—Design constraints, linearly related Stewart platform, relation matrix, Stewart platform, structure coefficient matrix. I. INTRODUCTION In past decade, hexapod robots, often called the Stewart Platforms after the original inventor [8], have received increasing attention due to their inherent advantages over conventional serial mechanism. A hexapod consists of six legs connecting a fixed base plate to a mobile plate. A typical hexapod mechanism is shown in Fig. 1. By changing the length of the six legs, the pose of the mobile plate can be moved in all six degrees of freedom (DoF) with respect to the base plate. Kinematically the legs function in parallel, so the structure is also known as a parallel link manipulator. It can be proven that regardless of the load on the mobile plate, all the forces which act on the legs must be axial forces. Since steel is much stiffer to compression and tension forces than to bending forces, a hexapod is very strong compared to conventional serial link robots where all the forces on the robot’s end effector act to twist and bend the robot’s arms. A wide variety of practical applications have been developed using such parallel link mechanisms. Examples of these applications are a new generation of machine tools (such as the Octahedral-Hexapod 6 Axis Milling Machine from Ingosell, IL, and the VARIAX of Giddings and Lewis, Inc.), dexterous surgery robot for medical ap- plication, 6 DoF dimensional measurement device for manufacturing processes, and a six DoF active vibration control system developed for NASA Large Space Structure. The mechanical simplicity of a hexapod mechanism provides great engineering application potentials for realizing six DoF positioning capacity using six single DoF linear motors. However, the “price” of the mechanical simplicity of a hexapod is that the kinematics of the platform are mathematically complex, especially when dealing with the forward kinematics. The forward kinematics problem of hexapod robots is the problem of calculating the position of the mobile plate with respect to the base plate for any given set of values of six leg lengths of the hexapod. To date, there exists few practical closed-form mathematical formula in the literature that allows us to calculate the position and the orientation of the mobile plate of the hexapod. As a result of the Manuscript received February 13, 1996; revised September 23, 1996. This work was supported in part by NSF Grant DMS-9401411. This paper was recommended for publication by Associate Editor Y. F. Zheng and Editor S. Salcudean upon evaluation of the reviewers’ comments. J. Yang is with the Department of Mathematics, Duke University, Durham, NC 27707 USA. Z. J. Geng is with Genex Technologies, Inc., Rockville, MD 20852 USA. Publisher Item Identifier S 1042-296X(98)03566-6. 1042–296X/98$10.00  1998 IEEE 504 IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 14, NO. 3, JUNE 1998 Fig. 1. A hexapod robot (Stewart platform). lack of closed-form solution, numerical iterative procedures must be used in many engineering applications. Not only are the iterative algorithms computationally expensive, but also there is no guarantee that a correct solution can be found. In addition, the number of iterations needed for the numerical procedures cannot be determined a priori, therefore the computational time of forward kinematics (FK) solution is unpredictable. The mathematical complexity of the forward kinematics of hexapods is a serious deficiency that prevents hexapod systems from being used for many high speed and real-time engineering applications. In this paper, we will provide a closed-form FK solution to a class of hexapods. We do not foresee any difficulty in the engineering implementation of this class of hexapods. We will also prove math- ematically that for the class of hexapods studied in this paper, there can be at most eight sets of solutions for a given set of leg lengths. We believe such results were never obtained before in the literature. In Section II, we review some background materials on the FK problem of Stewart platforms and make a brief survey of the current state of the problem. Section III is the main part of the paper. In which we detail our solution of what we call linearly related Stewart platforms. In Section IV, we present a practical example that can be solved using our method. In Section III-A, we define the linearly related Stewart platforms, and in Section III-B we sketch our method of solution. Readers who are not interested in details can move on to Section IV to see the example. More details of solutions are presented in Section III-C. Mathematical discussion of the number of possible real solutions of our configuration is made in Section III-D. We believe the number of solutions to a hexapod problem is both theoretically interesting and practically useful. In real world applications, only one set of solutions out of all mathematically possible real solutions is the correct one. It is important to know in advance how many solutions there are from which one practical solution will be chosen. A discussion of the situations when linearly related platforms are geometrically singular is made in Section III-E. The result is also interesting in its own right in understanding geometric singularities in Stewart platforms. A discussion of the complexity of our algorithm is made in Section III-F. II. BACKGROUND In this section, we make a brief survey on the state of the art of current researches on the FK problem of Stewart platforms. First we introduce some notations and definitions which will be used throughout the paper. We want to emphasize one important convention used throughout this paper, bold face letters are reserved exclusively for vectors. Let A i and B i , i = 0; � � � ; 5, denote the attachment points of the legs to the mobile and base plates, respectively (see Fig. 1). Denote by L i the leg vector from B i to A i . Let l i = kL i k; i = 0; 1; � � � ; 5 denote the lengths of the leg vectors. To determine the pose of the mobile plate at any given time, it suffices to find the coordinate (x; y; z) of the origin of the mobile frame with respect to the fixed base frame and the rotating angles of the mobile frame with respect to the fixed frame, i.e., the yaw, pitch, and roll, denoted by �; �; , respectively. A. Inverse Kinematics Fix a base coordinate frame XY Z. Put a moving xyz-frame on the mobile plate (see Fig. 1). Let R be the 3 � 3 rotation matrix R, which defines the rotating angles of the mobile frame xyz with respect to the fixed frame XY Z and let p be the displacement vector p of the frame xyz with respect to the frame XY Z. The problem of inverse kinematics of a hexapod (Stewart platform) is to find the lengths l i , i = 0; 1; � � � ; 5, of the six legs of the hexapod, knowing the coordinates of the attachment points of the legs on the base plate B i = (b x; i ; b y; i ; b z; i ) T with respect toXY Z and the coordinates of the attachment points of the legs on the mobile plate A i with respect to xyz. The inverse kinematics solution for Stewart platform type of parallel link robotic manipulator is quite straightforward. Given R and p, the leg vector can be computed by the formulas L i = RA i + p�B i (1) and the length of the legs then follow easily. B. Forward Kinematics and Conventional Iterative Solution The forward kinematics problem involves solving six simulta- neous nonlinear equations for the values of the six unknowns x; y; z; �; �; which define the pose of the mobile plate. Conventional iterative solution of the forward kinematics exploits the Newton–Raphson method. With the Newton–Raphson method, a set of functions f i (q) is defined via f i (q) = [R(q)A i + p(q)�B i ] T [R(q)A i + p(q)�B i ]� l 2 i (2) for i = 0; � � � ; 5, where q is a vector containing the estimated values of the mobile plate position, i.e., x; y; z; �; �; . The iterative algorithm requires computing the leg lengths using the inverse transform for an estimate of the platform position. Then the estimated leg lengths are subtracted from the measured leg lengths, and this function will approach zero as the estimate of the platform position improves. The next estimate of the platform position is determined using the matrix of partial derivatives or the Jacobian. The iteration formula is q n+1 = q n � df(q n ) dq n �1 f(q n ): (3) Substituting (2) into (3) and performing the vector multiplication results in the equation for f i (q), while differentiating yields the values of df(q n )=d(q n ). Using the Gauss–Jordan technique, the need to compute the inverse is eliminated, and the resulting change to q n is computed directly. The algorithm is run until the error between any of the leg lengths computed using the estimated platform position and the measured leg lengths is smaller than a given error bound. The advantage of iterative procedures is that it is simple to apply, and is applicable to any type of hexapod configuration, whereas the disadvantage is that there is no guarantee the solutions can always be found. The computation time needed for finding solutions using the iterative methods is usually unpredictable. IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 14, NO. 3, JUNE 1998 505 C. Survey of State-of-the-Art The derivation of currently available methods for closed-form FK solutions is to apply different elimination procedures to eliminate the unknowns from a set of constraint equations and to form one polynomial with a single unknown. The advantages of this type of methods are: 1) all possible solutions can be found; 2) the effects of input error on the output link can be quantified; 3) problems near singularities can be avoided. The disadvantages are: 1) the elimination procedure is very complicated, which usually introduces spurious roots; 2) most methods lead to polynomials of degree 8 or higher. Since no general formulas exist for high degree polynomials, in order to find the roots, one is forced to employ numerical methods. However, the root finding procedure of polynomials is very sensitive to numerical precision, especially for high order polynomials. Geng et al. [2] derived a set of formula that allow direct calculation of the FK for a special configuration, i.e., the 3-2-1 configuration of a hexapod, where the attachment points of three legs meet at one point on the mobile plate, while the attachment point of other two legs meet on another point on the mobile plate, the attachment point of the last leg is arbitrary. The speed of this algorithm is about 100 times faster than the Newton–Raphson algorithm. Griffis and Duffy [4] and Nanua et al. [6] studied the forward kinematics of a special case of hexapod configuration and obtained an eighth degree polynomial in the square form of a single variable. Geng et al. [3] studied the FK problem for a hexapod configuration where six legs form three pairs with the attachment points of the paired legs coincident on the mobile plate. The attachment points on the base can be noncoplanar. A sixteenth degree polynomial was obtained. And an eighth order polynomial can be derived for the simple case where attachment points on the base are coplanar. Lin et al. [5] considered the FK of a 4-4 hexapod which has two pairs of joint meet in both the base and the mobile plates. They obtained an eighth order and a twelfth order polynomials for different cases. Zhang and Song [9] showed that analytical closed-form FK solutions are available if the following condition is satisfied: one rotational degree of freedom of the moving link is decoupled from the other five. We refer to this as the 5-1 configuration. Recently, Zhang and Song [10] derived a closed-form FK solution for a near general hexapod. A near general hexapod is the one such that the attachment points are assumed to the co-planar for both mobile plate and base, respectively. They obtained a set of 21 equations in terms of three unknowns. By simultaneous elimination of two unknowns, they obtained a twentieth order polynomial with one unknown. Cheok [1] studied a method of obtaining closed-form FK solution by adding additional passive leg to a hexapod. Using the leg length information of the additional leg, the calculation of FK can be greatly simplified, and the solution can be obtained in closed form. However, adding additional sensor device to a hexapod will increase the cost and complexity of the hardware system. Nguyen [7] investigated an Newton–Raphson based FK method and applied it to adaptive control of a Stewart Platform-based manipulator. Among aforementioned FK methods, only two provide true closed-form (nonnumerical) solutions without adding additional sensors: the 3-2-1 configuration by Geng [2], and the 5-1 configu- ration by Zhang [9]. The others only offer a conversion of the FK problem into a high order polynomial to which the solutions need to be found numerically. They are not true closed-form solutions. The second author of this paper developed the 3-2-1 configuration primarily for using a hexapod as a six DoF measurement device where six strings were used instead of rigid legs. The mechanical design for connecting three strings together is simple. However, it is difficult to design a joint that connects three rigid legs concentrically while preserving the required rotational degrees of freedom and rigidity. The second case, the 5-1 configuration leads to an asymmetrical shape of the mobile plate and introduces many undesirable structural design features. In contrast, the class of hexapods to be presented in next section is not only engineering implementable but also has much better symmetry property than 5-1 configuration. III. CLOSE SOLUTIONS OF LINEARLY RELATED STEWART PLATFORMS We have been able to obtain close solutions for a practical class of the Stewart Platform, which will be called the linearly related platform in the sequel. A. Linearly Related Stewart Platforms Recall from Fig. 1, A i ; B i , i = 0; � � � ; 5 are the attachment points for the plates (cf., Section II). Let A i and B i denote the vectors A 0 A i and B 0 B i , respectively, for i = 1; � � � ; 5. We will avoid using coordinate frame as much as possible. However, if one is more comfortable working with coordinates, the vectors A i and B i can be viewed as having coordinates in the XY Z-frame. Note here the B i ’s are fixed vectors, but the A i ’s are moving vectors, depending on the position of the mobile plate, one could for example think of A i ’s as functions of time. We call the Stewart Platform linearly related if there exists a 3 � 3 matrix M such that MB i = A i (4) for i = 1; 2; � � � ; 5 at any one position of the mobile plate. Such a matrix M will be called a relation matrix of the Stewart Platform in the sequel. Since the top and bottom plates will be nondegenerate hexagons, the relation matrix will be of rank at least 2, which is the only condition of the matrix. Of course the existence of such a matrix does not depend on the position of the mobile plate, rather it depends on the relative shape of the base and mobile plates. In particular, if the base and mobile plates are identical in shape (but may differ in size), then the Stewart Platform is linearly related. B. The Sketch of Solutions We assume our plates are nondegenerate hexagons. We can use B 1 and B 2 as a basis for vectors on the base plate. Similarly, we can use A 1 and A 2 as a basis for vectors on the mobile plate. It is obvious from Fig. 1 that we have A i = �L 0 +B i + L i ; i = 1; � � � ; 5: (5) Since B 1 and B 2 form a basis for vectors on the base plate, we have constants � i ’s and � i ’s for i = 3; 4; 5 such that B i = � i B 1 + � i B 2 ; i = 3; 4; 5: (6) We will call these � i ; � i the design constants of the Stewart Platform. Because of (4), these same � i ’s and � i ’s also work for A i ’s, i.e., A i = � i A 1 + � i A 2 ; i = 3; 4; 5: (7) Substitute (5) into the above equations, we get for i = 3; 4; 5 �L 0 +B i + L i =� i (�L 0 +B 1 + L 1 ) + � i (�L 0 +B 2 + L 2 ): (8) From (6), all B i ’s in the above equations cancel one another, and we can rewrite the above equations as (1� � i � � i )L 0 + � i L 1 + � i L 2 = L i ; i = 3; 4; 5: (9) 506 IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 14, NO. 3, JUNE 1998 We square both sides (dot products) of the above equations. Since the lengths of all the vectors involved are known, we obtain three linear equations of the dot products L 0 � L 1 ; L 1 � L 2 ; L 0 � L 2 . In the generic case, one is able to solve this system of three linear equations. So the special condition satisfied by the linearly related Stewart Platform has enabled us to translate the lengths of the six legs into the lengths of three legs L 0 ; L 1 , and L 2 and the three dot products among them. Altogether they give 6 quadratic equations of the 9 coordinates of L 0 ; L 1 and L 2 . The remained three equations needed to solve the nine coordinates come from the lengths of A 1 ; A 2 , and A 1 �A 2 . We have �L 0 +B 1 + L 1 =A 1 (10) �L 0 +B 2 + L 2 =A 2 (11) �L 1 �B 1 +B 2 + L 2 = �A 1 +A 2 : (12) We set N 1 = L 1 � L 0 and N 2 = L 2 � L 0 . Again square both sides of these equations, we find the following three linear equations involving N 1 and N 2 N 1 �B 1 =C 1 (13) N 2 �B 2 =C 2 (14) N 1 �B 2 +N 2 �B 1 =C 3 : (15) Together with the three nonlinear quadratic equations kN 1 k 2 = N 1 ; kN 2 k 2 = N 2 ; N 1 �N 2 = N 3 ; (16) we can reduce the problem to a system of three quadratic equations on three unknowns. After cancellation and appropriate substitution, we end up with a quartic algebraic equation of one unknown, which of course is solvable. The whole procedure is remarkably simple and its implementation on computers can be easily carried out. C. Further Details From now on, we will be using a fixed coordinate frame centered at B 0 and so positioned such that B 1 = a 1 i and B 2 = a 2 i+ b 2 j; b 2 6= 0. Let N 1 = u 1 i+ v 1 j+w 1 k and N 2 = u 2 i+ v 2 j+w 2 k. The six equations we obtained above can then be written as u 2 1 + v 2 1 + w 2 1 =N 1 (17) u 2 2 + v 2 2 + w 2 2 =N 2 (18) u 1 u 2 + v 1 v 2 + w 1 w 2 =N 3 (19) a 1 u 1 =C 1 (20) a 2 u 2 + b 2 v 2 =C 2 (21) a 1 u 2 + a 2 u 1 + b 2 v 1 =C 3 : (22) Eliminating the three variables u 1 ; v 1 ; v 2 , we get the following three quadratic equations on u 2 ; w 1 , and w 2 K 1 u 2 2 +K 2 u 2 + w 2 1 =D 1 (23) K 3 u 2 2 +K 4 u 2 + w 2 2 =D 2 (24) K 5 u 2 2 +K 6 u 2 + w 1 w 2 =D 3 (25) or K 1 u 2 2 +K 2 u 2 �D 1 = � w 2 1 (26) K 3 u 2 2 +K 4 u 2 �D 2 = � w 2 2 (27) K 5 u 2 2 +K 6 u 2 �D 3 = � w 1 w 2 (28) where K i ’s and D i ’s are numbers depending on N i ’s and a i ; b i ’s. Their exact formulas are irrelevant to our discussions in this subsec- tion. For later reference, the exact formulas are given in the Appendix. In the above system of equations, the multiplication of the first two is equal to the square of the last one. So finally, we obtain a degree 4 equation for u 2 as (K 5 u 2 2 +K 6 u 2 �D 3 ) 2 = (K 1 u 2 2 +K 2 u 2 �D 1 )(K 3 u 2 2 +K 4 u 2 �D 2 ): (29) Given u 2 , w 1 and w 2 are determined up to signs. Since w 1 w 2 is determined by u 2 , the sign of w 1 determines the sign of w 2 and vice versa. Therefore, for a fixed u 2 , there are two sets of (w 1 ; w 2 ) which are the negative of each other. It is obvious that geometrically, these give two sets of solutions which are reflections of each other with respect to the XY -plane. So for each u 2 , it suffices to understand one set of w 1 and w 2 . In general we will have eight sets of solutions forN 1 andN 2 . The vectors N 1 and N 2 determine the rotational matrix R completely, or equivalently, all the vectors A i ’s. So it remains to find one leg vector, say L 0 . KnowingN 1 andN 2 together with their dot products with L 0 , denoted by S 1 and S 2 , respectively, gives us the following two linear equations involving L 0 : L 0 �N 1 = S 1 ; L 0 �N 2 = S 2 : (30) Together with the length equation of L 0 , we can solve L 0 quickly which in general should yield two sets of solutions. Once L 0 is determined, using A i ’s and B i ’s, one finds the rest of L i ’s via L i = �B i + L 0 +A i ; i = 1; � � � ; 5: (31) Hence altogether there should be 16 sets of mathematically possible solutions for our systems of equations. However, as we will show next, only eight physically possible configurations will come out of these equations. D. Number of Solutions Assume (29) has four real solutions for u 2 . If not, then at least two of them are imaginary, so clearly there can be at most eight sets of real solutions. For simplicity, write P 1 =K 1 u 2 2 +K 2 u 2 �D 1 (32) P 2 =K 3 u 2 2 +K 4 u 2 �D 2 (33) P 3 =K 5 u 2 2 +K 6 u 2 �D 3 (34) P =P 1 P 2 � P 2 3 : (35) Equation (29) is equivalent to P = 0. Note that P 1 and P 2 are quadratic polynomials in u 2 with positive leading coefficients (see the Appendix for the value of K 1 and K 3 ). Hence each either has two real roots or are strictly positive. From (26), it is clear that a positive P 1 would lead to imaginary solution for w 1 . Similarly for P 2 . So in order for the system of equations to have real solutions, we need to assume both P 1 and P 2 have real roots. Let r 1 and r 2 , respectively, denote the minimum and the maximum of the roots of P 1 and P 2 . We claim that the equation P = 0 has one real solution in each of the two intervals [�1; r 1 ] and [r 2 ; 1]. Indeed, by our assumption P (r 1 ) � 0. Since the leading coefficient of P is equal to a 2 1 (a 2 2 + b 2 2 ) b 4 2 � a 2 1 a 2 2 b 4 2 which is clearly always positive, lim u !�1 P (u 2 ) =1. Hence by intermediate value theorem, there exists at least one u 2 in [�1; r 1 ] such that P (u 2 ) = 0. Similar argument works for [r 2 ; 1]. Notice that the leading coefficients of P 1 and P 2 are both positive, hence P 1 and P 2 are both positive for u 2 < r 1 or u 2 > r 2 . Hence if the roots of P = 0 in (�1; r 1 ] and [r 2 ; 1) equal to neither r 1 nor r 2 , then these roots will lead to imaginary solutions for w 1 and w 2 . IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 14, NO. 3, JUNE 1998 507 There is still one special case one needs to consider, that is, when either r 1 or r 2 (or both) happens to be a root of P . Let us assume say r 1 is a root of P . Hence it is a root of P 1 P 2 , it must also be a root of P 3 . However, since r 1 is the minimal roots among P 1 and P 2 , in order for w 1 and w 2 both be positive, one must have r 1 being a root for both P 1 and P 2 . Then it is clear that r 1 is a double root for P . Similar argument works for r 2 . To sum it up, we have shown that P can have at most two distinct roots in the interval [r 1 ; r 2 ]. These are the only roots that can lead to real solutions. Therefore there can be at most eight sets of real solutions. As will be demonstrated in the Appendix, these eight sets of solutions can be easily found using our algorithm. E. Remarks We make some remarks regarding the first step of our solutions, i.e., solving the following system of linear equations for L 0 �L 1 ; L 0 �L 2 and L 1 � L 2 c i; 1 L 0 � L 1 + c i; 2 L 0 � L 1 + c i; 3 L 1 � L 2 = d i i = 1; 2; 3 (36) where c i; 1 =(1� � i+2 � � i+2 )� i+2 (37) c i; 2 =(1� � i+2 � � i+2 )� i+2 (38) c i; 3 =� i+2 � i+2 (39) d i = [l 2 i+2 � (1� � i+2 � � i+2 ) 2 l 2 0 � � 2 i+2 l 2 1 � � 2 i+2 l 2 2 ]=2: (40) Note that the coefficient matrix of the system of (36) only depends on the design constants and is independent of the varying lengths of the legs. So if we compute the inverse of the coefficient matrix in advance, this system can be solved instantly in real life applications. However, some care is needed in choosing the design constants in order for the coefficient matrix to be nonsingular. For example, the design constants for a regular hexagon would be � 3 � 4 � 5 � 3 � 4 � 5 = �2 �3 �2 2 2 1 : This would lead to the following coefficient matrix �2 2 �4 �6 4 �6 �4 2 �2 which is singular. So we won’t be able to use (36) to find the dot products among L 1 ; L 2 , and L 3 . We point out that when the coefficient matrix is singular, it follows that d 1 ; d 2 , and d 3 must satisfy a linear equation in order for (36) to be solvable. From the formulas for d i ’s, it is obvious that l 0 ; l 1 ; � � � ; l 5 then satisfy a quadratic equation (or that l2 0 ; l 2 1 ; � � � ; l 2 5 satisfy a linear equation). For example, if one constructs a hexapod with both the base and mobile plates being regular hexagon, then the above discussion implies that d 1 � d 2 + d 3 = 0. It follows that the leg lengths of the hexapod must satisfy l 2 0 � l 2 1 + l 2 2 � l 2 3 + l 2 4 � l 2 5 = 0: Such a hexapod is of course not desirable because the legs can not move independent of each other. Fig. 2. Shape of the plate. F. Complexity of the Algorithm We give an estimated complexity of our algorithm by counting the number of multiplications needed. The contributions from additions are negligible. From the formula in the Appendix, we computed roughly 75 multiplications needed to write down the deg 4 equations of u 2 . We emphasize here the reason so few multiplications are needed is because a lot of calculations are independent of leg lengths, hence can be carried out beforehand and does not affect real time calculations. Finding the roots of the quartic equation involving u 2 is the most expensive step in our algorithm. From Ferrari’s explicit quartic formula, we see three square root operations and one cubic root operations. We also get a very conservative counts of less than 70 multiplications. From Section III-D, we know that only two of these u 2 ’s will lead to real solutions. It takes four multiplications to find out whether a given u 2 leads to real solutions. For a given u 2 , it takes less than 50 multiplications and two square roots to find two sets of solutions of L i ’s (not counting mirror images). So altogether, we need less than 260 multiplications, seven square roots, and one cubic root to get four sets of solutions. As a rough estimate, if we assume the square root takes about ten multiplications and the cubic root takes about 20 multiplications, then we get a total of less than 350 multiplications for our algorithm. This compares with an average of 4290 multiplications, and 630 sine functions needed for the iterative Newton–Raphson algorithm (cf., [2]). It shows that our algorithm is extremely efficient. IV. AN EXAMPLE Using the approach we laid out in the previous section, we demonstrate an explicit example. In our example, both the mobile and base plates has the shape of the hexagon in Fig. 2. It differs from the regular hexagon only by the position of one vertex (P 5 in Fig. 2). As is pointed out in the previous section, for regular hexagons, the coefficient matrix for system (36) is singular. The base and mobile plates are of the same shape, but the base is twice the size of the mobile one. For this Stewart Platform, the design constants are found to be as � 3 � 4 � 5 � 3 � 4 � 5 = �2 �3 �3 2 2 1 : The corresponding structure coefficient matrix is �2 2 �4 �6 4 �6 �9 3 �3 508 IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 14, NO. 3, JUNE 1998 TABLE I TABLE OF SOLUTIONS Fig. 3. Three-dimensional picture of the solutions. with inverse �1=2 1=2 �1=3 �3 5=2 �1 �3=2 1 �1=3 : We will assume that the XY Z-coordinate system is positioned so that B 0 is at the origin, B 1 = (20; 0; 0) and B 2 = (30; 10 p 3; 0). The coefficient matrix then determines the rest of the vectors on the base plates: B 3 = (20; 20 p 3; 0), B 4 = (0; 20 p 3; 0), and B 5 = (�30; 10 p 3; 0). Now for the following set of leg lengths: l 0 =18:13835715; l 1 = 10:15756929; l 2 = 13:44007650; l 3 =21:93023118; l 4 = 26:58493607; l 5 = 34:59409489 the four sets of solutions in Table I are computed using Maple, together with their mirror images with respect to the XY -plane (Fig. 3), one gets eight sets of solutions. Remark: Although in the example we give, bottom and base plates are assumed to have the same shape, our method of course applies to more general situations, i.e., they apply to any two plates that are linearly related. We only give this special example because in most real world designs, symmetries are often desirable. V. CONCLUSION We studied a class of Stewart Platforms for which we are able to provide true closed form solutions. Our methods are implemented using Maple. The algorithms of our methods are very simple and we believe it is suitable for real time applications. We also proved mathematically that the number of physically possible solutions for the class we considered is at most eight. APPENDIX Assume the solutions for the dot products among L 0 ; L 1 , and L 2 . For future reference, we list here explicitly the symbols we have used in Section III as functions of the lengths of the legs, l i = kL i k, i = 0; 1; � � � ; 5 N 1 = l 2 0 + l 2 1 � 2L 0 � L 1 (41) N 2 = l 2 0 + l 2 2 � 2L 0 � L 2 (42) N 3 = l 2 0 � L 0 � L 1 � L 0 � L 2 + L 1 � L 2 (43) C 1 = 1 2 (jjA 1 jj 2 � jjB 1 jj 2 �N 1 ) (44) C 2 = 1 2 (jjA 2 jj 2 � jjB 2 jj 2 �N 2 ) (45) C 3 =A 1 �A 2 �B 1 �B 2 �N 3 (46) K 1 = a 2 1 =b 2 2 (47) K 2 =2(a 2 C 1 � C 3 a 1 )=b 2 (48) K 3 =1 + a 2 2 =b 2 2 (49) K 4 = � 2a 2 C 2 =b 2 2 (50) K 5 = a 1 a 2 =b 2 2 (51) K 6 =(a 2 2 C 1 � a 1 a 2 C 3 � a 2 1 C 2 )=(a 1 b 2 2 ) (52) D 1 = � (C 2 1 b 2 2 + C 2 3 a 2 1 � 2a 1 a 2 C 1 C 3 � a 2 2 C 2 1 )=(a 1 b 2 2 ) +N 1 (53) D 2 =N 2 � C 2 2 =b 2 2 (54) D 3 =N 3 + (a 2 C 1 C 2 � a 1 C 2 C 3 )=(a 1 b 2 2 ): (55) REFERENCES [1] K. Cheok, J. Overholt, and R. Beck, “Exact methods for determining the kinematics of a Stewart platform using additional displacement sensors,” J. Robot. Syst., vol. 10, no. 5, pp. 689–707, July 1993. [2] Z. Geng and L. Haynes, “A 3-2-1 kinematic configuration of a Stewart platform and its application to six DoF pose measurements,” Int. J. Robot. Comput.-Integr. Manufact., vol. 11, no. 1, pp. 23–34, 1994. [3] Z. Geng, L. Haynes, J. Lee, and R. Carroll, “On the dynamic model and linematic analysis of a class of Stewart platforms,” J. Robot. Auton. Syst., vol. 9, pp. 237–254, 1992. [4] M. Griffis and J. Duffy, “A forward displacement analysis of a class of Stewart platforms,” J. Robot. Syst., vol. 6, no. 6, pp. 703–720, 1989. [5] W. Lin, J. Duffy, and M. Griffis, “Forward displacement analysis of the 4-4 Stewart platforms,” in Proc. 21st Biennial Mech. Conf. ASME, Chicago, IL, Sept. 1990, vol. DE-25, pp. 263–269. [6] P. Nanua, K. Waldron, and V. Murthy, “Direct kinematic solution of a Stewart platform,” IEEE Trans. Robot. Automat., vol. 6, pp. 438–444, 1990. [7] C. Nguyen, S. Antrazi, Z. Zhou, and C. Campbell, “Adaptive control of a Stewart platform-based manipulator,” J. Robot. Syst., vol. 10, no. 5, pp. 657–687, July, 1993. [8] D. Stewart, “A platform with six degree of freedom,” in Proc. Inst. Mech. Eng., London, U.K., 1965, vol. 180, pp. 371–386. [9] C. Zhang and S. Song, “Forward kinematics of a class of parallel (Stewart) platforms with closed form solutions,” Robot. Syst., vol. 9, no. 1, pp. 93–112, Jan. 1992. [10] , “Forward position analysis of nearly general Stewart platforms,” Trans. ASME, J. Mech. Des., vol. 116, no. 1, pp. 54–60, Mar. 1994.