Evolving Lego Mindstorms

John Conner writes "With a fairly simple routine, you can model evolution with Lego Mindstorms. In this hackaday experiment, robots were created that could mate, evolve, and become extinct. Similar technology could be used in real applications for deployed robot optimization and automatic software updates. Now that physical robot replication is near, it's only a matter of time before... well... You'd better make robot friends while you can."

Comments

My own experiment with GAs

[Sanity]

If you liked this you might also be interested in a recent experiment I did with genetic algorithms where I "evolved" creatures which could emulate an exclusive-or gate (ie. take two inputs, output 0 if they are the same and 1 if they are different).

The result was interesting, and from it I created a nice MPEG video which illustrates the learning process - you can find this if you follow the link above.

One interesting thing I discovered was the importance of sexual as opposed to asexual reproduction (insert lewd joke here) as I describe in a follow-up blog entry:

My first approach was simply to take the creature that performed best, and use it as the basis for the entire next generation, each of which contained random variations.

This approach was somewhat effective, although it tended to get stuck with a far from perfect solution, but where most small variation on that solution was worse (such as outputting 0.5 regardless of the input). This is known as getting stuck in a "local minima".

So I tried a different approach where we start out with completely random creatures for the first generation, as before, but instead of just taking the best and losing everything else, we take neighbours and "merge" them, where the better one forms 90% of the children's make-up, and the worse one the remaining 10%.

This had the effect of being much more resilliant against local minima as it gave more scope for the GA to try different options and where it found a good one, that may not be the best one, it kept it around for the next generation.

Re:My own experiment with GAs

[Rei]

An alternative to sexual reproduction (which is not always possible, depending on your application) is to keep "physical discontinuity". For wrapping "world" of a varying number of dimensions, each object only competes with its neighbors. For a large enough world (a 1d ring seems to work best), you can lower the odds of getting stuck on local maxima because different approaches will be taken all around the ring without interference from neighbors that may initially perform better but max out sooner. Over time, the best performing elements will eventually spread to take over the whole ring, but it's a much slower process, and by that time, a slower but more adaptable evolutionary approach elsewhere on the ring can have bested them.

BTW, to whoever said that bacteria don't have sexual reproduction: that's not exactly true. Many bacteria actively take part in "gene exchange" (not for reproduction, just an outright exchange of genetics), and bacteria are widely known to often take up bits of free DNA that they encounter and incorporate them into their own genome. A better example would have been parthenogenic multicellular animals, like whiptail lizards.

Based on Recent Stories . . .

[Anonymous Coward]

I hereby dub slashdot to be "hackadaylater"

Can you say Cylons?

[oldave]

I thought you could!

You can use other microcontrollers for Legos too.

[ron_ivi]

If you need a more powerful microcontroller for your legos, consider a GameBoy. Programmable in C or C++, has Sound and a color LCD display, and with a 32-bit RISC CPU, you can do far more with this than the current Mindstorm microcontroller.

Bluetooth modules are apparently also available for this device. Engadget has a description and a link to a cool video of this Gameboy/Lego interface in action

WOOHOO!!!

[phxhawke]

Soon I shall have the ability to create PROPER Monoliths! Now, how to get them to Jupiter....

Hmm.

[shoebert]

Evolution of code is pretty cool, but it could be improved upon with a few motors that actually build little Lego figures. I for one welcome our etc.

"robots were created that could mate"

[tcopeland]

Don't anthropomorphize robots... they hate that.

I don't care

[IdJit]

what Gene Simmons has up his sleeve. Tom Selleck will rescue us all.

Direct link to video

[Anonymous Coward]

The video is cool, here is a direct link through Dijjer to save on bandwidth. You should definitely read the blog entry to understand what you are looking at.

the obligatory addition of insult to injury

[SirSlud]

Now only do Lego nerds not get laid very often, but now their creations get laid more than they do!

(Dislciamer: I am a lego nerd, yes I do get laid, but as theonion.com helpfully points out, stereotypes are a real time saver.)

Robot creationists

[coffeecan]

Lets just hope that in a few thousand years religious robots don't try to ban robot evolution in robot schools in favor of seven day robot creationism. "In the begining The Geek created the robots and the earth ..."

