Fuzzy controller and emotional model for evacuation of virtual crowd behaviors

Abstract

This paper presents the optimal path planning from an initial position to a final position of virtual crowd movement in an emergency evacuation. We have used hybrid architecture based on reinforced fuzzy inference system to control dynamic obstacles and A* algorithm for path finding which are widely used in artificial intelligence. The proposed contribution is to model the collision avoidance problem using a logic inference system. This fuzzy logic addresses cognitive behavior that introduces the uncertainty and imprecision during decision-making, for this the emotional model of personality (OCEAN) is integrated for BDI agents (beliefs, desires and intentions) and perception of agents in the environment. We will demonstrate the implemented approach by developing application with Java and Netlogo platform and tested with several simulation examples, that show how a crowd can be evacuated without collision and generate macroscopic emergence behavior by microscopic interaction. This application can be used as a framework to simulate real situations of complex systems (stadium evacuation, airports, hospitals).

Keywords

Fuzzy logic decision making emotional model perception belief collision avoidance panic

1. Introduction

Modeling and simulation have become an important issue in science and engineering. The modeling of complex systems (Fig. 1) is difficult at a higher level since they are nonlinear systems, more precisely the movement of crowd pedestrians witch concerns many fields of application such as civil engineering, town planning $\ldots$ etc. For example, in civil engineering, we are interested on characteristics of a pedestrian crowd to ensure safe evacuation in emergency situations. Traditional modeling approaches depend on the accuracy and exact description of the systems. The use of mathematical concepts such as differential equations is justified for well-defined systems. But when complexity increases, these concepts become less effective. The processing of complex systems such as crowd navigation requires the manipulation of vague, imprecise, uncertain, or both imprecise and uncertain information. In a natural way, the agent can formulate the behavior of the system with linguistic propositions rules for example: “If the speed is high and a collision is in a face then slow down and turned”: “If the speed is high and a collision is in a face then slow down and turned”.

The idea presented in this paper is based on fuzzy inference system to control dynamic obstacles and path finding which are widely used in artificial intelligence. For this the emotional model of personality (OCEAN) is integrated for BDI agents (beliefs, desires and intentions) [1] and perception of agents in the environment.

The rest of this paper is organized as follows: The second section describes related work. Section three provides the fuzzy inference system. Emotional model is presented in section four. Section five presents a problem modelling with different algorithms and fuzzy logic controller. The sixth section describes fuzzy controller and decision making. Section seven presents implementation and results of the model. Comparative study is presented in section eight. At the end, a conclusion and perspectives is presented.

2. Related work

We distinguish several work in the literature in the simultaion and modelisation of the crowd behaviors. [2] proposed to model the mechanism of human thought by an approximate reasoning based on linguistic variables. The author introduces introduced Fuzzy Set Theory in 1965, which is an interface between the linguistic and the digital worlds. More generally, the term of the fuzzy logic corresponds to all of developments resulting from the theory of the fuzzy subsets. [3] provides a useful modelling tool for many applications when ambiguity is present. For example, the traffic signal alternatives at a midblock crosswalk are controlled using the fuzzy logic method in [4, 5] and a collision avoidance system for autonomous vehicles using a fuzzy steering controller is proposed in [6].

The behavior of virtual humans composing a crowd is characterized by a certain imprecision and uncertainty of the movement of these virtual humans during the simulation of their models. Fuzzy logic is used in this work to formalize this imprecision. During the simulation a virtual human has a vision in the distance and the position of the static and dynamic obstacles. The virtual man generates imprecise movements when the vision is bad. The objective of this work is to propose a microscopic model of a complex system and more precisely the interactions between crowd individuals in an evacuation.

Several models of collision avoidance such as social force models in a continuous environment [7], rule-based models [8], cellular automata models in discrete time [9, 10], game theory based models, robotic and agent-based models in continuous time exist in the literature. In the robotic domain Ishikawa [11] has describe about a navigation method using fuzzy control. His purpose is to construct an expert knowledge for efficient and better piloting of autonomous mobile robot. He has used fuzzy control to select rules for tracing a path and avoiding obstacles, which was derived from sensor information by fuzzy logic control. An intelligent algorithm for mobile robot vehicle has been described by Ishikawa [11] using neural networks. They proposed a hybrid method that realises path planning and motion command. Kam et al. [12] have discussed about the fuzzy techniques of using sensors in robot navigation. They also discussed the problem of machine intelligence, including rules-based techniques and behavior-based algorithms. Wang [13] has used fuzzy logic for navigation of mobile robots. Tschichold-Gürman [14] has described about fuzzy rule-net for the mobile robots navigation; using the rule-net he has also shown the simulation result for mobile robot. Benreguieg et al. [15] have discussed about navigation of mobile robots using fuzzy logic. Beaufrere and Zeghloul [16, 17] have discussed about navigation planning through an unknown obstacle field for mobile robots. They used a two dimensional set to model the free local environment. Their approach is based on fuzzy reasoning and Gaussian function. Helbing et al. [18] proposes a model in which agents move in the calculated direction on the basis of the equation of generalized Newton force. This technique enables to realistically simulate the fundamental community of the effects such as the formation of routes and bottlenecks. Other mathematical models and special cases exist in the literature inspired by the work of Helbing. [19] proposes that the interactions are based on the concept floor field where individuals follow the virtual trace field by other individuals. [20, 21] propose an evacuation of a dance hall where the crowd is made up of several groups dynamically led by chiefs. The goal is to see the effect of the number of agents on the effectiveness of the evacuation in case there are a lot of leaders, the evacuation may take more time than if it is done without a guide, and this is what increases the risk of an imbalance towards chaos. [22] presents a path generation approach based on conflicts for the evacuation plan.

