A Cyber-Physical Space Operational Approach for Crowd Evacuation Handling

Abstract

Crowded public venues are significantly under risks and uncertainties caused by fire and overcrowding hazards. For this purpose, Situational Awareness (SiA) -that is a mechanism to know what is going on around- can facilitate the automatic (or human involved) critical decision making and executing processes. Considering the dynamic and uncertain essence of crowd and hazard behavior in an emergency, executing the optimum evacuation plan is highly complex and needs strong models. In this paper, taking in input a model of the Cyber-Physical Space under SiA monitoring, we define an architectural-map-based Dynamic Bayesian Network (DBN) to describe and predict crowd and hazard behavior. Then, in order to minimize the total evacuation time, the authors present a quickest flow model for consecutive time intervals. Overall, the paper shows the importance of hazard quiddity, and crowd behavior on the evacuation efficiency in emergency situations. The approach is demonstrated through a small (but concrete) running example.

1 Introduction

Situational Awareness (SiA) can be defined as what is going on around and the ability of dynamic situation prediction. Literally, SiA deals with the perception of the elements of environment within a volume of time and space, the comprehension of their meaning, and the projection of their status in the near future (Endsley 1995). Moreover, Internet of Things (IoT) opens exquisite views on SiA. IoT is a “heterogeneous network of objects that communicate with each other and their owners over the Internet” (Gendreau 2015). With growing the IoT technologies, the SiA management and monitoring will be a critical issue, qua according to an estimation, “by 2020, a trillion IP addresses (objects) will be connected to the Internet” (Pretz 2014). IoT serves Machine-to-Machine connectivity to provide a degree of automation in many fields like crowd critical monitoring.

Indeed, an ideal SiA system is one that can put aside human factor from the loop, but there is still a huge gap to achieve this point.

Therefore, human plays a key role in “Cyber Situational Awareness” (CSiA) alongside of physical and virtual sensors. Mainly “Cyberspace” referred to the Internet as a type of dimension in the space, however, in IoT it extended from Internet to the physical spaces between the objects and their owners.

The role of CSiA becomes more highlighted in critical conditions like earthquakes, fires or floods where the rapid situation understanding is essential for an optimal decision making and agile executing by the emergency bodies. The problems are more critical in the case of overcrowding in a closed area where people are severely occluded.

Recently, the scientists are trying to deal with crowd monitoring problems vastly, considering both related social and technical aspects. From social point of view, the models study crowd behavior anthropologically and based on psychology and sociology sciences. The technical view, instead, investigates on event detection and especial aspects deriving from computer vision based algorithms.

In this paper, on the one hand, the authors define an architectural-map-based Dynamic Bayesian Network (DBN) to describe and predict crowd and hazard behavior. On the other hand, for minimizing the total evacuation time, the authors present a quickest flow model. Overall, the paper shows the importance of hazard quiddity and crowd behavior on the evacuation efficiency in emergency situations.

Based on our objective, this paper is organized as follow. Section 2 mentions some related works. Section 3 focuses on backgrounds and deals with issues, controversies, and problems. In this section, we briefly recall the theoretical foundations of SiA, CSiA, processing loops, BN, DBN, CAPS, social-behavioral modeling and their cost functions. Then we discuss social behavior modeling for evacuation in Sect. 4. Section 5 explains the definition of quickest flow and its application to the problem. A case study is presented in Sect. 6, to help better understanding the solving method. Section 7 targeted on presenting conclusions and future work.

2 Related Works

Following a literature review, we studied some researches concerning the application of Situational Awareness in crowd monitoring and decision making. In this regard, Tadda et al. (2010) provided a chapter as an “overview of Cyber SiA”; the chapter defines the basics of SiA, the models and some processes to performance measuring of a SiA system. Gendreau (2015) investigated on SiA measurement enhanced for efficient monitoring in the Internet of Things. Naderpour et al. (2013) used the fuzzy Dynamic Bayesian Network-based SiA to support the operators in decision making process in hazardous situations. Radianti et al. (2015) have proposed a spatio-temporal probabilistic model of hazard and crowd dynamics in disasters (based on DBN), with the intent of supporting real-time evacuation planning by means of situation tracking and forecasting. Tashakori et al. (2015) have introduced an indoor/outdoor 3D spatial city model for indoor incidents, using SiA concepts. Muccini et al. (2017) introduced CAPS modeling that is an architecture-driven modeling framework for the development of Situational Aware Cyber-Physical Systems. He et al. (2015) discussed K-shortest-path-based evacuation routing with police resource allocation in city transportation networks that can be somehow related to our topic.

