Adaptive pedestrian behaviour for the preservation of group cohesion

Crowds of pedestrians are generally recognised as a form of complex system (Batty 2001): even without making a serious attempt of providing a formal definition of the term crowd, and adopting a simplistic and common sense intuitive notion of “(too) many people in (too) little space” (Kruse 1986), the dynamics that can be identified in a crowded environment, in which several pedestrians move towards their own goals, are good indicators supporting this statement. Pedestrians share the same environment and they generally compete for the space resource; nonetheless, they can also exhibit collaborative patterns of interactions, for instance respecting (written or non-written) shared rules like giving way to passengers getting off a train before getting on board, or even respecting cultural dependant rules (e.g. gallantry). There are evidences of imitation among pedestrians whenever they need to cross a road (see, e.g., Helbing et al. 1997), but basic proxemic considerations indicate that normal behaviour includes a tendency to stay at a distance, to preserve a personal space (Hall 1966). Pedestrians continuously adapt their behaviour to the contextual conditions, considering the geometry of the environment but also social aspects. The overall crowd system, whose evolution depends on the individual decisions of pedestrians, shows several examples of self-organised behaviours, from the formation of lanes to oscillatory changes in the walking directions at narrow passages.

Computer models for the simulation of crowds are growingly investigated in the academic context and these efforts led to the implementation of commercial off-the-shelf simulators often adopted by firms and decision makers^a. Models and simulators have proved their adequacy in supporting architectural designers and urban planners in their decisions by creating the possibility to envision the behaviour of crowds of pedestrians in specific actual environments and planned designs, to elaborate what-if scenarios and evaluate their decisions with reference to specific metrics and criteria.

Despite the substantial amount of results and efforts this area is still quite lively and we are far from a complete understanding of the complex phenomena related to crowds of pedestrians in the environment: one of the least studied and understood aspects of crowds of pedestrians is represented by the implications of the presence of groups (Challenger et al. 2009). Pedestrians, in fact, exhibit a substantially different behaviour in a given scenario if friends or family members, for instance, are present in the same environment at the same time: they will try to reach the desired destination but they will also try to preserve a limited distance from the other group members, also temporarily neglecting the tendency to move towards their goals, in an interesting form of adaptive behaviour. In most current models, instead, pedestrians simply interpret the presence of other individuals as a sort of moving obstacle or simply as openers of a potential route to follow (in case of imitative behaviours). The research that is summarised in this paper is aimed at systematically evaluate the impact of the presence of groups in a population of pedestrians, also considering relatively large groups potentially structured into smaller sub-groups, performing the most appropriate form of validation (either quantitative or qualitative) against real data, coming from new observations or already present in the literature. While, in fact, some of the implications of the presence of groups, for instance on the walking speed of its members, have already been analysed, at least in low density situations (Federici et al. 2012; Schultz et al. 2010; Willis et al. 2004), the overall impact on other observable metrics such as space utilisation is still not clear. As previously suggested, we will talk about simple groups when referring to small sets of pedestrians bound by a strong relationship (e.g. friends, family members): the agents representing members of this kind of group are characterised by an adaptive behavioural mechanism aimed at preserving its cohesion, even in situations of high local density and presence of obstacles or counter flows of other pedestrians. The model we will introduce also considers larger groups, sometimes of “artificial nature” (e.g. groups of tourists), that can in turn be made up of other smaller groups (either structured or simple) or just by individuals: agents representing members of this kind of group are characterised by a tendency to stay close to other members but this tendency is not as strong as for simple groups and it does not necessarily prevent the fragmentation of groups.

The paper breaks down as follows: the following section will briefly report the most relevant related works, while a description of the introduced adaptive model for pedestrian behaviour encompassing the effects of group presence will follow. Section “Simulation results” will present the scenarios in which the model has been applied and the achieved results. Conclusions and future developments will end the paper.

We will not provide here a comprehensive overview of the different approaches and models for the simulation of pedestrian and crowd dynamics: scientific interdisciplinary workshops and conferences are in fact specifically devoted to this topic (see, e.g., the proceedings of the first edition of the International Conference on Pedestrian and Evacuation Dynamics (Schreckenberg and Sharma 2001) and consider that this event has reached the sixth edition in 2012) and it would be impossible to summarise all the relevant works present in the literature. On the other hand, we propose a schema classifying the different current approaches based on the way pedestrians are represented and managed. From this perspective, pedestrian models can be roughly classified into three main categories that respectively consider pedestrians as particles subject to forces, particular states of cells in which the environment is subdivided in Cellular Automata (CA) approaches, or autonomous agents acting and interacting in an environment.

The most widely adopted particle based approach is represented by the social force model (Helbing and Molnár 1995), which implicitly employs fundamental proxemic (Hall 1966) concepts like the tendency of a pedestrian to stay away from other ones while moving towards his/her goal. Proxemics essentially represents a fundamental assumption of most modelling approaches, although very few authors actually mention this anthropological theory (notably CA based models (Ezaki et al. 2012; Was 2010) and an agent-based model (Manenti et al. 2010)). Recent works also extend the social force model for specific applications to evacuation scenarios in panic situations (Shiwakoti et al. 2196).

CA based approaches are based on a discrete representation of the simulated environment. Each cell represents a portion of the space and it can be either vacant, occupied by an obstacle or a single pedestrian (although there are models relaxing this constraint which allow more than a single pedestrian to be situated in a given cell at the same time). The management of system evolution is also based on a discrete representation of time, discretised in equally sized intervals of time (steps). A uniform transition rule guides the evolution of the system; the rule determines the next state of each cell considering its current state and the states of nearby ones (where nearby depends on a specific notion of neighbourhood, that is a function mapping every cell to a set of “visible” nearby cells). CA approaches can be roughly classified in ad-hoc models, that represent an effective and efficient solution but just for specific situations (such as the case of bidirectional flows at intersections described in (Blue and Adler 1999), in which there are specific “lane direction” rules) and more general models, that can be adopted for representing any kind of environment and pedestrian movement tendency, whose main representative is the floor-field approach (Schadschneider et al. 2002), in which the cells are endowed with a discretised gradient guiding pedestrians towards potential destinations.

