Real-Time Physics Simulation Forum

Re: How to solve MLCP with Projected Gauss-Seidel?

2010-10-14T19:00:32+00:00

@Erwin: You're right! Thanks for correcting me on that.

Statistics: Posted by ngbinh — Thu Oct 14, 2010 7:00 pm

Re: How to solve MLCP with Projected Gauss-Seidel?

2010-10-14T06:04:48+00:00

I see. Thanks for the clarification.

Cheers,
-Dirk

Statistics: Posted by Dirk Gregorius — Thu Oct 14, 2010 6:04 am

Re: How to solve MLCP with Projected Gauss-Seidel?

2010-10-13T21:19:19+00:00

Its because if some problem is to be an LCP problem, it must be on the form
w=Ax+b>=0, x>=0, w^Tx =0.

So, when we want to model the coupling between normal force magnitudes and friction force magnitudes, the only way to put that into the form of an LCP is to introduce extra variables, like Stewart and Trinkle did (they use lambda as symbol in some of the papers if I recall). When you do that, you end up with a system matrix that cannot by solved by PGS anymore. Then, someone came up with the idea of dropping the friction cone approximation from Stewart-Trinkle, and just projecting the friction forces one by one in the PGS loop. (like its done in bullet?), That showed to work out well, but it is not on the LCP form.

/morten

Statistics: Posted by silcowitz — Wed Oct 13, 2010 9:19 pm

Re: How to solve MLCP with Projected Gauss-Seidel?

2010-10-13T18:22:19+00:00

@Erwin/Morten: You are refering to non-linerar complementary problems. Where did we move from the LCP to the NCP? Which part is actually non-linear in the ODE/Bullet formulation?

According to Kenny, updating the low/high limits for the friction every iteration makes the problem non-linear. This is also why we cannot prove convergence of PGS anymore.
Thanks,
Erwin

Statistics: Posted by Erwin Coumans — Wed Oct 13, 2010 6:22 pm

Re: How to solve MLCP with Projected Gauss-Seidel?

2010-10-13T17:58:29+00:00

@Erwin/Morten: You are refering to non-linerar complementary problems. Where did we move from the LCP to the NCP? Which part is actually non-linear in the ODE/Bullet formulation?

Statistics: Posted by Dirk Gregorius — Wed Oct 13, 2010 5:58 pm

Re: How to solve MLCP with Projected Gauss-Seidel?

2010-10-13T17:55:36+00:00

I was confused by Kenny's dissertation were he presented results and said that he used PSG. I wonder how he did that.

Look at my post before. It shows quite easily how you arrive at a velocity level formulation that can be solved using PGS.

Note that there is no difference between SI and PGS as Erwin points out correctly. The view of of the problem with SI is much easier (at least in my opinion) and allows some optimizations which are maybe not directly apparent if you take the PGS route. SI is not as abstract as PGS and helps understanding everything better if you ask me.

-Dirk

Statistics: Posted by Dirk Gregorius — Wed Oct 13, 2010 5:55 pm

Re: How to solve MLCP with Projected Gauss-Seidel?

2010-10-13T17:41:15+00:00