Taking advantage from all above mentioned literatures, this paper introduces a combination of DBN and Quickest flow models for emergency evacuation problems, taking into account a risk index that refers to each area’s crowd density. Thus, we involved the real time crowd dynamic behavior in our model to choose the optimum evacuation path in each time slice.

3 Background

3.1 Situational Awareness (SiA) and Cyber-Situational Awareness (CSiA)

SiA is a type of context aware behavior that refers to “knowing what is going on” within an environment (Endsley 2000). SiA involves direct and indirect information acquiring about the environment, about who is doing what and where, and then interpreting this information for a particular goal. The formal definition of SiA breaks down into three separate levels: (1) perception (recognition) of the elements in the environment, (2) comprehension of the current situation, (3) projection of future status (Endsley et al. 1995). Perception level involves the sensory detection of the system and its environment. Comprehension phase includes data perceiving and situation understanding to achieve the specified goal. Projection means deducing information to see its future effect on the operative environment.

Considering CSiA as a subset of SiA, it can be defined as a section of SiA that deals with Cyber-Physical systems (CPSs). CPSs are a kind of system of system (SoS) that define as a network of individual systems coordinating each other to benefit from the joined operation as a whole. CPSs create the situational information, with formalizing sensors values to situation parameters. Therefore, such situation parameters “can be fed to a data fusion process or be interpreted directly by the decision maker” (Franke et al. 2014). Despite CSiA concept is using in various fields like Industrial Control Systems, Military, and Information Fusion, we call it notably for its “emergency management” application.

3.2 Processing Loops

To monitor large areas, a relatively large number of sensors are needed. In such a cases, due to so-called large number of sensors, a quality loss of produced data could be occurred, which makes the monitoring failed or inefficient. To solve the above-mentioned problem, processing loops are introduced. Processing loops are some feedback models that guide operators on the decision making process. A processing loop is a module that can receive sensors’ data, process them, and find the dangerous or odd events under interaction with environment and human operator. Among different processing loops, OODA (observe, orient, decide, act), MAPE-K (monitoring, analysis, plan, executing, knowledge), and cognitive cycle (sensing, analysis, decision, action) are more often used in the related literature.

As it stands, despite there exist some differences between the processing loops, their applications are somehow the same. We take advantage from the concept of feedback loops to have a structured view on our monitoring and decision making steps.

3.3 CAPS

CAPS (an architecture-driven modeling framework for Situational Aware Cyber-Physical Systems) is a modeling languages used to describe (1) software architecture, (2) hardware configuration, and (3) physical space views for a situational aware CPS (SiA-CPS) proposed with one of the authors in previous work (Muccini et al. 2017). The framework is aimed at supporting the architecture description, reasoning, and design decision process.

According to the objective of this paper, we take advantage from the Physical Space View Modeling Language [SPML] CAPS viewpoint for our case. SPML describes the physical space involved in situation awareness. The SPML modeling language defines an area with its coordinates, as well as rooms with associated walls, ceiling, and floor.

The SPML language is about the site in the real world where the SiA-CPS equipment will be deployed. The central class in the SPML is the CyberPhysicalSpaces class. The CyberPhysicalSpace represents the overall environment in the 3D space in which the SiA-CPS nodes will be deployed. Any kind of SiA-CPS element (cyber element or physical element) can be placed in the environment. Each element is characterized by the name, the abscissa and the ordinate of the center of this element, dimensions (width, depth, height), elevation, fixed or movable, door or window, the angle, material type, and its attenuation coefficient of this material (Muccini et al. 2017). The attenuation coefficient is a decimal number ranging from zero to one.

In SPML an area identifies a portion of physical space in which element can be distributed. The shape of this area is given by its shell: a sequence of coordinates representing the perimeter of the area in the 2D space. A Wall is a class characterized by name of the material, attenuation coefficient, thickness, and the abscissa and the ordinate for the beginning and the end of this wall. To avoid unnecessary repetition of effort, we used existing extensible 3D modeling environments (and specifically, Sweet Home 3D) to represent the space model generated by CAPS. In other words, the model is realized using a customization of Sweet Home (Fig. 4) according to the SPML metamodel (Fig. 1). Sweet Home 3D supports the implementation of new plug-in files to develop new features.

Fig. 1.

SPML metamodel

3.4 Bayesian Network (BN) and Dynamic Bayesian Network (DBN)

A BN is a directed acyclic graphical model in which nodes correspond to random variables and arcs represent dependencies or causal relationships between these variables with conditional probabilities. The standard BN represents the static cause-effect relations among different objects in a situation. Thus, the BN is a compact graphical representation of the full joint probability distribution P(X) of discrete or continuous random variables X = {X₁, X₂, …, X_n}, included in the distribution network as:

