Journal of Applied Sciences

Year: 2005 | Volume: 5 | Issue: 4 | Page No.: 666-673
DOI: 10.3923/jas.2005.666.673

Searching All the Roots of Inverse Kinematics Problem of Robot by Homotopy Continuation Method

Tzong-Mou Wu

Abstract: In general, when we deal with the inverse kinematics design problem of robot, the results/outputs usually are given/desired but the inputs are unknown/to be found. People must understand how to control/determine the input variables to satisfy the results/outputs. This study presents a new method, homotopy continuation method, for the inverse kinematics problem of robot. The kinematic equations are derived and their solutions/roots also will be obtained by homotopy continuation method.

Keywords: inverse, numerical method, Kinematics, homotopy continuation method and design

INTRODUCTION

At all times, the exact solutions are our aim when solving the simultaneous equations. However, it is usually difficult to achieve this aim. Hence we must use the numerical techniques to help us to do it. We can use Gauss elimination to solve the simultaneous linear equations well. Nevertheless, in the process of solving inverse kinematics design problems, some troublesome simultaneous equations will be generated, especially the simultaneous non-linear equations. Up to the present, we have already many different methods can manage the simultaneous non-linear equations, such as Newton-Raphson method. But the solutions can not be guaranteed by these traditional numerical techniques. The problems of convergence and computing time often puzzle us when using these traditional numerical techniques. The homotopy continuation method is an improved method of these traditional numerical techniques. It has not the disadvantage of traditional numerical techniques, that is, the acquirement of good initial guess values and the worry of convergence and computing time.

Homotopy continuation method was known as early as in the 1930’s. This method was used by kinematician in the 1960’s at U.S. for solving mechanism synthesis problems. The latest development was done by Morgan^[1-3] at GM. We also have two important literatures by Garcia^[4] and Allgower^[5]. Continuation method gives a set of certain answers and some simple iteration process to obtain our solutions more exactly. Furthermore, there are several representative mathematical studies^[6-12] on the continuation techniques that were written in the 1970’s and 1980’s. Recently, some works are interested in this field^[13-23]. He^[19-22] studied the homotopy method through a series of different non-linear equation. Gritton et al.^[15] made the effort to search all roots of different non-linear chemical equation. These two authors carried out the ability of homotopy method to “a” non-linear equation. On the other hand, Lee et al.^[16] successfully solved the simultaneous non-linear equations of spatial 3R robot also by the homotopy continuation method. Wu^[23] presented some techniques for combining Newton’s and homotopy methods to avoid divergence on solving non-linear equation. Also, Wu^[24] explored all the linear and non-linear solutions of the kinematics design problems. This study will attempt to apply the homotopy continuation method to systematically solve the general inverse kinematics problem of robot.

INVERSE KINEMATICS PROBLEM OF ROBOT

The objects of kinematics studies are to obtain the “equations of motion” or called “kinematic equations”, i.e. the displacement, velocity and acceleration relationships between input and output variables. These equations usually can be derived by serial combination of 4x4 homogeneous transformation matrices in the problem of robot. As we known, the nominal position and orientation of the kth frame (XYZ)_k with respect to the base frame (XYZ)₀ can be written as:

Where, A_i is the basic rotational or translational matrix ^i-1A_i and they have four standard 4x4 homogeneous forms

Where, Rot, Tran, C and S denote the rotation, translation, cos and sin, respectively. For the general k linkages, the displacement equation is:

Where, ^kr is the displacement or position vector of analyzed point with respect to frame (XYZ)_k. After the displacement relationship of kinematic equations being determined from Eq. 3, we then differentiate it two times to get velocity and acceleration relationships, respectively.

Whatever how complicated these three kinematic equations are. We always have the general functional forms of kinematic equations as follows

