Smooth/non-smooth contact modeling of human crowds movement: numerical aspects and application to emergency evacuations

Abstract

The aim of this paper is to develop on discrete models that reproduce the behavior of a crowd of people in several emergency evacuation situations. The first step in this study is to determine how to treat contacts between pedestrians. For that, three already existing discrete approaches, one smooth and two non-smooth, originally proposed to simulate the collisions of granular assemblies, are first analyzed both from the theoretical and the numerical point of view. The solving algorithms are presented and the numerical formulation of the two non-smooth approaches is compared to standard plasticity in order to point out the common theoretical framework. The next step is to adapt these discrete approaches to represent pedestrians. The key point is to introduce a “willingness” for each particle through a specific desired velocity. These adapted discrete approaches are able to handle local interactions, like pedestrian-pedestrian or pedestrian-obstacle contacts, in order to reproduce the global dynamic of pedestrian traffic. Finally, results of several simulations in emergency configurations are presented as well as compared to real exercise ones.

1 Introduction

Over the last 50 years, many studies have been performed to describe the behavior of walking pedestrians [17, 18]. Models of crowd movements have been developed to reproduce particular crowd phenomena. These models may be classified according to the mode of representation of the crowd: (1) macroscopic models, where the crowd is represented as a whole [2, 5, 23, 25, 26, 44, 45], or (2) microscopic models [4, 18, 19, 24, 38, 40, 41, 43, 49, 52, 53], where the behavior, actions, and decisions of each crowd member are treated individually.

In this paper, a microscopic crowd model is sought. The first step in the modeling is to manage the contacts between pedestrians. Many approaches have been developed over the last decades to simulate the evolution and movements of granular systems formed by perfectly rigid particles. Among them, some of the most widely used belong to the “Discrete Element” (DE) class, which deals with multiple simultaneous collisions. Thus, our idea is to extend and adapt these discrete models for studying the movements of human flow networks. To be considered as a pedestrian, each particle must have a “willingness” to move toward a given target, which might be time varying.

Within the DE class, two categories can be identified according to the way the contact is treated: the “smooth” approaches [1, 9, 10, 30] and the “non-smooth” approaches [15, 16, 27, 28, 36, 37, 39, 47, 48, 50, 46].

Regular approaches introduced by Cundall [9] handle contacts with a repulsion force. The contact forces are determined by a direct calculation: the forces’ amplitude depends on the distance between particles. The use of stiff repulsion laws leads to a “slight” interpenetration between particles and requires small time steps to ensure the stability of the time integration scheme. The Distinct Element Method (DEM) (Cundall [9, 10]) is characteristic of this class of regular approaches. It has inspired many of the other approaches in this class and is often used for comparison and understanding of their performance. Helbing [18−20] already applied such an approach to the crowd.

In non-regular approaches, contact forces are determined from the solution of local nonlinear equations. The non-smoothness is retrieved in three nonlinear aspects: (1) spatial non-linearity, due to the condition of geometric non-interpenetration (use of inequalities instead of equalities); (2) time nonlinearity, due to shocks between particles (velocity discontinuities); and (iii) the nonlinear contact law. Non-regular laws are used to link forces with the configuration parameters (unilateral contact). The most prevalent non-smooth approach in granular media simulations is the Non-Smooth Contact Dynamics (NSCD) approach, developed by Moreau and co-workers [28, 37, 48, 50]. It is based on the use of the “coefficient of restitution” in order to represent changes in the relative velocity of a rigid particle before and after collision. Two approaches built following Moreau’s line of work and termed respectively, “NSM1” and “NSM2” caught our attention. In the first one developed by Maury [32], the contact force between two colliding particles is determined with a constraint on the particles’ position. Such an approach has already been applied to crowd modeling by Venel [33, 53]. The second approach has been proposed by Frémond and co-workers [11, 12, 15, 16], where the contact force between two colliding particles is determined with a constraint on the relative deformation velocity between particles, as in Moreau’s approach. The particles’ system is considered deformable, and the motion equations result from the principle of virtual work, whereas constitutive laws are given by a pseudopotential of dissipation. In Frémond’s approach, the rebound is characterized through a “coefficient of dissipation” instead of the “coefficient of restitution” used by Moreau. Frémond [16] showed that the use of a restitution coefficient may be inappropriate in correctly representing the collision of more than two particles.

This paper is divided into three parts. The first section introduces the three approaches previously mentioned that are well-suited for studying granular assemblies: DEM, NSM1 and NSM2. Both their theoretical and numerical aspects are presented. Making some assumptions, both non-smooth approaches will be rewritten with the same formalism as the one used for the standard plasticity. In NSM2, for the sake of simplicity, a quadratic pseudopotential of dissipation augmented with indicator functions is chosen in the following numerical simulations. In the second section, we focus on how to adapt the three approaches to the crowd by giving a “willingness” to the particles [41, 42, 43]. Finally, several numerical simulations of emergency evacuation situations are performed and presented in the last section to compare the three approaches with each other and with experimental data.

2 Presentation of three approaches for granular media

A granular medium is by definition a set of particles subjected to gravity that interact with each other by contacts, with or without friction and with or without cohesion. In this paper, we assume that the movement of the particles stays in a plane, particles are circular with a more or less large size, and their rotation is neglected. However, refer to Dal Pont and Dimnet [11] for extended research with particles of more complex shapes.

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

