We present a computational component that allows to evaluate the minimum time necessary to evacuate people from a place (e.g., a public building). The space and time dimension are discretized according to metrics and models in literature. The component formulates and solves a linearized, time-indexed flow problem [3] on a network that represents feasible movements of people monitored at a suitable frequency. This computational component is the core part of an IoT infrastructure aimed at monitoring crowds in public spaces for planning evacuation paths. The CPU time to solve the model is compliant with real-time use. An application of the algorithm to a real location with real data is described, and diverse uses of the methodology are presented.
Crowded public venues are significantly under risk, and casualties may be caused by hazards of various nature and possible consequent overcrowding. Evacuation plans are becoming more and more elaborated, and restrictive regulations are imposed by law both in normal exercise of public services and when organizing public events. A good evacuation plan takes into account different types of crises and emergencies (e.g., earthquake, fire, ...), different scenarios, and different risks. Safe and first aid zones are carefully identified, as well as evacuation paths to safe areas1.
While very elaborated, standard emergency plans may still suffer of limitations. First, they are mostly design-time and do not take real-time data into account. Consequently, an emergency plan may suggest people in an auditorium to move to the outside park when fire originated right in that area; or, it may suggest evacuation routes that are currently not walkable. Secondly, once paths from buildings to external safe areas are drawn, directions for their use are normally care of human operators — when available — and are based on a partial view on how emergency is constraining the building area. Third, while the release of an evacuation plan may take weeks and requires external reviewers for approval, only few people typically (and unfortunately) read them2.
To cope with the above issues, this paper uses a run-time network flow model that, based on both design
(e.g., building dimension and structure, room capacities, door capacities) and run-time information (e.g.,
current amount of people in the building, in specific rooms and corridors) easily acquired via IoT devices, may
support the quick evacuation of people in case of hazard. The model, developed in the late eighties [
In the present context, an optimal solution does not have — of course — a big prescriptive validity: in other words, optimal flows through the building might in general be difficult to implement in practice (in case of risk, people tend to move quite unpredictably). The interest of an optimal solution mainly lies in its numerical value, that is the minimum amount of time necessary, in ideal conditions, to let a given distribution of people out of the place. This number can be used to monitor safety conditions from time to time. In fact, the main plus with respect to standard evacuation plans, are:
i) Optimal solutions can continuously be updated thanks to the efficient mathematical structure of the problem, so evacuation guidelines can be adjusted according to visitors positions that evolve over time. ii) In this way, evacuation plans can be based on real-time information. Just to indicate one advantage, paths that become suddenly unfeasible can automatically be discarded by the system. iii) The model can be incorporated into a mobile app supporting emergency units to evacuate closed or open spaces. iv) Problem solutions for different time horizon provide a Pareto frontier that relates available time to the best possible people outflow in the given conditions. All that given, our overall view (backed up by ongoing work) is to integrate the mathematical model and algorithm here proposed with an IoT infrastructure and a mobile app.
The paper is organized as follows. Literature is briefly discussed in Section 2. Section 3 presents the flow model. Section 4 refers on how model parameters should be set up to deal with real cases. The application of the model to a real exhibition venue is presented in Section 5, while the IoT architecture including the flow model component is presented in Section 6. Conclusions are finally drawn in Section 7.
1The evacuation plan adopted during the Researchers Night event, hosted in the city of L’Aquila in 2016 (NdR2016) can be found at http://tiny.cc/ResearchersNight2016.
2The evacuation plan for the NdR2016 event was downloaded from website/mobile applications prepared for the event just 36 times against 5700 total visitors.
Evacuation routing problems (ERP) for large scale roads and buildings are complex and subject to various
modeling issues. In literature, the ERP is addressed by either static or dynamic algorithms. Indeed, a static
network cannot properly model time related constraints, and a dynamic view can then be obtained by a sort
of time expanded network that models flows over time. Choi et al [
Recent research bases evacuation planning on a transshipment problem. For instance, Schloter et al. [14] study two classical flow models in order to deal with crowd evacuation planning: one algorithm aims at finding the best transshipment as a convex combination of simple lex-max flows over time; a second one computes earliest arrival transshipments that maximize the flow towards the sink for every point in time.
Other papers propose a hybrid optimization-simulation approach. To quote an example, Abdelghany
et al. [
One of the most crucial issues addressed in the recent literature is the ability of finding good feasible
solutions in short time. In general, a trade-off is observed between complex models that accurately describe
the scenario, but cannot be solved quickly and thus call for heuristics (so loosing accuracy of solution
and situation assessment), and simpler models that can be solved quickly and exactly, but lack from the
viewpoint of scenario description. In this perspective, however, Choi et al.’s early paper [
The following network construction basically follows [
The flow model uses an acyclic digraph D with node set V × T and arc set
E = {(i, t) → (j, t + 1) : ij ∈ A, t ∈ T }
Referred to as τ -time or dynamic network in [
0 ≤ yit ≤ ni t ∈ T, i ∈ V (3)
Equation (1) is just a flow conservation law: it expresses the occupancy of cell j at time t as the number yt−1 of persons present at time t − 1, augmented of those that during interval (t − 1, t] move to j from another j cell i ∕= j, minus those that in the same interval leave cell j for another room i ∕= j. Box constraints (2), (3) reflect the limited hosting capability of the elements of G.
cij cij' cij" 0 cij – cij –jcij' ujt–1 n' cij' – cnij'j"––cn"j' vjt–1 ij cij" – njc–ij"nj" wjt–1 ujt–1 nj' vjt–1
wjt–1 nj" nj yjt–1 3.2 To model the relation between time and people outflow, one can try to maximize the number of persons evacuated from the building within τ :
max y0τ (4)
This is the Max Flow Problem (MFP) considered in [
t uit−1 ≤ n′i vit−1 ≤ n′i′ − n′i wit−1 ≤ ni − n′i Arc capacity constraints (2) are then replaced by (5) (6) (7) 0 ≤ 0 ≤ 0 ≤
t φij
t χij
t ψij ≤ ≤ ≤ cij − cij n−′v c′ij utj−1
c′ij − c′i′j vt−1 c′ij − n′j′ − n′j j
c′i′j wt−1 c′i′j − nj − n′j′ j Consistency of the φ, χ and ψ variables with the x flow variables requires χ = 0 (ψ = 0) if φ (if χ) does not saturate its capacity. This is ensured, at optimality, by the properties of basic solutions. After rephrasing (7): where aij = cij n−′j c′ij a′ij = cn′i′jj′ −− cn′i′j′j a′i′j = nj c−′i′j n′j′ and aij < a′ij < a′i′j , we observe the following fact (that can be generalized to any piecewise linear approximation of the congestion curve).
Proposition 1. Suppose that, in a feasible solution, u¯it < n′i and v¯it > 0. Let
δ = min{n′i − u¯it, v¯it} Then a solution with uit = u¯it + δ, vit = v¯it − δ and the other components unchanged is also feasible and no worse than the given one.
Proof. See [
It is worth mentioning that, the polyhedron in the new varables is not necessarily integral. For large flows, however, the linear relaxation provides a sufficiently good approximation to an optimal integer solution. 4
To get a reliable model, parameters must be set to numbers that reflect reality. Those numbers depend on several considerations, the most relevant being: model granularity, walking velocity in various conditions (on a flat, on staircases etc.), door (and staircase) entrance capacities, room (and staircase) capacities. 4.1
The issue of model granularity touches both spatial and temporal units, and affects the shape and size of the unit cells in which the building is decomposed, as well as the slots that form the evacuation time horizon.
As described in the previous sections we embed the building plan into a grid, whose cells are assumed isometric: that is, can be crossed in any direction in the same amount of time. That amount will define the time slot duration, and cells will be regarded as virtual unit rooms that communicate one another via physical or virtual (i.e., open space) doors, see Figure 1.
Grid geometry can vary. Ideal isometric cells are circles, but circles are not embeddable into a grid with adjacent cell sides. Hexagon cells are a good compromise between isometry and plan embedding. However, in our study case we found room sizes and shapes well compatible with a square grid where each room is split into an integer number of cells. 4.2
The cornerstone on which the length of each unit time slot in T — and consequently its reciprocal, the monitoring frequency — is established, is the free flow walking velocity, i.e. the speed at which humans prefer to walk in non-congested and non-hampered conditions. Clearly, its value varies for different categories of people (child, adult, elderly, disable etc.) and slope (flat, upstairs, downstairs). This parameter is important to perceive the distance that an individual can possibly walk during a specific period of time. Through its evaluation one can define the cells in which an area is to be divided for best approximation of traveling time. Table 1 reports different evaluations of pedestrian free flow velocity found in literature.
Stairs (m/s) up down 0.56 0.65 0.61 0.69
0.8 ± 0.19 0.59 0.76 0.81 ± 0.13 0.83 0.86
Reference
Fruin 1971 [
Fang et al. 2012 [
We assume the free flow walking speed for a flat surface equal to 1.25 m/s. Furthermore, in our study, the flow is rarely upward and almost all people are supposed to go to safe places located at the building ground floor: for this situation, we consider a downstream free flow speed of 0.76 m/s. 4.3
The capacity of a door depends on such various aspects as user composition, door type (always open, open
when used, turnstile), crowdedness and, last but not least, door width. A study by Daamen et al. [
Experiments conducted by Kretz et al. [
None of the aforementioned studies considers bidirectional flow through doors, and so do we in our optimization model: in fact, although bidirectional flows are in principle possible, they will never occur in an optimal solution even without considering flow rate reductions due to collisions.
We assume 1.2 p/m/s for every door, meaning that a maximum number of 6 persons can pass through a 1-meter width door per time slot (5 seconds). We also assume capacity proportional to door width.
Staircase capacity is treated differently. Fruin [
The pedestrian density is the number of persons per square meter monitored at any time. This information is crucial for crowd safety and evacuation performance, as movements are dramatically reduced in highly dense areas. As density increases, pedestrian movements become constrained and flow rate consequently decreases. According to UK fire safety regulations, the maximum allowed density corresponds to 0.3 square meters per standing person, a value that increases to 0.5 for public houses, to 1.0 for dining places, to 2.0 for sport areas and to 6 for office areas. In our case study — gallery indoor space — the maximum capacity of each cell is calculated by assuming 0.8 square meters per visitor, that is 1.25 persons per square meter. 5
Using the measures discussed in the previous section, we next describe an application of the model of Section 3.2 to the safe evacuation of Palazzo Camponeschi, a building in l’Aquila (Italy) normally used for exhibitions. Safety conditions of the building, which consists of 31 rooms including corridors, are supervised by L’Aquila Fire Brigade. Rooms sizes vary in a large range, and so the average time of a person to cross them from door to door is required. As explained in §3.1, we split each room in unit cells, each behaving as a (virtual) quasi-square room that can be traversed in a unit time slot. In practice, we embedded the building plan into a quasi-square grid as shown in Figure 3.
The embedding results in a graph with 109 nodes (Figure 4) corresponding to the cells of Figure 3 and including node 0 as safe place. Adjacent cells are linked by 259 arcs which allow people flow inside the building. All arcs are assumed bidirectional except the three towards the safe place. A time slot corresponds to the time required for crossing one cell: using average free flow speeds from §4.2 and considering cell size, we obtained time slots of 5 seconds each, and therefore the monitoring frequency. Door capacities vary according on size and features. As a rule of thumb, no more than 6 persons can pass through a 1-meter width door per monitoring frequency. Since downward free flow speed on stairs is lower than on a flat, staircase and related arc capacities are reduced to 5 persons/meter every 5 seconds.
We next report the simulation of an emergency occurring in two different conditions in terms of building occupancy (Scenarios 1 and 2) and route prescription. In both simulations, we computed the minimum time 30 60 90 120 150 180 210 240 270 300 330 360 390 417 442 467 492 511 524 528 0,29 sec 0,43 sec 0,21 sec 0,37 sec 0,28 sec 0,34 sec 0,32 sec 0,28 sec 0,31 sec 0,32 sec 0,43 sec 0,37 sec 0,56 sec 0,45 sec 0,46 sec 0,48 sec 0,48 sec 0,54 sec 0,65 sec 0,56 sec 101 100 103 104 105 106 107 required to N persons, randomly distributed in the building room, for reaching a safe place. The code for simulation was written on OPL language and solved on CPLEX version 12.8.0. We ran all the experiments on a Core i7 2.7GHz computer with 16Gb of RAM memory under Windows 10 pro 64-bits.
In the first simulation we suppose an initial occupancy of N = 528: this datum comes from an experiment performed in L’Aquila during the Researchers Night event on 29 September 2017, when the simultaneous presence of 528 people in Palazzo Camponeschi was recorded as peak value.
We solved problem (1)-(8) for τ = 1, 2, . . . until a solution of value N is found. Table 2 reports the number of evacuees (column 2) at each τ and the computation time of each resolution step (column 3). In terms of evacuation time, everyone has reached a safe place in 1 minute and 30”. As shown in the table, computations require 1.15 seconds (presolve included) in the worst case and are therefore totally compliant with real-time applications.
In a second scenario, we repeated the simulation doubling the number of people in the building. In this
time (seconds)
Scenario 2: 1,056 individuals case everyone can reach a safe place after 36 time slots, i.e., 3 minutes. Also in this case computation time is definitely short, being always under 3.39 seconds including presolve.
This first simulation depicts an ideal situation in which flows autonomously choose the best among all the available routes in the building. Of course, managing such an ideal evacuation is not easy and perhaps unpractical. As a general practice, in fact, evacuation is conducted through pre-determined routes. In a second simulation, then, we suppose that the prescribed evacuation routes are the shortest paths from any cell to the safe place. In this situation, evacuating 528 (1056) individuals takes of course more time: 1 minute and 40” (3 minutes and 20”).
By comparing this simulation to the previous one, we observe that people flows plainly for some time (1 minute and 5” in the first scenario, 2 minutes and 10” in the second). After that time, shortest routes start experiencing congestion, and evacuation is slowed down. The phenomenon is illustrated in the charts of Figure 5: as one can expect, the tail of people still in the building increases with initial occupancy. 6
The mathematical model and algorithm described in this paper are part of an IoT infrastructure for evacuation handling. The IoT infrastructure, whose architecture is sketched in Figure 6, is designed to collect the required run-time data. It is studied to be tolerant to faults (therefore to guarantee correct response also in emergency case), performant (in terms of computational time and resources), and to include both situational awareness sensors (such as disaster detectors, people counters, DVR cameras, and RFID technologies to count the number of people in closed spaces, to get information about their velocity, and direction) and actuators (e.g., to close or open windows or doors, to display evacuation information). The computational component adopted, that is the subject of the present paper, will thus become the central element that, while inputting situational awareness information, will provide evacuation recommendations.
This information is going to be displayed into a mobile app. The main goal of the application, to be run on a tablet, is to show a 2D-representation of the monitored space providing also contextual data on where the crowd is at any time, and how it moves in normal and emergency cases. In this line, we have recently implemented the visualization of the crowd heat-map on mobile devices. Given such a visualization, actuators might be piloted directly from the mobile app in order to direct people through the fastest evacuation path.
While we do not expect, neither wish to, remove humans from the decision process, our project wants to support their decisions by providing run-time information — that could be unavailable otherwise — by periodically re-calculating best evacuation paths or evaluating minimum evacuation time under conditions that can vary from time to time. Just to list a couple of possibilities, (a) new sources of emergencies can be shown at run-time, (b) unexpected human behaviors can be taken into account. 7
This work uses a run-time network flow model for supporting the rapid evacuation of people from a building in case of emergencies. The model takes as input both static information (such as building dimension and structure, room capacities, door capacities) and run-time information (such as number of people in the building, number of people in specific rooms and corridors) acquiring it through IoT devices.
The building topology is described by a graph. Run-time data are used to create a time-indexed acyclic digraph that models all the feasible transitions between adjacent rooms at any time. Minimizing the total evacuation time corresponds to solve max flow problems with non-linear capacities that model congestion. Preliminary evaluations have been conducted on a real case.
Future work includes to: i) enrich the model with further design-time and run-time information to make the evacuation plan more accurate; ii) empirically evaluate the model in extensive scenarios, and to compare estimated vs. real data (as, e.g., those generated during evacuation tests); iii) complete the realization of the IoT infrastructure and app mentioned in Section 6 using the computational component here developed. [10] Kratchman JA An investigation on the effects of firefighter counterflow and human behavior in a sixstorey building evacuation Thesis (2007) des