Pascal Van Hentenryck and Andy van Dam have both been awarded large grants in this second year of NSF's Information Technology Research (ITR) competition. Their proposals were among the 309 selected from a field of over 2000. NSF director Rita Colwell, in announcing the grants, said ``NSF is proud to be a leader with these bold ITR projects, Through long-term, high-risk research, we expect a wide range of positive results that will benefit the nation as a whole. Our objective is to support the development of software and IT services that will help scientists and engineers make the kind of discoveries that will eventually be applied by industry.''
Pascal's grant, for work in conjunction with Eli Upfal of this department and researchers at MIT and Georgia Tech, is on ``Stochastic combinatorial optimization'' and will yield $1,484,000 over four years. Andy van Dam's three-year, $1,750,000 grant, ``Electronic books for the tele-immersion age: a new paradigm for teaching surgical procedures,'' will directly involve researchers from the University of North Carolina - Chapel Hill as well as Brown and indirectly researchers from UPenn, working with those from UNC on realtime 3D model acquisition and reconstruction.
Pascal summarizes work under his new grant as follows: Optimization is the science that integrates information into a mathematical model whose solution yields optimal decisions. It has developed into a indepdent discipline and is now routinely used in industry. However, there are many real optimization problems for which no solutions are known. For instance: a snowstorm is approaching Chicago and United Airlines, at its Operations Center, must plan how to cancel and reroute its flights. Although substantial information on weather forecasts, plane and crew status, passenger itineraries, and hotels is available electronically, this information is not exploited in a scientific way. Instead, humans make ad-hoc decisions based only on their experience. Why is this the case, especially when the airline is a very sophisticated user of optimization for planning? Because the application is a large-scale stochastic combinatorial optimization problem for which no known algorithm produces good solutions in reasonable time.
Our fundamental research in this relatively unexplored area will have two complementary thrusts: (1) exploiting the orthogonal strengths of constraint and mathematical programming to tackle the hard combinatorial problems arising in stochastic optimization (e.g., multistage or Monte Carlo approaches) and (2) studying stochastic combinatorial substructures that are amenable to efficient solutions or approximations.
Of his grant, Andy says: Tele-immersion will provide a dramatic new medium for groups of people remote from one another to work and share experiences in an immersive 3D virtual environment, much as if they were co-located in a shared physical space. Immersive ``time machines'' will add an further important dimension, that of recording experiences in which a viewer, immersed in a 3D reconstruction, can literally walk through the scene or move backward and forward in time. While there are many potential application areas for such novel technologies, including maintenance and repair, design and virtual prototyping, paleontological and archaeological reconstruction, and the like, we will focus on a societally important and technologically challenging driving application, teaching surgical management of difficult, potentially lethal injuries.
We will develop a new paradigm for teaching surgical procedures: immersive electronic books that in effect blend a time machine with 3D hypermedia. Our goal is to allow surgeons to witness and explore (in time and space) a past surgical procedure as if they were there, with the added benefit of instruction from the original surgeon or another instructor as well as integrated 3D illustrations, annotations, and relevant medical metadata. The trainee should be able freely and naturally to walk around a life-sized, high-fidelity 3D graphical reconstruction of the original time-varying events, pausing or stepping forward and backward in time to satisfy curiosity or allay confusion. We will bring together experts in the respective disciplines and leverage our prior work in tele-immersion in order to achieve these goals.