A multidisciplinary team led by Carnegie Mellon University computer scientist Edmund M. Clarke has received a five-year, $10 million grant from the National Science Foundation's Expeditions in Computing program to create revolutionary computational tools that will advance science on a broad array of fronts, from discovering new cancer treatments to designing safer aircraft.
The researchers will combine Model Checking and Abstract Interpretation, two methods that have been successful in finding errors in computer circuitry and software, and extend them so they can provide insights into models of complex systems, whether they are biological or electronic.
Specifically, computer scientists, biomedical researchers and engineers from eight leading research institutions will use the techniques to better understand what causes deadly pancreatic cancer and the common heart rhythm problem known as atrial fibrillation. At the same time, they will use the techniques to study the embedded computer systems that are increasingly critical to the safe operation of aircraft and automobiles.
"Biological and embedded computer systems may be on opposite ends of the research spectrum, but they pose similar challenges for creating and analyzing computational models of their behavior," said Clarke, the FORE Systems University Professor of Computer Science and the 2007 winner of the Association for Computing Machinery's Turing Award, the computer science equivalent of the Nobel Prize. "Solutions to these problems at either end will enable new approaches to modeling across the spectrum that ultimately will improve health and safety. With this new initiative, I think we finally have achieved the critical mass of expertise and effort needed to crack these puzzles."
In addition to Clarke, who is one of the co-inventors of Model Checking, the research team includes project Deputy Director Amir Pnueli, a New York University computer scientist and a Turing Award winner for his work on systems verification. Among the other notables on the team are Patrick Cousot, an NYU computer scientist and co-inventor of Abstract Interpretation, and James Glimm, a National Medal of Science winner who heads the Department of Applied Mathematics and Statistics at the State University of New York at Stony Brook.
"Professor Clarke has truly assembled a dream team for this important new initiative," said Carnegie Mellon President Jared L. Cohon. "Computational modeling and simulation have become critical to discoveries in almost every scientific discipline, so finding new ways to build and explore these models will pay research dividends for years to come."
Carnegie Mellon is one of three lead institutions receiving the latest round of awards under the National Science Foundation's Expeditions in Computing program. The program, established last year by the Directorate for Computer and Information Science and Engineering (CISE), provides the CISE research and education community with the opportunity to pursue ambitious, fundamental research agendas that promise to define the future of computing and information and render great benefit to society. Funded at levels up to $2 million per year for five years, the Expeditions in Computing program represents some of the largest single investments currently made by the directorate.
Model Checking and Abstract Interpretation are the result of more than 30 years of research. Model Checking is the most widely used technique for detecting and diagnosing errors in complex hardware and software designs. It considers every possible state of a hardware or software design and determines if it is consistent with the designer's specifications; it produces counterexamples when it uncovers inconsistencies. It is limited, however, by the size of the systems it can analyze.
Abstract Interpretation, by contrast, doesn't attempt to look at every possible state of a system, but to develop a simplified approximation of a system that preserves the particular properties that need to be assessed. This makes it possible to analyze very large, complex systems, such as the one million lines of code in the Airbus A380's primary flight control system, but with less precision than is possible with Model Checking.
In this new project, the researchers plan to take advantage of the strengths of both methods by tightly integrating the two into what they call MCAI 2.0.
One of the challenge problems driving this development involves modeling of pancreatic cancer, the fourth-leading cause of cancer deaths in the United States and Europe. Computer modeling is particularly important for discovering how this cancer develops and how it might be detected at an early, treatable stage because researchers have had trouble developing an animal model. Christopher Langmead, a Carnegie Mellon computer scientist, and James Faeder, a computational biologist at the University of Pittsburgh School of Medicine, will lead this effort, working with researchers at the Translational Genomics Research Institute.
"The death last year of our computer science colleague Randy Pausch, who had pancreatic cancer, made all of us at Carnegie Mellon appreciate the importance of improved models for this disease," Clarke said.
Atrial fibrillation, the most common form of heart rhythm disturbance, contributes to congestive heart disease and is responsible for 15 to 20 percent of strokes. Its incidence increases with age, so the aging demographics of America mean that this condition afflicting 2 to 3 million people today could be a problem for 10 million by 2050. A team led by Flavio Fenton, a biomedical researcher at Cornell University, and Radu Grosu, a computer scientist at SUNY at Stony Brook, will explore how modeling can enable physicians to predict the onset of atrial fibrillation.
A growing number of embedded systems are being integrated into cars -- electronic stability control, anti-skid systems, hybrid powertrains, collision-avoidance systems -- though the ability to develop models of how these systems interact with each other is severely limited. Rance Cleaveland, a computer scientist at the University of Maryland, and Bruce Krogh, a Carnegie Mellon electrical and computer engineer, will focus on distributed automotive control and electronic stability control as they lead the development of models that can help manufacturers integrate these systems into automobiles.
The aerospace industry has been a key driver of embedded software technology since the earliest weather-satellite launches of the 1960s, but it is now faced with exponential growth in the size and complexity of these systems in both spacecraft and commercial aircraft. With aircraft manufacturers seeking to better utilize microprocessors, NYU's Cousot and Gerard Holzmann, a computer scientist at NASA's Jet Propulsion Laboratory, will develop models that identify potential conflicts that can occur as microprocessors are shared between systems.
Research will be coordinated through a new Institute for Model Discovery and Exploration of Complex Systems, which will be headquartered in Carnegie Mellon's newly constructed Gates Center for Computer Science.
Considerable education and outreach activities are planned. These include an interdisciplinary educational program in complex systems science directed by Scott Smolka, a computer scientist at SUNY at Stony Brook, and minority-focused summer workshops on complex embedded and biological systems under the direction of Nancy Griffeth, a computer scientist at the City University of New York's Lehman College.
Clarke emphasized that Carnegie Mellon will funnel the bulk of its project money to support graduate students, rather than faculty salaries. In addition to the NSF grant, the School of Computer Science and the Ray and Stephanie Lane Center for Computational Biology at Carnegie Mellon are providing supplemental support for the project.