Abdelhak et al. [23] added emotions as cognitive characteristics of agents to the behavior of crowds. Lin et al. [24] recommends an adaptive distributed guiding protocol, which takes several factors such as dangerous areas, the distance to the exits, their width, and the degree of each location by considering the congestion. The goal is to help the moving objects in order to avoid a dangerous region. The simulation results show that the proposed protocol can guide mobile objects (people) for a fast exit. In [25] authors integrate beliefs, emotions and intentions into collective decision-making by modeling the behavior of the crowds of a real incident. Ni et al. [26] propose an agent-based social force model for advanced evacuation analysis of passenger ships and takes into account the interaction forces between the passengers, crew and obstacles.The funnel-shaped exits of the cabins can help the improved efficiency of the evacuation; this gives the ability to get around and over obstacles.; this gives the passenger the ability to get around and over obstacles. [27] presents a complete analysis of logic models of evacuation crowd behavior as well as the interactive effects of information (objective and subjective) and the study of the psychology. [28] propose a dynamic program to find the shortest path in a network. Its objective is to extend the shortest path in stochastic networks where travel times are defined as exponential. [29] present a general treatment of shortest path problems by dynamic programming in networks having normal probability distributions as arc lengths by extension the general shortest path in stochastic networks where travel times are defined as normal. [30] simulate the crowd evacuation phenomenon through the simulation of the artificial fish improved speed. The methodology used by [31] is the modification of the Dijkstra algorithm to find the most sure and short way. The first modification implies the restriction of the direction of the node, and the second modification blocked the nodes which are touched by the fire. In El-Hadidy and El-Bagoury [32] a new search model is proposed to find a three-dimensional randomly located target in a zone known; for an ideal search strategy that minimizes the time required to detect the target.

Several models have been developed to simulate the evacuation weather in the microscopic or macroscopic axis, but little work has been done on the path planning of a dense panicked crowd. [33] introduced a collision avoidance technique for a crowd robust navigation of individuals in an evacuation. his model is inspired by the Reynolds model.

Xue et al. [34] have integrated the fuzzy logic with the social force model and reproduced the dynamical features of pedestrian evacuation. Li et al. [35] presented a fuzzy logic-based approach for crowd simulation that extracts fuzzy rules from the realistic videos that can be considered a parameterized behavior model. [36] proposed a microscopic model of crowd evacuation defined on a continuous space and used a fuzzy logic technique to reproduce human reasoning. In [37] the authors proposed a genetic fuzzy system to model and simulate a pedestrian steering behavior in a built environment. In [38] the authors translate the forces modeled by SFM equations into desire and interaction effects described by linguistic expression rules and fuzzy sets. [39] proposed a fuzzy theory-based behavioral model to investigate evacuation dynamics in a cellular space. In [34] the authors propose a pedestrian model with fuzzy logic for generating the decision that represent the intrinsic control factors of decision-making.

We note that the fuzzy logic is very used in robotic navigation and agent models are widely used in the modeling of a crowd in the case of an emergency evacuation but with difficulty in finding a better path which is difficult in reality. For this reason, a collision avoidance technique for a robust crowd navigation of individuals is presented by proposing an algorithm which is based on reinforced fuzzy controller for avoidance of dynamic obstacle (crowd control) with the emotional model (we have incorporated the emotional model of personality (OCEAN) detailed in Sections 3 and 4) and different perceptions of agent in the environment (position of agent and angle of vision), we add A* pathfinding algorithm to avoid static obstacle.

Figure 1.

Complex system: a) Flight of birds; b) crowd evacuation; c) Panic movement in metro, Emergency evacuation.

3. Fuzzy inference system

Fuzzy logic can be seen as an extension of boolean logic; moreover, it makes it possible to treat linguistic variables whose values are words or expressions of the natural language. In this section, we present the basic properties of a fuzzy inference system [40] why its ideal for modeling and controlling a crowd movement for collision avoidance. Fuzzy logic is used to represent an imprecise value between true and false. The input variables of the regulator are transformed into linguistic variables with the definition of membership functions [41, 42].

A Fuzzy Inference System is designed to transform input data in output data with fuzzy logic [43] from the evaluation of a set of rules (Fig. 2). The input data are from the fuzzification process and the set of rules are defined by know-how of expert [44, 45, 46].

Figure 2.

Illustration of fuzzy inference system.

This fuzzy logic was introduced to address the problems faced by many complex systems (robotic, crowd behaviors, air traffic control, diagnostic support, $\ldots$ ) which have to deal with information that is imperfect (uncertainties, imprecisions). In contrast to boolean logic, fuzzy logic allows a condition to be in a different state than true or false, (there are degrees in checking a condition). The Fuzzy Inference System consists of three stages:

•

FUZZIFICATION: which consists in characterizing the linguistic variables used in the system. It is therefore a transformation of the real inputs into a fuzzy part defined on a representation space linked to the input. Fuzzy logic is used to representonverts the crisp input to a linguistic variable using the membership functions stored in the fuzzy knowledge base.

•

INFERENCE: consist of using the inference engine, which is a mechanism for condensing the information of a system through a set of rules defined for the representation of any problem. Each rule delivers a partial conclusion which is then aggregated to the other rules to provide a final conclusion. Using If-Then-Else, fuzzy rules controller converts the input to the fuzzy output. The rules constitute the fuzzy inference system; these rules are detailed in a more formal framework in Section 6.

•

DEFUZZIFICATION: Convert the fuzzy output of the inference engine to crisp using membership functions analogous to the ones used by the fuzzifier (aggregate the qualified consequents to produce a crisp output).

4. Emotional model

Emotion is an integral part of the decision process, hence the importance of its incorporation in the behavioral process of this model. Each individual in the crowd is modeled by a physiological cognitive agent as personality, goals to be accomplished and existing social force relations with other agents.When an agent acquires new information (by partial perceptions of the environment or through messages sent by other agents), it automatically updates its basic beliefs. The plans identify strategies that the agent can follow. We used five factors of personality vector of OCEAN model Costa [1]:

1)
(Extrovert, Introvert)
2)
(agreeableness, unagreeableness)
3)
(on-scientiousness, unconscientiousness)
4)
(Neuroticism, Emotional stability)
5)
(Openness to Experience, Closed to experience)

these factors range from [ $-$ 100, 100] because this factors are compatible with human personality in the crowd evacuation and describe the personality in the most complete way possible. For emotions, the emotional theory OCC defined by Ortony and Clore [47] and Ekman [48].

Russel and Mehrabian [49] find the difficulty of representing both emotions in a small two-dimensional space. Fear and anger are relatively close in a space based solely on the criteria of activation and pleasure. They propose a three-dimensional model in which emotions are classified according to the following bipolar dimensions: appreciability/no-appreciability ( $+$ P/ $-$ P), activation/deactivation ( $+$ A/ $-$ A) and dominance / no-dominance ( $+$ D/ $-$ D). Russel and Mehrabian classify 151 emotions in this space and presents them in the PAD space; remarking the presence of the six basic emotions of the Ekman model: joy, anger, surprise, fear, sadness and disgust (Fig. 3).

