-The simulation of pedestrian dynamics is a consolidated area of application for cellular automata based models: successful case studies can be found in the literature and off-the-shelf simulators are commonly employed by end-users, decision makers and consultancy companies. These models, however, generally consider individuals, their interactions with the environment and among themselves, but they generally neglect (or treat in a simplistic way) aspects like (i) the impact of cultural heterogeneity among individuals and (ii) the effects of the presence of groups and particular relationships among pedestrians. This work describes an innovative cellular automata based model encapsulating in the pedestrian's behavioural model effects representing both proxemics and a simplified account of influences related to the presence of groups in the crowd. The model is tested in a simple scenario to evaluate the implications of some modeling choices and the presence of groups in the simulated scenario. Results are discussed and compared to experimental observations and to data available in the literature.
Crowds of pedestrians are complex entities: they are characterized by a peculiar mix of competition for the space shared by pedestrians and the collaboration due to the (not necessarily explicit but generally shared) social norms, and the overall system behavour depends on individual choices, which in turn depend on the past actions of other individuals and on the current perceived state of the system. Phenomena that can be observed in crowded spaces are the results of self-organization and they can be safely defined as emergent properties, and this is a further indicator of the intrinsic complexity of a crowd.
Nevertheless, the relevance of human behaviour, and especially
of the movements of pedestrians, in built environment in normal
and extraordinary situations, and its implications for the activities of
architects, designers and urban planners are apparent (see, e.g., [
Cellular Automata [
The paper breaks down as follows: the following section introduces the CA based pedestrian and crowd model considering the possibility of pedestrians to be organized in groups, while Sect. III summarizes the results of the application of this model in a simple simulation scenario. Conclusions and future developments will end the paper.
We now introduce some principles considered during the definition
of our model. We decided to simulate the interactions between
pedestrians in an environment that is discrete both in space and
in time. We introduced a two-dimensional cellular automata (CA)
structure with local interactions, a discrete-time dynamical system to
model the movements of pedestrians inside a structured environment.
We chose a discrete approach in order to achieve an efficient
implementation for fast computer simulation, while maintaining a
sufficient expressiveness in the definition of the rules for pedestrian
movement. Moreover, the model employs floor fields (see, e.g., [
Our system is represented by the triple: Sys = hEnv ; Ped ; Rules i. The first element to be introduced is the environment: it contains different objects (e.g. walls, obstacles, etc.) and pedestrians. Without the environment it is not possible to define and generate pedestrians. Pedestrians have a position inside the environment, they can observe their neighborhood looking for the best path to reach the targets specified in a schedule. Every pedestrian is endowed of an internal state, that is a memory used to save the schedule, feelings, past actions and the characterization of the pedestrians.
Now we introduce our model in detail, starting from the representation of space and environment. Then we focus the attention on the modeling of pedestrian, finishing with details on the update rules.
The representation of the space in our model is mutuated from the Cellular Automata theory. The space is splitted into squared cells with fixed width, obtaining a two-dimensional grid. Namely, in our model the space is discretized into small cells which may be empty or occupied by exactly one pedestrian. At each discrete time step it is possible to analise the state of the system by observing the state of each cell (and, consequently, the position of each pedestrian into the environment). In our model the environment is defined as Env = hSpace; Fields ; Generators i where the Space is a physical, bounded bi-dimensional area where pedestrians and objects are located; the size of the space is defined as a pair of values(xsize; ysize) and it is specified by the user. In our model we consider only rectangular-shaped scenarios (but it is possible to shape the scenario defining non-walkable areas). The space in our model is modeled using a three-layer structure: Space = hl1 ; l2 ; l3 i where each layer represents details related to a particular aspect of the environment. As represented in Figure 1, each layer is a rectangular matrix sharing the same size of the other two. The first layer contains all the details about each cell are saved in the first layer (l1). A cell may be a generating spot (i.e. a cell that can generate new pedestrians 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 position of each pedestrian. The aim of this partitioning is to branch 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 targets are saved into the first and second layer. A target is a location in the environment that the pedestrians may desire to reach, due to its position or to the presence of a particular object. Examples of targets in a train station are ticket machines, platforms, exits, lounges and so on. A traveller may have a complex schedule composed of different targets like: (a) I have to buy a ticket, then (b) I want to drink a coffee and (c) reach platform number 10 to board the train to Berlin. This plan can be translated in the following schedule: (i) ticket machine, (ii) lounge, (iii) platform 10. From now on the words schedule and itinerary are used interchangeably as they both define the same concept. We will describe how pedestrians will be able to move towards the target later on.
Generators are cells that, at any iteration, may generate new pedestrians according to predetermined rules. Generating spots are groups of generator cells located in the same area and driven by the same set of rules of generation. In our model a generating spots is defined as follows: spot = hspotID ; maxPed ; positions ; groups ; itineraries ; frequency i where spotID is an identifier for the generator; maxP ed is the maximum amount of pedestrians that the spot can generate during the entire simulation; positions indicate the cells belonging to that generating spot (a spot may in fact contain different cells); groups being the set of group types that can be generated, each associated with a frequency of generation; itineraries that can be assigned to each pedestrian, considering the fact that group members share the 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 never generate pedestrians, 100 means always generate pedestrians).
Information about generators are stored in the first layer, on the contrary, targets are represented in the second layer, specified with floor field values. Every target has a position and it is associated to a floor field that guides pedestrians to it.
2) Floor Fields: As stated previously, the floor field can be thought of as a grid of cells underlying the primary grid of the environment. Each target has a floor field and the values are saved into the l2 of the environment. A floor field contains information suggesting the shotest path to reach the destination. Floor field values are distributed in every cell of the environment. In our model each cell contains information about every target defined in the model. Given the cell at position (x; y), the corresponding floor field values are saved into l2. The content of l2(cx;y) is a list of pairs with the following structure: (f loorID; value). Values of a floor field are integers between 0 and 256. Given a target, if a cell has a floor field value 0 for that particular destination, means that no indications to reach the target is available. On the contrary, if the value of the cell is 256 means that the target has been accomplished (because the target is in that cell). If a cell has value 0 for a particular destination, this means that no data is available for reaching the target.
We can distinguish between two classes of floor fields: static and dynamic. The static floor field does not evolve with time and it is not influenced by the presence of pedestrians. The dynamic floor field is modified by the presence of pedestrians and it is updated using two procedures called diffusion and decay. In our model we have only static floor fields, specifying the shortest path to destinations and targets. Interactions between pedestrians that in other models are described by the use of dynamic floor fields, in our model are modeled through a perception model based on the idea of observation fan, which will be introduced in Section II-C. An example of floor field is presented in Figure 1.b. A greyscale is used to visually show its values: darker cells have higher floor field values, target is in red. Cells near the target have higher values. Floor field values influence the transition probabilities of a pedestrian, as a person usually will try to follow the shortest path to the target.
Our model is a discrete-time dynamical system, and update rules
are applied to all pedestrians following an update method called
shuffled sequential update [
Each iteration corresponds to an amount of time directly
proportional to the size of the cells of the environment and to the reaction
time: given a squared cell of 40 40cm2, the corresponding timescale
is approximately of 0:3sec of real time, obtained by transposing the
empirically observed value of average velocity of a pedestrian, that is
1:3m=s to the maximal walking speed of one cell per time step [
We now focus the attention on the modeling of pedestrians: first we introduce the representation of the pedestrians. They are modeled as the state of cells in a bidimensional grid. Each pedestrian is provided with some attributes describing details like group membership, ID, schedules, gender, age. Then we introduce the perception model: each pedestrian is endowed with a set of observation fans that determines how they see and evaluate the environment. Attributes, internal state and environment influence the behavior of our pedestrians: movement decisions are modeled using a Finite State Automata and a set of rules. In detail, a pedestrian can move in one of the cells belonging to its Moore neighborhood, to any possible movement is associated a revenue value, called likability, representing the desirability of moving into that position. While in the previous section we introduced the notion and structure of simulation turn, we will now show how a single pedestrian act is performed. In the following sections we introduce how pedestrians decide their movements, for now we introduce the two main tasks they perform: they observe the environment and the internal state to obtain the spatial awareness; they evaluate the likability of the possible movements and they choose the solution that maximizes the benefits.
1) Pedestrian Characterization: We decided to reduce the characterization of our pedestrians to a small set of essential attributes and in particular pedestrian = hpedID ; groupID ; schedulei with pedID being an identifier for each pedestrian, groupID (possibly null, in case of individual) the group the pedestrian belongs to and schedule a list of goals to be accomplished by the pedestrian (one of the above introduced itineraries).
2) Perception model: In our model every pedestrian has the capability to observe the environment around him, looking for other pedestrians, walls and objects. Perception capabilities are modeled with the idea of observation fan. An observation fan can be thought as the formalization of physical capabilities: it determines how far a pedestrian can see and how much importance has to be given to the presence of obstacles and other pedestrians. An observation fan is similar to the idea of neighborhood of a cell in the CA theory as it defines the shape of the observable area, and how to evaluate the observed things according to their distance from the pedestrian. An observation fan is defined as follows:
= htype; xsize; ysize; weight ; xo set ; yo set i where: type identifies the direction of the fan: it can be 1 for diagonal directions and 2 for straight directions (the fan has different shapes and is usually asymmetric); sizes and offsets are defined as shown in figure 2. Sizes (xsize and ysize) define the maximum distance to which the pedestrian can see. The shape of the fan is influenced by both the direction and the sizes. The offsets are used to define if the pedestrian can see backward and the size of the lateral view (only type 2, see Fig 2.c); weight is a matrix of values wx;y 2 R+ defined in the interval [0; 1]. These values determine the relationship between the thing that has been observed and the distance (e.g. the distance of a wall influences differently the movement of a pedestrian).
For each class of groups is possible to define multiple observation fans; each fan can be applied when evaluating walls, pedestrians 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, one made of supporters of the first team and the other of supporters of the second team. Groups belonging to the first class will interact differently if dealing with other groups belonging to the first class or belonging to the second one.
evaluation phases and the transition rules that model the pedestrian behavior. First, we introduce our concept of pedestrians modeled as Deterministic Finite Automata. Then we focus the attention on the behavior of the pedestrians in our model. It is determined by different aspects, like the minimization of the time necessary to reach the destination, the need to keep a significative distance from strangers while preserving the cohesion of the group and avoiding obstacles. The decision of a movement is taken after an evaluation of the environment and the internal state, choosing the best tradeoff of the aspects previously introduced.
trian is represented as a flow made of four stages: sleep, context evaluation, movement evaluation, movement.
When a new iteration is started, each pedestrian is in a sleeping state. This state is the only possible in this stage, and the pedestrian does nothing but waits for a trigger signal from the system. The system wakes up each pedestrian once a iteration and, then, the pedestrian passes to a new state of context evaluation. In this stage, the pedestrian tries to collect all the information necessary to obtain spatial awareness. When the pedestrian has collected enough data about the environment around him, it reaches a new state. In this state behavioral rules are applied using the previously gathered data and a movement decision is taken. When the new position is notified to the system, the pedestrian returns to the initial state and waits for the new iteration.
In our model pedestrian active behavior is limited to only two phases: in the second stage pedestrians collect all the information necessary to recognize the features of the environment around him and recall some data from their internal state about last actions and desired targets. A first set of rules determine the new state of the pedestrian. The new state, belonging to the stage of movement evaluation, depicts current circumstances the pedestrian is experiencing: e.g. the situation may be normal, the pedestrian may be stuck in a jam, it may be compressed in a dense crowd or lost in an unknown environment (i.e. no valid floor field values lead to the desired destination). This state of awareness is necessary to the choice of the movement as different circumstances may lead to different choices: a pedestrian stuck in a jam may try to go in the opposite direction searching for an alternative path, a lost pedestrian may start a random walk or looking for other floor fields.
We represent pedestrian behavior with a deterministic finite automaton (DFA)3. Our automaton M is a 4-tuple (Q; E; ; q0), where:
E a list of events;
: Q E ! Q a transition function; q0 2 Q an initial state.
The set of states Q is partitioned into four subsets: 1) Sleeping: only one state (sleeping); 2) ContextEvaluation: only one state, the pedestrian is collecting data to achieve spatial awareness; 3) M ovementEvaluation: the pedestrian is aware of its situation and it is evaluating all the possible alternatives; 4) M ovement: nine states belong to this subset, one for each direction;
Also the events belonging to E are partitioned into four subsets, as every event can be associated to only one pair of states.
4) Pedestrian movements: We now focus the attention on the modeling of how our pedestrians evaluate the possible movements and how they choose the best movement.
pedestrians can change their position along nine directions (keeping the current position is considered a valid option), into the cells belonging to their Moore neighborhood of range r = 1. Each possible movement has a value called likability that determines how much the move is good in the terms of the criteria previously introduced.
In order to keep our model simple and reduce complexity, we do not consider multiple speed. At each iteration a pedestrian can move only in the cells belonging to the Moore neighborhood, reaching a speed value of 1 or can maintain the position (in this case speed is 0)4.
b) Functions and notation: In order to fully comprehend the pedestrian behavior introduced in the following paragraphs, it is necessary to premise the notational conventions and the functions we have introduced in our modelization: cx;y defines the cell with (valid) coordinates (x; y); F loors is the set of the targets instantiated during the simulation. Each target has a floor field and they share the same floorID (i.e. with t 2 F loors we define both the target and the associated floor field); Groups the set containing the groupID of the groups instantiated during the simulation dynamics; Classes is the set containing all the group classes declared when defining the scenario; Directions is the set of the possible directions. Are nine, defined using cardinal directions: fN; N E; E; SE; S; SW; W; N W; Cg.
Given x 2 [0; xsize 1] and y 2 [0; ysize 1], we define some functions useful to determine the characteristics and the status of the cell cx;y: cell walkability: this function determines if the cell cx;y is walkable or not (e.g. if there is a wall). If the cell is walkable the function returns the value 1, otherwise it returns 0. It is defined as follows: l1(cx;y) = [0; xsize
1] [0; ysize 1] ! f0; 1g : 0 if the cell is not walkable,1 otherwise; (1) floor field value: this function determines the value of the floor field t in the cell cx;y. If the cell contains the target associated to the target t, the function returns the value 256. If there is no floor field available for the target t the function returns the value 0. If a valid floor field is present the function return its 3We are not modeling all the features of a deterministic finite automaton: we are not recognizing languages and we do not have accepting states. 4Our pedestrians can move only to the cells with distance 1 according to the Tchebychev distance. value, which is defined in the interval [1; 255]: l2(cx;y; t) = [0; xsize 1] [0; ysize 1] t 2 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 belonging to a particular group g specified as input. If a pedestrian belonging to that group is contained in the cell, the function returns 1, otherwise it returns 0: l3(cx;y; g) = [0; xsize 1] [0; ysize 1] g 2 groups ! [0; 1] : 0 if the cell does not contain a pedestrian belonging to the group g, 1 otherwise. (3) c) Observation fan: We define x;y;d as the set of cells that are observable according to the characteristics of the observation fan , used by a pedestrian located in the cell at coordinates (x; y) and looking in the direction d.
The overall likability of a possible solution can be thought as the desirability of one of the neighboring cells. The more a cell is desirable, the higher is the probability that a pedestrian will choose to move into that position. In our model the likability is determined by the evaluation of the environment and it is defined as a composition of a sequence of characteristics:
likability = goal driven component + group cohesion proxemic repulsion - geometrical repulsion + stochastic contribution
Formally, given a pedestrian belonging to the group class g 2 Groups, in the state q 2 Q and reaching a goal t 2 F loors, the likability of a neighbouring cell cx;y is defined as li(cx;y) and is obtained evaluating the maximum benefit the pedestrian can achieve moving into this cell (following the direction d 2 Directions) using the observation fan for the evaluation.
goal driven component: it is the pedestrian wish to quickly reach its destination and is represented with the floor field. Our model follows the least effort theory: pedestrians will move on the shortest path to the target which needs the least effort. This component is defined as l2(cx;y; t): it is the value of the floor field in the cell at coordinates (x; y) for the target t; group cohesion: it is the whish to keep the group cohese, 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 weight matrix: ci;j 2 x;y;d
X (group; d; (x; y); g) = wi;j l3(ci;j ; g) (4) geometrical repulsion: it represents the presence of walls and obstacles. Usually a pedestrian wishes to avoid the contact with these object and the movement is consequently influenced by their position. This influence is defined as the presence of walls (located in layer l1) inside the observation fan , according to the weight matrix for walls specified in the same observation fan: ci;j 2 x;y;d
X (walls; d; (x; y)) = wi;j l1(ci;j ) (5) proxemic repulsion: it is the repulsion due to presence of pedestrians, alone or belonging to other groups (e.g. strangers). A pedestrian whishes to maintain a safe distance from these pedestrians and this desire is defined as the sum of these people
in the observation fan , according to the weight matrix for the
group of these pedestrians:
stochasticity: similarly to some traffic simulation models (e.g.
[
Formally, these four influences compose the likability of a movement as follows: 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)
Group cohesion and floor field are positive components because they positively influence a decision as a pedestrian wishes to reach the destination quickly, keeping the group cohese at the same time. On the contrary, the presence of obstacles and other pedestrians has a negative impact as a pedestrian usually tends to avoid this contingency.
The formula 7 summarizes the evaluation of the aspects that characterize the likeness of a solution. A pedestrian for each possible movement opens an observation fan and examines the environment in the corresponding directions, evaluating elements that may make that movement opportune (e.g. the presence of other pedestrians belonging to the same group or an high floor field value and data that may discourage as the presence of walls or pedestrians belonging to other groups).
The simulated scenario consists in a rectangular corridor, 5m wide and 10m long. We assume that the boundaries are open and that walls 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 and 25 cells respectively. Pedestrians are generated at the east and west borders and their goal is to reach the opposite exit. Floor fields, environment geometry and generators are graphically represented in Figure 3.
We investigated the capability of our model to fit the fundamental
diagram proposed in the literature for characterizing pedestrian
simulations [
As shown in Figure 4 our model correctly represents the nature of pedestrian dynamics: if the frequency of generation is low, consequently the flow is low. Increasing the frequency leads to a higher throughput until a critical density has been reached. If the system density is increased beyond that value, the flow begins to decrease significantly as the friction between pedestrians make movements more difficult. Observing the same figure we can state that, before the critical density has been reached, the flow is fluid, similar to the laminar flow that can be see in the models of traffic simulation. After the value of critical density has been reached, the simulations underline a greater variability in the fundamental diagram. In fact, at higher density the possibility of events that may disrupt the flow are more frequent causing a sensible variation of the throughput.
This result is a first element of validation of the model; in addition,
the model has been validated against data (related to a specific
experimental setting, i.e., a specific density value) acquired in an
experimental observation [
We also performed additional qualitative observations of the dynamics generated by the model and we can state that it is capable to generate the following phenomena: lane formation at high densities; the higher is the number and the size of the groups into the environment, the lower will be the total flow, due to the higher degree of friction between different groups.
We were interest in studying the dynamics of friction and avoidance that are verified when two groups with different size, traveling in opposite directions, are facing each others in a rectangular shaped corridor. We simulated the 5m 10m corridor with one large group traveling from the left (west) to the right (east), opposed to one small group traveling in the opposite direction. The aim of this particular set up was to investigate the differences in the dispersion of the smaller 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 the small group as the challenging group and the large group as the opponent group.
We considered opponent group of five different sizes: 10, 20, 30, 40 and 50. Challenging groups were defined with only two sizes: 3 and 5. The results are consistent with the observable phenomena as the model can simulate all the three possible cases that can be spotted in the real world: the challenging group remains compact and moves around the opponent group; one or more members of the challenging group moves around the larger group in the other side with respect to the other members of the group; one or more members of the challenging group remain stuck in the middle of the opponent group and then the small group temporarily breaks up.
It is also interesting to point out that in our model, if a split is verified in the challenging group, when their members overcome the opponent group, they aim to form again a compact configuration. The actual size of the simulation scenario is however too small to detect this reforming of the group5. In Figure 5 are presented some images representing the state of the simulation at different time steps. As stated before, it is possible to observe the range of different circumstance that our model is able to simulate: for example, in 5, in the simulation #1 the challenging groups can overcome the opponent one simply by moving around it, the same situation is represented in simulation #2 and #4 but the challenging group experiences more friction generated by the opponents. In the same figure, the simulation #3 and #5 show a challenging group that splits in two and their members moving around the opponent group on both the two sides.
Finally, we investigated the relationships between the time necessary to the members of the challenging group to reach the opposite end of the corridor in relation with the size of the opponent group. As expected, and in tune with the previous observations, the larger the size of the opponent group, the higher time necessary to the members of the challenging group to reach their destination is. The difference of size in the challenging group only slightly influences the performances: it is easier to remain stuck in the opponent group but the difference between three and five pedestrians is insufficient to obtain significant differences.
The paper presented a CA based pedestrian model considering groups as a fundamental element influencing the overall system 5We carried out additional simulations in larger environments and we qualitatively observed the group re-union. dynamics. An original model considering a simple notion of group (i.e. a set of pedestrians sharing the destination of their movement and the tendency to stay close to each other) has been presented and applied to a simple scenario, gathering results that are in tune with the existing literature on this topic. Validation against real data is being conducted and preliminary results show a promising correspondence between simulated and observed data. Future works are aimed at a concrete application of the model in the context of the Crystals project and further extensions of the notion of group and related dynamics.