A team of engineers from Penn State and The Aerospace Corporation have created a set of software tools that takes its cues from natural evolution and applies them to solving large, complex planning problems.
Patrick Reed, associate professor of civil engineering, said the evolutionary algorithmic tools, dubbed Genetic Resources for Innovations in Problem Solving (GRIPS), can be applied to very complicated problems that require decision makers to balance trade-offs for costs, risks and several performance goals.
"Evolutionary algorithms abstract an engineering design into its controlling variables and you make them fight to survive. You create computer algorithms that just like mating and mutation in the natural world, you mate and mutate the designs" variables. And those designs that have a better trait get propagated. The idea is when you have huge spaces, really complicated engineering, science or policy problems, these types of algorithms give you a lot more freedom in terms of the complexities you can incorporate," he said.
Development of GRIPS began when Matthew Ferringer started his advanced degree work in 2005. Ferringer, who was a 2008 Penn State aerospace engineering doctoral graduate, became interested in Reed's efforts in solving computationally demanding water management problems where decision makers are confronted with lots of conflicting objectives.
"Matt saw what we were doing and had some of his own ideas," Reed said. The collaboration continued after Ferringer completed his doctorate and continued his work with The Aerospace Corporation as a project leader.
The result was GRIPS. Using it, the team began to try to discover the complex tradeoffs decision makers face in problems such as airline flight scheduling and satellite constellation design.
Ferringer said with airlines "some of the key concerns decision makers must trade-off include profit, cost, revenue generated and how disruptive any changes are to the existing schedule."
He stated that an airline could focus on one factor, such as maximizing profit, but doing so could result in a high number of schedule disruptions that would be expensive and difficult to implement. GRIPS exploits massively parallel evolutionary search to take into account the airline's different priorities, examines the possibilities and begins whittling them down. In the airline example, the team examined the airline's actual schedule, consisting of hundreds of flights.
"In the scheduling design space, where many hundreds of trillions of schedules are possible, GRIPS is able to not only find efficiency improvements but also illustrate where those gains might come at the cost of significant disruption to the network. The competitive advantage that GRIPS brings to the table is that all of this is accomplished by evaluating a very small fraction of the possibilities," Ferringer said.
As part of the collaboration Reed and Ferringer are also exploring how scientific visualization can be used to help decision makers understand their tradeoffs. Decision makers are allowed to play with their problem in a highly visual and interactive way where they can look at different design options, experiment with new ideas and easily eliminate designs that don't suit their needs.
"The whole point in visualizing the tradeoffs GRIPS finds in this manner is it shows you the data in a very intuitive way," Ferringer stated. "For example for the airline application, we were able to show that the most disruptive schedule changes did not translate into maximum profit. Rather those GRIPS solutions that disrupted approximately half of the current schedule maximized profit on the order of several hundred million dollars per annum. However, the visualization also quickly helped us observe several solutions that exhibited very minimal disruption for about half of the maximum profit. The later set of schedules, offered the greatest profit at minimal disruption."
The final result of the GRIPS evolutionary process was 120 possible airline schedules.
"One hundred and twenty possibilities is a tiny, tiny fraction," he said. "But these are the solutions that have market value instantly to the company. The idea is to give these airlines a set of good answers they can make an informed decision from."
Reed said, "It opens the problem up from looking at one magical solution to an array of possibilities."
Ferringer said before GRIPS, one approach an airline might take to increase efficiency is to have a group of employees experimenting with small changes to an existing schedule and evaluating the consequences of the changes. They might be forced to use this approach because of the extreme complexity and interdependencies of the network.
"With GRIPS, we are able to go way beyond tweaks and cast a net over the vast ocean of possibilities by pulling out high quality schedules while at the same time helping planners understand the costs and benefits for implementing them. There's a tremendous satisfaction because you don't need to go to bed with buyer's remorse, thinking 'Did I miss something?'"
Timothy Thompson, a senior engineering specialist with The Aerospace Corporation, added, "It's a very competitive market, so just a little bit of an edge can make a huge difference."
In the case of designing, maintaining, and replenishing satellite constellations, engineers have to consider complex design factors and tradeoffs between the desired effectiveness and the cost to achieve it.
Ferringer said, "Classically, the design of satellite constellations follows an intensely iterative process where a handful of designs, that often have their foundations in knowledge gained by decades of experience, are evaluated. The process can guide decision makers to a result colored by their experiences. Using GRIPS we help frame the debate between mission stakeholders by focusing their attention on the key tradeoffs which can confirm or contradict past experience. It is from the contradictions that the seeds of innovation are sown."
"The evolution of ideas takes a very long time, decades sometimes," Reed said. "What if we could accelerate that and give people a bigger view of their critical tradeoffs at a much higher dimension? To be able to give them three, four, five, six, seven things they care about -- that's a leap that is just now occurring with the computing resources available."
Reed said that Penn State and The Aerospace Corporation have entered into a memorandum of understanding where GRIPS will be licensed for companies to use. One firm, Apptimation LLC, has already licensed the technology for aviation, energy, finance, logistics and travel applications.
The civil engineer said GRIPS could be applied to a number of areas, including environmental problems, water markets and risk management. "GRIPS is an engine for discovery because it lets us consider really complicated problems, allows us to explore them and discover their often surprising trade-offs."