NSF Expeditions, 2008-2012

This pages contains a list of NSF Expeditions projects that were started in 2007 to 2012.

2008

Expedition to Understand, Cope with, and Benefit From Intractability

• Lead PI: Sanjeev Arora (Princeton)
• Collaborators: Rutgers University, New York University and the Institute for Advanced Study
• In their Expedition to Understand, Cope with, and Benefit From Intractability, Sanjeev Arora and his collaborators at Princeton University, Rutgers University, New York University and the Institute for Advanced Study will attack some of the deepest and hardest problems in computer science, striving to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms. Computational intractability, a concept that permeates science, mathematics and engineering, limits our ability to understand nature or to design systems. The PIs hope to better understand the boundary between the tractable and the intractable. This has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines and to cast new light on fields such as quantum computing, secure cryptography and pseudorandomness. The research team plans to draw on ideas from diverse fields including algorithms, complexity, cryptography, analysis, geometry, combinatorics and quantum mechanics.

Expedition Computational Sustainability: Computational Methods for a Sustainable Environment, Economy, and Society

• Lead PI: Carla Gomes (Cornell)
• Collaborators: Bowdoin College, the Conservation Fund, Howard University, Oregon State University and the Pacific Northwest National Laboratory
• In the Expedition Computational Sustainability: Computational Methods for a Sustainable Environment, Economy, and Society, Carla Gomes and her colleagues at Cornell University, Bowdoin College, the Conservation Fund, Howard University, Oregon State University and the Pacific Northwest National Laboratory will explore the development and application of computational methods to enable a sustainable environment, economy and society. By tackling challenges that have not traditionally been addressed by computational approaches, Gomes and her team hope to create a new field of computational sustainability--much like computational biology has arisen in past decades--that will stimulate new research synergies across the areas of constraint optimization, dynamical systems, and machine learning. The research team is highly interdisciplinary, bringing together computer scientists, applied mathematicians, economists, biologists and environmental scientists.

Open Programmable Mobile Internet 2020

• Lead PI: Nick McKeown (Stanford)
• In the Open Programmable Mobile Internet 2020 project, Nick McKeown and his colleages at Stanford University address fundamental issues emerging in the forthcoming broadband wireless mobile revolution. It aims to create an "open" alternative to mobile ubiquitous computing and communication that can spur innovations, which will have a dramatic impact on the choices users will have in the way their data and information is computed, stored and communicated. Their architecture will enable: identity-based computing that frees us from managing a large number of physical and digital keys and enables the development of an integrated security infrastructure; a fluid computing experience that provides seamless access to data and applications anywhere and on any available network; an open, programmable and secure environment, where it is easy both to write and deploy applications on devices that are secure and to enable remote services and backup storage in the cloud; and fast radio access networks where new radio technology mitigates interference, exploits diversity at all levels and improves transmit channel knowledge.

Molecular Programming Project

• Lead PI: Eric Winfree (Caltech)
• Collaborators: U. Washington
• In the Molecular Programming Project, Erik Winfree and his colleagues at the California Institute of Technology and University of Washington will develop fundamental computer science principles for programming information-bearing molecules like DNA and RNA polymers and demonstrate their application experimentally. Inspired by the biomolecular programs of life--from the low-level operating system controlling cell metabolism to the high-level code for development, the process by which a single cell becomes an entire organism--Winfree and his colleagues are working to create analogous molecular programs using non-living chemistry. The objects of their study, molecular programs, are collections of molecules that may perform a computation, fabricate an object or control a system of molecular sensors and actuators. The project aims to develop tools and theories for molecular programming--such as programming languages and compilers--that will enable systematic design and implementation of technological and biotechnological applications that require information processing and decision-making to be embedded within and carried out by chemical processes.

2009

Next-Generation Model Checking and Abstract Interpretation with a Focus on Embedded Control and Systems Biology

• Lead PI: Edmund M. Clarke, Carnegie-Mellon University
• Collaborators: CUNY, NYU, Stony Brook, University of Maryland, Cornell, Jet Propulsion Laboratory
• Computer hardware and software systems can be found in almost all aspects of modern life. While most of us think of computers as the machines on our desks, hardware and software systems embedded in a multiplicity of complex physical systems perform a growing number of important societal functions. For example, embedded computers make our airplanes and cars safer and more efficient, they make our national power grid more reliable, and they provide new diagnostic and therapeutic capabilities in healthcare, ranging from medical imaging systems to implantable heart devices. As these tightly integrated cyber-physical systems perform increasingly complex and important functions, we must engineer them in a way that ensures we can bet our lives on them. This Expedition seeks to explore the use of model checking and abstraction interpretation to analyze and predict the behavior of complex embedded and dynamical cyber-physical systems. The research team will develop the next generation of tools and technologies necessary to enable exhaustive analysis of the behavior of increasingly complex systems, promising safer, more secure embedded cyber-physical systems such as those found in automotive and aerospace applications. Furthermore, the researchers participating in this Expedition intend to use these new tools and technologies to develop transformative systems biology models, promising a deeper understanding of complex biological systems such as inter- and intra-cellular signaling in pancreatic cancer.

