INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL ISSN 1841-9836, 13(5), 865-880, October 2018. Running Cells with Decision-Making Mechanism: Intelligence Decision P System for Evacuation Simulation Y. Niu, Y. Zhang, J. Zhang, J. Xiao Yunyun Niu, Yongpeng Zhang, Jieqiong Zhang School of Information Engineering China University of Geosciences in Beijing, Beijing 100083, China yniu@cugb.edu.cn, zyp940701@163.com, jieqiong1755@163.com Jianhua Xiao* The Research Center of Logistics Nankai University, Tianjin 300071, China jhxiao2008@163.com *Corresponding author: jhxiao2008@163.com Abstract: Cell migration is a central process which happens along with multicellu- lar organisms' development and maintenance. The process that cells move to speci�c locations in particular directions has some similarities with pedestrian walking be- haviour. In this work, we propose a simulation model called an Intelligence Decision P System (IDPS), which is inspired by the process of cell migration. Each cell has its own decision-making mechanism and moving mechanism. They move towards its goals on a two-dimensional space under the guidance of external signals and its own regulations. Cells also communicate with each other according to speci�c interaction mechanism. The environment is de�ned as a place for cell movement. It includes signal objects, some of which help start or end the migration and others have great in�uence on the speed and directions of cells. It also keeps a record of current po- sition for each cell. Comparing with traditional P systems, cells can be considered as intelligent particles with decision-making mechanism and they can move to their destination. A case study is about modeling and simulating a building evacuation problem in a �re emergency by using the IDPS model. To our best knowledge, the topic of evacuation simulation was not under study in the �eld of membrane comput- ing before. The simulation result shows that the IDPS allows much easier and more precise modelling of pedestrian evacuation problems. So it is supposed to be a good simulation model for pedestrian walking behaviour. Keywords: membrane computing, P system, modeling and simulation, pedestrian evacuation. 1 Introduction Membrane computing is a branch of natural computing, which is inspired by the structure and the function of living cells or the organization of cells in tissues and organs [21]. The computational models in membrane computing are called P systems. Most P systems were proved to be computationally universal [16]. And many NP-hard problems or PSPACE problems were solved by P systems in a polynomial time or even a linear time [1,36]. Moreover, P systems provided distributed parallel and non-deterministic frameworks for computing and modeling [33], and then applied to various aspects of engineering [7,20]. On one hand, optimization algorithms with membrane structure, such as membrane-inspired evolutionary algorithms (MIEA) [21] and multi-objective membrane algorithm guided by the skin membrane (SMG-MOMA) [34], were proposed and outperformed general optimization algorithms. On the other hand, some kind of Copyright ©2018 CC BY-NC 866 Y. Niu, Y. Zhang, J. Zhang, J. Xiao P systems are used as modelling notation for ecological systems [2] and crowd behaviour [26]. Readers can �nd detailed assessments of various P systems in [22]. In traditional P systems, cells were designed for computing rather than moving. Membrane structure divided the space to several parts at the beginning. Objects or membranes evolved following speci�c rules. The computational results usually de�ned according to objects present in the output membrane in the halting condition. Recently, some P systems have involved the idea cell moving. Gemmating P systems introduces a new means of communication between membranes while keeping the de�nition of p system closer to the true structure of the cell. Through the movement of the membrane, the system sends a signal to the area designated by the target indication. At the same time, cells can selectively receive these signals [5]. Petre et al. got inspiration from mobile ambients and came up with mobile P-systems. By wrapping the object with the membrane and moving it to a predetermined destination, any two �static� cells can establish direct and secure communication [23]. The population P system allows cells to receive an object from other cells connected to it, which has no restriction on the transmission of the object [4]. In addition, cell movement can also be applied to the construction of the environment. Zhang et al. let the cell play the role of an obstacle and achieves dynamic environmental changes through cell movement [37]. However, most of P systems do not involve the concept of position except the spatial P systems [3] and grid-exploring P system [13]. In spatial P systems, objects in membranes are associated with positions. Membranes delimit space to di�erent regions. Evolution rules are associated with the positions of objects. Spatial P systems were proved to be universal and could be used to model the evolution of populations in presence of geographical separations [3]. The grid-exploring P system uses generalized membranes to form the grid elements. The changes of the positions of membranes leaded to di�erent spatial structures of the whole system. The arrangement of the inner membrane of the grid is optimized by arti�cial evolution to shorten the total time required for all particles to pass through the full channel. It takes the information- carrying particles as the main body of the movement [13]. In this study, we propose a simulation model called intelligent decision P system (IDPS), which is inspired by the cell migration process. Cells in this model are intelligent and movable. They choose their way to move according to their own mechanism and the interaction with their surroundings. Cell migration is a central process along with the multicellular organisms' development. Tis- sue formation during wound healing and immune responses all require the accurate movement of cells in particular directions to speci�c locations. Cells' movement is targeted. For example, when the white blood cells chase and attack the invading bacteria, they ignore the red blood cells and other harmless substances. If they meet the obstructions on their way, they can adjust their actions to bypass them. During the migration process, there are also some kinds of compe- tition behaviours as well as cooperation behaviours between cells. Information can be exchanged between di�erent cells. Cells often migrate in response to speci�c external signals. When they receive the signals, they open their internal switches and start the migration process. Some of the signal molecules may even a�ect the speed and direction of cell migration. The cells receive signaling molecule by using cell-surface receptor, which triggers a series of biochemical reactions and protein-protein interactions in the cell. After that, the signal molecules inside cells pass the information to the cytoskeleton and the molecular motor to complete the migration process. The process of cell migration is illustrated by Figure 1. First, a tip extends out of the polar feet. Second, the cell precursor and extracellular matrix form new cell adhesion. Third, cell shrinks. Finally, the tail is separated from the surrounding matrix, and the cell moves forward. The process includes cytoplasmic displacement at leading edge (front) and laminar removal of dorsally-accumulated debris toward trailing edge (back). The actions are similar to a pedestrian's walking motions. When walking, the forefoot steps on the ground �rst and the rear foot rises. Running Cells with Decision-Making Mechanism: Intelligence Decision P System for Evacuation Simulation 867 adhesion position polar feet new adhesion position old adhesion position cell migration direction Figure 1: Cell migration By comparison, we �nd that cells' migration has inherent similarities with pedestrians' walk- ing behaviour. For example, both cells and pedestrians can move to their destination and choose routes according to their own decision-making mechanisms. They can communicate with each other to update their knowledge during these processes. They can adjust their behaviours ac- cording to the environment around them. There are blocking, pushing or competition behaviour in both cell migration process and crowd evacuation process. So a simulation model which is inspired by the cell migration process is expected to be used to model the crowd evacuation behaviour. This is the main motivation of this study. Evacuation planning has become increasingly important in recent years which has attracted the attention of more and more researchers [10]. The e�cient evacuation of pedestrians is very important especially in the presence of a disaster such as a �re. E�ective evacuation strategy is the key to improve evacuation e�ciency and reduce the number of casualties. The public safety manager can use it to simulate pedestrian evacuation in the corresponding place, and then notice the potential danger in some evacuation process or draw up a reasonable evacuation plan [17]. In order to ensure the safety of evacuees, it is urgent to develop procedures for the evacuation of evacuees in emergency situations. However, the study of evacuation dynamics is very complex [35]. On one hand, a large number of people who belong to di�erent categories involved in the situation. The interaction between them is nonlinear and complex. The psychological factors also have great in�uence on their behaviours especially in a emergent situation. On the other hand, di�erent evacuation scenarios usually need di�erent strategies, and disasters often change the spatial accessibility of a scene. It is very di�cult for current modeling technologies to reproduce realistic situations completely. The basic task of indoor evacuation research is to simulate the building environment [25] and evacuees' behaviours [29]. Some researchers have conducted empirical studies of evacuation behavior, but there are wide variations in the results of various studies [27]. The reason for this may be due to cultural and population di�erences [11] or di�erent motives for movement [24]. There are several modelling techniques for evacuation problems in the literature. Both con- tinuum models and network-based models are macroscopic models. Both time and space are continuous. However, it is not very good at simulating the details of individual behavior [15]. The network-based models solve the problem of simulation of discrete events [8]. There are three famous microscopic models, that is, cellular automata models, agent-based models and social- force models. Cellular automata models represent the surroundings by a grid of cells [6]. Each cell can be occupied by one pedestrian or several pedestrians. Time is discrete, and at each step the movement of the individual depends on the state of the adjacent individuals and the prede�ned rules [31]. Agent-based models use di�erent agents to model individual pedestrians and form the macroscopic behaviour based on the interactions between agents [18]. Each agent has unique rules, so these models can model heterogenetic crowd [28]. But these models require a high cost of computing. In the social-force models, the movement of the individual is in�uenced by the forces from di�erent directions, such as the attraction of the direction of the target and the repulsion from other individuals [12]. Game-theoretic models allow evacuees to predict the behavior of other evacuees, based on the microeconomic concept of maximizing subjective util- 868 Y. Niu, Y. Zhang, J. Zhang, J. Xiao ity [14,19]. It is very di�cult for current modeling technologies to describe both the environment and the pedestrians as realistically as possible. Because of the similarity between cell migration and pedestrian walking behaviours, in this work we propose a simulation model called an intelligence decision P system (IDPS), which is inspired by the cell migration process to model the crowd evacuation behaviour. The main contributions of this paper can be summarized as follows. (1) Intelligence decision P system is de�ned including decision-making mechanism, moving mechanism, interaction mechanism. It also involves an accurate description of environment around cells. Each cell moves towards their goals on a two-dimensional space under the guidance of external signals and its own regulations. In each step, cells decide what is the next action to be performed through a deliberation decision-making process until the termination signal occurs. Several characteristics, such as non-deterministic maximally parallel manner, priority rules and communication rules are also inherited by our model from traditional P systems. Unlike traditional P systems, cells in the IDPS are intelligent and movable. They communicate with each other during the moving process. So the IDPS combines individual intelligence and swarm intelligence, where cells can be considered as intelligent particles. (2) To our best knowledge, the topic of evacuation simulation was not under study in the �eld of membrane computing before. In this study, the IDPS is used to model the building evacuation process in the presence of a �re disaster as a new modelling technique. Evacuees with di�erent knowledge bases are described by cells with decision-making mechanism. They percept environment and interact with each other to update their knowledge bases during the evacuation process. Each pedestrian is modelled individually. Our model can describe the movement or the interactions of pedestrians as realistically as possible. The result shows that the IDPS model allows much easier and more precise modelling of building evacuation problems. 2 Intelligence decision P system Formally, an Intelligence Decision P System of degree n ≥ 1 is de�ned as follows Π = (Γ,E(0),C1, . . . ,Cn,R,G,ss,st), where: � n ≥ 1 (the system contains n cells, labeled with 1, 2, · · · ,n; all these n cells are placed in the environment and the environment is labeled with 0); � Γ is the alphabet of objects; � The environment E is de�ned as a set of objects to describe the scene of cell movement. It includes signal objects, some of which help start or end the migration and others have great in�uence on the speed and directions of cells. It also includes a system clock to keep a record of current time of the system and a counter to calculate the number of cells going out of the exits. The width of environment is denoted by w, and the height of environment is denoted by h. E(0) is the set of objects in the environment at the beginning of the simulation; � C (j) i = {p (j) i ,v (j) i ,K (j) i ,m (j) i } represents the state of cell i at step j, where p (j) i = (x (j) i ,y (j) i ) records the real-time location of cell i with 0 < x (j) i < w, 0 < y (j) i < h, v (j) i is the speed of the cell i at step j, K (j) i = {k1, . . . ,kn} describes the knowledge base of cell i at step j, and m (j) i means the type of cell. C (0) i denotes the initial state of cell i. Running Cells with Decision-Making Mechanism: Intelligence Decision P System for Evacuation Simulation 869 � R is the set of evolution rules which includes the following types of rules: 1. Knowledge base update rules: Cells make decision based on their own knowledge bases. The initial knowledge bases are set according to cell types mi. And then they are updated in two di�erent ways. One is obtaining information from the environment. The other is exchanging infor- mation with other cells. (1) Interaction with environment: Cells obtain information from the environment, such as information about real-time tra�c, route guidance signals, obstacles, starting signal and termination signal. Each information has a perception region. If a cell is in this region, it can get the informa- tion as shown in the following rules. K (j) i → K ′(j+1) i ,∀i ∈{1, . . . ,n}, K ′(j+1) i = { K (j) i ∪{a}, pi ∈ Ra K (j) i , pi /∈ Ra where Ra indicates the perception region of information a. The knowledge base of cell i is updated by adding information a, if cell i reaches to Ra. (2) Communication with other cells: Cells can share information with their neighbors. We suppose the distance of two neighbors is not no more than a threshold d. If lbest ∈ K ′(j+1) i ∪K ′(j+1) k , |pi−pk| ≤ d is the information which leads to the best running plan of cell i or cell j, and lbest is not in K ′(j+1) i , K ′(j+1) i is updated by adding information lbest. K ′(j+1) i → K (j+1) i ,∀i ∈{1, . . . ,n}, K (j+1) i = { K ′(j+1) i ∪{lbest}, lbest /∈ K ′(j+1) i K ′(j+1) i , lbest ∈ K ′(j+1) i 2. Type transition rules: Cell type is de�ned according to the knowledge base in the cell. The knowledge base change may lead to the cell type transition. K (j+1) i m (j) i → K (j+1) i m (j+1) i . 3. Decision-making rules: According to the knowledge base and the current position, cell i can obtain several running schemes at step j. K (j) i p (j) i →{Scheme (j) i,1 , . . . ,Scheme (j) i,ik }. Choose the best scheme Scheme (j) i,best according to speci�c requirement, for example, minimizing distance from current position to the exit. {Scheme(j)i,1 , . . . ,Scheme (j) i,ik }→ Scheme(j)i,best. It is worth mentioning that priorities can be easily added to these rules for decision- making. 870 Y. Niu, Y. Zhang, J. Zhang, J. Xiao 4. Position-updating rules: The expected velocity and moving direction can be calculated from Scheme (j) i,best, Scheme (j) i,best → (v ′(j) i ,d ′(j) i ). In the process of moving, the actual situation may not allow cells to follow the direction of planning, then the cells need to adjust their behaviour. For example, when a cell encounters an obstacle (a wall or other cells in front of the cell), it needs to bypass the obstacle to move on. The actual velocity and direction of cell i at step j are denoted by v (j) i and d (j) i , respectively. (v ′(j) i ,d ′(j) i ){o1, . . . ,oq}→ (v (j) i ,d (j) i ), where o1, . . . ,oq represent obstacles. Cell i updates its position according to the current position and speed. (x (j) i ,y (j) i )(v (j) i ,d (j) i ) → (x (j+1) i ,y (j+1) i ), where (x (j) i ,y (j) i ) means the position of cell i at step j, (v (j) i ,d (j) i ) means the speed and the moving direction of cell i at step j. � G is the set of destinations or exits of the moving cells. � ss is the starting signal for cell movement, while st is the termination signal. The rules of a system as above are used in the non-deterministic maximally parallel manner. When the starting signal ss appears in the environment, cells move towards their goals under the guidance of rules in R. In each step, cells decide what is the next action to be performed. They usually stop moving when they reach their destinations or they get the termination signal st from the environment. A con�guration of IDPS Π is described by the multisets of objects in the cells and the environment. C (j) 1 , . . . ,C (j) n represent the states of all the cells present in the system at step j. They involve four basic characters of cells. That is, position, speed, knowledge base and type. The next system's con�guration is determined by rules in R from the previous one. All computations start from the initial con�guration and proceed. Cells stop moving when they reach their destinations or when they get the termination signal st from the environment. The system stops evolving when all cells stop moving. The simulation results can be obtained by counting the number of cells going out of the exits. 3 Intelligence decision P System for evacuation simulation This section describes how intelligence decision P system model the evacuation process of evacuees with di�erent knowledge bases in a �re emergency. A teaching building of China University of Geosciences (Beijing) was used as a sampling evacuation environment in this study, see Figure 2. The classrooms, the walls, the doors, the corridor and the exits are represented by yellow, gray, blue, light blue and green, respectively. There are three exits, from left to right, exit 1, exit 2 and exit 3. The black area represents the safe area outside the building. For the sake of simpli�cation, cells in our model have the same size and the same moving speed. The de�ection angle of cell's moving direction is denoted by θ, θ ∈ [0, 360].The viewing angle is set by default to 120◦ [9]. Evacuees can only see objects within their visual �elds, and evacuees cannot see the situation in other side of the wall (see Figure 3). Running Cells with Decision-Making Mechanism: Intelligence Decision P System for Evacuation Simulation 871 Figure 2: The experimental scene wall exit Figure 3: The visual �eld of a cell 3.1 Knowledge base update There are eight categories of cells in our model. They are divided according to their familiarity of the exits. The �rst kind of cells have the knowledge about how to reach all the exits; the second, the third and the fourth kinds of cells have knowledge about two di�erent exits,respectively; the �fth, the sixth and the seventh kinds of cells know one exit only and the eighth kind of cells have no idea about any passable exits. Evacuees knowing all the exits have the whole knowledge of the building, we call them "experts". Others have partial information about the building, we call them "followers". In the initial state, every cell knows at least one exit. Cells get information to update their knowledge base in three ways. (1) The followers tend to be attracted by the experts. Followers identify experts based on the object mi in cell i. If the followers see the experts, they will move to the experts and then they get useful information, and update the knowledge base. (2) The followers have a certain probability to interact with each other. They share their own current optimal route information, and update their knowledge base. (3) The information about the nearest exit can be obtained from the guide signs. If cells in it's perception region and �nd these signs, they update their knowledge base immediately. The knowledge base can be updated by using the following rules. K′i → Ki,∀i ∈{1, . . . ,n}, Ki = { K′i ∪{lbest}, lbest /∈ K ′ i K′i, lbest ∈ K ′ i where lbest is the best information held by other evacuees who interact with the evacuee i. If the evacuee i interacts with other neighbors( the distance of two evacuees is less than 2) and acquires new information lbest, he updates the knowledge base K ′ i to K ′ i ∪{lbest}, otherwise the original knowledge base K′i is maintained. K′i = { Ki ∪{g}, pi ∈ Rg Ki, pi /∈ Rg 872 Y. Niu, Y. Zhang, J. Zhang, J. Xiao where Rg indicates the perception region of the information g sent by guide signs. The knowledge base of evacuee i is updated by adding information g, if evacuee i reaches to Rg. When cells get new information and update the knowledge bases, their categories may be changed at the same time. During the evacuation process, when a �re occurs, the exit may be blocked by �re. In that case, some evacuees may have no useful information to �nd any exit. They belong to the eighth category, and have to walk randomly until their knowledge bases are updated by interaction with other evacuees or the environment. When they get information about another exit, they will change their category once again. Similarly, cells can become "experts" when they obtain information about all exits during the evacuation process. P0 represents evacuees who have no idea about any passable exits. P1, P2, and P3 represent evacuees who know one exit, two exits and three exits, respectively. mi =   P0, Ki = ∅ P1, Ki = {a} or {b} or {c} P2, Ki = {a,b} or {a,c} or {b,c} P3, Ki = {a,b,c} Where a, b, and c respectively represent the information of the three exits. 3.2 Behaviour adjustment According to the knowledge base, evacuees tend to choose the path with the shortest distance. Scheme (j) i,best → (v ′(j) i ,d ′(j) i ) calculates the expected speed and moving direction. However, they cannot move as expected in many cases. To avoid collisions, cells attempt to keep a distance from the surrounding obstacles while moving. These obstacles include walls and other evacuees. So cells have to adjust their behaviour to avoid collisions. If the best way to the exit is blocked, the evacuee will choose another way to move. The feasible speed and moving direction can be calculated by (v ′(j) i ,d ′(j) i ){o1, . . . ,oq}→ (v (j) i ,d (j) i ), where o1, . . . ,oq represent obstacles. In the narrow corridor, the �ows of cells of two opposite directions are often encountered. To avoid the confusion caused by cross �ow of cells, cells attempt to communicate with other cells who move in the opposite direction. They exchange information with each other and update their knowledge base. According to the new knowledge base, they re-plan evacuation routes. Some of them change their direction, and then communicate with other evacuees who are moving in the opposite direction. This process is repeated until all evacuees move in the same direction. This kind of behaviour adjustment is shown in Figure 4. moving direction moving direction moving direction Figure 4: Interactive behaviour in cross �ow Running Cells with Decision-Making Mechanism: Intelligence Decision P System for Evacuation Simulation 873 3.3 IDPS-based simulation of evacuation All cells have initial knowledge base K (0) i at the beginning. When the ss (initial signal) appears, cells start moving. In detail, the evacuation process can be simulated according to the following steps. Step 1: The system checks whether there is a termination signal st. If there is a termination signal st, the simulation is �nished. Otherwise, go to step 2. Step 2: If the cell �nds the exit in its view �eld, go to step 7. Otherwise, the simulation continues. Step 3: If the cell interacts with the expert before, go to step 6. Otherwise, the simulation continues. Step 4: If the cell �nds no expert in its view �eld, go to step 6. Otherwise, the simulation continues. Step 5: The cell moves to the expert and gets information, go to step 8. Step 6: If the cell �nds the guide sign in its view �eld, it gets the information provided by the guide sign, go to step 8. Otherwise, the simulation continues. Step 7: The cell has a certain probability to interact with its neighbours and share information with them. Step 8: The cell updates the knowledge base and translates category. Step 9: The cell makes path planning according to the decision-making rules. Step 10: The cell adjusts its behaviour and moves with the actual velocity. Step 11: If the cells reach the exit, the evacuation is successful. Otherwise, the simulation continues and go to step 2. In general, the probability of interaction between cells is set to 20%. But when a cell cannot plan the route because there is no information available, its interaction with its neighbours will rise to 100% until it can plan an available evacuation route based on the information obtained. On the other hand, if a cell has interacted with one expert, he will not go looking for other experts because he has got enough information. 4 Experiments and results analysis The simulation system is implemented using NetLogo. Two scenarios are considered in this experiment. In scenario 1, �re occurred in the classroom and did not block any exit. After the evacuation of the sta� in the classroom where the �re broke out, the classroom can be closed to ensure that the �re will not spread for a certain period of time. In scenario 2, the �re happened at the exit 1 and made exit 1 impassable. In a short period of time, the �re will block the exit 1, and evacuees need to consider what strategy should be taken if the planned evacuation route is blocked in the evacuation process. The total number of evacuees in experiment is set to 500. The proportion of experts can be adjusted. We will discuss it in section 4.1. There are six types of followers at the beginning. Their proportion is given in Table 1. And the initial position of evacuees is distributed randomly. Table 1: Initial proportion of the number of di�erent types of followers Type of evacuees 1 2 3 4 5 6 Exit 1 √ √ √ Exit 2 √ √ √ Exit 3 √ √ √ Proportion 10% 10% 10% 20% 30% 20% 874 Y. Niu, Y. Zhang, J. Zhang, J. Xiao The results of experiment are evaluated by average evacuation time and the number of casu- alties. The average evacuation time is used to measure evacuation e�ciency. It is calculated by the following equation [30] Avg.E(t) = (Σnei=1tei) + tsnf ntotal (1) where ntotal is the total number of evacuees in the building, tei is the time to reach the exit for evacuees i, ts is the total simulation time, ne is the number of successful evacuations, and nf is the total number of evacuees who did not escape in the simulation. After some investigation, we found that the concentration of smoke generally reached the maximum value that evacuees can bear within 180s in the teaching building. So we set the simulation time to 180s. When the smoke concentration reaches this value, the evacuees in the building will get injured and not move any more. At the same time, the system sends out a termination signal to end the simulation process. Some of the properties of the experiment are simulated by random control, so individual simulation results with the same environment and parameter speci�cations may be di�erent. The properties of experiment that are controlled in this way include the initial position of evacuees and evacuees's interactive behavior. Because of this potential di�erence between simulations, we perform multiple simulations for each scenario and note the average result. For each experiment, the experimental result takes the average of the results of the ten experiments. 4.1 The e�ect of experts Experiments were conducted to test experts' impact on evacuation e�ciency in scenario 1 and scenario 2 (Figure 5 and Figure 6, respectively). Figure 5 illustrates the evacuation e�ciency in scenario 1 with 30 experts and without experts. When there was no experts to guide the crowd, it was not until 174s that the evacuation was completed. This value is very close to the terminal time (180s). Under the guidance of 30 experts, all evacuees completed the evacuation within 140s. Although no one was injured in the two experiments, the e�ciency of the evacuation with 30 experts was much higher than the evacuation without experts. Figure 6 illustrates the evacuation e�ciency in scenario 2 with 30 experts and without experts. Since exit 1 was blocked, more than 40 evacuees failed to evacuate without experts. When there are 30 experts involved, all evacuees can evacuate within 180s. Although evacuees try to move to the nearest exit they know, sometimes that is not the best choice for them. Without accurate information about the building, evacuees spend a lot of time on redundant paths. When experts appears in the crowd, this situation can be improved greatly. Because they can provide information about the best exit to the followers. Figure 5: The e�ect of experts in scenario 1 Figure 6: The e�ect of experts in scenario 2 Running Cells with Decision-Making Mechanism: Intelligence Decision P System for Evacuation Simulation 875 The impact of experts' quantity on evacuation e�ciency was also tested. The number of experts were set to 0, 20, 50 and 100 respectively, see Table 2. In scenario 1, the average evacuation time decreased with the increasing number of experts. But if the number of experts exceeded a threshold, its e�ect on the evacuation process was not obvious. In scenario 2, the average evacuation time was increased comparing with that in scenario 1 and 42 evacuees got injured without experts. When experts appear in the crowd, the average evacuation time is shortened obviously and the number of injured evacuees reduced greatly. As shown in Table 2, the experts' quantity plays an important role in the evacuation process. The more experts, the fewer injured evacuees. Therefore, we should pay attention to popularize the knowledge of building structure to evacuees at ordinary times. Table 2: The e�ect of experts Experiments Scenario 1 Scenario 2 Exp#1 Exp#2 Exp#3 Exp#4 Exp#1 Exp#2 Exp#3 Exp#4 number of evacuees 500 500 500 500 500 500 500 500 number of experts 0 20 50 100 0 20 50 100 Avg.E(t) 85.3 75.2 50.7 45.2 102.5 86.4 72.7 67.1 Avg.Hurt 0 0 0 0 42 5 0 0 4.2 The e�ect of guide signs In this subsection, we analyze the e�ect of guide signs. Five experiments were conducted with di�erent numbers of guide signs. Figure 7 shows the location distribution of guide signs in the building, where the orange areas represents the guide signs. Guide sign 1 points to exit 1. Both guide sign 2 and guide sign 3 point to exit 2. Both guide sign 4 and guide sign 5 point to exit 3. There was no guide sign in Exp# 1; the number of guide signs was increased sequentially from Exp# 2 to Exp# 6. Figure 7: Distribution of guide signs Experiments were conducted to test the guide signs' impact on evacuation e�ciency in sce- nario 1 and scenario 2 (Figure 8 and Figure 9, respectively). Figure 8 shows that the evacuation e�ciency increases with the increase of the number of guide signs in scenario 1. However, the number of evacuees near exit 1 will increase dramatically, and the probability of overcrowding and injury rise. In scenario 2, exit 1 is congested, the evacuation e�ciency is decreased. Attention should be paid to evacuation guidance in this area. Moreover, the invalid road signs will give evacuees the wrong guide. In Exp#2, because of the wrong guidance of guide sign 1, many evacuees took the ine�ective path. Therefore, in the early stage of evacuation, the evacuation e�ciency in Exp#2 is 876 Y. Niu, Y. Zhang, J. Zhang, J. Xiao lower than that in Exp#1, see Figure 9. But after 80s, the evacuation e�ciency in Exp#2 began to increase gradually, and �nally exceeded the evacuation e�ciency in Exp#1. The reason for this phenomenon may be that guide sign 1 makes a large number of evacuees gathered near the exit 1, and the probability of successful interaction between them is increasing, so the evacuees can quickly �nd the location of the nearest exit. Another phenomenon that we can observe from Figure 9 is that the emergence of guide sign 2 and guide sign 3 makes the evacuation e�ciency improved signi�cantly. So guide sign 2 and guide sign 3 are more important than other signs. The average evacuation time and the average number of casualties are reported in Table 3. It is shown that guide signs play an important role in shortening evacuation time and reducing the number of injured evacuees in most cases. But in scenario 2, when exit 1 is blocked, there are still a lot of evacuees moving towards exit 1 because of the guide sign 1. In that case, both the average evacuation time and the average number of casualties in Exp#2 are more than those in Exp#1. Therefore, if an exit is blocked by �re, the corresponding guide signs may have a bad e�ect on the evacuation process. Figure 8: The e�ect of guide signs in scenario 1 Figure 9: The e�ect of guide signs in scenario 2 Table 3: The e�ect of guide signs Experiments Scenario 1 Exp#1 Exp#2 Exp#3 Exp#4 Exp#5 Exp#6 Avg.E(t) 85.7 82.3 71.5 66.7 60.2 57.2 Avg.Hurt 0 0 0 0 0 0 Experiments Scenario 2 Exp#1 Exp#2 Exp#3 Exp#4 Exp#5 Exp#6 Avg.E(t) 104.8 112.5 97.3 89.5 81.2 78.2 Avg.Hurt 56 77 11 0 0 0 4.3 The e�ect of composition proportion of the crowd In this section, three experiments with di�erent proportions of evacuees were conducted. The parameters of three di�erent crowds are listed in Table 4. Table 5 shows the comparison of the experimental results under the in�uence of three di�erent proportions of evacuees. When the number of evacuees who knew exit 1 and exit 2 was more, the average evacuation time is relatively shorter, but there are injured evacuees. When the number of evacuees who knew exit 3 was higher, although the average evacuation time was longer, there were no injured evacuees. The reason for this phenomenon may be due to a large number of evacuees gathered in the vicinity of exit 1, resulting in a long time congestion phenomenon. This congestion hampered Running Cells with Decision-Making Mechanism: Intelligence Decision P System for Evacuation Simulation 877 the movement of many evacuees who wanted to go to other exits, and some evacuees failed to evacuate in time. Therefore, in an emergency, more attention should be paid to handle the crowd e�ciently and avoid congestion. Table 4: The proportion of di�erent types of evacuees Type of evacuees 1 2 3 4 5 6 Exp# 1 20% 10% 20% 30% 10% 10% Exp# 2 20% 20% 10% 10% 30% 10% Exp# 3 10% 20% 20% 10% 10% 30% Table 5: Results of experiments with di�erent proportions of evacuees Experiments Scenario 1 Scenario 2 Avg.E(t) Avg.Hurt Avg.E(t) Avg.Hurt Exp#1 83.7 5 123.5 63 Exp#2 76.3 2 82.6 32 Exp#3 90.4 0 97.2 41 4.4 The e�ect of interaction probability In this section, experiments were designed to analyze the e�ect of interactive probability. The probability of interaction between followers are set to 0%, 20%, 40%, 60%, 80% and 100%, respectively. Experts and guide signs were not involved in these experiments at the beginning. However, when an evacuee got information about all exits, he can convert his role from a follower to an expert. Figure 10 and Figure 11 show the experimental results in scenario 1 and scenario 2, respec- tively. As the increase of the probability of interaction, the evacuation time decreases rapidly in the early stage. But as the probability of interaction becomes higher and higher, this reduction trend slows down, and then there is even a rising trend. This phenomenon occurs because the interaction between the evacuees takes a certain amount of time, and frequent interactions may get a lot of repetitive information. This factor has an adverse e�ect on evacuation e�ciency. By the experiments, we can see that 60% is the best interaction probability in both scenario 1 and scenario 2. Figure 10: The e�ect of interaction probability in scenario 1 Figure 11: The e�ect of interaction probability in scenario 2 878 Y. Niu, Y. Zhang, J. Zhang, J. Xiao 5 Conclusions In view of the similarity between cell migration process and the pedestrian walking behaviour, an intelligence decision P system (IDPS), which was inspired by the process of cell migration, was proposed in this paper to simulate the building evacuation. It involves decision-making mechanism, moving mechanism, interaction mechanism of cells, as well as accurate descriptions of external information around them. It can use both continuous and discrete time and space representations. In two-dimensional space, each cell moves towards their goals under the guidance of external signals and its own regulations. Each cell has its own decision-making mechanism and moving mechanism. They can also communicate with each other or interact with external signals in their surroundings during the moving process. A case study was modeling and simulating the evacuation of pedestrians in buildings by using the IDPS. When a �re occurs, evacuees received signals and started to move toward the exits. They made decisions which were in their best interests. We analyzed some factors that a�ect evacuation e�ciency, including experts, guide signs, the proportions of di�erent types of evacuees, and the interaction probabilities. The results of experiment are evaluated by average evacuation time and the number of casualties. The results showed that the IDPS model allowed much easier and more precise modelling of pedestrian evacuation problems. This study combined the P system approach with new application scenarios. The crowd evacuation in buildings under emergency situations was modeled and simulated based on a novel P system. So far as we know, the topic was not under study in the �eld of membrane computing before. Some characters of P systems, such as non-deterministic maximally parallel manner, priority rules and communication rules, were used to help simulate the building environment and evacuees' behaviours. The IDPS model can easily be combined with probabilistic approaches or other technologies to simulate more complex behaviours. Our model can be applied to other types of crowd management problems, such as high-rise building evacuation simulation, with appropriate modi�cations. Funding This work was supported by the Beijing Natural Science Foundation [grant numbers 4164096]; the National Natural Science Foundation of China [grant numbers 61502012, 61373066, 61772290]; the Humanity and Social Science Youth Foundation of Ministry of Education of China [grant number 13YJC630010]; the Science and Technology Development Strategy Research Program of Tianjin [grant number 16ZLZXZF00030]; the Asia Research Center in Nankai University [grant number AS1711]; and the Collaborative Innovation Center for China Economy. Bibliography [1] Alhazov, A.; Martin-Vide, C.; Pan, L. (2003); Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes, Fundamenta Informaticae, 58(2), 66�77, 2003. [2] Barbuti, R.; Bove, P.; Milazzo, P.; Pardini, G. (2015), Minimal probabilistic P systems for modelling ecological systems, Theoretical Computer Science, 608, 36�56, 2015. [3] Barbuti, R.; Maggiolo-Schettini, A.; Milazzo, P.; Pardini, G.; Tesei, L. (2011); Spatial P systems, Nat Comput, 10, 3�16, 2011. Running Cells with Decision-Making Mechanism: Intelligence Decision P System for Evacuation Simulation 879 [4] Bernardini, F.; Gheorghe, M. (2004); Population P Systems, Journal of Universal Comput- erence, 10(5), 509-539, 2004. [5] Besozzi, D.; Mauri, G.; P un, G. (2003); Gemmating P systems: collapsing hierarchies, Theoretical Computer Science, 296(2), 253�267, 2003. [6] Blue, V.J.; Adler, J.L. (2001); Cellular automata microsimulation for modeling bidirectional pedestrian walkways, Transportation Research Part B Methodological, 35(3), 293�312, 2001. [7] Ciobanu, G.; Pérez-Jiménez, M.J.; P un, G. eds. (2006); Applications of membrane com- puting, Springer Berlin Heidelberg, 287(1), 73�100, 2006. [8] Chalmet, L.G.; Francis, R.L.; Saunders, P.B. (1982); Network Models for Building Evacua- tion, Fire Technology, 18(1), 90-113, 1982. [9] Fu, Y.W.; Liang, J.H.; Liu, Q.P.; Hu, X.Q. (2015); Crowd Simulation for Evacuation Be- haviors Based on Multi-agent System and Cellular Automaton, International Conference on Virtual Reality and Visualization., 103-109, 2015. [10] Gómez, N.P.; O'Brien, K.; Silverman, B.G.; Badler, N.I. (2005); Crowd Simulation In- corporating Agent Psychological Models, Roles and Communication, First International Workshop on Crowd Simulation, 21�30, 2005. [11] Helbing, D.; Johansson, A.; Al-Abideen, H.Z. (2007); Dynamics of crowd disasters: an empirical study, Phys. Rev. E - Statist., Nonlin., Soft Matter Phys, 75(4), 1-7, 2007. [12] Helbing, D.; Molnar, P. (1995); Social force model for pedestrian dynamics, Phys. Rev. E, 51(5), 4282�4286, 1995. [13] Hinze, T.; Weber, L.L.; Hatnik, U. (2016); Walking membranes: grid-exploring P systems with arti�cial evolution for multi-purpose topological optimisation of cascaded processes, International Conference on Membrane Computing, 251-271, 2016. [14] Hoogendoorn, S.; Bovy, P.H.L. (2003); Simulation of pedestrian �ows by optimal control and di�erential games, Optimal Control Applications & Methods, 24 (3), 153�172, 2003. [15] Hughes, R.L. (2002); A continuum theory for the �ow of pedestrians, Transportation Re- search Part B, 36(6), 507�535, 2002. [16] Ionescu, M.; P un, G.; Yokomori, T. (2006); Spiking Neural P Systems, Fundamenta Infor- maticae, 71, 279�308, 2006. [17] Ibrahim, A.M.; Venkat, I.; Wilde, P.D. (2017); Uncertainty in a spatial evacuation model, Physica A Statistical Mechanics & Its Applications, 479, 485-497, 2017. [18] Junaedi, H.; Hariadi, M.; Purnama, I.K.E. (2013); Multi agent with multi behavior based on particle swarm optimization (PSO) for crowd movement in �re evacuation, International Conference on Intelligent Control & Information Processing, 366-372, 2013. [19] Lovreglio, R.; Ronchi, E.; Nilsson, D. (2016); An Evacuation Decision Model based on perceived risk, social in�uence and behavioural uncertainty, Simulation Modelling Practice & Theory, 66, 226-242, 2016. [20] Pan, L.; P un, G.; Pérez-Jiménez, M.J. (2011); Spiking neural P systems with neuron division and budding, Science China Information Science, 54(8), 1596�1607, 2011. 880 Y. Niu, Y. Zhang, J. Zhang, J. Xiao [21] P un, G. (2000); Computing with membranes, Journal of Computer and System Sciences, 61(1), 108�143, 2000. [22] P un, G.; Rozenberg, G.; Salomaa A. (2009); The Oxford Handbook of Membrane Comput- ing, Oxford University Press, 2009. [23] Petre, I.; Petre, L. (2001); Mobile Ambients and P-Systems, Turku Centre for Computer Science, 2001. [24] Predtechenskii, V.M.; Milinskii, A.I. (1978); Planning for Foot Tra�c Flow in Buildings NBS, Fire Technology, 1978. [25] Ronchi, E.; Nilsson, D.; Gwynne, S.M.V. (2012); Modelling the Impact of Emergency Exit Signs in Tunnels, Fire Technology, 48(4), 961-988, 2012. [26] Sakellariou, I.; Stamatopoulou, I.; Kefalas, P. (2012); Using membranes to model a multi- agent system towards underground metro station crowd behaviour simulation, ECAI 2012 workshop. Montpellier, France, August, 28, 5�10, 2012. [27] Schadschneider, A.; Seyfried, A. (2010); Empirical results for pedestrian dynamics and their implications for cellular automata models, Networks & Heterogeneous Media, 6(3), 545�560, 2010. [28] Shi, J.; Ren, A.; Chen, C. (2009); Agent-based evacuation model of large public buildings under �re conditions, Automation in Construction, 18(3), 338�347, 2009. [29] Tan, L.; Hu, M.; Lin, H. (2015); Agent-based simulation of building evacuation: Combin- ing human behavior with predictable spatial accessibility in a �re emergency, Information Sciences, 295, 53-66, 2015. [30] Wagner, N.; Agrawal, V. (2014); An agent-based simulation system for concert venue crowd evacuation modeling in the presence of a �re disaster, Expert Systems with Applications, 41(6), 2807-2815, 2014. [31] Yuan, W.; Tan, K.H. (2007); An evacuation model using cellular automata, Physica A: Statistical Mechanics and its Applications, 384(2), 549�566, 2007. [32] Zhang, G.; Liu, C.; Rong, H. (2010); Analyzing radar emitter signals with membrane algo- rithms, Mathematical and Computer Modelling, 52(11-12), 1997�2010, 2010. [33] Zhang, G.; Rong, H.; Cheng, J.; Qin, Y. (2014); A population-membrane-system-inspired evolutionary algorithm for distribution network recon�guration, J. Electron, 23(3), 437�441, 2014. [34] Zhang, X.; Li, J.; Zhang, L. (2016); A multi-objective membrane algorithm guided by the skin membrane, Nat. Comput, 15(4), 597�610, 2016. [35] Zhang, X.; Li, X.; Meha�ey, J., Hadjisophocleous G. (2017); A probability-based Monte Carlo life-risk analysis model for �re emergencies, Fire Safety Journal, 89, 51-62, 2017. [36] Zhang, X.; Wang, S.; Niu, Y.; Pan, L. (2011); Tissue P systems with cell separation: attacking the partition problem, Science China Information Sciences, 54(2), 293�304, 2011. [37] Zhang, G.; Gheorghe, M.; Pérez-Jiménez, M.J. (2017); Real-life Applications with Membrane Computing, Springer International Publishing, 2017.