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.

Posted in Math