[ODE] Re: Ridid-body simulation techniques

[Russ Smith]

Bob Hearn <rah@ai.mit.edu> wrote:
> I'm working on a 2d rigid-body simulator as a platform for AI 
> research, and I wanted to ask you a few questions about ODE and about 
> simulators in general.  It would be great if I could ODE, and spend 
> my time working on my research instead of writing simulators - fun 
> though that is!

hi,

funny, i wrote simulators so i could spend time on my research instead
of building robots - fun though that is.

> Foremost in my mind is the question of why one would need an LCP 
> solver.  I've read the papers by Baraff, and they leave me puzzled. 
> I've emailed him with questions, but he's been most unhelpful.

there are many ways to simulate a rigid body system - there are many
ways to model the physics of the system differently, and for each of
those ways there are multiple solvers and integration methods. the LCP
problem arises because we want to use the following physical model for
contacts:
  * contacts are modelled as constraints
  * at each time step, all the contact constraints are in a consistent
    state, where consistent is defined as:
      - either the contact is breaking, i.e. the contacting surfaces are
        coming apart (not the other direction) and the contact constraint
        does not exert any force.
      - or the contact is non-breaking, and the contact constraint exerts
        just enough force to keep the bodies from interpenetrating.

the last two conditions are a wordy description of an LCP problem.

> But this makes no sense to me.  In my contact model, I treat 
> collisions and contact separations symmetrically, as follows. 
> Normally, I just integrate for one time step to get the new state, 
> treating contact constraints just like any joint constraint.  But 
> when the new state contains a "contact exception", then it must be 
> resolved.  These include overlapping objects, and "tensional" contact 
> forces - that is, contact constraints that are acting to hold bodies 
> together rather than keep them apart.
> 
> Both of these situations are unphysical, and must be corrected.  I 
> first identify when exactly the exception occurred (with a heuristic 
> binary search), step to that time, then resolve the exception.  For 
> overlaps, a collision occurs, possibly creating a new permanent 
> contact constraint (if the relative velocity is low enough).  For 
> tensional contact constraints, I simply remove the constraint. 
> (There are other contact exceptions for sliding off an edge, 
> sticking/slipping, etc.)
> 
> As the name implies, both events are exceptional - for most 
> timesteps, neither will occur, and all one has to do is solve the 
> linear equations induced by the constraints.  Even if there's some 
> subtlety I'm missing about potential complications with multiple 
> contacts trying to separate at once, it seems unreasonable to pay an 
> LCP-solve cost for most of the timesteps, when usually the linear 
> equations suffice.

i dont fully understand your technique - but it sounds like you've
actually implemented an LCP solver! if you have frictionless (1D)
contact constraints, then switching them on and off like this (within
a single timestep) to satisfy the physical constraints is actually
one of the popular solution methods for solving the LCP problem.
 
> Yet, everywhere I look, people are using LCP solvers.  I've looked 
> over the ODE docs, but it's not clear to me when the LCP solver is 
> used.

LCP solvers are used (as opposed to more ad-hoc techniques) because
LCP conditions are a good way to express a number of physical
properties (friction being the most well known), and it's a good
cleavage point for the software: you can concentrate on improving the
LCP solver independently from the physical model, integrator etc.

the LCP solver in ODE is used every time the big system matrix needs
to be inverted, i.e. every time step.

>  Also, it looks like contact constraints are intended to be 
> used only during collision resolution, and then destroyed.  How do 
> you deal with objects in permanent contact, or with walking robots, 
> where the legs must stay on the ground for a time?

the contact joint is recreated each timestep. contacts are created and
destroyed like this, instead of being persistent, because it's fairly
hard to track the motion of a single contact point over time - e.g.
two different configurations that are one time step apart can have
different sets of contact points - how do you tell which ones are the
"same" ?

> Also, presumably you don't use the LCP solver when not dealing with 
> contact situations... what method or methods do you use to solve for 
> normal articulated systems?

in the no-LCP-condition case the LCP solver reverts to a simple
factorizer. i use L*D*L^T factorization.

>  I'm currently using conjugate gradients, 
> but static friction can lead to singular systems in some cases.  I 
> don't really want to always use SVD, since it's so much slower...

ODE systems are always positive definite, and ODE is targeted towards
smallish physical systems, so i use a dense L*D*L^T.

> My application is essentially a 2d robot world.  The model is A. K. 
> Dewdney's book "Planiverse" - he's invented a rich anatomical and 
> mechanical library for me to draw on.  The creatures will be 
> controlled by Society of Mind-inspired behavioral programs.  They 
> need to be able to walk around, pick things up, throw things, etc. 
> They need an environment with houses, walls, mechanical devices made 
> with joints and springs, etc.
> 
> Do you think ODE is currently suited for this use?  Would it be 
> realtime for a simple 2d walking robot?  For a few robots, plus a 
> reasonably complicated 2d environment?

i've not thought about 2D much. a 3D simulator is really a waste as
the possible joint types in 2D are far fewer, and the system matrices
do not have to be so big. a 3D sim would also need extra stabilization
so that bodies do not go out of the 2D plane.

> Thanks,
> Bob Hearn

-russ

-- 
Russell Smith
http://www.q12.org