PaperlayerView exact revision on arXiv

Source-linked AI summary

Handling congestion in crowd motion modeling

B. Maury, A. Roudneff-Chupin, F. Santambrogio, J. Venel

arXiv:1101.4102v1math.NAcs.NA

TL;DR

Crowd-motion models often soften congestion, while this paper addresses actual contact and forbidden overlap. It projects desired motion onto feasible velocities in both microscopic and macroscopic models, extending a sweeping-process framework to the macroscopic setting. The paper also highlights a fundamental difference: the macroscopic model is not expected to follow from microscopic homogenization.

  • Problem

    The paper addresses how to model crowd motion when people make actual contact and overlapping is forbidden, rather than treating congestion only through softer responses.

    Source: §1 · p. 2

  • Method

    It projects spontaneous velocities onto feasible non-overlapping motions and extends the sweeping-process framework to a macroscopic density model using Wasserstein distance.

    Source: §1 · p. 2

  • Results

    The sweeping-process framework extends to the macroscopic model without assuming gradient forcing, while the microscopic and macroscopic models remain fundamentally different.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Because maximal density is not properly defined microscopically, the macroscopic model cannot be expected to arise through homogenization.

    Source: §1 · p. 3

    The macroscopic model is not derived from the microscopic model by a rigorous homogenization process.

    Source: §5 · p. 18

Abstract

from arXiv · show

We address here the issue of congestion in the modeling of crowd motion, in the non-smooth framework: contacts between people are not anticipated and avoided, they actually occur, and they are explicitly taken into account in the model. We limit our approach to very basic principles in terms of behavior, to focus on the particular problems raised by the non-smooth character of the models. We consider that individuals tend to move according to a desired, or spontanous, velocity. We account for congestion by assuming that the evolution realizes at each time an instantaneous balance between individual tendencies and global constraints (overlapping is forbidden): the actual velocity is defined as the closest to the desired velocity among all admissible ones, in a least square sense. We develop those principles in the microscopic and macroscopic settings, and we present how the framework of Wasserstein distance between measures allows to recover the sweeping process nature of the problem on the macroscopic level, which makes it possible to obtain existence results in spite of the non-smooth character of the evolution process. Micro and macro approaches are compared, and we investigate the similarities together with deep differences of those two levels of description.

1. Introduction.

The introduction distinguishes soft congestion from hard contact constraints and sets out a basic projection-based model of crowd motion. It develops the model at microscopic and macroscopic scales, while emphasizing that their formal similarities do not make the macroscopic model a homogenized version of the microscopic one.

1. Introduction.

  • The paper targets hard congestion, where actual contact occurs and motion must respect non-overlap, rather than models that respond to proximity through soft congestion.Prior macroscopic approaches often use repulsive terms or modify desired paths near crowded areas.Source: §1 · pp. 1–2
  • Individuals are assigned a spontaneous velocity, and their actual velocity is its closest feasible counterpart under the non-overlapping constraint.The introduction deliberately leaves social and strategic behavior aside to focus on hard-congestion issues.Source: §1 · pp. 2–3
  • The microscopic model fits a sweeping-process framework, while the macroscopic model uses Wasserstein distance to extend that framework without requiring gradient forcing.The macroscopic formulation addresses the difficulty that its projected velocity field has uncontrolled regularity.Source: §1 · p. 2
  • Despite shared modeling principles, maximal density is not properly defined microscopically, so the macroscopic model cannot be expected to arise through homogenization.Source: §1 · p. 3

2. Hard congestion models.

The models represent congestion by projecting desired motion onto feasible velocities: non-overlap for individual disks and a density cap for the population. Their respective constraints also yield pressure-based formulations.

2.1. Microscopic setting.

  • The microscopic setting models individuals as rigid disks with a shared radius and constrains their center-to-center distances to prevent overlap.The desired velocity depends on location and is assumed identical in form for all individuals.Source: §2.1 · p. 3
  • At contact, feasible velocities must not reduce the gap between disks; the actual velocity is the Euclidean projection of the spontaneous velocity onto that feasible set.Obstacles are omitted for simpler notation but can be included in the feasible-configuration set.Source: §2.1 · p. 3
  • A saddle-point formulation introduces pressure as the interaction force between contacting individuals and exposes a Darcy-like structure.The formulation expresses constraints on velocity through the active contacts.Source: §2.1 · pp. 3–4