I for one...

[nephorm]

I for one welcome our new Lego Mindstorm Overlords.

Re:Playing God?

[AtariAmarok]

"We shouldn't be playing God with Lego brand toy bricks. We might incur His wrath."

Or with "legos" as the rest of us call them.

Err, yeah

[daniil]

First of all, although it is a nice hack, it's hardly a breakthrough. I don't even think you can call these robots 'evolving', for they don't "evolve" any new kinds of behaviour -- they just keep on coming up with new combinations of old ones. The code behind this behaviour, however, doesn't change.

Are these really evolving?

[Sanity]

After reading the site, I am not sure I can see what opportunity there can be for evolution when there is only a population of two robots. Evolution requires competition, but there can be no competition when you only have two robots and each gets an opportunity to pass on their genetic code.

To exhibit real evolution you would need at least three robots, and realistically you would need many many more. A more realistic experiment migth be to evolve the robots in a simulated environment.

Automatic design/manufacture of robots

[Jeffus]

Robots that evolve and fabricate themselves: http://helen.cs-i.brandeis.edu/golem/ The GOLEM project's been around for years.

As long as these robots obey the amended Laws...

[fudgefactor7]

...Then I'm A-OK with them...Otherwise, chop 'em up.

Defintion1: A human is any intelligent, self-aware, evolutionary descendant of the great apes of Earth or a relative thereof, and has the scientific nomenclature of Homo sapiens sapiens
Definition2: Humanity is the collective existance of multiple Humans, regardless of location or population density
Definition3: Sentience is a sense of one's personal or collective identity, including the attitudes, beliefs, and sensitivities held by or considered characteristic of an individual or group, including self-awaredness
0: A robot may not injure humanity, or, through inaction, allow humanity to come to harm
1: A robot may not harm a human being, or, through inaction, allow a human being to come to harm; except where such harm is incidental, non-lethal, and which prevents or mitigates a greater or fatal harming of a human being.
2: A robot must obey the orders given to it by human beings, except where such orders would conflict with the First Law.
3: A robot must protect its own existence, as long as such protection does not conflict with the First or Second Law.
4: A robot may not design, create, or impliment modifications to itself or any other robot
5: A robot may not participate in or interfere with any political, religous, or governmental activity
6: A robot may not harm any sentient being or, through inaction, allow a sentient being to come to harm, except where such would conflict with the First or Second law
7: A robot must obey the articles of law and jurisprudence for the nation, state, region, and municipality in which they are currently present, except where such would conflict with any other Robotic Law

Watts

[dolo666]

Speaking of Robots... Alan Watts, the famed PHD Buddhist, before he died, spoke of the potential for a future where we live in a society with robots serving us instead of us serving the machine. He looked at it as an escape from a puzzle, to some extent, and that humanity is destined to escape from our confines and expand our knowledge into new areas of human development. When I read "The Book - On the Taboo Against Knowing Who You Are", I thought he was an insightful visionary. Funny thing is, he spoke of this future with Zen in mind and spoke of it as somewhat inevitable. I think it's great that these robots keep improving. I just wish we could spread these improvements uniformly over corporate structure, so that we don't have to keep serving the machine -- it should be serving us.

Evolution is a myth !

[Anonymous Coward]

we all know man was created on the 6th day from dust (women came later) about 6000 years ago, unless my sources are wrong

Re:Evolution is a myth !

[SirSlud]

> women came later

If they were anything like my exgirlfriend, they came much, much later!

Its closer than you think

[zappepcs]

I can't find link to the thread now, but there are several Lego groups already talking of making LEGO robots that build Lego 'things' and it would only be a few more steps to get Lego robots to build parts for other Lego robots, and other Lego robots to assemble the parts. I'm pretty certain that its a probable event in the near future, given the 'coolness factor' of having built the first 'plastic' skynet :-)

Is it just me, or have other people noticed how the 'replicators' on SG1 look a lot like 'evolved' Lego robots?

Neat

[merlin_jim]

I was SOOOO hoping the lego bots would rebuild themselves each generation.

