Saturday 29 January 2011

BoxCar 2D

BoxCar 2D is a neat little evolutionary algorithm, that over time evolves dune buggies (inside a physics engine) that have to traverse an ever more rugged landscape.

BoxCar 2D screen shot
The little plateaus in the maximum fitness achievement give a lot of information about the environment. Will it ever get over that nasty spike at 396? Yes! But then there's that steep hill at 420... It finally powered over that at generation 39. But how long until it passes that gully around 490? At generation 54, it hauls itself out, and gets as far as the next bad obstacle at 529. Even after 700 generations, it can't get past that one... (Okay, I've been running this for too long, I admit. It's quite hypnotic. And it's fun watching later generations just power over obstacles that were literally insurmountable by their ancestors.)

average fitness over 400+ generations
What this shows is a combination of the power of evolution, and the restriction of a fixed representation. The algorithm can get so far, but to get further, there needs to be more novelty available. Look at the graph of average fitness. It rapidly shoots up to several 100 (here, fitness = distance travelled), but then it's just a noisy constant, with no overall improvement. Looking at the vehicles produced, it's easy to see why. They rapidly find good solutions within the constraints of a rigid octagonal body with wheels fixed to the vertices, but can then go no further. Watching the cars race across the terrain, it's clear they need more, maybe a flexible body, maybe something else. But they're locked into the one representation: that needs to change, to develop, too. I look forward to something like BoxCar 2D but with added evo-devo!

No comments:

Post a Comment