Systems of polynomial equations

Question

Hi all,

I'm an engineer assigned to determine some parameters of a manipulator (ie., calibration). It has a number of parameters, but after some manipulations of its dynamic equations, I can have the following equations:

$\mathbf{l}_i^T \mathbf{R}_x \mathbf{R}_i \mathbf{p} = 0$ with $i=0,..,N$ (1)

where $\mathbf{l}_i$ (3x1 vector) and $\mathbf{R}_i$ (3x3 vector) can be measured and computed using external devices. $\mathbf{R}_x$ and $\mathbf{p}$ are the ones that I have to determine. $\mathbf{R}_x$ is a unitary matrix (actually some rotation matrix with 3 degrees of freedom). $\mathbf{p}$ is fixed and is some linear transform of some other parameters. Further isolating $\mathbf{R}_x$, I can get the following system:

$[(\mathbf{R}^T_0 \mathbf{R}^T_x \mathbf{l}_0) \times (\mathbf{R}_1^T\mathbf{R}_x^T\mathbf{l}_1)] . \mathbf{R}_k^T \mathbf{R}_x^T \mathbf{l}_k = 0$ (2) where $k=2,..,N$ with $\times$ denotes cross product and $.$ denotes dot product. $N$ is the number of measurements.

At this point, I'm not sure how to solve this system of equations. The reason that I chose to isolate $\mathbf{R}_x$ because once it is found, I can find other parameters using a large but doable linear system. My questions are:

1) Is it possible to solve the system (2)? Any idea to analytical or numerical solutions is highly appreciated. The problem is not trivial at all. For example, if I limit $\mathbf{R}_x$ to one degree of freedom (DOG), and set it to become $\mathbf{R}_x$ = [cos(a) -sin(a) 0; sin(a) cos(a) 0; 0 0 1] (Matlab notation), then I will have an equation with $\cos(a)^3, \sin(a)^3, \cos(a)^2\sin(a), \dots$ terms with $N=3$. If I use $x=\cos(a)$ and $y=\sin(a)$ with constraint $x^2 + y^2 = 1$, then I have a system of polynomial equations, as titled. That simplified system is somehow doable but no way trivial. And that is for 1 DOG only. It'll get much worse for all 3 DOGs altogether.

2) Since $\mathbf{l}_i$ (3x1 vector) and $\mathbf{R}_i$ are measured, it can have measurement noises. If the system is linear, the way is to find least square, but I'm not sure about this. Any theory to deal with this case?

3) Can Groebner basis theory be useful in my case? When I searched for a solution for question 1 above, it seems helpful as shown in http://www.scholarpedia.org/article/Groebner_basis#Robotics However, further reading indicates that it may not be stable with measurement noises, floating point, etc. I'm not sure it's worth my time and effort to study the theory, given that I have a deadline. In addition, learning such advanced math theory by myself can be very difficult, if not impossible. Please advise.

Thank you very much.

Answer 1

I won't be able to answer your question entirely, but I hope these remarks can be useful.

1. I believe your problem could be tractable using Groebner bases: I remember a seminar talk from the late 1990's by Laureano Gonzalez-Vega where he solved an electrical engineering problem a colleague had asked by precisely that kind of trick: turning sines and cosines into a polynomial system with the sum of squares equals 1 constraint.

2. Though I don't remember all the details, I think his problem was simpler. But both computers and algorithms have improved noticeably in the past 10 years, hence my guarded optimism.

3. I briefly looked around for any written reference from that specific work, and I could not find anything. It's highly likely the detailed solution was never published. In the meantime, chapters 1 and 2 of Some Tapas of Computer Algebra might be useful get an idea about polynomial system solving.

4. The topic is technical. You mention investing time in learning the theory, but what I learned from the people I know who solve polynomial systems for a living is that learning the theory is not the hardest or more time intensive: solving is an art as well as a science, and experience counts for a lot. There are ways of recasting a problem that can turn it from too hard to feasible, and veterans of the subject have a knack for seeing those. I don't know what kind of deadline you are working with, but that will not make matters easier.

5. Related to my previous point: all the examples I know of successful applications of Groebner bases to (hard) engineering problems have involved a close collaboration between specialists in the field of engineering in question and polynomial system solving experts. The good news is that those symbolic computation experts who have a real interest in engineering applications are always looking for new examples and new challenges, so you might be able to interest one of them in your problem.

