Mutating Animations

Weird_one writes "Discover magazine's current issue has an intriguing article involving using genetic algorithims to evolve an animation of a walking individual."

Re:sceptical

[Narphorium]

I think the advantage with genetic algorithms would be that once you have clearly defined a fitness function that allows a character to 'wave hello', you can easily evolve several more characters each with their own distictive wave with very little extra work.

Think of the battle scenes in LOTR for example, 10,000 orcs is not something that you want to be keyframing by hand.

Its more difficult than one thinks...

[arvindn]

In simple textbook situations illustrating the genetic algorithm, we simply represent the solution space as a string of bits, and cut it at some point and recombine them to form offspring. However, real world applications are a lot more complex. That's because an arbitrary cut-n-paste of solution strings is likely to result, with extremely high probability, in an invalid string. This is the problem of having a sparse solution space. In this particular example, suppose you represent the figure as a sequence of pixels and try to apply a genetic algorithm on that representation. You'll never get anywhere, because most sequence of pixels are meaningless.

What needs to be done to make the GA work is to develop a solution space representatin in which each parameter can be varied independently of the others. In this case:

The character's body plan involved 700 distinct parameters that needed to be optimized to teach it how to walk like a human. .

So its not like the computer learnt to walk by itself. There's a lot of hard work involved before you can even start the GA. Congrats to Reil.

<shameless plug> On a slightly related note, I'm about to start implementing a GA to develop a killer AI for gtkboard [sourceforge.net] . If you are interested in coding a GA, you are welcome to join :) (Of course it won't be anywhere as complex as the one in the article, but still lots of fun.)

Chrichton: Prey

[daedel]

I just got finished reading this book, and had to chuckle at seeing this article. The book is about a group of nanomachines given agent based programming called PRED/PREY which uses something like the genetic programming spoken of in the article. Of course things go awry in there somewhere, but it is an interesting, and moderately technical fiction on this subject.

Video Clips from Natural Motion

[gopher_hunt]

Heres the link to what they were talking about in the article. Walker Evolution [naturalmotion.com]

This next one shows off a lot more of what they can do. Mainly they abuse their models.
Natural Motion Show Real [naturalmot...irror1.com] (14.5M Divx)
I love the tennis ball in the crotch clip. Insert bob saget joke here.

Karl Sims' Work

[Narphorium]

Karl Sims has also done a lot of work with evolutionary graphics and animations.
Check out his web site here [genarts.com] especially the section on Evolved Virtual Creatures [genarts.com].

An incredibly fun example of this from 1997

[captainktainer]

This freeware program [the-underdogs.org] from Jeffrey Ventrella is an open-ended version of this. Small wormlike creatures evolve to find the most efficient, fastest method of locomotion through liquid. You can change various parameters to make it easier or harder for the little swimmers.

DarwinBots [libero.it] makes use of true genetic algorithms for propulsion, attack, feeding, social behavior, and evolution of multicellularity. I like Darwin Pond better, personally, because it's more stable and DarwinBots doesn't have the "cuteness" factor.

Because these figures are engaging in human-type motion in a reasonably believable 3D environment, I can understand how it's important- however, it isn't truly revolutionary in nature. It's just another step in the evolution (appropriate, ne?) of genetic algorithms.

Speaking of animations... fixed repost.

[Mantle]

I found this [sodaplay.com] link quite interesting to play with. Nothing to do with AI, but rather simulation of organic motion. Quite lifelike and it's fun to play with all the variables.

Re:it's like NP complete

[Anonymous Coward]

No, it's not similar at all: merely being able to evaluate the fitness function in polynomial time doesn't mean that you can determine in polynomial time whether any given solution is optimal. There are plenty of problems that are not known to be in NP (and hence not NP-complete) for which the evaluation of the fitness can be done quickly.

Re:Just wait for the game with this feature...

[brianosaurus]

Of course the scene was constructed to aid the AI. When have you ever seen AI that can handle anything you throw at it? Check the latest Turing contest (or whatever its called) to see how many winners there have been in the last eternity.

That doesn't mean that given that particular situation the AI can't hold its own (until, of course, you out smart it, you genius who has been blessed with being a free-thinking human being instead of a "simple" AI).

How long did it take these genius human beings to develop AI to this point? Of course its limited, but that works just find in games. So long as the AI's object is "kill everything that isn't a human-controlled player" as opposed to "make a brilliant pass to score a gooooooooooooooooal!", they do pretty well.

Eventually (at least according to Moore, and I can guarantee he (and/or his spawn) will still want to be selling CPUs 20 years from now!) machines will be able to kick you ass at pretty much anything you wish they couldn't.

The appeal of genetic algorithms

[Neuronerd]

The field of machine learning consists of probably at least some 1000 researchers worldwide. Genetic Algorithms in the way they are usually used are an algorithm for optimization.

The problem of optimizing: You have a set of parameters p_i. You have a fitness/ energy or objective function F that somehow measures how good you are doing. The algorithm is supposed to yield some p_i that lead to optimal performance, that is maximal F.

What is a good algorithm? Whereas some years ago people would write sentences like "my algorithm is better than your algorithm" we now know that without prior knowledge about the function to be optimized all optimization algorithms are equally good. So today you can only say ... my algorithm works better for this and that type of data because it incorporates this or that knowledge about the problem encountered.

Algorithms used Depending on what you know about the problem set you can then build various algorithms. The following are among the most common algorithms for optimization: Methods based on gradients (i.e. vanilla, conjugate gradients), Methods based on random search and genetic Methods.

Why this is a good example for using genetic algorithms Genetic algorithms completely ignore the gradient information. In the case of walking the gradient of the fitness function may be difficult to define. That is why this is a classical example of using genetic algorithms.

Why genetic algorithms are absolutely hopeless for more interesting problems Genetic algorithms do not obtain a lot of information. In Particular for example David MacKay shows that the number of bits per generation is very low (1 bit for asexual, sqrt(size(genome)) for sexual systems). This means that the information acquired per generation is very low and that to obtain human like abilities it would take forever.

For interesting problems other optimization methods must be used that use information from the environment in a far more efficient way. Without learning I guess there can not be human like performance.

evolution on your pc

[niff]

you should really check out framsticks [poznan.pl].

you can even see the current generation walk or crawl in 3d.
one of the coolest programs ever

some screenshots [poznan.pl] here