Cad Cam Development



Numerical Methods for solving globally convergent nonlinear polynomial system of equations. Pathfinder part 1

I am programming pathfinder with user defined geometrical constraints that the robot has to obey. There is an inverse kinematic chain to solve. The problem is, that a robot does not have constant dimensions but user-defined dimensions. Therefore I couldn’t analyze the complete kinematic chain in preprocessing or even before programming. This system of equations from robot has to be solved globally. Due to the miscellaneous geometrical constraints I cannot easily predict  the start point because it will vary over constraints. There are many applications to this problem in biology, economics, physics, engineering, geometry (intersection of surfaces) and of course mathematics and we have not solved that problem yet. Because of  the existence of  several  roots, and  that these  usually  are  dispersed  to  unknown  positions  in  N-dimensional space,  efficient numerical methods are hard  to develop.

Example. Inverse kinematic chain for two revolute joins.

Suppose we have to compute the inverse kinematic chain so that we can manipulate the robot that has two revolute joins. Look at the picture below. The pair (x,y) forms a destination point that a robot need to reach.

Simple kinematic chaind with two revolute joins

Intersection of two circles

The arm’s lengths l_{0},l_{1},l_{2} are user defined variables that can be modified within GUI. How to solve the inverse kinematic chain? The normal kinematic chains is described by system of equations (1). We need to solve it accordingly to angle. There is no way of pre processing the sytem of equations so that a start point for Newton-Raphson method could be defined. You have to solve them either as global nonlinear system of equations or just using the smart remark that this kinematic chain can be solved same as intersection of two circles what has been already described for instance here.

Line searching and globally convergent Newton-Raphson

There is no single globally convergent method for solving polynomial equation. The best Newton-Raphson method requires start point. Global solution methods are designed to compute all roots in the whole domain of polynomial.  You can extend Newton-Raphson to globally convergent method so that you discretize the domain of polynomial you are solving into smaller intervals. The bounds of the small intervals will be start points for Newton-Raphson method. However this can take many iterations and if you are working with some stiff equations you can realize that the discretization step you chose was to big. The secant method is similar to Newton-Raphson method. I truly advise you to avoid implementing this kind of algorithm unless you know the polynomial you are solving very good.

If you know your equation you are going to solve quite good you can start trying to solve it with globally convergent Newton-Raphson method. Such procedure for globally convergent system of nonlinear polynomial equations has been described in numerical recipies. The main idea is to provide a procedure called Line Searching so that you could provide a step in Newton-Raphson method. There are many proposals of how this step should look like.  Look in Numerical Recipies or for example here: A line search lter approach for the system of nonlinear equations by Pu-yan Nie, Ming-yong Lai, Shu-jin Zhu, Pei-ai Zhang.

Gröbner bases

Wolfgang Gröbner

There are also algorithms in Gröbner bases. [The thoery of Gröbner bases was developed by Buchberger. Gröbner bases are very special and useful bases for a special subsets of polynomial rings in l variables, called polynomial ideals. They are named after Gröbner who was Buchberger’s thesis advisor. Gröbner bases can be thought of as a generalization of Euclid’s algorithm for computing the greatest common divisor of two polynomials and of the Gauss triangularization algorithm for solving linear systems. The usefulness of Gröbner basis for solving nonlinear polynomial systems comes from the fact, that, whenever the system has a finite numer of solutions, Gröbner basis provides an equivalent system of triangular form. Using Gröbner bases, polynomial systems are converted to polynomial triangular systems, which can be solved by backward substitution, much in the manner of the Gauss triangularization algorithm for the linear systems. The biggest drawback of Gröbner basis and solving polynomials by them is its complexity. If the system has a finite number of solutions in the affine plane, as well as in the projective plane, then a Gröbner basis can be computed in Gröbner bases can be thought of as a generalization of Euclid’s algorithm for computing the greatest common divisor of two polynomials and of the Gauss triangularization algorithm for solving linear systems. The usefulness of Gröbner basis for solving nonlinear polynomial systems comes from the fact, that, whenever the system has a finite number of solutions, Gröbner basis provides an equivalent system of triangular form. Using Gröbner bases, polynomial systems are converted to polynomial triangular systems, which can be solved by backward substitution, much in the manner of the Gauss triangularization algorithm for the linear systems. The biggest drawback of Gröbner basis and solving polynomials by them is its complexity. If the system has a finite number of solutions in the affine plane, as well as in the projective plane, then a Gröbner basis can be computed in O(m^l) m-the highest degree among polynomials, l- number of variables.]  by Shape Interrogation, Nicholas Patrikalakis, Takashi Maekawa.

The cost therefore becomes prohibitive for polynomials of higher order than 4-5. If you have to compute it many times like it is done in finding path for robot in inverse kinematic chains the cost can be unacceptable. Personally I have not yet implemented this kind of math.

Homotopy

Homotopy methods are methematically elegant, but unfortunately, numerically ill-conditioned. If we try to get around this problem by implementing the algorithm in rational arithmetic, we end up with enormous memory requirements because we have to solve large systems of complex initial value problem. Interval methods like those described above can be applied to the solution of these IVP’s but they can be slow in practice. Nonetheless there are lots of articles in the web about homotopy and personally I’ve been reading them with pleasure. The best I can advise you to read is: Chin-Hong Park and Hong-Tae Shim WHAT IS THE HOMOTOPY METHOD FOR A SYSTEM OF NONLINEAR EQUATIONS(SURVEY) ?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s