Multiagent Systems and Potential Fields to Smoke Dispersion Applied to Evacuation Simulations: The Case of Kiss Nightclub

ABSTRACT

We often visit places with a large concentration of people, such as malls, football stadiums, restaurants or nightclubs. In the media, there are often reports of emergency situations in these places. It is known that in a fire situation, one of the main causes of death is the inhalation of smoke. Therefore, it is essential that at the start of emergency situations, people leave quickly to avoid possible injuries. We have investigated the dispersion of smoke in closed places and simulated the crowd behavior in these situations. This paper aims to present a new proposal to model smoke dispersion in closed environments using the concept of potential fields joined with cellular automata. To validate the work, we have tested our behavioral model in a real scenario, the Kiss nightclub tragedy.

Introduction

In recent years, studies have been carried out to understand the behavior of smoke in closed places to help people escape from places where there is fire. In an emergency situation, fires can be classified as accidental or intentional, with the dispersion of smoke and fire varying according to the materials burned in the combustion process (Seito et al. 2008).

In a fire associated with the combustion phenomenon, four dangerous situations generally appear: heat, flames, insufficiency of oxygen and smoke. Of these four factors, smoke is the factor that causes the most physical harm to people (Seito et al. 2008). Considering a fire situation in an environment that does not have any type of alarm or signaling, when people smell smoke, they will instinctively seek the nearest exit. However, smoke will hinder vision, causing tearing, in addition to causing respiratory symptoms such as coughing and suffocation. Smoke can cause panic because it occupies a large volume of the environment, making it difficult for people to move in an evacuation (Seito et al. 2008). There is great importance in conducting studies of the behavior of smoke to prevent deaths caused by smoke inhalation during fires.

Building projects should include active and passive measures to facilitate the escape of people, but simulations of emergency situations minimize the chances of fatality. Therefore, the objective of this paper is to propose a model to simulate the dispersion of smoke in an environment using potential fields and cellular automata. Cellular automata represent evolutionary systems that form an initial random configuration; each component of the system evolves based on the current situation of its neighbors, and a set of rules that are the same for all components (Wolfram 1983).The potential field is an array or field of vectors that represent the space. The main idea of this method is to establish a potential field of attractive forces around the target point and a potential field of repulsive forces around obstacles. The sum of all forces determines the subsequent direction and velocity of the movement (Koren and Borenstein 1991), and a new potential field called the artificial potential field is established (Zhang, Chen, and Chen 2012).

In this work, a new application for potential fields is proposed that joins cellular automata to describe the dispersion of smoke in a closed environment. Our preliminary results were presented in (Correa, Bicho, and Adamatti 2018). We simulated an emergency situation causing crowd evacuation in which each person is modeled as an autonomous agent using multiagent simulation (Wooldridge 2009).

Crowd simulation is a complex system that seeks to represent the behavior and the movement of a crowd with visual graphic resources. There are many applications in this area; for example, in the enterprise industry, it is used to properly simulate the movement of a large number of virtual humans in movies or games (Cassol 2016), and to evaluate complex environments of difficult evacuations of a large concentration of people, such as the evacuation of a football stadium. We may also consider situations in which people or certain groups are in an emergency situation. In the crowd simulation, we find the concept of disindividualization that can be described as the situation in which individuals act in groups and are not seen as individuals, facilitating the antinormative behavior (Vilanova et al. 2017).

The challenge in the computer graphics area is to model individual human behavior in its most elementary form. One possibility is to develop this type of model considering simple characteristics for individuals. An example of this idea is the work of Reynolds (Reynolds 1987), which used particle simulation to show the behavior of flocks or shoals. The flock movement is the result of the actions of each bird, with each one acting according to its perception of the environment, generating a collective movement. In this way, Reynolds defines the boids, which are the virtual characters. Each boid has the ability to perceive the local environment, and maintain its position and orientation in the group through the three rules as shown in Table 1¹.

Table 1. Rules of Flocking Model.

