Street smarts

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.

Beaumont and his teammate Blessing Okeke, a teaching fellow in applied mathematics, chose a different approach. They wrote an algorithm that finds a viable (though inefficient) solution quickly and then "perturbs" it with random changes to try to improve it in the remaining time.

“I think we got a good high-level idea of what the problem was pretty quickly,” said Beaumont. “The main problem is that there are so many potential solutions you can try, so you have to be intelligent about the different options you explore.”

They found success with simulated annealing, a technique inspired by metallurgy, in which a metal is repeatedly heated and cooled so that the particles can settle into place and harden. In an algorithmic sense, it's a way to repeatedly identify slight improvements to a solution.

"It's a really interesting application of physics, computationally, to a real system," said Rosalind Reid, Executive Director of IACS.

The teams, coached by lecturers Mauricio Santillana and Pavlos Protopapas, presented their approaches for feedback from Ergun and members of the IACS advisory board partway through the Challenge.

“When you characterized the problem, I think you characterized it correctly as saving lives rather than finding the very best solution,” Guy Steele ’75 told the first team. “If you’re in a search space where just finding a ‘good enough’ solution is adequate, you can probably find much faster algorithms.”

To win the Challenge, he added, “You don’t necessarily have to find the very best answer."

With a hypothetical population of 2,478 victims, and penalties accruing at the end of each period, the final scores were expected to be somewhere between 5,122 (the estimated best possible solution given unlimited computing power) and approximately 10,000 (clearing roads at random).

Beaumont and Okeke won the Challenge by saving the most people in the shortest time, achieving a final score of 6,793.

It was clear, however, that the winners' excitement had less to do with the iPad prizes and more to do with the Challenge experience—just what Protopapas had expected when he conceived of organizing a student challenge during the winter break.

“It gives them an opportunity to get down to doing a hard problem,” said Ergun. “I imagine that’s an empowering thing to do.”

Blessing Okeke and Chris Beaumont won the IACS Computational Challenge.

To read more about the IACS Computational Challenge and the winning approach, visit Chris Beaumont's blog.

Computational science

Computational science is a broad field with essential applications in almost all areas of life, from economics to neuroscience, and from traffic lights to astrophysics. Computational algorithms allow researchers to delve into problems far too complex for either human calculations or random trial and error, even by a supercomputer.

Computational skills are playing an increasingly important role in graduate studies in science and engineering. At SEAS, for instance, computational techniques are used to model fluid dynamics in human arteries, to analyze climate data and plate tectonics, to understand the chemistry of biological systems, and to evaluate privacy in information networks.

To support the development of 21st-century skills, SEAS recently introduced a new graduate secondary field in computational science.