Figure 3.
Three-dimensional PAD space model proposed by Russel and Mehrabian.

Figure 4.
Proposed model.

Every moment the agent feels a mood that reflects its emotional state over time. The decision taken by the agent to choose the optimal path based on its partial perception of the environment and the spread of panic by the neighboring agents. The agent will replace the initial destination with a new one. In general, the decision process encompasses all activities between the time a stimulus for action is perceived, and when the commitment to action is performed. The agent perceives its environment (a panic or a dense crowd danger in its path), consults its knowledge base at the Quadtrees cells, thus the choice of the route is taken in a list of exits stored in an order of the closest distance at each node of the Quadtree decomposition. When this factor is above the threshold, heuristic is changed without forgetting the comfort distance.

Table 1
Interval of RIC space values

Emotion Relavance Involvement Control

Anger [ $-$ 1, $-$ 0.5] [ $-$ 1, 1] 1

Fear [ $-$ 1, $-$ 0.5] [ $-$ 1, 1] $-$ 1

Sadness [ $-$ 0.5, $-$ 0.01] [ $-$ 1, 1] $-$ 1,1

Neutral [ $-$ 0.01, 0.01] [ $-$ 1, 1] $-$ 1,1

Surprise [0.01, 0.5] [ $-$ 1, 1] $-$ 1,1

Joy [0.5, 1] [ $-$ 1, 1] $-$ 1,1

Panic [ $-$ 1, $-$ 0.8] [ $-$ 1, 0.5] $-$ 1

Abdelhak et al. [23] added three-dimensional RIC space, each attribute of the emotional vector belongs to a value range. The relevance attribute ( $+$ R/ $-$ R) over the interval [ $-$ 1, 1] indicating the intensity and the agreeability of a disturbance. the implication attributes ( $+$ I/ $-$ I) on the interval [ $-$ 1, 1] describing the degree of involvement of a disturbance in the variation of the individual’s goals. She assigned two values for the control attribute ( $+$ C/ $-$ C), the value 1 to designate an adaptation to the new situation and $-$ 1 otherwise. Thereafter, for each emotion of the model will be identified by a value interval in the three-dimensional space (Table 1). The triggered emotion is thus determined according to the values of the attributes of the emotional vector and their correspondences in the three-dimensional space.
5. The proposed model

Emotion	Relavance	Involvement	Control
Anger	[ $-$ 1, $-$ 0.5]	[ $-$ 1, 1]	1
Fear	[ $-$ 1, $-$ 0.5]	[ $-$ 1, 1]	$-$ 1
Sadness	[ $-$ 0.5, $-$ 0.01]	[ $-$ 1, 1]	$-$ 1,1
Neutral	[ $-$ 0.01, 0.01]	[ $-$ 1, 1]	$-$ 1,1
Surprise	[0.01, 0.5] [ $-$ 1, 1]	$-$ 1,1
Joy	[0.5, 1]	[ $-$ 1, 1]	$-$ 1,1
Panic	[ $-$ 1, $-$ 0.8]	[ $-$ 1, 0.5]	$-$ 1

This section describes modelisation and simulation of the complex system of autonomous agents for collision avoidance of virtual crowd behaviors to provide emergence phenomena. The Fig. 4 illustrates the modeling and simulation of proposed model.

5.1 Modelization

In the modeling part we observe:

•
Modeling of the environment by a quadtree decomposition and local perception of the environment for each agent BDI (position, the distance from itself to other agents, speed, angle, $\ldots$ ) (Algorithm 2).
•
The action performed by the agent to avoid any type of collision (path planning and decision making): in this part, we see the contribution by the A* algorithm for path finding to avoid static obstacles (Algorithm 4) and Fuzzy controller for decision making (Algorithm 5). For input variable of fuzzy logic we introduce the five factors of personality vector of OCEAN model [1] to represent heterogeneous pedestrians with various characteristics, such as openness, conscientiousness, extraversion, agreeableness, and neuroticism), these factors range from [ $-$ 100, 100]. Perceptions of agent are added which are distance $d$ , angle $\alpha$ , distance $d g$ and angle $\theta$ (Section 6.1.1). The output variables are speed, danger degree, MaxNeighbor and direction (Section 6.2.2) which represents the reality of the crowd movement (Algorithm 5).

5.2 Simulation

For simulation part we note:

•
The simulation is illustrated by Netlogo 5.2.1 platform. Which is very well adapted to the modeling of complex systems to explore the emergence due to interactions between agents. Other modules are implemented by the java language, such as fuzyy logic and A* algorithm.

Figure 5.
Agent planning in part of his path.

In order to eliminate any risk of collision with obstacles, we use the information obtained by the agent in perceiving the environment which is represented by the circle within (Fig. 5):

