=Paper=
{{Paper
|id=None
|storemode=property
|title=A Cellular Automata Model for Pedestrian and Group Dynamics
|pdfUrl=https://ceur-ws.org/Vol-741/ID2_BandiniRubagottiVizzariShimura.pdf
|volume=Vol-741
|dblpUrl=https://dblp.org/rec/conf/woa/BandiniRVS11
}}
==A Cellular Automata Model for Pedestrian and Group Dynamics==
https://ceur-ws.org/Vol-741/ID2_BandiniRubagottiVizzariShimura.pdf
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.