Customizable Domain-Specific Computing

• Lead PI: Jason Cong, UCLA
• Collaborators: Rice, UC Santa Barbara, Ohio State University
• Sometimes one-size solutions just don't meet all our needs. Human civilization has made great advances through specialization, yet most computer users have limited choices when it comes to the type of hardware and software systems they can use to solve a problem in a particular area. The researchers involved in this Expedition believe customized computing has the potential to deliver order-of-magnitude improvements in energy efficiency, development effort, time-to-solution, cost, and overall productivity by crafting computing tools tailored to specific applications and needs. The key to the team's success is a customizable heterogeneous platform that includes a wide range of customizable computing elements, customizable and scalable high-performance interconnects based on RF-interconnect technologies; highly automated compilation tools and runtime management systems to enable rapid development and deployment of domain-specific computing systems, and a general, reusable methodology for replicating success in different application domains. In the spirit of hardware-software co-design, the research team will balance software and hardware considerations to better expose opportunities for order-of-magnitude improvements in computing efficiency, while using a software approach that supports automation and reuse and is accessible to domain experts. To demonstrate the power of their approach, the team will apply their domain-specific computing design techniques to revolutionize the role of medical imaging and hemodynamic modeling in healthcare, promising cost-effective, yet convenient solutions for preventative, diagnostic, and therapeutic procedures.

RoboBees: A Convergence of Body, Brain and Colony

• Lead PI: Robert Wood, Harvard University
• Collaborators: Northeastern University
• Busy as a bee. A hive of activity. Bees and bee colonies have long been held up as models of efficiency and coordination. Using a host of different sensors, unique communication protocols, and a precise hierarchy of task delegation, thousands of bees can work independently on different tasks while all working toward a common goal--keeping their colony alive. Researchers in this Expedition will create robotic bees that fly autonomously and coordinate activities amongst themselves and the hive, much like real bees. The research team aims to drive research in compact high-energy power sources, ultra-low-power computing, and the design of distributed algorithms for multi-agent systems. Furthermore, the RoboBees created will provide unique insights into how Mother Nature conjures such elegant solutions to solve complex problems.

2010

Computational Behavioral Science: Modeling, Analysis, and Visualization of Social and Communicative Behavior

• Lead PI: James Rehg, Georgia Tech
• Collaborators: USC, Boston University, UIUC, CMU, MIT
• It is well-known that the social and communicative behavior of children as young as 12-24 months contains important clues about their risk for a variety of developmental disorders, such as autism and Attention Deficit Hyperactivity Disorder (ADHD). Moreover, the ability to identify and treat such disorders at an early age has been shown to significantly improve outcomes. Autism represents a particularly compelling need in the US, since it affects one child in 110 with a lifetime cost of care at $3.2 million per person. This Expeditions project aims to develop novel techniques for measuring and analyzing the behavior exhibited by children and adults during face-to-face social interactions, including interactions between caregivers and children, children playing and socializing in a daycare environment, and clinicians interacting with children during individual therapy sessions. By developing methods to automatically collect fine-grained behavioral data, this project will enable large-scale objective screening and more effective therapy delivery and assessment to those in need, including socio-economically disadvantaged populations. More generally, this new computational technology will make it possible to automatically measure the behavior of large numbers of individuals in a wide range of settings over long periods of time. Other disciplines, such as education, marketing, and customer relations, could benefit from a more objective data-driven approach to behavioral assessment. The long-term goal of this project is the creation of a new scientific discipline of computational behavioral science, which draws equally from computer science and psychology in order to transform the study of human behavior.

Understanding Climate Change: A Data Driven Approach

• Lead PI: Vipin Kumar, University of Minnesota
• Collaborators: North Carolina A & T University, North Carolina State University, Northwestern University, University of Tennessee/Oak Ridge National Laboratory
• Climate change is the defining environmental challenge facing our planet. Yet, there is considerable uncertainty regarding the social and environmental impact due to the limited capabilities of existing physics-based models of the Earth system. Consequently, important questions relating to food security, water resources, biodiversity, and other socio-economic issues over relevant temporal and spatial scales remain unresolved. A new and transformative approach is required to understand the potential impact of climate change. Data driven approaches that have been highly successful in other scientific disciplines hold significant potential for application in environmental sciences. This Expeditions project aims to address key challenges in the science of climate change by developing methods that take advantage of the wealth of climate and ecosystem data available from satellite and ground-based sensors, the observational record for atmospheric, oceanic, and terrestrial processes, and physics-based climate model simulations. These innovative approaches will help provide new understanding of the complex nature of the Earth system and the mechanisms contributing to the adverse consequences of climate change, such as increased frequency and intensity of hurricanes, precipitation regime shifts, and the propensity for extreme weather events that result in environmental disasters. Methodologies developed as part of this project will be used to gain actionable insights and to inform policymakers.

