On a surface the size of a ping-pong table, five canister-shaped robots whir, click and interact, fighting for control of a bright orange golf ball. These robots are soccer players, competitors in RoboCup, the Robot World Cup Initiative, which was created in 1993 to promote research into robotics and artificial intelligence. Even its creators admit that its goal -- to develop a robot soccer team that can beat a human world championship team -- is ambitious. But they claim that RoboCup is a landmark project, similar to the Apollo space program, an engineering challenge that will push the creation of new, "breakthrough technologies."
Ironically, some of the robots themselves were created by computer ingenuity. RoboCup hosts competition in three leagues: small-size, medium-size and simulation. For now, these computer-created robots are playing in the simulation league -- as purely software creations, they compete only on a computer screen. But they are playing as well as many of their man-made peers.
Researchers David Andre and Astro Teller of Carnegie Mellon University entered their Darwin United team in the software league in 1998. Darwin United was created "automatically," using a form of computer programming known as genetic programming, or GP. And genetic programming may be exactly the type of breakthrough technology the RoboCup federation had in mind.
GP programs, which can handle tasks ranging from robot-like motion to human-like inventions, aren't written in the same way that traditional software is written. They are created automatically, evolved from smaller, simpler programs. Actually, the job of GP programmers is to get a computer to solve a particular problem without telling the computer just how to do it. It is, in many ways, the antithesis of traditional programming, in which human programmers write every command line -- telling the computer exactly what to do in every conceivable situation.
GP programmers begin in quite a different manner, by creating the environment in which their programs "evolve." To create that environment, human programmers write software that randomly produces several small chunks of program code. Using the human programmers' description of the problem to be solved, the software then examines these baby programs, and determines which of them come closest to solving it.
The most promising programs survive, and "crossbreed," swapping chunks of program code with each other to create another generation of programs. For generation after generation, programs are "bred" in this way. The human-created environment guides the software to keep the best and discard the rest. Occasionally, the human-created software environment introduces a random "mutation," changing a variable here or a command there. Over the course of many generations, the environment "evolves" complex, effective programs.
Software programs that evolve using genetic programming techniques are often convoluted, bizarrely multilayered creations, nothing like the software a human might write. But they are remarkably powerful and flexible. Andre and Teller's robots came in 17th out of 36 teams. It was a respectable showing, especially considering that the competing software had been written by some of today's best artificial intelligence researchers. The Darwin United team is "not bad for something that was created out of thin air," comments John Koza, a consulting professor of medical informatics at Stanford University, who is considered the inventor of genetic programming.
Genetic programming can be used to tackle a wide variety of problems, such as creating satellite controllers, designing artificial limbs and solving tricky problems in molecular biology. The beauty of genetic programming is that the programmer doesn't need to be an expert in satellite design, physiology or molecular biology to do this. The programmer creates a "fitness measure" -- a way for the software to know when it has successfully "evolved" a working solution -- and the software arrives at the solution using the evolutionary process of GP.
Early work in GP focused on designing circuits similar to those found in stereos. The "problem" given to the software was to design a type of circuit known as a low-pass filter; a successful "solution" would be a circuit that could pass low-frequency sounds to the stereo's woofer. The "fitness measure" in that case was the ability to separate the low- and high-frequency sounds.
Automatic programming is something of a holy grail in computer science. Koza, who holds the patent on the process of genetic programming and is the president of Genetic Programming Inc., has high standards for what he considers a successful system of automatic programming. The most important, he says, is that it produce results that stand on their own.
"The results must be interesting in their own right," he says -- "not simply because they were machine-produced." He's not interested in what he calls "toy problems." Instead, he says, he wants to use GP to tackle the sort of problems that challenge the best human minds.
In fact, he is not being unrealistic. Already there are GP-evolved solutions that compete with (and in some cases even surpass) human ingenuity.
In 1996, Koza used genetic programming to evolve a design for a specific type of electrical circuit. The computer produced several solutions; but one result infringed on a 1947 patent, while others infringed on patents filed in the 1920s. In other words, the GP results closely matched ideas conceived by humans. Koza's genetic programming has produced circuit designs that infringe on 21 patents in all, and duplicate the functionality of several others in novel ways.
Recently, researcher Lee Spector, an associate professor of computer science at Hampshire College in Massachusetts, used genetic programming to create a fast algorithm for evaluating data structures known as and/or trees. The GP-evolved algorithm was faster than any created by humans and led to the discovery of a new quantum rule.
GP also has been used to evolve protein-analyzing programs that are better than programs written by professional molecular biologists, and to design circuits that many electrical engineers previously thought to be impossible. On a very complex mathematical problem called the 1-d majority cellular automata problem, a GP-produced solution was the best in the world for about a year. It was eventually beaten out by a solution created by another evolutionary algorithm similar to GP. The human-created solution to this problem remains in third place.
With striking frequency, people who are considered the best in their fields are finding that GP-evolved solutions are better than anything they've come up with after years of research. As Koza points out, GP-evolved solutions are winning accolades even outside of the genetic programming world. "These are inherently publishable results," he says, "even as judged by standards external to our field."
Genetic programming's capacity for innovation extends beyond the realm of math and science problems into more subjective territory as well. It has been used to create artificially evolved music, art and images.
Spector has combined his research in quantum algorithms with dabblings in jazz. He's the director of the GenBebop program, which uses genetic programming to create interactive jazz music-making programs. A human plays a four-measure "call." The program improvises a four-measure "response." Spector says modestly that the responses are "not brilliant" -- though they are judged to be "good" by the music critic software used in creating the artificial musician, and GenBebop is working to make them better.
Genetic programming can be used to create images based on other aesthetic criteria as well, or even help us to understand the criteria themselves. The Faceprints project uses genetic programming to study human perceptions of physical beauty. Human test subjects are presented with several computer-generated images of faces. They vote on which faces are most attractive. The faces that the test subjects consider most attractive are crossbred, using GP techniques. As wave after wave of human test subjects rate the faces on attractiveness, a face evolves that matches most people's conception of beauty. The "most evolved face" in the Caucasian Female category is a green-eyed, Teutonic vixen who would not be out of place on "Baywatch." A study of attractiveness in Caucasian males is under way.
Someday, a similar program may be used instead of a police sketch artist to turn eyewitness accounts into images of suspects.
It's not hard to imagine how genetic programming's power and flexibility could be harnessed to create a variety of consumer products. GP-evolved programs may be used to study the molecular composition of various drugs, isolating and editing out unwanted side effects. GP-evolved art and music might compete with works by human artists. Genetic programming may also be used to create intelligent agents, software programs that "learn" from their human users. In fact, we may see a new breed of robotic pets, computer-controlled toys whose ability to change their own programming will enable them to learn tricks and "communicate" with their owners.
GP inventor Koza and many others believe that genetic programming will be used in the future as an invention machine. David Andre, now a computer science grad student at UC-Berkeley, has worked with Koza and co-authored his latest book, "Genetic Programming III: Darwinian Invention and Problem Solving." Andre predicts that in the next five to 10 years we will see many more examples of genetic programming being used to invent or design products that actually get used and sold. Genetic programming, Andre says, will "almost certainly be a tool that designers and engineers use in the process of inventing."
"Some people think that logic is the key to creating artificial intelligence," says Koza. "But logic is not the key to invention."
For an invention to be patentable, he points out, it must include an illogical element, a flash of insight. Patent law specifically refers to "the illogic of the invention process." In other words, if an invention can be logically inferred from existing knowledge, then it is not patentable.
"There needs to be an illogical or unjustifiable step to qualify something as an invention," Koza says. "What humans bring to the invention process is not their logic, but their illogic." Genetic programming, with its random breeding, mating and mutation, includes that element of fruitful illogic.
"Difficult problems can now be attacked using search techniques like genetic programming," says Andre, "and as computers become faster, and as genetic algorithms become more powerful, GP can be used to solve increasingly complex problems."
In April, Koza's Genetic Programming Inc. opened up a new, 1,000-node cluster of computers devoted to genetic programming. His previous work was done on a 64-node cluster. The new cluster is one of the largest chunks of computing power in the world and opens up new possibilities for GP-evolved solutions.
Advances in the field of genetic programming will likely continue to improve circuit and limb design and many other activities -- maybe even robot competitions. An intermediate goal in the RoboCup competition -- before robots take on Brazil's World Cup team, for example -- is to get rid of the walls that currently keep the robots on their tables. That would require better robot "vision" and maneuvering, which could certainly be designed with genetic programming. And maybe with GP-evolved artificial intelligence, future robots won't be just playing soccer with humans, but teaching their human peers new tricks.
Shares