2.2. Macroscopic setting.

  • The macroscopic setting represents the crowd by a density in a closed room, with feasible densities capped at the saturation value of one.The density is advected by the actual velocity.Source: §2.2 · p. 4
  • Macroscopic feasible velocities have non-negative divergence on the saturated zone, and their projection formulation also admits a pressure-based saddle-point form.The pressure vanishes where density is below saturation and satisfies a complementarity condition.Source: §2.2 · pp. 4–5

3. Rigorous formalisms, well-posedness issues.

The section develops rigorous formulations for the microscopic and macroscopic crowd models, addressing well-posedness and the challenges raised by nonconvex admissible sets and boundary exits. For the macroscopic model, it considers both a Wasserstein catching-up approach and a gradient-flow alternative with weaker regularity requirements and a proximal algorithm.

3.1. Microscopic model : generalized sweeping processes.

  • In the microscopic model, uniform prox-regularity of K depends on angles between active-constraint gradients; its coefficient degenerates as disk size shrinks and depends on N.Intersections of individually prox-regular sets need not retain a uniform prox-regularity constant, as the angle between their normals can drive the constant toward zero.Source: §3.1 · pp. 6–7
  • For Lipschitz, bounded desired velocity and any initial configuration in K, the microscopic model has a unique absolutely continuous solution.The differential inclusion is equivalent to the velocity projection formulation because the normal and feasible-velocity cones are mutually polar.Source: §3.1 · p. 7

3.2. Macroscopic model.

  • The macroscopic catching-up method uses Wasserstein distance because the L2 velocity projection is nonsmooth and does not control regularity, while Eulerian density differences lose the Lagrangian displacement structure.The algorithm transports density by the desired field, then projects onto the constrained set in the Wasserstein sense.Source: §3.2 · pp. 8–9
  • For macroscopic prediction, the desired field is assumed to keep mass in the room and be regular enough to preserve absolute continuity, with an exception allowed at an evacuation exit.The exit case is handled by a modified admissible set that permits mass on the exit boundary and removes its density constraint.Source: §3.2 · pp. 9, 12
  • In dimensions d ≥ 2, the probability space is not nonpositively curved, so squared Wasserstein distance can be concave; generalized geodesics nevertheless establish projection well-posedness without a distance restriction.The admissible set is geodesically convex, but ordinary geodesic convexity does not suffice for the uniqueness argument in this setting.Source: §3.2 · p. 10
  • The macroscopic projection is uniquely attained for every probability measure and is continuous, despite the admissible set lacking a uniformly positive prox-regularity constant.Generalized geodesics give the needed convexity for the projection problem.Source: §3.2 · p. 10
  • For C1 desired velocity and initial density in K, the macroscopic catching-up approximations converge as the time step vanishes to a solution of the transport equation with projected velocity.The limit satisfies ∂tρ + ∇·(ρu) = 0 and u = PCρU.Source: §3.2 · p. 11
  • At an allowed exit Γ, particles crossing the boundary are represented as mass on Γ, where the model no longer tracks what happens to them.This is a modeling simplification; the particles are not assumed to be physically blocked at the exit.Source: §3.2 · p. 12
  • With exits, KΓ is not geodesically convex, so Wasserstein geodesics may leave it and projection uniqueness is unknown; the algorithm accepts any distance minimizer.The projection can involve measures supported beyond Ω, which are projected onto measures over Ω satisfying an extra density constraint; the same idea could remove the no-exit assumption that id + τU maps Ω into Ω.Source: §3.2 · p. 12