While particle and CA based approaches are mostly aimed at generating quantitative results about pedestrian and crowd movement, agent based models are sometimes aimed at the generation of effective visualisations of believable crowd dynamics, and therefore the above approaches do not necessarily share the same notion of realism and validation. Works like (Bandini et al. 2004; Henein and White 2005) essentially extend CA approaches, separating the pedestrians from the environment and granting them a behavioural specification that is generally more complex than what is generally represented in terms of a simple CA transition rule, but they essentially adopt similar methodologies. Other approaches like (Musse and Thalmann 2001; Shao and Terzopoulos 2007) are more aimed at generating visually effective and believable pedestrians and crowds in virtual worlds. Finally, works like (Paris and Donikian 2009), employ cognitive agent models for different goals, but they are not generally aimed at making predictions about pedestrian movement for sake of decision support.

A relatively small number of recent works represent a relevant effort towards the modelling of groups, respectively in particle-based (Moussaïd et al. 2010; Xu and Duh 2010) (extending the social force model), in CA-based (Sarmady et al. 2009) (with ad-hoc approaches) and in agent-based approaches (Manzoni et al. 2011; Qiu and Hu 2010; Rodrigues et al. 2010; Tsai et al. 2011) (introducing specific behavioural rules for managing group oriented behaviours). All the above mentioned approaches interpret the impact of groups by means of additional contributions to the overall pedestrian behaviour representing the tendency to stay close to other group members. However, the above approaches mostly deal with small groups in relatively low density conditions; those dealing with relatively large groups (tens of pedestrians) were not validated against real data. The last point is a crucial and critical element of this kind of research effort: computational models represent a way to formally and precisely define a computable form of theory of pedestrian and crowd dynamics. These theories must be validated employing field data, acquired by means of experiments and observations of the modelled phenomena, before the models can actually be used for sake of prediction. The scarcity of data specifically characterising the behaviour of pedestrians in the presence of groups hinders this validation activity: for the present work we adopted the choice of validating the model in absence of groups with available data from the literature and exploring the effect of the introduction of groups with mechanisms and parameters that satisfied a (qualitative) face validation (Klügl 2008) against available video footages of groups of pedestrians (Federici et al. 2012) and preliminary data from experiments in controlled situations (Vizzari et al. 2012).

This section formally introduces a model representing pedestrian behaviour in an environment, considering the impact of the presence of simple and structured groups in the simulated scenario. The model is characterised by a discrete representation of the environment and time evolution, essentially based on floor-field CA approaches. Nonetheless, the pedestrian behavioural specification is so articulated, encompassing even an adaptive mechanism for the preservation of group cohesion, to the point that the model is more properly classified as agent-based. The different elements of the model will now be introduced, starting from the adopted representation of the environment and simulation evolution strategy. Then groups, pedestrians and the mechanism for the evaluation of available actions will be described. Finally, the adaptive mechanism for the preservation of group cohesion will be introduced.

Representation of the environment

The physical environment is represented in terms of a discrete grid of square cells: E n v = c₀, c₁, c₂, c₃, … where ∀c _i :c _i  ∈ Cell. The size of every cell is 40cm × 40cm according to standard measure used in the literature and derived from empirical observation and experimental procedure (Fruin 1992; Weidmann 1993). Every cell has a row and a column index, which indicates its position in the grid: $\mathit{\text{Row}}\left(c_i\right),\mathit{\text{Col}}\left(c_i\right):\mathit{\text{Cell}}\to \mathbb{N}$. Consequently, a cell is also identified by its row and column on the grid, with the following notation: E n v_j,k = c: (c ∈ Env) ∧ (Row(c) = j) ∧ (Col(c) = k).

Every cell is linked to other cells, that are considered its neighbours according to the Moore neighbourhood, that is all the cells surrounding the cell being considered, even in diagonal directions: it is possible to express Moore neighbourhood as joining of orthogonal cells, also called Von Neumann neighbourhood, and diagonal cells.

Every cell in the environment can be in three possible states: free, occupied by an obstacle, or occupied by a pedestrian. In the third case the cell contains also a reference to the specific pedestrian occupying it: State(c) = s : s ∈ FREE, OBSTACLE, PEDESTIAN _i . In addition to the potential presence of physical objects (pedestrians and obstacles) each cell is also linked to additional structures that contain information useful to support pedestrian movement.

Definition of spatial markers

Space can be annotated at design-time with different markers, a set of cells that play particular roles in the simulation. Three kinds of marker are defined in the model:

• start areas, places (sets of cells) were pedestrians are generated: they contain information for pedestrian generation both related to the type of pedestrians and to the frequency of generation. In particular, a start area can generate different kinds of pedestrians according to two approaches: (i) frequency-based generation, in which pedestrians are generated during all the simulation according to a frequency distribution; (ii) en-bloc generation, in which a set of pedestrians is generated at once in the start area when the simulation starts;

• destination areas, final places where pedestrians want to go;

• obstacles, non-walkable cells defining obstacles and non-accessible areas.

Space annotation allows the definition of virtual grids on the environment, as containers of information for agents.

Definition of floor fields

Adopting the approach of the floor field model (Nishinari et al. 2004), the environment of the basic model is composed also of a set of superimposed virtual grids, structurally identical to the environment grid, that contains different floor fields that influence pedestrian behaviour.

The goal of these grids is to support long range interactions by representing the state of the environment (namely, the presence of pedestrians and their capability to be perceived from nearby cells) in terms of field modifications. In this way, a local perception for pedestrians actually simply consists in gathering the necessary information in the relevant cells of the floor field grids. In other works, the concept of perception and its practical implementation is more sophysticated, starting from the definition of the field of view mechanism in humans: in (Paris and Donikian 2009) pedestrian’s perception is investigated from a cognitive point of view, while a more physical approach is adopted in (Shao and Terzopoulos 2007). Nonetheless, in CA based approaches such a precise perception model is rarely employed and still the achieved results are often extremely interesting, therefore we decided to employ a simple perception model and evaluate its adequacy.

Some of the floor fields are static (created at the beginning and not changing during the simulation) or dynamic (changing during the simulation). Three floor fields are considered in the model:

• the path field assigned to each destination area, that indicates for every cell the distance from the destination, acting thus as a potential field that drives pedestrians towards it (static floor field);

• the obstacles field, that indicates for every cell the distance from an obstacle or a wall (static floor field);

• the density field that indicates for each cell the pedestrian density in the surroundings at the current time-step (dynamic floor field).

All these fields can be seen as grids identical to the environment grid: a function that extracts the values of the fields for the given cell is defined as follows:

