[ODE] Ragdoll characters with ODE

[Adam Paul Coates]

On Fri, 8 Aug 2003, Martin C. Martin wrote:

> Adam Paul Coates wrote:
> >
> > policy/value iteration, simple search, even linear regression or neural
> > nets can get you pretty close.
>
> Policy/value iteration has real problems with more than a few degrees of
> freedom, and is almost impossible with more than five degrees of freedom,
> unless you can exploit a lot of knowledge about the problem.

Right - hence the large state space which gives ridiculously large
memory/time requirements for the algorithm.  If you're willing to spend
the computational time and resources then it can be done (admittedly, most
people couldn't do this on a desktop machine -- we always took over a
bunch of the Sun workstations :) hehe...) and you do have to make an
effort to simplify things to avoid the nasty computational growth.  But if
you chop the state down to something like 5-10 discrete values for various
angles, and then, for sure, exploit knowledge about which joints will
affect others, I think this is actually doable for a simple humanoid.

I saw a demo of a 6-legged robot with each leg having 3 or 4 DOFs (can't
recall..).  I think the policy search took something on the order of days
and I suspect made some simplifications to divide the state up into
"independent" parts that helped speed things up -- are there other ways of
dividing things up like this?  This is way simpler than a human;  but the
walking motion that it developed was really bizarre but looked effective
and very 'organic' -- nice for animation or cool demos :)

> What did you have in mind for linear regression?  That the torque would be
> linear in the angles and angular velocities of the joints?  I can pretty
> much guarantee you that won't work.  Also, you need to tell it the "right"
> torque for a bunch of angle/angular velocity combos.  Where are you going
> to get that data?
Ack;  yup - weighted linear regression would fit, but data is probably
tough to get for physical modeling.  If you just wanted to "cheat" and
move the skeleton around you could do something -- but at that point you
might as well lerp between motion-capture data.

> Neural nets are a representation, not a learning technique.  It's common
> to choose the weights of a NN using policy/value iteration, evolution, or
> the standard backprop algorithm.  For the backprop, you'll again need
> training data.
Right - I usually think backprop right off when thinking of neural nets,
but you're right that you can use whatever you want.

> What do you mean by "simple search"?  Given the above, I doubt anything
> that counts as simple search would work.
You can perform 'simple' search over the weights of the neural net (or
whatever) attempting to minimize whatever your objective function is.
I'm at a loss as to what that objective function might be, although I
think one could come up with one.

> >  In a class project last year, we "taught"
> > an airplane to fly itself in a knife-edge, etc. using neural nets
>
> That's much easier than walking.
Exactly, which is why I'm interested.  Aircraft are really stable inside
basic flight -- lol but the rolls looked ugly in a Cessna 172. :| But even
for something "nice and simple" the neural-net representation wasn't
exactly ideal;  they're very sensitive creatures *sigh*  <<flashback>>
*shutters*

> > The --really-- great/horrible
> > thing about most of these algorithms (and you could adapt GAs to do this)
> > is that they usually give you a fat lookup-table that defines exactly what
> > output to use for a given input.  i.e., current state goes in --> joint
> > velocities come out.  Very very easy to implement, and very very fast at
> > runtime.  The trouble, of course, is designing the character model and
> > then coming up with this table, which for a large input space [e.g., if
> > your input is the state of every joint] your table will be -huge-;
>
> A lookup table is a representation, but only one possible representation.
> A neural net is far from a "huge lookup table."

Yup.  In fact I thought there was a suggestion that neural nets provide an
'optimal' (in some sense) compression of data -- can't remember the
specifics... any idea what I'm thinking of?  It may well be that neural
nets -are- a great way to store the finished policy (or whatever you want
to call it) but depending on the number of nodes/arcs, I don't know how
fast this would be for doing real-time physically modeled humanoids in
ODE.  Of course, Moore's Law might fix that.  If it's just two-layers and
you add a step to delete low-weight arcs, then it's probably fine for a
handful of characters.  A squashed table is less accurate, but it's quick
and painless (thank goodness!  The control code for the helicopter UAV
we're working on isn't very long and its fast -- which is good, because
the navigation software is a processor hog :) [which is pretty easy on a
Pentium 266 :| ])

> For those who aren't afraid of reading a Ph.D. thesis, I'd suggest reading
> those from the MIT leg lab, especially Mike Wessler's Ph.D. thesis.

Spiffy - I'll check it out.  I'm just a student -- still coming up with
lots of goofy ideas that sometimes work really well, and some that don't
work at all, but such is the way of learning :)  lol

I'm interested in the problem as more of a control issue than an animation
one. i.e., if I tell "Bob" to do a backflip by giving him some reasonable
specification for one, then I'd like his policy to start spitting out
controls that will move him through the necessary states to complete it.
Far from saying that the GA/Neural net approach is bad (it's actually
really cool from a biological perspective), I'm only saying that there are
lots of ways that could be tried and that ODE would be a great way to try
them. Their setup was for offline animation;  I just wonder if a genetic
algorithm would be able to explore a sufficient space of possible
organisms that it could create a "super brain" able to do lots of
different things.  Maybe it can -- in fact I hope it can.  Being able to
specify a handful of actions to your computer game NPC and have it do
really unintuitive things (like balance on uneven terrain) would be
spectacular.  Maybe you'd only have to control the legs and hip to do
this?

Regards,

AC