Multiagent Model of People Evacuation from Premises while Emergency Adv Syst Sci Appl 2019; 01; 98-115 Published online at http://ijassa.ipu.ru/index.php/ijassa/article/view/558 Multiagent Model of People Evacuation from Premises while Emergency Andrey Samartsev1, Vladimir Ivaschenko1, Alexander Rezchikov*1, Vadim Kushnikov1 , Leonid Filimonyuk1, Aleksey Bogomolov1 1) Institute of Precision Mechanics and Control of RAS, Saratov, Russia E-mail: iptmuran@san.ru Received May 17, 2018; Revised March 13, 2019; Published April 15, 2019 Abstract: The multi-agent model of emergency evacuation process in case of limited space conditions is offered. A distinctive feature of the proposed model is the systematic consideration of physical interactions between agents and their reasonable behavior in conditions of evacuation from premises of a complex configuration. The model allows to investigate the state and behavior of people in emergency and determine the time of their evacuation. The proposed model can be used as a basis for determining ways and developing plans for evacuation from premises in emergency situations. Keywords: multiagent model, intelligent agent, evacuation of people, premises, emergencies. 1. INTRODUCTION Currently, the problem of combating emergencies is becoming especially urgent. The statistics for 2016 presented by the Ministry of Emergency Situations of Russia [37] indicate significant human and material losses caused by emergencies. Emergency evacuation of people from the premises as well as pre-emptive solutions [10, 26, 29-32, 40-45] are the most effective ways to reduce damage in case of accidents, catastrophes, fires and terrorist acts. In many situations, evacuation occurs spontaneously. This, among other things, is largely due to the inadequate development of existing organizational, technical and software tools for managing the evacuation process, the need to develop adequate models and algorithms to support decision making to ensure the effective evacuation of people in emergencies. In cases of spontaneous people evacuation from the premises, each person independently chooses a route and, on the way, makes decisions that they consider beneficial for achieving their goals. At the same time people decision making is influenced by the state and behavior of other people, the environment (walls and other obstacles), as well as such factors as panic [7, 8, 25], the failure of warning systems, unfamiliarity with the evacuation plan, the instinct of self-preservation, etc. Therefore, the research of spontaneous evacuation is significant. In addition, the investigation of spontaneous evacuation makes it possible to take into account the behavior of people and identify bottlenecks, such as the maximum intensity of the flow of people through the exits from the premises, the places of their maximum accumulation, the capacity of the premises, etc., to organize the optimal control of the evacuation process [33, 34]. *Corresponding author: rezchikov1939@mail.ru mailto:iptmuran@san.ru MULTIAGENT MODEL OF PEOPLE EVACUATION FROM PREMISES WHILE EMERGENCY 99 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) Thus, it is very important to ensure quick and unhindered evacuation in case of emergency. The quality of the evacuation process is usually checked by computer simulation, since the natural experiment in this situation can be dangerous and difficult to reproduce. In connection with the above, it is not surprising that the dynamics of the behavior of large masses of people, in particular during evacuation, has long been actively studied. The model of social forces, proposed by Helbing and Molnar in 1995, is widely used. Its modifications have been actively proposed and are being investigated so far [2, 14-17, 24, 48]. In the classical interpretation of this model, people in the crowd are acted upon by forces on the one hand that attract them to the goal, and on the other hand forces that keep them away from each other and from obstacles at a certain distance. In addition, people can be affected by randomly changing force, designed to take into account the deliberate deviation of pedestrians from a given route. In general, the model is considered quite successful, although it is criticized for the fact that the underlying assumptions simplify the behavior of pedestrians. Pedestrians in the model tend to adjust the speed of motion in inverse proportion to the distance from obstacles and other pedestrians. In fact, pedestrians can use better escape strategies, for example, "squeeze" between two other pedestrians to find a calmer route. In addition, the model is rather complicated in terms of the computation speed [47]. There are also fluid dynamic models [13, 27, 35, 47, 49]. They are quite accurate when modeling human flows of high (but not extremely high) density in the absence of panic. Disadvantages of these models are that they give little information about the behavior of specific people, and only simulate the situation in general. Models of this class are often difficult to understand intuitively, in addition, in practice, there are serious differences between the patterns of fluid movement and the panicking crowd. At the moment, the most promising are the agent models [3, 4, 7-9 12, 21, 23, 25, 35, 36, 39, 47, 49], in which the system is defined as a set of agents interacting according to certain rules. Such models a priori determine the states of agents, their characteristics, as well as the rules of their interaction and behavior in various situations. Agent behavior is understood as a function (or algorithm) that links the information that an agent receives about its local environment and the actions that it takes. Interaction of agents in the process of evacuation can consist in avoiding collisions with each other or walls, in physical contact, in the spread of panic sentiments. Note that the process of spontaneous evacuation is a vivid example of a decentralized system, when management is not carried out from the outside, and each person acts in accordance with their personal interests, and the global behavior of the system arises as a result of the many evacuees actions. In this case, the global behavior of the system may differ from the behavior of the elements of the system (this phenomenon is called emergence). For example, if each evacuation participant begins to hurry, the overall evacuation rate may be reduced due to a crush at the exit (the effect "faster is slower"). Agent models make it possible to take into account the emergence effect to the full [47]. Among the agent models that are suitable for describing the evacuation process, there are continuous and discrete ones. Discrete models are based on the apparatus of cellular automata [1, 18-20, 35, 38, 47, 49]. Such models are conceptually simple and computationally effective. However, in most cases, discrete models are an oversimplification of reality: pedestrians move discretely from their cells to their neighboring cells, the trajectories of their movement are angular and resemble the movements of a chess rook, collisions with each other and with walls are described rather roughly. Nevertheless, by using such models, it is possible to explain some aspects of crowd behavior, for example, crushes at the exits and the effect "faster is slower". The most natural and convincing realization of the agent approach are continuous agent models. In such models, the characteristics of agents can take any value on some continuous segment. This approach requires more computational resources than discrete, but it allows to 100 A. SAMARTSEV, V. IVASCHENKO, A.REZCHIKOV, V.KUSHNIKOV et al. Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) achieve better modeling accuracy. Continuous agent models are presented in [4, 6, 21, 22, 40, 46]. The model presented in this article belongs to that class either. The existing works of these classes are not without some drawbacks. Some models are too complex in terms of the quantity of parameters [4] or the computational speed, for instance [2, 14-17, 21, 24]. Many works do not consider evacuation from premises of complex shape [4, 14-17, 20, 21, 24, 38]. Some models do not take into account the physical interaction of agents, their inertia [4, 21]. Many models do not take into account the reasonableness of evacuated people, in particular the possibility of overtaking one agent by another [14-17]. A lot of models do not take into account the specifics of the evacuation process, but only model the behavior of "walking people" [21-24]. Commercial models often do not reveal many details of the crowd behavior modeling process they use. The purpose of this article is to describe a model without all problems mentioned in previous paragraph, to develop software package based on the model and to simulate the evacuation process with use of the software package. The aim of simulation is to validate model by comparing model simulation results with ones of other models and statistic data, visually observing agents behavior and estimating of “reasonability” of their actions. 2. PROBLEM FORMULATION Without loss of generality let us consider the premises, the floor plan of which is shown in Fig. 1. 1 - people, 2 - walls, 3 – exit zones Fig. 1. Premises map and people’s distribution inside it. In the xOy plane parallel to the floor of the premises, the following components are specified: 1. A finite set of walls, each of which is specified by parameters: (xW, yW) – coordinates of the lower-left corner of the wall, xW W and yW W – its width and length. We assume that the walls are perpendicular to the coordinate axes Ox и Oy, since this is the case in majority of the floor plans. 2. A finite set of exits from the premises specified by the parameters: (xE, yE) – coordinates of the lower left corner of the exit; xW E and yW E – its width and length, respectively. After a person got into one of the exit zones, it can be assumed that they MULTIAGENT MODEL OF PEOPLE EVACUATION FROM PREMISES WHILE EMERGENCY 101 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) successfully evacuated. Note here that the exit zone should not be directly in the doorway, but at some distance from it, since after the person leaves the room, they still influences on the evacuation process [5]. 3. A finite set of evacuated people, which we will consider as a set of their circle projections onto the plane xOy. We consider the centers of these circles as coordinates of people. 4. A finite set of evacuation zones, each of which is specified by the parameters: (xZ, yZ) – coordinates of the lower left corner of the evacuation zone, xW Z и yW Z – its width and length. At the very beginning of the evacuation people are concentrated within such zones. The presence of evacuation zones allows to take into account the possible absence of people in some rooms and in the space outside the premises at the first moment of time. Parameters of people: – radius vector (coordinates) of the center of the circle around the projection of the person on the plane xOy – x(t); – radius of projection – r; – mass of a person – m; – vectors of its velocity – v(t) and acceleration – a(t); – the maximum possible speed – vmax and acceleration – amax. The speed and acceleration of the person at the beginning of the evacuation are assumed to be equal to zero. It is necessary to perform a simulation of the process of spontaneous people evacuation from the premises and to develop activities aimed at managing and speeding up this process. The activities include the possible creation, movement and expansion of certain building openings, adjustment of evacuation plans, and personnel instructions. These events must help to speed up people's movement along evacuation routes and avoid crushing. 3. MULTI-AGENT MODEL 3.1. Model construction In the proposed model, as in [2, 14-17, 22, 24], the law of agents’ motion is determined by the relations: .)()()( ;)()()( ttattt tttxttx     (1) where Δt is model time step. The agents’ velocities change after collisions. The description of their physical interaction with each other and obstacles can be presented in various ways. It is permissible to regard collisions of agents as partially elastic [28]. During partially elastic collision some of the kinetic energy passes into thermal or other forms of energy. To describe the partially elastic collision, a recovery coefficient 0 ≤ ε ≤ 1 is introduced, which determines the nature of the interaction of the colliding bodies. For ε = 1 the collision is absolutely elastic, if ε = 0 it is absolutely inelastic, and for 0 < ε < 1 it is partially elastic. The normal components of the velocity to the shared tangent plane to the surfaces of the colliding bodies at the point of their contact (the collision plane) after impact at a partially elastic collision are calculated by the formulas: .)1( ;)1( 21 2211 22 21 2211 11 mm vmvm vu mm vmvm vu nn nn nn nn         (2) Here v1n и v2n are the normal projections of the agent velocities to the collision plane before impact, u1n and u2n are the normal projections of the agent velocities to the collision 102 A. SAMARTSEV, V. IVASCHENKO, A.REZCHIKOV, V.KUSHNIKOV et al. Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) plane after impact, m1 and m2 are the masses of the colliding agents. Tangential projections of the agent velocities to the collision plane after impact do not change [28]. When the agent collides with a wall, the projection of its velocity of motion parallel to the wall does not change, while the other projection reverses its sign and decreases its value according to the coefficient ε. For example, when an agent collides with a wall parallel to the Ox axis, its speed is recalculated according to the relations ,; yyxx uu   where v = (vx, vy), u = (ux, uy) is the agent's velocity before the collision with the wall and after, respectively. Let the direction of the acceleration vector a(t) of each agent, provided that each of them tends to get to the nearest exit from the room as fast as possible. To do this, we introduce the concept of the optimal vector (from the agent's point of view) of the velocity vopt(t), which approximates the agent to the chosen exit and allows, if possible, not to interfere with obstacles - other agents and walls. The actual velocity of the agent v(t) may differ from the optimal one due to its collisions with other agents and walls. Then we can assume that the agent moves with the acceleration a(t), whose modulus is determined from the physiological capabilities of the person (|a(t)| = amax), and the direction coincides with vopt(t) – v(t). If vopt(t) = v(t), then the agent moves without acceleration. Fig. 2 shows a graphical interpretation of the relationship between agent parameters. Here we should pay attention to the fact that the vectors a и vopt – v are collinear. Fig. 2. Graphical interpretation of connection between agent parameters The optimal speed module vopt(t) is bounded from above by the physiological capabilities of the agent vmax. If there are no obstacles ahead of the agent along the route, for example other agents or walls, then usually |vopt(t)| = vmax. To avoid collision with other agents along the route, the vopt(t) module may decrease. Let us consider the approach to the choice of the vector vopt(t) in more detail. Let e be a vector specifying the direction to the nearest exit, taking into account the layout of the room. The choice of vector e is determined solely by the location of the agent, walls and exit zones, but not by the location of other agents. Thus, it is possible to determine the vector field e for a given premises map. In this case, the calculations of this field during the simulation are carried out only once, which is an advantage from the point of view of the computational speed. The field of the vector e for the premises map under study is shown in Fig. 4. Let lα – be the distance from the center of the agent to the nearest obstacle (human or wall) in the direction at an angle α to the vector e, L is the specified critical distance, and r is the radius of the person projection on the xOy plane. MULTIAGENT MODEL OF PEOPLE EVACUATION FROM PREMISES WHILE EMERGENCY 103 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) Then the modulus of the agent optimal velocity vector vαopt(α) in the direction at an angle α to the vector e can be calculated from the expressions: .,0)( ;,/)()( ;,)( rl rLlrLrl rLl opt maxopt maxopt          (3) People have different physiological capabilities, therefore it is necessary that each agent has individual values of vmax and аmax. Let function        2 ; 2 -);cos()()(   optf (4) Then the angle γ between the vectors vopt and e is defined as the angle at which the value of the function f(α) maximal. That is, the direction of the vector vopt of the agent's movement is chosen according to the criterion        2 ; 2 -and ifmax)(  f (5) The value of the vector vopt is determined by substituting α = γ into expression (3): |vopt |=vαopt(γ) (6) The presented way of choosing the value of vopt allows the agent to maneuver between other agents, trying firstly to avoid collision with them as much as possible, and secondly, to approach the nearest exit as quickly as possible. Here we are assuming a good familiarity with the floor plan of the premises. Thus, the choice of the optimal speed vector vopt takes into account both the layout of the room and the location of other agents around it. The vopt vector must be recalculated for each agent at each step of the model time. Note that in the described model there are also attributes used in known models [4, etc.], such as: the angle and range of the agent's view of the surrounding space, the moment of inertia and the angle of rotation of the agent's head: 1. The direction that approximates the agent to the exit (taking into account the presence of walls in the room) is determined by the field of the vector e. The viewing angle of the agent can be considered equal to π, since in expression (5)        2 ; 2 -   , i.e. the agent analyzes all possible alternatives for movement in the plane in front of him. 2. Since the agent calculates the optimal speed values based on the situation analysis within the critical zone, we can assume that the agent's viewing range is not less than L. 3. Part of the energy in the impact goes into a rotational motion. In the model, these energy losses are taken into account exclusively by the recovery coefficient (formula (2)). 4. The ability of the agent to rotate the head is accounted for by the large viewing angle mentioned in 1. Thus, in the model some parameters are set implicitly, which simplifies the model and increases the computational speed. 3.2 Approach to model implementation 3.2.1 Calculation optimizations As follows from the model (1) - (6), for each agent for each step of model time, it is required to calculate distances to all other agents and walls of the room. Proceeding from the calculated values, it is necessary to calculate the maximum possible velocities for a certain set of directions of motion of a given agent by the ratio (3) (16 possible directions are accepted with step π/8), and then by criteria (4) - (6), determine the direction and the magnitude of the optimal speed vector, and then the acceleration of the agent. 104 A. SAMARTSEV, V. IVASCHENKO, A.REZCHIKOV, V.KUSHNIKOV et al. Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) The algorithm (for one step of model time) in this case will have computational complexity O(N2+NM), where N is the number of agents, and M is the number of walls. The quadratic complexity is not acceptable for systems with a large number of agents, so optimization is needed here, aimed to improve the asymptotic of the computational speed. Let С = {cij | 0 ≤ i < n, 0 ≤ j < m} is the network that divides the space into cells with side h; n, m – number of cells horizontally and vertically, respectively; cij is a cell with coordinates (i, j), and W ⊂ C is the set of cells to which the wall corresponds. In the software implementation, the room was divided by the network C into cells of width h = 10 cm. This cell size is small enough for having centers of two agents inside at once. The following data structure is being supported during calculations: – each agent has the coordinates of the cell in which he is located; – each cell cij contains a reference to an agent whose center is in the given cell (in the absence of such an agent, the reference is null). Each cij cell has the following attributes: – belonging to a wall or floor. – distance to the nearest exit dij; – vector eij, which specifies the direction to the exit. Therefore, for a given agent, it is necessary to test a limited set of neighboring cells for the presence of walls and other agents, which makes it possible to improve the computational complexity of the algorithm to O(N). 3.2.2 Calculation of the distances scalar field to the exit The attribute of the distance between exit and cij cell dij was calculated using the graph G = (V, E) given in the following way. Suppose that for each cell cij  W here exists a vertex of the graph G vij  V, and eijkl  E is the edge of the graph between the vertices vij and vkl. Then the set of edges E is defined as follows: E = {eijkl |∀a,b (a ∈ [min(i, k); max(i, k)] & & b ∈ [min(j, l);max(j, l)] → cab ∉ W) & (7) & (i, j) ≠ (k, l) & (i–k) ⊥ (j–l) & |i–k |≤ 2 & |j–l| ≤ 2)}. In addition, for each edge of the graph G, its length is given, which is proportional to the real distance between the cell centers corresponding to the vertices of the edge. The length lijkl of the edge eijkl is defined by the relation 22 )()( ljkilijkl  (8) Consider the formula for defining the set of edges in more detail. 1. ∀a,b (a ∈ [min(i, k); max(i, k)] & b ∈ [min(j, l); max(j, l)] → cab  W) means that among cells cij and ckl, and also cells between them in a rectangle with a diagonal connecting cij and ckl, there are no cells corresponding to the walls. 2. (i, j) ≠ (k, l) means that the graph is not reflexive. There is no sense for loops since they can not change the value of the distance from the exit to any vertex. 3. (i–k) ⊥ (j–l) means that numbers (i–k) and (j–l) are coprime, i.e. these numbers have no common divisors except number 1. This relation allows to simplify the graph, since edges for which this relation is not satisfied, can not change the value of the distance from the exit to any vertex. 4. |i–k |≤ 2 & |j–l| ≤ 2 means that the distance vertically and horizontally between the cells is not greater than 2. Thus, two vertices are connected by an edge only in cases where the corresponding cells: a) directly touch each other (they are vertical or horizontal neighbors); b) touch each other at one point (they are diagonal neighbors); c) are one cell far from each other by one dimension and two cell far from each other by the other (here an analogy with the L-shaped move of the chess knight can be drawn). MULTIAGENT MODEL OF PEOPLE EVACUATION FROM PREMISES WHILE EMERGENCY 105 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) Additionally, the connected cells and the cells that are between them should not correspond to the cells with the wall. Fig. 3 shows a fragment of graph G superimposed on the part of the room shown in Fig. 1 near the point with coordinates (15, 8). For clarity, in the picture edges, incident to two vertices are highlighted in red. One of these vertices is far from the walls and therefore has 16 incident edges. The second vertex is near the walls, so the number of edges incident to this vertex is less, and, in this case, is 9. Fig. 3. A fragment of the graph G near the point with coordinates (15, 8) On a given graph, it is necessary to implement the algorithm for finding the shortest paths for finding the distance from the exit to all other cells. Thus, for each vertex vij for which cij W, the distance dij to the nearest exit is determined. For cells cij∈W we assume that dij = ∞. In Fig. 4 graphically shows the scalar field d of the distances to the exit zone: the darker areas of the room are located further away from the exit. Also, Fig. 4 shows the field of the vector e, which is directed toward decreasing values of the field d. 3.2.3 Calculation of the vector field setting the direction to the nearest exit Let us dwell in more detail on the vector e field calculation procedure. We introduce the graph G’, which differs from the graph G by the set of edges. The set of edges E' of the graph G' is defined as follows E’ = { eijkl | (i, j) ≠ (k, l) & (i–k) ⊥ (j–l) & |i–k |≤ 2 & |j–l| ≤ 2)}. (9) Thus, when choosing a set of edges the presence of walls in the room is ignored. For the cell cij there are 16 possible directions of the vector eij with step π/8. These directions correspond to all the incident edges of the vertex vij in the graph G’. We number these edges from 0 to 15 in counterclockwise order starting from the edge parallel to the Ox and denote them respectively by e0 … e15. For each of these directions, we calculate the ratio mk = dk/lk, where lk is the length of the edge ek, and dk is the difference between the values of the distance attribute to the exit between vertices incident to ek. Thus, we obtain a vector m of 16 elements (m1 … mk). We introduce the vector m0 = (m01 … m0k), obtained from m by averaging the neighboring elements as follows: .10/)(5/)(5/2 16mod)18(16mod)14(16mod)17(16mod)15(0   kkkkkk mmmmmm (10) Let the element m0s be minimal, m0s = min m0. Then the angle between the vector e and the Ox axis is defined as s * π/8. The field of the vector e calculated for the premises is shown in Fig. 4. 106 A. SAMARTSEV, V. IVASCHENKO, A.REZCHIKOV, V.KUSHNIKOV et al. Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) Fig. 4. Scalar field d and vector field e 3.2.4 Multiparticle collisions When the model is implemented in practice, the question of multiparticle collisions arises. Two-particle collisions in the model are resolved by recalculating the velocities of the collided agents according to formula (2), provided that the distance between the centers of the agents is less than or equal to the sum of their radii, and the agents are approaching closer to each other. Multiparticle collisions are resolved by recalculating the velocities of colliding agents according to formula (2) in pairs for all colliding agents in the order determined by the indexes of the colliding agents on the list. It should be noted that many-particle collisions, as a rule, arise only in the case of a crush. In its absence, such collisions are extremely rare, in view of the fact that in the model the time step is sufficiently small, and the collision of agents takes only one step of model time. 4. MODEL USAGE RESULTS 4.1 Program structure The software for implementing the multi-agent model is written in the Java programming language using the Swing GUI library. Here is the structure of the program for implementing the model: 1. Set the initial data: the room dimensions, the coordinates of the walls, the exits from the room, the number and parameters of the agents, and the type of simulation results. 2. Initializing of the network C: constructing the graph G or the network C, defining the scalar field d and the vector field e. 3. Generation of agents within the evacuation zones. 4. The calculation of vopt for each agent (3 - 6). 5. The calculation of a for each agent. 6. The calculation of v for each agent (1). 7. The calculation of x for each agent (1). 8. Collision check for each pair of agents. If the collision takes place, then the speed should be recalculated. MULTIAGENT MODEL OF PEOPLE EVACUATION FROM PREMISES WHILE EMERGENCY 107 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) 9. Check of collisions with walls for each agent. If there is a collision, then the speed should be recalculated. 10. Verification of the exit condition for each agent. If the agent has reached the exit, then he is excluded from the list. It is considered that the agent has reached the exit if his center is in the exit zone. 11. Collection and storage of statistics. If there are no people left in the room, go to step 14. 12. Display the position of agents and walls on the screen in the program window. 13. Go to the next step of the model time. Go to step 4. 14. If the required number of intermediate experiments is not completed, then proceed to step 3. 15. Displaying the results of the experiment (graphics of functions). 16. Go to step 1 (user request). 4.2 Modelling results Computational experiments conducted on the software and information complex have shown that during evacuation agents demonstrate "reasonable" behavior. Most vivid example of such behavior is overtaking of one agent by another (Fig. 5). Fig. 5. Illustration of overtaking one agent by another (three stage of overtaking from left to right) In the situation there is no physical contact between the agents. The agent behind and having the maximum speed greater than the one of the agent moving in front of him, analyzes the situation around and chooses a route for overtaking. Eventually he gets to the exit, not waiting for the agent in front and does not spend his energy on physical contact with the other agent. The other examples of “reasonable” behavior of the agent are avoidance of collision with walls, deceleration when approaching obstacles (walls or congestion of other agents), maneuvering between other agents and choice of the nearest exit from premises during evacuation. However, agents demonstrate quite poor level of strategic “reasoning”, for example they never try to choose other exit when the one they approached occasioned to be flooded by other agents. All types of that behavior could be visually observed via software package UI. When studying the evacuation process with a large number of evacuated, there was an accumulation of agents in the exit zone and a crush which were also observed in [2, 14-17, 20, 22]. As an example, we present the results of numerical simulation of the evacuation process from a premises measuring 20 × 10 meters, the plan of which is shown in Fig. 1. The room contains 34 walls, each of which is specified by the parameters (x, y, xW, yW) in meters: (3.0; 3.0; 0.2; 10.0); (5.9; 3.0; 0.2; 1.0); (5.9; 5.0; 0.2; 2.0); (5.9; 5.0; 0.2; 2.0); (5.9; 108 A. SAMARTSEV, V. IVASCHENKO, A.REZCHIKOV, V.KUSHNIKOV et al. Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) 8.0; 0.2; 3.0); (5.9; 12.0; 0.2; 1.0); (7.9; 3.0; 0.2; 5.0); (8.9; 10.0; 0.2; 3.0); (11.9; 10.0; 0.2; 3.0); (15.9; 10.0; 0.2; 1.0); (15.9; 12.0; 0.2; 1.0); (17.9; 3.0; 0.2; 5.0); (17.9; 10.0; 0.2; 3.0); (19.9; 3.0; 0.2; 1.0); (19.9; 5.0; 0.2; 2.0); (19.9; 8.0; 0.2; 2.0); (20.9; 10.0; 0.2; 1.0); (20.9; 12.0; 0.2; 1.0); (22.9; 3.0; 0.2; 10.0); (3.0; 3.0; 3.5; 0.2); (7.5; 3.0; 11.0; 0.2); (19.5; 3.0; 3.5; 0.2); (3.0; 6.0; 3.0; 0.2); (20.0; 6.0; 3.0; 0.2); (7.9; 7.8; 5.1; 0.2); (15.0; 7.8; 3.1; 0.2); (3.0; 10.0; 4.0; 0.2); (8.0; 10.0; 2.0; 0.2); (11.0; 10.0; 1.0; 0.2); (16.0; 10.0; 0.5; 0.2); (17.5; 10.0; 1.0; 0.2); (19.5; 10.0; 3.5; 0.2); (3.0; 12.8; 10.0; 0.2); (15.0; 12.8; 8.0; 0.2). On the map, in 3 meters from the walls of the room the exit zones are set and specified by the parameters (x, y, xW E, yW E) in meters: (0; 0; 0.2; 16); (0.2; 0; 25.8; 0.2); (25.8; 0.2; 0.2; 15.8); (0.2; 15.8; 25.8; 0.2). The evacuation zone is defined by one element, which is specified by the parameters (x, y, xW Z, yW Z) in meters: (3; 3; 20; 10). The following numerical values of the evacuation process parameters were used: – number of evacuees (agents): 100; – their maximum speed vmax: random uniformly distributed quantity on a segment 1 – 2 m/s; – their maximum acceleration amax: randomly uniformly distributed quantity on the interval 1 – 2 m/s2; – the initial coordinates of each agent were chosen according to the uniform distribution law inside evacuation zones, proceeding from the condition that initially the projection of a person should not intersect the projections of other people and the walls; – radius of projection r: random uniformly distributed quantity on the segment 0,22 – 0,29 m; – critical distance: L = 2 m; – mass m: random uniformly distributed quantity on the segment 60 - 100 kg; – model time step: Δt = 0,004 s; – coefficient of recovery: ε = 0,4 [22, 28]. The results of modeling the evacuation process are shown in Fig. 6 - 9. The function hn(t) shows the dependence of the people inside premises number on time, provided that at the initial moment there are n people in the room. The function m nh is the result of averaging the function hn(t) over m implementations obtained during the simulation. The chart of function )( 100 100 th is shown on Fig. 6. Fig. 6. Chart of function )( 100 100 th MULTIAGENT MODEL OF PEOPLE EVACUATION FROM PREMISES WHILE EMERGENCY 109 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) The results showed that in the first few seconds of the evacuation process very few people leave the premises, since most of them are only at the beginning of their way to the exits. Then, at the exits, crowds of people begin to form, at which time the intensity of the flow of people through the doors increases. By about the 17th second, the intensity of the human flow through the exits is weakening. This is due to the fact that at this time, agents with lower speed of movement begin to evacuate, as well as with uneven distribution of the load over the exits from the premises (evacuation through some exits by this time could have already stopped). The long "tail" on the chart of the function )( 100 100 th in the range of the argument values from 35 to 70 s is explained by the formation of crushes at the exits from the room for some realizations of the experiment. Thus, with some initial arrangements of agents and the distribution of their parameters, evacuation can be delayed. Dependency resemble to )( 100 100 th was also analyzed in [2, 11] and graphs of a similar shape were obtained both in computer simulation and in the analysis of statistical data obtained during the actual evacuation. The quantitative differences between our research and results in [2, 11] are explained by different initial conditions (premises map and the number of people). A computational experiment was also performed to analyze the dependence of the average evacuation time tm(n) from the number of people n in the room: dtth n nt nm )( 1 )( 0 100    (11) The simulation results are shown in Fig.7. Fig. 7. Chart of function tm(n) As it can be seen from Fig. 7, the time of evacuation of people increases with the number of people increase. Some deviations from the monotonicity of the function tm(n) can be explained by the instability of the evacuation process in relation to the initial conditions, in particular, to the location of the agents in the premises at the very beginning of evacuation, and by the frequent formation of crushes. Let the function vh(n), which is defined for integer values of the interval [1; h], here h is the number of people at the beginning of the evacuation, n is the agent number in the agent list sorted by the order in which they reach the premises exit, and the value of the function is the maximum speed vmax of the agent with the number n in the specified list. 110 A. SAMARTSEV, V. IVASCHENKO, A.REZCHIKOV, V.KUSHNIKOV et al. Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) Let the function )(tv m h as the result of averaging the function vh(n) over the m implementations obtained during the simulation. Chart of function )( 1000 50 tv is shown in Fig. 8. Fig. 8. Chart of function )( 1000 50 tv As it can be seen in the Fig. 8, agents with a higher maximum speed are usually evacuates faster. The maximum speed of agents, which managed to evacuate among the very first ones, is especially great, because the crushes have not yet formed in the openings, and such agents can use their speed advantage to the full extent. After that, the maximum agent speed is reducing, and, finally, the last agents with the lowest maximum speed are evacuated, who did not managed to take advantageous positions in the evacuation process and had to wait for the disappearance of crushes in openings. Also, the analysis of the premises was carried out for the presence of places most dangerous in terms of quantity of the agents collisions with each other. In Fig. 9 the heat map of the premises is presented where the most dangerous places are marked with a more saturated red color. As it can be seen, the most dangerous are positions before the openings and slightly to the left and to the right of the opening. This can be explained by agents attempts to wedge into the main flow before the opening and the intensity of this flow. MULTIAGENT MODEL OF PEOPLE EVACUATION FROM PREMISES WHILE EMERGENCY 111 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) Fig. 9. Heatmap for collision possibility This map was constructed after modelling of 50 people evacuation from a given premises and averaging the results after 50 experiments. 5. CONCLUSION The model of the people evacuation process from premises in emergency situations in conditions of limited space of complex configuration is offered, which allows to obtain a more adequate assessment of the evacuation process due to the system considering of physical interaction of people in the evacuation process and the procedure for reasonable correction of goals pursued by intellectual agents in the evacuation process. The simulation of evacuation process in case of emergency on the basis of the proposed model makes it possible to assess the state and behavior of people in the occurrence of emergencies in the premises, as well as the number of people evacuated from the premises with different floor plan and occupation, depending on the maximum possible values of speed and acceleration. The model also allows to research impact of agent parameters on the order of their evacuation and find the most insecure places in the premises, where agents collide with each other and crushes appear. Strengths of the model include decent computational performance, account of agents’ physical interaction and complex premises map, focus on spontaneous evacuation process and possibility of computation parallelism. Experiments have shown results close to the ones of known evacuation models, during them agents have demonstrated patterns of “reasonable” behavior. Weaknesses of the current model implementation include absence of consideration of some factors, for example, agents’ ignorance of floor plan, agents’ verbal interaction, agents’ mutual assistance, other weakness is poor strategic “reasoning” in some cases. Integration with emergency models is of scientific and practical interest, for that emergency influence rules on agents must be considered. The model can be used for buildings evacuation safety validation or as a part of simulator for EMERCOM personnel training. 112 A. SAMARTSEV, V. IVASCHENKO, A.REZCHIKOV, V.KUSHNIKOV et al. Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) REFERENCES [1] Alizadeh, R. (2011). A dynamic cellular automaton model for evacuation process with obstacles. Safety Science, 49(2), 315-323 [2] Aptukov A.M., Bratsun D.A. & Liushnin A.V. (2013). Modelirovanie povedeniia panikuiushchei tolpy v mnogourovnevom razvetvlennom pomeshchenii [Modeling the behavior of a panicking crowd in a multilevel branched room], Komp'iuternye issledovaniia i modelirovanie, Vol. 5, № 3, 491– 508, [in Russian]. [3] Antonini G., Bierlaire M. & Weber M. (2006). Discrete choice models of pedestrian walking behavior // Transportation Research Part B. – 2006. – Vol. 40, № 8. – P. 667–687. [4] Beklarian A.L. & Akopov A.S. (2016). Agentnaia model' povedeniia tolpy pri chrezvychainykh situatsiiakh [Agent model of crowd behavior in emergency situations], XVI Aprel'skaia Mezhdunarodnaia nauchnaia konferentsiia po problemam razvitiia ekonomiki i obshchestva, Higher School of Economics Publishing House, 665-681, [in Russian]. [5] Beklarian A.L. (2015). Front vykhoda v modeli povedeniia tolpy pri chrezvychainykh situatsiiakh [Exit front in crowd behavior models in emergency situations], Vestnik Tambovskogo universiteta. Seriia: Estestvennye i tekhnicheskie nauki. Vol. 20, № 4, 851-856, [in Russian]. [6] Bosse, T., Hoogendoorn, M., Klein, M.C.A., Treur, J., Wal, C.N. et al.: Modelling Collective Decision Making in Groups and Crowds: Integrating Social Contagion and Interacting Emotions, Beliefs and Intentions. Auton Agnts Mult-Agnt Syst J, Vol. 27, 52-84 (2013) [7] Breer V.V. & Novikov D.A. (2012). Modeli upravleniia tolpoi [Crowd control models], Problemy upravleniia, № 2, 38–44, [in Russian]. [8] Breer V.V., Novikov D.A. & Rogatkin A.D. (2014). Stokhasticheskie modeli upravleniia tolpoi [Stochastic crowd control models], Upravlenie bol'shimi sistemami, № 52, 85–117, [in Russian]. [9] Cherif F. & Chighoub R. (2010). Crowd simulation influenced by agent’s sociopsychological state, Journal of computing, Vol. 2, № 4. 48–54. [10] Filimonyuk L. The Problem of Critical Events’ Combinations in Air Transportation Systems // Advances in Intelligent Systems and Computing, Springer International Publishing, 2017. Vol. 573. pp. 384-392. [11] Galea E., Deere S. & Filippidis, L. (2012). The Safeguard Validation Data Set— sgvds1 a Guide to the Data and Validation Procedures. Fire Safety Engineering Group, University of Greenwich London. [12] Gwynne, S., Galea, E. R., Owen, M., Lawrence, P. J., & Filippidis, L. (1999). A review of the methodologies used in the computer simulation of evacuation from the built environment. Building and environment, 34(6), 741-749 [13] Henderson L.F (1971). The statistics of crowd fluids, Nature, № 229, 381–383 [14] Helbing D., Farkas I. & Vicsek T. (2000). Simulating dynamical features of escape panic, Nature, № 407, 487–490. [15] Helbing D. (2001). Traffic and related self-driven many-particle systems, Reviews of Modern Physics, Vol. 73, № 4, 1067–1141. MULTIAGENT MODEL OF PEOPLE EVACUATION FROM PREMISES WHILE EMERGENCY 113 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) [16] Helbing D., Farkas I., Molnar Т. & Vicsek T. (2002). Simulation of Pedestrian Crowds in Normal and Evacuation Situations, Pedestrian and evacuation dynamics, Vol. 21, № 2, 21–58. [17] Helbing D., Johansson A. & Al-Abideen H.Z. (2007). Dynamics of crowd disasters: An empirical study, Physical review, Vol. 75, № 4, 0461091–0461097. [18] Kirchner, A., Klüpfel, H., Nishinari, K., Schadschneider, A. & Schreckenberg, M. (2003). Simulation of competitive egress behavior: comparison with aircraft evacuation data. Physica A: Statistical Mechanics and its Applications, 324(3-4), 689-697 [19] Kirchner, A., Nishinari, K., & Schadschneider, A. (2003). Friction effects and clogging in a cellular automaton model for pedestrian dynamics. Physical review E, 67(5), 056122. [20] Kirik E.S., Kruglov D.V. & Iurgel''ian T.B. (2008). O diskretnoi modeli dvizheniia liudei s elementom analiza okruzhaiushchei obstanovki [On a discrete model of people's movement with an element of analysis of the environment], Zhurnal SFU. Seriia «Matematika i fizika», Vol. 1, № 3, 266–276, [in Russian]. [21] Korepanov V.O. (2009). Imitatsionnye modeli takticheskogo povedeniia agentov [Simulation models of tactical behavior of agents], Upravlenie bol'shimi sistemami. № 26, 66–76, [in Russian]. [22] Korhonen T. (2016). Fire Dynamics Simulator with Evacuation: FDS+Evac Technical Reference and User’s Guide (FDS 6.5.2, Evac 2.5.2), VTT Technical Research Centre of Finland. [23] Krasnoshchekov P.S. (1998). Prosteishaia matematicheskaia model' povedeniia. Psikhologiia konformizma [The simplest mathematical model of behavior. Psychology of conformism], Matematicheskoe modelirovanie, Vol. 10, № 7, 76– 92, [in Russian]. [24] Moussaida M., Helbing D. & Theraulaza G. (2011). How simple rules determine pedestrian behavior and crowd disasters, PNAS, Vol. 108, № 17, 6884–6892. [25] Novikov D.A. (2015). Modeli informatsionnogo protivoborstva v upravlenii tolpoi [Models of information confrontation in crowd management], Problemy upravleniia, № 3, 29-39, [in Russian]. [26] Petrova M.S., Petrov S.V. & Vol''khin S.N. (2006). Okhrana truda na proizvodstve i v uchebnom protsesse [Labor protection at work and in the educational process], ENAS, 152 s, [in Russian]. [27] Predtechenskii V.M. & Milinskii A.I. (1979). Proektirovanie zdanii s uchetom organizatsii dvizheniia liudskikh potokov [Designing of buildings taking into account the organization of movement of human flows], Stroiizdat, 375 s, [in Russian]. [28] Putilov K.A. (1963). Kurs obshchei fiziki. T. 1. Mekhanika. Akustika. Molekuliarnaia fizika. Termodinamika. Izd. 11. [Course of General Physics. Vol. 1. Mechanics. Acoustics. Molecular physics. Thermodynamics. Ed. 11], Gos. izd-vo fiz.-mat. lit-ry, 560 s, [in Russian]. [29] Rezchikov A., Kushnikov V., Ivaschenko V.A., Bogomolov A., Filimonyuk L., Kachur K. (2016). Control of the air transportation system with flight safety as 114 A. SAMARTSEV, V. IVASCHENKO, A.REZCHIKOV, V.KUSHNIKOV et al. Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) the criterion. Automation Control Theory Perspectives in Intelligent Systems, Springer. [30] Rezchikov A., Kushnikov V., Ivaschenko V.A., Bogomolov A., Filimonyuk L., et al. (2017) The approach to provide and support the aviation transportation system safety based on automation models, Springer. [31] Rezchikov A., Dolinina O., Kushnikov V., Ivaschenko V., Kachur et al. (2016). The Problem of a Human Factor in Aviation Transport Systems, Indian Journal of Sciences & Technology. [32] Rezchikov, A.F., Kushnikov, V.A. & Ivashchenko, V.A. (2017). Prevention of critical events combination in robotic welding. Journal of Machinery Manufacture and Reliability. №4 370-379. [33] Samartsev A.A., Rezchikov A.F. & Ivashchenko V.A. (2016). Ispol'zovanie dinamicheskikh planov evakuatsii pri pozhare na promyshlennykh predpriiatiiakh [Use of dynamic evacuation plans in case of fire in industrial plants], Matematicheskie metody v tekhnike i tekhnologiiakh MMTT-29 V.3, 177-181 [in Russian]. [34] Samartsev A.A., Rezchikov A.F. & Ivashchenko V.A. (2016). Podkhod k minimizatsii vremeni evakuatsii liudei iz pomeshchenii promyshlennogo predpriiatiia [The approach to minimizing the time of evacuation of people from the premises of an industrial enterprise], Komp'iuternye nauki i informatsionnye tekhnologii: materialy Mezhdunar. nauch. Konf, Saratov: Nauka, [in Russian]. [35] Santos, G. & Aguirre, B. E. (2004). A critical review of emergency evacuation simulation models. [36] Skobelev P.O. (2010). Mul'tiagentnye tekhnologii v promyshlennykh primeneniiakh: k 20-letiiu osnovaniia Samarskoi nauchnoi shkoly mul'tiagentnykh sistem [Multiagent technologies in industrial applications: to the 20th anniversary of the founding of the Samara scientific school of multi-agent systems], Mekhatronika, avtomatizatsiia, upravlenie, № 12, 33-46, [in Russian]. [37] Sravnitel'naia kharakteristika chrezvychainykh situa-tsii, proisshedshikh na territorii Rossiiskoi Federatsii v 2016/2015 godakh [Comparative characteristics of emergency situations that occurred on the territory of the Russian Federation in 2016/2015] [Online]. Available http:// http://www.mchs.gov.ru/folder/33160904, [in Russian]. [38] Stepantsov M.E. (2004). Matematicheskaia model' napravlennogo dvizheniia gruppy liudei [Mathematical model of directed movement of a group of people], Matematicheskoe modelirovanie, Vol. 16, №3, 43–49, [in Russian]. [39] Tarasov V.B. (1998). Agenty, mnogoagentnye sistemy, virtual'nye soobshchestva: strategicheskoe napravlenie v informatike i iskusstvennom intellekte [Agents, multi-agent systems, virtual communities: a strategic direction in in-formatics and artificial intelligence], Novosti iskusstvennogo intellekta, № 2, 5-63, [in Russian]. [40] Tupikov D.V. & Ivashchenko V.A. (2014). Neirosetevoe prognozirovanie znachenii faktorov vozniknoveniia pozhara na proizvodstvennykh ob"ektakh [Neural network forecasting of the values of the factors of occurrence of a fire at MULTIAGENT MODEL OF PEOPLE EVACUATION FROM PREMISES WHILE EMERGENCY 115 Copyright ©2019 ASSA. Adv. in Systems Science and Appl. (2019) production facilities], Matematicheskie metody v tekhnike i tekhnologiiakh MMTT-27, V.3, 59-61 [in Russian]. [41] Tupikov D.V. & Ivashchenko V.A. (2015). Podkhod k obespeche-niiu pozharnoi bezopasnosti na promyshlennykh predpriiatiiakh [Approach to ensuring fire safety in industrial premises], Matematicheskie metody v tekhnike i tekhnologiiakh MMTT-28, Vol. 3, 51-54, [in Russian]. [42] Tupikov D.V. & Ivashchenko V.A. (2013). Razrabotka bazy znanii dlia operativnogo upravleniia vzryvo- i pozharo-opasnym proizvodstvom [Development of a knowledge base for the operational control of explosive and fire hazardous production], Vestnik Saratovskogo gosudarstvennogo tekhnicheskogo universiteta, № 3 (72), 133-137, [in Russian]. [43] Tupikov D.V. & Rezchikov A.F. (2014). Podkhod k postroeniiu nechetkoi bazy znanii dlia opredeleniia pozharoopasnykh situatsii [Approach to constructing a fuzzy knowledge base for determining fire hazard situations], Matematicheskie metody v tekhnike i tekhnologiiakh MMTT-27, Vol. 3, 125-127, [in Russian]. [44] Tupikov D.V., Rezchikov A.F. & Ivashchenko V.A. (2014). Algoritm podderzhki priniatiia reshenii po ustraneniiu pozharoopasnykh situatsii na promyshlennykh predpriiatiiakh [Algorithm for supporting decision-making on the elimination of fire-hazardous situations in industrial enterprises], Upravlenie bol'shimi sistemami, №52, 148-163 [in Russian]. [45] Tupikov D.V. Rezchikov A.F. & Ivashchenko V.A. (2014). Podkhod k prognozirovaniiu znachenii faktorov pozharo-opasnykh situatsii [Approach to predicting the values of fire hazard factors], Mekhatronika, avtomatizatsiia, upravlenie, № 7, 48-51, [in Russian]. [46] van der Wal, C. N., Formolo, D., Robinson, M. A., Minkov, M., & Bosse, T. (2017). Simulating crowd evacuation with socio-cultural, cognitive, and emotional elements. In Transactions on Computational Collective Intelligence XXVII (pp. 139-177). Springer, Cham. [47] Winter H. (2012). Modelling Crowd Dynamics During Evacuation Situations Using Simulation, Lancaster University. [48] Yu W. & Johansson A. (2017). Modeling crowd turbulence by many-particle simulations, Physical review, Vol. 76, № 4, 046105. [49] Zheng, X., Zhong, T., & Liu, M.: Modeling crowd evacuation of a building based on seven methodological approaches. Building and Environment, 44(3), 437-445 (2009)