•
Position ( $X, Y$ ): is the spatial location in $X$ , $Y$ coordinates of the agent in the virtual space.
•
Comfort distance ( $d$ ): is the minimum distance between agents and obstacles to avoid collision.
•
Distance goal ( $d g$ ): is the minimum distance between the agent and goal.
•
Comfort zone (COD): it covers a comfort distance $d$ .
•
Risk zone (RID): it covers a $d/2$ .
•
Radius of vision ( $\alpha$ ): Custom domain of vision.
•
Angle of deviation ( $\theta$ ): the agent is steering with angle $\theta$ to the path, it represents the angle between the position of the agent and the goal.
•
Radius of comfort $R=(2d\textit{tang}(\alpha/2)$
•
Speed ( $\vec{v}$ ): the speed varies with the state of health and mobility, ranging from zero (when the health or mobility $=$ 0) at 2.5 m/s (when running in panic).
•
Desired velocity( $\vec{v_{d}}$ ) is the sum of steering with velocity.

5.3 The algorithms

In this section, we describe the different algorithms of the proposed approach:

5.3.1 Algorithm 1

Is called “Crowd path planning”, is the main one of our approach, it uses four other algorithms which are:

•
Quadtree modeling() for environment modeling (Algorithm 2).
•
Path(): to find a fixed obstacle path (Algorithm 4).
•
Collision avoidance() Is the fuzzy inference system in order to avoid any type of collision, a collision factor is added to his heuristic in A* algorithm (Algorithm 6).
•
update() for update and change of position and the speed of the agent for going at the exit (Algorithm 3).

[h] Initialisation:maxspeed, maxforce, $d$ , $\alpha$ , velocity[], acceleration[], location[], static obstacle; Quadtree modelling(); //Algorithm 2 all agent Agent(Path); // moving with A* Algorithm 4 Agent(Collision avoidance); //Algorithm 5; Agent(Update); //change position, direction and acceleration Algorithm 3. evacuation of all agents

Crowd path planning
5.3.2 Algorithm 2

Is named Split and Merge, the idea is to produce an initial partition into small regions (Split) by recursive subdivision of the environment in the regions (nodes) of identical sizes to a convergence criterion of homogeneity, which will then grow by regrouping (Merge). Each region is associated with a vertex of the graph, the edges connect the vertices corresponding to two touching regions. This allows us to build an adjacency graph. The merging party consists of grouping the neighboring vertices of the graph with the same homogeneity characteristics (color or shape). We opted for the split in Quadtree which shows the square regions as it well modelled the two-dimensional space and allows an easy navigation between the sub regions (Fig. 6). The only inconvenience of this structure is that it does not take into account any notion of height, so a passage having two dimensions and a half (2D1/2) can solve the problem. For three-dimensional spaces, an Octree (tree-like data structure where each node can have up to eight sons) is ideal for the subdivision.

[H]

//Initialization; Input: sheet $=$ image to be decomposed C= homogeneity criterion of a sheet; // colors, shapes i $=$ 1 to true // going down division

starting from the top !C // not quite homogeneous sheet Subdivide a sheet into 4 sheets; division into 4 square regions; Vect[] $=$ i ; // save the decomposition levels for each sheet levels for each sheet

// merger and creation of the graph

sheet of Quadtree Create node; // creation of nodes in the graph for all sheets Create arc(node fils, node parent);//same level for Vect[] Create arc(node fils, node fils) ; // different level Vect[] Dellete arc; // removal of ars to the decomposed cells: merger

Quadtree modelling

5.3.3 Algorithm 3

Its update algorithm when the agent changes the position, direction and the speed (Output of the fuzzy controller).

velocity.add(acceleration); velocity.limit(maxspeed); location.add(velocity); acceleration.mult(0.1); update()

5.3.4 Algorithm 4

Is named Path, we have using A* algorithm for path finding [50] is an algorithm search of artificial intelligence that performs a heuristic search [51] in an area to find an optimal path from the initial node to the final node. This search algorithm is based on a heuristic evaluation between two nodes in order to eliminate many paths of high costs. To find a path from one point to another, we must begin by heading to the destination. It is precisely this idea that the A* algorithm uses. The idea is very simple: at each iteration A* will try to get closer to the destination, it will therefore focus on possibilities directly closer to the destination, putting aside all others. All [b]

//Initialization;

Current node = Starting node each element $s$ of the list of neighbors $s$ .state $=$ free and $s\not\in$ closed list $F(s)=G(s)+H(s)$ ; $s$ $\not\in$ open list Add the node to the open list; // the nodes to explored Put the current node as the parent of the node $s$ ; the new cost is better Update the open list; Update the parent of node; the open list is empty No solution; current node $=$ the optimal node in the open list; Remove the optimal node from the open list; Place it in the closed list; // final path current node $=$ destination node Path() possibilities, not allowing to get closer to the destination are set aside, but not suppressed. They are simply put in a list of possibilities to explore (open list) if ever the solution currently explored is poor. Indeed, we cannot know in advance whether a path will lead or be shorter. Enough for this path lead to a dead end that the solution becomes unusable. The algorithm will therefore first move towards more direct paths. And if these paths fail or prove wrong later, it will examine solutions being put aside. This is going back to review the solutions that we set aside the algorithm ensures that we always find a solution (if it exists, of course). What makes this algorithm search complete, fast and optimal. Several distances can be used like the Manhattan distance, diagonal or Euclidean.

5.3.5 Algorithm 5

Is named Collision avoidance, the idea is to presents a fuzzy inference system for avoiding any type of collision, it’s based of input and output variables which represent an imprecise value between true and false when the complexity increases with imprecise and uncertain information.

Figure 6.

a) environment subdivision by the Quadtree method, the homogeneous regions have the same color, b) construction of the adjacency graph.

For the congestion factor $\alpha$ at the Algorithm 5, it is calculated as follows: $\alpha=$ number of individuals in a hazardous area/(maximum number of people being able to occupy the comfort and dangerous zone).

[H]

//Initialization;

$\alpha=$ congestion factor; // to each node ( $\alpha\geqslant$ threshold) or (next node $=$ agent) collision avoidance; calculate (A* Algorithm 4) with $H(c)=H(c)+\alpha$ calculate (A* Algorithm 4) // advance the way is free there is danger in the way // input of fuzzy logic output of fuzzy logic; //Decision making Agent(Path); Collision avoidance

6. Fuzzy controller and decision making

Fuzzy Logic [52] is ideal for modeling and controlling a crowd movement in a large scale for collision and to treat uncertain and imprecise information. This fuzzy is used to represent an imprecise value between true and false. The input variables of the regulator are transformed into linguistic variables with the definition of membership functions. Thus, this operation consists of determining the degree to a value to a fuzzy set as the work of [41].

6.1 Inputs and outputs of a fuzzy controller

In this paper, we chose the OCEAN personality factors in the emotional model. Figure 7 shows the fuzzy set of the environment.

Figure 7.

The controler input variables: a) five factors of OCEAN model; b) distance d; c) distance dg; d) angle $\alpha$ ; e) angle $\theta$ .

6.1.1 Inputs variables

The input variables of the fuzzy rules for collision avoidance are:

1.
OCEAN personality factors
2.
distances $d$
3.
distances $d g$
4.
Angle $\alpha$
5.
Angle $\theta$

The OCEAN personality factors (Section 4) with value between $-$ 100 and 100, which are decomposed into three fuzzy sets:

•
Negative
•
Neutral
•
Positive

The perceptions of agent are:

1)
Distance $d$
2)
Angle $\alpha$

which are respectively decomposed into three and five fuzzy sets. We observe three distances for $d$ with a value between zero and $\infty$

