GPEvac: GNN-Based PPO for Adaptive Evacuation Routing During Shooting Events

• Between 2020 and 2024, America recorded 3,106 mass shootings, 1,295 more than in the previous five years, and research on decisions before containment remains limited.Source: §1 · p. 1
• The Run–Hide–Fight protocol lacks adaptability across environments, while decentralized, uninformed choices can lead to suboptimal routes, congestion, and encounters with the threat.Source: §1 · p. 1
• GPEvac combines computer-vision tracking and crowd-density measurement with a global view to calculate adaptive routes that avoid dynamic threats and congestion bottlenecks.Source: §1 · p. 1
• A GNN with edge-centric message passing and a virtual global node generates context-aware embeddings that feed PPO and a permutation-invariant scorer across graph topologies.Source: §1 · pp. 1–2

2 Related Works

• Dijkstra’s algorithm and A* handle static environments, but shooter movement and crowd congestion make them computationally infeasible for real-time support in large-scale scenarios.Source: §2 · p. 2

2.1 Deep Reinforcement Learning (DRL)

• Existing evacuation DRL methods optimize local obstacle avoidance or represent spatial structure, but may lack graph abstraction or dynamic message passing for real-time state changes.PPO is an actor-critic approach that uses a clipped surrogate objective to enhance training stability.Source: §2.1 · p. 2

2.2 Graph Neural Networks (GNNs)

• GNNs encode topology through message passing and produce permutation-invariant embeddings, while a virtual global node propagates long-range dependencies beyond one-hop layers without relying on deeper, oversmoothing-prone stacks.The literature also compares aggregation and routing designs including GINE, PNA, ResGated, GAT, and Graph Transformers.Source: §2.2 · p. 2

2.3 GNN-Based Deep Reinforcement Learning

• Decentralized graph-based multi-agent methods can limit coordination, while centralized variants face instability, non-stationarity, and sample-complexity concerns; GPEvac instead formulates multi-node routing as a single-agent problem.Source: §2.3 · p. 2
• Related GNN-based evacuation systems are described as limited by iterative scalability, single-path optimization, lack of a permutation-invariant actor, or assumptions of predictable hazards.GreyGNN-MARL, DRAGON, and Wu and Mu are discussed as examples of these limitations.Source: §2.3 · pp. 2–3

3 Methodology

• GPEvac structures tracking data as a dynamic graph, processes it into node embeddings, and uses PPO to formulate safe routing decisions for each room.The pipeline uses a hand-crafted GNN to represent the state for the PPO agent.Source: §3 · p. 3

3.1 Simulation Environment

• The simulation covers acyclic buildings with structural bottlenecks and cyclic buildings with multiple escape routes, while shooter movement is modeled as a random walk.Occupant movement is represented as discretized flow between connected nodes, with transit updated over five time steps.Source: §3.1 · p. 3
• The reward combines penalties for threat proximity and elapsed time with rewards for individual and complete evacuations.Threat penalties decay with distance; time penalties scale with the number of occupants remaining.Source: §3.1 · pp. 3–4

3.2 The Graph Neural Network

• An edge-first GNN updates edge embeddings before node embeddings, then uses a learnable virtual global node to share information about distant threats and exits.The model processes node and edge features, including occupancy, threat presence, traversal time, and occupancy gradients.Source: §3.1 · p. 3, §3.2 · p. 4

Critic Network

• The centralized critic combines mean node embeddings with the final global embedding to estimate a value for the whole graph state.This graph-level estimate evaluates the holistic environment rather than localized agent observations.Source: Critic Network · p. 4

Actor Network

• Each node selects a neighboring node through a shared policy that scores source-edge-target transitions, then masks inactive nodes and invalid or blocked actions.The edge scores are arranged by source node and neighbor index, avoiding dependence on an arbitrary fixed node ordering.Source: Actor Network · pp. 4–5

4.1 Baseline Methods

• Because ASTERS and C-CASTERS are calibrated to specific simulations, direct comparison would require changing their mechanics and assumptions and would be scientifically invalid.The authors instead implement two intelligent baselines for a rigorous evaluation.Source: §4.1 · p. 5

Greedy Policy