$$ P(X) = \prod\limits_{i = 1}^{n} {P(X_{i} } where \left| {Par(X_{i} ))} \right.\,\,\,\,\,\,{\text{Par }}\left( {{\text{X}}_{\text{i}} } \right) \, = {\text{ the parent set of X}}_{\text{i}} \;{\text{for any i}} = 1, \ldots ,{\text{n}} $$

(1)

DBN is a BN by adding the temporal behavior to some system’s variables. The dependency between random variables in a specific moment, capture their dynamic behavior. The random variables of BN (nodes) that in presence of time become temporal nodes, are assumed to have the first order Markov dependency on their values at the previous moment and each temporal node has an additional parent (a copy of the same node from the previous time slice) (Tolstikov et al. 2007). Thus, here ${\text{X}}_{\text{t}}^{\text{i}}$ is i^th node at time frame t and random variables par(${\text{X}}_{\text{t}}^{\text{i}}$) are its parents, which can include variables from a preceding time step, repetitive.

$$ P(X_{t} \left| {X_{t - 1} ) = \prod\limits_{i = 1}^{n} {P(X_{t}^{i} \left| {Par(X_{t}^{i} ))} \right.} } \right. $$

(2)

The joint probability distribution for a sequence of length T is therefore given by unrolling the formula 2:

$$ P(X_{1:T} ) = \prod\limits_{t = 1}^{T} {\prod\limits_{i = 1}^{n} {P(X_{t}^{i} \left| {Par(X_{t}^{i} ))} \right.} } $$

(3)

3.5 DBN-Based Hazard and Crowd Behavior Model

DBN can explain the dynamic behavior of a hazard. Let us consider occurring a hazard in a closed area with some rooms linked together (like a museum), assume that we realize a growing fire or overcrowded situation in time t = 1 in room 1. The hazard can spread time by time to neighbor locations with different possible behaviors (Radianti et al. 2015). In overcrowding hazard, we can consider each location’s crowdedness as empty, some, full, or overcrowded. Although an empty location or a place in which located some people, can host more people from neighbor locations, a full location should be unloaded in order to accept more people. Whilst the overcrowded location considers as presence of a hazard that crowd evacuation should be perform to lead the flow to other places as fast as possible. The following figure is an example to illustrates the links between location situation and crowd behavior for two neighbor rooms.

In both situations of overcrowding and other hazards (like fire and terrorist attacks), we can study the crowd flow with DBN. The model assesses the crowd direction who are leaving a hazardous area. Figure 2, models the crowd flow between two rooms in an indoor venue according to DBN. If the hazard happens in room 1 (or near to room 1), people will move from room 1 to room 2 that supposedly is the optimum next interval destination, and decreasing the number of persons located in area 1 impact crowdedness of both rooms. Here, 1 is a parent for in-1 and out-1 and people can move to 2 or stay in the same place.

Fig. 2.

DBN behavioral model

Fig. 3.

2D map of UFFIZI second floor

Therefore, our following quickest flow model specifies what destination is selected for next interval and DBN calculates the remained crowd in location X based on its parents “in X” and “out X”. In other words, the situation of each location depends on the neighbor locations that are directly linked to that. The structure of graff highly depends on the number of neighbors and parental situation.

In the same way, the hazard status (like fire) can be modeled with DBN. The hazard in time step t which can spread to neighbors considering the time delay. For the above example, in the next time step, room1 hazard can spread to room 2 or can have another state in the same room. Thus, the hazard1 can be a parent for hazard2 or hazard1 itself.

4 Social Behavior Modeling in Evacuation

In the special situation that a space gets increasingly crowded and evacuation is needed, flow of people cannot be smooth and they cannot follow a straight path. In this situation, some variables such as crowd confusion and velocity are important.

4.1 Confusion

In a Crowded area, confusion due to stress, anxiety, low visibility, and etc. can negatively impact the evacuation process (Radianti et al. 2015). When a person is confused, he is not able to take the optimal decision in the critical moment. Confusion depends on the number of human operators in evacuation procedure. It means that, in the presence of operators, the possibility of optimum path selection would be high and the confusion possibility would be trivial. The reason is that, the operators will have the optimum evacuation path provided by the DBN and quickest flow models. However, in our case, the confusion considered as a variable of Risk Index that is the number of persons located in each area divided by the capacity of that area, which highly impact on the crowd walking speed. In other words, a high density makes people more confused and slow.

4.2 Velocity