•
(ZER: zero distance)
•
(COD: comfort distance)
•
(RID:risk distance)

and five angles of vision $\alpha$

•
(SMV: small vision)
•
(GRV: Great vision)
•
(ZERO: zero vision)
•
(NSMV: negatives small vision)
•
(NGRV: negative great vision)

In addition, considering the relation between the agent and the goal the distance information between the agent and the goal $d g$ and an angle between the targets $\theta$ are added into state space.

We observe two distances for $d g$

•
(N: near)
•
(F: far)

and three angle for $\theta$

•
(Nega: Negative)
•
(Z:Zero)
•
(Pos:Positive)

6.1.2 Outputs variables

The output variables are:

1.
Speed
2.
Danger degree
3.
MaxNeighbor
4.
Direction

witch are respectively decomposed into three fuzzy sets for speed with value between one and 2,5:

•
Slow
•
Average
•
High

Three fuzzy sets for danger deviation witch has a value between zero and five:

•
Low
•
Smal
•
High

Three fuzzy sets for MaxNeighbor with value between 1 and 100:

•
Smal
•
Medium
•
Large

and three fuzzy sets for direction (Fig. 8):

•
Turn
•
Stop
•
Run.

Figure 8.
The controler output variables: a) speed; b) danger degree; c) max neighbor; d) direction.

6.2 Fuzzy rules

The fuzzy rules are derived from toolbox of Matlab simulink exactly with the Fuzzy Logic of Matlab. This toolbox added the required input and output components in Simulink as defined in Section 6 with their fuzzy sets. The input variables of the controller are converted to linguistic variables of membership function, the fuzzy rules are obtained by combining all the possibilities between the input variables and the desired output variables. The fuzzy rules are based on empirically real-life experiences in the case of evacuate crowd and avoid of collisions between individuals.

The linguistic rules can be for example:

•
R1: If (Distance d is RID) and (Anglealpha is SMV) and (Distance dg is Far) and (Angletheta is Zero) then (Speed is Average) (Dangerdeviation is Low)
•
R2: If (Distance d is RID) and (Anglealpha is zero) and (Distance dg is Near) and (Angletheta is Zero) then (Speed is Average) (Dangerdeviation is Low)
•
R3: If (Distance d is RID) and (Anglealpha is NSMV) and (Distance dg is Far) and (Angletheta is Zero) then (Speed is Average) (Dangerdeviation is Low)
•
R4: If (Distance d is RID) and (Anglealpha is SMV) and (Distance dg is Far) and (Angletheta is Pos) then (Speed is Average) (Dangerdeviation is Low)
•
R5: If (Distance d is COD) and (Anglealpha is NGRV) and (Distance dg is Far) and (Angletheta is Neg) then (Speed is high) (Dangerdeviation is Small)
•
R6: If (Distance d is COD) and (Anglealpha is GRV) and (Distance dg is Far) and (Angletheta is Pos) then (Speed is high) (Dangerdeviation is Small)
•
$\ldots\ldots$
•
$\ldots\ldots$
•
R10: If (Openness is Positive) and (Conscientiousness is Neutral) and (Extraversion is Positive) and (Agreeableness is Neagative) and (Neuroticism is Negative) then (Speed is Slow) (Danger degree is Medium) (MaxNeighbor is Medium)
•
R11: If (Openness is Positive) and (Conscientiousness is Positive) and (Extraversion is Positive) and (Agreeableness is Neagative) and (Neuroticism is Negative) then (Speed is Average)(Danger degree is Smal)(MaxNeighbor is Large)
•
R12: If (Openness is Negative) and (Conscientiousness is Positive) and (Extraversion is Positive) and (Agreeableness is Neagative) and (Neuroticism is Negative) then (Speed is Average)(Danger degree is Medium) (MaxNeighbor is Medium)
•
$\ldots\ldots$
•
$\ldots\ldots$
•
R41: If (Openness is Positive) and (Conscientiousness is Positive) and (Extraversion is Positive) and (Agreeableness is Positive) and (Neuroticism is Positive) and (Distance d is COD) and (Anglealpha is GMV) and (Distance dg is Far) and (Angletheta is Neg) then (Speed is High) (Danger degree is Small) (MaxNeighbor is Small)
•
R42: If (Openness is Positive) and (Conscientiousness is Positive) and (Extraversion is Negative) and (Agreeableness is Positive) and (Neuroticism is Positive) and (Distance d is RID) and (Anglealpha is ZERO) and (Distance dg is Near) and (Angletheta is Zero) then (Speed is Slow) (Danger degree is High) (MaxNeighbor is Medium)
•
$\ldots\ldots$
•
$\ldots\ldots$

Figure 9.
Surface viewer control: a) Con-scientiousness, Openness, danger-degree; b) distance, angle $\alpha$ , danger-deviation;s c) Openness, Con-scientiousness, Speed.

After that, we use an aggregation centre-of-gravity function for velocity. To obtain the real output defuzzified velocity, we take the membership values ( $v$ ) for each fuzzy output set, multiply each by its set centre value ( $v_{i}$ ), and divide this by the sum of all of the centre values illustrated in Fig. 9.

$\displaystyle V_{\textit{defuzz}}=\frac{\sum_{i=1}^{m}V*V_{i}}{\sum_{i=1}^{m}V% _{i}}$

with $m$ which is the number of rules and $V$ , the control variable. Similarly, the real output defuzzified Deviation is obtained by centre-of-gravity function. The surface control in Fig. 9 represents a series of rules if - then. The inference is based on min or max operations to make the rule inference and max operator for the aggregation of rules.
7. Result and simulation

We implemented the model with the Netlogo 5.2.1 platform (Fig. 13). It is very well adapted to modelling a complex systems, to explore the emergence due to interactions between agents and its flexibility to change the direction of an agent to right or left by a selected angle $\beta$ with a simple Netlogo command ‘ $r t$ ” or ‘ $l t$ ”. We have conducted experiments by varying several factors such as the number of agents, emotional behavior Ocean factors, speed $\vec{v}$ , distance ( $d$ , $d g$ ) and angle vision ( $\alpha$ , $\theta$ ) of agents.

7.1 Scenario 1