• The Greedy Policy uses Dijkstra’s algorithm to direct evacuees along shortest paths to safety, without accounting for the threat.Its rationale is that faster exits should reduce cumulative vulnerability.Source: Greedy Policy · p. 5

Rule-Based Policy

• The Rule-Based policy routes toward an exit when a sufficiently safe path exists; otherwise, it chooses a neighboring node farther from the shooter.Its safety threshold λ is tuned separately for each layout using 100 simulation instances.Source: Rule-Based Policy · p. 5

4.2 GPEvac

• Across all configurations, the best GPEvac policy significantly outperforms the Rule-Based baseline in exposure time, threat penalty, and return.A one-sided Wilcoxon signed-rank test reports p = 3.65 × 10−2 for exposure time, p = 6.71 × 10−5 for threat penalty, and p = 4.92 × 10−6 for returns.Source: §4.2 · p. 6, Table 1 · p. 6

4.3 Real-Time Inference

• For 55- and 70-node schools, median inference takes 14.73 ms; graphs exceeding 1,000 nodes are processed in a fraction of a second.Initialization scales super-linearly but is an offline step, whereas single-step inference scales sub-linearly.Source: §4.3 · p. 6, Table 2 · p. 6

4.4 Ablation Studies

• Removing edge updates raises threat penalty from 4.43 to 5.46 (p = 0.0186), while removing the virtual global node causes further performance declines.The ablation table reports the lowest threat contact with edge updates, a virtual global node, and PNA.Source: §4.4 · pp. 6–7, Table 3 · p. 7
• GATv2, ResGated, and Graph Transformer variants perform less consistently in the cyclic layout, while GINE is highly unstable.These alternatives achieve low threat penalties in the acyclic layout, but their performance deteriorates in the more topologically complex cyclic layout.Source: §4.4 · p. 7
• Replacing the GNN with a two-layer MLP increases threat contact and training variance; PNA's multiple aggregators capture varied statistics such as threat risk and exit distance.The authors attribute PNA's superior performance to its use of multiple aggregators.Source: §4.4 · p. 7

5 Conclusion

• GPEvac outperforms intelligent baselines across diverse building topologies using a dynamic-graph GNN and permutation-invariant edge-scoring actor.The framework uses edge-centric message passing and a virtual global node to encode long-range spatial relationships.Source: §5 · p. 7
• 14.73 ms on local CPUs enables GPEvac to compute global routing updates for potential integration with real-time surveillance networks.The authors also describe digital screens and dynamic exit signs as ways to steer occupants away from threats.Source: §5 · p. 7
• Urban planners could compare evacuation exposure times across layouts as a quantitative metric for building-design survivability.The authors also envision transferring the architecture to intelligent transportation and resource allocation.Source: §5 · p. 7

5.1 Limitations and Future Work

• A large-scale architectural dataset is needed for rigorous training and evaluation of zero-shot generalization across diverse building topologies.Future work could also incorporate capacity constraints, intelligent adversarial strategies, and stress-induced human behavior.Source: §5.1 · p. 7
• Chaotic real-world emergencies can introduce localization errors, motivating probabilistic node features to account for observational uncertainty.The authors say deployment also requires rigorous evaluation in high-fidelity simulation platforms to assess operational safety and reliability.Source: §5.1 · p. 7

A Introduction and Related Works

• The Department of Homeland Security’s Run-Hide-Fight protocol is described as the standard framework for active-shooter response.Figure 5 is captioned as an illustration of the protocol.Source: A Introduction and Related Works · p. 11, Figure 5 · p. 11
• Under the protocol, individuals decide whether to evacuate, stay in place, or confront the attacker based on their immediate surroundings.The response choices correspond to running, hiding, or fighting.Source: A Introduction and Related Works · p. 11
• The protocol’s decentralized decisions are illustrated in Figure 5.The caption identifies the figure as the Run-Hide-Fight Protocol.Source: A Introduction and Related Works · p. 11, Figure 5 · p. 11

B.1 Dataset

• Two school layouts adapted from C-CASTERS are represented as graphs, with rooms as nodes, passageways as edges, and empirically derived traversal-time edge weights.The traversal times come from Unreal Engine simulations.Source: §B.1 · p. 11