The following notation will be used to indicate these grids, assuming that pedestrians know only the path field associated to their own destination:

The definition of every type of floor field is now illustrated.

Path field

Each destination is associated to a path field indicating the shortest path between each cell in the environment and their destination. These floor fields act as a potential, driving pedestrian towards the destination (one floor field exists for every destination): starting from every destination defined in the scenario, the information are spread into the environment according to a particular method. In (Kretz et al. 2010) authors analysed different methods for the calculation of the distance potential field: starting from the considerations in this work, we decided to apply the chessboard metric to manage the Moore neighbourhood using the $\sqrt{2}$ variation over corners.

For every path field and for every cell, the value of the distance is calculated with this metric and it is associated to every cell: value increases if the distance increases.

Figure 1 proposes a graphical representation of the floor fields used in the model in a simple corridor scenario: in Figure 1a and 1b the path fields associated to destination areas (in blue) are proposed: darker tonalities indicate the approaching to the destination.

Graphical representation of different floor fields in a simple corridor scenario: Figures 1 a and 1 b represent two path fields associated to different destination areas. Figure 1c represents the obstacle fields provided by walls. Figure 1d and 1e show the density field with the related pedestrian position at a precise time step.

Full size image

Obstacle field

This floor field contains all the information related to the position of obstacles in the scenario: just one grid exists for all the non-walkable areas in the environment. Chessboard metric with $\sqrt{2}$ variation over corners is used also to produce the spreading of the information in the obstacle field: a particular radius r _ob is considered as the border of propagation of information about the presence of the obstacle.

The algorithm works as follows: after the initialisation of all the cell with a null value, the chessboard metric with $\sqrt{2}$ variation for all the cells that lie under the radius r _ob from the obstacle is calculated; r _ob represents therefore the maximum distance for which an obstacle generates a repulsive effect. A non-null value is then associated to these cells (i.e. higher values represent cells nearest to the obstacles) according to the following functions:

Figure 1c represents obstacle field in which lightest values indicate the approaching to the obstacles (in red).

Density field

The grid associated to this field contains information necessary to the management of interaction between pedestrians and to the calculation of statistics related to the local densities in the environment.

In general, the concept of density is usually related to the number of persons in a fixed portion of space: despite that, density can be measured in different ways and the concept of mean density in a particular cell of the scenario has to be analysed more in detail. In the pedestrian dynamics literature, the concept of cumulative mean density (CMD) indicates the density experienced by pedestrians in a cell: the concept was first introduced in (Still 2000), where the author defined that CMD is measured only when a pedestrian passes over there, by counting the number of people in the surroundings of the pedestrian (given a distance range). At the end of simulation, average on all the measurements is computed for each of the cells of the space. It is a local and pedestrian-based concept of density, that gives information about how pedestrian experiences the nearby space, ignoring the time periods in which a portion of space has been empty.

In (Castle et al. 2011), CMD evaluation in LEGION^b and STEPS^c software is analysed and compared: in LEGION, the surrounding of a pedestrian is identified into a radius r = 1.5 m with an area^d of Area = r² ∗ Π = 7.07m². STEPS adopts a similar approach calculating the density in a discrete way using the cells that fall within r = 1.25 m of each persons: the area considered is Area = r² = 6.25m².

In our model, the management of density field is a bit more complicated with respect to previous cases. It is modified according to the following mechanism: when a pedestrian p moves in a cell c, the density field is modified in the grid adding 1 to the cell in which he/she moves, and subtracting 1 from the cell he/she just left. The modification is applied also to neighbour cells in a range given by a radius r = 2 m (equal to five cells from c, considering the proposed scale of discretisation), but the value added/subtracted decreases with the inverse of the square of the distance between the cell and p:

Figures 1d and 1e represent the density field (in which lightest values that indicate highest values of the density) and an instant position of agents, respectively.

Simulation time and update strategy

Simulation time is modelled in a discrete way by dividing time into steps of equal duration: we assume that a pedestrian moves exactly 1 cell per time step. The average velocity of a pedestrian, which can be estimated through observations or experiments (Fruin 1992) in about 1.2 m s^-1, will thus determine the duration of the each time step: considering that the size of the cell is 40cm×40cm, the duration of each time step is thus 0.33s.

Note that in this way, the maximum of velocity allowed in this model is 1.2m s^-1: different works (Kirchner et al. 2004; Weng et al. 2006) investigated how variations in the pedestrian velocity (1.0ms^-1 and 1.5ms^-1) can be modelled with CA approach and how these choices influence simulation results. It must be emphasised that, however, this parameter is not strictly embedded in the model and it could be changed, essentially modifying only the analysis and results interpretation phases.

When running a CA-based pedestrian model, three update strategies are possible (Klüpfel 2003):

• parallel update, in which cells are updated all together;

• sequential update, in which cells are updated one after the other, always in the same order;

• shuffled sequential update, in which cells are updated one after the other, but with a different order every time.

The second and third update strategies lead to the definition of asynchronous CA models (see (Bandini et al. 2012) for a more thorough discussion on types of a-synchronicity in CA models).

In crowd simulation CA models, parallel update is generally preferred (Schadschneider et al. 2009), even if this strategy can lead to conflicts that must be solved. Some works (Kirchner et al. 2003) claim even that simulations are more realistic if the conflicts that arise are not solved, but to prevent the movement of all pedestrians involved in a conflict with a certain probability.

In their pioneering work, (Gipps and Marksjö 1985) used a sequential update, despite that (Blue et al. 1999) point out that “with sequential updates the order of each move becomes unrealistically important, since as each entity moves, the next entity re-positions in relation to the previous entity. Thus, the first entity would act the position of all entities over the whole lattice”.

Nonetheless, we chose to investigate the effects of allowing the possibility of this form of micro coordinated movements and therefore we adopted a shuffled sequential update scheme for the activation of agent behaviours according to the fact that one of the elements involved in the prediction of movement is the previous position of the pedestrian in the environment and that conflicts may be represented by proxemic separation, rather than space exclusion.

Please note that the structure of the model and the defined mechanisms remain valid in case of a parallel update scheme: the model would only need the definition of a mechanism and strategy to manage conflicts to support this schema. Of course, this different choice would have an impact on the simulation results and thus on the calibration phases and a comparison among these different approaches can be pointed out.

Groups

