Charting a Path to the Planets
An Evolutionary Algorithm plots a New Course in Space Travel. by Mike martin
An advanced software program, one that uses a digital form of natural selection to sort through complex computational puzzles, is helping an MU researcher and his students chart the fittest routes for guiding spacecraft through an endless maze of interplanetary possibilities. The result could fuel a revolution in rocket science.
What computer scholars refer to as "differential evolution" is a relatively simple computing methodology -- at least for engineers -- that uses concepts of reproduction, random mutation and natural selection to solve problems. Think of it as a form of digital Darwinism, one that MU mechanical and aerospace engineering professor Craig Kluever and his former MU graduate students Aaron Olds and Michael Cupples are using to teach an old theory new tricks.
"With any space mission, you want to put as many instruments or as many people as possible on board. That can take a lot of fuel," says Kluever, who holds a James C. Dowell professorship. "Our differential evolution algorithm can find the route that takes the least time or the least fuel, or that maximizes the amount of payload a spacecraft can carry."
In evolutionary computation, the scientists say, Darwin's theory has found one of its least controversial, most successful applications.
The process bears a remarkable resemblance to DNA transcription and replication, where, instead of 1s and 0s that make up the binary language of computer programming, nature uses four chemical bases represented by the first letters of adenine, cytosine, guanine and thymine.
Just as biological evolution forces new combinations of A, G, C and T to compete with old combinations until a fitter organism emerges, digital evolution puts new combinations of 1s and 0s in competition until an optimal solution emerges. In short, solving by evolving.
The idea of solution evolution began germinating in the 1950s. Faced with complex problems in space flight, bridge engineering, skyscraper construction and other minutely detailed, step-by-step processes, scientists began using computers to randomly test potential solutions, letting the machines weed out those that failed to make the grade. Over time, researchers noted the process was beginning to look like something out of Darwin's Origin of Species.
In the 1960s, American computer scientists Lawrence J. Fogel and John Henry Holland formalized the science of evolutionary computing with their work on what they described as "genetic algorithms." Mapping the most fuel-efficient route from Columbia to Los Angeles provides a simple example of Fogel and Holland's method.
To start, one would develop an algorithm with a "population" of various routes along different highways. The algorithm would next cycle through dozens of "fitness functions," checking each for "efficiency parameters." One fitness function would test for the number of mountains along a particular route; another might check for routes with the fewest stops; a third could seek routes with the optimal average speed limit. The algorithm then uses evolutionary programming to select, mutate and recombine these fitness function findings in ways that, eventually, produce the most efficient route.
As in natural selection, mutation plays a key role in this digital Galapagos. To visualize a digital mutation, imagine strings of 1s and 0s merging to form new strings, each representing a new solution. The string 011110111101111 might represent a road trip from Columbia to Los Angeles that uses 75 gallons of unleaded gasoline. But, like nature, computers can make mistakes. A digital mutation -- an accidental combination that produces a slight variation of that string, say, 011110111101100 -- might represent a 74-gallon road trip. After a round of fitness checks, the computer's evolutionary algorithm would save the mutation, adding it to the digital mix until the fittest solution emerges.
For expeditions to faraway destinations such as Mars or Jupiter, the differential evolution, or DE, algorithm uses "parameter vectors" to point the way. Parameter vectors are like mathematical genes composed of bits and bytes that a computer interprets. Just as human genetic information determines brown hair or blue eyes, DE's digital DNA codes for launch date, rocket boost intervals and other mission-critical elements.
Along every parameter vector, the differential evolution program assigns a value to each bit of digital DNA, locating it between the upper and lower limits of a range. Using this method, a parameter vector might code for a morning or evening launch, a Monday or Friday rocket boost or a planetary approach farthest from or nearest to the Sun. The algorithm makes this happen by taking advantage of the mathematical equivalents of mutation, selection and reproduction, allowing progeny vectors to give "birth," as it were, to new generations of vectors, each intent on mapping ever-more-efficient routes.
This propagation of progeny vectors goes on until an "optimal" route emerges from the original vector family, Kluever says. His colleague, Olds, likens this digital evolution process to the creation of "children that will survive into the next generation if they are an improvement over their parents."
A long-distance space voyage is like a road trip over "a substantial number of hills and valleys," explains Olds, now a project engineer at Analytical Mechanics Associates, Inc., in Hampton, Va. The differential evolution algorithm takes advantage of those ups and downs by helping the spacecraft make use of gravity's peaks and valleys.
In the parlance of space science, this is known as a "gravity assist," the fuel-saving process whereby a spacecraft uses a planet's gravitational field to change course or slingshot itself farther into space. Olds likens the process to a pedal-free bike ride down a steep street.
As planets orbit around the sun, they create dozens of gravity boost opportunities. Unfortunately, such boost scenarios are riddled with potential trajectory pitfalls. Here differential evolution algorithms really shine, Olds says. By charting "propulsion maneuvers" -- fuel burns that keep the ship on track -- the algorithms correct for such variables as unequal incoming or outgoing velocities. Once the ship is in place, the programs allow the ship to use smaller burns at scheduled intervals to remove errors in the trajectory.
By the end of the 1980s, evolutionary and genetic computer algorithms had became so widely accepted that budding digital geneticists could purchase a software package called Evolver for their desktop computers. Today the Ithaca, N.Y. -based Palisade Corporation makes Evolver as a supplement for the Microsoft Excel spreadsheet. Interplanetary travel software is also available commercially, Olds says, most notably through the Satellite Tool Kit from Analytical Graphics in Exton, Penn.
The MU research team has shown, in a study published in a recent edition of the Journal of Spacecraft and Rockets, that these and their own differential evolution algorithms offer several advantages over proprietary programs. Such programs include, most notably, the MIDAS program currently used by NASA and the Jet Propulsion Laboratory.
Whereas NASA's space mission design software acts locally, Kluever says, differential evolution acts globally.
"MIDAS and other programs break one large space flight into several smaller flights. They use a gradient method that strings together local minima, areas along the route that consume minimal amounts of fuel, into one long trip."
Local optimization programs minimize propellant use "by starting with a trajectory guess," Aaron Olds adds. "The term 'local' is used because the minimum fuel consumption point will be found only for the valley in which the initial guess is placed. The algorithm will not climb out of one valley in hopes of finding a lower one." At least, not without help from programmers and engineers.
Differential evolution, on the other hand, visualizes the entire trip, from point A to point Z, rather than just individual stages. "Our software looks for a global minimum – the most fuel-efficient route mapped out ahead of time that provides perspective all at once," Kluever says. This approach "allows more missions to be analyzed more rapidly."
The ability to analyze several potential missions ahead of time makes the differential evolution algorithm "a very good feasibility tool," says Dave Brody, media director and science writer for Imaginova, the parent company of Space.com and publisher of Space News. "It seems like a good top-level way to analyze a mission or missions from an initial or proposal stage," Brody says. "In that respect, it represents a new paradigm for space travel: up front, rather than stage-by-stage mission optimization."
Designed as "open source" -- for use and modification by just about everyone -- differential evolution space flight software will, of necessity, be easy to use. Such an advantage is a plus for the private and commercial space flights Brody says will soon be commonplace.
"NASA's current software is user generated. As a result, it's arcane and complex," he explains. "To expect it to transfer to another information technology culture may not be realistic. The differential evolution algorithm may be a much better way for planners to talk to one another across organizations and across the globe."
Potential investors will likely also appreciate the evolution solution. "As a private investor, if I can get an overview of an entire trip rather than a series of snapshots, that's much better," Brody says.
To test their algorithm, Kluever and Olds programmed it to map what they call "challenging interplanetary optimization" problems: the 1997 Cassini Mission to Saturn, the 1989 Galileo mission to Jupiter, a mission to the comet Tempel 1, and a round trip to Mars.
One of the most complicated space explorations in history, Cassini's seven-year journey began from Earth, included two gravity assists from Venus, an Earth gravity assist and, finally, a boost from Jupiter's gravity before its arrival at Saturn. The differential evolution algorithm globally optimized the Cassini mission in 1.2 minutes, Kluever reported. It optimized the Galileo mission in 51 seconds, with even faster times for the Mars and comet missions.
"For the Cassini and Galileo cases, Kluever says, "the optimal route determined by the DE algorithm essentially matched the actual space missions."
A Mars mission is a relatively simple trip, Kluever says. He envisions differential evolution tackling more ambitious missions to asteroids, a Jovian moon, or beyond. Long-distance missions to smaller targets require lots of "travel tricks," Kluever says. Feats of interplanetary prestidigitation might include coasting for more than a year with lots of trajectory-correction maneuvers, then using Venus, Earth and Jupiter for multiple gravity assists.
For a trip to Jupiter's moon Europa that he hopes will someday uncover oceans of frozen water, University of California-Berkeley paleobiologist Jere Lipps worries most about the need to quickly get past damaging radiation. Lipps says DE could play a role in overcoming this obstacle.
"Radiation deteriorates electronics and the mass of the spacecraft must be increased to shield it," Lipps says. "I want to get to those far-off objects with the least radiation exposure, as fast as possible and with the biggest payload. The last two goals seem to be part of the differential evolution program and I suspect radiation avoidance could be part of the program, too."
Using differential evolution to send human crews to near-Earth asteroids intrigues Dave Brody, who sees a time when these once threatening space travelers could become our best friends.
"For the kind of deep space missions differential evolution addresses, asteroids are your crew survival guides, building supply centers and interplanetary gas stations," Brody says. "They're rich in water and heavy metals like iron and nickel." Brody envisions crews constructing and repairing space stations using raw materials from asteroids that might otherwise spell our doom.
"As you know, for every action there's an equal and opposite reaction," Brody says, citing Newton's third law. "For every ton of material you jettison from an asteroid headed toward Earth, you push the asteroid in the opposite direction."
Asteroids are also green, says Brody, at least in the Earth-environmental sense. One day, he says, they'll eliminate strip mining. "Precious metals like titanium, platinum, and palladium that are hard to come by on Earth are far easier to mine on an asteroid," he explains. "Asteroids will become a valuable part of almost every futuristic space mission, in large part because software that uses new algorithms like differential evolution makes travel to them, and landing on them, possible."
Given the potential of differential evolution, it may seem surprising that NASA isn't exactly jumping to adopt the program. Brody isn't surprised. He says the space agency is often slow on the uptake. "NASA has a lot of lessons to learn," he says.
The European Space Agency, on the other hand, has shown interest, as have a number of forward-thinking entrepreneurs. Private space travelers may, in fact, be the first to boldly go where DE takes them. Companies such as Las Vegas-based Bigelow Aerospace are already showing an interest, Brody says.
And indeed, the MU team's paper reads like an enterprising prospectus for making a trek to the stars so inviting that no self-respecting billionaire could possibly resist it.