Variability-Aware Software for Efficient Computing with Nanoscale Devices

• Lead PI: Rajesh Gupta, University of California, San Diego
• Collaborators: Stanford, UC Irvine, UCLA, University of Illinois at Urbana-Champaign, University of Michigan
• As semiconductor manufacturers build ever smaller circuits and chips, they become less reliable and more expensive to produce--no longer behaving like precisely chiseled machines with tight tolerances. Understanding the variability in their behavior from device-to-device and over their lifetimes--due to manufacturing, aging, and different operating environments--becomes increasingly critical. This project fundamentally rethinks the hardware-software interface and proposes a new class of computing machines that are not only adaptive but also highly energy efficient. It envisions a computing system where components--led by proactive software--routinely monitor, predict and adapt to the variability of the manufactured systems in which they are placed. These machines will be able to discover the nature and extent of variation in hardware, develop abstractions to capture these variations, and drive adaptations in the software stack from compilers to runtime to applications. The resulting computer systems will work while using components that vary in performance or grow less reliable over time and across technology generations. A fluid software-hardware interface will thus mitigate the variability of manufactured systems and make machines robust, reliable and responsive to the changing operating conditions. Changing the way software interacts with hardware offers the best hope for perpetuating the fundamental gains of the past 40 years in computing performance at a lower cost. In addition to plans for involving graduate and undergraduate students in the research, the team has built strong industrial ties and is committed to outreach to community high-school students through a combination of tutoring and summer school programs.

2011

• No awards

2012

An Expedition in Computing for Compiling Functional Physical Machines

• Lead PI: Daniela Rus, Massachusetts Institute of Technology (MIT)
• Collaborators: University of Pennsylvania and Harvard University
• This project envisions a future where 3-D robotic systems can be produced and designed using 2-D desktop technology fabrication methods. If this feat is achieved, it would be possible for the average person to design, customize and print a specialized robot in a matter of hours. Currently, it takes years and many resources to produce, program and design a functioning robot. This new project would completely automate the process, from sketches on-demand, anywhere, and with the skill of a team of professional engineers, leading to potential transformations in advanced manufacturing.

Making Sense at Scale with Algorithms, Machines and People (AMP)

• Lead PI: Michael Franklin, University of California (UC) Berkeley
• AMP will tackle the challenge known as the Big Data problem, in which current data analytics fall short in making sense of the volume, diversity and complexity of data being generated by computers, sensors and scientific instruments; media such as images and video; and free-form tweets, text messages, blogs and documents. AMP seeks to turn this knowledge into insight, to uncover the keys to solving huge societal problems, from improving productivity and efficiency and creating new economic opportunities, to unlocking discoveries in medicine, science and the humanities. The team will focus on key societal applications, including: cancer genomics and personalized medicine; large-scale sensing for traffic prediction, environmental monitoring, and urban planning; and network security.

ExCAPE: Expeditions in Computer Augmented Program Engineering

• Lead PI: Rajeev Alur, University of Pennsylvania
• Collaborators: Cornell, MIT, University of California Los Angeles, University of Illinois at Urbana-Champaign, University of Maryland, University of Michigan, UC Berkeley, Rice University
• ExCAPE aims to change computer programming from the tedious, error-prone, purely manual task it has always been to one in which a programmer and an "automated program synthesis tool" collaborate to generate software that meets its specifications. Computers have revolutionized daily life, and yet the way computers are programmed has changed little in the last several decades. The ExCAPE team brings together expertise in theoretical foundations (computer-aided verification, control theory, program analysis), design methodology (human-computer interaction, model-based design, programming environments), and applications (concurrent programming, network protocols, robotics, system architecture) to pursue research focused on developing new computational engines for transformation and integration of synthesis artifacts, and effective methods for programmer interaction and feedback.

Making Socially Assistive Robots

• Lead PI: Brian Scassellati, Yale University
• Collaborators: MIT, University of Southern California, Stanford University
• This Expedition will develop the fundamental computational techniques that will enable the design, implementation and evaluation of robots that encourage social, emotional and cognitive growth in children. Critical societal problems require sustained, personalized support that supplements the efforts of educators, parents and clinicians. For example, clinicians and families struggle to provide individualized educational services to children with social and cognitive deficits, whose numbers have quadrupled in the U.S. in the last decade alone. In many schools, educators struggle to provide language instruction for children raised in homes where a language other than English is spoken, the fastest-growing segment of the school-age population. This Expedition aims to support the individual needs of these children with socially assistive robots that help to guide the children toward long-term behavioral goals that are customized to the particular needs of each child and that develop and change as the child does.