As suggested in the introduction, we focus on two types of group: simple and structured. Simple or informal groups are generally made up of friends or family members and they are characterised by a high cohesion level, moving all together towards the same goal due to shared goals and to a continuous mechanism of adaptation of the chosen paths to try to preserve the possibility of performing non-verbal communication (Costa 2010). Structured groups, instead, are more complex entities, usually larger than simple groups (more than 4 individuals) and they can be considered as being composed of sub-groups that can be, in turn, either simple or structured. Structured groups are often artificially defined with the goal of organising and managing the movement (or some kind of other operation) of a set of pedestrians.

Groups can be formally described as:

Structured groups include at least one subgroup, while simple groups only comprise individual pedestrians. We will refer to the group an agent a directly belongs to as G _a , that is also the smallest group he belongs to; the largest group an agent a belongs to will instead be referred to as $\overline{G_a}$. It must be noted that $\overline{G_a}=G_a$ only when the agent a is member of a simple group that is not included in any structured group.

Pedestrians

In this model, a pedestrian is defined as an utility-based agent with state. Functions are defined for utility calculation and action choice, and rules are defined for state-change. Pedestrians are characterised as:

where:

1. 1.
   $$\mathit{\text{Id}}\in \mathbb{N}$$

   is the agent identification number;

2. 2.
   $$\mathit{\text{GroupId}}\in \mathbb{N}$$

   is the identification number of the group to which the pedestrian belong to; for pedestrians that are not member of any group this value is null.

3. 3.

   State that represents the state of the agent related to its position in the space and to its attitude with respect to the simulated scenario. It is defined as:

   $$\mathit{\text{State}}:〈\mathit{\text{Position}},\mathit{\text{PrevDirection}}〉$$

where Position indicates the current cell in which the agent is located, and PrevDirection is the direction followed in the last movement;

1. 4.

   Actions is the set of possible actions that the agent can perform. Possible actions are movements in one of the eight neighbor cells (indicated as cardinal points), plus the action of remaining in the same cell (indicated by an ‘X’):

   $$\mathit{\text{Actions}}=\left\{N,S,W,E,\mathit{\text{NE}},\mathit{\text{SE}},\mathit{\text{NW}},\mathit{\text{SW}},X\right\}$$

Admissible actions AdmAct _p (⊆ Actions) are all the actions that move the pedestrian p from cell c in cells that are free at the moment it is updated:

The effect of each action is to move the pedestrian p in the direction indicated. This means that when an action a is chosen (for example, N), the new cell is calculated as follows:

When the movement is completed, the cell is marked as occupied, and the old cell is marked as free:

The last effect of an action is to update the density field by reducing density in the surroundings of oldCell and increasing it in the surroundings of newCell;

1. 5.

   Destination is the goal of the agent in terms of destination area. This term identifies the current destination of the pedestrian: in particular, every destination overlaps with a set of cells that are defined as destination areas by means of the appropriate spatial marker. Destination is used to identify which path field is relevant for the agent:

   $$\mathit{\text{currentPathField}}=\mathit{\text{PathField}}\left(\mathit{\text{Destination}}\right)$$

where PathField is the precise path field associated to Destination and currentPathField is the path field relevant for the agent.

All these elements take part in the mechanism that manages the movement of pedestrians: as previously introduced, they are essentially utility-based agents. To every movement in the cell neighbourhood a value of utility is associated, according to a set of factors that concur in the overall dynamics.

Mechanism of action evaluation

In Algorithm 1 the agent life-cycle during all the simulation time is proposed: every time step, every pedestrian perceives the values of path field, obstacle field and density field for all the cells that are in its neighbourhood. On the basis of these values and according to different factors, the agent evaluates the different cells around him, associating an utility value to every cell and selects the action for moving into a specific cell.

Algorithm 1 Agent life-cycle

As previously suggested, the action selection strategy starts gathering the value of floor fields in cells included in the neighbourhood of agent’s current position. The obtained values will be used in the evaluation of the movement towards the related cell.

After acquiring the perceived information from the environment, the agent elaborates a desirability value for each of the admissible actions (movements), according to several factors and more precisely:

• the desire to move towards a goal, a destination in the environment;

• the tendency to stay at a distance from the obstacles (e.g. walls, columns), that are perceived as repulsive;

• the desire to stay at a distance from other individuals, especially those that are not members of the same simple group, an effect of proxemic separation;

• a direction inertia factor, increasing the desirability of performing straight forms of movement;

• the penalisation of those movements that cause an overlapping event, the temporary sharing of the same cell by two distinct pedestrians;

• two contributions related to the tendency to preserve group cohesion, respectively devoted to simple and structured groups.

All the above contributions, which will be more thoroughly described in the following part of this section, are considered by the overall utility function U _a (c) of a destination cell c which corresponds to an action/direction for agent a, that takes the form of a weighted sum of components associated to the above factors:

where d is the distance of the new cell from the current position, that is 1 for cells in the Von Neumann neighbourhood (vertically and horizontally neighbour cells) and $\sqrt{2}$ for diagonal cells: the factor is introduced to penalise the diagonal movements. Note that κ _g , κ _ob , κ _s , κ _d , κ _ov , κ _c , κ _i  ∈ [0, 100]: the use of these parameters, in addition to allowing the calibration and the fine tuning of the model, also supports the possibility of describing and managing different types of pedestrian, or even different states of the same pedestrian in different moments of a single simulated scenario.

Given the list of possible actions and associated utilities, an action is chosen with a probability proportional to its utility. In particular, the probability for an agent a of choosing an action associated to the movement towards a cell c is given by the exponential of the utility, normalised on all the possible actions the pedestrian can take in the current turn:

where N is the normalisation factor and c is the currently considered destination cell.

Every element that contributes to the utility calculation will now be formally described.

Goal attraction

Agents are driven towards their goal using information derived from the related path field, calculating the distance between their current cell and the destination area. The function that manages the goal attraction evaluates the reduction of distance moving from cell Position in cell c where x = Row(Position), y = Col(Position), i = Row(c) and j = Col(c):

where ∀ c ∈ Cells, G(c) ∈ [-1, 1].

Obstacle repulsion

The interaction between agents and obstacles and non-accessible areas in the environment has negative impact towards the movement, because of the tendency of pedestrians to manage the available space without walking too close to obstacles and walls: for instance, considering the scenario of a corridor, pedestrians tend to stay in the centre instead of close to the walls. Information for the location and influence of obstacle are associated to the obstacle field introduced in Section “Obstacle field”. Considering a cell c with i = Row(c) and j = Col(c),

