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!

Non-linear solutions

The Genetic algorithm is a means of solving a non-linear inverse problem; another notable method is simulated annealing. In the old days, the Monte Carlo method was used; Monte Carlo is where the casino are where all solutions are a matter of chance (hence, try them all). Start with an initial model, then incrementally move to a better solution. In a non-linear model, one perturbs the parameters then checks to see if the solution is better than the previous one. In a linear model, one can compute the correct direction to go by using the invariant derivatives of the defining mathematical model.

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.

The challange was more complicated then it sounds

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.

impact

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. :)

Legos = Open Source Software

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.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= -=-=-=-=-=-=-=-