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."
If you liked this you might also be interested in a recent experiment [locut.us] 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.
by Anonymous Coward
on Monday March 28 2005, @11:43AM (#12066650)
The video is cool, here is a direct link [dijjer.org] through Dijjer [dijjer.org] to save on bandwidth. You should definitely read the blog entry to understand what you are looking at.
Very interesting, and I'll have to check out the link.
It's intriguing to me, though, that you mention two things which I thought were no longer thought in evolutionary theory:
1) it tended to get stuck with a far from perfect solution I know that one who plays with these things can tell when a solution is "far from perfect", but there's often no way to tell if one is getting "close to perfect", since the solution space is so damned huge, and the fact that the environment can not only change dram
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.
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 [cmu.edu] clearly consider asexual reproduction to be a form of genetic algorithm.
If you need a more powerful microcontroller for your legos, consider a GameBoy [charmedlabs.com]. 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 [engadget.com] modules are apparently also available for this device. Engadget [engadget.com] has a description and a link to a cool video of this Gameboy/Lego interface in action
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..."
But it honestly wouldn't be too far from the truth, right?
Except that, in this case, "God" is some dork in his underwear and a thinkgeek.com t-shirt. There's only ever been two "people" on the planet, one of them was Jesus (at least once), and the other looks the same as her mother, grandmother, great-grand mother, etc.
In all seriousness, I wonder if this isn't more an experience on collaborative learning than it is evolution? You have two beings with limited ways of moving, a simple communication proto
If people read that linked slashdot story, they would see that self-replicating robots are not much closer than when von Neumann wrote about them. The LEGO Mindstorm evolution is pretty cool just because Mindstorms is being used as a platform for this and since the evolution system is doesn't require an outside computer.
However, the small population used (2 bots) and the seemingly weak fitness function make me think that this project won't go anywhere fast (pardon the pun) and is just a genetic dead end. E
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.
The human body is just designed around a fixed number of atom types and a fixed number of genes. Clearly, we haven't evolved and cannot evolve in successive generations just by mixing these components in different ways.
Over a certain complexity level, emergent behaviors are formed in ways that were not designed. Emergent capabilities don't exceed the theoretical range of capability for the organism, but designing an optimum offspring turns out to be a devilishly difficult task, while genetics me
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.
...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
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.
Speaking of Robots... Alan Watts [wikipedia.org], 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.
With all the advances they're making in prosthetics these days, I'm guessing within 50 years, we'll be treating our bodies more like cars, and we'll regularly upgrade ourselves to be faster and stronger.
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?
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...
I get so many zipzap clones going to trade shows and the like. When they first came out they were a popular giveaway. I probably have five or six and only bought the first one (a radio shack Zip Zap from the second day after they were introduced)
I've been trying to figure out what to do with them. Other than generic cat toy. If my PIC programming was up to snuff I'd probably go for it.
Why oh why hasn't anyone invented an 802.11 general purpose IP device yet?
About 5 years ago I read a paper on an experiment with using sexual reproduction with simulated life. I wish I could remember the authors, because their results were actually interesting.
The way they set it up was to have a grid in which organisms lived (all simulated in a computer, of course). Each organism was controlled by a neural network. Males had eyesight, so they could tell what was in front of them a few squares. Females had a sense of smell, so they could tell when a male was around. (IIRC). In o
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. [erachampion.com]
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 [erachampion.com]
Karl Sims [biota.org] 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.
Meta bracketing the evolution of the use of Legos in the scientific community might be as fruitful as the use of the Lego Mindstorms set. Investigation is limited by the questions we ask and the tools we have at hand. The use of Lego "toys" and the meme that has grown up around them has alot to tell of what we can accomplish and how we set out to accomplish it. Over history at large, an example might be Euclidean geometry which funneled and defined much of scientific thought up to the time of Newton, and is now seen to be limited and antiquated. In miniture the use of Lego Mindstorms to investigate "serious" science in an interesting paradigm that continues to influence and grow popping up in diverse books and papers.
Although I'm posting this late enough no one will probably see it...
This isn't really evolution, since there is no determination of fitness. With normal GAs you (somehow) evaluate the "fitness" of the creature, which is typically used to drive how often, and with whom, the creature reproduces.
In the stuff I've done [heroicproportions.org], general lifespan is driven by genes, as are reproduction behaviors, movement and eating habits. Available "energy" i.e. food eaten, put additional limits on lifespan and mating. Thus, there are some "natural" fitness measurements, if a creature dies off before it mates, it wasn't fit enough... If it doesn't have enough energy to share with it's offspring, that allows them both to survive, it wasn't fit enough.
One of the more interesting genes I've been using lately is a "mutation rate". If I start out with some base creatures, that I know are likely to survive, but aren't great, they will frequently evolve to the point where they are co-existing with the environment pretty well, and once that point has been reached, their mutation rate drops to nearly zero.
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.
Why does evolution always catch more attention when it is played out in the real world?
Because we've pretty much squashed whatever native talent most people have for abstract thought (or for appreciating the fruits of thought experiments). Never mind that people bank on the the output of weather sims every time they pack up to go skiiing - but anything that requires some extrapolation to the physical world is just too much for too many people these days. I truly, truly lay that at the feet of the "it tak
My own experiment with GAs (Score:5, Informative)
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:
Direct link to video (Score:5, Informative)
Parent
Skynet (Score:5, Funny)
Parent
Re:My own experiment with GAs (Score:2)
It's intriguing to me, though, that you mention two things which I thought were no longer thought in evolutionary theory:
1) it tended to get stuck with a far from perfect solution I know that one who plays with these things can tell when a solution is "far from perfect", but there's often no way to tell if one is getting "close to perfect", since the solution space is so damned huge, and the fact that the environment can not only change dram
Re:My own experiment with GAs (Score:4, Interesting)
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.
Parent
Wrong (Score:2)
Re:Wrong (Score:2)
Re:Wrong (Score:5, Informative)
Parent
Based on Recent Stories . . . (Score:3, Funny)
Can you say Cylons? (Score:5, Funny)
You can use other microcontrollers for Legos too. (Score:5, Informative)
Bluetooth [engadget.com] modules are apparently also available for this device. Engadget [engadget.com] has a description and a link to a cool video of this Gameboy/Lego interface in action
WOOHOO!!! (Score:3, Funny)
Hmm. (Score:5, Interesting)
"robots were created that could mate" (Score:5, Funny)
+1 Funny as hell (Score:2)
I don't care (Score:4, Funny)
Robot Porn! (Score:2, Funny)
the obligatory addition of insult to injury (Score:5, Funny)
(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 (Score:5, Funny)
Re:Robot creationists (Score:3, Insightful)
Except that, in this case, "God" is some dork in his underwear and a thinkgeek.com t-shirt. There's only ever been two "people" on the planet, one of them was Jesus (at least once), and the other looks the same as her mother, grandmother, great-grand mother, etc.
In all seriousness, I wonder if this isn't more an experience on collaborative learning than it is evolution? You have two beings with limited ways of moving, a simple communication proto
What!?!?! (Score:2, Funny)
What's wrong with you people?
I for one... (Score:4, Funny)
Self replicating robots are /not/ near. (Score:2, Interesting)
However, the small population used (2 bots) and the seemingly weak fitness function make me think that this project won't go anywhere fast (pardon the pun) and is just a genetic dead end. E
Yeah, and... (Score:2)
I'm missing the "really cool" factor about what he actually got done.
Err, yeah (Score:4, Insightful)
Re:Err, yeah (Score:3, Insightful)
The human body is just designed around a fixed number of atom types and a fixed number of genes. Clearly, we haven't evolved and cannot evolve in successive generations just by mixing these components in different ways.
Over a certain complexity level, emergent behaviors are formed in ways that were not designed. Emergent capabilities don't exceed the theoretical range of capability for the organism, but designing an optimum offspring turns out to be a devilishly difficult task, while genetics me
Are these really evolving? (Score:5, Insightful)
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 (Score:5, Informative)
As long as these robots obey the amended Laws... (Score:3, Funny)
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
Re:As long as these robots obey the amended Laws.. (Score:4, Funny)
Parent
Watts (Score:3, Interesting)
Evolution is a myth ! (Score:3, Funny)
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 ! (Score:5, Funny)
If they were anything like my exgirlfriend, they came much, much later!
Parent
Forget making robot friends (Score:2, Interesting)
Its closer than you think (Score:5, Interesting)
Is it just me, or have other people noticed how the 'replicators' on SG1 look a lot like 'evolved' Lego robots?
Neat (Score:5, Interesting)
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 [mit.edu]
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...
Re:Zip Zaps RULE! (Score:2)
I've been trying to figure out what to do with them. Other than generic cat toy. If my PIC programming was up to snuff I'd probably go for it.
Why oh why hasn't anyone invented an 802.11 general purpose IP device yet?
There should be a chip I can plug into my d
So basically... (Score:5, Funny)
Sex and evolution (Score:2, Interesting)
The way they set it up was to have a grid in which organisms lived (all simulated in a computer, of course). Each organism was controlled by a neural network. Males had eyesight, so they could tell what was in front of them a few squares. Females had a sense of smell, so they could tell when a male was around. (IIRC). In o
Just to fan the flames...it's not modelling evol (Score:5, Funny)
Evolving embodied agents with Genetic Algorithms (Score:5, Interesting)
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 [erachampion.com]
In 2005, a milestone was reached (Score:5, Funny)
So, in 2005, geeks finally created AI that had abilities surpassing the abilities of the geeks themselves.
Careful Now (Score:5, Funny)
Cool robotic movement work (Score:5, Interesting)
The evolution of the Lego meme in science (Score:3, Interesting)
Lack of fitness (Score:3, Interesting)
This isn't really evolution, since there is no determination of fitness. With normal GAs you (somehow) evaluate the "fitness" of the creature, which is typically used to drive how often, and with whom, the creature reproduces.
In the stuff I've done [heroicproportions.org], general lifespan is driven by genes, as are reproduction behaviors, movement and eating habits. Available "energy" i.e. food eaten, put additional limits on lifespan and mating. Thus, there are some "natural" fitness measurements, if a creature dies off before it mates, it wasn't fit enough... If it doesn't have enough energy to share with it's offspring, that allows them both to survive, it wasn't fit enough.
One of the more interesting genes I've been using lately is a "mutation rate". If I start out with some base creatures, that I know are likely to survive, but aren't great, they will frequently evolve to the point where they are co-existing with the environment pretty well, and once that point has been reached, their mutation rate drops to nearly zero.
Re:Playing God? (Score:3, Funny)
Or with "legos" as the rest of us call them.
LegoPron.COM (Score:4, Funny)
Parent
Re:Logical problem with their "evolution" (Score:4, Insightful)
Parent
Re:Physical? (Score:3, Insightful)
Because we've pretty much squashed whatever native talent most people have for abstract thought (or for appreciating the fruits of thought experiments). Never mind that people bank on the the output of weather sims every time they pack up to go skiiing - but anything that requires some extrapolation to the physical world is just too much for too many people these days. I truly, truly lay that at the feet of the "it tak