LINK TO ORIGINAL ARTICLE

ScienceDaily 8/26/99 

In First Case Of Fully Automated Design, Computers Shape Lego
Bricks Into Various Designs Without Human Input 

WALTHAM, Mass. -- Evolution, until now the unchallenged domain
of living organisms, may soon become possible for robots as
well. So say computer scientists at Brandeis University, where a
simple computer-based form of evolution -- nature's own design
strategy -- has succeeded in designing LEGO structures without
any assistance from humans. It's the first successful leap from
today's computer-aided design into the futuristic realm of fully
automated design, and the first baby step toward the artificial
intelligence community's longstanding dream of evolutionary
robotics, where robots might eventually adopt some form of
evolution. 

Brandeis's Pablo Funes and Jordan Pollack, the researchers who
masterminded this achievement, say this trial-and-error approach
to designing LEGO bridges, tables, and cranes lays the
groundwork for robots capable of reworking their own hardware
without any human guidance at all. Their work appears in the
most recently published issue of the journal "Artificial Life,"
and the university has filed for patent protection on the work. 

"The necessity of allowing robots' brains and bodies to evolve
together has been around since the dawn of evolutionary
robotics," says Pollack, associate professor of computer science
in Brandeis's Volen National Center for Complex Systems. "Our
view is that in nature there is never a brain without a body,
and that small changes to both must be made in a co-evolutionary
fashion." 

To make this rudimentary evolutionary hardware, Pollack and
Funes, a graduate researcher, constructed a computer program
capable of plucking out structurally sound LEGO designs from a
sea of possibilities. They then provided the program with simple
optimization goals, such as spanning a distance and carrying a
weight -- laying the groundwork for the fully automated design
of LEGO-based structures such as a two-meter bridge, a crane
capable of lifting a one-kilogram weight, and a table that could
support the same weight. 

After the computer analyzed hundreds of its own designs and spit
out the best ones, Pollack and Funes broke out their LEGO bricks
and built the structures. Almost without exception, they found,
the computer had engineered structures that were structurally
sound.  "We're not saying these structures are engineering
marvels, but we've shown that even a simple evolutionary
program, paired with the right physics, can design complex
structures without any engineering expertise from humans. A
number of other researchers have tried to evolve more impressive
simulated structures, but ours are the first to translate into
reality," Pollack says. 

The computer's design success was largely a function of its
skill in evaluating the integrity of LEGO structures, which
Pollack says can be determined through the patent-pending
algorithms he and Funes developed to analyze torque in networks
of the sticky blocks. The program is no speed demon; it took a
day and a half to design the two-meter bridge. But the
cantilevered design it eventually came up with is, at least in
Pollack's estimation, superior for a self-supporting LEGO bridge
of that size. 

"What I find most fascinating about these results," Pollack
says, "is that a very simple algorithm 'discovered'
sophisticated structures that took humans many centuries to
design -- a cantilever for the bridge, and an inverted triangle
for the crane." 

The work was partially sponsored by the Office of Naval Research
and the National Science Foundation. With a new research grant
from the Defense Advanced Research Projects Administration
(DARPA), members of Pollack's laboratory are now developing
similar systems that feature limited motion, which is expected
to allow fully automatic design of robot bodies and brains. 

-- Note: This story has been adapted from a news release issued
by Brandeis University for journalists and other members of the
public. If you wish to quote from any part of this story, please
credit Brandeis University as the original source. You may also
wish to include the following link in any citation:
http://www.sciencedaily.com/releases/1999/08/990826071332.htm