1 A Cellular Automata Model for Pedestrian and Group Dynamics Stefania Bandini∗† , Federico Rubagotti∗ , Giuseppe Vizzari∗† , Kenichiro Shimura†‡ ∗ Complex Systems and Artificial Intelligence (CSAI) research center Department of Computer Science, Systems and Communication (DISCo) Università degli Studi di Milano - Bicocca, Viale Sarca 336/14, 20126 Milano, Italy bandini@csai.disco.unimib.it, f.rubagotti@campus.unimib.it, vizzari@csai.disco.unimib.it † Center of Research Excellence in Hajj and Omrah (Hajjcore) Umm Al-Qura University, Makkah, Saudi Arabia ‡ Research Center for Advanced Science & Technology The University of Tokyo - Komaba 4-6-1, Meguro-ku, Tokyo, 153-8904, Japan shimura@tokai.t.u-tokyo.ac.jp Abstract—The simulation of pedestrian dynamics is a consolidated area phenomena related to crowds of pedestrians in the environment, of application for cellular automata based models: successful case studies models and simulators have shown their usefulness in supporting can be found in the literature and off-the-shelf simulators are commonly architectural designers and urban planners in their decisions by employed by end-users, decision makers and consultancy companies. These models, however, generally consider individuals, their interactions creating the possibility to envision the behaviour/movement of crowds with the environment and among themselves, but they generally neglect of pedestrians in specific designs/environments, to elaborate what- (or treat in a simplistic way) aspects like (i) the impact of cultural if scenarios and evaluate their decisions with reference to specific heterogeneity among individuals and (ii) the effects of the presence metrics and criteria. of groups and particular relationships among pedestrians. This work describes an innovative cellular automata based model encapsulating in Cellular Automata [3] have been widely adopted as a conceptual the pedestrian’s behavioural model effects representing both proxemics and computational instrument for the simulation of complex systems and a simplified account of influences related to the presence of groups (see, e.g., [4]); in this specific context several CA based models (see, in the crowd. The model is tested in a simple scenario to evaluate the e.g., [5], [6]) have been adopted as an alternative to particle-based implications of some modeling choices and the presence of groups in the simulated scenario. Results are discussed and compared to experimental approaches [7], and they also influenced new approaches based on observations and to data available in the literature. autonomous situated agents (see, e.g., [8], [9], [10]). The main aim of this work is to present a CA based model for pedestrian and crowd dynamics for a multidisciplinary investigation of the complex I. I NTRODUCTION dynamics that characterize aggregations of pedestrians and crowds. This work is set in the context of the Crystals project2 , a joint re- Crowds of pedestrians are complex entities: they are characterized search effort between the Complex Systems and Artificial Intelligence by a peculiar mix of competition for the space shared by pedestrians research center of the University of Milano–Bicocca, the Centre of and the collaboration due to the (not necessarily explicit but generally Research Excellence in Hajj and Omrah and the Research Center shared) social norms, and the overall system behavour depends on for Advanced Science and Technology of the University of Tokyo. individual choices, which in turn depend on the past actions of The main focus of the project is on the adoption of CA and agent other individuals and on the current perceived state of the system. based approaches to pedestrian and crowd modeling to investigate Phenomena that can be observed in crowded spaces are the results meaningful relationships between the contributions of anthropology, of self-organization and they can be safely defined as emergent cultural characteristics and existing results on the research on crowd properties, and this is a further indicator of the intrinsic complexity dynamics, and how the presence of heterogeneous groups influence of a crowd. emergent dynamics in the context of the Hajj and Omrah. The last Nevertheless, the relevance of human behaviour, and especially point is in fact an open topic in the context of pedestrian modeling of the movements of pedestrians, in built environment in normal and simulation approaches: the implications of particular relationships and extraordinary situations, and its implications for the activities of among pedestrians in a crowd are generally not considered or treated architects, designers and urban planners are apparent (see, e.g., [1] in a very simplistic way by current approaches. In the specific context and [2]), especially considering dramatic episodes such as terrorist of the Hajj, the yearly pilgrimage to Mecca that involves over 2 attacks, riots and fires, but also due to the growing issues in facing millions of people coming from over 150 countries, the presence the organization and management of public events (ceremonies, of groups (possibly characterized by an internal structure) and the races, carnivals, concerts, parties/social gatherings, and so on) and cultural differences among pedestrians represent two fundamental in designing naturally crowded places (e.g. stations, arenas, airports). features of the reference scenario. Studying implications of these Computational models for the simulation of crowds are thus grow- basic features is the main aim of the Crystals project. ingly investigated in the scientific context, and these efforts led to The paper breaks down as follows: the following section introduces the realization of commercial off-the-shelf simulators often adopted the CA based pedestrian and crowd model considering the possibility by firms and decision makers1 . Even if research on this topic is still of pedestrians to be organized in groups, while Sect. III summarizes quite lively and far from a complete understanding of the complex the results of the application of this model in a simple simulation 1 see, e.g., Legion Ltd. (http://www.legion.com), Crowd Dynamics Ltd. scenario. Conclusions and future developments will end the paper. (http://www.crowddynamics.com/), Savannah Simulations AG (http://www. savannah-simulations.ch). 2 http://www.csai.disco.unimib.it/CSAI/CRYSTALS/ 2 according to the simulation parameter), and can be walkable or not. A cell is thus characterized by a cellID, an unique key for each cell, it can be associated to a generator if the cell can generate pedestrians, it can be walkable or not (e.g. the cell contains a wall). The second layer, denoted as l2 , contains information about the values of the floor fields into each cell. Values are saved as pairs (f loorID, value). Data saved into the second layer concerns targets and the best path to follow to reach them. The third layer l3 is made up of cells that may be empty or occupied by one pedestrian. This layer stores the Fig. 1. The separation of the environment into three layers in a L-shaped position of each pedestrian. The aim of this partitioning is to branch corridor configuration. three different domains of information into three different views in order to keep our model cleaner and easier to understand. 1) Generators and Targets: Information about generators and II. GA-P ED M ODEL targets are saved into the first and second layer. A target is a location We now introduce some principles considered during the definition in the environment that the pedestrians may desire to reach, due to of our model. We decided to simulate the interactions between its position or to the presence of a particular object. Examples of pedestrians in an environment that is discrete both in space and targets in a train station are ticket machines, platforms, exits, lounges in time. We introduced a two-dimensional cellular automata (CA) and so on. A traveller may have a complex schedule composed of structure with local interactions, a discrete-time dynamical system to different targets like: (a) I have to buy a ticket, then (b) I want to model the movements of pedestrians inside a structured environment. drink a coffee and (c) reach platform number 10 to board the train We chose a discrete approach in order to achieve an efficient to Berlin. This plan can be translated in the following schedule: (i) implementation for fast computer simulation, while maintaining a ticket machine, (ii) lounge, (iii) platform 10. From now on the words sufficient expressiveness in the definition of the rules for pedestrian schedule and itinerary are used interchangeably as they both define movement. Moreover, the model employs floor fields (see, e.g., [11]) the same concept. We will describe how pedestrians will be able to to support pedestrian navigation in the environment. In particular, move towards the target later on. each relevant final or intermediate target for a pedestrian is associated Generators are cells that, at any iteration, may generate new to a floor field, a sort of gradient indicating the most direct way pedestrians according to predetermined rules. Generating spots are towards the associated point of interest. groups of generator cells located in the same area and driven by the Our system is represented by the triple: Sys = hEnv , Ped , Rulesi. same set of rules of generation. In our model a generating spots is The first element to be introduced is the environment: it contains defined as follows: different objects (e.g. walls, obstacles, etc.) and pedestrians. Without spot = hspotID, maxPed , positions, groups, itineraries, frequencyi the environment it is not possible to define and generate pedestrians. Pedestrians have a position inside the environment, they can observe where spotID is an identifier for the generator; maxP ed is the their neighborhood looking for the best path to reach the targets maximum amount of pedestrians that the spot can generate during specified in a schedule. Every pedestrian is endowed of an internal the entire simulation; positions indicate the cells belonging to that state, that is a memory used to save the schedule, feelings, past actions generating spot (a spot may in fact contain different cells); groups and the characterization of the pedestrians. being the set of group types that can be generated, each associated Now we introduce our model in detail, starting from the represen- with a frequency of generation; itineraries that can be assigned to tation of space and environment. Then we focus the attention on the each pedestrian, considering the fact that group members share the modeling of pedestrian, finishing with details on the update rules. same schedule but that different groups may have different schedules, each associated with a frequency; f requency is a value between 0 and 100, specifying the frequency of pedestrian generation (0 means A. Space and Environment never generate pedestrians, 100 means always generate pedestrians). The representation of the space in our model is mutuated from Information about generators are stored in the first layer, on the the Cellular Automata theory. The space is splitted into squared contrary, targets are represented in the second layer, specified with cells with fixed width, obtaining a two-dimensional grid. Namely, floor field values. Every target has a position and it is associated to in our model the space is discretized into small cells which may be a floor field that guides pedestrians to it. empty or occupied by exactly one pedestrian. At each discrete time 2) Floor Fields: As stated previously, the floor field can be thought step it is possible to analise the state of the system by observing of as a grid of cells underlying the primary grid of the environment. the state of each cell (and, consequently, the position of each Each target has a floor field and the values are saved into the l2 of the pedestrian into the environment). In our model the environment is environment. A floor field contains information suggesting the shotest defined as Env = hSpace, Fields, Generatorsi where the Space path to reach the destination. Floor field values are distributed in every is a physical, bounded bi-dimensional area where pedestrians and cell of the environment. In our model each cell contains information objects are located; the size of the space is defined as a pair of about every target defined in the model. Given the cell at position values(xsize, ysize) and it is specified by the user. In our model (x, y), the corresponding floor field values are saved into l2 . The we consider only rectangular-shaped scenarios (but it is possible to content of l2 (cx,y ) is a list of pairs with the following structure: shape the scenario defining non-walkable areas). The space in our (f loorID, value). Values of a floor field are integers between 0 and model is modeled using a three-layer structure: Space = hl1 , l2 , l3 i 256. Given a target, if a cell has a floor field value 0 for that particular where each layer represents details related to a particular aspect of the destination, means that no indications to reach the target is available. environment. As represented in Figure 1, each layer is a rectangular On the contrary, if the value of the cell is 256 means that the target matrix sharing the same size of the other two. The first layer contains has been accomplished (because the target is in that cell). If a cell all the details about each cell are saved in the first layer (l1 ). A cell has value 0 for a particular destination, this means that no data is may be a generating spot (i.e. a cell that can generate new pedestrians available for reaching the target. 3 We can distinguish between two classes of floor fields: static and with pedID being an identifier for each pedestrian, groupID dynamic. The static floor field does not evolve with time and it is not (possibly null, in case of individual) the group the pedestrian belongs influenced by the presence of pedestrians. The dynamic floor field to and schedule a list of goals to be accomplished by the pedestrian is modified by the presence of pedestrians and it is updated using (one of the above introduced itineraries). two procedures called diffusion and decay. In our model we have 2) Perception model: In our model every pedestrian has the only static floor fields, specifying the shortest path to destinations capability to observe the environment around him, looking for other and targets. Interactions between pedestrians that in other models pedestrians, walls and objects. Perception capabilities are modeled are described by the use of dynamic floor fields, in our model are with the idea of observation fan. An observation fan can be thought modeled through a perception model based on the idea of observation as the formalization of physical capabilities: it determines how far fan, which will be introduced in Section II-C. An example of floor a pedestrian can see and how much importance has to be given to field is presented in Figure 1.b. A greyscale is used to visually show the presence of obstacles and other pedestrians. An observation fan its values: darker cells have higher floor field values, target is in red. is similar to the idea of neighborhood of a cell in the CA theory as Cells near the target have higher values. Floor field values influence it defines the shape of the observable area, and how to evaluate the the transition probabilities of a pedestrian, as a person usually will observed things according to their distance from the pedestrian. An try to follow the shortest path to the target. observation fan is defined as follows: ζ = htype, xsize, ysize, weight, xoffset, yoffseti B. Time and Update Type where: Our model is a discrete-time dynamical system, and update rules • type identifies the direction of the fan: it can be 1 for diagonal are applied to all pedestrians following an update method called shuffled sequential update [12]. At each iteration, pedestrians are directions and 2 for straight directions (the fan has different updated following a random sequence. This choice was made in shapes and is usually asymmetric); • sizes and offsets are defined as shown in figure 2. Sizes (xsize order to implement our method of collision avoidance based on cell reservation. In the shuffled sequential update, a pedestrian, when and ysize) define the maximum distance to which the pedestrian choosing the destination cell, has to check if this cell that has been can see. The shape of the fan is influenced by both the direction reserved by another pedestrian within the same time step. If not, the and the sizes. The offsets are used to define if the pedestrian pedestrian will reserve that cell, moving at the end of the iteration. can see backward and the size of the lateral view (only type 2, If the cell is already reserved, an alternative destination cell can be see Fig 2.c); • weight is a matrix of values wx,y ∈ R+ defined in the interval chosen. Each iteration corresponds to an amount of time directly propor- [0, 1]. These values determine the relationship between the thing tional to the size of the cells of the environment and to the reaction that has been observed and the distance (e.g. the distance of a time: given a squared cell of 40×40cm2 , the corresponding timescale wall influences differently the movement of a pedestrian). is approximately of 0.3sec of real time, obtained by transposing the For each class of groups is possible to define multiple observation empirically observed value of average velocity of a pedestrian, that is fans; each fan can be applied when evaluating walls, pedestrians 1.3m/s to the maximal walking speed of one cell per time step [13]. belonging to the same group, to other groups or, lastly, to particular groups. For instance, this feature is useful when modeling situations like football matches: it is possible to define two classes of groups, C. Pedestrians one made of supporters of the first team and the other of supporters We now focus the attention on the modeling of pedestrians: first we of the second team. Groups belonging to the first class will interact introduce the representation of the pedestrians. They are modeled as differently if dealing with other groups belonging to the first class the state of cells in a bidimensional grid. Each pedestrian is provided or belonging to the second one. with some attributes describing details like group membership, ID, schedules, gender, age. Then we introduce the perception model: each 3) Behavior and Transition Rules: In this section we introduce the pedestrian is endowed with a set of observation fans that determines evaluation phases and the transition rules that model the pedestrian how they see and evaluate the environment. Attributes, internal behavior. First, we introduce our concept of pedestrians modeled as state and environment influence the behavior of our pedestrians: Deterministic Finite Automata. Then we focus the attention on the movement decisions are modeled using a Finite State Automata and behavior of the pedestrians in our model. It is determined by different a set of rules. In detail, a pedestrian can move in one of the cells aspects, like the minimization of the time necessary to reach the belonging to its Moore neighborhood, to any possible movement destination, the need to keep a significative distance from strangers is associated a revenue value, called likability, representing the while preserving the cohesion of the group and avoiding obstacles. desirability of moving into that position. While in the previous section The decision of a movement is taken after an evaluation of the we introduced the notion and structure of simulation turn, we will environment and the internal state, choosing the best tradeoff of the now show how a single pedestrian act is performed. In the following aspects previously introduced. sections we introduce how pedestrians decide their movements, for a) Pedestrian states and transitions: The behavior of a pedes- now we introduce the two main tasks they perform: they observe the trian is represented as a flow made of four stages: sleep, context environment and the internal state to obtain the spatial awareness; evaluation, movement evaluation, movement. they evaluate the likability of the possible movements and they choose When a new iteration is started, each pedestrian is in a sleeping the solution that maximizes the benefits. state. This state is the only possible in this stage, and the pedestrian 1) Pedestrian Characterization: We decided to reduce the charac- does nothing but waits for a trigger signal from the system. The terization of our pedestrians to a small set of essential attributes and system wakes up each pedestrian once a iteration and, then, the in particular pedestrian passes to a new state of context evaluation. In this stage, the pedestrian tries to collect all the information necessary to obtain pedestrian = hpedID, groupID, schedulei spatial awareness. When the pedestrian has collected enough data 4 Fig. 2. Example of the shape of an observation fan for a diagonal direction (in this case south-east) and for a straight direction (in this case south): (a and c) in light cyan the cells that are observable by the pedestrian and are used for the evaluation, in green the observable backward area; (b and d) the weight matrix applied for the evaluation, in this case objects or pedestrians near the pedestrian have more weight that farther ones (e.g. this fan is useful for evaluating walls). about the environment around him, it reaches a new state. In this the current position is considered a valid option), into the cells state behavioral rules are applied using the previously gathered data belonging to their Moore neighborhood of range r = 1. Each possible and a movement decision is taken. When the new position is notified movement has a value called likability that determines how much the to the system, the pedestrian returns to the initial state and waits for move is good in the terms of the criteria previously introduced. the new iteration. In order to keep our model simple and reduce complexity, we do In our model pedestrian active behavior is limited to only two not consider multiple speed. At each iteration a pedestrian can move phases: in the second stage pedestrians collect all the information nec- only in the cells belonging to the Moore neighborhood, reaching a essary to recognize the features of the environment around him and speed value of 1 or can maintain the position (in this case speed is recall some data from their internal state about last actions and desired 0)4 . targets. A first set of rules determine the new state of the pedestrian. b) Functions and notation: In order to fully comprehend the The new state, belonging to the stage of movement evaluation, depicts pedestrian behavior introduced in the following paragraphs, it is current circumstances the pedestrian is experiencing: e.g. the situation necessary to premise the notational conventions and the functions may be normal, the pedestrian may be stuck in a jam, it may be we have introduced in our modelization: compressed in a dense crowd or lost in an unknown environment • cx,y defines the cell with (valid) coordinates (x, y); (i.e. no valid floor field values lead to the desired destination). This • F loors is the set of the targets instantiated during the simu- state of awareness is necessary to the choice of the movement as lation. Each target has a floor field and they share the same different circumstances may lead to different choices: a pedestrian floorID (i.e. with t ∈ F loors we define both the target and the stuck in a jam may try to go in the opposite direction searching for associated floor field); an alternative path, a lost pedestrian may start a random walk or • Groups the set containing the groupID of the groups instanti- looking for other floor fields. ated during the simulation dynamics; We represent pedestrian behavior with a deterministic finite au- • Classes is the set containing all the group classes declared tomaton (DFA)3 . Our automaton M is a 4-tuple (Q, E, δ, q0 ), where: when defining the scenario; • Q a list of states; • Directions is the set of the possible direc- • E a list of events; tions. Are nine, defined using cardinal directions: • δ : Q × E → Q a transition function; {N, N E, E, SE, S, SW, W, N W, C}. • q0 ∈ Q an initial state. Given x ∈ [0, xsize − 1] and y ∈ [0, ysize − 1], we define some The set of states Q is partitioned into four subsets: functions useful to determine the characteristics and the status of the 1) Sleeping: only one state (sleeping); cell cx,y : 2) ContextEvaluation: only one state, the pedestrian is collect- • cell walkability: this function determines if the cell cx,y is ing data to achieve spatial awareness; walkable or not (e.g. if there is a wall). If the cell is walkable the 3) M ovementEvaluation: the pedestrian is aware of its situa- function returns the value 1, otherwise it returns 0. It is defined tion and it is evaluating all the possible alternatives; as follows: 4) M ovement: nine states belong to this subset, one for each direction; l1 (cx,y ) = [0, xsize − 1] × [0, ysize − 1] → {0, 1} : Also the events belonging to E are partitioned into four subsets, 0 if the cell is not walkable,1 otherwise; (1) as every event can be associated to only one pair of states. 4) Pedestrian movements: We now focus the attention on the • floor field value: this function determines the value of the floor modeling of how our pedestrians evaluate the possible movements field t in the cell cx,y . If the cell contains the target associated and how they choose the best movement. to the target t, the function returns the value 256. If there is a) Direction and speed of movement: At each time step, no floor field available for the target t the function returns the pedestrians can change their position along nine directions (keeping value 0. If a valid floor field is present the function return its 3 We are not modeling all the features of a deterministic finite automaton: 4 Our pedestrians can move only to the cells with distance 1 according to we are not recognizing languages and we do not have accepting states. the Tchebychev distance. 5 value, which is defined in the interval [1, 255]: l2 (cx,y , t) = [0, xsize−1]×[0, ysize−1]×t ∈ F loors → [0, 256] : 0 if the floor field for t is not available, 256 if the cell is the target, the floor field value for t otherwise; (2) • presence of pedestrians belonging to a particular group this function determines if in the cell cx,y contains a pedestrian Fig. 3. Representation of the corridor scenario: environment geometry, belonging to a particular group g specified as input. If a generators and floor fields. pedestrian belonging to that group is contained in the cell, the function returns 1, otherwise it returns 0: in the observation fan ζ, according to the weight matrix for the l3 (cx,y , g) = [0, xsize−1]×[0, ysize−1]×g ∈ groups → [0, 1] : group of these pedestrians: 0 if the cell does not contain a pedestrian ci,j ∈ζx,y,d X ζ belonging to the group g, 1 otherwise. (3) ζ(strangers, d, (x, y), g) = wi,j · (1 − l3 (ci,j , g)); (6) c) Observation fan: We define ζx,y,d as the set of cells that are observable according to the characteristics of the observation fan • stochasticity: similarly to some traffic simulation models (e.g. ζ, used by a pedestrian located in the cell at coordinates (x, y) and [14]), in order to introduce more realism and to obtain a looking in the direction d. non deterministic model, we define  ∈ [0, 1] as a a random The overall likability of a possible solution can be thought as value that is different for each likability values and introduces the desirability of one of the neighboring cells. The more a cell is stochasticity in the decision of the next movement. desirable, the higher is the probability that a pedestrian will choose to Formally, these four influences compose the likability of a move- move into that position. In our model the likability is determined by ment as follows: the evaluation of the environment and it is defined as a composition of a sequence of characteristics: li(cx,y , d, g, t) = jw ζ(walls, d, (x, y)) + jf f ield(t, (x, y))− jg ζ(group, d, (x, y), g) − jn ζ(strangers, d, (x, y), g) + . (7) likability = goal driven component + group cohesion - proxemic repulsion - geometrical repulsion + stochastic contribution Group cohesion and floor field are positive components because Formally, given a pedestrian belonging to the group class g ∈ they positively influence a decision as a pedestrian wishes to reach Groups, in the state q ∈ Q and reaching a goal t ∈ F loors, the the destination quickly, keeping the group cohese at the same time. likability of a neighbouring cell cx,y is defined as li(cx,y ) and is On the contrary, the presence of obstacles and other pedestrians obtained evaluating the maximum benefit the pedestrian can achieve has a negative impact as a pedestrian usually tends to avoid this moving into this cell (following the direction d ∈ Directions) using contingency. the observation fan ζ for the evaluation. The formula 7 summarizes the evaluation of the aspects that • goal driven component: it is the pedestrian wish to quickly characterize the likeness of a solution. A pedestrian for each possible reach its destination and is represented with the floor field. Our movement opens an observation fan and examines the environment in model follows the least effort theory: pedestrians will move on the corresponding directions, evaluating elements that may make that the shortest path to the target which needs the least effort. This movement opportune (e.g. the presence of other pedestrians belonging component is defined as l2 (cx,y , t): it is the value of the floor to the same group or an high floor field value and data that may field in the cell at coordinates (x, y) for the target t; discourage as the presence of walls or pedestrians belonging to other • group cohesion: it is the whish to keep the group cohese, groups). minimizing the distances between the members of the group. It is defined as the pedestrians belonging to the same group in the observation fan ζ, evaluated according to the associated III. S IMULATION SCENARIO weight matrix: The simulated scenario consists in a rectangular corridor, 5m wide ci,j ∈ζx,y,d and 10m long. We assume that the boundaries are open and that walls ζ(group, d, (x, y), g) = X ζ wi,j · l3 (ci,j , g) (4) are present in the north and south borders. The width of the cells is 40cm and the sizes of the corridor are represented with 14 cells • geometrical repulsion: it represents the presence of walls and and 25 cells respectively. Pedestrians are generated at the east and obstacles. Usually a pedestrian wishes to avoid the contact with west borders and their goal is to reach the opposite exit. Floor fields, these object and the movement is consequently influenced by environment geometry and generators are graphically represented in their position. This influence is defined as the presence of walls Figure 3. (located in layer l1 ) inside the observation fan ζ, according to We investigated the capability of our model to fit the fundamental the weight matrix for walls specified in the same observation diagram proposed in the literature for characterizing pedestrian simu- fan: lations [15] and other traffic related phenomena. This kind of diagram ci,j ∈ζx,y,d X ζ shows how the average velocity of pedestrians varies according to the ζ(walls, d, (x, y)) = wi,j · l1 (ci,j ) (5) density of the simulated environment. Since the flow of pedestrians • proxemic repulsion: it is the repulsion due to presence of is directly proportional to their velocity, this diagram is sometimes pedestrians, alone or belonging to other groups (e.g. strangers). presented in an equivalent form that shows the variation of flow A pedestrian whishes to maintain a safe distance from these according to the density. In general, we expect to have a decrease pedestrians and this desire is defined as the sum of these people in the velocity when density grows; the flow, instead, initially grows, 6 Fig. 4. Fundamental diagram for the rectangular corridor with groups of size 3. The density is specified as frequency of generation. The ratio between members of groups and alone pedestrians is 40/60. since it is also directly proportional to the density, until a certain Fig. 5. Images representing the state of the simulation taken at different threshold value is reached, then it decreases. time steps. The opponent group is composed of 50 pedestrians, while the challenging group size is 5. As shown in Figure 4 our model correctly represents the nature of pedestrian dynamics: if the frequency of generation is low, con- sequently the flow is low. Increasing the frequency leads to a higher the model can simulate all the three possible cases that can be spotted throughput until a critical density has been reached. If the system in the real world: density is increased beyond that value, the flow begins to decrease • the challenging group remains compact and moves around the significantly as the friction between pedestrians make movements opponent group; more difficult. Observing the same figure we can state that, before • one or more members of the challenging group moves around the the critical density has been reached, the flow is fluid, similar to larger group in the other side with respect to the other members the laminar flow that can be see in the models of traffic simulation. of the group; After the value of critical density has been reached, the simulations • one or more members of the challenging group remain stuck underline a greater variability in the fundamental diagram. In fact, at in the middle of the opponent group and then the small group higher density the possibility of events that may disrupt the flow are temporarily breaks up. more frequent causing a sensible variation of the throughput. It is also interesting to point out that in our model, if a split is This result is a first element of validation of the model; in addition, verified in the challenging group, when their members overcome the the model has been validated against data (related to a specific opponent group, they aim to form again a compact configuration. experimental setting, i.e., a specific density value) acquired in an The actual size of the simulation scenario is however too small to experimental observation [16]. Additional experimental observations detect this reforming of the group5 . In Figure 5 are presented some would be useful to further evaluate the capability of the model to images representing the state of the simulation at different time steps. generate quantitatively valid simulations. As stated before, it is possible to observe the range of different We also performed additional qualitative observations of the dy- circumstance that our model is able to simulate: for example, in 5, in namics generated by the model and we can state that it is capable to the simulation #1 the challenging groups can overcome the opponent generate the following phenomena: one simply by moving around it, the same situation is represented • lane formation at high densities; in simulation #2 and #4 but the challenging group experiences more • the higher is the number and the size of the groups into the friction generated by the opponents. In the same figure, the simulation environment, the lower will be the total flow, due to the higher #3 and #5 show a challenging group that splits in two and their degree of friction between different groups. members moving around the opponent group on both the two sides. Finally, we investigated the relationships between the time neces- A. Large group vs small group counterflow sary to the members of the challenging group to reach the opposite end of the corridor in relation with the size of the opponent group. We were interest in studying the dynamics of friction and avoid- As expected, and in tune with the previous observations, the larger ance that are verified when two groups with different size, traveling the size of the opponent group, the higher time necessary to the in opposite directions, are facing each others in a rectangular shaped members of the challenging group to reach their destination is. The corridor. We simulated the 5m × 10m corridor with one large group difference of size in the challenging group only slightly influences traveling from the left (west) to the right (east), opposed to one small the performances: it is easier to remain stuck in the opponent group group traveling in the opposite direction. The aim of this particular set but the difference between three and five pedestrians is insufficient up was to investigate the differences in the dispersion of the smaller to obtain significant differences. group with respect of the size of the large group and the overall time necessary to walk through the corridor. From now on we call IV. C ONCLUSIONS AND F UTURE D EVELOPMENTS the small group as the challenging group and the large group as the The paper presented a CA based pedestrian model considering opponent group. groups as a fundamental element influencing the overall system We considered opponent group of five different sizes: 10, 20, 30, 40 and 50. Challenging groups were defined with only two sizes: 3 5 We carried out additional simulations in larger environments and we and 5. The results are consistent with the observable phenomena as qualitatively observed the group re-union. 7 dynamics. An original model considering a simple notion of group [7] D. Helbing and P. Molnár, “Social force model for pedestrian dynamics,” (i.e. a set of pedestrians sharing the destination of their movement Phys. Rev. E, vol. 51, no. 5, pp. 4282–4286, May 1995. [8] J. Dijkstra, J. Jessurun, and H. J. P. Timmermans, Pedestrian and and the tendency to stay close to each other) has been presented and Evacuation Dynamics. Springer–Verlag, 2001, ch. A Multi-Agent applied to a simple scenario, gathering results that are in tune with the Cellular Automata Model of Pedestrian Movement, pp. 173–181. existing literature on this topic. Validation against real data is being [9] C. M. Henein and T. White, “Agent-based modelling of forces in conducted and preliminary results show a promising correspondence crowds.” in Multi-Agent and Multi-Agent-Based Simulation, Joint Work- between simulated and observed data. Future works are aimed at a shop MABS 2004, New York, NY, USA, July 19, 2004, Revised Selected Papers, ser. Lecture Notes in Computer Science, P. Davidsson, B. Logan, concrete application of the model in the context of the Crystals project and K. Takadama, Eds., vol. 3415. Springer–Verlag, 2005, pp. 173–184. and further extensions of the notion of group and related dynamics. [10] S. Bandini, M. L. Federici, and G. Vizzari, “Situated cellular agents approach to crowd modeling and simulation,” Cybernetics and Systems, ACKNOWLEDGMENTS vol. 38, no. 7, pp. 729–753, 2007. [11] C. Burstedde, K. Klauck, A. Schadschneider, and J. Zittartz, “Simulation This work is a result of the Crystal Project, funded by the Centre of pedestrian dynamics using a two-dimensional cellular automaton,” of Research Excellence in Hajj and Omrah (Hajjcore), Umm Al-Qura Physica A: Statistical Mechanics and its Applications, vol. 295, no. 3-4, University, Makkah, Saudi Arabia. pp. 507–525, 2001. [12] H. L. Klüpfel, “A cellular automaton model for crowd movement and egress simulation,” Ph.D. dissertation, Universität Duisburg-Essen, Jul. R EFERENCES 2003. [13] U. Weidmann, “Transporttechnik der Fussgänger,” Schriftenreihe des [1] M. Batty, “Agent based pedestrian modeling (editorial),” Environment IVT, vol. 90, ETH Zürich, 1992. and Planning B: Planning and Design, vol. 28, pp. 321–326, 2001. [14] M. Rickert, K. Nagel, M. Schreckenberg, and A. Latour, “Two lane [2] A. Willis, N. Gjersoe, C. Havard, J. Kerridge, and R. Kukla, “Human traffic simulations using cellular automata,” Physica A: Statistical and movement behaviour in urban spaces: Implications for the design and Theoretical Physics, vol. 231, no. 4, pp. 534–550, 1996. modelling of effective pedestrian environments,” Environment and Plan- [15] A. Schadschneider, W. Klingsch, H. Klüpfel, T. Kretz, C. Rogsch, and ning B, vol. 31, no. 6, pp. 805–828, 2004. A. Seyfried, “Evacuation dynamics: Empirical results, modeling and [3] S. Wolfram, “Computation theory of cellular automata,” Communica- applications,” in Encyclopedia of Complexity and Systems Science, R. A. tions in Mathematical Physics, vol. 96, pp. 15–57, 1984. Meyers, Ed. Springer, 2009, pp. 3142–3176. [4] J. R. Weimar, Simulation with Cellular Automata. Logos Verlag Berlin, [16] L. Manenti, S. Manzoni, G. Vizzari, K. Ohtsuka, and K. Shimura, 1998, iSBN 3-89722-026-1. “Towards an agent-based proxemic model for pedestrian and group [5] A. Schadschneider, A. Kirchner, and K. Nishinari, “CA approach to dynamic,” in WOA, ser. CEUR Workshop Proceedings, A. Omicini and collective phenomena in pedestrian dynamics.” in Cellular Automata, M. Viroli, Eds., vol. 621. CEUR-WS.org, 2010. 5th International Conference on Cellular Automata for Research and Industry, ACRI 2002, ser. Lecture Notes in Computer Science, S. Ban- dini, B. Chopard, and M. Tomassini, Eds., vol. 2493. Springer, 2002, pp. 239–248. [6] V. J. Blue and J. L. Adler, “Cellular automata microsimulation for modeling bi-directional pedestrian walkways,” Transportation Research Part B: Methodological, vol. 35, no. 3, pp. 293–312, 2001.