The givens and unknowns in forward/analysis and backward/design questions are reverse. Generally, in the analysis problems, the givens are all the input variables, including fixed and changeable variables and the unknowns are the output variables. However, in the robotic inverse problem, the givens are the output and input fixed variables, the unknowns therefore are the input changeable variables. More clearly, the givens are the fixed robotic links length L_i and our desired displacements, velocities or accelerations. The unknowns are the changeable robotic links rotational angle θ_i and translational quantity S_i. According to the character of kinematic equations of robot, we can rewrite Eq. 4 by the following forms:

Since, in the orthogonal coordinate systems, we have to represent the kinematic displacement equations as x, y or x, y, z components. So we will obtain the kinematic displacement equations with Sθ and Cθ forms. By this reason, we unfortunately get a set of simultaneous non-linear equations in Eq. 5-1. However, when the simultaneous non-linear equations being determined, i.e. (θ_i, S_i) being obtained, the kinematic velocity and acceleration Eqs. in 5-2 and 5-3 are linear about respectively. We can use popular Gauss elimination method to find them easily. They are not our purpose in this paper. This paper will deal with the simultaneous non-linear equations such as Eq. 5-1 by homotopy continuation method.

HOMOTOPY CONTINUATION METHOD

When dealing with the numerical problem, for example the Newton-Raphson method, there are two troublesome questions. One is the good initial guesses are not easy to detect and another is we worry whether the method we use will converge to useful solutions. Homotopy continuation method can eliminate these shortcomings.

Given a set of equations in n variables x₁, x₂, …, x_n. We modify the equations by omitting some of the terms and adding new ones until we have a new system of equations, the solutions to which may be easily guessed/given/known. We then deform the coefficients of the new system into the coefficients of the original system by a series of small increments and we follow the solution through the deformation, using methods such as Newton-Raphson. This is called homotopy continuation original system.

If we wish to find the solution vector for a system of simultaneous non-linear equations written in the form:

We choose a new simple start system

The start system G(X) must be known or controllable and easy to solve. Then, we define the homotopy continuation as:

Where, t is an arbitrary parameter and varies from 0 to 1, i.e., t∈[0,1]. Therefore, we have the following two boundary conditions:

This is called homotopy continuation method. It is also called Bootstrap method or Parameter-Perturbation method, but these names did not become popular.

For convenience in the general construction and programming of homotopy kinematic displacement equations of robot, we develop the following procedures in this paper for searching all roots of this problem.

Firstly, we rewrite vector Eq. 6 as the following scalar form:

Secondly, we choose a new simple start system as:

Where we take a known and controllable equations system similar to Eq. 10 as:

Hence, we can define the homotopy kinematic displacement equations of robot as:

Finally, we only need to solve Eq. 13 instead of Eq. 10 by varying each unknown θ_i from 0° to 360° and S_i from its permissible translation interval -S_i to S_i with Newton-Raphson method at every parameter t which is increased slowly from 0 to 1 for obtaining the solutions. Above are our all procedures for searching all roots of inverse kinematics problem of robot.

Example 1: The plane two degrees of freedom robot: Consider the plane two degrees of freedom robot shown in Fig. 1. We have the following simultaneous non-linear equations:

Assume that the robotic links length are L₁ = 2, L₂ = 1 and if we would like to guide its gripper P passing through our desired location (Px, Py) = (-1, 1.5). We must to determine the necessary links angle (θ₁, θ₂) in Eq. 14 by homotopy technique. Firstly, we choose a new known and controllable start system as:

Where:

Secondly, we define the homotopy kinematic displacement equations of this robot as:

Then, we run Eq. 17 by Newton-Raphson method and change links angle θ₁ and θ₂ from 0° to 360° respectively (dCita), the homotopy parameter t from 0 to 1 slowly (dt). We can obtain the results of this problem as shown in Fig. 2.

