[ec2m] Re: Physics engines [Darwin2k details]

[Chris Leger]

Hi all,

I just got back from vacation and saw some of the recent message
traffic.  Some details on Darwin2K:

- The low-level dynamics engine library (called "Dyno"; it's a
self-contained package) is capable of simulating multiple mechanisms.

- However, the evolutionary algorithm and higher-level functionality
currently only support a 
single robot.

The dynamics algorithm used in Dyno is a reduced-coordinate formulation,
and thus is O(n^3) for *each* robot where n is the number of degrees of
freedom (DOFs) of the system.  This is slower than other packages that
use Featherstone's method, which is linear in the number of DOFs. 
However, to the best of my knowledge (which is admittedly limited w.r.t.
Featherstone's work), the Featherstone algorithm can't deal with closed
kinematic chains or other constraints (aside from those that give a
tree-shaped or serial-chain mechanism its degrees of freedom); that's
the main reason I'm not using Featherstone.  The main advantage of the
reduced-coordinate approach over fully constraint-based approaches (e.g.
Langrangian-based methods) is that you can take much larger time steps
without worrying about your mechanisms flying apart.  

Currently, Dyno doesn't support inter-mechanism contacts; however, that
should be about a weekend's-worth of work for me to add, and is on my
to-do list anyway :)  Making the higher-level robot control stuff work
with multiple robots is probably somewhat less work, and also something
I haven't gotten around to finishing yet.  

As for the details of contact simulation, I have several different types
in place.  There is an implementation of Baraff's LCP-derived algorithm
for computing frictional contact forces; however, his presentation of
the algorithm is incomplete for 3D implementations and it turns out
that, quite frequently, the algorithm does not converge; so, I have also
added a compliant contact, and user-defined contacts for specific
classes of materials (i.e. inflatable robot wheels in contact with soil
having various physical parameters).  

I'm not sure what level of physical realism you're looking for; I built
Darwin2K for doing automated synthesis for robotics, so I've been fairly
finicky in many places and there's support for stuff like computing
internal forces and moments in beams so that structural design can be
done as well.  However, impact conditions (which in reality violates the
rigid-body assumption) are extremely difficult to model accurately and
so I haven't spent much time on that; I've used compliance-based
contacts instead.  

I'll be happy to provide further details (to this list, if anyone's
interested or privately if not) if desired.

Chris


-- 
"The worst habit you can possibly acquire is to become uncritical 
towards your own concepts and at the same time skeptical towards 
those of others. Once you arrive at that state you are in the grip 
of senility, regardless of your age."       -Karl von Terzaghi