The first simulation (Fig. 10a) represents agents that are distributed randomly; Opennes (blue), Conscientiousness (green), Extraversion (yellow), Agreeableness (red), Neuroticism (black) with initial speed of 1.5 m/s, a radius of 5 m and a vision angle of 180 ${}^{\circ}$ . According to the first experiment, we noticed the appearance of emergent behaviors such as paths and groups formation from simple interactions between individuals (Fig. 10b).

Figure 10.

a) Evacuation starting, b) group formation, c) end of evacuation without collision.

In this scenario the rules number 5 and 42 are applied (Section 6.2) with high Speed and small Danger degree for output value (Fig. 10c).

7.2 Scenario 2

The second simulation shows a 3D view of crowd evacuation. Its studies the influence of the speed, the radius and the angle of vision on the path of 50 individuals distributed randomly with five factors of an ocean model (10 panicked agreeableness) and vision angle of 360 ${}^{\circ}$ . We noticed the propagation of panicked agents and appearance of waiting queues with emerging behaviors (Fig. 11).

Figure 11.

Line formation near the exit with spread of panic in 3D view.

In this scenario the rules number 10, 11 and 12 are applied (Section 6.2).

7.3 Scenario 3

Figure 12 shows the trajectories taken by the different agents in an exit with the three factors of ocean model. It represents the pedestrians with positive characteristic Conscientiousness (green), Neuroticism(black) and Agreeableness (red), traits. The green agent takes a fairly direct trajectory and moves in an orderly way behind the other agents (Fig. 12a). The black agent also moves quickly, but takes a tortuous route when congestion occurs near the exit (Fig. 12b). Neuroticism trait can clearly be distinguished, The agent with a positive Neuroticism trait is easily deflected by the crowd. The red agent moves quickly and often try to weave through others in the crowd (Fig. 12c). In this scenario the rules number 4 and 41 is applied, the input parameters variables are OCEAN value $=$ 80, $d=$ 1.6, $dg=$ 21, $\alpha=$ GV, $\theta=$ pos.

The output value are $v=$ 1.6, danger degree $=$ small, (Section 6.2).

Figure 12.

Motion trajectories of agents with three positive personality factors, the traits are a) Conscientiousness, b) Neuroticism and c) Agreeableness.

7.4 Scenario 4

This simulation (Fig. 13) shows the performance of the Algorithm 1 Crowd path planning. In green is represented the optimal path found for all the 30 agents distributed randomly. Each individual goes to the evacuation point following the optimal path. During execution, the individuals avoid collisions and shove through the decision making model (Sections 5 and 6).

Figure 13.

Crowd path planning.

7.5 Scenario 5

This experiment illustrates the decision making by individuals of a crowd of 72 agents distributed as follow: 40 Opennes (not-panicked), 20 Conscientiousness (normal) and 12 Neuroticism (panicked) who are randomly distributed in three groups. We note that at the moment $t=$ 20 the spread of panic among people and the crowd begins to move towards the evacuation points, at the moment $t=$ 29 there is a stampede at ‘Exit’ due to the panic behavior. Not-panicked individuals consult their basic knowledge at the nodes and choose the exits with less danger in their list of goals and start to move to the second Exit named SOS (change the direction with an output of the fuzzy controller). This decision making in complex systems allows the finding of the optimal route and avoids the chaos (Fig. 14).

Figure 14.

Decision making.

In this scenario the rules number 1, 2, 3, 4, 10, 11 and 12 are applied.

Figure 15.

Time execution of crowd evacuation.

Figure 15 illustrates the relation between the density of the crowd and the evacuation time of simulation scene, where the role of the collision avoidance module is clearly seen when the crowd is dense. The green line indicates that the proportion of positive Conscientiousness agents in the crowd has little effect on the total time of evacuation. The black line shows that a greater proportion of Neuroticism agents lead to a significant increase in evacuation time.

Table 2

validation of the evacuation time

Comparison model	Scenario 1	Scenario 2	Scenario 3
Evacuation time according to Togawa (s)	19.66	28.4	23.7
Evacuation time of the proposed model (s)	14.20	20.8	18.6

Table 3

A Comparative Table between proposed approach and some research work on evacuation crowd planning in a complex environment

Author/year	Environmental modeling	Heterogeneity	Collision avoidance	The results
Haifa et al. 2012	Cellular automata	Heterogeneous	Reynolds model	Panic propagation
Mauro et al. 2014	Not discussed	Heterogeneous	Microscopic model	Panic propagation
			with fuzzy logic
Sahil et al. 2015	cell grid	Heterogeneous	Density filters	Group formation
Altieres et al. 2016	Not discussed	Not discussed	Social Force	Lane formation
Libi et al. 2016	cellular space	Not discussed	Fuzzy theory	Emergence phenomena of evacuation
El-Hadidy et al. 2017	Regular grid	Not discussed	Rules base interaction	Minimises time to detect target
Zhuxin et al. 2017	Virtual environment	Heterogeneous	RVO2 model	Influence of personalities
				in the crowd phenomena
Chennoufi et al. 2018	Quad-tree	Heterogeneous	Newton force	Appearance of emergent
				behaviours
Hong et al. 2018	Agent modeling	Not discussed	social force model	resolves the slow speed problem
			and a leader of group	behaviours
zakaria et al. 2019	Virtual	Heterogeneous	fuzzy logic	Influence of emotions in the evacuation
Our work	Quad-tree decomposition	Heterogeneous	Fuzzy controller rules	- Generates pedestrian trajectories
				- Appearance of emergent behaviours

7.6 Validation

Evaluating the simulation results for evacuation of virtual crowd behaviors influenced by human personality is a challenge. To validate the results and test its durability in real time. We compared the maximum evacuation time provided by the Togawa Mathematical Equation with results simulations, we have achieved good results (Table 2).

The Togawa equation is defined as follows [45]:

$\displaystyle\textit{Te}=\textit{Na}/(B+N)+\textit{Ks}/V$

•
Te: is the approximative time for evacuation (s).
•
Na: is the total number of agents in the model (people).
•
$B$ : is the width of the exit(m).
•
$N$ : is the narrowest flow capacity of personal passage/ms time unit.
•
Ks: is the travel distance of the agent who was evacuated from the room (m).
•
$V$ : is to determine the speed of agents (m/s).

For all our experiments, we consider the following values:

•
$\textit{Na}=$ The Number of people detailed in each scenario, $B=$ 0.2 m, $N=$ 3,
•
$\textit{Ks}=$ 0.6 m to 7 m
•
$V$ : varies according to health status and mobility, starting from 0 to 1.5 m/s (in normal situation) and 2.5 m /s (in case of panic)

7.7 Temporal complexity

It is very difficult to find the best path in a complex system because of the different interactions between individuals, spatial and temporal constraints.

The proposed model is programmed in Java and implemented with the Netlogo 5.2.1 platform (Fig. 13). It is free and very well adapted to modeling complex systems. Different scenarios were tested by modifying several factors such as number of agents, behavior and other parameters (Section 6). The fuzzy controller model is an ideal way to model and control crowd movement in the large-scale.

When the crowd increases, the algorithm is always effective, converges widely because it has a logarithmic temporal complexity.

The Crowd path planning algorithm use the basic algorithm A* to calculate the path to the exit by avoiding fixed obstacles and the fuzzy controller to avoid dynamic obstacle.

If cost of additions and comparisons are $O(1)$ complexity, the complexity of A* is:

$\displaystyle O(n+\textit{mlog(n)}).$

For a crowd of agents we have a temporal complexity for dynamic collision avoidance in the worst case scenario given by the following approximation:

$\displaystyle O(n+1)=((O(1)+O(1)+O(1)+O(1)+O(1)+O(1)+O(n+\textit{mlog(n)}))*k)% =((1+1+1+1+1+1+O(n+\textit{mlog(n)}))*k)=((6+O(n+\textit{mlog(n)}))*k)=6*k+k*O% (n+\textit{mlog(n)})$

8. Comparative study

The study of complex systems is very difficult, especially when it comes to crowd behavior in an evacuation. Many studies on the simulation of behaviors exist, but a few exist on agent-based planning with a fuzzy logic controller. We note that the fuzzy logic is very used in robotic navigation, but not in crowd navigation. Agent models are widely used in the modeling of a crowd in the case of an emergency evacuation but with difficulty in finding a better path which is difficult in reality. Our collision avoidance technique for a robust crowd evacuation, which is modelled by agents and based on fuzzy controller is compared with other research works.

Table 3 shows a comparison between proposed approach and different recent works on crowd planning according to four criteria for describing defined models as follows:

1)
Environmental modelling: represented in graph, grid, or tree.
2)
Heterogeneity: individuals may be homogeneous or heterogeneous entities (age, physiology $\ldots$ ).
3)
Collision Avoidance: primary criterion for multi-agents planning.
4)
The results: crowd evacuation models reproduce many phenomena observed in a wide reality.

9. Conclusion

In this paper, we propose a new approach of a collision avoidance model of autonomous agents and behavioral interaction in complex systems. The model contains modeling and simulation of autonomous agents in evacuations based on several algorithms such as Quadtree for modeling the virtual environment, the A* for multi agents planning and fuzzy inference system for collision avoidance. We have added physiological and emotional factors of BDI agents, which are successfully implemented. The OCEAN personality model is introduced to model the psychological characteristics of a pedestrian, and it can generate the different decision preferences that represent the intrinsic control factors of decision-making. The fuzzy relationships between personality traits and decision preferences are determined by a fuzzy inference system. This architecture allowed the appearance of phenomena without the system tipping into chaos. Hoping we gave more in the field of crowd planning in the behavioral aspect.

We can also consider some improvements so that this model can be considered as a decision support tool in crisis situations of complex system. In the near future,we reinforce the fuzzy rules by emotions inspired with the video of real evacuation exercises of our institution to avoid collisions and reduce evacuation time. This model has various potential extensions to be explored; it can be used as a framework to simulate real situations. We are interested in the spatial part of the environment and thinking a new model of collision learning in order to manage new situations with GPU programming and integrate a real environment using geographic map GIS (geographic information system).

References

Costa

Paul

. Toward a new generation of personality theories: Theoretical contexts for the five-factor model. In The five-factor model of personality: Theoretical perspectives, 1996; 51.

Zadeh

. Fuzzy sets as a basis for a theory of possibility. Fuzzy sets and systems.1999; 100(1): 9-34.

Zadeh

. A fuzzy-algorithmic approach to the definition of complex or imprecise concepts. In: Systems Theory in the Social Sciences. Springer; 1976, pp. 202-282.

Noyce

. Pedestrian crosswalks at midblock locations: Fuzzy logic solution to existing signal operations. Transportation Research Record: Journal of the Transportation Research Board.2009; (2140): 63-78.

Niittymaki

Kikuchi

. Application of fuzzy logic to the control of a pedestrian crossing signal. Transportation Research Record: Journal of the Transportation Research Board.1998; (1651): 30-38.

Llorca

Milanés

Alonso

Gavilán

Daza

Pérez

, et al. Autonomous pedestrian collision avoidance using a fuzzy steering controller. IEEE Transactions on Intelligent Transportation Systems.2011; 12(2): 390-401.

Helbing

Farkas

Vicsek

. Simulating dynamical features of escape panic. Nature.2000; 407(6803): 487.

Reynolds

. Flocks, herds and schools: A distributed behavioral model. ACM SIGGRAPH computer graphics. vol. 21, ACM, 1987, pp. 25-34.

Chenney

. Flow tiles. In: Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation. Eurographics Association, 2004. pp. 233-242.

10.

Suwais

. Assessing the Utilization of Automata in Representing Players’ Behaviors in Game Theory. International Journal of Ambient Computing and Intelligence (IJACI).2014; 6(2): 1-14.

11.

Ishikawa

. A method of indoor mobile robot navigation by using fuzzy control. In: Intelligent Robots and Systems’ 91. Intelligence for Mechanical Systems, Proceedings IROS’91. IEEE/RSJ International Workshop on. IEEE, 1991. pp. 1013-1018.

12.

Kam

Zhu

Kalata

. Sensor fusion for mobile robot navigation. Proceedings of the IEEE.1997; 85(1): 108-119.

13.

Wang

. Modeling and control of hierarchical systems with fuzzy systems. Automatica.1997; 33(6): 1041-1053.

14.

Tschichold-Gürman

. The neural network model RuleNet and its application to mobile robot navigation. Fuzzy Sets and Systems.1997; 85(2): 287-303.

15.

Benreguieg

Hoppenot

Maaref

Colle

Barret

. Fuzzy navigation strategy: Application to two distinct autonomous mobile robots. Robotica.1997; 15(6): 609-615.