Just to clear out some potential confusion early on, its not NN-CP, its NN-CG, because the last two letters refers to Conjugate Gradients Anyways, I had good results using the NNCG solver in Jinngine (http://code.google.com/p/jinngine/). But I would really like to hear about other peoples experiences, in case somebody should try it out.

/morten silcowitz

Statistics: Posted by silcowitz — Wed Oct 13, 2010 5:41 pm

Re: How to solve MLCP with Projected Gauss-Seidel?

2010-10-13T16:13:23+00:00

* Correction: NNCP should be NNCG *

Let me put it another way: Bullet does not solve for friction and normal forces together

I think you misunderstand, Bullet does solve friction and normal forces together during all PGS iterations. The interaction (or impulse exchange) between contact constraints is the same as the interaction between contact and friction constraints. In other words, for n iterations, the friction is based on the most up-to-date normal force for n times, and the normal force is based on the friction force for previous iteration for (n-1) times. By default, Bullet uses 10 iterations, but you can increase this if you like higher quality/stiffness.

Erwin, you are right Stewart used Lemke to solve MLCP. I was confused by Kenny's dissertation were he presented results and said that he used PSG. I wonder how he did that.

The PGS that Kenny describes in his PhD thesis chapter 6 (did you read chapter 6?) is based on the NCP/PGS formulation used by ODE quickstep or the Bullet PGS/SI constraint solver.
Sequential Impulse is just a different name than PGS, it is not more efficient, just more intuitively explained that's all. The PGS derivation is more math-heavy.

For very stiff systems, or systems with large math ratios, you might want to try a direct solver instead of an iterative solver. You should check out ODE's Dantzig solver (dWorldStep instead of dWorldQuickstep) or ngbinh's work on Trinkle/Stewart using the PATH solver. Perhaps Kenny Erleben's latest NN-CG work might help too?
Thanks,
Erwin

Statistics: Posted by Erwin Coumans — Wed Oct 13, 2010 4:13 pm

Re: How to solve MLCP with Projected Gauss-Seidel?

2010-10-13T15:03:43+00:00

Thank you all.

Erwin, you are right Stewart used Lemke to solve MLCP. I was confused by Kenny's dissertation were he presented results and said that he used PSG. I wonder how he did that.

Currently, I have implemented NCP from the paper "Poulsen,M., Niebe,S., Erleben,K.: Heuristic Convergence Rate Improvements of
the Projected Gauss-Seidel Method for Frictional Contact Problems", the link you gave me http://wscg.zcu.cz/WSCG2010/Papers_2010 ... edings.pdf .
It works well for simple configuration, I didn't have a chance to test it for complicated systems.

As I understand SI is very similar to this approach and much faster. I will try to implement it later and compare the results.

I am interested in simulation of stiff systems like large vehicles.
What scheme would you recommend for time stepping, especially for stiff systems?
Explicit - problem with convergence?
Implicit - additional iteration to bring joints to the current time step?
Maybe Verlet? - how does it work with stiff configurations?

Thank you.

Ros.

Statistics: Posted by leromi — Wed Oct 13, 2010 3:03 pm

Re: How to solve MLCP with Projected Gauss-Seidel?

2010-10-13T13:24:20+00:00

Sorry, I read the thread way too quick. So what we usually do for games and what is also explained in Kenny Erleben's thesis is a velocity based time stepper. The original problem (using only holonome constraints to get you the idea is):

x' = v
v' = M^-1 * ( JT * lambda + f_ext )
C(x) = 0

So you have three equations for three unknowns (x', v', lambda), but you cannot solve it. The first two and the third equations are not related. Many ways exist, but the one usually used in games uses a symplectic Euler and solves on the velocity level instead of the position level. This is already a linearization since you now look at the tangent space of the original constraint space. So basically you have:

x2 = x1 + v2 * dt
v2 = v1 + M^-1 * ( JT * lambda + f_ext ) * dt
J * v2 = 0

M * v2 - JT * lambda * dt = M * v1 + f_ext * dt
-J* v2 = 0

[ M -JT ] [ v2 ] = b
[ -J 0 ] [ lambda' ] = 0 // lambda' = lambda * dt

This system could *not* be solved with PGS (it also has zeros on its diagonals). But it has other interesting properties, e.g. it is always sparse and for hierarchical structures you can solve it in linear time. If you now plug the second into the third equation you get the so called effective mass form which I already mentioned above:

J*M-^1*JT * lambda = -J * ( v1 + M-^1 * f_ext * dt )

This can be solved with PGS now since J*M-^1*JT is PD diagonal dominant. Usually you don't have only holonome constraints, but also contact, friction, limits, and motors. From there it is pretty simple to add these. Erwin summarized the friction differences very well and I agree that this is usally sufficient for games. I cannot comment on robotics though. Still I recommed using an impulse implementation like SI since they are very efficient and easy to implement. You can also play with different friction ideas like e.g. circular clamping very, very easily. You cannot prove convergence in these cases (at least I can't), but this works really well in practise.

HTH,
-Dirk

Statistics: Posted by Dirk Gregorius — Wed Oct 13, 2010 1:24 pm