Street smarts

Students develop hurricane response plans on Cambridge roads, gaining practical experience in computational science
Debris lingered just outside New Orleans in July 2006--almost a full year after Hurricane Katrina devastated the region. Photo courtesy of Flickr user Angie M. Photography.

Imagine a powerful hurricane has wreaked havoc on the city of Cambridge, Mass. Thousands of residents are injured, but debris blocks roads everywhere, preventing medical workers from reaching the victims.

Crews are mobilizing to clear paths between the victims and two medical centers, Mount Auburn Hospital and Harvard University Health Services. Which roads should they open first, in order to quickly reach the largest number of victims? How many of those roads can they actually clear each day with the equipment available?

This was the problem posed to tech-savvy students participating in the IACS Computational Challenge in January. The competition was part of ComputeFest , a 2-week program hosted by the recently created Institute for Applied Computational Science (IACS) within the Harvard School of Engineering and Applied Sciences (SEAS).

"The amount of debris created by regularly occurring disasters is huge," said Özlem Ergun , Visiting Associate Professor of Applied Mathematics at SEAS. In her usual post, Ergun is co-director of the Center for Health and Humanitarian Logistics at Georgia Institute of Technology, where she helps emergency management officials plan their response to disasters.

"The first problem," she said, "is really to figure out in what order to open the streets so that you create connectivity between the population and the critical infrastructure."

The Cambridge debris data was generated by Georgia Tech graduate students using the Federal Emergency Management Agency (FEMA) Hazus software, which visually models the human and environmental impacts of earthquakes, hurricanes, and floods.

In the Challenge scenario, 2,478 disaster victims were distributed unevenly across 443 Cambridge locations served by two hospitals (one large, one small), connected by 604 road segments (blocked by varying amounts of debris), and accessed via a fleet of bulldozers that roughly doubled in size over a 9-day cleanup period. A penalty was imposed to simulate the real-life pressure of time--the chance of people losing their lives if help took too long to arrive.

In short, the number of data points and constraints was huge.

The two teams were asked to write code that would find a decent solution within 3 hours’ time on the high-performance computing cluster at SEAS.

"It’s very tricky in that there are these simultaneous competing goals," said Chris Beaumont, a visiting student in astronomy at Harvard’s Graduate School of Arts and Sciences. "If it was just, ’Here’s a map of a city and you have to establish the most efficient path to clear the debris to connect everybody,’ that would be pretty easy--that’s a well-known problem. Or if it was just, ’Clear things as fast as possible,’ that might be easy. But it’s a combination of different factors, which means you may not take the most efficient path. You might dig some kind of awkward path to get to a really important area as quickly as possible."

For a problem this complex, the teams had to translate every parameter and constraint into the vocabulary of network theory. Hospitals became "source nodes"; population points became "demand nodes." Roads became "edges," each with a weight corresponding to the resources required to clear it. Through the lens of computational science, the storm-ravaged city became a vast data set and a question of multi-period network expansion.

"Most of our creativity went into formulating the problem," reflected Ariana Minot, a first-year graduate student in applied mathematics. "I’ve never tried to solve a problem that wasn’t in the context of the course I’d taken, where there were assumptions about what kind of methods to use, so that was really different."

A visualization of the roads cleared by Day 5, in the solution devised by Ariana Minot, Yu Qin, and Yifan Wu ’14.

Minot and her teammates, Yu Qin and Yifan Wu ’14, knew early on that they would need to devise an algorithm that could see the "big picture." A poor algorithm might start opening roads in a westward direction to reach a nearby pocket of 20 people, blind to the fact that a group of 100 people were only slightly further away, to the east.

Their final algorithm drew on a concept from biology, imitating the strategy of foraging ants. As the insects explore the environment around the nest, they leave a trail of pheromones that gradually evaporates. The ants follow their neighbors’ familiar scent, so the shortest, most efficient paths become more frequently traveled. As a result, despite the randomness of the ants’ initial explorations, the colony as a whole is able to quickly select the optimal route to the food.