Evacuation Planning Research (Public Artifact)

This repository is a public artifact of my graduate research at the University of Idaho on evolving evacuation strategies for urban networks. The core is a C++ simulator paired with a small domain language (SLang) for defining scenarios.

The research proposes optimizing static routing distributions (node → edge probabilities) with an Evolution Strategy to maximize safety while accounting for congestion and variability in traveler behavior. The simulator is a macroscopic agent model using a BPR-style travel-time link function. A detailed write‑up appears in the paper/ directory (see paper/Paper.tex).

Funding and rights: This work was funded by the U.S. National Science Foundation (NSF) and performed at the University of Idaho (UOI). Copyright and ownership remain with NSF and UOI; this repository is a public showing of the research and code for educational and archival purposes.

Modernization note: The goal of this project is to make the original work easy to build, run, and explore on modern systems with minimal changes to the code or results. We are introducing small build and tooling updates (e.g., Bazel, hermetic artifacts, visualization) while preserving the behavior and structure of the original simulator and scenarios.

Directory Map

• simulation/ – C++ simulation engine, SLang lexer/parser, Bazel targets.
• slang/ – LaTeX source of the SLang language reference.
• paper/ – Draft of the research paper, figures, and resources.

Architecture in Brief

• City as a directed graph (nodes, edges). Link travel time uses freeflow * (1 + b * (c/cmax)^beta).
• Agents are grouped and evaluated in a priority queue by arrival time.
• Chromosome encodes per-node distributions over outgoing edges (probabilities sum to 1 per node).
• Evolution Strategy (ES+/ES,) optimizes safety (sum over agents) subject to traffic dynamics; parameters set via parameters in SLang.
• SLang defines city, edges, nodes, agents, parameters, and run commands.

Build (Bazel)

This repo builds with Bazel (Bzlmod via MODULE.bazel). To keep builds simple and reproducible, the lexer/parser C sources live in simulation/generated/ and are consumed directly by Bazel. You can regenerate them with Flex/Bison if you wish, but it is not required to build.

Build the simulator:

bazel build //simulation:evac

Optional AddressSanitizer for debugging:

bazel build --config=asan //simulation:evac

Run

Use the run wrapper to ensure the outputs/ directory exists and execute the simulator with a scenario file:

bazel run //simulation:evac_run -- simulation/slang/highway.slang
# or the 4×4 grid scenario
bazel run //simulation:evac_run -- simulation/slang/minigrid.slang

The wrapper sets the working directory to the workspace root and creates outputs/ automatically. If you prefer to run the binary directly, create the directory first and pass the scenario path:

mkdir -p outputs
bazel run //simulation:evac -- simulation/slang/highway.slang

Results are written to outputs/<CityName>Final.txt (drawable format with edges, nodes, probabilities, and agent routes). Historical results and plotting scripts remain under simulation/results.

Test (CI/Local)

A small end‑to‑end integration test runs the simulator on a 4×4 grid and asserts the drawable is produced:

bazel test //simulation:evac_minigrid_it

Visualization (GIF)

For hermetic, Bazel‑native artifacts (preferred for CI) you can build the drawable and an animated GIF for the provided scenarios. Artifacts are written to bazel-bin/simulation/.

• Minigrid (4×4 grid):

# Requires Pillow: pip3 install --user Pillow
bazel build //simulation:drawable_minigrid
bazel build //simulation:gif_minigrid
# Artifacts:
#   bazel-bin/simulation/minigridFinal.txt
#   bazel-bin/simulation/minigrid_anim.gif

• Highway:

# Requires Pillow: pip3 install --user Pillow
bazel build //simulation:drawable_highway
bazel build //simulation:gif_highway
# Artifacts:
#   bazel-bin/simulation/highwayFinal.txt
#   bazel-bin/simulation/highway_anim.gif

Notes:

• The renderer (simulation/tools/viz_gif.py) is a small homebrewed script that draws the network and agents and overlays a progress bar across the bottom to highlight start/end and progress through the simulation. It supports trails, edge width by probability, and scaling by group size.
• The simulator honors EVAC_OUTPUT_DIR (set by the Bazel rules) when producing drawables in hermetic builds.

Historical Scenarios (GIF builds)

You can also build GIFs for the historical comparison/validation scenarios in this repository. These are hermetic builds that first produce a drawable and then render a GIF using the bundled Python visualizer.

# Requires Pillow: pip3 install --user Pillow
# Topology change adaptation
bazel build //simulation:gif_topology

# Safety function adaptation
bazel build //simulation:gif_safety

# Agent distribution variation
bazel build //simulation:gif_agents

# Capacity sensitivity (also see MRCCP topology)
bazel build //simulation:gif_capacity
bazel build //simulation:gif_mrccp

# Note: Non‑Boise GIFs are not committed to the repo to keep size small.
# Build them locally as needed using the targets above.

# Build everything at once
bazel build //simulation:all_gifs

Research Results

Other Experiments (Static Figures)

Static figures from the original results are included for quick reference. You can generate matching GIFs locally (see build targets above).

Topology changes

Safety function changes

Agent distribution changes

Capacity sensitivity and MRCCP

Comparison (Bazzan 2014)

Real‑World (Boise)

The following animations were generated from historical drawable outputs of the Boise network experiments used in the research. They visualize agent movement under distributions evolved by the ES optimizer for different population and capacity settings. These drawables do not include per-agent timestamps; the animation interpolates uniformly between route nodes but still illustrates the optimized routing qualitatively.

• Population series (60k agents variants):

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

• Capacity and safe-to-danger variants:

10% pop + 40% capacity

10% pop + 40% capacity (plain)

10% pop + 40% capacity (safe-to-danger init)

10% pop (safe-to-danger init)

Notes:

• “safe-to-danger” initialization seeds probabilities by moving agents from the safest nodes outward before optimization; this can accelerate convergence.
• Reduced capacity (e.g., 40%) models degraded infrastructure; evolved probabilities adapt by redirecting flow away from bottlenecks while guiding agents toward high-safety sinks.

Supporting Figures

Validation (Grid/Maze)

Basic grid/maze validations to confirm designated routes are discovered under freeflow/capacity perturbations.

Performance (Boise Runtime)

Runtime scaling for Boise population experiments.

Contributing & Modernization

The modernization effort focuses on build/test/visualization and documentation without altering the original algorithms or data. If you’re exploring the code:

• Prefer hermetic Bazel targets for reproducible outputs.
• Use --config=asan for debugging.
• Keep changes small and scoped; aim to preserve behavior.

For code style, build, and test guidelines see AGENTS.md.