Network Algorithms for Smart Fire Evacuation


Thesis Advisor: Dr. Malick Ndiaye

Behavioral research in fire protection engineering reveals that evacuee response to a fire alarm going off is often suboptimal. The decision to begin evacuation is often delayed by other unproductive behaviors, such as exploring the surroundings to find the hazard, gathering personal belongings, looking for group members, or engaging in groupthink: Looking at others for behavioral cues to decide whether to ignore the fire alarm or to take it seriously. If individuals have been exposed to many false alarms, it is a common response to ignore the fire alarm and continue normal activities, expecting the alarm to be turned off by the building management.

Even in the fortunate event that occupants make the rational decision to evacuate immediately, research has shown that they are very prone to choosing suboptimal exits, often trying to leave the building the same way they entered it, or instinctively ignoring exits with negative labeling, i.e., doors that would normally trigger a fire alarm if opened and whose use is prohibited or penalized by the institution in non-emergency situations.

For those reasons, the fire research community concluded that there is an urgent need to develop real-time guidance systems that route evacuees to safety during a fire. Ideally, such a system should suggest paths that keep evacuees away from untenable conditions, where untenability may be due to high temperature, dangerous levels of smoke, or crushing crowd density. Since the causes of untenability are dynamic, so should the routing recommendations of such a system. Moreover, since untenable conditions may arise in any area of the building, not all fire exits can be assumed accessible, and therefore, it would be naive to route every individual to their nearest exit, which may not be necessarily tenable.

How can routing recommendations be generated in real-time while being tailored to each individual in the building? This is the research question that instigated the design of a theoretical framework for a real-time fire evacuation system. This theoretical exposition produced two main research contributions, which are described below.

Pre-Optimization Algorithms for Real-Time Fire Evacuation Guidance Systems in Buildings

Building plans can be modeled as networks, and thus, the problem of routing evacuees to safety in real time can be solved with a network optimization algorithm. Currently, network algorithms proposed for fire evacuation are either static (i.e., assuming zero arc travel time, which fails to detect crowd congestion and bottlenecks) or, at best, are dynamic, catering to travel times influenced by crowd density but failing to account for the current and near-future movement of fire and smoke. If run on a building network with no data about hazard location and propagation, a dynamic network algorithm could select from a solution space containing paths that are either currently untenable or will be untenable before occupants on it reach safety.

Therefore, we proposed a set of three pre-processing algorithms to ‘weed out’ dangerous paths from a building’s network model, marking such paths as unviable before they are included as part of the initial solution space of a graph optimization problem. Thus, the proposed set of algorithms is recommended to run on a building’s network model before applying any network optimization technique that routes occupants to safety.  

Manuscript Availability: Currently under peer-review

Data Availability: Not applicable – No new data was generated.

To face the catastrophic event of a building fire, fire engineers must work closely with architects to create a building plan that allows the safe evacuation of all occupants. Fire engineers perform many calculations and simulations to estimate the Required Safe Evacuation Time (RSET) from a zone based on its occupancy and the distribution of exits and subsequently validate that the RSET everywhere in the building remains less than the corresponding Available Safe Egress Time (ASET).

The RSET calculation can be performed with several models, the most popular of which is the Hydraulic Model as laid out in the SFPE Handbook of Fire Protection Engineering. The Hydraulic Model estimates the speed of crowds through various building elements and their consequent evacuation times. While this model caters to the reduction in crowd speed due to crowd density, it does not address the reduction in crowd speed due to two other significant factors: Smoke and the Crawling Response.

Smoke causes poor visibility, breathing difficulty, and possibly skin burns, thus causing further reduction in crowd speed for the same level of crowd density. Further, if the smoke becomes too dense at the evacuees’ walking height, it may force them to crawl under the layer of smoke to continue evacuating. Surely, the crowd dynamics would be altered when the movement mode changes from walking to crawling. Unfortunately, there is a dearth of research that correlates crowd speed to smoke density in both of these movement modes.

This work gathered and integrated empirical data points from several pioneering works that measured the speeds of individuals and crowds in different smoke densities. The findings consisted of two modified hydraulic models: One model caters to upright walking in smoke, and another caters to crawling on all fours under smoke. With three hydraulic models available (including the original SFPE model), a decision tree was also developed to aid in model selection under various environmental conditions.

Manuscript Availability: Publicly available here.

Data & Software Availability: Available upon request.