where ∀ c ∈ Cells, Ob(c) ∈ [-1, 0] and r _ob is the maximum distance for which an obstacle generates a repulsive effect.

Proxemic separation

All the interactions among pedestrians are subjected to the proxemic separation relationship, stating that all the persons tend to maintain a certain distance with respect to others and according to the local density calculated, stored and maintained into the grid of the density field. According to Proxemic theory (Hall 1966) the public distance among pedestrians is between 3.0 m and 6.0 m. Considering a cell c with c = Env_i,j:

where DensF_i,j is the value of the density field for the cell c and MaxDensity is the maximum global density value that the density field can assume, according to the radius r used in its definition. Output of S function are in the [-1,0] range. In our case, the value of MaxDensity that can be reached with a discretisation of 40 cm × 40 cm is equal to 6.25 m^-2 with r = 1.

Direction inertia

This factor represents the fact that pedestrians tend to maintain the direction during movement towards a destination. Unexpected changes of direction are usually avoided by pedestrians: for this reason, a value is added in the case that cell c is located in the same direction with respect to the previous movement (except the case in which agent remained in the same cell, i.e. PrevDirection = X):

where D(c) is the direction in which the agent must move to reach cell c from the current position.

Overlapping extension

CA-based models are characterised by a limit to the maximum manageable density that also limits their possibility to effectively represent highly crowded situations. A relaxation to the non-interpenetration principle, allowing the overlapping of two pedestrians in a single cell, was investigated as a means to overcome this limit in a controlled and systematic way (Klüpfel 2003). We adopted this approach, allowing pedestrians to transiently overlap with a small probability: at each time step (a maximum of) two pedestrians are allowed to stay on each cell.

State TWO _PEDS_i,j indicates that cell c is occupied at the same time by agent i and agent j. The set of admissible actions AdmAct is modified allowing that also cells already occupied by one other pedestrian are admissible cells, for j ∈ Pedestrians:

With this extension, we want to model the fact that in some situations, especially in high densities, pedestrians rotate their body to pass in tight spaces. So, densities higher than the limit of 6.25 m^-2 are allowed, because of the maximum possible density is 12.5 m^-2, thought those parameters must be finely calibrated to prevent unreasonable (and not justified by empirical evidences) crowding conditions. Overlapping also influences the calculation of utility function U _a (c), assigning a penalty if the overlapping occurs:

Because of overlapping event can happen just in particular situation of densities, a trade-off function on the basis of the density value in the scenario is defined, managing the calibration of overlapping event k _ov according to contextual factors (essentially the local density):

where i = Row(c), j = Col(c), DensF_i,j is the value of density field in the cell c, δ _high and δ _low are the two density thresholds that regulate the activation of overlapping. Please note that a zero value for the κ _ov parameter does not mean that the overlapping comes without costs, on the contrary it means that the overlapping is not allowed. Therefore, the overall Balance function gradually makes the overlapping phenomenon more likely with the growth of the local density.

Cohesion for simple groups

A positive contribution to the evaluation of the utility of a given cell can be assigned whenever the movement towards that point of the environment is able to reduce the perceived distance from other members of a simple group. The overall reduction of distance is essentially an aggregation of the reduction of distance from all other members of the group; more formally the value of the C _a function for a given cell c, an agent a member of group G _a is defined as follows:

where η is a normalisation factor that, along with numerical values, allows to translate the cohesion value into the range [-1,1], and DistFunction is a function that represents the gain of agent a with respect to agent a _i belonging to the same group G _a , moving into cell c. In the case of the evaluation of group cohesion, the perception of agents is expanded: every agent is able to perceive the members of the same group considering a distance parametric value g _d . DistFunction is so defined as:

representing the gain that agent a obtains moving in a particular cell c with respect to agent a _i .

Inter group cohesion

The role of this component of the utility associated to a movement is to increase the desirability of choices that reduce the distance from the members of the structured group the agent belongs to (if any). The form of the function is therefore relatively similar to the one associated to the cohesion of simple groups, with a significant difference: the larger a group is the more difficult is to perceive its “centre” and also its direction. Moreover, ties between members of a large, possibly artificial group, are plausibly less influential than those binding members of a simple group. Therefore we decided to reduce the overall effect of cohesion for very large groups. We also support the definition of a hierarchical structure of groups and we exploit this structure when computing the value for this contribution to the overall utility of a given movement.

Considering an agent a, let us remind that by ${\bar{G}}_a$ we denote the largest group agent a belongs to; it could be a highly structured group including a subgroup, simple or structured, to which a directly belongs to, or it could even be equal to G _a , should a be member of a simple group not belonging to any structured group. Considering this notation, an I _a (c) function for a given cell c, is defined as follows:

where function $\mathit{\text{DistFunctionI}}{\bar{G}}_{a,a_i}$ works on the tree-structure of the macro-group, identifying the proximity of two sub-groups G _a and $G_{a_i}$ (i.e. the groups agents a and a _i directly belong to) in the tree of the group structure by means of the detection of the nearest common root of the two groups in $\bar{G}$.

More formally:

where mcg is the smallest sub-group of ${\bar{G}}_a$ including both G _a and $G_{a_i}$.

Adaptation mechanism for group cohesion preservation

While the above elements are sufficient to generate a simple pedestrian model that considers the presence of groups, even structured ones, the introduced mechanisms are not sufficient to preserve group cohesion, as discussed in a previous work adopting a very similar approach (Bandini et al. 2011). This is mainly due to the fact that in certain situations pedestrians adapt their behaviour in a more significant way than what is supported by simple and relatively small modifications of the perceived utility of a certain movement. In certain situations pedestrians perform an adaptation that appears in a much more decisive way a decision: they can suddenly seem to temporarily loose interest in what was previously considered a destination to reach and they instead focus on moving closer to (or at least do not move farther from) members of their group, generally whenever they feel that the distance from them has become excessive. In the following, we will discuss a metric of group dispersion that we adopted to quantify this perceived distance and then we will show how it can be used to adapt the weights of the different components of the movement utility computation to preserve group cohesion.

Group dispersion metrics