OK, so I'm offering a lot of words and not a lot of solutions; I hope this is somewhat helpful nonetheless.

Answer 2

Thanks for your reply, Thiery. Your point 4 is exactly my fear. I'm afraid that after spending so much my time and effort, I'm still not proficient and experienced enough to manipulate and solve the problem.

I want to elaborate my question 1 further. If I have full 3 DOGs altogether, I need more measurements (N >= 5, I guess) but I can have as many measurements N as I want. The $\mathbf R_x$ is the full rotation matrix as shown here http://en.wikipedia.org/wiki/Rotation_matrix#General_rotations (I couldn't make a matrix displayed here).

Expanding and deriving the equations in $\sin(a), \cos(a), \sin(b), \cos(b), \sin(c), \cos(c)$ where a, b, c is roll-pitch-yaw angles and its resulting polynomials in $x_1 = \sin(a), x_2 = \cos(a), x_3 = \sin(b), x_4 = \cos(b), x_5= \sin(c), x_6 = \cos(c)$ is not really tractable.

So, maybe system of polynomials and Groebner bases may be not the only way. I hope maybe there is another beautiful mathematical approach to this problem.

Answer 3

Continuing from my previous posts:

I represent the rotation as quaternion $[q_1, q_2, q_3, q_4]^T = [\mathbf{q}^T, q_4]^T$, instead of roll, pitch, yaw angles, then $\mathbf{R}_x = (2q_4^2 -1) \mathbf{I}_3 -2q_4\lfloor \mathbf{q} \times \rfloor + 2\mathbf{q}\mathbf{q}^T$ where $\lfloor \mathbf{q} \times \rfloor$ is the skew-symmetric matrix for 3-by-1 vector q. By doing so, I reduce the number of variables from 6 to 4, with 1 additional constraint $q_1^2+ q_2^2+ q_3^2 + q_4^2 = 1$.

From this, I can retrieve a system of polynomial equations of 6th-order with 4 variables:

$P_k(q_1, q_2, q_3, q_4) = 0$ where $k=2,\dots,N$

My original question (1) now becomes:

1b) How to solve this system numerically? An analytical solution will be extremely sexy and highly desired because it may help me to avoid singular configurations when collecting data $\mathbf{l}_i, \mathbf{R}_i$ but it is nearly impossible.

Newton method and its variant is not feasible because we don't know a good prior of $q_1, ..., q_4$ (completely zero information about its prior). Newton method need a starting point and a wrong one can lead to a wrong solution. In fact, if we know the prior, we can easily linearize the system and use some EKF-based estimator to estimate it. Unfortunately, that's not the case.

So, I don't know if there is any method that solves the above system numerically. Something similar to Laguerre's method, extended to multivariate case.

Dear experts, please enlighten. Your help is greatly appreciated.

Answer 4

I do not have an exact answer for your question. I am an Engineer myself and have come across a similar problem in my research. You may find the techniques used there to be useful.

I assume that there are two problems you are trying to address here:

1) For a given $\{I_i,R_i\}$, when does there exist a solution ($p,R_x$) satisfying (1)?

2) If a solution exists, then how to compute the right solution? If the solution does not exist, then how to model the problem and find the best solution?

The first problem can be addressed just by counting the number of variables and equations in (1). The number of equations is equal to $N$ and the number of variables is equal to $5$. Number of variables is equal to $5$ because you have three degrees of freedom in choosing $R_x$ and two degrees of freedom in choosing $p$. Perhaps you can then use arguments similar to those in "On Feasibility of Interference Alignment in MIMO Interference Networks" to obtain necessary and sufficient conditions on $N$ characterizing the scenarios when (1) is feasible.

Regarding the second problem, if you are happy in finding an approximate solution then you can think of iterative algorithms (which hopefully converges to the right solution) to solve (1). One algorithm that I can think of on the top of my head is motivated from Algorithm 1 in "Approaching the Capacity of Wireless Networks through Distributed Interference Alignment". The algorithm for your problem would be as follows, which aims at minimizing $f(R_x,p) = \sum_i (\mathbf{l}_i^T \mathbf{R}_x \mathbf{R}_i \mathbf{p})^2$

1) Start with some $R_x$ and $p$.

2) Fix $R_x$ and find the best $p$ that minimizes $f(R_x,p)$.

3) Fix $p$ and find the best $R_x$ that minimizes $f(R_x,p)$.

4) Repeat steps (3) and (4) till the algorithm convergences.

Hope this helps!