LINK TO ORIGINAL ARTICLE

ScienceNOW 

30 August 1999 

Evolving Toy Story 

Few people over the age of six would think of Lego construction
toys as the building blocks of life. But now two scientists have
shown that it is possible to "breed" a working Lego structure,
such as a bridge or a crane, without any human intervention. The
researchers call the result, published in the current Artificial
Life, a step toward the "evolutionary" design of robots. 

Brandeis University computer scientist Jordan Pollack and
graduate student Pablo Funes brought to life their bridges and
cranes on a computer, using a type of program known as a genetic
algorithm. Inspired by the biological process of evolution, the
program starts with 1000 randomly chosen brick designs and lets
them evolve in two different ways. "Mutation" means that a
brick's position in any particular design is randomly modified,
or a brick is added at random. "Crossover" means that components
of two "parent" designs are randomly switched--a process akin to
sexual reproduction. Each of the resulting "offspring" is rated
according to its fitness for the desired task: for example, how
heavy a weight the structure could lift without falling over.
After breeding many "generations" (which usually took a day or
two), a structure would evolve that seemed ready for its task.
At that point, Pollack and Funes built and tested it. 

The cranes that emerged from the genetic algorithm look like
nothing a human would build; clumsy and ungainly, they have all
sorts of unnecessary bumps and lurch forward as they strain to
pick up a one-pound weight. But that's not the point, says
Pollack. What matters, he says, is that "an incredibly stupid
and simple algorithm" regularly evolved features that had not
been programmed into either the algorithm or the fitness rating.
The cranes, for example, always evolved vertical struts that
added strength to the diagonal arm. What's interesting, says
Pollack, is that the program "rediscovered basic engineering
constructions." 

"The unique thing about [Pollack's] work is his use of modular,
buildable components and his actual building and testing of the
evolved structures," says Randall Beer, a robotics researcher at
Case Western Reserve University in Cleveland, Ohio. However,
Beer adds, evolving robots that move, rather than cranes or
bridges that simply bear weight, will be a much more challenging
problem, in part because the physics of moving parts is more
complicated. 

--DANA MACKENZIE