Intuitively, the dispersion of a group can be seen as the degree of spatial distribution of their members. In the area of pedestrian modelling and simulation, the estimation of different metrics for group dispersion has been discussed in (Bandini et al. 2011) in which different approaches are compared to evaluate the dispersion of groups through their movement in the environment. In particular, two different approaches are compared here: (i) dispersion as occupied area and (ii) dispersion as distance from the centroid of the group. This topic was also considered in the context of computer vision algorithms (Schultz et al. 2012), in which however essentially only line abreast patterns were analysed. Therefore we will focus on the former approach.

Formally, the above introduced formulas of group dispersion for each approach are defined as follows:

with Area(Group) as the area occupied by the group, Size(Group) as the number of its members, centroid as its centroid. Results underline that the second approach suffers the effect of particular configurations in which the value of cohesion appears as low while a face validation of the situation indicates a good group cohesion. These wrong evaluations are detected in particular in medium and high-density situations in which groups tend to stretch themselves to walk through bottlenecks or narrow walkable areas. The centroid method identifies groups as highly disperse under these conditions, because some pedestrians can be far from the centre of the group.

Differently, the first metric, that can appear as more simple, defines the dispersion of the group as the portion of space occupied by the group with respect to the size of the group. Figure 2 illustrates how this metric works: the first step works on all the vertices (i.e. the members of the group, see Figure 2a), building a convex polygon with the minimum number of edges that contain all the vertices. The second step works on this output, calculating the area of the convex polygon (see Figure 2b). The dispersion value is calculated as the relationship between the polygon area and the size of the group.

Graphical representation of a group composed of nine members (a) and the area of the convex polygon that contains all the group members (b).

Full size image

Trade-off analysis

A trade-off between the goal attraction and the intra-inter group cohesion is necessary to preserve group cohesion: in the situation in which the spatial dispersion value is low, the cohesion tendency has to be less influential than the goal attraction on the overall pedestrian behaviour. On the contrary, if the level of dispersion of group is high, the cohesion component is more important than the goal attraction. An adaptation of the two related parameters in the utility computation is necessary, by means of a Balance(k) function that can be used to formalise these requirements:

where k _i , k _g and k _c are the weighted parameters U _a (c) and

is another function that works on the value of group dispersion as the relationship between the area and the size of the group, applying on it the hyperbolic tangent (assuring values in the [0,1) interval for the considered range of values for group dispersion). The value of δ is a constant that essentially represents a threshold above which the adaptation mechanism starts to become more influential; after a face validation phase, we set this value to 2.5, allowing the output of DispBalance function in the range [0,1] according to all elements in U _a (c). The hyperbolic tangent approaches value 1 when Disp(Group) ≥ 6 (values ≥6 indicate a high level of dispersion for small-medium size groups (1-4 members)).

A graphical representation of the trade-off mechanism is shown in Figure 3: red and green boxes represent the progress of parameter k _c and parameter k _g (k _i is treated analogously), respectively. Note that the increasing of the dispersion value produces an increment of k _c value and a reduction of k _g parameter.

Graphical representation of Balance(k) , for k = 1 and δ = 2.5 .

Full size image

Furthermore, according to (Xu and Duh 2010), the value of separation among group members has to be modified, on the basis of the assumption that pedestrians within a group allow to stay more close each other with respect to strangers: more in detail, the value of separation in a group is equal to the half among strangers.

The S function must therefore be substituted by a S _a function, considering these social aspects. In particular, this function is defined as follows:

where SepGroup _a (c) provides the value to discount to the separation repulsion on the basis of the group to which the agent a belongs to (the case in which agent does not belong to a group is also expressed):

It must be emphasised the fact that this adaptive balancing mechanism and the current values for its parameters were heuristically established and they actually require a validation (and plausibly a subsequent calibration) by comparing results achieved with this configuration and relevant empirical data about group dispersion gathered from actual observations and experiments in controlled situations.

This section describes the results of a simulation campaign carried out to evaluate the performance of the above described model that had mainly two goals: (i) validate the model, in situations for which the adaptation mechanism was not activated (i.e. no simple groups were present in the simulated population), (ii) evaluate the effects of the introduction of simple groups, performing a qualitative face validation of the introduced adaptation mechanism considering available video footages of the behaviour of groups in real and experimental situations.

The chosen situations are relatively simple ones and they were chosen due to the availability of relevant and significant data from the literature. In particular, the first one is a linear scenario, a corridor in which we test the capability of the model to correctly reproduce a situation in which two groups of pedestrians enter from one of the ends and move towards the other. This situation is characterised by a counterflow causing local situations of high density and conflicts on the shared space. We essentially evaluate and validate this scenario by means of a fundamental diagram (Schadschneider et al. 2009): shows how the average velocity of pedestrians in a section (e.g. one of the ends of a corridor) varies according to the density of the observed environment. Since the flow of pedestrians is directly proportional to their velocity, this diagram is sometimes presented in an equivalent form that shows the variation of flow according to the density. In general, we expect to have a decrease in the velocity when density grows; the flow, instead, initially grows, since it is also directly proportional to the density, until a certain threshold value is reached (also called critical density), then it decreases. Despite being of great relevance, different experiments gathered different values of empirical data. Consensus on the shape of the function is wide, but the range of the possible values has even significant differences from different versions, as you can see in Figure 4 showing a set of different diagrams, both lines related to design manuals (namely Predtechenskii and Milinskiı̆ 1978; Weidmann 1993) and also data points related to experimental measurements (respectively carried out in the context of the Hajj in Saudi Arabia by (Helbing et al. 2007) and in the city of Osaka, in Japan, by (Mori and Tsukaguchi 1987)).

Empirical fundamental diagrams for pedestrian movement in planar facilities as reported by design manuals ((Weidmann 1993 ) – WM – and - (Predtechenskii and Milinskiı̆ 1978 ) – PM) and also data points related to experimental measurements (respectively carried out in the context of the Hajj in Saudi Arabia by (Helbing et al. 2007 ) – Helbing – and in the city of Osaka, in Japan, by (Mori and Tsukaguchi 1987 ) – MT).

Full size image

The second scenario in which the model has been tested is instead associated to a situation in which pedestrians have to perform a turn and two different flows have to merge: geometrically, it is represented by a T-Junction also depicted in Figure 5, in which two branches of a corridor meet and form a unique stream. Also in this kind of situation it is not hard to reach high local densities, especially where the incoming flows meet to turn and merge in the outgoing corridor. The main goal of the analysis of the model behaviour in this scenario was the evaluation of its capability to generate patterns of spatial utilisation (i.e. aggregated density maps resulting from the single individual trajectories adopted by the pedestrians) that are in good agreement with those resulting from the actual observations available in the literature (Zhang et al. 2011).

