Follow Slashdot blog updates by subscribing to our blog RSS feed

 


Forgot your password?
Close
typodupeerror
×
Programming IT Technology

Mutating Animations 218

Posted by michael from the learning-to-fly-but-i-ain't-got-wings dept.
Weird_one writes "Discover magazine's current issue has an intriguing article involving using genetic algorithims to evolve an animation of a walking individual."
This discussion has been archived. No new comments can be posted.

Mutating Animations More

Mutating Animations

Comments Filter:

  • Just wait for the game with this feature... (Score:5, Interesting)

    by anttik ( 689060 ) on Saturday July 19, 2003 @03:07AM (#6476944) Journal
    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.

    • Jobs (Score:4, Funny)

      by Anonymous Coward on Saturday July 19, 2003 @03:11AM (#6476956)
      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!"

    • Re:Just wait for the game with this feature... (Score:4, Interesting)

      by Anonymous Coward on Saturday July 19, 2003 @04:01AM (#6477074)
      "When CPU's will become fast enough to use this level of learning on the fly"

      This does not have to be done real time to work. Most likly you would just need to compile the AI once for an enviroment and just record the results of the last generation to a file to be used later.

      • Re:Just wait for the game with this feature... (Score:4, Interesting)

        by brianosaurus ( 48471 ) on Saturday July 19, 2003 @06:55AM (#6477371) Homepage
        Nah. Cuz then when your character gets killed, you'll try something different and eventually beat it. But if i can learn what you're doing, it will adapt and respond smarter on your subsequent attempts.

        Years ago I wrote a Tcl-scripted netrek hockey bot. I could reload its script on the fly, so its behavior could change. Early on people learned that it just shot towards the goal everytime. Then all of a sudde, during a game, i loaded in new code that passed to a teammate instead of always shooting on goal. The other team was floored, as the perfectly executed pass led to a goal.

        Sure it hadn't used some advanced AI (rather it was trivial and totally artificial), but it was enough to fool some of the people.

        Preload the AI with enough info to make it interesting when you start the game. But if it can learn enough (not necessarily in real time) to come back and bite you in the ass on level 12, its probably doing pretty well.

    • Re:Just wait for the game with this feature... (Score:5, Interesting)

      by fo0bar ( 261207 ) * on Saturday July 19, 2003 @04:25AM (#6477118)
      Download the E3 demo of Half-Life 2. In it there is a section where people are fighting alongside Gordon. This didn't look too spectacular until the presenter announced that these characters were NOT moving according to a script. The characters were given an objective (help Gordon get to point X), but were not given a path to take or any knowledge about the obstacles in the way. At that point my eyes opened wide, watching these people duck behind debris, covering fellow fighters, shoot-move-shoot-move... the movement and logic that they possessed looked either preprogrammed (which again, they say is not the case), or very human-like.
      • I saw the HL2 E3 demo and I was also amazed. Specifically the part when Gordon runs into a room after attacking an alien/zombie. Gordon barricades the door with a table and hides behind a washing machine. The alien trys to open the door with no success, then to my surprise, the alien tries the window. Now *that* is what I'm looking for in a AI/game.

        I'll hold my final opinion until the leak comes out, but it sure beats killing scientists and barny because they wont move out of the way.

      • Re:Just wait for the game with this feature... (Score:4, Insightful)

        by mr3038 ( 121693 ) on Saturday July 19, 2003 @05:47AM (#6477240)
        Download the E3 demo of Half-Life 2. In it there is a section where people are fighting alongside Gordon. This didn't look too spectacular until the presenter announced that these characters were NOT moving according to a script.

        Call me a skeptic, but I don't swallow that immediately. When Black and White was still in production there was some press that stated that the game had such a great AI that if the developers dropped a ball to the citizens, they started to play soccer by their own, assisted by the AI only. Did anybody ever see anything even remotely near that level of intelligence in the final release?

        Yes, that scene could really use AI to move all the characters but it remains to be seen if the scene is constructed specially so that AI can survive on its own or was the AI really intelligent? Don't expect too much. It's AI instead of I for a reason.

        • 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 devel
      • I think they were saying is that the characters actions are not directly scripted... i.e. "say this line, enemies come up hill, wait 3 seconds, start shooting at enemies", but instead, the actions are more dynamic and controlled by a.i. What they are NOT claiming (as far as I know) is that the a.i. learns and evolves as do the walking figures in the parent story.
        • What they are presumably doing is give the AI objectives and then add a large number of algorithms it can choose from in order to overcome obstacles.

          Objective: escort Gordon to helipad
          Obstacle: Gordon isn't moving
          Algorithm: Hang around, look for bad guys
          Obstacle: Gordon moved out of sight
          Algorithm: Follow cheapest path to Gordon's location
          Obstacle: Enemies ahead firing at Gordon
          Algorithm: Cover him. Kill bad guys.
          Obstacle: There is no path to Gordon
          Algorithm: Find closed portals that would lead to him, ope
    • But I think I'll still have to wait like 20 years for that.

      No, you'll have to spend 20 years playing the AI over, and over, and over again before it can even begin to evolve into something worth playing.
      /Timedemo 1 Might help.

    • Re:Just wait for the game with this feature... (Score:5, Insightful)

      by arvindn ( 542080 ) on Saturday July 19, 2003 @05:05AM (#6477177) Homepage Journal
      I'll assume that you're referring to the game adjusting to your playing style, because there are no real-time CPU constraints if you just want to evolve a generic entity. If that's the case, the more serious problem would probably be getting sufficient user input. Genetic algos usually take hundreds, sometimes thousands of generations, and since you cant wait for the user to play the game thousands of times you've got to improvise.

      In the case of board games, we've had learning algorithms for a long time now. I remember Fritz4 (chess program) having it 6-7 years ago.

      • Given the number of people that play counter-strike, I would think that there would be sufficient user input to create bots that learn to play the levels and against people very well and in a human like fashion.

        Of course in order for it to work really well, you'd have to have some sort of distributed system of learning, sort of like a seti program for CS bots, but I'd think if you even had a dedicated group as small as 100 people each willing to play 100 rounds of counterstrike, you could get pretty damn
    • "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."

      No, make the bots start from scratch, that way a new player can get use to the controls by shoot fish in a barrel(literally?) and as the bots evolve, so will the players skill in shooting and hunting them... it could work. :)

    • Re:Just wait for the game with this feature... (Score:4, Insightful)

      by Trinition ( 114758 ) on Saturday July 19, 2003 @06:55AM (#6477370) Homepage
      But the point of the article was not that the characters learned to walk on the fly. It was that no one had to program these guys how to walk.

      So, game makers no longer have to record a real person's movements, or formulate the movements themselves. They just let generations of these things learn in a "lab" setting. Once they've got the result they want, they can then save the settigns and use it in the production game without the need to "learn on the fly". You don't have to have a fast CPU to use it in a game. This is a development tool that saves time on making a walking algortihm that will look artificial. Instead, you make a computer come up with that walking algorithm for you.

      The best part is, you could apply this strategy to models that are entirely dreamed up. Maybe a 5 legged serpent? No one knows how one of those might walk, but this technique learn how one walks.

    • The CPU doesn't have to be fast enough to do the genetic code real-time, you do that beforehand, and develop the neural network over time through genetic algorithms, then simply attach that finished neural network to characters in the game.

      Imagine if stick-figure man from the example were given a sword, and the goal of staying alive (and standing) the longest... Eventually you could come up with some sort of genetically evolved fighters... Now that's something I'd love to see.
    • Game dev's don't want that, or at least not that level of 'smartness'; the strategies the cpu will come up with will be too smart for the player, thus making the game 'not fun'.

      I do agree with you; genetic algorithms have many uses in games (and design/engineering/programming etc), but ghame dev's already have to tune down their ingame AI because it's too good.

  • If you liked that.... (Score:5, Interesting)

    by Great_Jehovah ( 3984 ) on Saturday July 19, 2003 @03:08AM (#6476947)
    Check this out: http://q12.org/phd-movies.html [q12.org]

    Not quite as slick but a lot more amusing.

  • These must be stopped! (Score:5, Funny)

    by questamor ( 653018 ) on Saturday July 19, 2003 @03:10AM (#6476952)
    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.
  • Gussy it up all you want, Trebek... But can the stick figures fight? http://www.cutthroatsd.com/

  • Heathens! (Score:4, Funny)

    by Anonymous Coward on Saturday July 19, 2003 @03:15AM (#6476970)
    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!
  • I don't know, it sounds really cool and all, but in my experience, anything involving Genetic Algorithms consists of more hype than results. I mean, say you want to actually use this system to make an animation of, say, a guy waving 'hello'? You would have to write a fitness function that gives more points for animations that look more like they are waving hello, then run the simulation, probably get weird results, and then go back and modify the fitness function till you get something that looks decent.

    • Re:sceptical (Score:5, Interesting)

      by dustman ( 34626 ) <dleary.ttlc@net> on Saturday July 19, 2003 @03:38AM (#6477022)
      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.
      • I saw this in the SIGGRAPH proceedings back when it was new. The animated short movie "Luxo Jr" came after the work creating a single-muscled walker. They used a lamp geometry in the paper. The lamp taught itself how to hop along evenly, forward flip, backflip, go up and down stairs.

        Animators then went crazy with the idea and brought Luxo to life (through traditional keyframing).

    • Re:sceptical (Score:2, Informative)

      by Narphorium ( 667794 )
      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.

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

        Which is why they didn't :) Massive (the program they used to create and simulate all those battle sequences) is basically a huge neural net programm, with each orc/character having a seperate decision module which chooses a stance, an attitude etc. depending on where it is and where the other actors are (many elves close by and my squad got cut up-->run away!!). They then ran the sim and
    • Some of the other replies make some good points. I would just like to add that it seemsto me by one of the vids in a link from that article advertises actions that are less "controlled", and more "sporadic" such as the effect of a bioped model being knocked down to the ground or blown up. The site seems to suggest adding these unpredictable actions to your already strictly defined animation. So, you as the animator show your model how to wave "Hello", and then let the GA take over when you blow him up wi

    • it's like NP complete (Score:4, Interesting)

      by autopr0n ( 534291 ) on Saturday July 19, 2003 @04:00AM (#6477073) Homepage Journal
      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.

      • Re:it's like NP complete (Score:2, Informative)

        by 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.
      • "On the other hand, there are a lot of things that you can use GAs for. PORNO FOR THE PEOPLE! [autopr0n.com]" Heh....that's a classic example :)
    • What's more important is using this system in situations like WETA digital's Massive - the program that co-ordinates the battle sequences in Lord of the Rings. Instead of having thousands of orcs choosing among a few motion capture patterns to make up a charge of 30000 uruk-hai, they could have autonomous agents that actually know how to walk, and run, and get up after they trip over a dead body, or jump over the body of a fallen comrade, or whatever...

      tell the system you want it to work out the best way f
  • 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??

  • um.. (Score:2)

    by Naikrovek ( 667 )
    .. animations don't mutate, its the program that mutates and represents its new self with animation.
  • This sounds great, but you would then need a computer ten times as powerful to run the thing past all the patents etc. just in case it had evolved an idea somebody else had come up with!

    How does the law apply to 'discoveries' versus 'inventions'?

  • When watching the video, I was rather disappointed when the 20th Generation figure at the end didn't trip and fall off the edge of the grid.

  • Coolest Java applet ever: BioBloc (Score:5, Interesting)

    by FleaPlus ( 6935 ) on Saturday July 19, 2003 @03:40AM (#6477028) Journal
    The other day I stumbled upon what could quite possibly be the coolest Java applet ever [biobloc.net]. 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.
  • I doubt that "your favorite car" could be built by a genetic algorith. The whole idea is that you get something that you wouldn't expect. Now, you might be able to get some "interesting cars" out of them.


    For those of you interested in a small open source project that deals with genetic algorithms, using Artificial Neural Networks, check out this sourceforge project:


    http://sourceforge.net/projects/annevolve/


    Dan

    • Not only something you've never thought of though- GAs are also good at optimising things. How about a car gearbox that works out whether you are in a sporty mood or not, and shifts automatically? How about a car tailored to your body size and shape? How about one that designs the engine characteristics and matches it to your prefered driving style. Perhaps you like cruising, or perhaps you like accelerating upto 65 and then cruising, how about it gears the car for that, and ignores top speed. etc. etc.
  • then will we get smarter OSs that learn to blue-screen all by themselves?

  • Its more difficult than one thinks... (Score:5, Informative)

    by arvindn ( 542080 ) on Saturday July 19, 2003 @03:45AM (#6477037) Homepage Journal
    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 (Score:4, Informative)

    by daedel ( 625142 ) on Saturday July 19, 2003 @03:46AM (#6477039)
    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.
    • I have a feeling that nanotech + genetic algos can be particularly deadly. One of the constraints for GA is that we can't afford to have population of billions as nature can. With nanotech that might be possible, and then who knows what might evolve?
    • I am never sure whether to be amused or disgusted when I see somebody hold up Michael Chricton for his "insight" when he has, essentially, just ripped off well-known -- and better developed -- ideas from real science fiction writers. He's a hack, he doesn't get the science even remotely correct, and he doesn't make up for it in dialog or plot.

  • Non-GA Approach (Score:1, Interesting)

    by Narphorium ( 667794 )
    Ken Perlin created a similar technology which procedurally animates characters walking using his Perlin Noise functions.
    While this isn't technically a GA approach, it does provide simialr results in real-time.

    Check out his cool applet [nyu.edu].

  • Levels of thinking (Score:3, Interesting)

    by autopr0n ( 534291 ) on Saturday July 19, 2003 @03:55AM (#6477062) Homepage Journal
    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.
  • Here [naturalmotion.com] is another movie (mpeg, 1.5 MB) demonstrating a set of legs learning to walk over time.
  • Reading the article, I was strongly impressed with what a good, ground-level introduction to the concept of "what is genetic programming". I think that showing the science applied to a seemingly simple, common concept (walking, and specifically animating virtual walking) really helps make the big concept here easier to understand.

    Good article.

  • Video Clips from Natural Motion (Score:5, Informative)

    by gopher_hunt ( 574487 ) <slashdot@0db.us> on Saturday July 19, 2003 @04:03AM (#6477080) Homepage Journal
    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.

  • Genetic Algs, Boids and artificial life (Score:3, Interesting)

    by krahd ( 106540 ) on Saturday July 19, 2003 @04:04AM (#6477085) Homepage Journal
    When I read the article, it immediatly made me remember the Boids [red3d.com] which are a computer model of coordinated animal motion such as bird flocks and fish schools, first introduced by Craig Reynolds [red3d.com]. 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 [channon.net] 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!

  • Karl Sims' Work (Score:1, Informative)

    by Narphorium ( 667794 )
    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].
  • 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.
  • http://www.sodaplay.com/constructor/player.htm 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.

  • 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.
    • sodaplay always looks to me just like xspringies - an x windows spring/mass simulation thats been around for quite a while. Its quite a fun thing to play with - you can take one of the defined models and change gravity, the strength of the springs and so on and see how it works.

  • "genetic algorithms are increasingly being harnessed for real-world tasks such as designing more efficient refrigerators"

    Wow. Walking refrigerators.
  • Here's an evolution software for MacOS X (and a nice walker screensaver too!)

    http://www.spiderland.org/breve/

  • crawling or doing somersaults (Score:4, Funny)

    by aardwolf204 ( 630780 ) on Saturday July 19, 2003 @04:31AM (#6477129)
    "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
  • Is it far fetched to give an AI bot the ability to test a new function? Could we take a bot and give it the ability to test program functions themselves? Hook this bot into an internet CVS data base and let it test code for functions. The bot could request code for speach synthesis, remote sensing interpretation of images, and all the other code requirements to develope a primitive awareness.

    Perhaps the way to develope real AI is only possible when the AI creation can request code to enable functions. Stra

  • not the same, but different (Score:4, Interesting)

    by jefu ( 53450 ) on Saturday July 19, 2003 @06:14AM (#6477282) Homepage Journal
    I managed to finally put my genetic grammar program grammidity [sourceforge.net] up on sourceforge. It should work pretty much as packed up, on linux - though it does require povray for the 3d examples and timidity for the sound example.

    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.

  • My mac has a screen saver that does that. Whoop-de-friggin do. (the screen saver is cool. this posting masquerading as news is not.)

    This would hae been news back in the 1900s ;). Get over it.

  • The appeal of genetic algorithms (Score:3, Informative)

    by Neuronerd ( 594981 ) <konrad@ko[ ]ing.de ['erd' in gap]> on Saturday July 19, 2003 @07:05AM (#6477391) Homepage

    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.

  • Reminded me of sodaconstructor (Score:3, Interesting)

    by Trinition ( 114758 ) on Saturday July 19, 2003 @07:06AM (#6477394) Homepage
    When I read this article, my mind immediately conjured up sodaconstructor [sodaplay.com]. 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.

  • It's for beer too! (Score:4, Interesting)

    by Tsu Dho Nimh ( 663417 ) <abacaxi.hotmail@com> on Saturday July 19, 2003 @07:30AM (#6477433)
    And that method designed one seriously cool refrigerator [enginsoft.it].

    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.

  • Proof positive that with enough intelligent design and a keen eye for the result you're aiming towards, you can have a carefully manipulated, narrowly defined creation take on properties that look just like they evolved, if you stringently ignore the fact that they were intelligently designed, keenly aimed, narrowly defined, and heck, made in your own image. Now if they could only get the stick figure to say, "I am fearfully and wonderfully made."
  • Shouldn't the same development process be possible to use for robot controller SW? You will of course have to change the physiological input parameters (the robot you are constructing will most likely NOT have the same muscles as a human body), but the process should be the same, and the resulting controlling algoritm would be better at controlling the robot walk (move) than a human-constructed program.

  • Don't get too excited (Score:5, Interesting)

    by SystematicPsycho ( 456042 ) on Saturday July 19, 2003 @08:47AM (#6477548)
    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.
    ---
    • Lemme get this straight: you're saying that GA's basically just order the phase space of all possible, correct, postures and put them in the right sequence?

      If you are, then you're wrong. GA's specifically don't go through the whole phase space. The whole thing about GA's is that they are a short cut through the phase space, with the selection process cutting off the [algorithms leading towards] dead ends.
      What GA's do is to cut down on the paths which lead into the phase space of possible answers which aren
      • I meant what I said -

        "Genetic algorithms work by minimizing the amount of searching needed in a search space..."

        The key word is minimizing. You're wrong, GAs start off with the entire search space (initially) and during evolution the search space is minimized eventually leading to a local or global optima. If you didn't start with the entire search space in the beginning then you wouldn't be conducting a proper search - as you wouldn't be looking at all the possible solutions to begin with.

        Say you want
  • The demos mostly show the figures being hit, blasted, or shot. Maybe that's to appeal to game makers, but it suggests that the figures still have a rather limited repertoire. I'd like to see more gymnastics and other complex body movement, not just the physics model of a jointed body crumpling.

  • evolution on your pc (Score:2, Informative)

    by niff ( 175639 )
    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

  • Walking is solveable by hill-climbing (Score:4, Interesting)

    by Animats ( 122034 ) on Saturday July 19, 2003 @12:59PM (#6478850) Homepage
    Karl Sims did this about fifteen years ago, although he had to use a Connection Machine back then. It's appeared in a few games, screen savers, and such. The main insight here is that walking is solveable as a hill-climbing problem. Any of the usual hill-climbing algorithms (neural nets, genetic algorithms, simulated annealing, etc.) can do the job.

    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.

  • What you are basically looking for is a controllable way to make a character traverse a route.

    I recall seeing a video some time back where someone was trying to make some swimmers and walkers from blocks tied together with a simulated spine. The swimmers were great - they eventually evolved into something resembling fish.

    The walkers, on the other hand, took advantage of an error in the scoring system. Since they were graded on the distance that they moved, most of the walkers evolved into tall and skinn

    • Actually, GA's can very easily give you that...all you have to do is tweak some of those 700 parameters (make that muscle a bit tighter, that bone a bit heavier), run the sim and hey presto, a gait which matches the physiology of the character.

      Not only that, but you can tweak your fitness algorithm (the selector) by saying that a walk where the shoulders move sideways more is a better walk.
  • It is kind of peculiar that all of their demos [naturalmotion.com] have a rather quick and abrupt hit/fall/tie/don't move much animation sequence. At first it is amusing but it appears all the animations are like that. Thought I'd point that out.
  • If you attached a 3d engine onto CYC, you can trail and error, learn how to use limbs you attach onto a robot. Eventually its using the best result as it learns to grasp... Then when it judges weight/shape/density/wind, and throws, it can learn how to best hit a target.

    I'm interested to see which AI is seen first. We'll probably have both versions of AI down the line though. I wonder if there are any more AI possibilities.

  • While this is pretty cool, it's nothing like "real" evolution. They started out with a humanoid figure and gave it a bunch of parameters and asked it to walk.
    What they didn't do was say things like:

    - the figure has to live on a planet with a certain amount of gravity
    - food may or may not be plentiful
    - temperature can change
    - must be durable over many years and able to handle many terrains
    - give no shape or composition to start with
    - and so on...

    Sorry, these models are just cool toys.

Slashdot Top Deals

A morsel of genuine history is a thing so rare as to be always valuable. -- Thomas Jefferson

Close