Pedestrian Trajectories and Collisions in Crowd Motion

Abstract

In several biological systems, crowding can occur (ants, bees, birds, fishes, people, etc.). In human societies, crowding affects several aspects of our lives. Human crowds are considered to be one of the most complex systems. Their dynamics, resulting from individual interactions and giving rise to fascinating phenomena, is often difficult to understand and hard to model, which intrigues experts from different fields. The technological advancement, especially in computer performance, has allowed to model and reproduce pedestrian movement more realistically. Nowadays, researchers from different disciplines, such as social sciences and bio-mechanics, are better equipped to examine and understand the crowd movement and pedestrian interactions. Professionals from architects and transport planners to fire engineers and security advisors are also interested in crowd models that allows them to optimize the design and operation of a facility. In the phase of modelling pedestrian and crowd movement, the role of mechanics is prime. Using the principles of mechanics, the necessary equations of new models are derived so that scientists are able to simulate pedestrians’ cognitive and behavioral mechanisms as observed by psychologists and sociologists. Finally, it is worth mentioning that by only using the equations from collision theory, several collective phenomena were well reproduced.

A 2D microscopic approach for crowd movement modeling has been studied and applied for ten years now. This collective research is reported in [3, 9, 10, 53–55, 66, 79–84].

The first idea was to use a granular media flow model based on the collision theory introduced in 1995 by Michel Frémond [31] and described in Chap. 2.

In this model the movement of the granular particles is in a 2D space and the particles, in the initial version, are rigid. Philippe Pécol [79], improved the granular media flow model to manage collisions in the trajectories of pedestrians. He compared the results of his model and other models to experiments in the case of urgent evacuations. The evacuation times given by his model are very satisfactory in the case of emergency.

More recently, Bachar Kabalan [53] addressed three new aspects. The first one concerns pedestrian navigation towards a final destination, the second one consists of managing pedestrian-pedestrian interactions and the last aspect is the validation and verification of the model.

The basis of this model is presented in what follows. Current research tracks are finally introduced but not detailed.

6.1 Definitions—Phenomena of Typical Crowd Self-Organization

A crowd is defined in the dictionary as a multitude of people united in the same location. A group of people in a crowd shares the idea of geographic proximity, but also possesses a collective conscience and intelligence. The thoughts and actions of each member of this group are all oriented toward the same goal, for example, the evacuation of a room. This is the primary characteristic of a crowd, unlike in a group in which varying motivations exist. Furthermore, the overall intelligence of a crowd is generally inferior to that of any one of its members. Reactions are guided by primary emotions (fear, anger, desire, joy) more than by reflective consideration of the circumstances.

Between isolated pedestrians and a dense crowd, other design scenarios include: light to heavy pedestrian traffic, groups of people walking together, parades, religious and political demonstrations, and sporting events such as marathons.

Usually, for relative dense crowds, the number of individuals, the time period of their movements, and the crowd density (people/m$^{2}$) are chosen in a way so as to exclude movements during which interaction is non-existent or only present for very short periods of time. In [27], for engineering practice, the authors even precised the definition of a crowd as a large group of individuals (${\ge }100$ people) within the same space at the same time, whose movements are for a prolonged period of time (${\ge }60$ s), and who is dependent on predominantly local interactions (density $\ge 1$ people/m$^{2}$).

Fig. 6.1

Two systems using a a centralized and b a decentralized mechanism [70]

Each individual in a crowd usually behaves according to his or her own motivations, without conforming to a leader’s orders or following a pre-established plan (Fig. 6.1a). Nevertheless, the behavior of an individual in a crowd is heavily influenced by that of the other individuals nearby. Although each individual is independent, all are interconnected by a vast network of interactions as illustrated in Fig. 6.1b. All the local interactions between nearby individuals give way to the global dynamic of the system. Such a system possesses emergent properties, i.e. collective behaviors that spontaneously appear on the group scale, without having been explicitly intended by the individuals. Accordingly, the movements of a crowd, as well as many other collective human behaviors (for example, automobile traffic, the spread of a rumor [59], the spread of sickness on networks [69, 74], or the evolution of opinions during an election, [62]), obey certain self-organization processes, several of which are described in the following paragraphs. Self-organization can be defined as the spontaneous emergence of a global structure triggered by local interactions between members of a system. There are four main mechanisms that play a role in self-organized systems, [15]:

• positive feedback or the snow ball effect, [70]: It is when an individual is encouraged to do a certain act since those who surround him are already doing it. Take for example the Mexican wave. It starts with a small group of fans then gets amplified to encompass the whole crowd of a football stadium;

• negative feedback: without this mechanism, positive feedback leads the system to a state of dynamic amplification without control. This mechanism counteracts the amplification effect to bring the system back to a stable state;

• random perturbations: if all members of a system had identical behavior, no positive and negative feedback can occur. Paradoxically, without random perturbations, no self-organization could take place, [44].

• multiple interactions: interaction between two individuals occurs when one acquires new information from another leading the former to modify his/her behavior in light of what he/she had just learned. These interactions can be direct without leaving a trace (visual, audio, or sensory signs) or indirect leaving a trace (trails, chemical deposits,...).

The first studies describing the behaviour of pedestrians walking in a crowd include both qualitative (e.g., the determination of pedestrians’ preferences) and quantitative (e.g., the walking speed or walking pace¹ of pedestrians) observations. These observations allow us to list certain behavioral characteristics of pedestrians as well as highlight and describe several phenomena of a crowd’s self-organization that occur in certain specific situations. The main goal of these studies was to develop guidelines for planning and designing pedestrian facilities. Before 1995, a number of simulation models have been proposed, e.g. queuing models and models for the route choice behaviour of pedestrians. None of these approaches adequately takes into account the self-organization effects occurring in pedestrian crowds. These may, however, lead to unexpected obstructions due to mutual disturbances of pedestrian flows, [38]. Since then, the different kinds of spatio-temporal collective motion patterns formed by pedestrian crowds due to the sensitive dependence of emerging pedestrian flows on the geometrical shape of pedestrian facilities have been investigated in detail. More recently, Hoogendoorn et al. [49], proposed a theory predicting self- organization, as well as results from experimental research that provide more insight into these dynamic phenomena. This theory of self-organization in pedestrian flow is based on the assumption that each pedestrian aims to minimize his or her predicted disutility of walking. So of all the available options (e.g. accelerating, decelerating, changing direction, doing nothing), a pedestrian tries to choose the one that will yield the smallest predicted disutility. It is referred to the principle of least effort, i.e. an individual will try to adapt to his or her environment or will try to change the environment to suit its needs, whichever is easier. The experimental research performed by these authors provides more insight into these dynamic phenomena as well as exposing other forms of self-organization, i.e. in case of over-saturated bottlenecks or crossing pedestrian flows. The resulting structures are similar to states that occur in granular matter and solids, including their imperfections (voids in granular flow also so-called vacancies²). Groups of pedestrians that are homogeneous in terms of desired walking speeds and direction seem to form structures consisting of overlapping layers. This basic pattern forms the basis of other more complex patterns emerging in multi-directional pedestrian flow: in a bi-directional pedestrian flow, dynamic lanes are formed which can be described by the layer structure. Diagonal patterns can be identified in crossing pedestrian flows. In [49], the authors both described these structures and the conditions under which they emerge, as well as the implications for theory and modeling of pedestrian flows.

Self-organization phenomena are macroscopic effects reflecting the pedestrians’ microscopic interactions. Some of the frequently observed ones are presented below.

When a pedestrian pathway narrows into a bottleneck, the individuals become more nervous and want to move faster. Individuals will push each other, causing the movement to become less fluid, the crowd denser, and the time necessary to traverse the bottleneck longer. This is the effect of faster is slower.

Fig. 6.2

Arch phenomenon in front of a door, based on [39]

Furthermore, when a dense crowd wants to traverse a narrow space, such as a door, the small space quickly becomes blocked and an arch of people forms around it. This is the partial blockage and arch phenomenon, illustrated in Fig. 6.2. In a pedestrian flow at the bottleneck entry, this effect may be caused by inefficient merging behaviour, e.g. due to overly polite or aggressive behaviour. Finally, when the crowd becomes very dense and immobile, the individuals shuffle in place. This is called the gridlock phenomenon.

In crowds of pedestrians moving along the same pathway but into opposite directions, lines of uniform walking direction are formed if the pedestrian density exceeds a critical value. These lines of pedestrians walking in a single line³ are naturally formed. They reduce pedestrian collision while increasing the pedestrians’ speed. This phenomenon is in Fig. 6.3, and will be called lane formation in counter flow.

Fig. 6.3

Lane formation in counter flow, based on [97]

Fig. 6.4

Formation of a single file during an evacuation, based on [81]

In addition, during an evacuation through one exit, the individuals will also arrange themselves one behind the other, in single file. This phenomenon is illustrated in Fig. 6.4.

