A discrete contact model for crowd motion

• The model targets crowd motion in highly dense configurations.Source: R´esum´e · p. 1
• Each person’s spontaneous velocity represents the motion they would choose without other people.Source: R´esum´e · p. 1
• Actual velocity is the projection of spontaneous velocity onto velocities satisfying the non-overlap constraint.Source: R´esum´e · p. 1
• The paper adapts sweeping-process results for uniformly prox-regular sets to establish well-posedness.Source: R´esum´e · p. 1
• It proposes a prediction-correction numerical scheme and presents numerical illustrations.Source: R´esum´e · p. 1

Introduction

• Prior crowd models include cellular automata, network and queuing models, social-force models, and macroscopic fluid, gas-kinetic, and flow-conservation approaches.Source: Introduction · pp. 1–2
• Lane formation and arches upstream of exits are standard self-organization benchmarks recovered by cellular-automata and social-force models.Source: Introduction · p. 2
• Emergency motion can involve direct conflict between people and congestion, unlike standard pedestrian-flow conditions; the authors aim to estimate interaction forces and local casualty risk.Source: Introduction · p. 2
• The model projects each person’s spontaneous velocity onto velocities admissible under non-overlap, allowing existing crowd-motion prediction models to supply spontaneous motion.Source: Introduction · p. 2
• The well-posedness argument draws on results for sweeping processes by uniformly prox-regular sets.Source: Introduction · p. 2
• The paper presents the model and well-posedness in Section 2, the numerical scheme in Section 3, and illustrations in Section 4.Source: Introduction · p. 2

1 Modelling

• Individuals are represented by equal-radius disks with centers q_i, and their configuration must satisfy the non-overlap constraint.Source: §1 · p. 2
• The signed distance D_ij(q)=|q_i−q_j|−2r measures the gap between disks, while spontaneous velocity U_i may depend on positions.Source: §1 · pp. 2–3
• At contact, feasible velocities satisfy G_ij(q)·v≥0, with G_ij defined as the gradient of the signed distance.Source: §1 · p. 3
• The actual velocity is the feasible velocity closest to U in least-squares sense, obtained by projection onto the closed convex cone C_q.Source: §1 · p. 3
• The feasible-velocity set does not vary continuously with q: it is all of R2N without contact and a half-space with a single contact.Source: §1 · p. 3

2.1 Reformulation

• With no contacts, the actual velocity equals the spontaneous velocity; with contacts, the configuration evolves within the feasible set through a differential inclusion involving its outward normal cone.The cone is defined as the polar of the feasible-velocity cone.Source: §2.1 · p. 4
• For Lipschitz, bounded U and any feasible initial configuration, the inclusion has one and only one absolutely continuous solution on every finite interval [0, T].The argument relies on proving that Q is uniformly prox-regular and that its normal cone agrees with the proximal normal cone.Source: §2.1 · p. 6

2.2 Prox-regularity of Q

• The feasible set’s proximal normal cone equals the sum of the individual contact-set normal cones, and uniform prox-regularity is derived using an inverse triangle inequality based on contact-vector angles.The inequality requires nonnegative coefficients; the authors note that its prox-regularity constant is not claimed to be optimal.Source: §2.2 · pp. 8, 10
• F_k is interpreted as a pressure force exerted on person k by neighbors, while −F_k is interpreted as a reaction force.Source: §2.2 · p. 11
• The number of neighbors of individual k, excluding l, is bounded by 5.Source: §2.2 · p. 12
• The construction selects successive neighbors and terminates within N − 2 steps, producing distinct auxiliary individuals for the force estimates.The analogous construction for F_l ensures the selected individuals are distinct; the proof takes ǫ = 1/12N.Source: §2.2 · pp. 12–13

3.1 Time-discretization scheme

• The time-discretization scheme uses a first-order expansion of the velocity constraints to approximate the next configuration.With time step h, the approximation imposes Dij(qn) + h Gij(qn) · v ≥ 0 for every pair i < j.Source: §3.1 · pp. 13–14
• The scheme forms an inner convex approximation of feasible configurations and projects the predicted position onto it.The prediction is qn + hU(qn), and the correction is qn+1 = P_{Q̃(qn)}(qn + hU(qn)).Source: §3.1 · p. 14
• The position update is also a semi-implicit discretization, and its convergence proof is deferred to future work.The approximation N(Q̃(qn), qn+1) stands in for N(Q, qn).Source: §3.1 · p. 14

3.2 Numerical solutions

• The discrete actual velocity is computed by projecting spontaneous velocity onto the approximated feasible-velocity set, using an Uzawa solution method.The minimization is reformulated in saddle-point form.Source: §3.2 · pp. 14–15
• The Uzawa algorithm can be shown to converge for fixed ρ > 0 when 0 < ρ < 2/∥B∥²; more precisely, the velocity sequence (vₖ) converges to u.The multiplier sequence tends to some limit.Source: §3.2 · p. 15
• A 14-person configuration with 29 contacts has a non-injective matrix and non-unique Kuhn-Tucker multipliers.Figure 8 illustrates this degeneracy.Source: §3.2 · p. 15, Figure 8 · p. 15
• Jammed configurations required more Uzawa iterations, as expected when local prox-regularity is low.The authors relate local prox-regularity to the condition number of the algorithm's matrix.Source: §3.2 · p. 16

An example of spontaneous velocity

• The example directs pedestrians along the shortest obstacle-avoiding path to the nearest exit, with U0(x) = −s ∇D(x) and geodesic distance D computed by Fast Marching.Fast Marching sets exit-node distances to zero and assigns obstacles large values so shortest paths avoid them.Source: An example of spontaneous velocity · p. 16
• In nonconvex rooms, this strategy produces a discontinuous velocity field, excluding Theorem 2.10 and making future configurations discontinuous with respect to initial data.The authors say the affected places, particularly upstream of obstacles, empty after a few moments.Source: An example of spontaneous velocity · p. 17
• Contacts with obstacles must be handled alongside person-to-person contacts because people intending to avoid an obstacle can be pushed onto it by those behind them.The complex-geometry illustration uses a floor evacuation through exit stairs.Source: An example of spontaneous velocity · p. 17

Simple evacuation

• For 1000 randomly placed people, straight constant-speed paths concentrate density near the exit, producing upstream congestion and arches whose contact multipliers indicate constraint pressure.The multipliers should not be treated as direct measures of discomfort, though high values are expected where people may be crushed.Source: Simple evacuation · p. 17

Complex geometry

• 109s versus 48s without congestion was the final evacuation time in the complex-floor scenario, where a transient jam slowed exit flow before clearing.The jam forms in the room on the left and eventually disappears.Source: Complex geometry · pp. 17–18