In the walking speed issue, the age of each person can determines his default walking speed. For example, the average walking speed of pedestrians age 65 or above is 0.889 to 1.083 m/s, while that of pedestrians aged below 65 is 1.042 to 1.508 m/s (Feng et al. (2016); TranSafety Inc. (1997)). However, the pedestrians’ walking speed is highly depending on crowdedness rate, which is specified by Risk Index.

5 Optimal Crowd Evacuation Using Quickest Flow Model

The model performs the crowd evacuation optimization in emergency cases, with minimization of the total evacuation time. The idea has its roots in vehicle routing optimization in transportation problems, however it fixed with the human factors and crowded areas characteristics in a conceptual application. The indoor area that will be used as case study, consists of a set of rooms linked by a set of paths, and a number of entrances (as sources) and a number of emergency exits (as destinations). We assume that in an emergency, crowd will be evacuated from source to destination through the network taking into account the rooms and paths capacity and the crowd arrival rate in each area.

Considering the above discussed social behavioral aspects, we assume that more crowdedness situation leads to more confusion, less velocity, and obstacle. The confusion is assumed to be dependent on the risk element calculated by the number of persons that are located in an area divided by the area’s capacity for different time intervals. In other words, we assume that the confusion has a positive linear relation to the obstacle on the path. Indeed, the more crowd in the path, the more individual confusion. The risk value will be considered as a cost for our quickest flow network calculations. We also assume that the operators are located in the paths intersections in a proper specific number, thus, their role is to lead crowd’s flow to the optimum path, without any additional cost.

To illustrate the implementation of the proposed approach in a real environment, the “Uffizi Gallery” is chosen as a running example. The museum is located in central Florence, Italy, and is one of the world’s best known and most visited museums with almost 2.1 M visitors per year. The museum is spread out over three floors and the visit starts from second floor because of its grand staircase. To implement our model, we consider the following section of the second floor 2D map that is consist of seven different areas. Due to a non-disclosure agreement, the position of the emergency doors is fictitious.

Our approach takes into account the following components:

• the OODA processing loop, as the reference control loop model;

• the CAPS modeling environment, to specify the area under monitoring;

• a risk index, to dynamically calculate the density of each area;

• the Dynamic Bayesian Network, to model the location network layout.

Based on those inputs, we then compute the quickest evacuation path. Section 6 provides a description of the steps above, whit their application to the running example.

6 Application of the Optimal Crowd Evacuation Approach to the Running Example

Considering our case as a situational aware IoT system, we apply our method to find the optimal evacuation path in a dynamic real time system. In other words, we mainly concentrate our investigations about situational aware IoT systems on indoor crowd management in emergency situations. This would provide us with some concrete real world experiences and a scenario to reason upon.

6.1 CSiA and Processing Loops

To monitor a large area such as the UFFIZI museum, a relatively large number of sensors are needed. In such a cases, due to so-called large number of sensors, a quality loss of produced data could be occurred, which makes the monitoring failed or inefficient. Software Engineering scientists tried to adopt novel processing loops (such as OODA loop, MAPE-K feedback loop, and cognitive cycle) to manage a process. Here we recall the OODA loop for UFFIZI case.

The OODA loop guide operators on the decision making process, and on using available information. This loop originally designed for military command and control system, anyhow it is compatible by other civil systems like our CSiA Model. The OODA process can be defined in four main steps: Observe (know what is happening), Orient (understand the meaning of what was observed), Decide (weighing the options available and picking one), and Act (carrying out the decision). The loop starts again from beginning, after a decision has been made and the related action has been taken.

Observe: the sensors (cameras and people counters) monitor the crowd situation and count the number of people in each area.

Orient: the data gathered refines in this phase to be ready for decision step. Information should be classified in consecutive time slices.

Decide: predefined rules for each area are set, for instance, the count of persons inside the room should be lower than the room capacity in normal situation, if not the overcrowding emergency situation is detected. In emergency case, the quickest flow should be chosen in accordance with the DBN risk element. If an emergency case is detected, a message will be send to the involved operators to execute evacuation, otherwise no action required by the system.

Act: The situation monitors by the human operators and in the emergency situation, they lead the crowd flow to the optimum path for evacuation.

6.2 Caps

Figure 4 shows the SPML model representing the physical environment of our UFFIZI scenario, the selected part of the second floor. It contains many kinds of obstacles that are concrete walls dividing the whole building into rooms and corridors, connector doors and an emergency door. The physical environment of our scenario contains many deployment areas. From the figure, we can see a number of SiA-CPS elements deployed in the environment (they are hypothetical because of an agreement). Here we used existing extensible 3D modeling environments (Sweet Home 3D) to represent the space model generated by CAPS. Sweet Home 3D supports the implementation of new plug-in files to develop new features (SWEETHOME-SWEET 2015).

