Evolving Genetic Virtual Creatures

Inspiration

Back in 1994 Karl Sims developed his Evolved Virtual Creatures. More info here and here.

I have always found these sort of simulations fascinating, using the principals of genetics to evolve better solutions to a problem. For years I have wanted to try writing my own evolved creatures, but coding a physics engine to handle the movements and joints was beyond me so it was yet another entry on my to do list (until now).

2D Physics

For my virtual creatures I decided to start with 2D. I needed a general physics engine that takes care of all the individual world parts interacting and moving. Erin Catto’s Box2D has all the physics simulation features that I need to finally start experimenting with a 2D environment. Box2D is great. You only need some relatively simple coding to get the physics setup and then Box2D handles all the collisions etc for you.

Random Creatures

The creatures I am using are the simplest structures I could come up with that hopefully lead to some interesting movements. Creatures consist of three segments (rectangles) joined together by rotating (revolute joints in Box2D) joints. The size of the rectangle segments and joint rotation speeds are picked at random. Once the random creature is created it is set free into a virtual world to see what it does.

Virtual Creature

Many of them crunch up and go nowhere,

Virtual Creature

but some setups result in jumping and crawling creatures.

In only a few minutes thousands of random creatures can be setup and simulated. From these thousands the creatures that perform well are saved.

Performance Criteria

Once thousands of random virtual creatures have been created you need a way to pick the best ones. For these creatures I used three different criteria;

1. Distance traveled. The maximum X distance the creature travels in 5,000 time steps.

Virtual Creature

2. Distance crawled. The maximum X distance the creature travels in 5,000 time steps, but with a height restriction to weed out creatures that jump too high.

Virtual Creature

3. Height reached. The maximum Y height the creature reaches in 5,000 time steps.

Virtual Creature

The best picks become a set of creatures in the saved “gene pool”. If you have a large enough random set of creatures (say 10,000) and only take the top 10 performers then you do tend to get a set of creatures that perform the task well.

Mutations

Mutation takes a current “good creature” that passed criteria searching and scales segment length, segment width, joint rotation torque and joint rotation speed by a random percentage. The mutated creature is then run through 5,000 time steps and checked if it performs better than the original. If so, it is saved over the original and mutations continue. This process can be left to churn away for hours hands free and when the mutations are stopped you have a new set of best creatures.

For the creatures described here the features I randomly change are the segment widths and heights, the joint motor torques and the joint motor speeds (for 10 total attributes that can be tweaked by mutation). The user specifies a max mutation percentage and then each of the creature values are changed by


changepercentage:=maxmutationpercentage/100*random;
amount:=(MaxSegmentWidth-MinSegmentWidth)*changepercentage;
if random(2)=0 then amount:=-amount;
segmentwidth:=segmentwidth+amount;

The new attribute is clamped to a min and max value so as not to suddenly grow extremely long segments or super fast motors. You can also randomly mutate only 1 of the attributes rather than all 10 each mutation.

Choosing the right mutation amount can be tricky. Too high a random percentage and you may as well be randomly picking creatures. Too low a percentage and you will get very few mutations that beat the current creature. After some experimenting I am now using a mutation rate of 15% and mutating 3 of the attributes (ie a segment length, a motor’s torque, etc) each mutation.

Running on an i7-6800K CPU my current code can churn through up to 21 mutation tests per second. This screen shot shows 9 copies of Visions of Chaos running, each looking for mutations of different creature types, ie 3 segment distance, 4 segment height reached, etc etc.

Virtual Creatures

A mutation test requires the new mutated creature to be run for 5000 time steps and then comparing against its “parent” to see if it is better in the required fitness criteria (distance traveled, distance crawled or height reached).

Mutation Results

After mutating the best randomly found creatures for a while, this movie shows the best creature for distance traveled, distance crawled and height reached.

I will have to run the mutation searches overnight or for a few days to see if even better results are evolved.

4 Segment Creatures

Here are some results from evolving (mutating) 4 segment creatures. Same criteria of distance, crawl distance and height for best creatures. Note how only the white “arms” collide with each other. The grey “body” segments are set to pass through each other.

5 Segment Creatures

And finally, using 5 segments per creature. Only the 2 end arms collide with each other (otherwise the creatures always bunched up in a virtual knot and moved nowhere).

Availability

These Virtual Creatures are now included in the latest version of Visions of Chaos. I have also included the Box2D test bed to show some of the extra potential that I can use Box2D for in future creatures.

To Do

This is only the beginning. I have plenty of ideas for future improvements and expansions;

1. Using more than just mutations when evolving creatures. With more complex creatures crossover breeding could be experimented with.

2. Use more of the features of Box2D to create more complex creature setups. Arms and legs that “wave” back and forth like a fish tail rather than just spinning around.

3. 3D creatures and environments. I will need to find another physics engine supporting 3D hopefully as easily as Box2D supports 2D.

Jason.

One response to “Evolving Genetic Virtual Creatures

  1. I love Virtual Creature Evolution in concept. And recently I’ve been interested in how Kin Selection https://en.wikipedia.org/wiki/Kin_selection might affect it.
    That is an extended version of fitness where you are considered to get an implicit advantage from having close family members who do well. – It’s a plausible way to explain the evolution of counter intuitive behavior like empathy and altruism.
    And as far as virtual evolution is concerned, what it effectively does is to smooth out the fitness landscape: If there is a very narrow region of very high fitness surrounded by a lake of low or mediocre fitness, tiny changes will knock out “almost” great creatures, on one hand limiting diversity and on the other possibly accidentally deleting those great creatures from evolution (assuming you do not use elitism which you very well might)
    So anyway, the way to do it is basically to compare creatures based on a weighted sum of their collective fitness with their relatives. For that purpose you gotta calculate the Coefficient of Relation https://en.wikipedia.org/wiki/Coefficient_of_relationship between all your individuals. That’s presumably the hard part about trying to do this. I’m not quite sure how involved this ends up being.
    It’d probably be a lot more important in crowd tasks where you simulate the entire population at once but it might even give interesting new results in tasks for individuals.

    Another really interesting concept that’s already been tried more and was rather effective in many situations is the idea of novelty search. In it you keep a record of past behavior (the tricky part is to figure out what a good record is. If distance is your goal a simple one might be to just go for “What point did individuals end up at by the end of their lives?”) and a way to compare them (in this simple distance example you’d find the, say, ten individuals of the past closest in their end point to your current individual and ask how far away from those ten it got. This distance is what replaces the usual fitness score)
    This technique effectively asks individuals to explore the entire space of behaviors more or less evenly, much more effectively avoiding local optima.
    People also considered combining these novelty scores with classical fitness functions.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s