On Using Genetic Algorithms to Train Neural Network Driven Creatures to Walk in Flash

I remember seeing Karl Sims’ video Evolved Virtual Creatures a long time ago. I was completely stunned but unfortunately forgot about it for many years. I was reminded of it again last year when reading about training neural networks using genetic algorithms (Tom Mitchell’s Machine Learning is highly recommended) and decided to evolve my own creatures.

Preparation

Here is the first demo.

Genetic Algorithms - Ants

The task is to teach an ant to get to the end of the L-shaped corridor as fast as possible. All an ant is allowed to do (every frame) is rotate freely and turn on its forward thrust (acceleration). Ant’s behavior is encoded in its DNA consisting of several genes. Every gene prescribes what an ant does in the frame that corresponds to the index of the gene in the DNA. Specifically, each gene is a 3-bit number encoding the ant’s possible behavior:

var gene:int = dna[simulationStep];
var acceleration:Boolean = gene & 1;
var turnPositive:Boolean = gene & 2;
var turnNegative:Boolean = gene & 4;

The genetic operators used are not tuned for this particular application. What you see on the screen is one population of 100 individuals. It takes time but if you let them learn you’ll see that in the end they achieve the goal in the most optimal way.

Evolution

Encouraged by the result (also, it only took about 2 hours to code) I wanted more. Without further ado I present the walking creatures (after 300 generations).

Genetic Algorithms - Walking

The task here is to give physics-based (thank you, Box2D!) ragdoll figures brains to be able to move a certain distance. Following Ngo and Marks’ paper Spacetime Constrains Revisited I set out to make my own creatures in Flash. In short, I am using a genetic algorithm to train a neural network that controls motors in the creature’s joints. The fitness function is plainly how far a creature can get within a certain amount of time. The neural network used is very simple – it’s a single layer feed-forward neural network with the inputs being the angles at every joint, vertical velocity and horizontal distance traveled and the outputs the speed of the motor and the target angle of every joint.

Results

I was really happy to see results only after about 300 generations (it took a night though): a frog. Excited, I ran it again and again and interestingly, I only got frogs. I tried to change the fitness function a bit so that the creatures that touch the ground are penalized but didn’t get anything interesting. Also tried to make the torso a bit heavier and an inchworm-like creature evolved. If you like, you can try to evolve your own creatures, here’s the link to first generation (with a little bit of creativistic randomization to start with). At the end of every generation, the best DNA is traced so if you happen to get some interesting locomotion, please send it to me and I’ll post it here. (Source code to follow after a brief clean-up.)

Edit: Get the source code in the next GA post.

What’s Next

My plan is to try what behaviors will emerge with different shapes, physics set up, fitness functions or selection algorithms.

  • http://makc3d.wordpress.com/ makc

    damn that ants are slow… how many hours before they can actually get the job done?

  • http://www.ubervu.com/conversations/blog.glowinteractive.com/index.php/2010/02/on-using-genetic-algorithm-to-train-neural-network-driven-creatues-to-walk-in-flash/ uberVU – social comments

    Social comments and analytics for this post…

    This post was mentioned on Twitter by makc3d: genetically trained neural networks in flash, click here.

  • Arby

    Very interesting. I think the reason the walking one always ends up as a ground creature is that maybe you’re not evolving the “spine” of the torso? To me after running it only twice, looks like the torso segment rotates down quite easily and quickly. This would imply to me that gravity pulls at it, and it being hinged rather than “spine-like” sets up your creature to never be able to walk upright. We do not walk upright by balancing our upper body as if it were on a pivot. There’s lots of muscle all around to keep our “pivot” rather difficult to flex, really. So do a version where the pivot stiffness changes too.

  • http://blog.glowinteractive.com/index.php/author/jan/ Jan

    makc: I would give it a night, they don’t learn very quickly :)

  • http://blog.glowinteractive.com/index.php/author/jan/ Jan

    Arby: In my demo the joints are 100% stiff, therefore the creatures bend down by their own choice. Besides, as nature shows, there are many evolution steps between “ground” and walking creatures.

  • Hkhkhkhhk

    teste

  • http://www.facebook.com/heath.d.martin Heath Martin

    The going theory, as far as I know, for the evolution of bipedal locomotion was as an effort to save energy over long distances. Have you considered including an energy expenditure function to the fitness model? I don’t know what kind of data you can collect, but if you measure the change in angle of each joint and the load on that joint, you can use that to represent the energy expended. If you aren’t able to get the loads on the joints, you might be able to just use the absolute change in angle to approximate the energy expenditure. You might get something closer to bipedal locomotion if you express a preference for conservation of motion over speed.