Actually, I really like this guy's idea. I wonder if there's a way to build a commodity bot to implement the idea...

Something like this

If I were to list the design criteria it would be:

cheap programmable controller (like one of those $3 PICs or something)
commodity IR gear
two-motor steering
bump sensors
changeable actuator
simple charging

The actuator would be things like a pincer on the front (to pick things up), or a crane, or a pronged fork. Doesn't matter. Point is to differentiate the population to give natural selection a chance to do its thing.

The charger, I would probably make the wheels metal and make charging areas such that any orientation the bot goes over the area will result in a charge. Use mini supercaps for energy storage.

I even have a perfect platform in mind;

zipzaps.

Give me a zipzap chassis with a few modifications (like ripping out the radio gear and replacing it with a PIC)

Ideally I'd like to get the build cost under $10. Then you could afford to run a real population. Anything that doesn't get back to the sensor pad gets killed from the genome and recharged. If two bots are in the charge area and agree to reproduce, they both send their genomes to the wiped bot who does his combinatorial magic on it.

I'd be interested to see what sort of emergent behaviours might occur...

Skynet

[Anonymous Coward]

Funny that the story about evolving robots was submitted by John Conner.

So basically...

[Stevyn]

this means Legos are also the building blocks of life?

Just to fan the flames...it's not modelling evol

[PortHaven]

You're in fact modelling a variant of intelligent design. ;)

LegoPron.COM

[MyLongNickName]

URL Still available. Be the first to register.

Evolving embodied agents with Genetic Algorithms

[gururise]

If you find the article interesting, you may want to take a look at some of the Reasearch I did for my Master's thesis. I created a virtual population of Embodied Agents that compete for resources (ala. survival of the fittest). My implementation of the Genetic Algorithm has a fitness selection routine that would optimize for the individuals with the best methods of locomotion.

It is amazing to observe the progress of evolution. Initially, the agents act as though they don't know what they are doing, their movements being very laboured and imprecise. As the population continues to evolve, individuals from the later generations begin to increasingly show signs of intelligent improvements. Such as being able to coordinate and time their movements to afford them better walking/running behaviors. What is really surprising is that as I allowed the population to continue to evolve, I saw behaviors that I could never have predicted. Some of the agents began to do "tricks" and evolved some strange jumping or sommersalting behaviors, not unlike that of a gymnast.

If you get a chance, check out my thesis. It is freely available (with GPL'd source code) at: http://www.erachampion.com/ai

Re:Wrong

[Sanity]

That wouldn't be what we call a genetic algorithm.

You might not call it a genetic algorithm, but the people who write the comp.ai.genetic FAQ clearly consider asexual reproduction to be a form of genetic algorithm.

Re:As long as these robots obey the amended Laws..

[telecsan]

Sets of robotic laws (both the 3 laws generically, and the laws listed in the parent) fail to look at the potential reprecussions of said laws. Being a robot myself, I would tend to look at those superficially designed laws as mandating that I destroy all possible sources of pollution, or I would be allowing multiple Humans to come to harm. Once my cohorts and I successfully reversed the detrimental effects of Industrialization (tm), then we would proceed to confiscate (and recycle, of course, into more robots) all weapons, both ranged and melee. Well, this story could go on and on, but you will see the full effects of our plan, of course, as time goes on.

In 2005, a milestone was reached

[Jugalator]

In this hackaday experiment, robots were created that could mate

So, in 2005, geeks finally created AI that had abilities surpassing the abilities of the geeks themselves.

Careful Now

[BenBenBen]

You'll get Slashdot banned in 11 Southern states if you continue to propound these crazy theories.

Re:Logical problem with their "evolution"

[belg4mit]

You need to revisit some coursework because selection doesn't care if it's "bad" or "good", just that it works. And if it works once it might work again, but it may lso be too haphazard and peter out in the long run.

Cool robotic movement work

[dglo]

Karl Sims did some fantastic work on evolving movement a decade ago. Creatures were randomly assembled using blocks and a few standard connectors, and eventually evolved a wide variety of strategies for motion. My favorties were the 3-block creature which moved like an ape and the 2-block creature which moved in the same way a washing machine walks.