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 [1] for a state of the art). In this work, we refer to the Multi-Agent System (MAS) approach according to which crowds are studied as complex systems whose dynamics results from local behaviour of individuals and the interactions with their surrounding environment. A MAS is a system composed of a set of autonomous and heterogeneous entities distributed in an environment, able to cooperate and coordinate with each other [2], [3]. Many research areas contribute to the development of tools and techniques based on MAS for the modelling and simulation of complex systems, as crowds of pedestrians are. In particular, Artificial Intelligence (AI) has contributed in different ways [4]. At the very beginning, AI researchers mainly worked towards encapsulating intelligence in agent behaviours. Other main aspects which AI researchers recently investigated concern modeling and computational tools to deal with interactions [5], [6]. The result of this line of research is that we currently can exploit sounding tools that are flexible, adaptable, verifiable, situated and distributed. Due to the suitability of agents and of MAS-approach to deal with heterogeneity of complex systems, several examples of its application in the pedestrian dynamics area are presented in the literature [7]- [9].
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 [10], [11].
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 [12], anthropology [13] and direct observations gathered during experiments in collective environments [14]. This work is the result of CRYSTALS project, a multidisciplinary research project where multicultural dynamics and spatial and social relationships among individuals are considered as first class elements for the simulation of crowd of pilgrims taking to the annual Hajj (the annual pilgrimage towards Makkah).
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 [15], [16]).
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 [17] e.g. a proposal in which the concept of group is related to the idea of attraction force applied among pedestrians is presented as an extension of social force field model [18]; [19] proposes a model of pedestrian group dynamics using an agent-based approach, based on utility theory, social comparison theory and leader-follower model; in [20] a MAS-based analysis in which social group structures is presented, exploiting inter and intra relationships in groups by means of the creation of static influence weighted matrices not depending on the evolution of the system.
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.
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. 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 [12]:
Crowd Crystals are the small, rigid groups of men, 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. Their unity is more important than their size. The crowd crystal is a constant: it never changes its size. 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:
where:
is a family of features defined on the system regarding the groups where each C i is a set of possible values that the i th 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 G i as a 4-tuple:
where:
among agents which belong to the group G i and such that for all a, b ∈ A i with a = b, the pair (a, b) is in the transitive closure of r i . This means that the graph given by r i is undirected and connected without self-loops;
In this first proposal, we assume that agents can not belong to two different groups at the same time:
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:
Visually, we can represent each group as a graph GA i = (A i , E i ) where A i is the set of agents belonging to G i and E i is the set of edges given by the relationship r i . We require that GA i 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 = {L 1 , . . . , L q } as a family of agent features where every L i is a set of possible values that the i th feature can assume. Every agent can have different values related to a set of characteristics L: a = w a where w a ∈ L 1 × L 2 × . . . × L q is a vector with the values 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 [13] and related to the study of the set of measurable distances between people as they interact. The core of this theory is the fact that different persons perceive the same distance in different way, due to personal attitude. In order to develop these rules, it is necessary to introduce a set of functions to measure distances among agents in the case of a pedestrian inside and outside a group, depending on the semantic of space.
On A we define a pseudo-semi-metric:
that is a function that measures distances between agents, such that, given two agents a, b ∈ A, p(a, b) = p(b, a) (i.e., p is symmetric) and p(a, a) = 0 D , where D is a domain of distances, described as a totally ordered set with 0 D 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 ∈ A, a function p a : A → D that associates to a its distance from any other agents in A. Given two agents a, b ∈ A, p a (b) = p b (a).
Moreover, for every group G i we introduce another pseudosemi-metric:
that denotes the distance between two different agents belonging to the same group
From v i we derive, for any specific agent a ∈ G i a function v ia : A i → D that associates to the agent its distance from any other agents in
In fact, we introduce two different functions p and v i 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 v i functions have the same semantic ∀G i . A simplification is possible:
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 ∈ A belonging to a group G i a personal distance d a ∈ D.
We introduce a function da that, considering the feature values associate to the agent and to its group, derives d a as follows:
Given an agent a ∈ G i , with a = w a and its group G i with features z i , its personal distance is da(z i , w a ) = d a . This distance derives both from the global characteristics of group (i.e. z i ) and from the local characteristics of agent (i.e. w a ) we are considering.
Considering the distance among a and the other agents not belonging to its group, we require that a ∈ G i is in a safe proxemic condition if the distance p a (b) is above d a for all b ∈ A \ A i .
Formally, we define that an agent a ∈ G i is in a safe proxemic condition iff:
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 G i is characterized by a private defined distance δ Gi ∈ D that depends on the values of group features z i . We introduce a function dg that calculates δ Gi as follows:
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 ∈ T ⊆ R and t 0 as the starting time, the evolution of the system is given by a map ϕ : S × T → S, where S is the space of possible systems. The state of the system at time t is ϕ(S 0 , t), where S 0 is the state of the system at time t 0 . 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 r t is a dynamic irreflexive, symmetric relationship among agents which belong to the group G i . r t represents the relation at time t that is dependent on the whole evolution of the system from time t 0 to time t. For each group G i at time t it is possible to consider the graph given by the relation r t . In particular, to model the proximity relationship between agents, a possible definition of r t is the following:
recalling that v i is potentially different for each ϕ(S 0 , 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 r t . Let S be the function that defines the presence or absence of the safe group condition. In other words S ( r j | j ≤ t ) ∈ {0, 1}. 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. 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: 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 = {a 1 , a 2 , . . . , a n } with G 1 , . . . , G m groups: if m = 1 there is only one group coinciding with the whole A; if m = n, |A i | = 1 ∀i = 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 G i group;
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 = A, G, R, O, C where:
• A is the set of the pilgrims in the waiting boxes; • G is the set of groups of pilgrims; • R = {primary, residential, kindship, f unctional} represents the types of groups admitted in the scenario; • O = {C1, C2, C3, C4} is the set of possible goals, i.e. the train carriages; • C = {country, language, social rank} is the family of features regarding groups. Starting from this definition, a group can be defined for instance as G i = A i , z i , r i , o i where:
• A i ⊆ A represents the set of group members;
• z i = {Saudi Arabia, Arabic, medium};
• r i = primary;
Regarding the definition of characteristics of agents, a plausible family of characteristics can be L = {gender, age, marital status, impaired status}. From this point of view, an agent a ∈ A can be defined for instance as a i = {male, adult, married, no}.
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".