LINK TO ORIGINAL ARTICLE

Computers That Think Outside the Box 

By ANNE EISENBERG 

[O] ne of the latest problems computers are taking on is
evolution -their own, that is. 

In many spots in the United States and abroad, scientists have
created computer programs that can change and refine their own
software through successive generations; the process continues
until the software does what needs to be done with no help
whatsoever from the pesky humans who initiated it. 

One such project involves computer programs that are given
algorithms -math-based strategies -- and the rules of physics
and then assigned certain architectural tasks to perform. They
wind up reinventing structures like the triangle. The scientists
who set the programs in action in the first place have built the
designs, using Lego components, and given the artificial
architects a limited vote of confidence. 

"I'm not saying a computer can replace an architect -- at least,
not yet," said Jordan B. Pollack, a professor in the computer
science department at Brandeis University's Center for Complex
Systems in Waltham, Mass. "But our computer did start with a
simple algorithm and end with blueprints for structures that it
took humans hundreds of years to develop. 

And when we built the structures, they were functional." 

The structures Dr. Pollack is talking about are modest ones:
tables, bridges and cranes made from toy blocks. But as he and
Pablo Funes, an Argentine graduate student, report in the
current issue of the journal Artificial Life, the computer came
up with structures that could be built without specific guidance
from them. 

What the computer was given was a program that included the laws
of physics and some random patterns of Lego bricks. It was also
given the ability to let its designs evolve, in a "survival of
the fittest" system. Then the programmers stepped back. 

Dr. Pollack's field, evolutionary computing, is a futuristic
place where computers solve problems without being programmed to
do so, selecting the fittest solutions by mimicking natural
selection. Dr. Pollack predicts that evolutionary computing may
one day lead to robots smart enough to generate and test
themselves with no human engineering costs whatsoever, making
them cheap enough to be disposable. For now, though, Dr. Pollack
and his graduate student are at an early stage. 

The computer did have some initial input from the two
scientists. 

Funes wrote the program that gave the computer the background in
physics it needed to get started -- no small job. And Dr.
Pollack and Funes together developed an evolutionary strategy
for generating and testing designs. 

Then the computer was given randomly chosen initial designs and
permitted to proceed through "mutations" -- random modifications
of the locations of the bricks -- or "crossovers" -- random
switches of pieces of two parent designs. 

Each "offspring" design was then rated for fitness. 

"We didn't teach the computer how to design triangles or
counterbalances," Dr. Pollack explained. "It figured this out
without any engineering advice from us." As the computer
designed a crane, for example, it selected a triangle to make
the crane's base more stable -something it knew how to do by
applying the laws of physics. 

"It used the interaction of evolutionary algorithms and the laws
of physics to produce these interesting, very functional
structures that carry weights effectively at certain heights,"
Dr. Pollack said. "It came up with fairly sophisticated
solutions." 

When the computer was done with a task, Dr. Pollack and his
student built the design according to the blueprint produced,
building a crane that lifts one kilogram, a two-meter bridge, a
table. "Ours are one of the first systems in evolutionary
robotics where evolution-in-simulation translated into reality,"
Dr. Pollack said. 

His long-term vision is for computers to produce robots by
specifying both the mechanical bodies and the neural networks to
control them. 

The blueprint would be turned over to a fully automated factory
that would fabricate the robots "as cheaply as today they make
Sony Walkmans," he said. 

Dr. David Fogel, the chief scientist at Natural Selection, a
company in La Jolla, Calif., that uses evolutionary algorithms
to solve problems in medicine and industry, works in areas
related to Dr. Pollack's. 

"The most critical thing in Pollack's work is that he
demonstrates that you do not need to have specific expertise in,
say, mechanical engineering to design a useful construct," he
said. "All you need is a simple evolutionary algorithm and a
good model of the physics of the environment. The significant
thing is that he didn't design the crane -the program did." 

Dr. Fogel, too, uses evolutionary programming, but he does not
test designs with Legos. 

Instead, he focuses on the game of checkers, in addition to
looking at more serious building blocks like molecules. Using as
little expert information as possible, he and a colleague wrote
an evolutionary program to see if the computer could teach
itself to play checkers at an expert level. 

The computer's tactics evolved as it played against itself. 

After 10 generations, it defeated both Dr. Fogel and a graduate
student. 

"After 100 evolutions, we put it on the Internet," he said, "and
let it play against opponents without telling them they were
playing a program, not a person." The program has moved up to
the fourth-highest ranking, Class A, for checkers players. 

Dr. John Koza, an expert in evolutionary programming who is
president of Genetic Programming, in Los Altos, Calif., cited
many examples of automatically created solutions that were
competitive with results produced by people. As one example, he
pointed to circuits that are so original they infringe on
patents. "This is significant because if you automatically
create something that infringes, you have created the essence of
that invention," he said.