T-junction scenario.

Full size image

We investigated both scenarios with a significant number of simulations, varying the level of density by adjusting the number of pedestrians present in the environment, so as to analyse different crowding situations. For every scenario, in terms of environmental configuration and level of density, a minimum of 3 and a maximum of 8 simulations were executed, according to the variability of the achieved results (more simulations were run when the variability was high, generally around levels of density close to the critical thresholds). Every simulation considered at least 1800 simulation turns, corresponding to 10 minutes of simulated time. The rationale was to observe a good number of complete paths of pedestrians throughout the environment, that was configured to resemble a torus (e.g. pedestrians completing a movement through it re-entered the scenario from their starting point), therefore simulations of situations characterised by a higher density were also set to last longer.

As suggested above, for both the scenarios, we adopted two different experiment settings: in the first one, the individual pedestrians belonging to a given flow (i.e. all the pedestrians entering the corridor or the T-junction from one end) are represented as members of a large structured group, but no simple groups are present. This first part of the experimentation was also necessary to perform a proper calibration of the model, for the parameters not involved in simple group modelling. In the second experimental setting, we included a variable number of simple groups (based on the total number of pedestrians in the environment and according to available data on the frequency of groups of different size in a crowd (Federici et al. 2012; Moussaïd et al. 2010))^e first of all to calibrate and qualitatively validate the adequacy of the adaptation mechanism and then to explore its implications on the overall crowd dynamics.

The model has been implemented as an improvement of MAKKSim (Bonomi et al. 2011), an already existing simulation platform consisting of an extension to the Blender 3D modelling and rendering system. MAKKSim extends Blender by means of a set of Python scripts realising the model and simulation engine, in addition to support tools like algorithms for the semi–automatic generation of the fields starting from a CAD file and some specific spatial annotations defined through Blender’s user interface. A complete description of this system and its performance is out of the scope of this paper and it is object of current and future works: we just conclude this introduction to the achieved results by clarifying that the performance of the MAKKSim simulation engine is strongly bound to the number of simulated pedestrians. Situations characterised by a low level of density required less than 5 minutes to be completed, whereas high density situations required more than two hours.

Linear scenarios

This scenario proposes the analysis of the model performance when a bidirectional flow of pedestrians crossing a corridor is simulated. More in detail, the analysis of the flow is performed on three different linear scenarios with a variation of size in terms of width and height. The configurations taken into account are related to a linear corridor with size 2.4 m × 20 m (A), 3.6 m × 13.3 m (B) and 4.8 m × 10 m (C). Note that the variation in terms of width and height were applied according to the choice of maintaining the total area equal to 48 m² in every scenario. In particular, between the first and the second configuration the values of width and height were respectively multiplied and divided by 1.5, while between the first and the third configuration the values where respectively multiplied and divided by 2.

Figures 6, 7 and 8 show three fundamental diagrams, one for each environmental configuration, in which blue and red points respectively represent pedestrian flow without and with groups. Each point is associated with a simulation run of at least 10 minutes; in each run a pedestrian performs the crossing of the corridor a number of times, but when the density grows, in order to preserve the number of crossings, we need to increase the simulated time. Therefore, runs performed with higher density conditions had to be longer than those representing low density situations. Finally, we performed more runs in the density situations close to the critical threshold, since in those situations the results were characterised by the highest level of variability.

Fundamental diagrams with and without groups in corridor A.

Full size image

Fundamental diagrams with and without groups in corridor B.

Full size image

Fundamental diagrams with and without groups in corridor C.

Full size image

All the diagrams properly represent changes in the flow with respect to the level of density. The range for the critical value of density belongs to the interval [1.8-2.3] m^-2 in the situation without group, in tune with experimental results and empirical data from the literature.

About the impact of groups, a variation of flow in case of groups with respect to the case without group has to be analysed. Considering charts in Figures 6, 7 and 8, it is possible to note that the level of critical density reached by the flow without groups is higher with respect to the flow with groups: in the latter, the value of critical density belongs to the interval [1.5-1.8]m^-2. This means that the flow without groups increases until values in the interval [2.0-2.2]m s^-1 while the flow with groups until value in [1.5-2.0]m s^-1.

Considering these analyses, the presence of groups can be interpreted as a negative factor on the flow dynamics. This trend is maintained for a level of density < 2.5m^-2.

Differently, for higher densities (from 2.5m^-2 to 4.0m^-2), the presence of groups has a little impact on pedestrian flow: in Figures 6 and 7 it is possible to note that higher level of flow are assigned to situations with groups with respect to situations without groups. The behaviour in terms of speed and the detection of lanes explains the variation in the fundamental diagrams on the overall density interval. Also preliminary analyses on experimental data discussed in (Manenti et al. 2011) support these results, that might seem counterintuitive, showing that the presence of groups and, in particular, of couples, can positively influence the pedestrian flow.

The impact of groups can be analysed more in detail considering the singular influence of every type of group (according to its size) to the pedestrian flow with the goal to understand if a relationship exists between the size of the group and its (negative) contribution to the overall pedestrian dynamics.

To achieve this goal, data related to the different types of simulated groups were aggregated, and a comparison among the related fundamental diagrams was performed. As summary, Figure 9 represents on the same chart all group contributions: unlike the previous diagrams, the depicted points (and the connecting line) represent the average flow achieved for that kind of group in the total simulated time.

Comparison among fundamental diagrams on aggregate data with respect to groups of different size in corridor A.

Full size image

The choice of evaluating the influence of groups in different linear scenarios was also inspired by (Zhang et al. 2011), in which a comparison in terms of pedestrians flow from experimental data among three corridors of width 1.8 m, 2.4 m and 3.0 m is presented. In this case, authors show that, in conformance with (Hankin and Wright 1958), above a certain minimum of about 1.22 m, the maximum flow is directly proportional to the width of the corridors.

We have chosen to expand the width of the corridors considering the comparison among sizes of 2.4 m, 3.6 m and 4.8 m. Figure 10 represents the three different fundamental diagrams in case of groups: these results are in tune with the above mentioned theory about the dependency between maximum reachable flow and the width of a corridor. In particular, in the case of corridor C, relevant variations can be detected around the critical density value. After that value, the influence of width on the pedestrian flow seems to be not relevant, probably due to the activation of overlapping extension to deal with high density situation (Section “Overlapping extension”) and to the phenomenon of lane formation.

