Slashdot Mirror
Genetic Algorithm Generated Lego Bridge
mvicuna writes "[according to a Yahoo News story] Scientists programmed a computer to use "evolutionary steps" to build a bridge made out of Legos. Is this a Lego story or an AI story? :> " A good question. Some of each, perhaps? And they apparently did it without 1000 Pentiums, too. Here's the home page of the project itself. Tres cool stuff!
>Actually, the solution was the "best" in the fact
>that it fullfilled all the requirements given.
>The computer has no way of putting further
>requirements on its construction, so anything
>that solved the problem would be equally "best"
>for it.
No. That's plain and simply not how GA's work.l
They evaluate solutions based upon a fitness function, and choose some from among the solutions with higher fitness to "breed" in some form to get the next generation of solutions.
In some cases, there may be a known and reachable maximum fitness, but this is the exception, rather than the rule.
I'd be surprised to see "makes it all the way across" recieve full fitness. More likely, the number of bricks should be included, perhaps the width of the bridge at the narrowest point, etc.
GA's are not (usually) used to find "a" solution, but the best reachable solution.
I should note, though, that GA's are susceptible to local maxima; once one is reached, it may be difficult to change to the global optimum. However, there are techniques that address this problem in a wide variety of cases.
Hmmm, interesting.
:-)
But Terry Farrell is (or has the looks of) a standard Western Caucasian female. Where's the "ethnic" bit, outside of the Jadzia lineage that is?
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
What's that tube of Superglue doing in the corner of the picture? ;-)
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
Give computers a worldview and they'll see us as rivals.
We have to go there, but let's go prepared.
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
Note that the bridge that was built (the end point of their problem) is merely the first point in the solution space.
If a *real* bridge was desired then the solution space could be populated more fully with many more GA-generated solutions, and then searched using conventional AI techniques for points satisfying a heuristic based on other criteria, eg. no excess material, smoothness of form, and so on.
Alternatively one could add these criteria to the GA survival metrics. This would slow down evolution dramatically because the probability of survival of offspring would be drastically reduced, but it would deliver "real" solutions directly.
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
Although methods that don't get stuck in local minima despite using a worm's eye view of the world are valuable, the best answer is to use a bird's eye view instead so that local minima are directly observable for what they are. (The "view" is in solution space, ie. it doesn't necessarily have anything to do with the usual 4 dimensions.)
That's what humans do. For problem spaces a little smaller than we are, we actually supply the bird's eye view directly. For problem spaces much smaller or much larger than ourselves, we create mental models and plan our solutions within our mental bird's eye view of that model space.
Machinery can be made to do that too, although the overall problem belongs to Strong AI and is difficult (an understatement) in its most general form. There's no reason why this approach can't be used without much difficulty within small problem domains though, in which "full understanding" can be programmed quite simply using a good old-fashioned expert system.
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
Actually, craw was right in part. The only reason why GAs don't usually get stuck in local minima is because of one of two things (or both): either the ancestors live in different valleys in the first place and therefore part of the genome will always have a worldspan greater than any local minimum, or else the sensitivity to mutations is set such that the GA can break out of the largest expected local minimum.
If the original ancestors come from the same valley, and there is no other mechanism for inserting external genes, and mutations do not create solutions outside of the parameters of the original genome then there is no possibility of escape from the local valley. The main reason why this is rare is that mutations are not usually limited in this way, which is why craw was more or less right.
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
Leading off a number of contributions in this thread, does anyone here working in GAs/GP today know of anything approximating a possible "information mutation theory"? Anything that relates to combination or transformation of information descriptors or of domain parameters would be of interest.
Cheers!
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
Linked off the "1000 pentiums" story re Genetic Programming, the Salon article says:
.... :--)
Recently, researcher Lee Spector, an associate professor of computer science at Hampshire College in Massachusetts, used genetic programming to create a fast algorithm for evaluating data structures known as and/or trees. The GP-evolved algorithm was faster than any created by humans and led to the discovery of a new quantum rule.
If anyone thinks that Terminator/Matrix/Borg scenarios are totally unrealistic, they just don't understand the ability of GAs/GP to go beyond human potential. Our capabilities occupy just one local minimum in the solution space. AI machinery won't be constrained to that small valley of possibilities, as the research highlighted in Salon shows.
And on a lighter note:
The Faceprints project uses genetic programming to study human perceptions of physical beauty. Human test subjects are presented with several computer-generated images of faces. They vote on which faces are most attractive. The faces that the test subjects consider most attractive are crossbred, using GP techniques. As wave after wave of human test subjects rate the faces on attractiveness, a face evolves that matches most people's conception of beauty. The "most evolved face" in the Caucasian Female category is a green-eyed, Teutonic vixen who would not be out of place on "Baywatch."
Hmmm
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
Yes, their model parameters can't be sound. Real Lego is nowhere near that good.
However, that doesn't invalidate the work, as reducing bond strength could be expected to modify only local constructs, not progress in the direction of the distant goal.
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
As opposed to the naysayers who have already posted, I think that this work is very useful and difficult. As far as I can tell, they developed a system that, knowing the physical properties of legos, found a way to span a defined gap with no external support other than the initial lego. On the surface, this looks silly, but by implementing an "intelligent" algorithm to do a fairly complicated task is a good thing in my book. Though this is one of many small steps, it will help to further the progress of intelligent machines.
--
Gregory J. Barlow
fight bloat. use blackbox.
Gregory J. Barlow
fight bloat. use blackbox.
Yes, but your missing two points the general public doesn't think Unix is a toy (assuming they know wtf unix is) and the whole play nice thing isn't generally nessesary in the Unix world. So the answer then is No
This is incorrect: mutation fulfills a very different function. The crossover operator allows intermediate solutions to be generated which will hopefully break out of local minima. Genetic algorithms and genetic programming are population-based optimisation methods: the initial population will hopefully span the entire search space. Thus by generating intermediate solutions we will break out of local minima. Mutation is usually (in sensible GAs) small scale, and consequently causes us to search the area around current solutions. If mutation is too large then the algorithm becomes random search.
The problem ofcourse with the task is that the descision on a structure has to be made without testing, i.e. the testing process has to be abstracted, which is where I see the potential for advance coming in, the first steps towards machines with actual or simulated abstract thought processes, this being an admittedly primitve and slightly less abstract example of these processes. But it's a start!
A major problem with non-linear models is that one can get stuck in a local error minimum of the solution. To get out of these minima, one needs to seriously perturb the model parameters. In a genetic algorithm this is done by mutations.
It has been a long time (in a galaxy far, far away) since I took a statics engineering course. But it would seem to me that a critical aspect would be the configuration of the starting model. Additionally, a lego bridge is a fairly simple geometry/model. Remember, the concept of an arch bridge was figured out by people without computers.
It had to design a structure that could be built from one side of a gap to the other. In other words start building at one side, and eventually reach the other, without anchoring to anything but the top of the first side, and without any additional supports during construction.
God does not play dice - Einstein
Not only does God play dice, he sometimes throws them where they
This has more impact than most people realize. It goes way beyond legos. The ability to connect the 'here' and 'there' is essentially what every problem is about. One assesses what one's current knowledge is, and through various connections of this knowledge, one assertain rules for getting closer to the solution. If this is too much of a vague statement, let me try a more concrete example. The computer is given a programming language, and told of each function's syntax, purpose, etc. Next, the computer is given a task, such as 'build a system which does blah blah blah', where blah blah blah is some sort of task that would generally be delegated to a programmer. This is essentially what this machine did; it was given a certain base knowledge (that of legos), and given a task which would normally be given to an engineer. Granted, the solution probably wasn't the 'best' (whatever that means), but that is most likely due to 'best' being ill-defined.
:)
As machines get faster and faster, AI will become much more powerful, as it will be able to analyze exponential problems (those that branch out, such as learning) within a reasonable time.
We certainly do live in a great time to witness such events as this.
Think about it...
= -=-=-=-=-=-=-=-
A) General public/media thinks it's a toy
B) A favorite among scientists and engineers the world over
C) Made from small, re-usuable pieces that plug together
D) Several people can play with it at once, working together to form a large, complex structures
E) There are no rules other than the physics of how the pieces fit and the morals of playing nice with others.
Now, was I just talking about a bunch of kids using Legos or a bunch of geeks using Linux?
- JoeShmoe
PS - other noteworthy comparisons should probably be tacked on to this thread as a reply.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
-- I wonder which will go down in history as the bigger failure: the War on Drugs or the War on Filesharing