Separation	Alignment	Cohesion
(Avoiding collisions) A boid must keep a minimum distance from its neighboring boids and obstacles in the environment, verifying the need to increase or decrease its speed.	(Maintain the speed) The boid must adjust its velocity vector (modulus and orientation), keeping a coherent trajectory to the Neighboring boids.	(Maintain the cluster) The boid should maintain its position near the centroid of the positions of the neighboring boids.

This paper is organized as follows. In the next section, the works related to the proposed method are presented. The details of the model are introduced in Section 3. The real application and its results are presented in Section 4. Finally, the final considerations are given.

Related Works

The potential field method has been commonly used in obstacle prevention because its modeling is simple. However, the method has substantial deficiencies. (Koren and Borenstein 1991) presented a rigorous mathematical analysis to identify the problems inherent in the potential fields method. As a result, the authors defined a differential equation that combines the robot and the environment in a unified system.

(Zheng et al. 2017) proposed a model to study the dynamics of the evacuation of pedestrians under the influence of fire and smoke dispersion. The direction of the smoke dispersion was from top to bottom, which left less room for pedestrian movement, and pedestrian movement behavior was divided into three stages: normal walking, curved walking and crawling. The influence of fire and smoke on the movement of pedestrians was modeled by the field of fire floor and the field of smoke floor.

(Hardt, de Oliveira, and Goedert 2004) proposed a computational model for real-time simulation of the large-scale flow of smoke or gas in large environments, depending on a given configuration of obstacles and a field of winds. A discrete approach was adopted for wind transport and diffusion mechanisms, allowing simple and efficient simulation.

The work of (Cassol 2016) discusses the use of crowd simulation as a tool to reproduce and computationally evaluate the process of evacuation of agglomerated environments. The CrowdSim tool was developed to reproduce the behavior of people during the process of evacuating environments. This tool can automatically generate several evacuation plans to be carried out in the same environment, and these plans are evaluated to identify the best escape routes.

The work of (Pax and Pavón 2017) proposed an architecture of agents for internal scenarios, looking for performance and flexibility in the individual behavior of the agents. It maintained the crowd effects and allowed the modeling of rich and heterogeneous behaviors for each agent.

The Model

The Potential Fields Model

Considering a simple case, we can assume an element (e.g., a robot or an agent) is a point that is influenced by the potential $2D$ field. If we assume a differentiable potential field function $U(q)$, we can find the related artificial force $F(q)$ acting at the position $q=(x,y)$ (Siegwart, Nourbakhsh, and Scaramuzza 2011). We have:

(1) $F(q)=-\mathrm{\nabla }U(q),\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{\nabla }U(q)=\left[\begin{array}{c}\frac{\mathrm{\partial }U}{\mathrm{\partial }x},\frac{\mathrm{\partial }U}{\mathrm{\partial }y}\end{array}\right]$(1)

denotes the gradient vector of $U$ in the $q$ position. The potential field that acts on the element is the sum of the attractive field with the repulsive field:

(2) $U(q)=U_{att}(q)+U_{rep}(q).$(2)

The attractive potential can be defined as a parabolic function:

(3) $U_{att}(q)=\frac{1}{2}{k}_{att}.{\rho }_{goal}^2(q),$(3)

where $k_{att}$ is a positive scale factor and ${\rho }_{goal}(q)$ indicates the Euclidean distance $∥q-q_{goal}∥$. Since this potential is differentiable, if:

(4) $F_{att}(q)=-\mathrm{\nabla }{U}_{att}(q)=-k_{att}.{\rho }_{goal}(q)\mathrm{\nabla }{\rho }_{goal}(q)=-katt.(q-q_{goal}).$(4)

The repulsive potential should be strong when the element is close to the obstacle, but it should not have an influence when the element is far from the obstacle. We can define this rationship as follows:

(5) $U_{rep}(q)=\left\{\begin{array}{cc}\frac{1}{2}{k}_{rep}{\left(\frac{1}{\rho (q)}-\frac{1}{{\rho }_0}\right)}^2& ,\mathrm{i}\mathrm{f}\rho (q)\le {\rho }_0\\ 0& ,\mathrm{i}\mathrm{f}\rho (q)\ge {\rho }_0\end{array}\right..$(5)

The $k_{rep}$ constant is a scaling factor, $\rho (q)$ is the distance of $q$ to the obstacle and ${\rho }_0$ is the distance of influence of the obstacle. The repulsive potential function $U_{rep}$ is positive or zero, and it tends to infinity when the element approaches the obstacle. If the boundary of the obstacle is convex and differentiable in parts, $\rho (q)$ is differentiable everywhere in the free configuration space. We can define a repulsive force as:

(6) $F_{rep}=-\mathrm{\nabla }{U}_{rep}(q),$(6)

(7) $F_{rep}=\left\{\begin{array}{cc}{k}_{rep}\left(\frac{1}{\rho (q)}-\frac{1}{{\rho }_0}\right)\frac{1}{{\rho }^2(q)}\frac{q-q_{obstacle}}{{\rho }_0},& \mathrm{i}\mathrm{f}\rho (q)\le {\rho }_0\\ 0,& \mathrm{i}\mathrm{f}\rho (q)\ge {\rho }_0\end{array}\right.$(7)

Thus, the resultant force is:

(8) $F(q)=F_{att}(q)+F_{rep}(q),$(8)

which acts on the element and it is influenced by attractive and repulsive forces, directing the element away from the obstacles toward to the target (Siegwart, Nourbakhsh, and Scaramuzza 2011).

The Potential Field Model Adapted for Smoke Dispersion

This work creates a model to simulate the dispersion of smoke in an environment using the concept of potential fields associated with cellular automata. From this model, we simulated an emergency situation causing an evacuation of people based on a multiagent system. The Figure 1 shows the diagram of the methodology, and the following subsections present their steps.

Figure 1. Proposed Methodology.

Potential fields are typically used for agent movement models. In this work, a new application for the concept is proposed that describes the dispersion of the smoke in a closed environment. For that, it was necessary to make some adjustments to the equations of the potential fields; then it could be used in this new application. In the original definition of potential fields, they are considered only a possible target for the agent to reach, and there can be more than one obstacle in the environment. In our application, the equations were modified so that it was possible to have a single obstacle (fire) with several possible targets (doors). With this, the obstacle generates a force of repulsion while each target generates its force of attraction. Considering the vector agent’s position is $\overleftarrow{q}=(q_x,q_y)$, the Vector target position is $\overleftarrow{a}=(a_x,a_y)$ and the vector obstacle position is $\overleftarrow{o}=(o_x,o_y)$, the artificial potential field for the dispersion of smoke is obtained through the following equations:

Attractive Potential

(9) $U_a(q)=\frac{1}{2}{k}_a\frac{1}{\parallel \overrightarrow{q}-\overrightarrow{a}{\parallel }^2}.$(9)

The $k_a$ constant is how much the field deforms near the target point.

Attraction Force

(10) ${\overrightarrow{F}}_a(q)=-\mathrm{\nabla }{U}_a(q)=-\left[\frac{\mathrm{\partial }{U}_a}{\mathrm{\partial }{q}_x}\hat{i}+\frac{\mathrm{\partial }{U}_a}{\mathrm{\partial }{q}_y}\hat{j}\right]=-\left[A_a\hat{i}+B_a\hat{j}\right].$(10)

Calculating $A_a$, we have:

(11) $A_a=\frac{1}{2}{k}_a\left[\frac{2a_x-2q_x}{{[(q_x-a_x{)}^2+{(q_y-a_y)}^2]}^2}\right].$(11)

Calculating $B_a$, we have:

(12) $B_a=\frac{1}{2}{k}_a\left[\frac{2a_y-2q_y}{{[(q_x-a_x{)}^2+{(q_y-a_y)}^2]}^2}\right].$(12)

Repulsive Potential

(13) $U_r(q)=\left\{\begin{array}{cc}{C}_r& ,\mathrm{i}\mathrm{f}d(q,o)\le inf\\ 0& ,\mathrm{i}\mathrm{f}d(q,o)\ge inf\end{array}\right.,$(13)

(14) $\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}{C}_r=\frac{1}{2}{k}_r{\left(\frac{1}{d(q,o)}-\frac{1}{inf}\right)}^2.$(14)

The $k_r$ constant is how much the field deforms near the obstacle point, $d(q,o)$ is the Euclidean distance of the agent to the obstacle, and $inf$ is the distance of influence of the obstacle. Calculating $C_r$, we have:

$C_r=\frac{1}{2}{k}_r\left[\frac{1}{{(o_x-q_x)}^2+{(o_y-q_y)}^2}\right.$

(15) $\left.-\frac{2}{inf\sqrt{{(o_x-q_x)}^2+{(o_y-q_y)}^2}}+\frac{1}{in{f}^2}\right].$(15)

Repulsion Force

(16) ${\overrightarrow{F}}_r(q)=-\mathrm{\nabla }{U}_r(q)=-\left[\frac{\mathrm{\partial }{U}_r}{\mathrm{\partial }{q}_x}\hat{i}+\frac{\mathrm{\partial }{U}_r}{\mathrm{\partial }{q}_y}\hat{j}\right].\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{e},$(16)

(17) ${\overrightarrow{F}}_r(q)=-\left[\frac{\mathrm{\partial }{C}_r}{\mathrm{\partial }{q}_x}\hat{i}+\frac{\mathrm{\partial }{C}_r}{\mathrm{\partial }{q}_y}\hat{j}\right]=-\left[D_r\hat{i}+E_r\hat{j}\right].$(17)

Calculating $D_r$, we have:

$D_r=\frac{1}{2}{k}_r\left[\frac{2o_x-2q_x}{{[(o_x-q_x{)}^2+{(o_y-q_y)}^2]}^2}+\frac{2}{inf}\right.$

(18) $\left.\left(\frac{1}{2[(o_x-q_x{)}^2+{(o_y-q_y)}^2{]}^{\frac{3}{2}}}-2q_x+2o_x\right)\right].$(18)

Calculating $E_r$, we have:

$E_r=\frac{1}{2}{k}_r\left[\frac{2o_y-2q_y}{{[(o_x-q_x{)}^2+{(o_y-q_y)}^2]}^2}+\frac{2}{inf}\right.$

(19) $\left.\left(\frac{1}{2[(o_x-q_x{)}^2+{(o_y-q_y)}^2{]}^{\frac{3}{2}}}-2q_y+2o_y\right)\right].$(19)

Resultant Force

(20) $\mathrm{F}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{y},F(q)=-\sum _{i=1}^n{\overrightarrow{F}}_{a_i}(q)+{\overrightarrow{F}}_r(q).$(20)

The model potential field is defined by its attracting points which are the exit doors, and a repulsive point, which is the origin of the fire. The smoke is generated at the point of repulsion, starting gradually and moving according to the vectors generated by the potential field. Table 2 shows the steps of the smoke dispersion, which is an approximation of Fick’s Second Law (Serra and Villani 2008), where Fick’s Laws are diffusion mass transport equations. The second Fick law associated with potential fields defines the rules used in the cellular automata necessary to define how smoke can spread through the building.

Table 2. Smoke Dispersion Rules.

1st step	2nd step	3rd step
Each tick generates the smoke at the starting point of the fire (black patch), which is defined by the user.	Smoke spreads $1/8$ of its intensity to its neighbors (Moore’s Neighborhood).	Smoke disperses half $(1/2)$ of its intensity to the patch that its potential field vector is pointing to.

Kiss Nightclub: The Application in a Real Scenario

The application in a real scenario uses the blue print of Kiss nightclub, as Figure 2 shows. It is important to remember about the capacity of the nightclub, that was the maximum capacity of 691 people and the exit door width had an appropriate width to this capacity, but this specific door were the same entry door. However, at the moment of the incident the nightclub was overcrowded, according to reports there were about 1200 people there (Silva et al. 2017).

Figure 2. Blue print of Kiss nightclub (Silva et al. 2017).

The work of Silva et al. (Silva et al. 2017) considered two different scenarios: (1) without the norms required by NBR 9.077 (ABNT: NBR 9077 – Saidas de emergencia em edificios 2001) (Braziliam Norms of safety), where there is a single door for the evacuation; and (2) with the norms required by NBR 9.077 (ABNT: NBR 9077 – Saidas de emergencia em edificios 2001), having two doors for the evacuation of people. These two scenarios were executed with two values of population, 691 and 1200 people, which represents respectively, the maximum permitted quantity of people in the boate and the real quantity of people who were in the boate when the tragedy happened. In the simulations of Silva et al. (Silva et al. 2017), there is not any type of interaction between agents, as communication or formation of bands (flocking). People moved randomly until the panic button is pressed, after its activation, the people go directly for the door, to evacuate the environment. Also, they were not modeled the smoke dispersion. In this way, to define whether a person died the simulation accounts agents that, when searching for the door, went to the areas defined as been bathrooms. The results of (Silva et al. 2017) are presented in Table 3.

Table 3. Simulation of population with 691 agents and 1200 agents according Silva et al. (Silva et al. 2017). (S: people who have left; M: people who died; %: percentage of people who left or died in relation to the total number of people); S(20017): data from (Silva et al. 2017).

	With Flocking		Without Flocking
	With Com.	Without Com.	With Com.	Without Com.	S(2017)
Population: 691 agents
	Doors Amount: 1
S	29.13%	17.74%	28.65%	17.34%	64.18%
M	70.87%	82.26%	71.35%	82.66%	35.82%
Ticks	129.40	131.90	129.60	132.30	821.70
	Doors Amount: 2
S	34.91%	23.53%	34.69%	24.04%	97.67%
M	65.09%	76.47%	65.31%	75.96%	2.33%
Ticks	125.70	131.60	125.80	131.80	784.3
Population: 1200 agents
	Doors Amount: 1
S	18.92%	10.35%	18.95%	10.80%	66.06%
M	81.08%	89.65%	81.05%	89.20%	33.94%
Ticks	129.50	133.10	129.70	133.10	1335.10
	Doors Amount: 2
S	24.25%	16.08%	24.22%	15.62%	100%
M	75.75%	83.92%	75.78%	84.38%	0%
Ticks	125.60	131.50	126.20	132.20	1215.30

To exemplify the proposal of this work, we have used the blue print of Silva et al. (Silva et al. 2017) model, to execute new simulations, where we consider the communication between people, flocking formation and smoke dispersion. Table 4 shows the four scenarios, having 1 to 4 doors. For every scenario, 10 simulations were performed to calculate average, standard and percentage deviation, as shown in Table 5.

Table 4. Scenarios with 1, 2, 3 and 4 doors (the doors are in yellow).

One Door	Two Doors
Three Doors	Four Doors

Table 5. Simulations of population with 691 agents and 1200 agents in our approach.

	With Flocking		Without Flocking
	With Com.	Without Com.	With Com.	Without Com.
Population: 691 agents
Doors Amount: 1
	%	%	%	%
S	29.13%	17.74%	28.65%	17.34%
M	70.87%	17.74%	71.35%	1.06%
Ticks	129.40	131.90	129.60	132.30
Doors Amount: 2
	%	%	%	%
S	34.91%	23.53%	34.69%	24.04%
M	65.09%	76.47%	65.31%	1.14%
Ticks	125.70	131.60	125.80	131.80
Doors Amount: 3
	%	%	%	%
S	41.42%	33.55%	42.37%	33.84%
M	58.58%	66.45%	57.63%	66.16%
Ticks	131.70	133.00	131.90	132.40
Doors Amount: 4
	%	%	%	%
S	53.76%	41.22%	53.39%	42.19%
M	46.24%	58.78%	46.61%	57.81%
Ticks	135.60	133.50	135.80	134.00
Population: 1200 agents
Doors Amount: 1
	%	%	%	%
S	18.92%	10.35%	18.95%	10.80%
M	81.08%	89.65%	81.05%	89.20%
Ticks	129.50	133.10	129.70	133.10
Doors Amount: 2
	%	%	%	%
S	24.25%	16.08%	24.22%	15.62%
M	75.75%	83.92%	75.78%	84.38%
Ticks	125.60	131.50	126.20	132.20
Doors Amount: 3
	%	%	%	%
S	31.14%	23.41%	30.23%	23.49%
M	68.86%	76.59%	69.77%	76.51%
Ticks	131.50	132.90	131.70	132.80
Doors Amount: 4
	%	%	%	%
S	40.17%	29.31%	39.56%	28.72%
M	59.83%	70.69%	60.44%	71.28%
Ticks	135.50	134.10	135.50	134.10

Table 5 represents the values of the simulations in our approach and it is possible to notice that the difference of the values is a reflection of the smoke presence (or not). Despite the high percentages of people living in the work of Silva et al. (Silva et al. 2017), if we analyze the amount of simulation time, the values in “ticks” are very high, what means that it is necessary a lot of time for people to get out of the environment. However, in a real emergency situation, the evacuation must be happen very fast, i.e., in a short time. In this way, when the environment has the smoke, the simulation becomes more realistic, in a visual way, and in simulated results.

Final Considerations and Further Works

This paper presented a new model to simulate the dispersion of smoke in closed environments using cellular automata associated with the concept of potential fields and modeling an emergency situation using multiagent-based simulation. The results of our experiments showed that using the potential field in the modeling of smoke dispersion generally represents a good approximation of what happens in reality. For example, when there are a single door and a single focus of fire that generates smoke, the smoke tends to move toward the door leading to the shape of a drop, which is more rounded in the focus of the fire and narrowing in the vicinity of the door.

Modeling the evacuation of people in an emergency situation considered the flocking rules because we noted a relationship between the way birds fly and the behavior of crowds; thus, people will identify the nearest door to exit and will form bands, even in an emergency situation. Our results in an emergency situation, between exiting in an organized way or communicating with other people about the emergency, people live longer when they communicate with each other about the emergency situation. In addition, people leave faster when they leave in a coordinated way (Correa, Bicho, and Adamatti 2018).

To analyze the performance of our model with values of a real emergency situation, we choose the kiss nightclub (Santa Maria, RS, Brazil), because almost 300 people died. In addition, we have simulated the “ideal” conditions based on the Brazilian laws. After the results analysis, despite the values obtained are different of those recorded in the real situation (dead people and saved people), it is important to run previous simulations in places with high concentrations of people, because the analysis of smoke and people behavior will help to identify possible problems or unexpected events and how to do an immediate evacuation of the place in an emergency situation. In our simulations, the values show a higher percentage of saved people when the standards defined by Brazilian laws are executed (ABNT: NBR 9077 – Saidas de emergencia em edificios 2001).

As further works, we intend apply the concepts of Roadmap and Path Planning. Using these concepts, people do not just look for the nearest path, but rather the safest path. Another study ensured the conservation of mass in the generation of smoke. With all these aspects, we have a model closer to real emergency situation.

Interest statement

Bruna A. Correa has received scholar fellowship from CAPES (Coordination for the Improvement of Higher Education Personnel). Diana F. Adamatti and Alessandro L. Bicho declare that they have no conflict of interest.

Notes

1. These three rules are implemented in the flocking model, available in the NetLogo library (https://ccl.northwestern.edu/netlogo/).