Techy-savvy students developed hurricane response plans in SEAS competition
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. 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 two teams of tech-savvy students participating in the IACS Computational Challenge in January. The competition was part of ComputeFest, a two-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 amount of debris created by regularly occurring disasters is huge,” said Özlem Ergun, visiting associate professor of applied mathematics at SEAS. Photo by Eliza Grinnell/SEAS
The Cambridge debris data was generated by Georgia Tech graduate students using the Federal Emergency Management Agency (FEMA) Hazussoftware, which visually models the human and environmental impacts of earthquakes, hurricanes, and floods.
In the Computational 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 nine-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 three 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.”
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,” IACS board member and Oracle software architect 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.”
To read more about the IACS Computational Challenge and the winning approach, visit Chris Beaumont’s blog.
About Harvard Medical School (HMS)
Driving Change. Building Momentum. Making History.
“Since 1872, Harvard Medical School has been the incubator of bold ideas—a place where extraordinary people advance education, science and health care with unrelenting passion.
Whether training tomorrow’s doctors and scientists, decoding the fundamental nature of life, advancing patient care or improving health delivery systems around the world, we are never at rest. Allied with some of the world’s best hospitals, research institutes and a University synonymous with excellence, the School’s mission remains as ambitious as it is honorable: to alleviate human suffering caused by disease.”
About Harvard School of Public Health (HSPH)
Harvard School of Public Health is dedicated to advancing the public’s health through learning, discovery and communication. More than 400 faculty members are engaged in teaching and training the 1,000-plus student body in a broad spectrum of disciplines crucial to the health and well being of individuals and populations around the world. Programs and projects range from the molecular biology of AIDS vaccines to the epidemiology of cancer; from risk analysis to violence prevention; from maternal and children’s health to quality of care measurement; from health care management to international health and human rights.
About Harvard University.
Established in 1636, Harvard is the oldest institution of higher education in the United States. The University, which is based in Cambridge and Boston, Massachusetts, has an enrollment of over 20,000 degree candidates, including undergraduate, graduate, and professional students. Harvard has more than 360,000 alumni around the world.
Harvard University is devoted to excellence in teaching, learning, and research, and to developing leaders in many disciplines who make a difference globally. Harvard faculty are engaged with teaching and research to push the boundaries of human knowledge. For students who are excited to investigate the biggest issues of the 21st century, Harvard offers an unparalleled student experience and a generous financial aid program, with over $160 million awarded to more than 60% of our undergraduate students. The University has twelve degree-granting Schools in addition to the Radcliffe Institute for Advanced Study, offering a truly global education.
‘Universities nurture the hopes of the world: in solving challenges that cross borders; in unlocking and harnessing new knowledge; in building cultural and political understanding; and in modeling environments that promote dialogue and debate… The ideal and breadth of liberal education that embraces the humanities and arts as well as the social and natural sciences is at the core of Harvard’s philosophy. ’/ Drew Gilpin Faust
* The above story is adapted from materials provided by Harvard University