Slashdot Mirror
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."
← Back to Stories (view on slashdot.org)
← Back to Stories (view on slashdot.org)
When CPU's will become fast enough to use this level of learning on the fly, it will be great for gamers. Maybe the enemies don't have to learn walking, but learning strategy is a different thing. If they learn strategy by themselves and not by pre-programmed AI, I bet they will be more creative and a tougher opponent.
But I think I'll still have to wait like 20 years for that.
Not quite as slick but a lot more amusing.
Genetic algorithms must be stopped, and NOW
Who knows how soon it will be before these things gain the ability to work in the real world. It won't be long I tell you, before you look around and the entire PLANET will be full of these devilish unnatural creatures, all based on GENETICS.
But I think I'll still have to wait like 20 years for that.
Not if you listen to Steve Jobs in senile old age...
"This 2.0 GHz G6 runs at 1000 times the performance of an 8.9 GHz Pentium X!"
Evolution is a fraud made up by the godless devil-worshippin' computer scientists! Only God has the power of algorithm creation! The Bible clearly states in John 24:5 that God is the creator of the binary search, the hash table, the half-adder, the for loop, and matrix multiplication! You will all burn in Hell!
Yes.... now they can finally make better 3D CG porn now that they can simulate and even teach computer how to have sex in better ways and different positions. Hey, isn't the whole point of "EVOLUTION" to "REPRODUCE" more offsprings??
How would this be any easier than doing keyframed animation with inverse kinematics?
I read something about this idea a few years ago. I'm pretty sure it was by the guy that did BMRT... a thesis paper of his or something.
Basically, the redid the animation of "Luxo" in pixar's animation short. "Luxo" is the bouncing desktop lamp. Making animated characters (even those that aren't human) move "nicely" is quite hard. It takes a lot of work.
For their project, the specified the constraint: That Luxo must move from point A to point B, and that's all. The only input the model had was "how much force to use on each joint at each particular time". So, they were animating its "muscles" with a genetic algorithm, and also running a physics simulation on the system. (They assigned mass to the individual components, etc).
It evolved several techniques of locomotion: The "standard" bouncing hop (which the "real" luxo does), dragging itself across the table, somersaulting, etc...
In short, they came up with good looking animation, without requiring much user input. And in the end, they had a genetic algorithm which could make Luxo walk any distance, without requiring the work of an animator.
This is important, because although its relatively easy to just loop an animation, it looks rather unnatural.
The other day I stumbled upon what could quite possibly be the coolest Java applet ever. Once you start the applet, you assemble "bioblocs," which are 3D creatures assembled from connected blocks. Once you've assembled your creature, you can have it use genetic algorithms to try to learn how to most effectively walk, run, jump, and turn around using the blocks you've given it. I assembled a snake-like creature the other day, and was intrigued to see that it evolved a walking movement very similar to that of a sidewinder's.
In addition to assembling your own creatures, you can also load creatures that others have previously assembled, as well as enter your creatures into contests. A lot of the previously assembled creatures are -very- impressive, with movements quite similar to those evolved in nature.
Think of the battle scenes in LOTR for example, 10,000 orcs is not something that you want to be keyframing by hand.
then will we get smarter OSs that learn to blue-screen all by themselves?
h-t-t-p-colon-slash-slash-slash-dot-dot-org
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 . 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.)
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.
You know what I always found interesting. It's like these systems of thinking create newer systems of thinking. Evolution created Neural networks, and eventually created neural networks that can think and create things much faster then evolution (the human mind)
Then the human mind goes and creates digital computers, which again can do things the Neural network can't (and vise versa).
Anyway, just thought it was intresting.
autopr0n is like, down and stuff.
An NP complete problem is one that takes non-polynomial time to find the optimal answer, but can be verified in polynomial time. A genetic algorithm is similar, you need to have a fast fitness algorithm, or an operator who does the selection for you. If neither of those things are practical, then you probably shouldn't use a GA.
On the other hand, there are a lot of things that you can use GAs for.
autopr0n is like, down and stuff.
Heres the link to what they were talking about in the article. Walker Evolution
This next one shows off a lot more of what they can do. Mainly they abuse their models.
Natural Motion Show Real (14.5M Divx)
I love the tennis ball in the crotch clip. Insert bob saget joke here.
When I read the article, it immediatly made me remember the Boids which are a computer model of coordinated animal motion such as bird flocks and fish schools, first introduced by Craig Reynolds. Those where an example of emergent behaviour, where a bunch of independent moving things start moving in a coordinated way thanks to some "local guidelines" controlling their behaviour.
So, if every thing (boid) is telled to steer to avoid crowding local flockmates, steer towards the average heading of local flockmates and steer to move toward the average position of local flockmates, they start to move as a flock (!).
This approach of obtaining a more developed behaviour in an automatic (more accurately in an "emergent" way), is a lot related to genetic algorithms (GA) evolving an animation model, 'cos is exactly the opposite approach: In the first one the designer must specify the underlying mechanisms that permits the animation, while in the latter the designer must specify the result that is desired.
What I found more appealing of GA's approach is that the system can outperform the initial specifications, as is noted by a lot of papers in ALife. Some have developed an artificial world (in the paper linked above is named "Geb") where individuals can develope a (eventually) coordinated behaviour to survive (the fitnness function is an implicit
"survive function").
What would be cool is to use GA in a pre-determined way to evolve (in a explcit way) the basic behaviour that construct the coordinated mass beahaviours (like boids' flocking).
--krahd
mod me up, scottie!
mod me up scottie!
This freeware program 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 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.
I found this 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.
"We got some creatures that didn't walk at all but had these very strange ways of moving forward: crawling or doing somersaults."
#include beer.h
Im dreaming ofa big bndwdth, That can resist the
It doesn't evolve moving critters, but one of the included examples evolves 3d plants that compete for sunlight (kind of, sort of).
Another of the examples included allows the user to evolve midi files - with seriously odd results. Things may get odder though, I'm currently trying to figure out how to decompile midi files into source grammars then do crossover and mutation on them. Imagine Mozart crossed with Metallica.... Beethoven with the Brittany, or... I'd better not say, likely to get attacked.
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.
Googlefight "Slashdot Troll" against "BSD is dying" 303:229. BSD thus cant die.
When I read this article, my mind immediately conjured up sodaconstructor. With this applet, you create a bunch of "tendons" and/or "muscles" (line segments) connected together. You then adjust the function that controls the cycle of tension on each segment. The result is that you can make "creatures" that walk.
The thing that triggered this memory was the talk of "700 independent parameters". I pictured each muscle in this virtual walking body to be much like the line segments in sodaconstructor. The difference is that instead of a human thinking about how to adjust each one, random mutation adjusted them and evolution selected them.
The practical side of me says it would never fit into the usual slot they are stuffed into by kitchen designers, but I like it anyway.
Genetic algorithms work by minimizing the amount of searching needed in a search space by "evolving" candidate solutions and only evolving new ones from the best of the old ones. A candidate solution is evaluated against a fitness (of objective) function that assigns a fitness to a candidate solution.
Don't get to excited about the walking man - the difficulty and also art in Genetic Algorithms is finding a way to represent a candidate solution. The walking man isn't difficult to represent. To make it simple, pretend that the representation is like, work out a way to order the numbers 1..10 - where 1 == man crawling and 10 == man walking and the rest of the numbers in between are ordered to represent a certain posture. The genetic algorithm then searches through all the combinations and permutations of the numbers 1..10 until they are ordered - btw, instead of drawing numbers let's associate a number with a posture.
Now with this problem - think of a pool of numbers, each number associated with a posture and the Genetic Algorithm searches through the pool (of 100) until it finds the numbers 1..10 in order all standing next to each other.
---
Analytic & algebraic topology of locally Euclidean meterization of infinitely differentiable Riemmanian manifold
you should really check out framsticks.
you can even see the current generation walk or crawl in 3d.
one of the coolest programs ever
some screenshots here
Running, though, is harder. Steady-state running is reasonably well understood, but running on rough terrain remains hard. To control running well, you need predictive techniques - look-ahead, two-point boundary value solvers, and model-based control. This is where the insect brain leaves off and the lizard brain starts, and may be the beginnings of low-level AI.