Quest for solvers

[macin]

Hello there,

well I tinker with multibody dynamics for quite a while now but I still wonder which solvers can be used for which purpose. I work with impulse-velocity based LCP formulations. I know that Stewart, Trinkle and Anitescu propose LCP formulations which account for maximum dissipation (e.g. friction opposes sliding). However those formulations are rather hard to solve afaik. I know of two methods which can solve these LCPs: the direct Lemke pivoting method and the iterative non-smooth Newton method. Are there any others? If I want to use a projected GS solver then I cannot solve the (full) system because it has (partially) zeros on the diagonal - at least not in a straight forward way. Or are there any other possibilities to achieve maximum dissipation with a PGS approach? If we (somewhat simplified) delete the lower rows and columns to the right of the LCPs proposed by Trinkle and Stewart, then we are left with a J^T M^-1 J type of matrix which is symmetric and PSD and we can apply (Block-)PGS to solve the simplified LCP.

So what about other solvers? We can also reformulate LCPs as Quadratic Programs. So it should also be possible to solve at least the J^T M^-1 J type LCPs/QPs with a Conjugate Gradient approach as was mentioned earlier on the board. Are there any new insights on this? I read the paper "Conjugate gradient type algorithms for frictional multi-contact problems: applications to granular materials" by Mathieu Renouf and Pierre Alart however the results do not appear that promising. Are there other/better CG approaches for multibody contact QPs? Has anyone of you experimented with preconditioning of CG approaches? Maybe using even algebraic multigrid solvers? Is it worth a shot?

Are there any completely different noteworthy solution methods for those LCPs? Do you know of any multigrid approaches to solve multibody contact LCPs?

Regards,
Tobias

[ngbinh]

Glad to see someone share the same interest with me here.

There are many methods to deal with LCPs arised from Stewart/Trinkle/Anitescu formulation.

You can read one of my presentation to roughly get the idea:
http://www.cs.rpi.edu/~nguyeb2/docs/CP_solver.pdf
Remember I dealt with other formulation also (NCP,etc...).

If you just want to focus on LCP then the state of the art solver could be:
+ Lemke
+ Exploit sparsity (it's a must for large scene)
+ Exploit structure of the matrix ( read John LLoyd paper for an example: http://www.cs.ubc.ca/spider/lloyd/fastContact.html )
If you can do that, you can have a mostly linear solver with correct Coulomb friction.

But that's not everything, the major problem now is collision detection. Currently there is NO collision detection library give you what the method ( Stewart/Trinkle/Anitescu formulation ) need.

[Erwin Coumans]

But that's not everything, the major problem now is collision detection. Currently there is NO collision detection library give you what the method ( Stewart/Trinkle/Anitescu formulation ) need.

Can you elaborate what collision detection information STA exactly needs?

Isn't the closest points, penetration depth and continuous collision query to add contact points in advance (see Bullet's btCollisionWorld::convexSweepTest) sufficient? It should be easy to add 'all' future contact points (given the start and end transforms for two objects, assuming constant linear/angular velocity) using the convexSweepTest API, rather then just the first. Jan Bender already implemented the single-shot contact generation on top of Bullet for convex polyhedra.

Thanks,
Erwin

[ngbinh]

Can you elaborate what collision detection information STA exactly needs?

Isn't the closest points, penetration depth and continuous collision query to add contact points in advance (see Bullet's btCollisionWorld::convexSweepTest) sufficient? It should be easy to add 'all' future contact points (given the start and end transforms for two objects, assuming constant linear/angular velocity) using the convexSweepTest API, rather then just the first. Jan Bender already implemented the single-shot contact generation on top of Bullet for convex polyhedra.

Thanks,
Erwin

In short, STA formulation need ALL possible contacts to be stable. It can work with current Bullet too (as I show you once) but it's not as stable as it should.

I wonder if I can test Jan Bender's code?