Evolved virtual creatures (evolutionary programming, 1994) | Hacker News Reader

Evolved virtual creatures (evolutionary programming, 1994)

archive.org

31 pointsderwiki16 comments

(shameless plug:) here's a paper I worked on where we used evolved neural networks to control a robot (simulated, hoping to reproduce on the real robot soon):

http://arxiv.org/abs/0907.1839

I've been fascinated by this idea since before I saw Karl Sim's work. My take on it now is that it is something that could really break out, but there needs to be some hard-ass work on scaling, and on how to apply the technique effectively. The hardware we have now is so off the charts compared to 1994, you would suppose that everything would be easier -- but not really. Evolution is one application that can really, really eat up every ounce of CPU you throw at it, and still scream for more.

But flops aren't the sticking point, at least not yet. What is extremely difficult is finding ways to map evolutionary techniques to real-world problems effectively. It's just such a radical way of thinking that it tends to work at cross-purposes to the 'normal' patterns of engineering.

I can elaborate if anyone cares.

Very interesting, I've done work evolving neural networks for biped walking. As far as I know, usually researchers use monolithic NNs, why did you use 22 separate NNs? I've never seen anything like that, opens my mind up to some new NN architectures.

All evolutionary approaches seem pretty susceptible to local optima when tackling ambitious problems like biped gaits. You maintain diversity through demes and use incremental evolution?

One thing I hate about research in CS is that rarely is the source code provided to reproduce the research. I spent 3 months unable to reproduce the seminal Reil + Husbands biped walking paper (Reil went on to found NaturalMotion, which makes natural motion for CGI in movies). I swear they used some sort of voodoo magic. Is the source available for your simulator?

This reminded me of the game "Creatures". The artificial lifeforms the game revolves around use complex neural networks (with a few interesting twists).

"Creatures can learn a simple verb-object language, either via keyboard input from the user, or by playing on a teaching-machine in the environment, or from interactions with other creatures in the environment." http://www.cyberlife-research.com/cyberliferesearch/Creature...

I had the pleasure of doing some genetic programming research last year. It was lots of fun.

The most impressive use of simulated evolution that I've seen recently was a paper which describes the evolution of proteins, how this evolution mirrors a simulated annealing algorithm how this behaviour forms species.

http://www.pnas.org/content/106/6/1869.abstract

For genetic programming in general there was a paper in Science this year which is beautifully written and describes how physical laws appeared in the output of a genetic program applied to experimental data:

http://ccsl.mae.cornell.edu/natural_laws

If anybody is interested in genetic programming the following free book is very practical:

http://www.gp-field-guide.org.uk/

> how this evolution mirrors a simulated annealing algorithm how this behaviour forms species.

Before we did the full-on evolutionary stuff, I was fiddling with simulated annealing. There's definitely a connection.

It's all a subset of global optimization really. What makes evolution so fascinating is how it seems (at least in real life) to be able to direct its own path towards interesting solutions to particular problems. It's sort of like this mad genius, who keeps shouting brilliant things at you, but never listens. So you can never ask him a question -- you just have to set things up so he'll want to find an answer to the question you wish you could ask.

Jeffrey Ventrella and Brian Dodd expanded on these ideas in 1996 with one of the early PC games based on genetic algorithms (at Rocket Science Games.) http://www.ventrella.com/Darwin/darwin.html

Ventrella's main page is worth a look http://www.ventrella.com if you're interested in examples of genetic programing.

Simply wow. Is there any follow up to this research ?

It's really disappointing that the most impressive demo of genetic programming is so old...

Not really. It demos very well, but it's a difficult area, and there's not much real-world application (like most other a-life projects).

The guys working on EA's Spore considered evolving their creature animations, but opted instead for retargeted animation generated by hand. http://forum.spore.com/jforum/posts/list/28338.page

There are also procedural animation techniques, where you have a fixed skeleton and you are trying to find an animation that satisfies user-specified constraints, but that is really more of a motion-control topic.

I recall a professor of mine saying that Karl Sims's project is a popular choice for a final project in his advanced graphics course, but he tries to discourage it, as it turns out to be deceptively difficult to implement in a semester, even for particularly capable students.

John Koza at least as late as 2004 was writing about 'human competitive' GA results:

http://www.genetic-programming.com/jkpubs2004.html

There have been attempts to reproduce it and expand on it: http://ero.matfyz.cz/ (The demos here are really slick) http://www.cs.bham.ac.uk/~txm/creatures/index.html

But in general, sims' results are still among the most impressive ALife demonstrations.

Someone did a real world thing similar to this using a 3D printer. They evolved their creatures up to a certain level in simulation then made them real with a combination of 3D printed parts and manually inserted motors.

I've seen the video before and it's kind of cool, can't find the link now though. Anyone?

Something like this Google Tech Talk, "Polyworld: Using Evolution to Design Artificial Intelligence"? http://www.youtube.com/watch?v=_m97_kL4ox0

The DevoLab at Michigan State University is doing ongoing work in this area. At least one researcher (Jeff Clune) is looking at evolving generative encodings for neural networks, using the gait of virtual creatures as a sample problem.

http://devolab.msu.edu

I have to say that generative encodings are the most exciting new development of genetic algorithms.

Basically, the idea is this: Typically in GAs, the genotype (the bits that make up the genome, the ones that undergo selection and recombination) maps directly to a phenotype (one to one).

So if you were going to evolve a brain, there would have to be one gene for each connection in the brain. The problem is, such a direct 1-1 encoding can't scale to huge brains. For example in the human brain there are trillions of connections (synapses), which would mean searching a trillion-dimensional space (unfathomably difficult). Nature's solution is to use development, where a brain grows over time, where the genes don't directly specify each connection, but the blueprint for how a brain should grow.

So, in generative encodings in GAs, the principle is simlar. An indirect (or generative) encoding is where one gene can represent an aspect of a developmental process instead of directly specifying each component. In some ways it's similar to how in engineering you reuse components when making a building; if the manufacture of each nail had to be specified completely separately a project would be overwhelming.

I haven't heard of generative encoding before -- it sounds really cool. I could imagine something similar done with Genetic Programming. You could design a DSL (domain specific language) that is capable of building Neural Nets and then perform GP on programs written in the DSL. This could take the pressure off having to design a good development algorithm -- the GP would would do that for you.

Reply on news.ycombinator.com