B.2 Node and Edge Features

• GPEvac uses 47 node features and 20 edge features, including static layout information and dynamic features tied to shooter and evacuee locations.The feature set is deliberately redundant and is based on layout topology, shooter location, and evacuee distribution.Source: §B.2 · pp. 11–12

B.3 Temporal Complexity

• Initialization scales super-linearly with node count, while single-step inference scales sub-linearly; preprocessing all-pairs shortest paths shifts computation offline.The policy forward pass has O(|V| + |E|) asymptotic complexity under a sparse building topology with bounded average degree.Source: §B.3 · p. 12

Synthetic Graph Generation

• Inference-time benchmarks use 20 procedurally generated graphs per target node count, designed to mimic building floor plans with capped node degree.The generation procedure uses a hallway spine, cross-links, distributed exits, and room stubs.Source: Synthetic Graph Generation · p. 12

B.4 Simulation Environment

• Evacuees move incrementally across edges with capacity distributed over T timesteps, and cannot be reassigned mid-transit.Edge weights determine traversal capacity; bottleneck congestion increases delays and threat exposure, providing an implicit learning signal for avoidance.Source: §B.4 · pp. 12–13

B.5 Normalization

• Feature-specific normalization scales topology and distance measures, clips many features at 2, and normalizes localized evacuee counts by node capacity and total population.The predefined node capacity used for one normalization is 50.Source: §B.5 · p. 13

B.6 Virtual Global Node

• The learnable virtual global node connects to all real nodes, enabling efficient propagation of long-range dependencies in large-diameter graphs.Figure 6 depicts the global node and its edges.Source: §B.6 · p. 13, Figure 6 · p. 13

B.7 Masking

• Structural masks ignore padded nodes and edges, while dynamic action masks exclude invalid routing choices, including exits, empty nodes, and nodes in transit.The virtual global node connects only to real nodes, and critic pooling masks padded nodes.Source: §B.7 · p. 13

B.8 Additional Implementation Details

• The learning curve plateaued early, with the network converging to its optimal routing policy within the first 8 hours of an approximately 20-hour training run.Training used 18,000,000 environmental timesteps on one NVIDIA Tesla V100 GPU.Source: §B.8 · p. 13

C.1 Video Rollouts

• Supplementary rollout videos show GPEvac, Rule-Based, and Greedy policies under the exact same environment initialization seed for each layout.Source: §C.1 · p. 13

C.2 GPEvac

• Across both architectural layouts, GPEvac consistently outperforms both baselines in minimizing contact with the threat.Figure 7 averages cumulative exposure time over 32 test environments per layout.Source: §C.2 · p. 13, Figure 7 · p. 13

C.3 Reward Function

• At Rthreat/Rexit = 0.25, the authors identify an equilibrium between speed and safety; prioritizing evacuation risks routing evacuees into danger, while excess threat penalty delays evacuation.Source: §C.3 · pp. 13–14
• At Rthreat/Rexit = 0.25, GPEvac has the lowest normalized threat penalty and outperforms the near-optimal Rule-Based baseline.The reported value is the median over 5 independent training runs on the validation set, normalized to GPEvac’s default weighting.Source: Table 4 · p. 14

C.4 Rule-Based Baseline

• The Rule-Based policy’s highest average return occurred at λ = 4 for the Acyclic school and λ = 9 for the Cyclic school.Each threshold was evaluated in 100 random simulations per layout using identical seeds.Source: §C.4 · p. 14

• Because GPEvac minimizes global threat contact, it risks policies that sacrifice smaller groups; future work should audit fairness and explicitly protect vulnerable occupants.The authors name elderly people, children, and individuals with disabilities as groups needing consideration.Source: D Broader Impacts and Limitations · p. 14
• Stress-induced behavior, herd mentality, and panic are difficult to simulate, so future research should examine how stressed occupants perceive and respond to dynamic directions.The authors specify directions delivered via digital screens and smart exit signs.Source: D Broader Impacts and Limitations · p. 14
• GPEvac’s black-box nature makes specific routing decisions difficult to explain, posing hurdles for safety regulation, trust, and legal certification.Source: D Broader Impacts and Limitations · p. 14