Fig. 4.

3D map of selected area

Fig. 5.

Risk index

6.3 Risk Index

A simulation performed for 7 selected areas that are monitored by the virtual sensors (counters) in accordance with the DBN model. The model (Chiappino et al. 2013) analyzes the risk level of each selected area by introducing a performance indicator that monitors each room’s crowd based on its maximum capacity.

$$ R_{i} = \frac{{N_{i} }}{{N_{i}^{max} }} $$

(5)

Where R_i is the risk index, N_i is the number of people located in an area in a specific time interval, and ${\text{N}}_{\text{i}}^{\hbox{max} }$ is the maximum capacity of the related area. This index can show the crowd flows in a dynamic mode and let the decision makers to take best decision in overcrowding situations. As the index is a variable of confusion and velocity, it will be used in the following quickest flow model as a cost function to choose the optimum evacuation path at each time slice. The temporal window between each surveillance considered 20 s and the number of intervals are 4.

6.4 DBN

According to above mentioned Risk Index and DBN definitions, the structure layout is shown in Fig. 6. Nodes represent the different locations, node E represents the exit door, and arcs show the paths the people should be evacuated through. For example, a person located in the area 14, may pass to the area 13 or 2 (according to above 2D and 3D maps), or can stay in the same room in timespan between t-1 to t. In case of overcrowding (or any other emergency case), the system shows to the operators the most efficient path for leading people toward emergency exit by considering the quickest flow, behavioral aspects (like confusion), and structural constraints (e.g., size of rooms and doors).

Fig. 6.

Location network layout

6.5 Quickest Flow

In this section, a model is created to calculate the optimum path for dynamic evacuation in four selected consecutive time intervals. The weight assigned to each path is equal to the risk index for that location. Higher the risk index is, more the density, more the confusion, less the velocity, and more the possibility of obstacles.

The risk index, considered as a cost function for each node, is shown in Fig. 5. Based on it, the quickest flow for each time interval can be calculated according to the assigned weights (risk indexes) shown in Table 1.

Table 1. Risk indexes.

The table shows the density of each place in each monitored time slice. The crowd is entering from the entrance and passing by room number 14 and so on. We suppose an emergency situation happens and crowd should be evacuated from the quickest path. According to Fig. 3, the emergency exit is located on the room 10, thus, all people should pass by that room to be evacuated. Therefore, the density of the room 10 becomes higher than other areas.

The model applies a real time optimum path selection that leads crowd to the low density neighbor location. According to our primary assumptions, human operators are located on the intersections in a proper specific number to lead crowd to the optimum path. Practically, the decision making system decides which neighbor node has lower risk index, calculates the quickest flow, and shows the corresponding operator what area people should go through. Accordingly, in the next timespans, the system calculates new risk indexes and shows the quickest emergency evacuation flows.

In the following example, we consider room 14 as the origin and room E (exit door that is located on room number 10) as the destination to perform a maneuver of emergency evacuation. The crowd enters room 14, consequently the other areas will be crowded and will have a non-zero risk index. Below we show graphically how the system displays the quickest evacuation path dynamically with assigning related risk index weights to each node:

T 0: 14(0.33) → 2 (0) → 9 (0) or 11(0) → 10 (0) → E

T 20: 14(0.5) → 2 (0.05) → 9 (0) or 11(0) → 10 (0) → E

T 40: 14(0.58) → 2 (0.08) → 9 (0.01) → 10 (0) → E

T 60: 14(0.83) → 2 (0.13) → 9 (0.17) → 10 (0.12) → E

T 80: 14(0.75) → 2 (0.2) → 11(0.5) → 10 (0.75) → E

7 Conclusions and Future Work

This paper tries to take in input some Cyber-Physical Space models under SiA monitoring, to define an architectural-map-based Dynamic Bayesian Network (DBN) and predict crowd and hazard behavior. Quickest flow model for consecutive time intervals to minimize the total evacuation time. As a conclusion, the importance of hazard quiddity, and crowd behavior on the evacuation efficiency in emergency situations realized to be strongly important.

As future work, we are developing a model for SiA-based outdoor crowd monitoring to calculate the waiting time for ticketing, security check and entering the museum, using Two-Stage Stochastic Integer Programming Approach. As a similar future work, we will use dynamic mathematical model on our case to have some performance evaluation on, for instance, the shortest and quickest path calculation time.

In our future work, we will have a deep comparison between the traditional emergency evacuation plans with our model, taking into account the traditional safety emergency evacuation plan provided for the researcher’s night of the university of L’Aquila.