Moreover, if the evacuation exit is traversed simultaneously by two crowds moving in opposite directions, the individuals composing each crowd go through the exit alternately, creating the oscillations. Oscillatory variations of the walking direction develop at narrow passages (corridors, staircases, or doors). The average oscillation frequency increases with growing width and decreasing length of the passage. This phenomenon is illustrated in Fig. 6.5, and will be called the oscillations phenomenon. It can be observed by watching the video on the following link (file oscillation.avi are available at https://ifsttar.libcast.com/mast-sdoa or at http://extras.springer.com). In this video, two groups arrive at a constant flow rate from two opposite sides of an opening. Each group want to pass to the other side, giving rise to an oscillation phenomenon around the opening.

Fig. 6.5

Oscillations phenomenon

Another effect is corner hugging, illustrated in Fig. 6.6: when pedestrians turn around an angle or a corner, they slow down and get closer to the corner thus increasing the local density of the crowd.

When individuals are in competition to evacuate a given space, the evacuation becomes ineffective, or individuals behave inappropriately, sometimes even aggressively. We describe this type of behaviour as competitive.

Fig. 6.6

Corner hugging based on [97]

6.2 The Current Methods for Modeling Crowd Movement

Due to its complex nature, crowd movement does not lend itself easily to mathematical modeling. The wide variation in walking styles, the unpredictable behaviour of one isolated individual, and the large number of individuals potentially interacting with each other make any rigorous formalization of crowd phenomena difficult.

Despite the complexity of human behaviour, numerous models have been developed in recent years, hoping to accurately simulate crowd behaviours and situations. Crowd movement models are ideally designed to reproduce every behaviour exhibited by pedestrians as well as all the observed phenomena of crowds, in particular those mentioned in the preceding section. Of course, the complexity of behaviors and observed phenomena forces each model to target only one or two specific applications. Modeling of all of these levels of behaviour necessitates a complex and demanding formalization, integrating a large number of cognitive processes such as perception, motor control, individual motivations, memory, capacity for reason, etc. In [27], the authors compared a large number (27) of crowd motion models of the last decades, thereby providing an overview of the current literature on crowd motion models of that time. Moreover, this type of models could provide interesting research tools for other domains such as artificial intelligence, experimental psychology and cognitive neuroscience; though the aims of these various fields differ and lie outside this work’s area of application.

Crowd movement models in comparison with those of the flow of granular media have certain specific features of which the two main ones are: pedestrian scheduling and route choice, and pedestrian-pedestrian interaction.

Pedestrian Scheduling and Route Choice

Some of the most interesting and challenging theoretical and practical problems in describing pedestrians behaviour are route choice and activity scheduling. Specific terms must be first defined in order to clarify how they will be employed in this work. According to [12], a route is a chain of consecutive nodes joined by links, connecting the origin, the intermediate destinations, and the final destination. This definition can be applied to discrete networks that are made up of links and nodes. However, pedestrians usually move freely in their environment choosing a route from an infinite set of alternatives without being restricted to certain lanes or nodes. In this case, a route is the trajectory of a pedestrian that started at an origin and ended at a destination. Compared to other modes of transportation, a characteristic feature of pedestrian route choice is that the trajectories are continuous in time and space. Since a pedestrian chooses a route from an infinite set of alternatives, appropriate theories and models describing the pedestrian route choice are required. A trajectory is the graphical representation of the motion of an object, in our case an individual. A pedestrian’s trajectory is usually obtained by saving his coordinates at each time step and finally connecting all the points (see Fig. 6.7). A shy away distance is the minimum distance that pedestrians keep with different elements of the surrounding environment (walls, obstacles, other pedestrians...). This distance depends on obstacle characteristics and the available space for pedestrians [23].

Fig. 6.7

Pedestrian trajectories in the case of a bottleneck

Pedestrian activity scheduling pertains to which, in which order, and where pedestrians perform activities. Pedestrian activity scheduling has not been studied comprehensively in the past. There are some indications that pedestrians somehow optimize the order in which they perform their activities, and that directness plays an important role [48]. Hill [45] has analyzed in 1982 pedestrian strategies for choosing and describing routes. He concluded that, like most walking processes, route selection strategies are largely subconscious. Furthermore, directness is the most prevalent reason for choosing a particular route. Route directness pertains not only to the length of the route, but also to its complexity (in terms of direction changes). Pedestrians appear to frequently choose the shortest route, though they are seldom aware that they have chosen to minimize distance as a primary strategy in route choice ([34, 92]). Observations carried out in Jerusalem by Guy [34], showed a strong tendency, by about two thirds of the subjects, toward the shortest distance route. Other studies indicated that besides distance, pleasantness is an important route attribute. The two attributes together produce a high correlation with the route preferences [12]. Other factors deemed important in route choice behaviour are habit, number of crossings, pollution and noise levels, safety and shelter from poor weather conditions, and stimulation of the environment. The extent to which these route attributes play a substantial role in his/her route choice behaviour depends greatly on trip purpose [12], e.g. scenery is very important for recreational trips, but it plays no role for work-related walking trips. Cheung and Lam [16] study pedestrians choosing between escalators and stairways in subway stations and its dependency on the differences in travel times. The authors showed that pedestrians are more susceptible to delays in the descending direction than in the ascending direction, and are more inclined to use the escalator in the latter case.

Given the complexity of the pedestrian route choice problem, it was necessary to divide it into sub problems. This has been done by creating different levels of route choice, identifying pedestrian behaviors in each one and finally modeling them.

Two main approaches for classifying route choice behaviour can be found in literature. In the first approach [23], pedestrian behaviour is classified into three categories : (i) the strategic level, which encompasses decisions an individual makes concerning general organization of his or her activities, such as first going to buy a train ticket and then going to buy a magazine [100]; (ii) the tactical level, which entails the integration of local topology and trip planning so as to complete all planned activities along the way [23, 47]; and finally (iii) the operational level, which concerns the short-term movements of the pedestrian and his or her interactions with the individuals who cross his or her path [37, 72, 101]. In the second approach, pedestrian behaviour is classified based on navigation as a function of distance. According to [35], three spatial scales exist for pedestrian navigation: (i) long range (10 $\sim$ 200 m), (ii) medium range (5 $\sim$ 50 m), and (iii) short range (1 $\sim$ 10 m).

The two approaches are very similar where the main difference is in the used notations. The first approach was used by Hoogendoorn [46, 47] to develop the normative pedestrian behaviour theory and is much more widespread in the literature. For this reason, it will be developed below. However, the second approach seems to us to be much simpler and easier to be conveyed and has been chosen in [53].

The Strategic Level

In most models, a pedestrian’s behaviour is influenced strictly by his/her surroundings or his/her local environment. In reality, people decide on which activities they want to perform and in what order even before entering a certain facility. Therefore they compute a preliminary path that will allow them to accomplish their objectives. For example, before arriving to a train station, a passenger might have already decided to first buy the ticket, then buy a newspaper and finally head to the platform. If the passenger is familiar with the environment, he/she would have already planned his route. If not, he/she can consult the train station’s plan. In [50], it is considered that this process takes place at a strategic level.

The Tactical Level

At the strategic level, a preliminary path is planned that passes by the chosen intermediary and final destinations. In the tactical level, at each decision point (intermediate destination) everything that was chosen at the strategical level is reexamined according to local conditions and circumstances such as weather, topology, traffic, etc. At this level, pedestrians might cancel certain activities and change their route. A traveler who risks missing his/her train would cancel all activities and head directly to the platform. To model this behaviour, an algorithm should be capable of organizing the activities to be done (obligatory or optional), localizing the areas where they can be accomplished (familiar with the environment or not), and computing the corresponding route.

The operational level

At the operational level, pedestrians interact with their surroundings. Once on the path chosen at the upper levels, an individual interacts with other pedestrians and obstacles that he/she crosses on his/her way. Therefore the pedestrian is forced to deviate from his/her original route. This can be observed by comparing an individual’s trajectory with his/her planned path. At this level, a pedestrian decides to walk, wait, or accomplish a task.

Pedestrian-Pedestrian Interaction

Among the different forms of interaction between pedestrians, the act of avoidance stands out as an essential component of the coordination of collective movement. This action constitutes a central element of the majority of pedestrian movement models.

Existing experimental studies allow one to compare predictions from a model with certain observed global characteristics, such as flow intensity, velocity distribution or emerging collective arrangements. However, in these experiments, the lack of control of the observed situation creates a major obstacle for the identification of interaction laws and the validation of underlying hypotheses. In a natural environment, the result of an interaction on a pedestrian’s spontaneous behaviour is difficult to quantify, given that the observer neither controls the terms of the interaction nor knows the pedestrian’s desired direction, attention level, or comfort velocity.

Several approaches have been developed to take into account avoidance in crowd movement modeling. The first one is based on physics: pedestrians are considered as particles moving according to a set of forces. An attractive force pulls the pedestrians towards their destination and a repulsive one allows them to keep a distance with other pedestrians and obstacles in order to avoid collisions. Force-based models have had great success in the academic world for many years. However, important limitations have then been identified. Indeed, it is hard to objectively evaluate the intensity of the different forces applied on pedestrians. Moreover, those models turned out to be unreliable for fitting experimental data. For instance, collisions are not well simulated: pedestrians tend to rebound against each other like rigid particles, which is of course far away from the observed phenomenon. A radically different approach has been recently developed [71]. It is based on cognitive science: the pedestrian is now considered as a cognitive agent, who is able to gather information from his/her environment through a defined vision field. His/her behaviour is then led by two decisions based on the presence of other pedestrians and obstacles and of course the position of his/her destination point. First, the pedestrian chooses the most direct path to his/her destination, taking into account the possible collisions with obstacles. Second, he/she maintains a minimal security distance to the first obstacle, in order to have enough time for an emergency stop. Thanks to the implementation of these behaviors, the cognitive models seem to be more consistent with empirical data than the force-based models.

The introduction of social physchological forces (repulsive forces) in the proposed model will be only presented here. Different approaches exist and are under study (cf. [53]).

Empirical evidence of the complexity of pedestrian behaviour within a rather dense crowd, as previously mentioned (clustering, lanes and queues), leads us to consider the first important distinction between the different methodological approaches: pedestrians as a flow and pedestrians as a set of individuals or agents.

Thus we distinguish two large categories: the macroscopic models and the microscopic models. In the first category, the crowd is described with fluid-like properties, giving rise to macroscopic approaches. Macroscopic models describe how density and velocity of the pedestrian flow change over time, using partial differential equations (Navier-Stokes or Boltzmann-like equations). This approach is based on analogies observed at medium and high densities. The second category concerns microscopic models, where collective phenomena will emerge from the complex local interactions between many individuals (self-organizing effects).

In this section, we are interested in pedestrian behaviour on the operational level, such as collision or jostling avoidance. Modelling methods that focus on the operational level can be classified according to various criteria (Table 6.1): the crowd representation, the pedestrians’ movement space representation, the pedestrian representation, the pedestrian contact representation, the pedestrian movement representation, the crowd phenomenon targeted for analysis, the type of crowd examined, etc. We have chosen to classify and present the operational level models according to the method of crowd representation.

Table 6.1 Criteria for classifying crowd movement models

6.2.1 Macroscopic Models

In macroscopic models, pedestrians demonstrate a collective behaviour and the crowd is considered as a single entity. These models can be classified into two sub-categories: regression models and models of fluid dynamics (liquid or gas).

Regression Models

In regression models, the significant pedestrian variables are generally the flow rate and the mean speed. The global movement of the pedestrians is formulated using statistical relations between the different variables of flow and depends upon the studied infrastructure and the specific circumstances of the movement [33, 65]. Different regression models are discussed in [75]. In order to better understand how this type of model functions, we examine the historical approach of service levels, introduced by Fruin [33]. To characterize each place of contact, Fruin develops a gradation of service levels. Each level corresponds to an interval of crowd density at an observed average flow, going from A, for the best, to F, for the worst (Table 6.2).

Table 6.2 Levels of service for walking from Fruin [33]

The characterization of each service level, with regard to the behaviour of the pedestrians, is as follows:

• A: Up to this density, each traveler can move at his or her desired speed, since collisions remain unlikely.

• B-C: The travelers can still move with relative ease, avoid conflicts and choose their speed.

• C-D: Passing other pedestrians becomes more difficult. The small distance separating one person from another causes the pedestrians to reduce their speed.

• D-E: This critical zone brings about a slow general speed. The travelers movement becomes irregular, up to the point where movement and other changes of direction are nearly impossible.

• E-F: Contact between pedestrians becomes unavoidable, preventing pedestrians from passing each other.

Fluid Dynamics Models

To illustrate fluid dynamics models [6, 9, 13, 51, 52, 87, 88], we have chosen the crowd model of Bodgi [9] as an example, in which pedestrians are represented as an entity by a compressible fluid. This approach is often found in vehicle traffic models. The crowd behaviour is observed at point M given by the coordinates (x, y, z) in an inertial or Galilean frame of reference. The variables used are local and dependent upon both the time t and the position of point M. In [9], the author considers only the spatial coordinate x (x $\in$ [0 ;  L] if one considers the longitudinal position of the pedestrians over a footbridge of length L). In this case, the crowd behaviour is similar to that of a compressible liquid governed by the partial derivative equation of the conservation of mass:

$$\begin{aligned} \frac{\partial \eta }{\partial t}+\frac{\partial }{\partial x}(\eta \, v)=0 \end{aligned}$$

(6.1)

where $\eta$ represents the local density of pedestrians and v their local velocity.

Since there are two unknown variable functions $\eta$ and v, a second partial differential equation is necessary to complete the system. This equation is generally called the closure equation, and relates the variables $\eta$ and v. Other fluid dynamics models are presented in [75].

In conclusion, macroscopic models are limited in that they cannot take into account the characteristics of each individual pedestrian, such as his or her position, direction of movement and physical attributes. Furthermore, if one considers the observation that the majority of individuals in a crowd move in small groups, this type of model is no longer well adapted to reproduce crowd behaviour. On the other hand, these models prove to be useful when the crowd is dense and one is interested in the movement of the crowd as a whole. Because of this, Bodgi [10] succeeded in using an analytical study deduced from her macroscopic model, to determine both the critical number of pedestrians that will trigger synchronization with a particular footbridge, and the displacement of the latter when the combined crowd-structure system reaches a stationary state.

6.2.2 Microscopic Models

In microscopic models, the movement of each individual is represented in space and time. Each individual behaves, makes decisions and interacts with others in a specific way. These models can be classified into five sub-categories: rule-based models, social force models, cellular automata models, discrete choice models, and completely mathematical models.

Rule-Based Models

Rule-based models, introduced by Reynolds [90], draw from the flight patterns of birds in a group in order to model a crowd. For this scenario, three rules describe the behaviour of birds keeping a certain distance from each other (Fig. 6.8): (i) separation: the birds do not collide; (ii) alignment: the birds attempt to maintain a common direction and speed; and (iii) cohesion: the birds try to remain united. The first rule, consisting in the avoidance of collision between birds (or pedestrians), has the consequence of allotting no importance to each individual’s shape or form.

Fig. 6.8

The three rules describing the behaviour of birds [90]: a separation, b alignment, and c cohesion

Social Force Models

The social force model [4, 36, 37, 39, 40, 60, 72, 76–78, 85], developed principally by Helbing, allows one to control the movement of each pedestrian by the use of three forces: acceleration, repulsion and (optionally) attraction (Fig. 6.9). In this model, a disc represents the pedestrian. If a pedestrian’s motion is not disturbed, the driving force of acceleration allows him or her to move toward his or her desired destination, with the acceleration oriented at every instant toward this target.

The introduction of repulsive forces is inspired from a granular approach [21]. Each pedestrian has a specific mass and direction, and a particular manner of walking he or she adopts depending on the surrounding environment (obstacles and other pedestrians). Because there is no spatial discretization in the zone of movement, the pedestrian can move continuously in a 2D environment.

This model is predominately used to simulate evacuation situations. Though it holds the advantage of a low complexity, it is not adaptable to situations of high-density crowds. In these scenarios, the pedestrians in the model oscillate in place due to the repulsive distance-creating force [85].

Fig. 6.9

Social forces acting on pedestrian i. The plotted forces are: the driving force of acceleration allowing the pedestrian to move in a certain direction with the desired velocity, the at a distance interaction force due to pedestrian j, and a similar force due to an obstacle; non plotted are repulsive forces allowing to avoid certain pedestrians or obstacles and attractive forces allowing to approach certain objects or people. The introduction of last forces allows to introduce more realistic behaviours in the crowd movement [37]

Fig. 6.10

Example of a simulation of a room evacuation performed with a cellular automata model [96]

Cellular Automata Models

In cellular automata models, the 2D movement zone of the pedestrians is discretized [8, 56, 57, 96, 103–105]. A uniform grid of cells contains inaccessible cells (obstacles), occupied cells (pedestrians), and empty cells (Fig. 6.10). At each time step, the pedestrians shift into a neighboring cell according to certain rules. There are two ways of moving pedestrians at each time step. In one way, the pedestrians move in turn (individual by individual) in a random manner. The model thus intrinsically controls for contact, since a pedestrian cannot move into an occupied cell. In the other, the positions of the pedestrians are updated globally (at the same time), and a random choice is made if two pedestrians wish to move into the same cell. One advantage of cellular automata models is their capacity to create simulations in broad spaces with a large number of pedestrians, due to the reduced time needed to calculate the simulations. Their largest inconvenience is their lack of realism: pedestrian movement is constrained by the grid and contact between pedestrians is not directly controlled.

Completely Mathematical Models

In Venel’s mathematical model of crowd movement [10], the pedestrians are represented by discs, move with their own directions and speeds, and are able to sidestep each other and obstacles. Contact between individuals is controlled by a geometrical constraint that prevents the overlapping of two pedestrians. The velocity of a pedestrian is computed by placing the spontaneous velocity within the set of admissible velocities (i.e., the velocities that do not violate the non-overlapping constraint). A desired velocity, updated at every instant, allows the pedestrians to go in the shortest direction to reach their destination. This simulation draws from a model of granular interactions, in which contacts between grains are inelastic collisions. The mathematical model is well adapted for dense crowds in evacuation situations.

6.3 The Proposed 2D Discrete Model

The non-smooth approach proposed by Frémond [24, 25, 31, 32] that has mainly been applied to the movement of granular media, has already been proven successful in managing collisions between rigid particles. This original approach was selected to treat the contact and to control the type of collisions among particles. It is based on the theory of collisions of rigid bodies, first proposed by Frémond [31, 32] in a rigorous thermodynamic framework, accounting for the dissipative aspects of collisions, see Chaps. 2–5. The description of the behaviour of a collection of discrete bodies is based on the consideration that the system made of the discrete bodies, even if they are rigid, is deformable because their relative distances vary. Frémond introduces the concept of the coefficient of dissipation to handle the rebound and the velocities of particles after each collision. Local interactions between particles are managed by the use of pseudo-potentials of dissipation, [68]. A further kinematic impenetrability condition is introduced to avoid overlapping, see Chaps. 2–5.

Thus our idea was to adapt it so as to represent pedestrians and their strategy of displacement. The developed model will handle local interactions, such as pedestrian-pedestrian and pedestrian-obstacle, in order to reproduce the global and real dynamics of pedestrian traffic. First, to control the crowd movement on the ground in this model, four targets had to be managed: (i) multiple simultaneous collisions, i.e. to detect and to treat each local interaction, such as pedestrian-pedestrian and pedestrian-obstacle; (ii) the desire of each pedestrian to move in a particular direction with a specific speed at each time; (iii) the possibility to add forces to make the behaviour of the pedestrians more realistic (social forces, subgroup forces, etc.); and (iv) the possibility to study the interaction of the pedestrians with the structure under crossing.

Only the first three targets will be presented in this section. Concerning the pedestrian-structure coupling, a differential equation of Kuramoto [89], allows one to manage the evolution of the pedestrians’ phase. This equation will allow the convergence of the instantaneous angular frequency of each pedestrian towards that of the structure under certain conditions. Preliminary results for the Millenium Bridge are given in [83].

Analytical studies are also developed in [9, 10, 79] to determine the critical number of pedestrians among which synchronization may be triggered and the displacement amplitude of the footbridge when the crowd-structure system has reached a stationary state. Pécol [79] performed similar analyses deduced from his microscopic model and both fully coupled approaches are compared in [55]. While both models used an equation of type Kuramoto to model the synchronization of the induced pedestrian force with the bridge’s movement, each one adopted a different sensitivity parameter. Bodgi [9] proved mathematically that pedestrians are sensitive to the acceleration of the bridge while Pécol [79] chose Strogatz’s approach [98] where pedestrians are sensitive to the displacement amplitude of the bridge.

6.4 Multiple Contacts’ Detection

In a discrete 2D crowd movement model, if the particles (pedestrians) are numerous and able to continually move in the studied space, an effective method of detecting contacts and nearby neighbors is necessary. Without such a method, the time needed for calculation would be much too long. In the following, we will consider only particle-particle interactions, since particle-obstacle interactions can be generated analogously.

To detect contacts between particles, two stages must be isolated:

• the determination of particle couples susceptible to coming into contact;

• the calculation of the distance between these two particles.

The complexity of this second stage depends upon the form of the modeled particles. Since pedestrians are represented by convex shapes, we will choose the particles to be circular, with a fairly large size. This is for two reasons. First, a disc represents decently well an individual seen from above and is a very simple shape. Second, from a more practical point of view, this shape reduces the calculation cost of the simulations, since it allows one to define in a simple fashion certain notions such as particles normal to each other and the relative distance between two particles. Nonetheless, it would be very much possible to consider other representations.

The relative distance $D_{ij}$ between the particles i and j, in a system of N particles moving in space, is directly defined by:

$$\begin{aligned} D_{ij}(\mathbf {x})=|\mathbf {x}_{j}-\mathbf {x}_{i}|-(r_{i}+r_{j}) \end{aligned}$$

(6.2)

where $r_{i}$ is the radius of particle i, and $|\mathbf {x}_{j}-\mathbf {x}_{i}|=\sqrt{\left( q_{j}^{x}-q_{i}^{x}\right) ^{2}+\left( q_{j}^{y}-q_{i}^{y}\right) ^{2}}$.

There is a contact between the particles i and j when $D_{ij}(\mathbf {x})=0$, and an overlap when $D_{ij}(\mathbf {x})<0$.

The first option is to test all the possible contacts (Fig. 6.11). This method is, of course, the most crude and basic. For a system of N particles, it would be necessary to test $\frac{N(N-1)}{2}$ particle couples, an operation number on the order of $O(N^{2})$. For example, when the number of considered particles is around or greater than $10^{4}$, it becomes necessary to calculate at least 49995000 distances for each time step of the integration scheme. In terms of calculation time, this would be very costly.

Fig. 6.11

Test of all possible contacts. The particle is red when its hasn’t been tested yet, yellow when it is being tested, and green when the possible contacts are found

Proposing a method that identifies all of the potential contacts creates a difficulty. This method must be efficient as to not consume the largest part of the calculation time. One can find numerous methods such as Delaunay triangulation [19, 99], Linked Cell Method (LCM) or Manhattan Boxes [30, 102], Verlet Neighbor List (VNL) [2, 73], Linked Linear List (LLL) or Sweep and Prune [73, 86, 91, 102] and robust methods [11, 28, 29, 73], often appearing as extensions of the methods previously cited. Some of these possess parallel versions that allow one to benefit from super-calculators [19]. The different detection algorithms will not be detailed here, even if they are of great interest.

In the following, we will briefly present several methods of contact detection.

Delaunay Triangulation [19, 99]

This method consists in creating a triangular network between the centers of the bodies in the system. This allows one to obtain directly all the edges corresponding to potential contacts (Fig. 6.12). The contacts are then determined by calculating the relative distance between particles in potential contact.

Fig. 6.12

Delaunay triangulation

Linked Cell Method (LCM) or Manhattan Boxes [30, 102]

This method consists in cutting up the particle evolution space into boxes of the same size, as a function of the size of the particles (Fig. 6.13). The particles are then distributed in their corresponding boxes. Contacts between particles, whether of the same box or of adjacent boxes, are determined by calculating the relative distance between these particles. If one follows the route of the boxes, not all the adjacent boxes will need to be covered, since detections between boxes could already have been made. This allows one to limit the number of tests realized. This method is more suitable for systems composed of equivalently sized particles. In an optimal configuration, the number of operations necessary to find the potential contacts is in the order of O(N).

Fig. 6.13

Manhattan boxes [102]

Verlet Neighbor List (VNL) [2, 73]

The main idea of this method is to design an imaginary circle around each particle in the system and then create a list of neighboring particles within the circle (Fig. 6.14). The relative distances between the particles are then calculated. The optimal extension of the circular zone around the particles depends on their speed and the density of the total system. Creating the list of neighboring particles necessitates $\frac{N(N-1)}{2}$ calculations, a number of operations of the order $O(N^{2})$. This method is thus more suited for quasi-static systems, in which the list does not need to be updated for all time steps. The frequency of updates depends on the density of the system, the velocity of the particles and the radii of the imaginary circles.

Fig. 6.14

VNL—imaginary circles and storage of particles in lists [73]

Linked Linear List (LLL) or Sweep and Prune [73, 86, 91, 102]

This method plays out in three stages. The first consists in creating rectangular boxes that completely encompass each particle, and which have sides aligned in parallel along an axial system. In the second stage, each box is separately projected onto the axial system. Finally, a potential contact is determined for all boxes whose projections overlap the two axes (Fig. 6.15). This method is difficult to implement. However, in an optimal configuration [102], the number of operations necessary to find the potential contacts is in the order of O(N). This method is well suited for systems composed of differently sized particles.

Fig. 6.15

LLL—visualisation of encompassing boxes, their projections onto the axial system, the determination of the overlapping of the projections on the axes, and the determination of potential contacts [102]

Finally, the capabilities of these methods are compared in [73, 99]. The methods of Manhattan boxes and Delaunay triangulation demonstrate the best performances. In the model presented below, we have chosen to use Delaunay triangulation.

6.5 Presentation of Three Approaches to Granular Media

A granular medium is defined as a set of particles subjected to gravity that interact with each other via contact, with or without friction and with or without cohesion. In this section, three approaches generally applied to modelling granular media will be briefly presented and compared. They are denoted by $\textit{DEM}$ (Discrete Element Model), $\textit{NSM}1$ (Non Smooth Model 1) and $\textit{NSM}2$ (Non Smooth Model 2).

We assume then that the particles are restricted to moving in a plane, circular with a fairly large size, and with negligible rotation. One can refer to [24] for supplementary research on particles of more complex shapes and to [3, 79] for the full 2D case with rotation.

Let us consider a system of N circular particles moving in a plane. The center position of the ith particle is described by the vector $~^{t}\mathbf {x}_{i}=(q_{i}^{x},q_{i}^{y})\in \mathbb {R}^{2}$, $r_{i}$ is its radius, and $\mathbf {U}_{i}(t)=\frac{d\mathbf {x}_{i}(t)}{dt}$ is its velocity. When the generalized displacement vector $\mathbf {x}$ of size 2N, $^{t}\mathbf {x}=(^{t}\mathbf {x}_{1},^{t}\mathbf {x} _{2},...,^{t}\mathbf {x}_{N})$, is assumed to be a regular function of time, the dynamics equation for each particle can be written as the following differential system

$$\begin{aligned} \left\{ \begin{array}{rl} \dot{\mathbf {x}}(t) &{} =\mathbf {U}(t) \\ \mathbf{M }\,\dot{\mathbf {U}}(t) &{} =\mathbf {f}(t)+ \mathbf {g}(t) \\ &{} \end{array} \right. \end{aligned}$$

(6.3)

where M is the $2N\times 2N$ mass matrix of all the particles; $\dot{\mathbf {x}}$ denotes the generalized velocity vector of size 2N, $^{t}\dot{\mathbf {x}}=(^{t}\dot{\mathbf {x}} _{1},^{t}\dot{\mathbf {x}}_{2},...,^{t}\dot{\mathbf {x}}_{N})$, $^{t}\mathbf {U}=(^{t} \mathbf {U}_{1},^{t}\mathbf {U}_{2},...,^{t}\mathbf {U}_{N})$, and $\mathbf {f}$ (resp. $\mathbf {g}$) is the vector of at a distance forces (resp. contact forces) of size 2N applied to the system, or $^{t} \mathbf {f}=(^{t}\mathbf {f}_{1},^{t}\mathbf {f}_{2},...,^{t} \mathbf {f}_{N})$ (resp. $^{t}\mathbf {g}=(^{t} \mathbf {g}_{1},^{t}\mathbf {g}_{2},...,^{t}\mathbf {g}_{N})$).

Two major steps exist in each of the three approaches: the detection and the treatment (processing) of every contact. We will analyze only particle-particle interactions, since particle-obstacle interactions can be handled analogously.

In the case of circular particles, the detection of contact is straightforward. Let us introduce the unit vector $\mathbf {e}_{ij}$ directed from particle i to particle j by $\mathbf {e}_{ij}=\frac{\mathbf {x} _{j}-\mathbf {x}_{i}}{\Vert \mathbf {x}_{j}-\mathbf {x}_{i}\Vert }$. The distance $D_{ij}$ between two particles i and j can be expressed as:

$$\begin{aligned} D_{ij}(\mathbf {x})=\Vert \mathbf {x}_{j}-\mathbf {x}_{i}\Vert -(r_{i}+r_{j}) \end{aligned}$$

(6.4)

where $\Vert \mathbf {x}_{j}-\mathbf {x}_{i}\Vert =\sqrt{ \left( q_{j}^{x}-q_{i}^{x}\right) ^{2}+\left( q_{j}^{y}-q_{i}^{y}\right) ^{2} }$.

When particles i and j are in contact: $D_{ij}( \mathbf {x})=0$ and when they overlap: $D_{ij}(\mathbf {x})<~0$. If the number of considered particles increases, an efficient method of detection of contacts [28], or closest neighbors becomes necessary to reduce computation time. However, due to the relatively small number of considered particles in the simulations presented in this section, the use of such a method is not necessary in our research.

The next step is to determine the contact force vector $\mathbf {g}(t)$ in order to find $\mathbf {U}(t)$ and $\mathbf {x}(t)$. In $\textit{DEM}$, the local contact force between two particles i and j is chosen to be proportional to $D_{ij}$, whereas in $\textit{NSM}1$, it is defined so that particles never overlap, i.e., there is a constraint on the particles’ position. Additionally, in $\textit{NSM}2$, the local contact force is determined by a constraint on the relative deformation velocity between particles. Differences and similarities in contact treatment (processing) among the three approaches are detailed both analytically and numerically in the following sections. It will be shown that both the discretization of the $\textit{NSM}1$ and $\textit{NSM}2$ approaches constitute constrained minimization problems.

6.5.1 Theoretical Aspects of the Three Approaches

DEM

In the smooth approach introduced by Cundall in the seventies [21, 22], contact is treated using regular forces. The expression of the repulsive force applied to particle i, which represents local interaction via contact between particles i and j, is given by:

$$\begin{aligned} \mathbf {g}_{ij}(t)=k\min \left( 0,D_{ij}(\mathbf {x}(t))\right) \, \mathbf {e}_{ij}(t) \end{aligned}$$

(6.5)

where k is a stiffness constant. For crowd simulations, $k=1.2\times 10^{5}$ kg s$^{-2}$ is chosen by Helbing et al. [39].

The total contact force applied to particle i is thus:

$$\begin{aligned} \mathbf {g}_{i}(t)=\sum \limits _{\begin{array}{c} j=1 \\ j\ne i \end{array}}^{N}{ \mathbf {g}_{ij}(t)~.} \end{aligned}$$

(6.6)

With this approach, overlapping is required to control the contact. If there is no overlap between particles i and j ($D_{ij}( \mathbf {x})>0$), then $\mathbf {g}_{ij}=\mathbf {0}$.

NSM1

In this approach [63], contact between circular particles is treated as purely inelastic collisions, i.e., no rebound is considered. Extension of this approach to include other types of collisions (elastic collisions) is not straightforward, as mentioned by [63]. The particles’ positions must always be admissible, i.e., there should never be any overlap between particles. At the instant of collision, there is a discontinuity in the velocity $\mathbf {U}$. Hence, the velocity after collision, $\mathbf {U}^{+}$, is determined such that the position of colliding particles is feasible, i.e., $\mathbf {U}^{+}$ has a geometric meaning rather than a physical meaning.

The particles velocities after contact, $\mathbf {U}^{+}$, must belong to the set of admissible velocities defined by:

$$\begin{aligned} C_{\mathbf {x}}=\left\{ \mathbf {v}\in \mathbb {R}^{2N}:\forall i<j,\ ~^{t} \mathbf {G}_{ij}(\mathbf {x})\, \mathbf {v}\ge 0\ \text {as soon as}\ D_{ij}(\mathbf {x})=0\right\} \end{aligned}$$

(6.7)

$$\begin{aligned} \begin{array}{rl} \quad \text {where}\ \ \ ~^{t}\mathbf {G}_{ij}(\mathbf {x}) &{} =\nabla D_{ij}( \mathbf {x}) \\ &{} =\left( 0,...,0,-~^{t}\mathbf {e}_{ij},0,...,0,~^{t}\mathbf {e} _{ij},0,...,0\right) \in \mathbb {R}^{2N}~. \\ &{} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \quad \ \ \ \ \ \ \uparrow \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \uparrow \\ &{} \ \ \ \ \ \ \ \quad \ \ \ \ \ \ \ \ \ \text {particle }i\ \ \ \ \ \ \ \text { particle }j \end{array} \end{aligned}$$

(6.8)

Thus, since overlapping is forbidden by virtue of the condition $~^{t} \mathbf {G}_{ij}(\mathbf {x})\,\mathbf {U}^{+}\ge 0$, two particles i and j already in contact can only increase or preserve their relative distance. The polar cone $N_{\mathbf {x}}$ of $C_{\mathbf {x}}$ is then introduced [63, 67]:

$$\begin{aligned} \begin{array}{rl} N_{\mathbf {x}} &{} =\left\{ \mathbf {w}\in R^{2N},\ ~^{t}\mathbf {w}\ \mathbf {v}\le 0\ \ \ \forall \mathbf {v}\in C_{\mathbf {x}}\right\} \\[7pt] &{} =\left\{ -\sum \limits _{i<j}\mu _{ij}\,\mathbf {G}_{ij}(\mathbf {x}),\ \ \mu _{ij}=0\ \,\text {if}\, \ D_{ij}(\mathbf {x})>0,\ \mu _{ij}\in R^{+}\ \text { if}\ D_{ij}(\mathbf {x})=0\right\} ~. \end{array} \end{aligned}$$

(6.9)

The system (6.3) is rewritten using a differential inclusion:

$$\begin{aligned} \left\{ \begin{array}{ll} \mathbf{M }\ \, \dot{\mathbf {U}} + N_{\mathbf {x}} \ni \mathbf {f}, &{} \\ \mathbf {U}^{+}=P_{C_{\mathbf {x}}}\, \mathbf {U}^{-}, &{} \end{array} \right. \end{aligned}$$

(6.10)

where $P_{C_{\mathbf {x}}}$ is the Euclidean projection onto the closed convex cone $C_{\mathbf {x}}$. A solution of this problem was shown to exist [7, 64].

When there is no contact, the first equation of (6.10) reads as the ordinary differential equation $\mathbf{M }\ \,\dot{\mathbf {U}}= \mathbf {f}$. When there is a contact, the previous equation can be read as $\exists \mathbf {g}\in - N_{\mathbf {x}}\$, such that $\mathbf{M }\ \,\dot{\mathbf {U}} = \mathbf {f}+\mathbf {g}$, where the expression of the total contact force is $\mathbf {g}=\sum \limits _{1\le i<j\le N}\mu _{ij} \mathbf {G}_{ij}(\mathbf {x})$. The second equation of (6.10) provides the collision model. The velocity after contact $\mathbf {U}^{+}$ is then defined as the Euclidean projection of the velocity before contact $\mathbf {U}^{-}$ on the set $C_{\mathbf {x}}$. This approach allows us solve the following constrained minimization problem:

$$\begin{aligned} \mathbf {U}^{+}= \begin{array}{c} \arg \min \\ \mathbf {v}\in C_{\mathbf {x}} \end{array} \left[ \frac{1}{2}\Vert \mathbf {v}-\mathbf {U}^{-}\Vert _{\mathbf{M }}^{2}\right] \end{aligned}$$

(6.11)

where $\Vert \mathbf {y}\Vert _{\mathbf{M }}^{2}=~^t\mathbf {y}\ \, \mathbf{M } \ \,\mathbf {y}$.

$\textit{NSM2}$

$\textit{NSM}2$ is an original approach based on the theory of the collisions of rigid bodies, first proposed in [31, 32] a rigorous thermodynamic frame highlighting the dissipative character of collisions. The numerical aspects were later developed in [24, 25].

Let us consider the set of N particles as a deformable system composed of N rigid solids. Collisions among particles can be inelastic or elastic. Friction forces can also be considered, [25, 32]. The relative deformation velocity between the ith and jth particles in contact at point $A_{i,j}$ is defined by

$$\begin{aligned} {\varvec{\varDelta }}_{ij}(\mathbf {U}(t))=\mathbf {U}_{i}(G_i)+\varvec{\varOmega }_i\wedge \mathbf {G_i\,A_{i,j}}-\left( \mathbf {U}_{j}(G_j)+\varvec{\varOmega }_j\wedge \mathbf {G_j\,A_{i,j}} \right) \end{aligned}$$

(6.12)

where $G_i$ and $\varvec{\varOmega }_i$ are the center of mass and the angular velocity of the ith particle, respectively, see Chap. 5. When the rotation of the particles is neglected, the previous Eq. 6.12 becomes:

$$\begin{aligned} \begin{array}{rl} {\varvec{\varDelta }}_{ij}(\mathbf{U }(t)) &{} =\mathbf{U }_{i}(G_i)-\mathbf{U }_{j}(G_j)\\ &{} =\mathbf{U }_{i}(t)-\mathbf{U }_{j}(t)~. \end{array} \end{aligned}$$

(6.13)

The motion equations are written as:

$$\begin{aligned} \mathbf{M }\ \, \dot{\mathbf{U }}(t)= & {} -\mathbf{f }^{\, int}(t)+\mathbf{f }^{\, ext}(t)\ \ \ \text {almost everywhere} \end{aligned}$$

(6.14)

$$\begin{aligned} \mathbf{M } \, \left( \mathbf{U }^{+}(t)-\mathbf{U }^{-}(t)\right)= & {} -\mathbf{P }^{int}(t)+\mathbf{P }^{ext}(t)\ \ \ \text {everywhere} \end{aligned}$$

(6.15)

where $\mathbf{f }^{\, ext}(t)$ and $\mathbf{f }^{\, int}(t)$ are respectively the exterior and interior forces vectors of dimension 2N applied to the deformable system.

The existence of a solution of the system given by Eqs. (6.14) and (6.15) is proven in [17, 24, 31]. Equation (6.14) describes the smooth evolution of the multi-particle system, whereas Eq. (6.15) describes its non-smooth evolution during a collision. Hence, Eq. (6.14) applies everywhere, except at the instant of the collision, where it is replaced by Eq. (6.15). When contact is detected, velocities of colliding particles are discontinuous. Thus, in Eq. (6.15), the percussions $\mathbf{P }^{int}(t)$ and $\mathbf{P }^{ext}(t)$, interior and exterior to the system, respectively, are introduced, resulting from the variation of the linear momentum for the duration of the collision. By definition, percussions have the dimension of a force multiplied by a time. The $\mathbf{P }^{int}(t)$ percussions are unknown; these percussions take into account the dissipative interactions between two factors: the colliding particles (dissipative percussions) and the reaction forces that permit the avoidance of overlapping among particles (reactive percussions) [31, 32] defined the velocity of deformation at the moment of impact as $\frac{\varvec{\varDelta }(\mathbf{U }^{+})+\varvec{\varDelta }( \mathbf{U }^{-})}{2}$ and showed that $\mathbf{P }^{int}$ is defined in duality with $\frac{\varvec{\varDelta }(\mathbf{U }^{+})+\varvec{\varDelta }(\mathbf{U }^{-})}{2}$ according to the work of internal forces. He then introduced a pseudo-potential of dissipation $\varPhi$ that allows us to express $\mathbf{P }^{int}$ as:

$$\begin{aligned} \mathbf{P }^{int} \in \partial \varPhi \left( \frac{\varvec{\varDelta }( \mathbf{U }^{+})+\varvec{\varDelta }(\mathbf{U }^{-})}{2}\right) \end{aligned}$$

(6.16)

where the operator $\partial$ is the sub-differential that generalizes the derivative for convex functions [32].

The convex function $\varPhi$ [68] is defined as the sum of two pseudo-potentials: $\varPhi =\varPhi ^{d}+\varPhi ^{r}$, where $\varPhi ^{d}$ and $\varPhi ^{r}$ characterize the dissipative and reactive interior percussions respectively. $\varPhi ^{r}$ allows to define the reactive percussions which ensure the non-interpenetration between particles. It is defined as: $\varPhi ^{r} = I_C \left( \frac{{}^t ( \varDelta (U^+)+\varDelta (U^-)) N}{2} \right)$ where N is the normal vector to the plane tangent to the contact point between the two particles, $I_C$ is the characteristic function of the set C defined by $\left[ \frac{{}^t\varDelta (U^-) N}{2}, +\infty \,[\mathrm{or}] -\!\infty , \frac{{}^t\varDelta (U^-) N}{2}\right]$, according to the selected sense for the normal vector. The pseudo-potential $\varPhi ^{d}$ is chosen to be quadratic: $\varPhi ^{d}(y)=\frac{K}{2}y^{2}$, where K is a coefficient of dissipation. This choice allows one to find the classical results when using the coefficient of restitution. Other choices of $\varPhi ^{d}$ allow one to obtain a large variety of behaviors after impact [17, 32].

With the definition of the interior percussions given by Eq. (6.16), the existence and unicity of the solution of the system given by Eqs.  (6.14) and (6.15) is proven in [18, 25, 32].

In Eq. (6.15), the problem becomes determining the velocity $\mathbf{U }^{+}$ after particle collision. To determine $\mathbf{U }^{+}$, we have to solve the following constrained minimization problem:

$$\begin{aligned} \begin{array}{c} \mathbf{X }= \begin{array}{c} \arg \min \\ \mathbf{Y }\in \mathbf {R}^{2N} \end{array} \left[ ~^t\mathbf{Y }\ \mathbf{M }\ \mathbf{Y }+\varPhi ( \varvec{\varDelta }(\mathbf{Y }))-~^t(2\mathbf{U }^{-}+\mathbf{M }^{-1}\mathbf{P }^{ext})\mathbf{M }\ \mathbf{ Y }\right] \\ \end{array} \end{aligned}$$

(6.17)

where the solution $\mathbf{X }=\frac{{\mathbf{U }}^{+}+ {\mathbf{U }}^{-}}{2}$.

In this approach, the velocity of a particle after a contact ($\mathbf{U }^{+}$) has a physical meaning. Proof of the existence and uniqueness of this velocity after the simultaneous collisions of several rigid solids, as well as the dissipativity of the collisions, is presented in [24, 25, 31, 32].

6.5.2 Numerical Aspects of the Three Approaches

The time interval [0, T] is discretized into $N_{int}$ regular intervals $[t^{n},t^{n+1}]$ of length $h=\frac{T}{N_{int}}$. Let $\mathbf{x }^{0}= \mathbf{x }(0)$ and $\mathbf{U }^{0}=\mathbf{U }(0)$ respectively be the initial positions and velocities of the particles. Given $\mathbf{x } ^{n}$ and $\mathbf{U }^{n}$ at time $t^{n}$, we have to find $\mathbf{x } ^{n+1}$ and $\mathbf{U }^{n+1}$ at time $t^{n+1}$ for each approach.

For both $\textit{NSM}1$ and $\textit{NSM}2$, after making some assumptions, the contact problem can be written with the same formalism as that used in plasticity. The evolution equations of classical elastoplasticity, define a unilaterally constrained problem of evolution. Simo [94] showed that by applying an implicit backward-Euler difference scheme, this continuum problem is transformed into a constrained-optimization problem, governed by discrete Kuhn–Tucker conditions. Thus, this constrained problem of evolution collapses to the iterative solution of a convex mathematical programing problem.

Denoting ${\mathsf {\sigma }}$ the stress tensor and ${\mathsf {C}}$ the elasticity tensor respectively, the discrete constrained-optimization problem in the case of plasticity can be written as [93]:

$$\begin{aligned} \begin{array}{c} {\mathsf {\sigma }}^{n+1}= \begin{array}{c} \arg \min \\ {\mathsf {\sigma }} \end{array} \left[ \frac{1}{2}\Vert {\mathsf {\sigma }}-{\mathsf {\sigma }}_{predicted}\Vert _{{\large {\varvec{C}}}^{-1}}^{2}+\varDelta \lambda f({\mathsf {\sigma }}) \right] \\ \text {with}\ \ {\mathsf {\sigma }}_{predicted}={\mathsf {\sigma }}^{n}+{\mathsf {C}}\ :\varDelta \varvec{\varepsilon } \\ \end{array} \end{aligned}$$

(6.18)

where ${{\mathsf {C}}}^{-1}$ is the compliance tensor, $\Vert {\mathsf {X}}\Vert _{{{\mathsf {C}}}^{-1}}^{2}=~^{t}{\mathsf {X}}:{{\mathsf {C}}}^{-1}:{\mathsf {X}}$ is the energy norm and ${\mathsf {X}}$ is a stress tensor, $\varDelta \varvec{\varepsilon }=\varvec{\varepsilon }^{n+1}-\varvec{\varepsilon }^{n}$ is the total strain increment, $\varDelta \lambda$ is the plasticity multiplier, $f({\mathsf {\sigma }})$ is the elastic domain, and $\varDelta \lambda$ and ${\mathsf {\sigma }}$ satisfy the inequalities:

$$\begin{aligned} \left\{ \begin{array}{rl} f({\mathsf {\sigma }}^{n+1}) &{} \le 0 \\ \varDelta \lambda &{} \ge 0 \\ \varDelta \lambda f({\mathsf {\sigma }}^{n+1}) &{} =0~. \\ &{} \end{array} \right. \end{aligned}$$

(6.19)

In other words, the minimization problems obtained with $\textit{NSM}1$ and $\textit{NSM}2$ can also be solved using the well-known algorithms proposed, for example, in [93].

$\textit{DEM}$

The positions and velocities of particles at time $t^{n+1}$ are given by the explicit scheme:

$$\begin{aligned} \left\{ \begin{array}{rl} \mathbf{U }^{n+1} &{} =\mathbf{U }^{n}+h\mathbf{M }^{-1}( \mathbf{f }^{n}+\mathbf{g }^{n}) \\ \mathbf{x }^{n+1} &{} =\mathbf{x }^{n}+h\mathbf{U }^{n+1}~ \end{array} \right. \end{aligned}$$

(6.20)

where $\mathbf{f }^{n}$ is the vector of at a distance forces and $\mathbf{g }^{n}$ is the vector of contact forces at time $t^{n}$ (Eq. (6.3)). Based on Eqs. (6.5) and (6.6), the contact force applied to the particle i at time $t^{n}$ is given by:

$$\begin{aligned} \mathbf{g }_{i}^{n}=\sum \limits _{\begin{array}{c} j=1 \\ j\ne i \end{array}}^{N}k\min (0,D_{ij}(\mathbf{x }^{n}))\mathbf{e }_{ij}^{n}~. \end{aligned}$$

(6.21)

The overlap and stability of the time integration scheme depend on the chosen time step denoted by h [21, 81, 84]. The choice of this parameter is thus essential.

$\textit{NSM1}$

The positions of particles at time $t^{n+1}$ are obtained by the iterative equation:

$$\begin{aligned} \mathbf{x }^{n+1}=\mathbf{x }^{n}+h\mathbf{U }^{n+1} \end{aligned}$$

(6.22)

where $\mathbf{U }^{n+1}$ needs to be found such that $D_{ij}( \mathbf{x }^{n+1})\ge 0$.

As $D_{ij}$ is convex, the following relationship can be established:

$$\begin{aligned} D_{ij}(\mathbf{x }^{n+1})=D_{ij}(\mathbf{x }^{n}+h\mathbf{U } ^{n+1})\ge D_{ij}(\mathbf{x }^{n})+h^{t}\mathbf{G }_{ij}(\mathbf{x } ^{n})\mathbf{U }^{n+1}\ge 0~. \end{aligned}$$

(6.23)

Therefore, we search for $\mathbf{U }^{n+1}$ such that the approximation of the final distance between each pair of particles $D_{ij}(\mathbf{x } ^{n})+h^{t}\mathbf{G }_{ij}(\mathbf{x }^{n})\mathbf{U }^{n+1}$ is either positive or zero.

To calculate $\mathbf{U }^{n+1}$, we have to solve the constrained minimization problem:

$$\begin{aligned} \begin{array}{c} \mathbf{U }^{n+1}= \begin{array}{c} \arg \min \\ \mathbf{v }^{n+1}\in R^{2N} \end{array} \left[ \frac{1}{2}\Vert \mathbf{v }^{n+1}-\mathbf{V }_{predicted}\Vert _{ \mathbf{M }}^{2}-\sum \limits _{1\le i<j\le N}\mu _{ij}^{n+1}(D_{ij}(\mathbf{x }^{n})+h^{t}\mathbf{G }_{ij}(\mathbf{x } ^{n})\mathbf{v }^{n+1})\right] \\ \text {with}\ \ \mathbf{V }_{predicted}=\mathbf{U }^{n}+h \mathbf{M }^{-1}\mathbf{f }^{,n} \\ \end{array} \end{aligned}$$

(6.24)

where $\mu _{ij}^{n+1}$ is a Lagrange multiplier and has the dimension of a force. $\mu _{ij}^{n+1}$ and $\mathbf{U }^{n+1}$ must satisfy the Kuhn–Tucker conditions:

$$\begin{aligned} \left\{ \begin{array}{rl} \mu _{ij}^{n+1} &{} \ge 0 \\ D_{ij}(\mathbf{x }^{n})+h^{t}\mathbf{G }_{ij}(\mathbf{x }^{n}) \mathbf{U }^{n+1} &{} \ge 0 \\ \mu _{ij}^{n+1}\left( D_{ij}(\mathbf{x }^{n})+h^{t}\mathbf{G }_{ij}( \mathbf{x }^{n})\mathbf{U }^{n+1}\right) &{} =0~. \end{array} \right. \end{aligned}$$

(6.25)

The convergence of the numerical scheme given by Eqs. (6.22), (6.24), and (6.25) is proven in [7]. The inelastic collision law is implicitly included in the constrained minimization problem (6.24). The constraint affects the particle positions at the end of the considered time step, and $\mathbf{U }^{n+1}$ is computed such that these positions are admissible.

The expressions of $\mathbf{U }^{n+1}$ and $\mu _{ij}^{n+1}$ are related by:

$$\begin{aligned} \mathbf{M }\ \mathbf{U }^{n+1}=\mathbf{M }\ \mathbf{U }^{n}+h\mathbf{f }^{n}+h\sum \limits _{1\le i<j\le N}\mu _{ij}^{n+1}\mathbf{G }_{ij}(\mathbf{x }^{n}) \end{aligned}$$

(6.26)

where $\mu _{ij}^{n+1}$ and $\mathbf{U }^{n+1}$ satisfy the Kuhn–Tucker conditions Eq. (6.25).

$\textit{NSM2}$

On each interval $[t^{n},t^{n+1}]$, smooth forces are substituted by percussions applied at the time $\ \theta _{n}=t^{n}+~\frac{h}{2}$. All the non-smooth forces, or the percussions applied during the collision, are applied to the system at $\theta _{n}$. Hence, interior (resp. exterior) percussions to the deformable system are the sum of two factors: the interior (resp. exterior) percussions during contacts, and the percussions obtained from smooth forces exerted on the system during the system’s smooth evolution [25]. It follows that the velocities are discontinuous at times $\theta _{n}$ when percussions are applied to the system, but elsewhere are constant. This idea is represented by a piecewise affine function, constant on $[t^{n},\theta _{n}[$ and $]\theta _{n},t^{n+1}]$ and with a jump discontinuity at $\theta _{n}$ (see Fig. 6.16).

Fig. 6.16

$\textit{NSM}2$—velocity of the pedestrian i. Time intervals in yellow correspond to those where there is a contact and/or nonzero smooth force applied to the ith particle and where there is a jump discontinuity in the velocity

The equation governing a discontinuity on $[t^{n},t^{n+1}]$ is:

$$\begin{aligned} \begin{array}{c} \mathbf{U }^{n+1}(\theta _{n})-\mathbf{U }^{n}(\theta _{n})= \mathbf{M }^{-1}\left( -\mathbf{P }^{int}\left( \frac{\varvec{\varDelta }(\mathbf{U }^{n+1}(\theta _{n}))+\varvec{\varDelta }(\mathbf{U } ^{n}(\theta _{n}))}{2}\right) +\mathbf{P }^{ext}(\theta _{n})\right) ~. \end{array} \end{aligned}$$

(6.27)

Let ${\mathbf{X }}^{n+1}=\frac{{\mathbf{U }}^{n+1}(\theta _{n})+ {\mathbf{U }}^{n}(\theta _{n})}{2}$ so that Eq. (6.27) becomes:

$$\begin{aligned} \begin{array}{c} 2\mathbf{X }^{n+1}+\mathbf{M }^{-1}\mathbf{P }^{int}( \varvec{\varDelta }(\mathbf{X }^{n+1}))=2\mathbf{U }^{n}(\theta _{n})+ \mathbf{M }^{-1}\mathbf{P }^{ext}(\theta _{n})~. \end{array} \end{aligned}$$

(6.28)

From Eqs. (6.17) and (6.28), $\mathbf{X }^{n+1}$ can be obtained by solving the constrained minimization problem:

$$\begin{aligned} \begin{array}{c} \mathbf{X }^{n+1}= \begin{array}{c} \arg \min \\ \mathbf{Y }^{n+1}\in \mathbf {R}^{2N} \end{array} \left[ ~^{t}\mathbf{Y }^{n+1}\mathbf{M }\ \mathbf{Y } ^{n+1}+\varPhi (\mathbf{x }^{n},\varvec{\varDelta }(\mathbf{Y } ^{n+1}))-~^{t}(2\mathbf{U }^{n}(\theta _{n})+\mathbf{M }^{-1} \mathbf{P }^{ext}(\theta _{n}))\mathbf{M }\ \mathbf{Y } ^{n+1}\right] \\ \end{array} \end{aligned}$$

(6.29)

where ${\mathbf{Y }}^{n+1}=\frac{{\mathbf{U }}^{n+1}(\theta _{n})+ {\mathbf{U }}^{n}(\theta _{n})}{2}$.

The constitutive law used is the linear law corresponding to the quadratic pseudo-potential:

$$\begin{aligned} \begin{array}{c} \varPhi ^{d}(\mathbf{x }^{n},\varvec{\varDelta }(\mathbf{Y } ^{n+1}))=\sum \limits _{1\le i<j\le N}\frac{1}{2}K_{T}\left( ^{t}\varvec{ \varDelta }_{ij}(\mathbf{Y }^{n+1})~^{\perp }\mathbf{e }_{ji}^{n}\right) ^{2}+\frac{1}{2}K_{N}\left( ^{t}\varvec{\varDelta }_{ij}(\mathbf{Y } ^{n+1})\mathbf{e }_{ji}^{n}\right) ^{2} \end{array} \end{aligned}$$

(6.30)

where $\mathbf{e }_{ji}^{n}$ is the normal vector at the contact point, $~^{\perp }\mathbf{e }_{ji}^{n}$ is the tangent vector at the contact point, and $K_{N}$ and $K_{T}$ respectively are the coefficients of dissipation for the normal and tangential components of percussions. $K_{N}$ reflects the inelastic nature of collisions between particles. A collision between a particle and a wall is elastic for $K_{N}\rightarrow \infty$ [32]. Practically, a value of $K_{N}>10^{4}$ kg is well suited in the case of dense crowds. $K_{T}$ is due to the atomization of viscous friction and its value is often chosen to be zero. Its influence is shown in [53] and illustrated for the case of a pedestrian flow through a bottleneck.

The following inequality has to be verified when there is a contact between two particles i and j:

$$\begin{aligned} -~^{t}\varvec{\varDelta }_{ij}(\mathbf{Y }^{n+1})\mathbf{e } _{ji}^{n}+~^{t}\varvec{\varDelta }_{ij}(\frac{{\mathbf{U }}^{n}(\theta _{n}) }{2})\mathbf{e }_{ji}^{n}\le 0{~.} \end{aligned}$$

(6.31)

The dual formulation of the no interpenetration condition in Eq. (6.31) is used to express the potential $\varPhi ^ {r}$ in the following form:

$$\begin{aligned} \varPhi ^{r}(\mathbf{x }^{n},\varvec{\varDelta }(\mathbf{Y } ^{n+1}))=\sum \limits _{1\le i<j\le N}\mu _{ij}^{n+1}\left[ -~^{t}\varvec{ \varDelta }_{ij}(\mathbf{Y }^{n+1})\mathbf{e }_{ji}^{n}+~^{t}\varvec{ \varDelta }_{ij}(\frac{{\mathbf{U }}^{n}(\theta _{n})}{2}){\mathbf{e }}_{ji}^{n} \right] \end{aligned}$$

(6.32)

where $\mu _{ij}^{n+1}$ is a Lagrange multiplier and has the dimension of a percussion. $\mu _{ij}^{n+1}$ and $\mathbf{U }^{n+1}$ must satisfy the Kuhn–Tucker conditions:

$$\begin{aligned} \left\{ \begin{array}{rl} \mu _{ij}^{n+1} &{} \ge 0 \\[7pt] ~^{t}\varvec{\varDelta }_{ij}(\mathbf{Y }^{n+1})\mathbf{e } _{ji}^{n}-~^{t}\varvec{\varDelta }_{ij}(\frac{{\mathbf{U }}^{n}(\theta _{n}) }{2}){\mathbf{e }}_{ji}^{n} &{} \ge 0 \\[7pt] \mu _{ij}^{n+1}\left[ ~^{t}\varvec{\varDelta }_{ij}(\mathbf{Y }^{n+1}) \mathbf{e }_{ji}^{n}-~^{t}\varvec{\varDelta }_{ij}(\frac{{\mathbf{U }} ^{n}(\theta _{n})}{2}){\mathbf{e }}_{ji}^{n}\right] &{} =0~. \end{array} \right. \end{aligned}$$

(6.33)

The velocities and positions at the end of time steps are solutions of:

$$\begin{aligned} \left\{ \begin{array}{rl} \mathbf{U }^{n+1}(\theta _{n}) &{} =\mathbf{U }^{n+1}(\theta _{n+1})=2 \mathbf{X }^{n+1}-\mathbf{U }^{n}(\theta _{n}) \\[7pt] \mathbf{x }^{n+1} &{} =\mathbf{x }^{n}+h\frac{{\mathbf{U }}^{n+1}(\theta _{n})+\mathbf{U }^{n}(\theta _{n})}{2}~. \\ &{} \end{array} \right. \end{aligned}$$

(6.34)

The minimization problems (6.24) and (6.29) are solved using the classical Uzawa algorithm [20, 25, 26, 32].

To write Eq. (6.29) with the same formalism as Eqs. (6.18) and (6.24), only purely inelastic collisions need to be considered, as in $\textit{NSM}1$. We choose, then, $K_{N}=K_{T}=0$ in Eq. (6.30). Thus Eq. (6.29) becomes:

$$\begin{aligned} \begin{array}{c} \mathbf{U }^{n+1}= \begin{array}{c} \arg \min \\ \mathbf{V }^{n+1}\in R^{2N} \end{array} \left[ \frac{1}{2}\Vert \mathbf{V }^{n+1}(\theta _{n})-\mathbf{V } _{predicted} \Vert _{\mathbf{M }}^{2}-\sum \limits _{1\le i<j\le N}\mu _{ij}^{n+1}~^{t}\mathbf{G }_{ij}(\mathbf{x }^{n}) \mathbf{V }^{n+1}(\theta _{n})\right] \\ \text {with}\ \ \mathbf{V }_{predicted}= \mathbf{U }^{n}(\theta _{n})+ \mathbf{M }^{-1}\mathbf{P }^{ext}(\theta _{n}) \\ \end{array} \end{aligned}$$

(6.35)

Consequently, with $K_N=K_T=0$, the expressions of $\mathbf{U } ^{n+1}$ and of $\mu _{ij}^{n+1}$ are related by:

$$\begin{aligned} \mathbf{M }\ \mathbf{U }^{n+1}(\theta _{n})=\mathbf{M }\ \mathbf{U }^{n}(\theta _{n})+\mathbf{P } ^{ext}(\theta _{n})+\sum \limits _{1\le i<j\le N}\mu _{ij}^{n+1}\mathbf{G } _{ij}(\mathbf{x }^{n}) \end{aligned}$$

(6.36)

where $\mu _{ij}^{n+1}$ and $\mathbf{U }^{n+1}$ satisfy the Kuhn–Tucker conditions Eq. (6.33).

Table 6.3 Analogies between minimization problems in the case of plasticity and when using $\textit{NSM}1$ or $\textit{NSM}2$

Equations (6.26) and (6.36) have similar expressions; however, the calculation of the Lagrange multiplier $\mu _{ij}^{n+1}$ is different for each. For NSM1, the constraint is on the position of the particle and is dependent on the time step, so overlapping is always avoided. The velocity of the particle has a “geometrical meaning” since it is computed from the previously found position. However, for $\textit{NSM}2$, the constraint is on the velocity of the particle and is independent of the time step, so overlapping is possible. The velocity now has a greater physical meaning, and it can be accepted that the position of the particle after contact can violate the overlapping condition.

Table 6.3 shows the analogies between minimization problems in the case of plasticity and when using $\textit{NSM}1$ or NSM2 (Eqs. (6.18), (6.24), and (6.35)).

The difference in contact treatment between $\textit{NSM}1$ and $\textit{NSM}2$ can be illustrated with the following example. In the xy-plane, we consider a particle of radius $r=0.22$ m, initial position $\mathbf{x }_{initial}=^{t}(0.5,0.5)$ , and initial velocity $\mathbf{U }_{initial}=^{t}(\frac{1}{\sqrt{2}},- \frac{1}{\sqrt{2}})$. The ground corresponds to $y=0$. We choose $K_{N}=K_{T}=0$ kg, $T=0.8$ s, and $h=10^{-3}$ s. No exterior force is applied to the particle. The particle’s position in the xy-plane after a collision with the ground, and the time evolution of its velocity along the y-axis, are given for both $\textit{NSM}1$ and $\textit{NSM}2$ in Fig. 6.17. Considering the spatial trajectory of the particle’s center in the xy-plane, we illustrate previously made remarks about Eqs. (6.26) and (6.36) in the following figures. Figure 6.17b (a zoomed-in-on section of Fig. 6.17a) shows that unlike $\textit{NSM}1$, a light numerical overlapping can exist with $\textit{NSM}2$. Figure 6.17d (a zoomed-in-on section of Fig. 6.17c) shows that when the contact is detected, one intermediate velocity with no physical meaning is found just after the collision with $\textit{NSM}1$.

Fig. 6.17

Collision of a particle with the ground for $\textit{NSM}1$-$\textit{NSM}2$. Subplots a and b show the trajectory in the xy-plane of the particle’s center (radius $r=0.22$ m) after collision with the ground as a function of time. Subplots c and d show the time evolution of the velocity along the y-axis of the particle’s center after collision with the ground. Subplots b and d are magnifications of the green rectangles in subplots (a) and (c), respectively. The curve for $\textit{NSM}1$ is the red dotted line and the curve for NSM2 is the blue line

6.6 Adaptation of a Granular Approach to the Crowd

The 2D approach of rigid particles movement, in particular the one proposed by Frémond, can be adapted to crowd movement. A pedestrian can be represented as a particle by being given a willingness, i.e., a desire to move in a particular direction with a specific speed at each moment. To adapt the granular approach proposed by Frémond to a crowd, two steps need to be considered: first, the introduction into the model of the desired velocity of each pedestrian, in order to portray crowd movement; and second, the definition of the desired velocity of each pedestrian.

6.6.1 Introduction of the Desired Velocity of Each Pedestrian into the Particle Movement Approach

In order to introduce the willingness of each pedestrian to move at his or her desired velocity, an acceleration force is added to the particle movement approach. We can note: $\mathbf{f }^{int}(t)=\mathbf{f }^{a}(t)$, where $\mathbf{f }^{a}(t)$ is the acceleration force [37] allowing one to give a desired direction and velocity amplitude to each pedestrian. Each component $\mathbf{f }_{i}^{a}(t)$ of the vector force of dimension 2N: $^{t}\mathbf{f }^{a}=(^{t}\mathbf{f }_{1}^{a},^{t} \mathbf{f }_{2}^{a},...,^{t}\mathbf{f }_{N}^{a})$ is associated with pedestrian i and can be expressed as:

$$\begin{aligned} \mathbf{f }_{i}^{a}(t)=m_{i}\frac{\Vert \mathbf{U }_{d,i}\Vert \mathbf{e }_{d,i}(t)-\mathbf{U }_{i}(t)}{\tau _{i}} \end{aligned}$$

(6.37)

where $\mathbf{U }_{d,i}$ is the desired velocity of the pedestrian i; $\mathbf{e }_{d,i}$ is his or her desired direction; $\mathbf{U }_{i}$ is the pedestrian’s current velocity; and $\tau _{i}$ is a relaxation time, allowing the pedestrian i to recover his or her desired velocity after a collision. Smaller values of $\tau _{i}$ let the pedestrians walk more aggressively [39]. For this variable, Helbing chose $\tau =0.5$ s. An example of the post-collision trajectories as a function of $\tau$ for two identical pedestrians i and j moving in opposite directions is illustrated in Fig. 6.18. The expressions of $\Vert \mathbf{U }_{d,i}\Vert$ and $\mathbf{e }_{d,i}(t)$ need to be defined in order to find $\mathbf{f }_{i}^{a}(t)$. This is the purpose of the next paragraph.

Fig. 6.18

Trajectories of two identical pedestrians i and j moving in opposite directions for different values of $\tau$. After the collision, the external acceleration force allows each pedestrian to gradually change from the current post-collision velocity to the desired velocity, depending on the values of $\tau _{i}$ and $\tau _{j}$. In this example, $\tau _{i}=\tau _{j}=\tau$

Fig. 6.19

Geodesic distances to the exit of a room containing an obstacle. Two examples of shortest trajectory are plotted as a function of the initial position of the pedestrian in the room

6.6.2 Definition of the Desired Velocity

The amplitude $\Vert \mathbf{U }_{d,i}\Vert$ of the desired velocity represents the speed at which the ith pedestrian wants to move on the considered structure, and can be influenced by the pedestrian’s level of nervousness. Generally, this velocity is chosen following a normal distribution with an average of 1.34 m s$^{-1}$ and standard deviation of 0.26 m s$^{-1}$ [43].

Several definitions of the desired trajectory $\mathbf{e } _{d,i}(t)$ of pedestrian i are possible: (i) the most comfortable trajectory, where he or she exerts the least effort (e.g., by avoiding stairs) and changes direction the least frequently, etc.; (ii) the shortest path; or (iii) the fastest path to move from one place to another [50]. It is possible to combine two strategies in the same simulation or to change the preferred strategy for any reason during the simulation.

The strategy of the shortest path from one point to another [58] is implemented through a Fast Marching algorithm and can be used to obtain $\mathbf{e }_{d,i}$. This direction depends on the space or terrain (whether there are obstacles, etc.), the time, and also the characteristics of the individual (gender, age, slowed or hurried steps, etc.). It is defined by: $\mathbf{e }_{d,i}(t)=\frac{{\mathbf{U }}_{d,i}(t)}{\Vert {\mathbf{U }} _{d,i}\Vert }$. Figure 6.19 illustrates an example of the geodesic distances to the exit of a room containing an obstacle. Two examples of shortest trajectory are plotted as a function of the initial position of the pedestrian in the room.

6.6.3 The Influence of the Relaxation Time Parameter $\tau$

Here we consider the trajectories of two pedestrians moving in opposite directions after a collision. A study is performed to determine the influence of the relaxation time parameter $\tau$ on two post-collision variables: the time $t_{fi}$ that the pedestrian needs to recover his or her desired trajectory, and the final distance $d_{fi}$ resulting from the shock (Fig. 6.18).

When the initial distance $d_{in}$ is small and the value of $\tau$ is less than 0.5 s, several contacts may occur since the pedestrians walk aggressively and recover their desired velocity immediately after a collision.

When the value of $\tau$ is more than 0.5 s, there will only be one collision, and $t_{fi}$ and $d_{fi}$ increase linearly as a function of $\tau$ (Fig. 6.20).

Fig. 6.20

The final distance $d_{fi}$ as a function of $\tau$ and $d_{in}$ (left); the time $t_{fi}$ as a function of $\tau$ and $d_{in}$ (right). The velocity of the pedestrians is 1.5 m s$^{-1}$ and their radii are 0.25 m

Observing the results obtained after the collision between two pedestrians of different radii but with the same velocity (Fig. 6.21), one can notice that the lighter pedestrian (with a radius closer to 0.20 m) needs more time after the contact to resume his or her desired trajectory, while the heavier pedestrian (with a radius closer to 0.25 m) attains this trajectory faster. Simulations conducted for the case of pedestrians with different initial velocities have produced the same kind of results as those of pedestrians with the same velocities [79].

Fig. 6.21

$t_{fi}$ as a function of $\tau$ and $d_{in}$. The velocity of the pedestrians is 1.5 m s$^{-1}$ and their radii are 0.2 m and 0.25 m

6.7 Making the Behaviour of Pedestrians More Realistic

To make the behaviour of the pedestrians more realistic, several forces can be added to obtain $\mathbf{f }^{int}(t)$. For instance, $\mathbf{f }^{int}(t)=\mathbf{f }^{a}(t)+\mathbf{f } ^{soc}(t)+\mathbf{f }^{sgr}(t)$, where $\mathbf{f }^{soc}(t)$ is a socio-psychological force [39] that reflects the tendency of pedestrians to keep a certain distance from other pedestrians, and $\mathbf{f }^{sgr}(t)$ is a subgroup force [95] that allows one to take into account the subgroup behaviour of crowd movement. Both of these forces are detailed in the following paragraphs.

6.7.1 The Socio-Psychological Force

The expression of the socio-psychological force [36, 39], applied to the ith pedestrian interacting with pedestrian j, is given by:

$$\begin{aligned} \mathbf{f }_{ij}^{soc}(t)=A_{i}\exp \left( \frac{-D_{ij}(\mathbf{x }(t)) }{B_{i}}\right) \left( \varLambda _{i}+(1-\varLambda _{i})\frac{1+\cos \varphi _{ij}}{2}\right) \mathbf{e }_{ij} \end{aligned}$$

(6.38)

where $A_{i}$ denotes the interaction strength; $B_{i}$ the range of the repulsive interaction; $\varLambda _{i}<1$ the anisotropic character of pedestrian interactions, as the situation in front of a pedestrian has a larger impact on behavior than what is occurring behind; and $\varphi _{ij}$ the angle between the direction $\mathbf{e }_{d,i}(t)$ of the desired motion and the direction $-\mathbf{e }_{ij}$ of the pedestrian exerting a repulsive force. Figure 6.22 shows an example of a pedestrian-pedestrian interaction with and without the socio-psychological force. A video at the following link shows head-on encounter of 2 couples of pedestrians (file repulsionCollision.avi are available at https://ifsttar.libcast.com/mast-sdoa or at http://extras.springer.com). The pedestrians on the bottom avoid each other because the repulsive force is activated while the ones on the top collide since the repulsive force is not activated.

Fig. 6.22

Pedestrian-pedestrian interaction, a without and b with the socio-psychological force

One can notice that in Fig. 6.22 (left), which illustrates an interaction without the socio-psychological force, a pedestrian-pedestrian collision occurs. On the other hand, in Fig. 6.22 (right), which includes this force, there is no collision. Pedestrians avoid each other by turning around.

6.7.2 Subgroups: Pedestrians Holding Hands

A group is defined as a physical collection of people following the same way, but who may be or not a part of the same social group. A subgroup is defined as people within the same physical group who want to stay together [95] like those of friends or a family. Several studies have revealed that smaller subgroups constitute the majority of the people in a crowd [5, 95]. However, very few studies are able to model the subgroup behaviour [72, 95]. A particular subgroup concerns pedestrians who hold hands. It is recognized that holding hands is the most effective way of keeping children safe from traffic injury.

To describe the particular subgroup behaviour of the holding hands pedestrians, we were inspired by the article [14] describing the interactions between rigid particles as an “at-a-distance” velocity of deformation. This velocity is the derivative with respect to time of the squared distance between linked shoulders, i.e. points $A_i$ and $A_j$ for pedestrians i and j (Fig. 6.23). This model takes into account the effects of the subgroup as a continuous deformation within the subgroup of pedestrians who hold hands while existing methods in literature describe the cohesion of the subgroup with external forces [72, 95]. This new subgroup model [3] needs that pedestrians be oriented. The rotation of the pedestrians around themselves has been integrated in the 2D model to obtain an improvement of the microscopic approach proposed in [79–82]. It is noteworthy that the pedestrians orientation is rarely used in literature [1, 61]. Therefore, the center position of the ith particle is now described by the vector $~^{t}\mathbf{x }_{i}=(q_{i}^{x},q_{i}^{y}, \theta _i(t))\in R^{3}$, where $\theta _i(t) \in [-\pi ,\pi ]$ represents the walking direction of the particles about the $\mathbf{e }_z$-axis ($\theta _i(t)=0$ when the particle’s walking direction is parallel to the x-axis in the positive direction, $\theta _i(t)>0$ when the particle turns counterclockwise), $\dot{\theta }_i(t)=d\theta _i/dt$ its rotational velocity, and $\varvec{\varOmega }_i(t)=[0,0,\dot{\theta }_i(t)]$. A mass moment of inertia $I_i$ about a particle’s vertical axis is integrated in the inertial matrix of the set of particles making it of size $3N\times 3N$.

Fig. 6.23

Two pedestrians holding hands- Example of linked shoulders

Analogous to the acceleration force given by Eq. (6.37), a restoring torque must also be introduced to return the pedestrian to his desired direction after a perturbation. It is modeled as the combination of a linear rotational spring and of a linear rotational damper [3], and is defined for the ith pedestrian by:

$$\begin{aligned} l_{i}^a=k_i\big (\theta _i-\theta _{d,i}\big )+c_i\dot{\theta }_i=-I_i\ddot{\theta }_i \end{aligned}$$

(6.39)

where $\theta _{d,i}$ is the angle between $\mathbf{e }_{d,i}$ and the reference direction $\mathbf{e }_x=[1;0]$, $I_i$ (in kg.m$^2$) is the moment of inertia, $k_i$ (in kg $\cdot$ m$^{2}$ $\cdot$ s$^{-2}$ $\cdot$ rd$^{-1}$) is the torsional stiffness, $c_i$ (in kg $\cdot$ m$^2$ $\cdot$ s$^{-1}$ $\cdot$ rd$^{-1}$) is the rotational damping, and $\omega _i=\sqrt{\frac{k_i}{I_i}}$ (in rd $\cdot$ s$^{-1}$) is the undamped resonant frequency for pedestrian i. After a perturbation, a particle returns the fastest without oscillations to its desired direction when its rotation is critically damped ($\zeta _i=\frac{c_i}{2\sqrt{I_i\, k_i}}=1$). For $\zeta _i>1$, the individual returns more slowly to its desired position (Fig. 6.24a, b). For $\zeta _i<1$, it oscillates before returning to its desired direction (Fig. 6.24c, d). The collision in Fig. 6.24 occurs at $t=0.1$ s and the time step is $\varDelta t =0.01$ s. The solid line plotted inside the particle represents the pedestrian’s desired direction while the dotted line represents his current walking direction. We have chosen $\zeta _i=1$.

Fig. 6.24

Pedestrian-pedestrian interaction without repulsive forces: the left column shows the pedestrian’s movement after “collision” for $\zeta _i=1$ (top) and $\zeta _i=0$ (bottom), where $\theta _{d,i}=0$. The right column is a plot of the pedestrian’s rotation as a function of time

The maximum rotation must also be controlled so that pedestrians won’t rotate in an unrealistic manner after a shock. By solving Eq. (6.39), we obtain the rotation time-evolution of an individual about himself:

$$\begin{aligned} \theta _i(t)=\dot{\theta }_{0}(K_T,K_N)te^{-\omega _i t}+\theta _{d,i} \end{aligned}$$

(6.40)

where $\dot{\theta }_{0}(K_T,K_N)$ is calculated by the model (by solving Eq. (6.29)) after a shock takes place and $k_i=I_i\cdot \omega ^2_i$, the torsional stiffness (Eq. (6.39)), is introduced by the user ($k_i=k$ for the sake of simplicity). Figure 6.25 shows that the value of $\dot{\theta _{0}}$, calculated after a shock, varies with $K_T$ and is independent of $K_N$ for values greater than $2\times 10^3$ kg. From Eq. (6.40), we can easily obtain the expression of $\theta _{max}$:

$$\begin{aligned} \theta _{max}=\frac{\dot{\theta _{0}}(K_T)}{\omega _i \cdot e}+\theta _{d,i} \end{aligned}$$

(6.41)

By varying k (in kg $\cdot$ m$^{2}$ $\cdot$ s$^{-2}$ $\cdot$ rd$^{-1}$) between [0.5, 18.5], and for each value of $\dot{\theta _{0}}$ obtained from Fig. 6.25 (each value of $\dot{\theta _{0}}$ corresponds to a value of $K_T$), Eq. (6.41) gives the surface illustrated in Fig. 6.26. Now the user can specify the desired value of $\theta _{max}$ by choosing from Fig. 6.26 a point ($\dot{\theta _{0}},k$) which corresponds to a couple ($K_T,k$). The couple must be on or below the isoline representing the chosen value of the maximal rotation.

Fig. 6.25

Variation of $\dot{\theta }_{0}$ as a function of $\text {log}_{10}(K_T)$

Fig. 6.26

Variation of $\theta _{max}$ as a function of $\dot{\theta _{0}}$ and k

Now that the rotation is introduced into the model, the at a distance velocity of deformation is, see Chap. 5 and [32]:

$$\begin{aligned} \varvec{\varDelta }_{ij}^{*}\left( \mathbf{x }(t),\mathbf{U }(t)\right) =2\left( \mathbf{U }_{i}(t)-\mathbf{U }_{j}(t)\right) \cdot \mathbf{A }_{j}\mathbf{A }_{i}. \end{aligned}$$

(6.42)

In the previous expression of the pseudo-potential of dissipation, a new quadratic term function of the at a distance velocity of deformation is added:

$$\begin{aligned} \varPhi ^{d}\big (\mathbf{x },\mathbf{Y }\big )=&\frac{1}{2}\sum \limits _{1\le i\le j\le N}\bigg [K_{N}\Big (\,^{t}\varvec{\varDelta }_{ij}\big (\mathbf{Y }\big )\cdot \mathbf{e }^n_{ji}\Big )^{2}+K_{T}\Big (\,^{t}\varvec{\varDelta }_{ij}\big (\mathbf{Y }\big )\cdot ~^{\perp }\mathbf{e }^n_{ji}\Big )^{2}\bigg ]\nonumber \\ +&\sum \limits _{1\le i\le j\le N_{subgroup}}\frac{1}{2}K_{V}\Big (\,\varvec{\varDelta }^{*}_{ij}\big (\mathbf{x },\mathbf{Y }\big )\Big )^{2} \end{aligned}$$

(6.43)

where $K_V$ is the coefficient of viscous dissipation. A numerical study of the influence of $K_v$ is performed in [79]. It is shown that the higher the value of $K_v$ is, the more rigid the bond between the holding hands pedestrian is; thus a free pedestrian colliding the subgroup wont be able to break the bond.

On a same example illustrated in Fig. 6.27, a comparison has been done between different subgroup approaches: Singh [95], Moussaïd [72], and our approach for pedestrians holding hands with $K_v=100 \,{\text {Kg}} {\text {m}}^{-1}$. A subgroup composed of three pedestrians collides with a fourth pedestrian. It is shown that, with the proposed subgroup approach, the subgroup is re-formed faster after a collision than with the other approaches. Moreover, only the proposed approach allows to keep the shape of the subgroup throughout the whole simulation [3, 79].

Fig. 6.27

Example of a three holding hands pedestrians (in light blue) subgroup colliding with a fourth pedestrian (in red), each row correspond to an approach: Singh [95] top line, Moussaïd [72] middle line, and our approach [3, 79] bottom line

6.8 Simulations of Crowd Movement

In Fig. 6.28, one can find the different stages of the MATLAB program of the discrete crowd movement model. The simulations of crowd movement that were undertaken are split into four categories: (i) the reproduction of observed phenomena of crowd self-organization (see Sect. 6.1); (ii) the simulation of emergency evacuation exercises, with comparisons between the experimental and numerical results; (iii) the use of the model to improve the service quality of a studied space; and (iv) the modeling of sub-group movements.

Fig. 6.28

Discrete crowd movement model—stages in MATLAB program

Three parameters are proposed and calculated in order to compare and then comment on the different results: (i) the evacuation curve, which represents the temporal evolution of the number of pedestrians leaving a given location through one of several exits; (ii) the average rate of flow Q of pedestrians going across an exit, obtained via a temporal derivation of the previous curve; and (iii) the evacuation time from an initial position, or the average time necessary for a person to evacuate a structure, in function of their starting location.

6.8.1 Phenomena of Crowd Self-Organization

The first way to validate a crowd movement model is to attempt to reproduce real-life observed self-organization phenomena [39]. By adapting the three approaches, we have aimed to reproduce two classical phenomena [40, 101]: lane formation in counter flow and arch formation.

Lane Formation in Counter Flow

Observations show that when two groups of pedestrians, going in opposite directions, meet, the pedestrians begin to walk in a line in order to advance as effectively as possible. This phenomenon is called lane formation in counter flow.

We have tried to reproduce this type of situation with our crowd movement model. To do this, we have simulated a throng of 1500 pedestrians. At the beginning, the pedestrians are randomly positioned in a 80 m by 20 m rectangle. Half the pedestrians, represented by blue filled-in circles, wish to move to the right, and the other 750 pedestrians, represented by red empty circles, wish to move to the left (Fig. 6.29a). Since social forces are not introduced in this simulation, only the interior acceleration force is considered. Only this force, therefore, allows the pedestrians to move to their desired destination after a collision. The pedestrians all have identical characteristics (size, mass, desired speed, etc.). To keep the number of pedestrians walking in the considered space constant, as soon as a pedestrian leaves via one side, an identical pedestrian enters the space via a random position on the y-axis of the other side.

In Fig. 6.29b, we can see the phenomenon of lane formation. This phenomenon can be observed in the video at the following link (file melee1500p.avi are available at https://ifsttar.libcast.com/mast-sdoa or at http://extras.springer.com). The number of lanes that are formed depends on the length of the considered space and the density of the pedestrians present [36, 37, 40]. This phenomenon has never been quantified in experimental conditions.

Fig. 6.29

Simulation of a throng of 1500 pedestrians—a $t=0$ s, b $t=40$ s

The simulations seem to demonstrate that with successive collisions (or successive avoidances when social forces are added), a pedestrian ends up falling behind another one moving in the same direction. This walking position no longer demands avoidance of other pedestrians. As the lanes of pedestrians form, it becomes more and more difficult to walk anywhere except in lane. This behaviour is not explicitly planned for by any single pedestrian, but is rather the result of the collected behaviors of all the members in the crowd.

Arch Formation

Observations of pedestrians show that when a dense crowd wishes to go through a narrow opening, the pedestrians place themselves around this opening to exit as quickly as possible: one thus observes the formation of an arch around the exit.

Our crowd movement model allows one to reproduce this type of phenomenon. We have considered 200 pedestrians wishing to evacuate a 20 m by 20 m square room with a 1 m-wide opening on the right side (Fig. 6.30a). Social forces are not introduced. The pedestrians all have identical characteristics (size, mass, desired speed, etc.).

In Fig. 6.30, we can see the formation of an arch, a phenomenon experimentally observed in emergency evacuations. The corresponding simulation can be watched at the following link (file evacuation200p.avi are available at https://ifsttar.libcast.com/mast-sdoa or at http://extras.springer.com).

Fig. 6.30

Simulation of an evacuation from a room—arch formation—$t=0$ s, 200 people wish to evacuation (left); $t=6$ s, 187 people still need to evacuate (middle); $t=12$ s, 166 people still need to evacuate (right)

6.8.2 Evacuation Exercises: Comparison Between Numerical and Experimental Results

In this part, we will present comparisons between results obtained from real-life experiments and results from numerical simulations. Evacuations simulations are analyzed from four different locations: a room, a classroom, a movie theater and an elementary school.

Evacuation of a Room

The objective of this section is to compare an evacuation situation simulated with the three adapted approaches, considering only their manner of handling pedestrian-pedestrian and pedestrian-obstacle local contacts. Social forces are thus not introduced.

Let us consider a square room with sides of 5 m containing 20 pedestrians who wish to leave through an 82 cm-wide door. The parameters used in the simulations are given in Table 6.4.

Table 6.4 Evacuation from a room—parameters used in the evacuation simulations of the square room ($^{*}$uniformly distributed within the given interval); the response time is the time necessary for pedestrian i to begin evacuating the room after the start of the evacuation movement

Since the parameters of the pedestrians are generated randomly within a given interval (Table 6.4), 50 simulations are realized (Fig. 6.31) with the respective time steps $h=10^{-2}$ s, $h=10^{-3}$ s and $h=10^{-4}$ s for each adapted approach. For every approach, the initial conditions of these simulations are identical. Figure 6.31 shows the straight line obtained from a linear regression of the 50 simulations with the adapted NSM2 approach, for $h=10^{-2}$ s. The slope of this line allows one to determine the average flow rate Q of pedestrians crossing the exit. Table 6.5 contains both the values of Q obtained from the simulations that were realized with the three approaches and different time steps, and from a real-life exercise imitating emergency evacuation conditions [42].

Fig. 6.31

Evacuation of a room—evacuation curves for NSM2, with $h=10^{-2}$ s. The cyan-colored curves are the results of the 50 simulations. The linear regression of these simulations (the straight black line) allows one to obtain the average rate of flow for pedestrians exiting through the door

Table 6.5 Evacuation of room—average flow rate Q (ppl/min) of pedestrians leaving through the exit

In Table 6.5, one can see that the influence of the chosen time step on Q is negligible, as long as the temporal integration scheme is stable. In addition, one can observe that the value of Q obtained with the adapted NSM2 approach is very close to the value acquired from the emergency evacuation exercise. The pedestrians evacuate faster with the adapted NSM1 approach than with the other two approaches. These results are likely due to the manner of handling contact: perfectly inelastic for the adapted NSM1 approach, and elastic for the adapted DEM and NSM2 approaches. For these last two approaches, the difference between the values of Q could be caused by the phenomenon of overlapping, necessary for treating contact in the adapted DEM approach. Thus, in order to take into account pedestrians bumping into each other, it seems necessary to employ elastic collisions.

Evacuation of a Classroom

In this section, we will compare between a real-life exercise of a classroom evacuation and numerical simulations. The evacuation exercise, with a classroom of 30 students, is presented in [41]. The width of the classroom is 5.85 m and its length 6.75 m. The room contains 30 desks, organized into six rows and five columns. The longitudinal and transversal distances between the desks are, respectively, 0.9 and 1.35 m. The only door for entering or exiting the room is 0.5 m wide. The evacuation exercise is recorded by two video cameras. At the signal of the cameraman, all of the students stand up from their chairs and rush towards the exit. The parameters used in the numerical simulations are given in Table 6.6. Some of these parameters are uniformly distributed within a given interval. Fifty simulations have been realized.

Table 6.6 Evacuation of a classroom—parameters used in the simulations ($^{*}$uniformly distributed within the given interval); the response time is the time necessary for student i to begin evacuating after the start of the evacuation movement

Figure 6.32 shows examples of the progression of two numerical simulations obtained with the NSM1 and NSM2 adapted approaches. Since the progression obtained with the DEM approach is similar to that attained with the NSM2 approach, the former is not given. For all three adapted methods, a formation of an arch around the exit door is observed. For the DEM and NSM2 approaches, the students evacuate the classroom (first line of Fig. 6.32) without problem, whereas for the NSM1 approach, the students often are blocked (second line of Fig. 6.32).

Fig. 6.32

Evacuation of a classroom—example of the progression of two numerical simulations at different moments. The first line is obtained with the adapted NSM2 approach and the second with the adapted NSM1 approach. The walls are represented in black, the desks in blue, the exit door in magenta and the individuals by red circles

Fig. 6.33

Evacuation of a classroom—average evacuation time of the students starting from their initial positions. The three results presented in each circle give the average evacuation times according to the real-life evacuation exercise (at the top) and according to the numerical simulations (adapted DEM approach in the middle and adapted NSM2 approach at the bottom)

The adapted NSM1 approach does not appear to be effective for this situation. Because of this, we will limit our study to the other two methods. Figure 6.33 gives the average evacuation time of the students starting from their initial position (i.e., the desks). The average evacuation times acquired from the real evacuation exercise are given at the top, those from the 50 numerical simulations realized with the adapted DEM approach in the middle, and those with the adapted NSM2 approach at the bottom. One can observe similarities between the average evacuation times obtained from the evacuation exercise and those from the numerical simulations. First of all, if we consider each column, the average evacuation time increases as a function of the distance $d_{b-s}$: desk position—exit. Next, even if the evacuation times increase in function of $d_{b-s}$, the students in the two first columns (those closest to the door) require a disproportionate time in order to evacuate. Helbing [41], using the real-life evacuation exercise, explains this phenomenon with the fact that students naturally use the aisles between the desks that are closest to the door. If the students are seated at the desks and wish to move toward the exit, this would be the aisle to their left. Therefore, the students seated in the first two columns use the same aisle, increasing the density of people in this aisle and thus their evacuation time. However, using the simulations, we can give a different explanation. During the emergency evacuation, the density of the students around the narrow door becomes too great. Therefore, the students who arrive in front of the door can more easily exit than those who arrive from one of the two sides. The latter have difficulty inserting themselves into the flow of their peers who are leaving.

Fig. 6.34

Representation of the movie theater during a numerical simulation. Seats are portrayed as blue, walls as black, the movie screen as gray, the stairs as yellow, the doors as cyan and the exits as magenta (exit A at the top and exit B at the bottom). In function of the number of people in the red rectangles (the control zones numbered 1, 2 or 3), the moviegoers change from moving in the direction of the beige arrow to that of the magenta arrow

Evacuation of a Movie Theater

Similarly, we will undertake in the following a comparison between a real-life exercise and numerical simulations realized with the adapted NSM2 approach, this time for an evacuation from a movie theater. The evacuation exercise is presented in [57]. A cinema with 174 seats contains 101 seated students whose initial positions are fixed. Two evacuation routes are available, through either exit A or exit B (Fig. 6.34). Everyone in the cinema is asked to act cautiously in order to avoid injuries. After the alarm is set off, the students begin to evacuate in function of their reaction time.

The evacuation times of the students are the results of this real-life evacuation exercise. The parameters used in the simulations are in accordance with the observations made in the exercise and are summarized in Table 6.7. Some of the parameters are uniformly distributed within a given interval.

Table 6.7 Evacuation of a movie theater—parameters used in the simulations ($^{*}$uniformly distributed within the given interval)

One hundred numerical simulations are realized with the adapted NSM2 approach. This approach contains both the interior acceleration and socio-psychological forces presented in Sect. 6.7.1. To evacuate, the pedestrians use the shortest route. Several control zones are added in order to make the pedestrian movement more realistic and to avoid the appearance of areas of congestion (Fig. 6.34).

Fig. 6.35

Example of the progression of a numerical simulation at different times. The red circles represent the pedestrians

If the number of people is greater or equal to 5 in the first and second red rectangles, or greater or equal to 15 in the third, the other pedestrians move in the direction of the magenta arrow instead of that of the beige arrow.

An example of the progression of a numerical simulation is shown in Fig. 6.35 and can be watched at the following link (file evacuationMovieTheater.avi are available at https://ifsttar.libcast.com/mast-sdoa or at http://extras.springer.com).

The results of the real-life exercise and of the numerical simulations are summarized in Table 6.8. From the results summarized in the table, we can see there is practically no difference between the results from the experimental exercise and the results from the numerical simulations; or, at least, the differences are acceptable.

Table 6.8 Comparison between experimental exercise and numerical simulations for the evacuation of a movie theater

Figure 6.36 shows that the curve of the number of evacuated pedestrians in function of time, obtained from the numerical simulations, is very close to its counterpart from the real-life exercise.

Fig. 6.36

Comparison between the results of the experimental exercise and the results of the numerical simulations: number of evacuated pedestrians as a function of time. The 100 numerical simulations are the cyan-colored curves, the average of these is the black curve, and the curve from the real exercise is in red

Evacuation of an Elementary School

We next will apply the adapted NSM2 approach to an evacuation exercise in an elementary school, presented in [57]. This example demonstrates that it is possible to study a 3D problem while using a 2D approach. The building is composed of three floors and contains six classrooms, with a total of 130 pupils (from 6 to 10 years old). The initial number of people in each classroom is given in [57]. After the alarm is set off, the pupils begin the evacuation. Each class of pupils follows its respective teacher. Video footage is taken throughout the evacuation exercise and is used to determine the experimental results. To simulate this exercise, we propose the parameters summarized in Table 6.9. These parameters, meant to represent any given population, are obtained from [39, 57]. Some of these parameters are uniformly distributed within a given interval.

Table 6.9 Evacuation of an elementary school—parameters used in the simulations ($^{*}$uniformly distributed in the given interval)

One hundred numerical simulations are made with the adapted NSM2 approach. This approach contains both the interior acceleration and socio-psychological forces presented in Sect. 6.7.1. To evacuate, the pedestrians use the shortest route. An example of the progression of such a numerical simulation is shown in Fig. 6.37 and can be watched on the following link (file evacuationPrimarySchool.avi are available at https://ifsttar.libcast.com/mast-sdoa or at http://extras.springer.com).

Fig. 6.37

Evacuation of an elementary school—example of the progression of a numerical simulation at different moments. The walls are represented by black, the obstacles by green, the stairs by yellow, the doors by magenta and the pedestrians by red circles

Fig. 6.38

Comparison between results from the real-life exercise and those from the numerical simulations: evacuation of an elementary school—number of evacuated people as a function of time. The cyan curves represent the 100 numerical simulations, the black curve the average of these simulations, and the red curve the experimental exercise

Figure 6.38 shows the curves of the number of evacuated pedestrians as a function of time, obtained from the results of the experimental exercise and from the average of the results of the numerical simulations. Since the parameters of the numerical simulations hold true for any standard population, the results of these simulations are very close to those obtained from the experimental exercise. One can notice that on the evacuation curve obtained from the exercise, the flow suddenly decreases at $t\simeq 38$ s, then increases again after $t\simeq 48$ s. This phenomenon (possibly a jam or back-up) is not reproduced by our model. One possible explanation is that the pupils become blocked at some part of the building, probably when two classes meet in the stairwell. The fact that the pupils are grouped next to their teacher could add to this blockage.

6.8.3 A Predictive Model

This section has the objective of demonstrating that the adapted $\textit{NSM}2$ approach can be used to improve the service quality of a studied space. In the first study, we will look to see if the addition of a well-placed obstacle in front of a door can improve the service quality of its associated area. In the second study, we will seek to determine if the proposed crowd model can be used to locate in a considered space the zones that could give rise to pedestrian injury during an emergency evacuation. Finally, the third study will concern the modeling of travelers switching from train to platform or vice versa. This study will propose a solution to facilitate the evacuation of train platforms.

Addition of an Obstacle in Front of a Door

Let us consider a crowd that wishes to evacuate a room via a narrow door. For these types of geometries, called bottlenecks, researchers pay close attention to clogging or blockage, an effect that can arise at or close to the door. Theoretically, human behaviour during panic situations leads to arching and clogging as shown in Fig. 6.2 or 6.39a, respectively. In normal situations, pedestrians don’t rush toward the exit and a funnel shape is obtained rather than an arch (see Fig. 6.39b). Both phenomena can be watched on the following links (files clogging.avi and funnel.avi are available at https://ifsttar.libcast.com/mast-sdoa or at http://extras.springer.com).

Fig. 6.39

Simulation of a an urgent and b a normal evacuation through a bottleneck

Table 6.10 Evacuation of a square room with or without an obstacle—parameters used in the simulations ($^{*}$uniformly distributed in the given interval)

Clogging results in a reduction in the efficiency of the evacuation and creates strong pressures within the backed-up crowd. One possible remedy for this problem would be to place an obstacle in front of the door, as Helbing [36] has experimentally tested. In [106], experimental results have been presented about the effect that an obstacle has in the granular flow through an orifice. Previous authors showed that if the position of the obstacle is properly selected, a dramatic decrease of the clogging probability can be obtained. Interestingly, the clogging reduction effect is not caused by a net reduction of the flow rate, neither by a reduction of the density of particles at the very outlet. Instead, it is suggested that the introduction of an obstacle induces a strong reduction of the pressure above the outlet. This behaviour, which is proposed to be the one behind the clogging reduction, could have an analogy in the flow of crowds through bottlenecks, where it has been typically assumed that the main role of a column behind a door is to prevent straight motion of people towards the exit.

Continuing these considerations, in this section we will attempt to determine if our adapted $\textit{NSM}2$ approach is able to model this type of problem and to show how a space’s service quality can be improved during an emergency evacuation. Let us consider a 5 by 5 m square room that contains 20 people wishing to exit through a door 82 cm wide. In some of the simulations, an obstacle (for example, a pillar, etc.) will be placed in front of the exit.

The parameters used in the simulations are given in Table 6.10 and are uniformly distributed in their mentioned interval.

The flow rate J of people going through the exit was first calculated for every run. J (people/min) represents the number of pedestrians $\bigtriangleup N$, that passes a certain facility (in our case the narrow door) within a certain time interval $\bigtriangleup t$: $J= \frac{J}{b}=\frac{\bigtriangleup N}{\bigtriangleup t}$. The average flow rate $J_{mean}$ of J is then obtained and determined by $\tau$ and the parameters of the obstacle (position, distance from the exit, form and size).

Numerical simulations are carried out using the adapted $\textit{NSM}2$ approach, without introducing social forces. In emergency evacuation situations, pedestrians use the shortest path to evacuate. Several cases are simulated for different values of $\tau$ and varying positions, shapes and lengths of the rectangular obstacle that maintains a width of 0.45 m throughout the simulations (Fig. 6.40). Fifty simulations are executed for each position of the obstacle.

The values of $J_{mean}$ for the different simulations are presented in Table 6.11.

According to these results, when $\tau$ varies from 0.5 to 0.1 s, the number of evacuated pedestrian increased considerably. Smaller values of $\tau$ indicate more aggressive pedestrians who do not hesitate to rush and quickly regain their desired speed after a collision. When $\tau =0.1$ s and the obstacle is central ($p_{1} = 0.41$ m), $J_{mean}$ increases in relation to the dimensions of the obstacle. However, the evacuation of the pedestrians is only facilitated when the obstacle is close enough to the exit ($p_2 = 0.7$ m). On the other hand, when $\tau =0.5$ s and the obstacle is far from the exit ($p_{2} = 0.9$ m), the values of $J_{mean}$ are practically the same with and without the obstacle; and when the obstacle is near the exit ($p_{2} = 0.7$ m), there is no improvement in the quality of the evacuation service.

Fig. 6.40

Different positions of the obstacle in function of $L_o$, $p_1$ and $p_2$

Table 6.11 Evacuation of a square room with or without an obstacle—average flow $J_{mean}$ (pedestrian/min) of pedestrians going through the door as a function of $\tau$, $p_1$, $p_2$, obstacle’s shape (rectangular or circular) and obstacle’s size ($L_o$ or $D_o$)

When the obstacle is not centered on the exit ($p_{1} = 0$ m), in both cases $\tau =0.1$ s and $\tau =0.5$ s, $J_{mean}$ decreases as the dimensions of the obstacle increase.

The simulations show that an obstacle centered near the exit increased $J_{mean}$ in proportion to the length of the obstacle.

Numerical simulations have also been carried out with a circular obstacle. Depending on the values of the parameters $\tau$, $p_1$, $p_2$, and $D_o$, the circular obstacle can increase the average flow of evacuating pedestrians $J_{mean}$, improving the evacuation process in some cases (e.g. $\tau = 0.1$ s, $p_1= 0.41$ m, $p_2= 0.7$ m, and $D_o = 0.636$ m). More research will need to be conducted to determine the optimal parameters $\tau$, $p_1$, $p_2$, and $L_o$/$D_o$ for a circular and rectangular obstacle.

Evacuation of a Room with Two Adjacent Exits

The goal of this section is to show that the proposed crowd model can be used to estimate the areas and pedestrians in a room that are subjected to strong pressure during an emergency evacuation. Human tolerance for pressures and forces depends on the amplitude, duration, direction, and location of the contact force. For example, receiving a slap to the face can briefly generate hundreds of g (acceleration of gravity) locally, but does not produce any real damage; however, constant application of 16 g for one minute can be fatal. The position, age, and health of the pedestrian may also affect their tolerance. Because of the large number of varying properties possessed by the contact force and the pedestrian, determining whether a collision between two pedestrians can result in an injury is a complex problem. Therefore, only the areas of the room where the contact percussion is at its highest during evacuation will be studied.

The evacuation of a room containing 500 people who want to evacuate through two adjacent exits is simulated; the distance between the two exits is 4 m. The parameters used in the simulation are summarized in Table 6.12.

Table 6.12 Evacuation of a room with two adjacent exits - parameters used in the simulations ($^{*}$uniformly distributed over the given interval)

Figure 6.41 presents an example of an evacuation simulation.

Fig. 6.41

Evacuation of a room with two adjacent exits—pedestrians are colored according to the value of the contact percussion: gray when the pedestrian is not in contact with anything in their immediate environment, and otherwise, a color spectrum from yellow to red as their contact percussion increases. The green rectangle is the area in which pedestrians could be injured

The formation of an arch as a function of the value of the contact percussion is observed in front of each exit. The pedestrians exiting are not under pressure in the doorway, as if they were being protected by other pedestrians. Similarly, the pedestrians the farthest from the exits cannot be injured because they are not subjected to strong pressures. The people trapped between the two exits by the two streams of evacuating pedestrians are subject to strong pressures. In this area, a pedestrian could be injured (area defined by green rectangle on Fig. 6.41).

Modeling Travellers Moving Between Platform and Subway Car

This application of the model is the result of a pre-project for the RATP (RATP is the large Paris public transportation company) aimed at reducing evacuation time of a subway car in subway stations with a single exit. This project suggests the instillation of flashing arrows in such stations that indicate the direction of the exit when the train is stopped and are completely invisible when turned off.

This system is supposed to decrease the amount of time commuters spend moving between train and platform, using the numerical analysis to optimize the device. It should be noted that estimating the flows of people in the stations and subway cars in real time would require comprehensive (appropriate) software, according to the RATP.

Two scenarios are considered: with and without the presence of the indication arrow. Two times are compared in the two scenarios considered: the time required for a pedestrian starting outside the subway car to board a subway car and the time required for the pedestrians starting inside the subway car to exit onto the platform.

We will consider one part of a platform and one subway car. To simulate the two scenarios, we use the parameters given in Table 6.13 to represent a standard population. Some parameters are uniformly distributed over the given interval.

Table 6.13 Modeling travellers moving between platform and subway car- parameters used in the simulations ($^{*}$uniformly distributed over the given interval); the response time is the time necessary for pedestrian i to begin to evacuate after the start of the evacuation

Fifty numerical simulations of the two scenarios are carried out using the adapted $\textit{NSM}2$ approach. For each simulation, the initial conditions are exactly the same for the two scenarios, i.e. 20 pedestrians want to enter into the subway car and 25 pedestrians out of the 34 randomly positioned in the car want to get out.

The two scenarios, with and without the indication arrow, proceed as follows:

*:

$0\ \Rightarrow \ 10$ s: the subway car arrives and the indication arrow begins flashing.

*:

$10\ \Rightarrow \ 15$ s: the indication arrow continues flashing as the pedestrians position themselves around the doors.

*:

15 s: the doors open and pedestrians begin to exit the subway car, the pedestrians outside the car wait for the pedestrians inside to exit, allowing them to board.

*:

$15\ \Rightarrow \ 20$ s: the indication arrow remains illuminated.

*:

20 s: if the pedestrians have not finished exiting the subway car, the people outside the car force their entry.

Once the pedestrians have reached the yellow tactile strip:

*:

With the indication arrow: the pedestrians move randomly amongst themselves for 0.5 s (standard reaction time) before heading towards the exit to the right of the platform.

*:

Without the indication arrow: the pedestrians move randomly amongst themselves for 3 s (standard reaction time $+$ looking for the exit), slowing down to look for the exit before heading towards the exit to the right of the platform.

An example simulation of a platform/subway car exchange with and without an indication arrow is represented in Fig. 6.42 and can be watched at the following link (files metro_with_arrow.mp4 and metro_without_arrow.mp4 are available at https://ifsttar.libcast.com/mast-sdoa or at http://extras.springer.com). The dimensions of the car are the same as those of RATP cars. The people in blue are men, and those in pink are women. Once a person has found the exit of the platform, they will be colored in beige.

Fig. 6.42

Example of a simulation of a platform/subway car exchange a without and b with indication arrow

The results obtained from the simulations of a platform/subway car exchange for the two scenarios are summarized in Table 6.14.

The presence of the blue arrow does not change the speed of the pedestrians boarding the subway car, but does help pedestrians exiting the subway car evacuate the platform.

Table 6.14 Results of the simulations of a platform/subway car exchange with and with indication arrow

Modeling Subgroup Movement

The adapted $\textit{NSM}2$ approach is currently used to model the sub-group movement. The specific instances of counter-current movement by several sub-groups have been filmed. The video clips were chosen from [95]. Parameters such as the number of people, the number of sub-groups and the physical considerations were recorded. Situations in which members of sub-groups walking against the flow of pedestrian traffic, in groups of 2 to 4 people, have had to take evasive, measures have been selected.

The selected situations are reproduced with the proposed crowd movement model. The simulations are also performed with the Singh sub-group model [95]. The values of the parameters are: $d_{l,f}=0.7$ m, $\varphi _{l,f}=\pm \frac{\pi }{2}$ and $k_{sgr}=0.15$ s$^{-1}$ [72, 95].

Two simulated scenarios are presented in Fig. 6.43. Our results correlate strongly with the videos and digital simulations. For more details, see [79].

Fig. 6.43

Modeling sub-group movement in a crowd of pedestrians- Comparison between video sequences and numeric simulations. Corresponding sub-groups are circled in the same color

Conclusions

The 2D model based on the theory developed by Michel Frémond and adapted to crowd movement showed its efficacy in treating collisions between pedestrians and in estimating the time and flow of pedestrians to evacuate in an emergency situation, [54]. Thanks to its mechanical formulation using the principle of virtual work and the treatment of collisions by means of non smooth mechanics, this model has proved to correctly represent a wide variety of behaviors (elastic and inelastic collisions with rebound or not, pedestrians holding hands, etc.). However, in urgent evacuations or even highly dense events, it is important to evaluate the pressure applied to the pedestrians’ bodies in congested areas. This allows us to test measures and solutions aimed at preventing the pressure from reaching fatal levels. In order to achieve this, the particles representing pedestrians must be rendered deformable. This subject is currently in progress.

Whereas in high density crowds collisions are inevitable, in a sparse crowd pedestrians don’t appreciate the contact and prefer to avoid touching and maintain a personal space. Our model must be then improved, in order to be consistent with the experimental observations.

Different approaches for avoidance behaviors are addressed in [53]. In the cognitive approach, a pedestrian can assess the remaining distance to the first possible collision and the global distance to destination. Then by assessing the two distances he/she dodges possible collisions (without any effect on neighboring individuals) while minimizing the traversed distance to destination. As for the social repulsive force, its interest lies in modeling pushing or aggressive behaviour. A combination of the two approaches seems to be of interest in certain applications such as in railway stations especially during alighting/boarding processes. The 2D model was recently used in a study aimed at estimating the train dwell time (the time a train spends at a scheduled stop) at the RER-A Noisy Champs station (RER-A is the line A of the Réseau Express Régional) have been investigated for a given demand of boarding and alighting passengers, [66]. Two simulations of about 30 pedestrians passing through the turnstiles and about 50 pedestrians boarding and alighting the train can be watched at the following links (files tourniquet.avi and NoisyChamp.avi are available at https://ifsttar.libcast.com/mast-sdoa or at http://extras.springer.com). This study has been a part of evaluating public transport in the Île-de-France region. With a rising demand for public transport, it has become crucial to assess the design of pedestrian areas in the region’s railway and transfer stations as well as the impact of changes in the timetables of public transit systems. This is one of the objectives of the Grand Paris project that aims to modernize the existing transport network, to improve residents quality of life, and build a sustainable city.