|
Van Hentenryck in the hunt for algorithm that takes uncertainty into account
Five cutting-edge computer science projects at Brown were among the winners of the highly competitive National Science Foundation awards for information technology research. These extraordinary projects — which, if fully realized, will allow medical students to participate in a surgery that may have taken place months ago, or quadriplegics to move a robotic arm simply by thinking about it — won the scientists nearly $5 million of the $156 million distributed.
See additional articles:
By Cynthia Ferguson
Airlines routinely rely on sophisticated computer programs to schedule their hundreds of flights, planes, and crew members. As long as nothing unpredictable occurs — a rare event, of course, in real life — these scheduling programs work beautifully.
When a snowstorm threatens to close an airport, however, it’s a human being who has to step in and decide how to reroute planes and reschedule passengers. Despite having at their disposal mountains of electronic data on the weather, passenger itineraries, flight schedules and crew status, the airlines still rely on people to handle arrangements when the unexpected happens.
The introduction of unknown variables — such as weather — has long challenged computer scientists who develop scheduling and planning programs. When some of the input is unknown, they face what is called "stochastic combinatorial optimization."
"Although these problems occur all the time in industry, no one knows a good algorithm for solving them," says Pascal Van Hentenryck, professor of computer science. "They are among the toughest problems in computer science."
Still, Van Hentenryck and his collaborators from Brown, the Massachusetts Institute of Technology and the Georgia Institute of Technology remain undaunted. With their $1,484, 000 grant from the National Science Foundation, they hope to develop some of the methodology and tools needed to address the role of uncertainty in complex scheduling and planning.
Van Hentenryck’s team brings an impressive background to the problem – critical, Van Hentenryck says, to meeting this challenge. "This is not something that one person working alone would ever be able to solve," he notes. "It’s an area that is still relatively virgin and one that requires people with a lot of expertise in different fields."
Van Hentenryck has worked extensively in combinatorial optimization — the kind of sophisticated optimization programs that airlines and other industries currently rely on to maximize efficiency. Eliezer Upfal, also of the Brown computer science department, brings years of experience exploring the structure of stochastic problems. Their colleagues from M.I.T. and Georgia Tech supply expertise in these and related technologies — integer programming and approximation algorithms.
By studying specific problems, Van Hentenryck and his team hope to extract some basic principles behind stochastic combinatorial optimization. "Some believe we’ll never be able to solve this well," Van Hentenryck says, "but I think that in four years we’ll have made some substantial progress. I think we’ll have some of the building blocks."
|