3.3. Gradient flow setting.

  • When spontaneous velocity is the gradient of dissatisfaction, the microscopic dynamics has a gradient-flow form with ϕ = Ψ + IK and ∂ϕ = ∇Ψ + NK(q), using prox-regularity.Here Ψ is total dissatisfaction, for example the sum of distances to the exit.Source: §3.3 · p. 12
  • In the macroscopic case, assuming U = −∇D yields a continuous global dissatisfaction and a Wasserstein gradient flow in which ρ is advected by u.The formulation uses ϕ = Ψ + IK and a strong Fréchet subdifferential defined through transport maps; NK is its special case for ϕ = IK.Source: §3.3 · pp. 12–13
  • The gradient-flow formulation handles vector fields U less regular than the general case, which naturally requires Lipschitz continuity of U, or D ∈ C1,1.The paper points to gradient-flow theory in finite-dimensional spaces, Hilbert spaces, and metric spaces, particularly P(Ω).Source: §3.3 · p. 13
  • With a gradient structure, the prediction-and-correction catching-up algorithm can be replaced by a single-step proximal algorithm, also known as minimizing movements.The minimizing-movements method was first applied to P(Ω) with the Wasserstein metric by Jordan, Kinderlehrer, and Otto.Source: §3.3 · p. 13
  • The macroscopic gradient-flow treatment covers both no-exit constraints ρ ∈ K and exit constraints ρ ∈ KΓ, with the exit case being more difficult.Source: §3.3 · p. 13

4. Numerical solution.

The numerical schemes approximate congestion through projection, using local convex approximations microscopically and transport followed by Wasserstein projection macroscopically. The microscopic approximations converge under stated assumptions, while the macroscopic stochastic projection lacks a rigorous error estimate and the two descriptions are not linked by rigorous homogenization.

4.1. Microscopic model.

  • Microscopically, each catching-up step replaces the feasible set with a local convex approximation for projection; Uzawa computation can require more iterations in jammed configurations.The convex replacement is computationally convenient, and its projection can be written as a saddle-point problem.Source: §4.1 · pp. 13–14
  • For Lipschitz, bounded U, the microscopic piecewise-linear approximations converge uniformly on every finite time interval to the solution in Theorem 3.2.The result applies as the time step τ tends to zero.Source: §4.1 · p. 15

4.2. Macroscopic model.

  • Macroscopically, the scheme first transports cell mass by the desired velocity and redistributes it across mesh cells, then projects onto feasible densities in Wasserstein distance.The transport step moves cell centers and distributes each cell’s mass among the mesh cells it intersects.Source: §4.2 · pp. 15–16
  • The macroscopic stochastic projection redistributes excess mass from each saturated cell by random walks depositing it in non-saturated cells until the resulting density is admissible.Each walk carries excess mass m = (ρ − 1)|C| and deposits as much as possible when it encounters a non-saturated cell.Source: §4.2 · p. 17
  • The stochastic projection has no rigorous error estimate, and the alternative Wasserstein minimizing-movement scheme is too slow for efficient two-dimensional problems.The latter approach would require solving minimization problems involving W2.Source: §4.2 · p. 17
  • The macroscopic model is not derived from the microscopic model by rigorous homogenization, despite their shared least-squares projection principle.The paper identifies differences between the two descriptions, including that maximal density is not properly defined microscopically.Source: §5 · p. 18

5. From micro to macro.

Microscopic congestion depends on local packing and contact structure, while the macroscopic model uses a maximal-density constraint; these differences complicate micro-to-macro convergence, especially in dimensions two and higher.

Maximal density

  • Mean density upstream of an exit typically ranges from 0.85 to 0.87, yet submaximal density does not imply unconstrained flow in the microscopic model.The maximal packing value is attained only in a particular configuration; jammed arrangements can occur at lower densities.Source: §5 · p. 18

Constraints on the velocity

  • Microscopic feasible velocities depend on local structure: a triangular lattice imposes expansion constraints along three directions, unlike a constraint based only on density.The lattice directions are e0, eπ/3, and e2π/3, with e · ∇u · e ≥ 0 in each direction.Source: §5 · p. 19

Jams

  • The macroscopic model cannot reproduce blocked jams: when the desired field points toward an exit, its pressure correction keeps evacuation moving until the room is empty.In a saturated zone, the maximum principle makes the pressure nonnegative and pushes people outward at the door.Source: §5 · p. 20
  • The microscopic model can form blocked arches at exits, where contact pressures may act against the motion of people nearest the door.This contrasts with the macroscopic evacuation mechanism described for saturated zones.Source: §5 · p. 21