By some testing, we find that we just need to take the increment dt, in Fig. 2, as 0.01. Also every parameter t we need about 3 to 5 iterations, i.e. total iterations for one initial guess are 300 to 500 times, to converge to the solutions with error within 1E-10. It means that the computing time is little by homotopy method. It takes us about 6 (min) 21 (sec) to run the VB program on merely AMD K6/2-500 CPU, which includes 37x37x300=410700 to 37x37x500=684500 iterations in Eq. 17. Moreover, comparing Fig. 2a and b, we see that the typical Newton-Raphson method will converge to unpredicted answers even if these answers can satisfy our equations. It usually converges to larger cyclic values of desired answers, which must be obtained between 0° and 360°, because of the triangle equations are cyclic function. So these larger cyclic values will make one’s perplexity to judge the total useable answers. Unfortunately, it sometimes diverges/overflow.

Example 2: The space three degrees of freedom PUMA arm: The space three degrees of freedom PUMA arm and its coordinate assignment as shown in Fig. 3. θ₁, θ₂ and S are the input/to be found variables. L is given fixed link length but S is unknown changeable link length and S has the limitation of maximum length, i.e. it will be the value between -S and S.

Using transformation matrix methods in Eq. 1-3, we have the following relationships for each link

Therefore, we derive the kinematic displacement equations of this PUMA arm as:

Similarly, we have the following simultaneous non-linear equations:

Assume that the fixed robotic link length L = 2, the maximum changeable link length S = 3 and if we would like to guide robotic gripper P passing through the position (Px, Py, Pz) = (-2, 1.5, 1). Now, our task is to determine the necessary links angle (θ₁, θ₂) and link translation quantity S in Eq. 21 by homotopy technique. Firstly, we still choose a new known and controllable start system as:

And

Thus, the homotopy kinematic displacement equations of this PUMA arm, we define, are:

In the same way, we run Eq. 24 by Newton-Raphson method and change links angle θ₁ and θ₂ from 0° to 360°, link translation quantity S from -3 to 3 (dCita and dS), the homotopy parameter t from 0 to 1 (dt). We will get total four sets of the roots of this problem as shown in Fig. 4.

Running this program, we find when the initial guess (θ₁₀, θ₂₀, S₀) = (0°, 180°, -1), the typical Newton-Raphson method will “overflow” up to (θ₁, θ₂, S) = (-2.86E+11, -6.93E+11, -5.35E+09). By the help of homotopy method, we rerun Newton-Raphson from (θ₁₀, θ₂₀, S₀) = (20°, 10°, -3) and compare the results with homotopy shown in Fig. 4a and b, respectively. We also obtain the confusing cyclic answers by Newton-Raphson method in Fig. 4a. This situation will not occur in homotopy method, (Fig. 4b). The homotopy continuation method can guarantee the convergent and uniform solutions.

CONCLUSIONS

Typically, it is usually a big trouble and disadvantage for us to do the algebraic operation, for example, solving the simultaneous non-linear equations. Fortunately, by the aid of computer science, the simultaneous non-linear equations will be solved no more difficulty. With the computer improved and the numerical technique developed, the solutions of design variables in inverse kinematics design problems of robot become easier. We can use current high-speed processor to determine the solutions quickly. Also, we almost can real-time control the necessary inputs to meet the specified outputs whatever displacement, velocity or the acceleration.

Although, we already have many different numerical methods can help us to treat these non-linear equations. Typical Newton-Raphson method is a popular numerical method. However, it still has some well-known critical defects. By means of the development of numerical continuation technique, the defects in traditional numerical methods such as the acquirement of a good initial guess, the problems of convergence and the computing time will be avoided. Homotopy continuation method is one of the famous improved numerical continuation methods. Its convergence speed is fast, also the algorithm is clear and easy.

This study applies homotopy method to solve the simultaneous non-linear equations in the inverse kinematics design problems of robot. We can get well outcome by this method. This new interesting method will provide another numerical approach. It is hoped that the work presented here will contribute towards progress in the kinematics design, numerical method and other fields for scientists or engineers.

REFERENCES