-The paper presents an agent-based model for the explicit representation of groups of pedestrians in a crowd. The model is the result of a multidisciplinary research (CRYSTALS project) where multicultural dynamics and spatial and sociocultural relationships among individuals are considered as first class elements for the simulation of crowd of pilgrims taking to the annual pilgrimage towards Makkah. After an introduction of advantages of Multi-Agent System approach for pedestrian dynamics modelling, a formal description of the model is proposed. The scenario in which the model was developed and some examples about modelling heterogeneous groups of pedestrians are described.
I. INTRODUCTION
Models for the simulation of pedestrian dynamics and
crowds of pedestrians have been proposed and successfully
applied to several scenarios and case studies: these models
are based on physical approach, Cellular Automata approach
and Multi-Agent System approach (see [
Despite simulators can be found on the market and they are
commonly employed by end-user and consultancy companies
to provide suggestions to crowd managers and public events
organizers about questions regarding space management (e.g.
positioning signals, emergency exits, mobile structures), some
main open issues in Pedestrian Dynamics community are
highlighted as specific modelling requirements. For instance,
theoretical studies and empirical evidences demonstrated that
the presence of groups strongly modifies the overall dynamics
of a crowd of pedestrians [
In this paper, we propose an agent-based model for the
explicit representation and modelling of groups of pedestrians,
starting from some fundamental elements we derived from
theories and empirical studies from sociology [
In modelling groups, considering the differences in the
agent-based tools before mentioned, our goal was to provide
a general platform-independent model, without an explicit
description of space, time, perception functions and behavioural
functions which are usually strictly related to the development
of the tool. On the contrary, we focus on the organization
of pedestrians and on the study of relationships among
individuals and the relative group structure, both as static feature
and dynamic evolution. The main contribution of the approach
we are presented concerns the expressiveness of modelling.
Considering the explicit representation of relationships among
pedestrians, it is moreover possible to apply methods of
network analysis, in particular regarding the identification of
relevant structures (i.e. borders and spatially located groups
[
Differently, other proposals about group modelling
presented in the pedestrian dynamics literature do not explicitly
investigate the whole concept of group (both from static
and dynamic way) and do not consider elements derived
from anthropological and sociological studies: in [
The paper is organized as follows: we focus on the description of basic elements of the model and on the description of agent behavioural rules, directly connected with the analysis of internal states of agents. First, in section II, the scenario of the CRYSTALS project in which the presence of heterogeneous groups is particularly evident is explained. At last, an idea of application of the model to the case study, some conclusions and future directions are presented.
II. THE SCENARIO OF ARAFAT I STATION ON MASHAER
LINE
In this section we describe a case of study in which model requirements have been developed with the study of affluence and entrance on Arafat I station of new Mashaer train line (Fig. 1) during Hajj 2010, the annual Pilgrimage towards Makkah. Hajj is a phenomenon in which millions of pilgrims organized in groups come from all the continents and stay and live together for a limited period of time. In this situation, a lot of groups with different cultural characteristics live together and create the whole crowd of the Pilgrimage.
Fig. 1. A representation of the scenario of Mashaer train station in Arafat I An analysis focused on the presence of groups according to cultural relationships highlighted that four main types of groups can be identified within Hajj pilgrims crowds: 1) primary groups, the basic units social communities are built on consisting in small units whose members have daily direct relationships (e.g. families); 2) residential groups, characterized by homogeneous spatial localization and geographical origin; 3) kinship groups, based on descent; 4) functional groups,“artificial” groups which exist only to perform a specific functions (i.e. executive, control, expressive function). Relationships among members are only based on the fulfilment of a goal.
To model groups during Hajj, four kinds of static relationships have to be considered: primary, residential, kinship, functional. Moreover, every group can be characterized by a set of features like the country of origin, the language, the social rank. Differently, every pedestrian can be characterized by personal features like the gender, the age, the marital status, the impaired status. In Fig. 2 and 3 some examples on the previously presented groups are shown.
In this model, we refer to some considerations about
organizing structures related to particular patterns of pedestrians
such as crystals of crowd. This concept is directly derived by
the theory of Elias Canetti [
strictly delimited and of great constancy, which serve to precipitate crowds. Their structure is such that they can be comprehended and taken in at a glance.
Starting from this definition, a crowd can be seen as a set of crystals (i.e. groups of agents); a crowd of crystals is a system formally described as:
S = hA; G; R; O; Ci where:
A = fa1; : : : ; ang is the population of agents; G = fG1; : : : ; Gmg is a finite set of groups; R = fr1; : : : ; rlg is a finite set of static binary relationships defined on the system; O = fo1; : : : ; okg is a finite set of goals presented in the system; C = fC1; C2; : : : ; Csg is a family of features defined on the system regarding the groups where each Ci is a set of possible values that the ith feature can assume.
In the next sections we formally define groups and agents.
We define the concept of group in a crowd starting from the previously presented definition of crystals of crowd. Every group is defined by a set of agents and by a relationship that defines the membership of agents to the group. We derive the importance and the connection between the notion of group and the notion of relationship by multidisciplinary studies: informally, a group is a whole of individuals in a relationship with a common goal and/or a common perceived identity.
Every group is defined a priori by a set of agents: this set has a size (i.e. the cardinality of the group) and the composition of members can not change. Moreover, among group members, a static relationship already exists: the kind of relationship determines the type of group, e.g. a family, a group of friends, a working group and so on.
In order to characterize pedestrian groups, it is possible to identify a set of features, shared among all groups in a system: these features allow to analyse and describe more in detail different aspects which is necessary to take into account in the modelling of the system. On the basis of this assumption, a vector with the values of features as associated to every group. These values are shared and homogeneous on agents belonging to the same group. In the same way, every group has a goal that is shared among all the group members. In fact, every agent belonging to a group inherits from it the global attributes of the group and the goal. The latter idea is not a restriction: following multidisciplinary studies, people involve in a group share the same objective or project. The problem to mediate the goal associated to the group and the “local” goal associated to agent as single entity is not dealt with in this first proposal.
We define a group Gi as a 4-tuple:
Gi = hAi; zi; ri; oii where:
Ai A is a finite set of agents belonging to Gi; zi 2 C1 C2 : : : Cs is a vector with the values of features related to Gi group; ri 2 R is a static irreflexive, symmetric relationship among agents which belong to the group Gi and such that for all a; b 2 Ai with a 6= b, the pair (a; b) is in the transitive closure of ri. This means that the graph given by ri is undirected and connected without self-loops; oi 2 O is the goal associated to the group Gi.
In this first proposal, we assume that agents can not belong to two different groups at the same time:
Ai \ Aj = ; 8i; j = 1; : : : ; m and i 6= j
This constraint is certainly a restriction for the generalization of the model. Future works are related to the extension of the model to lead with this aspect. We can also describe the population of agents A as the union the populations of every group:
A = m [ Ai i=1
Visually, we can represent each group as a graph GAi = (Ai; Ei) where Ai is the set of agents belonging to Gi and Ei is the set of edges given by the relationship ri. We require that GAi is a non-oriented and connected graph (i.e. every pair of distinct nodes in the graph is connected).
Another fundamental element besides groups is the agent population A in which every agent represents a pedestrian in a crowd. In order to introduce characteristics related the pedestrians, we introduce L = fL1; : : : ; Lqg as a family of agent features where every Li is a set of possible values that the ith feature can assume. Every agent can have different values related to a set of characteristics L: a = hwai
Lq is a vector with the values where wa 2 L1 L2 : : : of features related to agent a.
After the characterisation of the main elements of the system, we now focus on behavioural rules of pedestrians belonging to a group in a crowd.
We deeply focus on two behavioural rules: the fact that pedestrians tend to maintain a minimum distance from pedestrians belonging the other groups (i) and the fact that pedestrians in a group tend to keep a maximum distance from other agents belonging to the same group (ii).
These rules are directly derived by Proxemics a theory first
introduced by E.T. Hall [
On A we define a pseudo-semi-metric: p : A
A 7! D; that is a function that measures distances between agents, such that, given two agents a; b 2 A, p(a; b) = p(b; a) (i.e., p is symmetric) and p(a; a) = 0D, where D is a domain of distances, described as a totally ordered set with 0D as a minimal element. We introduce D with the scope to not restrict the definition of the environment in a spatial domain: different simulation tools describe space both in a continuous and discrete way. In order to be platform-independent, in this work, we do not explicitly define the environment and, i.e., distances, in a spatial domain.
From p we derive, for any specific agent a 2 A, a function pa : A 7! D that associates to a its distance from any other agents in A. Given two agents a; b 2 A, pa(b) = pb(a).
Moreover, for every group Gi we introduce another pseudosemi-metric: vi : Ai
Ai 7! D that denotes the distance between two different agents belonging to the same group Gi. Given two agents a; b 2 Gi, vi(a; b) = vi(b; a) (i.e., vi is symmetric) and vi(a; a) = 0D. From vi we derive, for any specific agent a 2 Gi a function via : Ai 7! D that associates to the agent its distance from any other agents in Gi. Given two agents a; b 2 Gi, via (b) = vib (a).
In fact, we introduce two different functions p and vi due to a potential difference in their semantic from a theoretical point of view. Actually, considering scenarios of crowd simulations, this distinction is not necessary: in this sense, we assume that p and vi functions have the same semantic 8Gi. A simplification is possible:
8Gi; vi(a; b) = p(a; b) 8a; b 2 A
In the next section we will use p in order to calculate the distance among agents and to guide the behaviours of agents inside and outside groups. As previously written, we have introduced the distance domain D in order to allow us to not restrict the definition of distance to a spatial domain. Obviously, all crowd simulations are situated in a particular environment in which distances can be measured in R+: thinking about a spatially located or binary (true/false) systems simulating pedestrians, only positive real values are admissible. For this reason, we can reduce the complexity of D and admit that D R+, in which also binary values are included (i.e. false=0 and true=1).
1) Safe Proxemic Rule: The first rule we want to introduce is related to the behaviour during interaction between a pedestrian and other pedestrians belonging to a different group. From this point of view, in order to introduce the importance of personal differences derived, for instance, by cultural attitude and social context, in the pedestrian simulating context, we associate to every agent a 2 A belonging to a group Gi a personal distance da 2 D.
We introduce a function da that, considering the feature values associate to the agent and to its group, derives da as follows: da :
Y C C2C !
Y L L2L ! 7! D
Given an agent a 2 Gi, with a = hwai and its group Gi with features zi, its personal distance is da(zi; wa) = da. This distance derives both from the global characteristics of group (i.e. zi) and from the local characteristics of agent (i.e. wa) we are considering.
Considering the distance among a and the other agents not belonging to its group, we require that a 2 Gi is in a safe proxemic condition if the distance pa(b) is above da for all b 2 A n Ai.
Formally, we define that an agent a 2 Gi is in a safe proxemic condition iff: da
This first rule represents the fact that pedestrians tend to maintain a minimum distance from pedestrians belonging the other groups; if the safe proxemic condition is violated, agents tend to restore the condition of proxemic safeness.
2) Safe Group Rule: Every group Gi is characterized by a private defined distance Gi 2 D that depends on the values of group features zi. We introduce a function dg that calculates Gi as follows: dg : Y
C2C
C 7! D Given a group Gi, dg(zi) = Gi .
Previously, the introduced relationships R were called static relationships. The introduction of time into the model gives the possibility to define relationships that are time dependent: due to the fact that time can be modelled in a continuous or discrete way, the proposed model is defined in a way applicable to both continuous and discrete modelling. Considering a particular time t 2 T R and t0 as the starting time, the evolution of the system is given by a map ' : S T 7! S , where S is the space of possible systems. The state of the system at time t is '(S0; t), where S0 is the state of the system at time t0. We use the definition of time in order to introduce a new kind of relationship time-dependent (differently from the previous one). We call dynamic relationship a function r such that rt is a dynamic irreflexive, symmetric relationship among agents which belong to the group Gi. rt represents the relation at time t that is dependent on the whole evolution of the system from time t0 to time t. For each group Gi at time t it is possible to consider the graph given by the relation rt. In particular, to model the proximity relationship between agents, a possible definition of rt is the following: 8a; b 2 Gi; (a; b) 2 rt iff p(a; b) Gi recalling that vi is potentially different for each '(S0; t) since it is defined into the system.
It is possible to define a group as having the safe group condition at time t on the basis of the history of the evolution of the graph structure given by rt. Let S be the function that defines the presence or absence of the safe group condition. In other words S (hrj j j ti) 2 f0; 1g. The fact that S is dependent on the whole history of the graph structure is motivated by the necessity to take care of particular conditions that can temporary change the graph structure but that can be quickly recovered. By using the whole history we can avoid to consider unsafe (respect to safe) a group that is, in fact, in a safe (respect to unsafe) condition. For instance, considering a simulation placed into two rooms separated by a turnstile. The passage of a group through the turnstile can divide the group: in fact the group is not in an unsafe condition if we can detect that the passage through the turnstile is a temporary condition.
The safe group rule represents the fact that pedestrians in a group tend to keep a maximum distance from other agents belonging to the same group: if the safe group condition is violated, agents tend to restore the condition of group safeness.
On the basis of behavioural rules before introduced, it is possible to introduce an analysis about conditions (i.e. internal states) of agents. This analysis can be useful in order to study how agents change their internal conditions considering the application of the model in a simulation.
SPG 2
2 SP 6 3 3 6 1 1 4 4
SG
U 5 5
Considering the two behavioural rules before introduced, an agent can be in a safe proxemic condition or in unsafe proxemic condition; moreover, it can be in a safe group condition or in unsafe group condition. Four states, depending on the verification of the behavioural rules are admitted: 1) Safe Proxemic and Group state (SPG): an agent is in this state if both the safe proxemic and safe group condition are verified; 2) Safe Proxemic state (SP): an agent is in this state if only the safe proxemic condition is verified; 3) Safe Group state (SG): an agent is in this state if only the safe group condition is verified; 4) Unsafe state (U): an agent is in this safe if neither the safe proxemic nor safe group conditions are verified. if every agent represents a singleton, only two states are admissible: SPG and SG. In fact, SP and U states are not possible because every agent is always in a safe group condition.
An overview about internal states and the transitions among them is presented in the Fig. 4. Note that all the transitions among states are admissible.
Now, let us consider two particular configurations on the population of agents A = fa1; a2; : : : ; ang with G1; : : : ; Gm groups: if m = 1 there is only one group coinciding with the whole A; if m = n, jAij = 1 8i = 1; : : : ; m, all the groups have a size equal to 1 and every agent in the population is a singleton. In these cases we note that the previous finite state automata can be simplified as follows (Fig. 5 and Fig. 6): if there is only one group coinciding with A, only two states are admissible: SPG and SP. In fact, SG and U states are not possible because all agents of the population belong to the same Gi group; IV. MODELLING GROUPS IN THE SCENARIO OF ARAFAT I
STATION
Considering the scenario of Arafat I station before introduced, in this section we exploit the model above presented to describe groups of pedestrians in the entrance of the station. In this case, we can define the scenario, depicted in Fig. 1 as a system S = hA; G; R; O; Ci where:
A is the set of the pilgrims in the waiting boxes; G is the set of groups of pilgrims; R = fprimary; residential; kindship; f unctionalg represents the types of groups admitted in the scenario; O = fC1; C2; C3; C4g is the set of possible goals, i.e. the train carriages; C = fcountry; language; social rankg is the family of features regarding groups.
Starting from this definition, a group can be defined for instance as Gi = hAi; zi; ri; oii where: ri = primary; Ai
A represents the set of group members; zi = fSaudi Arabia; Arabic; mediumg; SP SG ai = fmale; adult; married; nog.
Regarding the definition of characteristics of agents, a plausible family of characteristics can be L = fgender; age; marital status; impaired statusg. From this point of view, an agent a 2 A can be defined for instance as
In this paper, we proposed an agent-based model for the explicit representation and modelling of groups of pedestrian in a crowd, focusing on the organization of pedestrians and on the study of relationships among individuals and the relative group structure.
Future directions are related to the development of simulation in the presented scenario in order to test and validate the model, and in the application of methods for network analysis on the group structures, in order to identify and study, for example, the presence of recursive patterns.
This research was fully supported by the Center of Research Excellence in Hajj and Omrah, Umm Al-Qura University, Makkah, Saudi Arabia, grant title “Crystal Proxemic Dynamics of Crowd & Groups”.