$$\left\{ \begin{array}{ll} \underline {\dot{q}}(t) =\,\underline{u}(t) \\ \underline {\underline {M}} \, \underline {\dot{u}}(t) =\,\underline {f}(t)+ \underline {g}(t) \end{array} \right.$$

(1)

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

Two major steps exist in each of the three approaches: the detection and the treatment of every contact. We analyze only particle-particle interactions because particle-obstacle interactions can be treated analogously.

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

$$ D_{ij}(\underline {q})=\Vert \underline {q}_{j}-\underline {q}_{i}\Vert -(r_{i}+r_{j}) $$

(2)

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

There is contact between particles i and j when $D_{ij}(\underline {q})=0$ and an overlap when $D_{ij}(\underline {q})<0.$ In order to reduce the computation time, an efficient method of detection of contacts [14], or closest neighbors, becomes necessary when the number of considered particles increases. However, due to the relatively small number of considered particles in the simulations presented in this article, its use is not necessary in our research.

The next step is to determine the contact force vector $\underline {g}(t)$ in order to find $\underline {u}(t)$ and $\underline {q}(t).$ In DEM, the local contact force between two particles i and j is chosen to be proportional to D _ij ; in NSM1, it is defined so that particles never overlap, i.e. there is a constraint on the particles’ position; and finally, in NSM2, it is determined by means of a constraint on the relative deformation velocity between particles. Differences and similarities in contact treatment among the three approaches are detailed in the next sections, both analytically and numerically. Thus, it will be shown that the discretization of both the NSM1 and NSM2 approaches fits into the same framework of constrained minimization problems.

2.1 Theoretical aspects of the three approaches

2.1.1 DEM

In the “smooth” approach introduced by Cundall in the seventies [9, 10], contacts are treated using regular forces. The expression of the repulsive force representing local interaction through contact between particles i and j, applied to particle i, is given by:

$$ \underline {g}_{ij}(t)=k\min \left( 0,D_{ij}(\underline {q}(t))\right) \underline {e}_{ij}(t) $$

(3)

where k is a constant stiffness. Helbing et al. [20] chose k = 1.2 × 10⁵ kg s⁻² for crowd simulations.

The total contact force applied to the particle i is then:

$$ \underline {g}_{i}(t)=\sum\limits_{\mathop{ j=1} \limits_{ j\neq i}}^{N}{ \underline {g}_{ij}(t).} $$

(4)

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

2.1.2 NSM1

In this approach [32], contacts between circular particles are treated as purely inelastic collisions, i.e. no rebound is considered. The extension of this approach to other types of collisions (elastic collisions) is not straightforward, as mentioned by Maury [32]. The particles’ positions must always be admissible, i.e. there should never be any overlap between particles. At the moment of one collision, there is a discontinuity of the velocity $\underline {u}.$ Hence, the velocity after collision $\underline {u}^{+}$ is determined so that the positions of colliding particles are feasible, i.e. $\underline {u}^{+}$ has a “geometrical” meaning rather than a “physical” meaning. The particles’ velocities after contact $\underline {u}^{+}$ must belong to the set of admissible velocities defined by:

$$ C_{\underline {q}}=\left\{ \underline {v}\in R^{2N}:\forall i<j,\quad ^{t} \underline {G}_{ij}(\underline {q})\underline {v}\geq 0\,\hbox {as soon as}\,D_{ij}(\underline {q})=0\right\} $$

(5)

$$ \begin{array}{rl} \hbox{ where }\quad ^{t}\underline{G}_{ij}(\underline{q}) & =\nabla D_{ij}( \underline{q}) \\ & =\left( 0,\ldots,0,-\,^{t}\underline{e}_{ij},0,\ldots,0,\,^{t}\underline{e} _{ij},0,\ldots,0\right) \in R^{2N}. \\ & \quad \quad\quad \,\,\, \uparrow \quad \quad \quad \quad \uparrow \\ & \quad \quad\quad \,\; \hbox{particle }i \quad\quad\; \hbox{particle }j \end{array} $$

(6)

Thus, as overlapping is forbidden by virtue of condition $^{t}\underline {G}_{ij}(\underline {q})\underline {u}^{+}\geq 0,$ two particles i and j already in contact can only increase or preserve their relative distance. The polar cone $N_{\underline {q}}$ of $C_{\underline {q}}$ is introduced [32, 34]:

$$ \begin{aligned} N_{\underline {q}} &=\left\{ \underline {w}\in R^{2N},\quad ^{t}\underline {w}\,\underline {v}\leq 0 \quad \forall \underline {v}\in C_{\underline {q}}\right\} \\ & =\left\{ -\sum\limits_{i<j}\mu_{ij}\underline {G}_{ij}(\underline {q}),\, \mu_{ij}=0\,\;\hbox {if}\,\; D_{ij}(\underline {q})>0,\, \mu_{ij}\in R^{+}\,\; \hbox {if}\,\; D_{ij}(\underline{q})=0\right\}. \end{aligned} $$

(7)

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

$$\left\{ \begin{array}{ll} \underline{\underline{M}}\,\underline{\dot{u}} + N_{\underline{q}} \ni \underline{f} \\\underline{u}^{+}=P_{C_{\underline{q}}}\underline{u}^{-}\end{array} \right.$$

(8)

where $P_{C_{\underline {q}}}$ is the Euclidean projection onto the closed convex cone $C_{\underline {q}}.$ A solution of this problem exists [3, 33].

When there is no contact, the first equation of (8) reads as the ordinary differential equation $\underline {\underline {M}}\,\underline {\dot{u}}= \underline {f}.$ When there is a contact, the previous equation can be read: $\exists \underline {g}\in- N_{\underline {q}}\, \hbox {such that}\,\underline {\underline {M}}\,\underline {\dot{u}} = \underline {f}+\underline {g},$ where the expression of the total contact force is $\underline{g}=\sum\nolimits_{1\leq i<j\leq N}\mu_{ij}\underline {G}_{ij}(\underline {q}).$ The second equation of (8) provides the collision model. $\underline {u}^{+}$ is then defined as the Euclidean projection of the velocity before contact $\underline {u}^{-}$ on the set $C_{\underline {q}}.$ This approach leads us to solve the following constrained minimization problem:

$$ \fbox{$\underline {u}^{+}= \begin{array}{c} \arg\min \\ \underline {v}\in C_{\underline {q}}\end{array}\left[ \frac{1}{2}\Vert \underline {v}-\underline {u}^{-}\Vert_{\underline {\underline {M}}}^{2}\right] $} $$

(9)

where $\|\underline {X}\|_{M}^{2}=^t\underline {X}\,\underline {\underline {M}}\,\underline {X}.$

2.1.3 NSM2

NSM2 is an original approach based on the theory of rigid bodies’ collisions first proposed by Frémond [15, 16] in a rigorous thermodynamic frame, along the lines of the works of Moreau [36]. The numerical aspects were later developed by Dal Pont and Dimnet [11, 12].

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 [12]. The relative deformation velocity between the i ^th and j ^th particles is introduced: $\underline{\Updelta}_{ij}(\underline {u}(t))=\underline {u}_{i}(t)-\underline {u}_{j}(t).$

The system (1) is rewritten:

$$ \left\{\begin{array}{ll} \underline{\underline{M}}\,\underline{\dot{u}}(t) =-\underline{f}^{int}(t)+\underline{f}^{ext}(t) \quad \hbox {almost everywhere} &\quad (10) \\ \underline{\underline{M}} \left(\underline{u}^{+}(t)-\underline{u}^{-}(t)\right)=-\underline{p} ^{int}(t)+\underline{p}^{ext}(t) \quad \hbox {everywhere} &\quad (11) \end{array}\right. $$

where $\underline {f}^{ext}$ (resp. $\underline {f}^{int}$) is the exterior forces vector (resp. interior forces vector) of dimension 2N applied to the deformable system. The existence of a solution of the system given by Eqs. (10) and (11) is proven in [7, 12, 16]. Equation (10) describes the smooth evolution of the multi-particle system, whereas (11) describes its non-smooth evolution during a collision. Hence, Eq. (10) applies almost everywhere, except at the instant of the collision, where it is replaced by Eq. (11). When contact is detected, velocities of colliding particles are discontinuous, and so in Eq. (11), the percussions $\underline {p}^{int}$ and $\underline {p}^{ext},$ interior and exterior to the system respectively, are introduced. By definition, percussions have the dimension of a force multiplied by a time. The $\underline{p}^{int}$ percussions are unknown; they take into account the dissipative interactions between the colliding particles (dissipative percussions) and the reaction forces that permit the avoidance of overlapping among particles (reactive percussions). Frémond [15, 16] defined the velocity of deformation at the moment of impact $\frac{\underline {\Updelta }(\underline {u}^{+})+\underline {\Updelta }(\underline {u}^{-})}{2}$ and showed that $\underline {p}^{int}$ is defined in duality with $\frac{\underline {\Updelta }(\underline {u}^{+})+\underline {\Updelta }(\underline {u}^{-})}{2}$ according to the work of internal forces. He then introduced a pseudopotential of dissipation $\Upphi$ that allows us to express $\underline {p}^{int}$ as:

$$ \underline {p}^{int}\in \partial \Upphi \left( \frac{\underline {\Updelta }( \underline {u}^{+})+\underline {\Updelta }(\underline {u}^{-})}{2}\right) $$

(12)

where the operator ∂ is the subdifferential that generalizes the derivative for convex functions [16] (see Appendix 1).

The convex function $\Upphi$ [35] is defined as the sum of two pseudopotentials: $\Upphi =\Upphi ^{d}+\Upphi ^{r},$ where $\Upphi ^{d}$ and $\Upphi ^{r}$ characterize the dissipative and reactive interior percussions respectively. The pseudopotential $\Upphi ^{d}$ is chosen to be quadratic: $\Upphi^{d}(y)=\frac{K}{2}y^{2},$ where K is a coefficient of dissipation. This choice allows one to find the classical results when the coefficient of restitution is used. Other choices of $\Upphi ^{d}$ allow one to obtain a large variety of behaviors after impact [6, 16].

In Eq. (11), the problem is to find the velocity $\underline{u}^{+}$ after particles’ collision. To determine $\underline{u}^{+},$ we have to solve the following constrained minimization problem:

$$ \fbox{$\begin{array}{c} \underline {X}= \begin{array}{c} \arg\min \\ \underline {Y}\in{\mathbf{R}}^{2N}\end{array}\left[^t\underline {Y}\, \underline {\underline {M}}\,\underline {Y}+\Upphi(\underline {\Updelta}(\underline {Y}))-^t(2\underline {u}^{-}+\underline {\underline {M}}^{-1}\underline {p}^{ext})\underline {\underline {M}}\,\underline {Y}\right] \\ \end{array} $} $$

(13)

where the solution $\underline {X}=\frac{\underline {u}^{+}+\underline {u}^{-}}{2}.$

In this approach, the velocity of a particle after a contact ($\underline {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 [11, 12, 15, 16].

2.2 Numerical aspects of the three approaches

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

For both NSM1 and NSM2, after making some assumptions, the contact problem can be written with the same formalism as that used in plasticity. The minimizing problem in the case of plasticity can be written [51]:

$$ \fbox{$\begin{array}{c} \underline {\underline {\sigma }}^{n+1}=\begin{array}{c} \arg \min \\ \underline {\underline {\sigma }}\end{array}\left[ \frac{1}{2}\Vert \underline {\underline {\sigma }}-\underline {\underline {\sigma }}_{predicted}\Vert _{\underline {\underline {\underline {\underline {C}}}}^{-1}}^{2}+\Updelta \lambda f(\underline {\underline {\sigma }})\right] \\ \hbox {with}\,\underline {\underline {\sigma }}_{predicted}=\underline {\underline {\sigma }}^{n}+\underline {\underline {\underline {\underline {C}}}}\, :\Updelta \underline {\underline {\varepsilon }} \\ \end{array}$} $$

(14)

where $\Vert \underline {\underline {X}}\Vert_{\underline {\underline {\underline {\underline {C}}}}^{-1}}^{2}=^{t}\underline {\underline {X}}:\underline {\underline {\underline {\underline {C}}}}^{-1}:\underline {\underline {X}}, \underline {\underline {\underline {\underline {C}}}}$ is the elasticity tensor, $\Updelta \underline {\underline {\varepsilon }}=\underline {\varepsilon }^{n+1}-\underline {\varepsilon }^{n}$ is the total strain increment, $\Updelta \lambda$ is the plasticity multiplier, $f(\underline {\underline {\sigma }})$ is the elastic domain, and $\Updelta \lambda$ and $\underline {\underline {\sigma }}$ satisfy the inequalities:

$$\left\{\begin{aligned} f\left(\underline {\underline {\sigma }}^{n+1} \right) & \le 0 \\ \Updelta \lambda & \ge 0 \\ \Updelta \lambda \,f\left(\underline {\underline {\sigma }}^{n+1} \right) & = 0. \\ \end{aligned} \right.$$

(15)

In other words, the minimization problems obtained with NSM1 and NSM2 can also be solved using the well-known solving algorithms proposed, e.g. in [51].

2.2.1 DEM

The positions and velocities of particles at time t ⁿ⁺¹ are given by the explicit scheme:

$$\left\{ \begin{array}{ll} \underline {u}^{n+1} &=\underline{u}^{n}+h\,\underline {\underline {M}}^{-1}( \underline{f}^{n}+\underline {g}^{n}) \\ \underline {q}^{n+1} &=\underline {q}^{n}+h\underline {u}^{n+1} \end{array} \right.$$

(16)

where $\underline {f}^{n}$ is the vector of forces at a distance and $\underline {g}^{n}$ is the vector of contact forces at time t ⁿ (Eq. 1). From Eqs. (3) and (4), the contact force applied to the particle i at time t ⁿ is given by:

$$ \underline {g}_{i}^{n}=\sum\limits_{\substack{ j=1 \\ j\neq i}}^{N}k\min (0,D_{ij}(\underline {q}^{n}))\underline {e}_{ij}^{n}. $$

(17)

The overlap and stability of the time integration scheme depend on the chosen time step denoted by h [9, 43]; hence its choice is essential.

2.2.2 NSM1

The positions of particles at time t ⁿ⁺¹ are obtained by the iterative equation:

$$ \underline {q}^{n+1}=\underline {q}^{n}+h\underline {u}^{n+1} \\ $$

(18)

where $\underline {u}^{n+1}$ has to be found such that $D_{ij}(\underline {q}^{n+1})\geq 0.$

As D _ij is convex, the following relationship can be established:

$$ D_{ij}(\underline {q}^{n+1})=D_{ij}(\underline {q}^{n}+h\underline {u} ^{n+1})\geq D_{ij}(\underline {q}^{n})+h^{t}\underline {G}_{ij}(\underline {q} ^{n})\underline {u}^{n+1}\geq 0. \\ $$

(19)

So, we search $\underline {u}^{n+1}$ such that the approximation of the final distance between each pair of particles $D_{ij}(\underline {q}^{n})+h^{t}\underline {G}_{ij}(\underline {q}^{n})\underline {u}^{n+1}$ is positive or zero.

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

$$ \fbox{$\begin{array}{c} \underline {u}^{n+1}=\begin{array}{c} \arg \min \\ \underline {v}^{n+1}\in R^{2N}\end{array}\left[ \frac{1}{2}\Vert \underline {v}^{n+1}-\underline {V}_{predicted}\Vert_{\underline {\underline {M}}}^{2}-\sum\limits_{1\leq i<j\leq N}\mu _{ij}^{n+1}(D_{ij}(\underline {q}^{n})+h^{t}\underline {G}_{ij}(\underline {q}^{n})\underline {v}^{n+1})\right] \\ \hbox {with}\quad \underline {V}_{predicted}=\underline {u}^{n}+h\underline {\underline {M}}^{-1}\underline {f}^{n} \\ \end{array}$} $$

(20)

where $\mu_{ij}^{n+1}$ is a Lagrange multiplier and has the dimension of a force. $\mu_{ij}^{n+1}$ and $\underline {u}^{n+1}$ must satisfy the Kuhn-Tucker conditions:

$$\left\{ \begin{array}{ll} \mu_{ij}^{n+1} &\geq\, 0 \\D_{ij}(\underline {q}^{n})+h^{t}\underline {G}_{ij}(\underline{q}^{n}) \underline {u}^{n+1} & \geq\, 0 \\ \mu_{ij}^{n+1}\left(D_{ij}(\underline {q}^{n})+h^{t}\underline {G}_{ij}( \underline{q}^{n})\underline {u}^{n+1}\right) & =\,0. \end{array} \right.$$

(21)

The convergence of the numerical scheme given by Eqs. (18), (20), and (21) is proven in [3]. The inelastic collision law is implicitly included in the constrained minimization problem (20). The constraint affects the positions of particles at the end of the considered time step, and $\underline {u}^{n+1}$ is computed such that these positions are admissible.

The expression of $\underline {u}^{n+1}$ and $\mu_{ij}^{n+1}$ is related by:

$$ \fbox{$\underline {\underline {M}}\,\underline {u}^{n+1}=\underline {\underline {M}}\,\underline {u}^{n}+h\underline {f}^{n}+h\sum\limits_{1\leq i<j\leq N}\mu_{ij}^{n+1}\underline {G}_{ij}(\underline {q}^{n}) $} $$

(22)

when $\mu_{ij}^{n+1}$ and $\underline {u}^{n+1}$ satisfy the Kuhn-Tucker conditions (21).

2.2.3 NSM2

On each interval [t ⁿ, t ⁿ⁺¹], regular forces are substituted by percussions applied at the time $\,\theta _{n}=t^{n}+\frac{h}{2},$ and all the non-regular forces, or the percussions applied during the collision, are applied to the system at $\theta_{n}.$ Both Eqs. (10) and (11) are numerically treated at the same time. Hence, interior (resp. exterior) percussions to the deformable system are the sum of the interior (resp. exterior) percussions during contacts and the percussions obtained from regular forces exerted on the system during the regular evolution of the system [12]. It follows that the velocities are discontinuous at times θ _n when percussions are applied to the system and are constant elsewhere. It 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. 1).

Fig. 1

NSM2-Velocity of the pedestrian i. Time intervals in yellow correspond to those where there is a contact and/or nonzero regular force applied to the i ^th particle and there is a jump discontinuity in the velocity

The equation governing a discontinuity on [t ⁿ, t ⁿ⁺¹] is:

$$ \begin{array}{c} \underline {u}^{n+1}(\theta_{n})-\underline {u}^{n}(\theta_{n})=\underline { \underline {M}}^{-1}\left( -\underline {p}^{int}\left( \frac{\underline {\Updelta }(\underline {u}^{n+1}(\theta_{n}))+\underline {\Updelta }(\underline {u} ^{n}(\theta_{n}))}{2}\right) +\underline {p}^{ext}(\theta _{n})\right). \end{array} $$

(23)

Let $\underline {X}^{n+1}=\frac{\underline {u}^{n+1}(\theta _{n})+\underline {u}^{n}(\theta_{n})}{2}$ so that Eq. (23) becomes:

$$ \begin{array}{c} 2\underline {X}^{n+1}+\underline {\underline {M}}^{-1}\underline {p}^{int}( \underline {\Updelta }(\underline {X}^{n+1}))=2\underline {u}^{n}(\theta_{n})+ \underline {\underline {M}}^{-1}\underline {p}^{ext}(\theta_{n}). \end{array} $$

(24)

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

$$ \fbox{$\begin{array}{c} \underline {X}^{n+1}=\begin{array}{c} \arg \min \\ \underline {Y}^{n+1}\in {\mathbf{R}}^{2N}\end{array}\left[ ^{t}\underline {Y}^{n+1}\underline {\underline {M}}\,\underline {Y}^{n+1}+\Upphi (\underline {q}^{n},\underline {\Updelta }(\underline {Y}^{n+1}))-^{t}(2\underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p}^{ext}(\theta_{n}))\underline {\underline {M}}\, \underline {Y}^{n+1}\right] \\ \end{array}$} $$

(25)

with $\underline {Y}^{n+1}=\frac{\underline {u}^{n+1}(\theta _{n})+\underline {u}^{n}(\theta_{n})}{2}.$

The constitutive law used is the linear law corresponding to the quadratic pseudopotential:

$$ \begin{array}{l} \Upphi ^{d}(\underline {q}^{n},\underline {\Updelta }(\underline {Y} ^{n+1}))=\sum\limits_{1\leq i<j\leq N}\frac{1}{2}K_{T}\left( ^{t}\underline { \Updelta }_{ij}(\underline {Y}^{n+1})^{\perp }\underline {e}_{ji}^{n}\right) ^{2}+\frac{1}{2}K_{N}\left( ^{t}\underline {\Updelta }_{ij}(\underline {Y} ^{n+1})\underline {e}_{ji}^{n}\right) ^{2} \end{array} $$

(26)

where $\underline {e}_{ji}^{n}$ is the normal vector at the contact point, $^{\perp }\underline {e}_{ji}^{n}$ is the tangent vector at the contact point; and K _N and K _T 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$ [16]. Practically, a value of K _N  > 10⁴ kg is well-suited for our analysis. K _T is due to the atomization of viscous friction, and its value is chosen to be zero.

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

$$ -^{t}\underline {\Updelta }_{ij}(\underline {Y}^{n+1})\underline {e} _{ji}^{n}+^{t}\underline {\Updelta }_{ij}(\frac{\underline {u}^{n}(\theta_{n}) }{2})\underline {e}_{ji}^{n}\leq 0. $$

(27)

Thus

$$ \Upphi ^{r}(\underline {q}^{n},\underline {\Updelta }(\underline {Y} ^{n+1}))=\sum\limits_{1\leq i<j\leq N}\mu_{ij}^{n+1}\left[ -^{t}\underline { \Updelta }_{ij}(\underline {Y}^{n+1})\underline {e}_{ji}^{n}+^{t}\underline { \Updelta }_{ij}(\frac{\underline {u}^{n}(\theta_{n})}{2})\underline {e}_{ji}^{n} \right] $$

(28)

where $\mu_{ij}^{n+1}$ is a Lagrange multiplier and has the dimension of a percussion. $\mu_{ij}^{n+1}$ and $\underline {u}^{n+1}$ must satisfy the Kuhn-Tucker conditions:

$$ \left\{ \begin{array}{ll} \mu_{ij}^{n+1} &\geq\, 0 \\ ^{t}\underline {\Updelta }_{ij}(\underline {Y}^{n+1})\underline {e} _{ji}^{n}-^{t}\underline {\Updelta }_{ij}(\frac{\underline {u}^{n}(\theta_{n}) }{2})\underline {e}_{ji}^{n} & \geq\, 0 \\ \mu _{ij}^{n+1}\left[^{t}\underline {\Updelta }_{ij}(\underline {Y}^{n+1}) \underline {e}_{ji}^{n}-^{t}\underline {\Updelta }_{ij}(\frac{\underline {u} ^{n}(\theta_{n})}{2})\underline {e}_{ji}^{n}\right] & =\,0. \end{array} \right. $$

(29)

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

$$\left\{ \begin{array}{ll} \underline {u}^{n+1}(\theta_{n})&=\underline {u}^{n+1}(\theta_{n+1})=2 \underline{X}^{n+1}-\underline {u}^{n}(\theta_{n}) \\ \underline {q}^{n+1}& =\underline {q}^{n}+h\frac{\underline {u}^{n+1}(\theta_{n})+\underline {u}^{n}(\theta_{n})}{2}. \end{array} \right.$$

(30)

The minimization problems (20) and (25) are solved using the classical Uzawa algorithm (see Appendix 1) [8, 12, 13, 16]. The convergence of this scheme has been proved in [13] for the case of Coulomb’s friction law.

To write Eq. (25) with the same formalism as Eqs. (14) and (20), only purely inelastic collisions have to be considered, as in NSM1. We choose then K _N  = K _T  = 0 in Eq. (26), thus Eq. (25) becomes (see Appendix 1):

$$ \fbox{$\begin{array}{c} \underline {u}^{n+1}=\begin{array}{c} \arg \min \\ \underline {v}^{n+1}\in R^{2N}\end{array}\left[ \frac{1}{2}\Vert \underline {v}^{n+1}(\theta_{n})-\underline {V}_{predicted} \Vert_{\underline {\underline {M}}}^{2}-\sum\limits_{1\leq i<j\leq N}\mu _{ij}^{{n+1}\,{t}}\underline {G}_{ij}(\underline {q}^{n})\underline {v}^{n+1}(\theta_{n})\right] \\ \hbox {with}\, \underline {V}_{predicted}= \underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p}^{ext}(\theta_{n}) \\ \end{array}$} $$

(31)

Consequently, with K _N  = K _T  = 0, the expressions of $\underline {u}^{n+1}$ and of $\mu_{ij}^{n+1}$ are related by:

$$ \fbox{$\underline {\underline {M}}\,\underline {u}^{n+1}(\theta_{n})=\underline {\underline {M}}\,\underline {u}^{n}(\theta_{n})+\underline {p}^{ext}(\theta_{n})+\sum\limits_{1\leq i<j\leq N}\mu_{ij}^{n+1}\underline {G}_{ij}(\underline {q}^{n}) $} $$

(32)

when $\mu_{ij}^{n+1}$ and $\underline {u}^{n+1}$ satisfy the Kuhn-Tucker conditions (29).

Equations (22) and (32) have similar expressions; however, the calculation of the Lagrange multiplier $\mu_{ij}^{n+1}$ is different. 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" because it is computed from the previously found position. However, for NSM2, the constraint is on the velocity of the particle and is independent of the time step, so an overlap is possible. The velocity now has more physical meaning, and it can be accepted that the position of the particle after the contact can violate the overlapping condition.

Table 1 shows the analogies between minimization problems in the case of plasticity and when using NSM1 or NSM2 (Eqs. 14, 20 and 31).

Table 1 Analogies between minimization problems in the case of plasticity and when using NSM1 or NSM2

The difference in contact treatment between NSM1 and NSM2 is then illustrated with an example. In the xy-plane, we consider a particle of radius r = 0.22 m, initial position $\underline {q}_{initial}=^{t}(0.5,0.5)$, and initial velocity $\underline {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⁻² s. No exterior force is applied to the particle. The position in the xy-plane and the time evolution of the velocity along the y-axis of the particle after collision with the ground are given for both NSM1 and NSM2 in Fig. 2.

Fig. 2

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

Considering the spatial trajectory of the particle’s center in the xy-plane, previously made remarks about Eqs. (22) and (32) are illustrated in the following figures. Figure 2b (zoomed in on a section of Fig. 2a) shows that except NSM1, a light numerical error on the position of the particle can exist with NSM2. Indeed, it is assumed that the contact, when it exists in [t ⁿ, t ⁿ⁺¹], is applied in the middle θⁿ of the time interval. In the studied case, the contact appears in the time interval [t ³⁹, t ⁴⁰]. If the contact occurs exactly at time θ³⁹, the particle is in perfect contact on one point with the ground at time t ⁴⁰; the ordinate of the particle’s center is equal to the particle’s radius (0.22 m). If the contact takes place in $[t^{39},\theta^{39}[,$ a light numerical overlapping exists. If the contact is in $]\theta^{39},t^{40}],$ the numerical error does not allow the particle to be in contact with the ground at time t ⁴⁰ (Fig. 2b). With NSM1, the particle is in perfect contact with the ground at time t ⁴⁰. Figure 2d (zoomed in on a section of Fig. 2c) shows that when the contact is detected, one intermediate velocity with no physical meaning is found at time t ⁴⁰ with NSM1. Moreover the discontinuity of the velocity at time θ³⁹ with NSM2 can be seen.

3 Extension of granular approaches to the crowd

A pedestrian can be represented as a circular particle by giving it a willingness, i.e. a desire to move in a particular direction with a specific speed at each time.

The first step of the modified approach is to give a desired trajectory to each particle. Several definitions of the desired trajectory of any one pedestrian are possible: either (1) the most comfortable trajectory for him, where he must exert the least effort, e.g. by avoiding the stairs or making the fewest changes in direction, etc.; (2) the shortest path; or (3) the fastest path to move from one place to another [24]. 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 is implemented through a Fast Marching algorithm [29] and is used to obtain the desired direction $\underline {e}_{d,i}$ of an individual i. This direction depends on the environment in which pedestrians walk (obstacles, etc.), the time of day, and also the characteristics of the individual (gender, age, hurried steps or not, etc.). It is defined by: $\underline {e}_{d,i}(t)=\frac{\underline {u}_{d,i}(t)}{\Vert \underline {u}_{d,i}\Vert },$ where $\underline {u}_{d,i}$ is the desired velocity of the ith pedestrian.

The amplitude $\Vert \underline {u}_{d,i}\Vert$ of the desired velocity represents the speed at which the ith pedestrian wants to move, and it can be influenced by his nervousness. This velocity is chosen by following a normal distribution with an average of 1.34 m s⁻¹ and standard deviation of 0.26 m s⁻¹ [23].

In the second step, the desired velocity of each pedestrian i is introduced into the original discrete models to simulate crowd movement. Let $\underline {f}(t)=\underline {f}^{a}(t)$ (DEM or NSM1) or $\underline {f}^{int}(t)=\underline {f}^{a}(t)$ (NSM2), where the so-called acceleration force $\underline {f}^{a}(t)$ [19] allows one to give a desired direction and amplitude of the velocity to each pedestrian. Each component $\underline {f}_{i}^{a}(t)$ of the vector force of dimension $2N:\, ^{t}\underline {f}^{a}=(^{t}\underline{f}_{1}^{a},^{t}\underline {f}_{2}^{a},\ldots,^{t}\underline {f}_{N}^{a}),$ is associated with pedestrian i and can be expressed as:

$$ \underline {f}_{i}^{a}(t)=m_{i}\frac{\Vert \underline {u}_{d,i}\Vert \underline {e}_{d,i}(t)-\underline {u}_{i}(t)}{\tau_{i}} $$

(33)

where $\underline {u}_{i}$ is the actual velocity and $\tau_{i}$ is a relaxation time, which specifies how long the pedestrian will take to recover his desired velocity either after a contact or after he suddenly changes his walking direction. Helbing [20] chose $\tau =0.5\,{\rm s}$ in his numerical simulations. Smaller values of $\tau_{i}$ let the pedestrians walk more aggressively. An example of the trajectories of two identical pedestrians i and j moving in opposite directions after collision is illustrated in Fig. 3 for different values of τ. The influence of the relaxation time parameter τ has been studied in [42]. The chosen value of this parameter is less than or equal to 0.5 s; as such, several contacts may occur because the pedestrians walk aggressively. The pedestrians’ behavior can be enriched by adding other external social forces [18, 38] so as to become more realistic (socio-psychological force, attractive force, group force, etc.). For instance, a socio-psychological force can reflect the tendency of pedestrians to keep a certain distance from other pedestrians. The expression of this repulsive force, applied to the ith pedestrian due to interaction with pedestrian j, is given by:

$$ \underline {f}_{ij}^{soc}(t)=A_{i}\exp \left( \frac{-D_{ij}(\underline {q}(t)) }{B_{i}}\right) \left( \Uplambda _{i}+(1-\Uplambda_{i})\frac{1+\cos \varphi_{ij}}{2}\right) \underline {e}_{ij} $$

(34)

where A _i denotes the interaction strength; B _i is the range of the repulsive interaction; $\Uplambda_{i}<1$ considers the anisotropic character of pedestrian interactions, as the situation in front of a pedestrian has a larger impact on his behavior than what is happening behind; and $\varphi_{ij}$ is the angle between the direction $\underline {e}_{d,i}(t)$ of desired motion and the direction $-\underline {e}_{ij}$ of the pedestrian exerting the repulsive force. $\underline {f}_{ij}^{soc}$ is the force at a distance: the further two pedestrians are from each other, the smaller the amplitude of the force because of the exponential term. The three extended approaches: DEMe, NSM1e and NSM2e will now be explored.

Fig. 3

Trajectories of two identical pedestrians i and j moving in opposite directions for different values of τ. This numerical simulation is done with extended NSM2. After the collision, the external acceleration force allows each pedestrian to gradually switch from the actual velocity after shock to the desired velocity, depending on the values of τ _i and τ _j . In this example, τ _i  = τ _j  = τ

4 Application to numerical simulations

In this section, numerical simulations are presented. The previous approaches have been implemented in a MATLAB environment, and some applications have been processed numerically. Three parameters are computed to compare evacuation results: (1) the evacuation or egress curve, which represents the time evolution of the number of persons having left the studied structure via one or several exits; (2) the average flow, which is obtained from the time derivative of the previous curve; and (3) the escape time from one’s initial position, which is the amount of time that a person needs to evacuate a structure versus his initial position.

The first simulation concerns the evacuation of a room. We compare the numerical results obtained with the three extended approaches with the results from the real evacuation exercise imitating conditions of panic obtained by Helbing et al. [22], using the parameter of average flow through the exit. The influence of the chosen time step for the numerical simulations is also examined.

The second simulation concerns the evacuation of a classroom. Numerical results obtained with the three extended approaches are compared with the real exercises results obtained by Helbing et al. [21]. The parameter being compared in this instance is the escape time from an initial position.

The last case deals with the evacuation of a primary school that has several floors. The egress curve obtained by Klüpfel [31] from his real exercise is compared to the one obtained numerically through the NSM2e method.

For the following simulations, the parameters’ values for each pedestrian (walking speed, radius, mass, response time, and relaxation time) have been chosen to be uniformly distributed within their range from experimental tests [21, 31].

4.1 Evacuation of a square room

We consider a square room with sides 5 m in length that 20 pedestrians want to escape through a door 82 cm wide. The parameters used in the simulations are given in Table 2.

Table 2 Evacuation of a room—parameters used in simulations ($^{\ast }$ uniformly distributed within their range)

As pedestrians’ parameters are randomly generated within a given range (see Table 2), 50 simulations are performed (Fig. 4) for each extended approach, for each time step h = 10⁻² s, h = 10⁻³ s, and h = 10⁻⁴ s, respectively. This example has already been presented in [43] for h = 10⁻² s. The socio-psychological force in Eq. (34) is not added in the simulation, and the initial conditions of the 50 runs are the same for each approach.

Fig. 4

Evacuation of a square room—Egress curves for NSM2e, with h = 10⁻² s. Egress curves of the 50 simulations are the cyan curves. The linear regression (black line) of the 50 simulations (black points) allows us to obtain the average flow through the door

Figure 4 shows the linear regression of the 50 simulations for NSM2e with h = 10⁻² s. The slope allows us to estimate the average flow Q (pedestrian/min) through the door. The values of Q for the simulations obtained with the three extended approaches at different time steps, as well as those obtained with a real evacuation exercise [22], are collected in Table 3.

Table 3 Evacuation of a square room—average flow Q (pedestrian/min) through a door 82 cm wide

It shows that the influence of the chosen time step on Q is negligible as long as the stability of the time integration scheme is ensured. Moreover, Q obtained with NSM2e is very similar to Q obtained with the real evacuation exercise imitating conditions of panic. However, pedestrians escape faster with NSM1e than with the two other extended approaches. These results are probably due to the way contact is treated: purely inelastic in NSM1 and elastic in DEM and NSM2. Taking into account elastic collisions seems to be necessary. The difference between Q obtained with DEMe and Q obtained with NSM2e could be due to the overlapping effect that is necessary for treating contacts in DEMe.

4.2 Evacuation of a classroom

The real evacuation exercise of 30 students from a classroom is presented in [21]. The classroom’s width is 5.85 m and its length 6.75 m. There are 30 desks in six rows and five columns. The longitudinal and the transverse distances between desks are 0.9 and 1.35 m respectively. The only exit is in the back of the classroom, and its width is 0.5 m. The evacuation process is recorded by two video cameras. As soon as a cameraman shouts a word of command, all students stand up from their chairs and hurry toward the exit. Parameters used in simulations are summarized in Table 4. As some parameters are uniformly distributed within their range, 50 simulations are performed. Figure 5 shows snapshots of the numerical simulations at different times that were obtained with NSM1e and NSM2e. The snapshots obtained with DEMe are similar to those obtained with NSM2e. For the three extended approaches, we observe the formation of an arch in front of the exit. For DEMe and NSM2e, pedestrians evacuate the classrooms (e.g. first line of Fig. 5) without problem, while for NSM1e, pedestrians are often blocked (e.g. second line of Fig. 5). NSM1e is not efficient for this situation. Our study is then limited to the two other models. Figure 6 indicates the average escape times from all desks (i.e. initial positions). The average escape times for each student that were obtained from the real experiment are at the top, from the 50 simulations of DEMe are in the middle, and from the 50 simulations of NSM2e are at the bottom.

Table 4 Evacuation of a classroom—parameters used in simulations ($^{\ast }$ uniformly distributed within their range)

Fig. 5

Evacuation of a classroom—snapshot of two numerical simulations at different times. The first row is obtained with NSM2e while the second row is obtained with NSM1e. Walls are black, desks are blue, the door is magenta, and pedestrians are red circles

Fig. 6

Evacuation of a classroom—escape times from all initial positions. The three numerical values in each circle indicate the average escape times obtained from the experiment (at the top) and the simulations (in the middle for DEMe and at the bottom for NSM2e)

Similarities can be noted for the average escape times obtained from the experiment and from the simulations. First, the escape time increases with the initial distance from the exit for each column of desks. Second, even though the escape time increases approximately with the initial distance from the exit, the students in the first and second columns need a disproportionate amount of time to escape. The explanation given by Helbing from the experiment is that students naturally use the passageway between the columns of desks that are closer to the door (i.e. the passageway to their left with regard to their direction of motion). This means that students in the first and second columns use the same passageway, thereby increasing the density and escape times. The explanation that we can give from the simulations is that since the density of students around the narrow door becomes so important during an emergency evacuation, students who are in front of the door can leave the classroom more easily than students who come by one side.

4.3 Evacuation of a primary school

NSM2e is finally applied to the evacuation exercise of a primary school, which was presented in [31]. This example shows that it is possible to study a 3D problem using a 2D approach. The building has 3 floors and 6 classrooms with about 130 pupils (between the ages of 6 and 10). The initial number of persons in each room is given in [31]. When the alarm is triggered, pupils start evacuating, and each class of pupils follows its teacher. Videotapes are taken during the real exercise and the experimental results are based on them. To simulate this exercise, we propose the set of parameters summarized in Table 5 that were obtained from [20, 31] to represent a standard population. One hundred numerical simulations are performed with NSM2e because some parameters are uniformly distributed within their range. NSM2e contains the socio-psychological force introduced in Sect. 3 An example of the snapshots of one numerical simulation at different times is shown in Fig. 7. Figure 8 gives the egress curve obtained from the real exercise as well as the mean of the egress curves obtained by numerical simulations. Using a set of parameters derived from the capabilities of a standard population, the simulation results are similar to those obtained with a class of pupils that follows its teacher during the real evacuation exercise. It can be noted that in the egress curve obtained from the real exercise, the flow suddenly decreases at t ≃ 38 s and then resumes its original slope after t ≃ 48 s. This phenomenon, potentially a pedestrian traffic jam, is not reproduced by our model. One possible explanation is that pedestrians were blocked somewhere in the building, possibly in the stairs where two classes could meet, since they were children under the responsibility of their teacher.

Table 5 Evacuation of a primary school—parameters used in simulations ($^{\ast}$ uniformly distributed within their range)

Fig. 7

Evacuation of a primary school—snapshots of one numerical simulation at different times. Walls are black, obstacles are green, stairs are yellow, doors are magenta, and pedestrians are red circles

Fig. 8

Evacuation of a primary school—Egress curves. Comparison between real exercise and numerical simulations results: the 100 numerical simulations are the cyan curves, the mean of these simulations is the bold black curve, and the real exercise curve is the bold red one

5 Conclusion

This paper presents three existing discrete approaches (one smooth and two non-smooth), which were originally proposed to simulate the granular assembly’s movement, that we adapted to represent pedestrians with varying willingnesses to move. For both non-smooth approaches, by making some assumptions (purely inelastic collisions, etc.), the contact problem can be written with the same formalism as that used in plasticity.

Social forces as well as a desired direction/velocity are introduced in order to simulate the behavior of real pedestrians. The three extended approaches are numerically implemented and applied to a real case of an evacuation of a room. The obtained results are compared to the experimental ones. The effect of the chosen time step on the results is studied and for both approaches, it is discovered to be negligible as long as the stability of the time integration scheme is ensured. The non-smooth approach adapted from the works of Frémond proved to be capable of reproducing this real evacuation exercise in a satisfactory way. Other simulations performed with this approach are compared with real evacuation exercises and confirm this conclusion as well.

The proposed modeling strategy would be useful in improving the design of public spaces for accidental situations (e.g. fires) by increasing the safety and comfort of the users.

Appendices

Appendix 1: Elements of convex analysis

We recall here some concepts and results of convex analysis.

1.1 Convex functions

1.1.1 Convex set

Let X be a vector space on R. A set $C\subset X$ is called convex if for all x and y of C and all θ of ]0, 1[, 

$$ \theta x+(1-\theta )y\in C. $$

(35)

1.1.2 Convex function

A function f defined on a set C of X with values in $\overline{R}=R\cup \{+\infty \}$ is called a convex function if for all x and y of C and all θ of ]0, 1[, 

$$ f(\theta x+(1-\theta )y)\leq \theta f(x)+(1-\theta )f(y) $$

(36)

where addition and multiplication in R are extended by

$$ (+\infty )+(+\infty ) =+\infty \\ $$

(37)

$$ \lambda (+\infty ) =(+\infty )\quad \hbox {if}\quad \lambda >0. $$

(38)

We call the set where it is defined the domain of f:

$$ dom(f)=\{x\in C/f(x)\neq +\infty \}. $$

(39)

1.2 Subdifferentiability

1.2.1 Vector space in duality

Two vector spaces V and $V^{\ast }$ are in duality if there exists a bilinear form $\{\cdot ,\cdot \}$ defined on $V\times V^{\ast }$ such that:

$$ \begin{array}{llll} \forall x\in V,& x\neq 0, \exists y^{\ast }\in V^{\ast }&\hbox {such that}& $\{$x,y^{\ast }$\}$\neq 0 \\ \forall y^{\ast }\in V^{\ast },& y^{\ast }\neq 0,\exists x\in V &\hbox{such that}& $\{$x,y^{\ast }$\}$\neq 0. \end{array} $$

(40)

1.2.2 Subgradient and subdifferential of a convex function

Let V and $V^{\ast}$ two vector spaces placed in duality by a bilinear form $\{\cdot,\cdot\}.$ A convex function f of V in $\overline{R}$ is subdifferentiable at point $x_{0}\in V$ if there is $x^{\ast}\in V^{\ast}$ such that for all $x\in V$

$$ \{x-x_{0},x^{\ast}\}+f(x_{0})\leq f(x) $$

(41)

$x^{\ast }$ is a subgradient. The set of subgradients is the subdifferential $\partial f(x_{0})$ (Fig. 9), and it is convex and closed on $V^{\ast }.$

Fig. 9

The convex function f has no derivative at point A. It has generalized derivatives at this point, which are the slopes of the lines that are passing through A and are under the curve representing the function. These slopes are subgradients that form the subdifferential

1.3 Dissipation pseudopotential

1.3.1 Lower semi-continuity

A convex function defined on a Banach space X is called lower semi-continuous if for all real r

$$ \{x\in X/f(x)\leq r\}\quad \hbox {is closed.} $$

(42)

1.3.2 Dissipation pseudopotential

This concept has been defined by Moreau. A dissipation pseudopotential is a positive convex function that is lower semi-continuous and zero at the origin.

Appendis 2: Optimization with convex constraint [8, 12, 16]

2.1 Kuhn-Tucker conditions

Let $f:\Upomega\subset E=R^{n}\longrightarrow R,$ differentiable in $x^{\ast}\in K$ with

$\Upomega$ open and convex,

$K=\left\{x\in\Upomega,\quad \varphi_i(x)\leq0,\,i=1,\ldots,m\right\}\neq{\O}$

$\varphi_i:\Upomega\longrightarrow R$ convex, differentiable in $x^{\ast}.$

• 1. If $x^{\ast}$ is a solution of

  $$ (P)\left\{ \begin{array}{ll} f(x^{\ast})&=\inf_{x\in K}f(x) \\ &x^{\ast}\in K \end{array} \right. $$

  (43)

  and if the constraints are qualified, i.e. $\varphi_i$ are affine or $\exists\omega\in K$ such that $\varphi_i(\omega)<0$ for the non affine $\varphi_i,$ then Lagrange multipliers λ _i  ≥ 0 exist and verify the Kuhn-Tucker conditions

  $$ \left\{ \begin{aligned} \nabla f(x^{ * } ) + \sum\limits_{1}^{m} {\lambda _{i} } \nabla \varphi _{i} (x^{ * } ) & = 0 \\ \lambda _{i} \varphi _{i} (x^{ * } ) & = 0,\quad i = 1, \ldots ,m. \\ \end{aligned} \right.$$

  (44)

• 2. Reciprocally, if $f:\Upomega\longrightarrow R$ is convex and differentiable, $x^{\ast}\in K$ and Lagrange multipliers λ _i  ≥ 0 exist and verify the Kuhn-Tucker conditions, then $x^{\ast}$ is a solution of (P).

2.2 Interpretation of the Kuhn-Tucker conditions

As K is convex and $x^{\ast}$ is a minimum of f, it is already known that

$$ (-\nabla f\left(x^{\ast}\right),x-x^{\ast})\leq0 \quad \forall x\in K, $$

(45)

which means that $-\nabla f\left(x^{\ast}\right)$ realizes an angle $\geq\frac{\pi}{2}$ with the interior directions $x-x^{\ast}.$

Kuhn-Tucker conditions add that

$$ -\nabla f\left(x^{\ast}\right)=\sum\lambda_i\nabla\varphi_i(x^{\ast}), \quad \lambda_i\geq0, $$

(46)

i.e. $-\nabla f\left(x^{\ast}\right)$ is in the cone

$$ {\sum\alpha_i\nabla\varphi_i(x^{\ast}),\quad \alpha_i\geq0}. $$

(47)

Moreover, the Kuhn-Tucker conditions express that $x^{\ast}$ is a solution of the minimization problem without constraint of the functional

$$ x\in\Upomega\longrightarrow f(x)+\sum\limits_1^m\lambda_i(x^{\ast}) \varphi_i(x) $$

(48)

whose solution corresponds to the annulation of the derivative.

2.3 Saddle point

Let E and M be two normed spaces and $L:E\times M\longrightarrow R.$ $(x^{\ast},\lambda)\in E\times M$ is a saddle point if $x^{\ast}$ is a minimum for $x\longrightarrow L(x,\lambda)$ and if λ is a maximum for $\mu\longrightarrow L(x^{\ast},\mu).$ In such point,

$$ \inf_{x\in E}\sup_{\mu\in M}L(x,\mu)=\sup_{\mu\in M}L(x^{\ast},\mu)=L(x^{\ast},\lambda)=\inf_{x\in E}L(x,\lambda)=\sup_{\mu\in M}\inf_{x\in E}L(x,\mu). $$

(49)

2.4 Lagrangian

The Lagrangian associated with the problem (P) is the function of $E\times R_{+}^{m}\longrightarrow R$ defined by

$$ L(x,\mu)=f(x)+\sum\limits_1^m\mu_i\varphi_i(x). $$

(50)

2.5 Saddle point of the Lagrangian and solution of the problem (P)

If $(x^{\ast},\lambda)\in E\times R_{+}^{m}$ is a saddle point of the Lagrangian of the problem (P), then $x^{\ast}\in K$ and $x^{\ast}$ is a solution of (P).

If the functions f and $\varphi_i$ are convex and differentiable in $x^{\ast}\in K,$ the constraints are qualified, and $x^{\ast}$ is a solution of (P), then at least one $\lambda\in R_{+}^{m}$ exists such that $(x^{\ast},\lambda)\in E\times R_{+}^{m}$ is a saddle point of L.

2.6 Dual problem of problem (P)

• 1. $\varphi_i$ are assumed to be continuous, and for all $\mu\in R_{+}^{m}$ the problem

  $$ (P_{\mu})\left\{ \begin{array}{c} L(x_{\mu},\mu)=\inf_{x\in E}L(x,\mu) \\ x_{\mu}\in E \end{array} \right. $$

  (51)

  has a solution and only one x _μ that continuously depends on μ.

  Then, if λ is a solution of the problem

  $$ (Q)\left\{ \begin{array}{c} G(\lambda)=\sup_{\mu\geq0}G(\mu) \\ \lambda\in R_{+}^{m} \end{array} \right. $$

  (52)

  with

  $$ G(\mu)=\inf_{x\in E}L(x,\mu)=L(x_{\mu},\mu), \\ $$

  (53)

  the solution x _λ of (P _λ) is a solution of (P).

  (Q) is named the dual problem of the primal problem (P) and μ is named the dual variable of the primal variable x.

• 2. We assume that (P) has at least one solution $x^{\ast},$ the functions f and $\varphi_i$ are convex and differentiable in $x^{\ast},$ and the constraints are qualified.

  Then the problem (Q) has at least one solution.

2.7 Uzawa method

The problem (P), whose constraints are

$$ K=\left\{x\in E,\quad \varphi_i(x)\leq0\right\}, $$

(54)

is resolved with the help of the dual problem, whose constraints ${\mu\in R_{+}^{m}}$ are simpler.

2.7.1 Approach

Knowing $\lambda_0\in R_{+}^{m}$ ordinary, a double sequence $(\lambda_k,x_k)$ is calculated.

2.7.2 Calculation of λ _k+1

Knowing $\lambda_{k}$ and $x_{k-1}, \lambda_{k+1}$ is sought as an approximation of the solution of (Q) by evaluating $\lambda_{k}+\rho\nabla G\left(\lambda_k\right)$ and taking the projection of this value on the domain ${\mu\geq0}$ (projected gradient method with fixed step $\rho$).

2.7.3 Calculation of $\nabla G\left(\lambda_k\right)$

Under the assumptions of Paragraph 2.6, it can be proved that G is differentiable and that

$$ \nabla G_{\mu}=(\varphi_i(x_\mu))_i. $$

(55)

To calculate $\nabla G\left(\lambda_k\right), x_{\lambda_k}$ has to be calculated first. Let $x_k=x_{\lambda_k}.$ This point is obtained with an optimization method without constraint as a solution of

$$ f(x_k)+\sum\lambda_{ki}\varphi_i(x_k)=\inf_{x\in E}(f(x)+\sum\lambda_{ki}\varphi_i(x)). $$

(56)

Under some assumptions, the sequence $((\lambda_k,x_k))_k$ converges to the saddle point of L, $(x^{\ast},\lambda)$ with $x^{\ast}$ being the solution of (P).

2.7.4 Sufficient convergence’s condition of the Uzawa method

$f:E\longrightarrow R$ is assumed to be elliptic with α being its ellipticity coefficient. K non empty is assumed to be defined by affine inequality constraints

$$ K=\left\{x\in E,\quad Cx\leq d\right\}, $$

(57)

and then if

$$ 0<\rho<\frac{2\alpha}{\|C\|^{2}}, $$

(58)

the sequence (x _k ) of the Uzawa method converges to the unique solution of (P).

Moreover, if the rank of C is m, the sequence $(\lambda_k)$ converges to the unique solution of the dual problem (Q) as well.

Appendix 3: Rewriting of the Lagrangian associated to the constrained minimization problem of NSM2

The constrained minimization problem of NSM2 is Eq. (25):

$$ \begin{array}{c} \underline {X}^{n+1}= \begin{array}{c} \arg\min \\ \underline {Y}^{n+1}\in R^{2N} \end{array} \left[^t\underline {Y}^{n+1}\underline {\underline {M}}\quad \underline {Y} ^{n+1}+\Upphi(\underline {q}^{n},\underline {\Updelta}(\underline {Y}^{n+1}))- ^t(2 \underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p} ^{ext}(\theta_{n}))\underline {\underline {M}}\quad \underline {Y}^{n+1}\right]. \\ \end{array} $$

Let L _NSM2 be the Lagrangian associated to the constrained minimization problems Eq. (25):

$$ \begin{array}{c} L_{NSM2}=^t\underline {Y}^{n+1}\underline {\underline {M}}\quad \underline {Y} ^{n+1}+\Upphi(\underline {q}^{n},\underline {\Updelta}(\underline {Y}^{n+1}))- ^t(2 \underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p} ^{ext}(\theta_{n}))\underline {\underline {M}}\quad\underline {Y}^{n+1} \end{array} $$

(59)

$$ \begin{aligned} &^t\underline {\underline {M}}=\underline {\underline {M}}\\ &\underline {\underline {M}}=cte\\ &^t\underline {u}^{n}(\theta_{n})\underline {\underline {M}}\quad \underline {u}^{n+1}(\theta_{n})= ^t\underline {u}^{n+1}(\theta_{n})\underline {\underline {M}}\quad \underline {u}^{n}(\theta_{n})\\ &\underline {Y}^{n+1}=\frac{\underline {u}^{n+1}(\theta_{n})+\underline {u}^{n}(\theta_{n})}{2}\\ &\|\underline {X}\|^{2}_{\underline {\underline {M}}}= ^t\underline {X}\quad \underline {\underline {M}}\quad \underline {X}. \end{aligned} $$

We assume that the rotation of the particle is neglected.

The constitutive law used is the linear law corresponding to the quadratic pseudopotential:

$$ \begin{array}{c} \Upphi^{d}(\underline {q}^{n},\underline {\Updelta}(\underline {Y} ^{n+1}))=\sum\limits_{1\leq i< j\leq N}\frac{1}{2}K_{T}\left(\left( ^t \underline {Y}^{n+1}_{i}- ^t\underline {Y}^{n+1}_{j}\right) ^{\perp}\underline { e}_{ji}^{n}\right)^{2}+\frac{1}{2}K_{N}\left(\left( ^t\underline {Y} ^{n+1}_{i}- ^t\underline {Y}^{n+1}_{j}\right)\underline {e}_{ji}^{n}\right)^{2} \end{array} $$

(60)

where $\underline {e}_{ji}^{n}$ is the normal to the contact; $^{\perp}\underline {e}_{ji}^{n}$ is the tangent to the contact; and K _N and K _T are the coefficients of dissipation for the normal and Tangential components of percussions. K _N reflects the inelastic nature of collisions between particles and K _T results of atomization of viscous friction.

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

$$ -^t\underline {\Updelta}_{ij}(\underline {Y}^{n+1})\underline {e}_{ji}^{n}+ ^t \underline {\Updelta}_{ij}\left(\frac{\underline {u}^{n}(\theta_{n})}{2}\right) \underline {e}_{ji}^{n}\leq0. $$

(61)

Thus

$$ \Upphi^{r}(\underline {q}^{n},\underline {\Updelta}(\underline {Y} ^{n+1}))=\sum\limits_{1\leq i<j\leq N}\mu_{ij}^{n+1}\left[-\left( ^t \underline {Y}^{n+1}_{i}- ^t\underline {Y}^{n+1}_{j}\right)\underline {e}_{ji}^{n} +\left(\frac{ ^t\underline {u}_{i}^{n}(\theta_{n})}{2}-\frac{ ^t \underline {u}_{j}^{n}(\theta_{n})}{2}\right)\underline {e}_{ji}^{n}\right] $$

(62)

where $\mu_{ij}^{n+1}$ is a Lagrange multiplier and has the dimension of a percussion.

We know that

$$ \begin{aligned} \|\underline {Y}^{n+1}-\frac{1}{2}\left(2\underline {u}^{n}(\theta_{n})+ \underline {\underline {M}}^{-1}\underline {p}^{ext}(\theta_{n})\right)\|^{2}_{ \underline {\underline {M}}} &= ^{t}\left[\underline {Y}^{n+1}-\frac{1}{2} \left(2\underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1} \underline {p}^{ext}(\theta_{n})\right)\right]\underline {\underline {M}}\left[ \underline {Y}^{n+1}-\frac{1}{2}\left(2\underline {u}^{n}(\theta_{n})\right.\right.\\ &\quad\left.\left. + \underline {\underline {M}}^{-1}\underline {p}^{ext}(\theta_{n})\right)\right] \\ & = ^t\underline {Y}^{n+1}\underline {\underline {M}}\quad \underline {Y}^{n+1}- ^t\left(2\underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1} \underline {p}^{ext}(\theta_{n})\right)\underline {\underline {M}}\underline {Y} ^{n+1}\ldots \\ &\quad +\frac{1}{4} ^t\left(2\underline {u}^{n}(\theta_{n})+\underline {\underline {M }}^{-1}\underline {p}^{ext}(\theta_{n})\right)\underline {\underline {M}}\left(2 \underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p} ^{ext}(\theta_{n})\right). \end{aligned} $$

(63)

Then Eq. (59) becomes

$$ \begin{aligned} L_{NSM2} &=\|\underline {Y}^{n+1}-\frac{1}{2}\left(2\underline {u} ^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p} ^{ext}(\theta_{n})\right)\|^{2}_{\underline {\underline {M}}}+\Upphi^{d}( \underline {q}^{n},\underline {\Updelta}(\underline {Y}^{n+1}))+\Upphi^{r}( \underline {q}^{n},\underline {\Updelta}(\underline {Y}^{n+1}))\ldots \\ & \quad-\frac{1}{4} ^t\left(2\underline {u}^{n}(\theta_{n})+\underline {\underline {M }}^{-1}\underline {p}^{ext}(\theta_{n})\right)\underline {\underline {M}}\left(2 \underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p} ^{ext}(\theta_{n})\right). \end{aligned} $$

(64)

Finding the minimum of L _NSM2 is equivalent to minimizing

$$ \begin{aligned} L^{^{\prime }}_{NSM2}&=\|\underline {Y}^{n+1}-\frac{1}{2}\left(2\underline {u }^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p} ^{ext}(\theta_{n})\right)\|^{2}_{\underline {\underline {M}}}+\Upphi^{d}( \underline {q}^{n},\underline {\Updelta}(\underline {Y}^{n+1}))\ldots \\ & \quad+\sum\limits_{1\leq i<j\leq N}\mu_{ij}^{n+1}\left[-\left( ^t\underline {Y} ^{n+1}_{i}- ^t\underline {Y}^{n+1}_{j}\right)\underline {e}_{ji}^{n} +\left( \frac{ ^t\underline {u}_{i}^{n}(\theta_{n})}{2}-\frac{ ^t\underline {u} _{j}^{n}(\theta_{n})}{2}\right)\underline {e}_{ji}^{n}\right] \end{aligned} $$

(65)

because $-\frac{1}{4} ^t\left(2\underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p}^{ext}(\theta_{n})\right)\underline {\underline {M}}\left(2\underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p}^{ext}(\theta_{n})\right)$ is known.

We can note

$$ \begin{array}{ll} \|\underline {Y}^{n+1}-\frac{1}{2}\left(2\underline {u}^{n}(\theta_{n})+ \underline {\underline {M}}^{-1}\underline {p}^{ext}(\theta_{n})\right)\|^{2}_{ \underline {\underline {M}}} & = \frac{1}{4}\|\underline {u}^{n+1}(\theta_{n})-\left(\underline {u}^{n}(\theta_{n})+ \underline {\underline {M}}^{-1}\underline {p}^{ext}(\theta_{n})\right)\|^{2}_{ \underline {\underline {M}}} \end{array} $$

(66)

and according to the definition of $^{t}\underline {G}_{ij}(\underline {q})$ (Eq. 6)

$$ -\left( ^t\underline {Y}^{n+1}_{i}- ^t\underline {Y}^{n+1}_{j}\right) \underline {e}_{ji}^{n} +\left(\frac{ ^t\underline {u}_{i}^{n}(\theta_{n})}{2}- \frac{ ^t\underline {u}_{j}^{n}(\theta_{n})}{2}\right)\underline {e}_{ji}^{n} =- ^{t}\underline {G}_{ij}(\underline {q}^{n})\frac{\underline {u} ^{n+1}(\theta_{n})}{2}. $$

(67)

As in NSM1, only purely inelastic collisions are considered, so we simplify Eq. (65) by examining only non-elastic impact: K _T  = K _N  = 0 (purely inelastic collisions), and according to Eqs. (66) and (67), Eq. (25) becomes:

$$ \fbox{$\begin{array}{c} \underline {u}^{n+1}(\theta _{n})=\begin{array}{c} \arg \min \\ \underline {v}^{n+1}\in R^{2N}\end{array}\left[ \frac{1}{2}\Vert \underline {v}^{n+1}(\theta _{n})-\left( \underline {u}^{n}(\theta_{n})+\underline {\underline {M}}^{-1}\underline {p}^{ext}(\theta_{n})\right) \Vert_{\underline {\underline {M}}}^{2}-\sum\limits_{1\leq i<j\leq N}\mu _{ij}^{{n+1} {t}}\underline {G}_{ij}(\underline {q}^{n})\underline {v}^{n+1}(\theta_{n})\right]. \\ \end{array}$} $$

(68)