Comparison among corridor widths: fundamental diagrams in case of groups in corridors A, B and C.

Full size image

Both in the linear and corner scenarios an analysis on the effectiveness of the mechanism to manage group cohesion is required: as previously introduced in Section “Trade-off analysis” a balance mechanism regulating the tendency to reach the goal and the tendency to stay cohesive with group members works on a metrics by evaluating group dispersion as ratio between the area occupied by the group and its size.

Finally, we analysed the relationship between the increase of the density and the level of group dispersion. The adopted indicator for the dispersion of groups is the one introduced in Section “Group dispersion metrics”, that is, the area actually occupied by the group, computed as shown in Section “Group dispersion metrics”. We found out that the density does not significantly influence the group cohesion: dispersion in couples is always in the interval [0.2-0.4]m², dispersion in triples in the interval [0.9 - 1.3]m² and dispersion in groups of six in the interval [5.0 - 5.6]m². This means that the mechanism to manage group cohesion works well, decreasing the tendency to reach the goal to preserve group cohesion. Figure 11 shows the comparison between dispersion values in groups of six in the three different linear scenarios. While in corridor B and C the dispersion of this kind of group is comparable, in corridor A the width definitely impacts on the variability on the dispersion of groups that belong to the interval [5.1 - 7.1]m². It must be noted that, in order to effectively validate the group cohesion mechanism we would need empirical data on the level of dispersion of groups in this kind of scenario and in different situations.

Comparison among the level of dispersions for group of six members in corridor A, B and C.

Full size image

T-junction scenario

The central result of this scenario is not represented by fundamental diagram data, but rather by an indication on how the pedestrians employed the available space throughout the simulation. In particular, we adopted a metric is called cumulative mean density (CMD) (Castle et al. 2011), a measure associated to a given position of the environment indicating the average density perceived by pedestrians that passed through that point. It is quite straightforward to compute this value in a discrete approach like the one described in this work. As suggested above, we wanted to evaluate the capability of the model to reproduce patterns of spatial utilisation that are in good agreement with those resulting from the actual observations available in the literature (Zhang et al. 2011). In this work an analysis on spatial dynamics of the motion of pedestrians in an experimental observation carried out on a T-junction scenario is performed by means of topographical information for density profile according to CMD values. The density in the T-junction is not homogeneous and a higher density region appears near the junction. The lowest density region is located at a small triangle area, where the left and right branches begin to merge. The density in the branches (near to starting areas) are not uniform and are higher over the inner side. From this point of view, pedestrians prefer to move along the shorter and smoother path.

Our model is able to reproduce the phenomenon: a comparison between the two different density profiles from one run of a simulation with an overall density equal to 2.5m^-2 is shown in Figure 12 (a). It can be noted that our model represents well the use of the space by pedestrians and their trajectories. The maximum CMD reaches is the same in the two density profile, and equal to 4.5m^-2.

Density profile for simulations in the T-junction scenario without simple groups (a) and in presence of simple groups (b) .

Full size image

In Figure 12 (b), instead, we propose the results of the simulations carried out in the same scenario but introducing simple groups, in the same proportion of the previous scenario: while qualitatively the diagram looks similar to the previous one, the highest level of density is actually sensibly lower and in general the CMD is lower in most parts of the environment. This result is interesting because the lower level of CMD suggests that in turning and merging situations characterised by an overall high level of density the impact of simple groups could be significant and beneficial for the overall flow. We further analysed this phenomenon by performing a set of simulations varying the density of pedestrians in the environment and the resulting fundamental diagram is shown in Figure 13: in low to moderate densities the presence of simple groups slightly reduces the overall flow of pedestrians, but in high density conditions the presence of simple groups actually makes the flow of pedestrian smoother than in the situation only including large structured groups. However, once again, it must be stressed that, in order to effectively validate the group cohesion mechanism, we would need empirical data also on the spatial patterns of movement in this kind of scenario and in different situations.

Comparison among the fundamental diagrams of experiments not including simple groups and including a set of simple groups of variable size.

Full size image

Finally, in Figure 14 we also report a graph showing the variations in the level of group dispersion in different situations characterised by a different level of density. As for the linear scenario, the level of dispersion does not seem to present a straightforward relationship with the level of density: it seems to increase at density levels close to the critical density, but then it seems to decrease to physiological levels (considering the size of the group).

Comparison among the level of dispersions for groups of different size in the T-junction scenario in different density conditions.

Full size image

The paper presented a model for the adaptive behaviour of pedestrians that are members of simple groups, that is, groups of friends and/or relatives. These pedestrians need to adapt their behaviour, namely reducing their goal orientation in order to preserve the cohesion of the group. The paper has formally introduced the model and discussed results that were compared to the available empirical data and relevant literature in absence of effects from the newly introduced mechanism and it has explored the effects of its introduction, after a face validation of its adequacy. The simulation results suggest that the effect of the presence of groups in the simulated population is not so simple to evaluate, since in the analysed situations the pedestrian flow is reduced due to the presence of groups only in low to moderate levels of density, while in high density situations the presence of groups might be even beneficial, smoothening the overall pedestrian flow.

Future works are aimed, on one hand, at achieving empirical data supporting an empirical validation and subsequent calibration of the group cohesion mechanism and then at further extending the model, for instance for representing the movement of elderly and special groups (like elderly and accompanying person), but also leader/follower schemes.

^asee http://www.evacmod.net/?q=node/5 for a significant although not necessarily comprehensive list of simulation platforms. The list includes over 60 models, commercial and academic, general purpose or specifically targeted on certain situations and scenarios, maintained or discontinued.^bLEGION is the most famous and used commercial software for pedestrian dynamics simulation, see http://www.legion.com/legion-software.^cSTEPS is an agent-based micro-simulation tool developed by Mott MacDonald for the simulation of pedestrian movement under both normal and emergency conditions, see http://www.steps.mottmac.com/.^dNote that LEGION works on continuous representation of environment, so the area is calculated as the circular area around the pedestrian.^eGroups of size 2 include about 28% of the total number of pedestrians, groups of size 3 about 24% and groups of size 6 about 12%.