Mathematical issues (convergence or non-convergence)

  • In dimensions two and higher, jammed microscopic configurations need not match macroscopic saturation: a jammed Cartesian lattice can converge to a density below the triangular-lattice reference.The limiting density then does not activate the macroscopic constraint, so its evolution can differ from the blocked microscopic configuration.Source: §5 · pp. 21–22
  • Even when both initial states saturate their constraints, microscopic contact-network restrictions differ from the macroscopic positive-divergence condition, so the models are not generally interchangeable.The paper notes that accounting for microscopic structure would be necessary to identify the corresponding macroscopic admissible velocities.Source: §5 · p. 22
  • For dimensions two and higher, convergence between the models remains a complex open issue that the paper leaves outside its scope.The authors identify Γ-convergence of dissatisfaction functionals and associated flows as ongoing work.Source: §5 · p. 22

6. Possible extensions.

The extensions add behavioral strategies, multiple populations, and a Nash-style velocity rule to the basic congestion model. They also expose trade-offs: strategies can alter contact patterns, while the Nash rule may admit many instantaneous velocities.

6.1. Strategies.

  • Individuals can respond to visible slower neighbors by decelerating or changing direction to pass or go around them while retaining desired speed.The strategy uses a neighborhood defined by proximity and a forward angle of view.Source: §6.1 · pp. 22–23
  • Simulations report rarefaction waves and typically no contacts when pedestrians prefer deceleration, whereas avoidance activates the congestion constraints.These outcomes are reported for simulations with the strategies in.Source: §6.1 · p. 23
  • In the macroscopic model, desired speed can decrease with local density; if people still push at saturation, congestion constraints may remain active.The density-dependent desired velocity keeps its initial direction, and the approach can use downstream density information.Source: §6.1 · p. 23

6.2. Multi-component populations.

  • Different individual strategies require no change to the microscopic mathematical structure, while a two-population macroscopic model uses a shared correction velocity to preserve the total-density constraint.The shared correction is chosen to minimize its L2 norm.Source: §6.2 · pp. 23–24

6.3. Nash equilibrium approach.

  • The Nash approach changes the mathematical nature of the evolution, and the earlier-section solutions are only particular solutions among infinitely many possibilities.Further development is needed for this formulation.Source: §6.3 · pp. 24–25
  • The Nash-style rule may have infinitely many equilibria: for two contacting disks, any diagonal velocity pair (α, α), with α ∈ [0, 1], is an equilibrium.The prior L2 projection instead assigns both individuals velocity 1/2 in this example.Source: §6.3 · p. 24

7. Numerical experiments.

The numerical comparison begins by matching an initial microscopic configuration to a macroscopic density, a choice the authors identify as difficult.

7. Numerical experiments.

  • For uniform densities, the comparison estimates the microscopic configuration’s mean density and normalizes it by the maximal disk density encountered during microscopic evolution.Figure 15 illustrates the calculation.Source: Micro-macro comparison · p. 25

Micro-macro comparison.

The two models form similar saturated zones, but their exit behavior differs, with faster evacuation in the macroscopic model. Their pressure fields share a spatial pattern despite differing numerical interpretations.

Micro-macro comparison.

  • Evacuation is faster in the macroscopic model, although saturated zones form similarly in the two settings.The comparison is made at equivalent time steps; Figure 17 presents the evacuation comparison.Source: Micro-macro comparison · p. 25, Figure 17 · p. 26
  • Pressure is maximal in the middle of the saturated zone and decreases at its entrance and exit in both models.Microscopic pressure is a Lagrange multiplier; macroscopic pressure is estimated from mass emitted by each cell during stochastic projection.Source: Pressure field · p. 26

Pressure field.

The microscopic setting describes situations where people leave through narrow exits.

Pressure field.

Realistic geometries.

The examples distinguish evacuation settings suited to microscopic and macroscopic descriptions, including a large-building evacuation and a stadium evacuation.

Realistic geometries.

  • Figure 19 shows evacuation of the first floor of the Mathematics Department building in Orsay.Source: Realistic geometries · p. 27
  • The macroscopic setting best fits evacuations where many people leave a large domain.Source: Realistic geometries · p. 27
  • The Stade de France example shows a macroscopic evacuation with narrow bench passages and results corresponding to real evacuation configurations.Source: Realistic geometries · p. 27
Loading 1101.4102v1…