CityMind — An Urban Intelligence System

CityMind is a simulation of a mid-sized city, modeled as a 20×20 grid graph, that helps city authorities make smarter, faster decisions. It was built as a semester-long Artificial Intelligence group project, and brings together five classic AI techniques — constraint satisfaction, evolutionary optimization, local search, informed search, and machine learning — into one coherent, interactive system built on a single shared city graph.

Built for the AI course at NUCES, Islamabad. A design document and a full implementation report are included in docs/.

What it does

The city starts as an empty grid and CityMind has to:

1. Plan the layout — place hospitals, schools, residential zones, industrial zones, power plants, and ambulance depots while respecting zoning rules (e.g. industrial zones can't sit next to schools or hospitals).
2. Build the road network — connect every location at minimum cost, while guaranteeing two independent routes between the primary hospital and the ambulance depot, so a single road failure never cuts them off from each other.
3. Place ambulances — position 3 ambulances to minimize the worst-case response distance to any residential area.
4. Route emergencies dynamically — guide a medical team to a sequence of trapped civilians, replanning instantly and optimally whenever a road floods mid-journey.
5. Predict crime risk — cluster neighborhoods by their properties, train a classifier on a synthetic crime dataset, and feed the predicted risk levels back into the graph as a travel-cost penalty that affects routing and ambulance placement.

All five pieces read and write the same CityGraph object, so a flooded road, a new crime label, or a layout change is instantly visible everywhere — there's no syncing logic anywhere in the codebase.

A Tkinter interface drives a 20-step simulation with flooding events, live re-routing, and overlay toggles (road network / ambulance coverage / crime heatmap), plus a running event log of every decision the system makes.

AI techniques used

Challenge	Technique	Why it fits
1 — City Layout	Constraint Satisfaction (Backtracking + AC-3 + MRV + forward checking)	Placement under hard rules is inherently a CSP; backtracking with AC-3 guarantees completeness, and on failure the conflict set tells you exactly which rule broke.
2 — Road Network	Genetic Algorithm	The search space is 2⁷⁶⁰ possible road sets — a GA navigates it efficiently while encoding the two-independent-paths safety requirement directly into the fitness function.
3 — Ambulance Placement	Simulated Annealing	The minimax response-time objective has many local optima and flat regions; SA escapes them via probabilistic uphill moves as temperature cools.
4 — Emergency Routing	A* with dynamic replanning	An admissible Manhattan-distance heuristic guarantees the shortest path, and A* is faster than Dijkstra for real-time replanning when roads flood mid-journey.
5 — Crime Risk	K-Means (unsupervised) → Decision Tree (supervised)	K-Means finds natural risk groupings with no labels; a Decision Tree then classifies new data with inspectable, explainable splits.

Project structure

citymind/
├── city_graph.py        # Shared CityGraph — single source of truth for all modules
├── challenge1_csp.py     # City layout planning (CSP: backtracking + AC-3 + MRV)
├── challenge2_ga.py      # Road network optimization (Genetic Algorithm)
├── challenge3_sa.py      # Ambulance placement (Simulated Annealing)
├── challenge4_astar.py   # Emergency routing (A* with dynamic replanning)
├── challenge5_ml.py      # Crime risk prediction (K-Means + Decision Tree)
├── simulation.py         # 20-step simulation orchestrator
├── main.py               # Tkinter visual interface
├── docs/
│   ├── phase1-design-document.md   # Original design doc with algorithm justifications
│   └── final-report.md             # Full implementation report, incl. deviations from the design
├── requirements.txt
└── LICENSE

Getting started

Requirements

• Python 3.9+
• numpy, scikit-learn (Tkinter ships with most standard Python installs)

Install

git clone https://github.com/<your-username>/citymind.git
cd citymind
pip install -r requirements.txt

Run the interface

python main.py

This opens the city grid (center), a control panel with Step / Auto Run / Reset and manual road-block controls (left), and a live event log (right). Use the radio buttons to switch between the Road Network, Ambulance Coverage, and Crime Risk Heatmap overlays.

Run headless (no UI)

python -c "from simulation import run_full; from city_graph import CityGraph; run_full(CityGraph())"

This runs the full 20-step simulation and prints every event to the console.

Architecture: the shared city graph

Every module receives a reference to the same CityGraph instance — none of them keep a private copy. State changes always go through a small set of controller methods, so propagation across modules stays consistent:

• get_neighbors(node_id) — reachable neighbors with current effective costs
• block_road(u, v) / unblock_road(u, v) — flood / clearing events
• update_crime_label(node_id, label) — written by the ML pipeline (Challenge 5)
• recalculate_effective_costs() — applies risk multipliers (Low ×1.0, Medium ×1.3, High ×1.7) to every edge

Because of this, a road blocked by the simulation is immediately invisible to the A* router and the ambulance placer with zero extra plumbing — they just read effective_cost off the graph each time.

See docs/final-report.md for the full per-challenge design, including the parameters used for the GA and SA (population size, cooling schedule, etc.) and the deviations made from the original Phase 1 design document as implementation progressed.

Team

Member	Role
Sahar e Iman	Challenge 4 (A* routing) & Challenge 5 (ML crime risk) lead
Moaz Khan	Challenge 1 (CSP layout) lead, shared graph & UI
Asheel Saqib	Challenge 2 (GA road network) & Challenge 3 (SA ambulance placement) lead

License

This project is licensed under the MIT License — see LICENSE for details.