This story is over 5 years old.

An Algorithm for Escaping a Burning Building

The algorithmic way to find the nearest exit.
April 29, 2015, 12:15pm

It's a bad scene on the tenth floor. The fire downstairs spread fast, no one seems to know quite what's going on, and the fire department only just arrived. At least one stairwell is blocked and the accounting department is panicking. The decisions made now will determine the survival of the building's occupants. Where do you turn?

One possible answer, according to a pair of recent papers published in the Journal of Computer​ Science and Applied Mathematica​l Sciences, is Dijkstra's algorithm. Both authored by the same team at the Technical University of Malaysia Malacca, one paper describes an algorithm and the other a theoretical autonomous evacuation navigation (AEN) system based on one.

The idea is the same: Take a building layout plan and merge it with what's known as a visibility​ graph, which is a graph in the graph theory sense—a series of nodes and connections, or "edges"—but with the additional feature of polygonal shapes or obstacles that must be avoided. It's easier just to see it (below). Navigating the graph requires that the navigator move from visible point to visible point while taking the shortest possible path around the obstacles. This is different from the typical graph theory graph, which assumes the nodes and edges are in empty space.


The solution comes in the form of Dijkstra's algorithm, which is the reigning champion of "shortest path" navigation and what you'll find (or a modified version of it) powering Google Maps and many, many other real-world applications. It's incredibly clever and almost obvious. The general idea is that from node to node, the navigator continually updates the shortest path to the next neighboring nodes based on the shortest path to the current node.

Read more: The Simple, Elegant Algorithm That Makes Google Maps Possible

It's still a time-consuming process, but given even the smallest graphs, the costs of calculating every possible route from start to finish would quickly become computationally impossible.

Visibility graph merged with building layout. Image: Samah et al

"Decision making during an emergency situation has to be made in perfect timing in order to reduce the evacuation time and avoid injuries," the researchers write in their paper. "Making the best decision during the evacuation is very difficult for the evacuees, most of the times they do not know which is the best route they should choose to reach the exit especially in a building since they are unfamiliar with the building structure. Moreover, the building structure changes due to the spreading of presence hazard and the task of finding a safe route is more difficult."

The AEN system is based on dynamic signage. So, if there were an emergency, evacuees could take the best, shortest route out of the building based on, say, the color of different exit signs: green for optimal, yellow for safe but slower, red for no good at all. Or something like that—the papers don't elaborate on the potential implementation much. The point is mostly that it works as intended, finding the shortest path around obstacles in a building.

"Dijkstra's algorithm has proven its advantages to solve the wayfinding problem towards the safest and shortest path in emergency evacuation," the researchers conclude. "Through this study, we able to avoid the hazardous location through blocking the affected area, calculate, and provide the updated path. It contributes the significance to the AEN system in terms of wayfinding navigation, and makes the system more intelligent and automated."