16.

Beaufrere

Zeghloul

. Navigation method for a mobile robot using a fuzzy based method-simulation and experimental aspects. IASTED 1811 WEST KATELLA AVE# 101, ANAHEIM, CA 92804, 1995.

17.

Beaufrere

Zeghloul

. A mobile robot navigation method using a fuzzy logic approach. Robotica.1995; 13(5): 437-448.

18.

Helbing

Farkas

Molnar

Vicsek

. Simulation of pedestrian crowds in normal and evacuation situations. Pedestrian and evacuation dynamics.2002; 21(2): 21-58.

19.

Schadschneider

. Cellular automaton approach to pedestrian dynamics-theory. arXiv preprint cond-mat/0112117, 2001.

20.

Shao

Terzopoulos

. Autonomous pedestrians. Graphical Models.2007; 69(5-6): 246-274.

21.

Gao

. Simulating crowd evacuation with a leader-follower model. IJCSES.2006; 1(4): 249-252.

22.

Pillac

Van Hentenryck

Even

. A conflict-based path-generation heuristic for evacuation planning. Transportation Research Part B: Methodological.2016; 83: 136-150.

23.

Abdelhak

Ayesh

Olivier

. Cognitive emotional based architecture for crowd simulation. Journal of Intelligent Computing.2012; 3(2): 55-66.

24.

Lin

Chen

. An adaptive guiding protocol for crowd evacuation based on wireless sensor networks. In: Vehicular Technology Conference (VTC Spring), 2013 IEEE 77th. IEEE, 2013. pp. 1-5.

25.

Bosse

Hoogendoorn

Klein

Treur

Van Der Wal

Van Wissen

. Modelling collective decision making in groups and crowds: Integrating social contagion and interacting emotions, beliefs and intentions. Autonomous Agents and Multi-Agent Systems.2013; 27(1): 52-84.

26.

Zhang

. An evacuation model for passenger ships that includes the influence of obstacles in cabins. Mathematical Problems in Engineering.2017.

27.

Yang

Chen

Pan

. A review of behavior mechanisms and crowd evacuation animation in emergency exercises. Journal of Zhejiang University Science C.2013; 14(7): 477-485.

28.

Olya

. Finding shortest path in a combined exponential–gamma probability distribution arc length. International Journal of Operational Research.2014; 21(1): 25-37.

29.

Olya

. Applying Dijkstra’s algorithm for general shortest path problem with normal probability distribution arc length. International Journal of Operational Research.2014; 21(2): 143-154.

30.

Zhang

Liu

Wang

Liu

. AFSA Based Path Planning Method for Crowd Evacuation. Journal of Information & Computational Science.2014; 11(11): 3815-3823.

31.

Samah

Hussin

Basari

ASH

. Modification of Dijkstra’s algorithm for safest and shortest path during emergency evacuation. Applied Mathematical Sciences.2015; 9(31): 1531-1541.

32.

El-Hadidy

MAA

El-Bagoury

AAAH

. Optimal search strategy for a three-dimensional randomly located target. International Journal of Operational Research.2017; 29(1): 115-126.

33.

Chennoufi

Bendella

Bouzid

. Multi-agent simulation collision avoidance of complex system: application to evacuation crowd behavior. International Journal of Ambient Computing and Intelligence (IJACI).2018; 9(1): 43-59.

34.

Xue

Dong

Fan

Jin

Jian

Liu

. Fuzzy Logic-based model that incorporates personality traits for heterogeneous pedestrians. Symmetry.2017; 9(10): 239.

35.

Liang

. A fuzzy logic based approach for crowd simulation. In: Advances in electronic commerce, web application and communication. Springer, 2012, pp. 29-35.

36.

Dell’Orco

Marinelli

Ottomanelli

. Simulation of crowd dynamics in panic situations using a fuzzy logic-based behavioural model. In: Computer-based Modelling and Optimization in Transportation. Springer, 2014, pp. 237-250.

37.

Nasir

Lim

Nahavandi

Creighton

. A genetic fuzzy system to model pedestrian walking path in a built environment. Simulation Modelling Practice and Theory.2014; 45: 18-34.

38.

Del Sent

Roisenberg

de Freitas Filho

. Simulation of crowd behavior using fuzzy social force model. In: 2015 Winter Simulation Conference (WSC). IEEE, 2015, pp. 3901-3912.

39.

Song

. A fuzzy-theory-based behavioral model for studying pedestrian evacuation from a single-exit room. Physics Letters A.2016; 380(34): 2619-2627.

40.

Urgen Zimmermann

. Fuzzy Set Theory and Its Applications. Kluwer Academic Publishers, 2nd, revised edition, 1991.

41.

Togawa

. Study of fire escapes basing on the observation of multitude currents, Report no. 4, Building Research Institute, International Journal of Rough Sets and Data Analysis (IJRSDA). 2015; 2(1): 1-21.

42.

Deepak

John

. Information systems on hesitant fuzzy sets. International Journal of Rough Sets and Data Analysis (IJRSDA).2016; 3(1): 71-97.

43.

Zadeh

, et al. Fuzzy sets. Information and Control.1965; 8(3): 338-353.

44.

Bühler

. Réglage par logique floue. LEI-BOOK-2005-010. Presses polytechniques et universitaires romandes, 1994.

45.

Passino

Yurkovich

Reinfrank

. Fuzzy control. vol. 20. Citeseer, 1998.

46.

Godjevac

. Idées nettes sur la logique floue. PPUR presses polytechniques, 1999.

47.

Ortony

Clore

. A. collins (1988). The cognitive structure of emotions, 1988.

48.

Ekman

. An argument for basic emotions. Cognition & emotion.1992; 6(3-4): 169-200.

49.

Russell

Mehrabian

. Distinguishing anger and anxiety in terms of emotional response factors. Journal of Consulting and Clinical Psychology.1974; 42(1): 79.

50.

Koenig

Likhachev

. Adaptive a. In: Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems. ACM, 2005, pp. 1311-1312.

51.

Hart

Nilsson

Raphael

. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics.1968; 4(2): 100-107.

52.

Ravi

Reddy

Zimmermann

. Fuzzy rule base generation for classification and its minimization via modified threshold accepting. Fuzzy Sets and Systems.2001; 120(2): 271-279.