Friday, September 14, 2007

1999 Computers That Think Outside the Box

October 7, 1999

WHAT'S NEXT; Computers That Think Outside the Box

ONE 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. Mr. Funes wrote the program that gave the computer the background in physics it needed to get started -- no small job. And Dr. Pollack and Mr. 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.

No comments: