A Practical Implementation of an algorithm for Decomposing

Sine-Cosine Equations with Parametric Coefficients

Jaime Gutierrez

Dpto. Matemáticas, Estadística y Computación

Universidad de Cantabria, Santander 39071, Spain

Abstract.

To solve symbolically the inverse kinematic problem usually requires to compute the roots of the so-called sine-cosine polynomials. A functional decomposition of a sine-cosine polynomial equation f(s,c)=0 reduces this task to the solution of two equations of degree less or equal than half the degree of f(s,c). Methods for simplifying the symbolic solution of kinematics problems through functional decomposition were initiated by G. Hommel and P. Kovacs, well documented with applications in the recent book of the latter author. They addressed the problem of simplifying the characteristic equation f(s,c)=0 for a revolute joint variable $\theta$( s and c stand for $sin(\theta)$ and $cos(\theta)$), whose solution provides the possible value(s) of the joint angle $\theta$ in a robot manipulator for each given position of the end effector.

The sine-cosine polynomial decomposition problem can be sated as follows:

given a sine-cosine characteristic equation f(s,c) for a revolute joint variable $\theta$, we want to know if there exist a univariate polynomial g(x) and a sine-cosine polynomial h(s,c) with deg(NF(h(s,c)) < deg(NF(h(s,c)) such that:

NF(f(s,c))=g(NF(h(s,c)) modulo the trigonometric identity s²+c²=1

and in the affirmative case to compute g(x) and h(s,c). Remark that NF stands for the normal form of a sine-cosine polynomial, i.e. the result of reducing it by replacing s² by 1-c².

It is remarkable that the simplification accomplished by functional decomposition agrees with the criteria for simplifiability as formulated by Smith and Lipkin, of purely geometric nature, regarding a 6R manipulator with the three last axis intersecting. On the other hand, it seems that the are not other symbolic algebraic simplification approaches (such as factorization) that can be tested in different instances occuring in robotics.

Regarding algorithms for the decomposition problem, we can mention the results of G. Hommel and P. Kovacs, requiring an exponential number of field operations in the input degree; even if the in last paper reduces the complexity by magnitudes and the authors state that satifyies all needs in kinematics, it is kept exponential. We must also mention work of von zur Gathen and Weiss, about Bivariate Homgeneous Decomposition (BHD): a homogenous bivariate decomposition of a univariate polynomial f(t) is of the form f(t)=g(h(t), k(t)) with polynomials g(x,y), h(t), k(t), where g(x,y) is a bivariate and homogenous. The authors present an algorithm of exponential time complexity in the input degree. Such decompositions are also of interest in kinematics, in fact, the kinematic equations can be converted through the tangent half angle substitution to univariate t-polynomials f(t).

It is very easy to see that if a sine-cosine polynomial f(s,c) is decomposable, then the f(t) associated univariate polynomial has a bivariate homogeneous decomposition, but not conversely. Nevertheless there is a serious limitation for efficient robotic applications to t-polynomials of degree bigger than six, because the BHD algorithm requires factorization procedures over algebraic extensions of the field K(t).

In this talk, we present the implementation of the the method by Gutierrez$\&$Recio(1997) for decomposing sine-cosine equations with numerical or parametric coefficients. The algorithm is in polynomial time. Factoring is not required in the algorithm, but rather it just need finding one root in the field K of a certain polynomial p(Z) in K[Z]. The implementation on MAPLE V, allowing decomposition over the rationals, algebraic extension of the rationals or parametric coefficient fields. The perfomance of the algorithm allows decomposing, almost instantaneously, sine-cosine polynomials of degree 16 with a Power Macintosh 9600/350.

Gathen, J.$\&$Weiss, J.:Homogeneous bivariate decompositions. Preprint, Dep. of Computer Science, University of Toronto, 1993.

Gutierrez, J.$\&$Recio, T.:Advances on the Simplification of Sine-Cosine Equations. To appear, J of Symbolic Computation, 40 pages, 1997. Preprint, Dep. of Computer Science, University of Toronto, 1993.

Kovács, P.$\&$Hommel, G.:Simplification of Symbolic Inverse Kinematic Transformations through Functional Decomposition. Adv. in Robotics. Ferrara, Sept. 1992.

Kovács, P.Rechnergestutzte symbolische Roboterkinematik. Vieweg Verlag, Wiesbaden (1993).

Smith, D.$\&$Lipkin, H.: A summary of the Theory and Application of the conics method in robot Kinemataic. 2nd. Intl. Conf. on Adv. in Robot Kinmetics. Linz (1990)- Springer- Verlag, pp. 81-88 (1991).