Conflict Detection and Resolution Algorithm in Crowd Evacuation

Conflict Detection and Resolution Algorithm in Crowd Evacuation

Problem Description
During crowd evacuation, physical collisions or congestion may occur among individuals due to overlapping paths, speed differences, or directional conflicts. The conflict detection and resolution algorithm aims to identify potential conflicts in real-time and avoid collisions by dynamically adjusting individual paths or speeds, thereby improving evacuation efficiency and safety. This problem involves computational geometry, multi-agent systems, and real-time decision optimization.

Solution Process

1. Conflict Types and Definitions

  • Type Classification:
    • Static Conflict: Collisions between individuals and obstacles or walls.
    • Dynamic Conflict: Head-on collisions, cross-path collisions, and rear-end collisions among individuals.
  • Mathematical Representation:
    Each individual can be considered as a circular agent with radius \(r_i\), position \(\mathbf{p}_i(t)\), and velocity \(\mathbf{v}_i(t)\). The conflict condition is:

\[ \|\mathbf{p}_i(t) - \mathbf{p}_j(t)\| < r_i + r_j \]

If this condition is satisfied within a future time step \(\Delta t\), it is considered a potential conflict.

2. Conflict Detection Methods

  • Geometry-Based Detection:

    • Velocity Obstacles (VO) Method:
      Maps other individuals and obstacles into velocity space, avoiding velocity directions that would lead to collisions.
      1. Calculate relative velocity \(\mathbf{v}_{ij} = \mathbf{v}_i - \mathbf{v}_j\).
      2. Construct the collision cone (CC): A cone with vertex at \(\mathbf{p}_j\) and opening angle \(\arcsin(\frac{r_i+r_j}{\|\mathbf{p}_i-\mathbf{p}_j\|})\).
      3. If \(\mathbf{v}_{ij}\) points inside the collision cone, a conflict exists.
    • Recursive Collision Detection:
      Performs binary search on continuous time intervals to check if path segments intersect (e.g., using ray-circle intersection tests).

  • Search-Based Detection:

    • Divides space into grids, detecting only individuals in adjacent grids (reducing computational load).
    • Uses quadtrees (2D) or octrees (3D) to accelerate spatial queries.

3. Conflict Resolution Strategies

  • Rule Priority Strategy:

    1. Speed Adjustment: Reduce speed or pause briefly to let the conflicting party pass first.
    2. Direction Fine-Tuning: Slight deviation from the original path (e.g., moving to the right side).
    3. Path Replanning: Locally switch to an alternative path (requires global map support).

  • Optimization Models:

    • Velocity Selection-Based:
      Finds a velocity vector in velocity space that satisfies maximum speed constraints and avoids collision cones:

\[ \min_{\mathbf{v}_i'} \|\mathbf{v}_i' - \mathbf{v}_i^{\text{pref}}\| \quad \text{s.t.} \quad \mathbf{v}_i' \notin \bigcup_j \text{VO}_{ij} \]

where $ \mathbf{v}_i^{\text{pref}} $ is the individual's preferred velocity (e.g., toward the exit).
  • Distributed Negotiation:
    Multiple conflicting individuals decide the yielding order through voting or game theory (e.g., Nash equilibrium).

4. Algorithm Implementation Workflow

  1. Real-Time Detection Loop:
    • Updates individual positions and velocities each frame.
    • Uses spatial partitioning techniques to quickly filter neighboring individuals.
    • Performs collision cone detection for each pair of neighboring individuals.
  2. Conflict Sorting:
    • Processes conflicts in ascending order of collision time, prioritizing urgent conflicts.
  3. Dynamic Adjustment:
    • Updates individual velocities if the conflict can be resolved (e.g., a safe velocity exists).
    • Triggers group-level strategies (e.g., flow control) if the conflict is unavoidable (e.g., in narrow passages).
  4. Posterior Verification:
    • Checks whether adjusted trajectories cause new conflicts (recursively detects until no conflicts remain).

5. Challenges and Optimization Directions

  • Computational Efficiency: Large-scale crowds require approximate algorithms (e.g., RVO2, ORCA).
  • Behavior Realism: Incorporates social force models or psychological rules (e.g., yielding to the elderly).
  • Dynamic Environments: Adapts to scenarios with sudden obstacles or closed exits.

Through the above steps, the conflict detection and resolution algorithm can significantly enhance the reliability and efficiency of evacuation simulations, providing theoretical support for practical emergency management.