Science 285 p. 1663

Random Samples 

10 September 1999 

Evolving Toy Story 

Few people over the age of 9 would think of Lego construction
toys as the building blocks of life. But now two Brandeis
University scientists have shown that with a computer program
based on evolutionary principles it is possible to "breed" a
structure, such as a bridge or a crane. It's a step, they say,
toward the "evolutionary" design of robots. 

 Computer scientist Jordan Pollack and graduate student Pablo
Funes designed their structures on a computer using a "genetic
algorithm" based on 1000 randomly chosen brick designs. The
patterns may evolve in two ways: "Mutation," which will randomly
add or change the position of a brick, and "Crossover," which
will randomly switch components of two "parent" designs. Each
design got a "fitness" score based on weight-bearing ability
(for the cranes) or length of span (for the bridges), which
determined how likely it would be to have "offspring." When a
promising structure eventually evolved, Pollack and Funes would
build one out of Lego bricks and test it. 

 The resulting structures are clumsy and inefficient-looking,
but they perform as their simulations promise. They demonstrate,
says Pollack, that "an incredibly stupid and simple algorithm"
can spur the evolution of unprogrammed features. The cranes, for
example, evolved a basic engineering principle, always adding
vertical struts to add strength to a diagonal arm. 

 "The unique thing" about Pollack's work, says robotics
researcher Randall Beer of Case Western Reserve University in
Cleveland, is that he hasn't stopped with computer simulations
but is "actually building and testing the evolved structures."