On the Origin of Circuits.
Imagine this: A wee spacecraft no bigger than a can of soda zips out to an asteroid. There, it grabs on like a leech, sucks minerals out of the surface, and fashions them into parts and supplies it needs to make itself into something bigger and better, with more ambitious travel plans.
By the time the renovated craft blasts off again, it will have morphed into NASA's first interstellar explorer, on its way to seek clues of life on planets circling alien suns.
It's still only a science fiction scenario, but NASA Administrator Daniel S. Goldin predicts that something like this might transpire in only 30 years.
If he's right, the building of future space vehicles will involve a radical departure from tradition. Instead of engineers painstakingly crafting every detail of their systems, they will depend increasingly on machines that design and build themselves.
This trend has already begun, and in its first successes, NASA officials find encouragement that the approach will eventually lead to far more reliable, versatile, and long-lived spacecraft than those being built today.
"These evolvable space systems would revolutionize NASA's space exploration," says Moustafa Chahine, chief scientist for NASA's Jet Propulsion Laboratory (JPL) in Pasadena, Calif.
Initially, NASA scientists and engineers are investigating how machines might revamp their own electronics. In doing so, they join a growing research area that has been dubbed evolvable hardware.
Specialists in the fledgling field investigate techniques for machine-executed design both in software and integrated circuits. The techniques rely on guided trial-and-error strategies inspired by Charles Darwin's theory of evolution by natural selection and known as evolutionary algorithms or artificial evolution (SN: 7/23/94, p. 63).
Although still largely in a research realm, evolvable hardware has started to appear in prototypes of practical devices ranging from cell phones and printers to robots, prosthetic limbs, and even an artificial brain (SN: 7/22/95, p. 62).
Last July, about 100 scientists and engineers from more than 70 universities, companies, and government labs worldwide met in Pasadena, Calif., to discuss the latest in both research and practical developments. Although the field has spurred workshops and conferences since 1995, the 3-day meeting--the First NASA/Defense Department Workshop on Evolvable Hardware--was the first in the United States.
Computers might already rival people as circuit designers. John R. Koza of Stanford University, who has pioneered ways of making computer programs evolve, predicts that his group or another will be filing patents "in the next year or two" on circuit designs created by their machines.
Like idiots savants, Koza's computers work their wizardry without any expert knowledge of circuits. The resulting designs, however, are at least as good as those that top-notch human designers were coming up with pre-1950, Koza suggests. Some of the designs would "squarely infringe" on patents issued to outstanding circuits of that era, he says.
He strutted out a parade of such designs at the meeting, describing how he and his colleagues simply specified a set of commands that told the computer how to place and wire circuit parts. Then, they let artificial evolution take over.
Evolutionary, or genetic, algorithms perform a fast shuffle of pieces of computer programs or digital codes, which the developers think of as genes. A complete set of genes--that is, either the commands making up an entire program or a sequence of digital codes containing all the instructions to build a particular circuit--make up one individual. To start the evolutionary process, a computer randomly jumbles large numbers of genes to create hundreds or thousands of such individuals.
The algorithm then tests these individuals by trying out the circuits they represent, either via simulation or by wiring the devices. It finds out how well, if at all, each circuit performs a desired function. From the tests, individuals earn fitness scores that help determine whether they will be permitted to breed. If so, they swap some of their genes with those of other high performers to create individuals with new combinations of commands or codes. The rest of the individuals die, erased from memory.
As the breeders mate with many partners to rebuild the population, the algorithm occasionally alters, or mutates, an offspring by changing a command or a bit. This adds another element of chance. Ideally, after hundreds or thousands of generations of breeding, testing, and culling, an exceptionally fit individual emerges and the design is done.
Three years ago, Adrian Thompson of the University of Sussex in Brighton, England, created a sensation when he made an actual circuit go through the evolutionary process. It wasn't that the final circuit--a device that could be used to discriminate between frequencies of 1 kilohertz (kHz) and 10 kHz--was so special. Rather, his experiment demonstrated that with artificial-evolution algorithms, a machine could alter itself on the fly.
Thompson performed his feat on a type of commercially available integrated circuit that had been around for 10 years. Called field programmable gate arrays, such microchips contain a grid of minuscule tiles filled with identical collections of components. In response to a string of digital codes, each tile's components can alter the functions that they perform and the routing of signals among the tiles can change.
One can think of the grid as a miniature New York City. All the streets and buildings are in place. In response to new codes, each establishment changes its type of business. A small army of traffic cops barricades certain streets but opens others, rerouting traffic in a way that can be changed again later.
Such reconfigurable circuits lend themselves well to evolution. Because reconfiguration takes only a few milliseconds, many generations of circuits can be tested in a short time.
Thompson wasn't the first to employ the notion of directing such grids to evolve. Australian computer scientist Hugo de Garis had proposed the idea in 1992. In that same year, Tetsuya Higuchi of the Electrotechnical Laboratory in Tsukuba, Japan, who was de Garis' boss at the time, began testing evolutionary algorithms on reconfigurable circuits called programmable logic arrays and soon after on the more complex gate arrays.
Thompson's experiments, however, highlighted some intriguing consequences of artificial evolution. He found that his evolved circuit was much different from what an experienced engineer might design. For instance, it used surprisingly few components, tantalizing investigators with the possibility that evolution might generate especially efficient circuits. It also wired some circuit elements into the grid in such a way that they were left in an indeterminate state between on and off.
That unusual use of components suggested that evolved designs could exploit mysterious aspects of chips that the designers of semiconductor building blocks might not know about. "What I like is that this is a way of finding the natural forms in this artificial medium," Thompson says.
Skeptics at the July meeting raised questions about the reliability of evolved circuits.
Julian Miller of Napier University in Edinburgh nonetheless agrees with Thompson. Evolved circuits are "a kind of automated inspiration," he says. "We can study these new designs and learn new principles."
Despite questions about whether evolved circuits represent an improvement on other devices, researchers have already begun to look for ways to incorporate them into products.
Higuchi's lab has put such circuits into a prosthetic hand that a wearer controls by moving the arm muscles that remain intact. Conventional prostheses that use muscle signals require roughly a month of training, during which the user learns to flex his or her muscles properly to trigger electrical signals that move the hand (SN: 8/28/99, p. 142). The evolvable hand instead adjusts itself to the user.
During a training session of only a few minutes, Higuchi says, the prototype circuit modifies itself to produce correct responses to electric signals from the user's arm muscles. The training relies on feedback from the user to let the circuit know if it's generating the intended hand movements. Over years of use, as the person's muscle signals change, the circuits would adapt, Higuchi says.
He and his colleagues have also been applying evolvable hardware to cellular phones, digital printers, and other devices. In printers, for instance, the circuits can make it possible to compress and decompress data extremely quickly and so print pages very rapidly. "At the beginning, I had no confidence that we could succeed in evolving real hardware," Higuchi says. "Now, we have products already being commercialized," he proudly notes.
De Garis, now at the Advanced Telecommunications Research Institute in Kyoto, Japan, heads a high-profile, controversial undertaking known as the Cellular Automata Machine Brain Project (SN: 7/30/94, p. 77). The project's goal is to create an artificial brain using evolvable hardware.
The team is working on a computer packed with 72 gate arrays and associated electronics estimated to rival 10,000 500-megahertz Pentium microprocessors. This hardware will model the behavior of 70 million brain cells, says Michael Korkin, president of Genobyte in Boulder, Colo., the hardware's maker. By contrast, the human brain contains roughly 100 billion neurons.
Though few other researchers give the project much chance of success, de Garis already envisions a next-generation machine, armed with a billion artificial neurons, that will beguile the public by controlling a lifelike robotic kitten.
After 6 years of development, the first-generation prototype of the brain exists, de Garis announced at the meeting. He flashed onto a screen several photographs showing parts of the machine, which are shaped to suggest brain tissue. "There are people in this room who still think I'm crazy," he said, scanning the audience. "Hopefully, I'll get my revenge ... soon."
He and his colleagues from the United States, Italy, and Poland report that they have run simulated circuits through an evolutionary process to learn, for instance, to detect moving patterns. However, de Garis conceded during questions following his talk that he has yet to work out most of the details of how to interconnect the approximately 60,000 blocks of circuitry of which the artificial brain is made.
A common thread--the emulation of biology--binds all the attempts to use evolvable hardware and to better understand its power (SN: 11/30/91, p. 361). Goldin's self-transforming spacecraft "sounds like an ambitious dream, but it could be possible if we effectively utilize biologically inspired technologies," the NASA chief asserts.
JPL researcher Eric Mjolsness presented results from a preliminary attempt to simulate, in a computer, growth of a tiny structure in flowering plants that gives rise to leaves, flowers, and stems. Such knowledge may one day prove important for developing "seed ships," Mjolsness asserts. These, too, would be small spacecraft thus affordable to launch, which could flower into full-blown craft or laboratories on other worlds.
NASA covets for its future space programs two abilities that living creatures long ago acquired: self-repair and adaptability to unforeseen circumstances (SN: 5/29/99, p. 347). As the space agency contemplates 100-year-plus interstellar missions, evolvable hardware promises--for electronics, at least--to bring both capabilities within reach.
RELATED ARTICLE: Invention by evolution
Call them courageous or foolish. Either way, computers that use artificial evolution to create designs can't help but try things that are new.
That's why the little antenna that Derek S. Linden held up in his hand in Pasadena, Calif., at the First NASA/Defense Department Workshop on Evolvable Hardware in July looks crumpled and weird.
Linden, an antenna expert at Linden Innovation Research in Herndon, Va., has coaxed his computer to design a whole family of extraordinarily cheap, easy-to-make antennas for ground-to-satellite communications. They look vaguely like black drinking straws that a creative child has bent into odd shapes. "They're like snowflakes. They never come out the same," Linden says, but the computer-designed antennas show "excellent performance."
Jordan Pollack recently chose to have his automated system use artificial evolution to design bridges, cranes, and tables. The designs, which he and Pablo Funes carried out in a Brandeis University laboratory in Waltham, Mass., were for structures made of those little plastic bricks known as LEGOs.
Since humans already know about the strength of triangular structures and the stabilizing effect of the counterbalance, it may seem that the Brandeis system was taking baby steps when it hit upon those structures in its designs. Au contraire, says Pollack, who showed pictures of the colorful LEGO creations at the meeting. The computer invented from scratch those most fundamental of forms because they are natural consequences of the physics of structures.
William A. Crossley of Purdue University in West Lafayette, Ind., presented examples in which evolution looks promising for designing new aircraft and space vehicles, from helicopters to satellites.
The proof that evolutionary hardware design is practical, however, may be those antennas, speculates computer scientist Jason D. Lohn of NASA's Ames Research Center in Mountain View, Calif. Linden has received a patent on the oddly folded antennas, probably the first for an invention by a nonhuman designer. "It's the first one that I've heard of," says Lohn.-P. W.
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||circuits designed by machines|
|Date:||Sep 4, 1999|
|Previous Article:||Rarest of the Rare.|
|Next Article:||Vitamin C lowers stress hormone in rats.|