Multi-UAV Potential Game Framework

A game-theoretic approach to decentralized multi-UAV persistent monitoring with convergence guarantees

This repository implements the algorithms and simulation framework described in the thesis: "Path Optimization for UAV Waypoint Navigation Using Potential Game Theory" (Loyola Marymount University, 2025)

🎯 What does it do?

Coordinates 3–10 UAVs to monitor a grid of waypoints (e.g., wildfire perimeters) by:

• Modeling coordination as an exact potential game with guaranteed Nash equilibrium convergence
• Linking revisit frequency to Nyquist sampling requirements for temporal coverage guarantees
• Supporting controlled overlap at high-priority locations for redundancy
• Benchmarking against IRADA (state-of-the-art distributed allocation)

🚀 Why use this framework?

Unlike heuristic or centralized approaches, this provides:

• ✅ Convergence guarantees via potential game theory
• ✅ Decentralized negotiation (no single point of failure)
• ✅ Tunable redundancy (overlap mode for safety-critical regions)
• ✅ Reproducible benchmarking (open-source outputs, configs, plots)

---

---

📦 Quick Start (2 minutes)

Prerequisites

• Python 3.10+
• Virtual environment (recommended)

---

Installation & First Run

Before running the simulation framework, ensure you have the following installed:

Required Software:

• Python 3.10+ (tested on 3.10.18-3.11)
• pip (Python package manager)
• Git (for cloning the repository)

Recommended Tools:

• VS Code or PyCharm (for code editing)
• Terminal/Command Prompt (for running scripts)

---

Requirements

Create a requirements.txt file with:

numpy>=1.21.0
pandas>=1.3.0
matplotlib>=3.4.0
pyyaml>=5.4.0
openpyxl>=3.0.0
imageio>=2.9.0

---

Step 1: Clone the Repository

# Clone the repository
git clone https://github.com/Intemnets-Lab/Multi-UAV-Potential-Games.git

# Navigate into the created directory
cd Multi-UAV-Potential-Games

# Verify you're in the right place
ls
# You should see files like: Games.py, IRADA.py, Analysis.py, settings.yaml, etc.

---

Step 2: Install Dependencies

Create a virtual environment (recommended) and install required packages:

# Create virtual environment
python -m venv PotentialDrones

# Activate virtual environment
# On Windows:
PotentialDrones\Scripts\activate
# On macOS/Linux:
source PotentialDrones/bin/activate

# Install dependencies
pip install -r requirements.txt

Core Dependencies (if requirements.txt is missing):

pip install numpy pandas matplotlib pyyaml openpyxl imageio

---

Step 3: Verify settings.yaml Configuration

Open settings.yaml and verify/modify the basic parameters:

# Simulation
simulation:
  n_runs: 100           # Number of simulation runs
  seed: 42              # Random seed (null for random)
  enable_logging: true  # Enable detailed logs

# Grid configuration
grid:
  width: 5              # Grid width (number of columns)
  height: 5             # Grid height (number of rows)
  spacing: 1000         # Spacing between waypoints (meters)
  zero_prob: 0.3         # Probability of zero-revenue waypoints
  lambda: 0.1           # For IRADA only

# UAV configuration
uav:
  num_uavs: 2           # Number of UAVs
  speed: 20             # UAV speed (m/s)
  max_flight_time: 1800 # Max flight time (seconds, e.g., 30 min)

# Revenue configuration
revenue:
  random: true          # Use random revenue (true/false)
  fixedvalue: 50        # Fixed revenue if random=false
  min: 10               # Min random revenue
  max: 100              # Max random revenue



# Algorithms to run (true/false)
algorithms:
  sequentialGG: true
  sequentialGR: true
  sequentialRG: true
  sequentialRR: true
  randomGG:     true
  randomGR:     true
  randomRG:     true
  randomRR:     true

Key Parameters for First Run:

• num_uavs: 2 - Start small to verify the setup works
• grid.width: 5, grid.height: 5 - Generates a 5×5 grid (24 waypoints + 1 depot)
• n_runs: 5 - Run 5 simulations for statistical analysis
• algorithms - Enable only sequentialGG and randomRG for faster testing (sample)

---

Step 4: Run Your First Simulation

Option A: Run Non-Overlap & Overlap Games

python Games.py

What Happens:

1. Creates dated folders under Results/NonOverlap/ and Results/Overlap/
2. Runs all enabled algorithms (from settings.yaml)
3. Generates Excel files for:
   • Revenue rates (revenue/YYYY-MM-DD/simulationN/*.xlsx)
   • Waypoint sequences (sequences/YYYY-MM-DD/simulationN/*_sequences.xlsx)
   • Waypoint grids (waypoints/YYYY-MM-DD/simulationN/*.xlsx)
4. Outputs negotiation logs (if enablelogging: true)

Expected Output:

Simulation Started
NonOverlap SimRun 1/5
DEBUG: SimRun 1 Mode NonOverlap Overlap=False
DEBUG: NonOverlap SimRun 1 Running Preflight
Running negotiation/output for NonOverlap, SimRun 1, preflight status=True
Wrote SimRun1 to NonOverlap/ModeGGSequential
Overlap SimRun 1/5
...
Simulation Complete

---

Option B: Run IRADA Benchmark

python IRADA.py

What Happens:

1. Searches for the latest Non-Overlap waypoint file (uses same grid for fair comparison)
2. Runs IRADA allocator for nruns simulations
3. Outputs to BenchmarkingIRADA/revenue/ and BenchmarkingIRADA/sequences/

Expected Output:

IRADA Run 1/5
IRADA run took 3.45s
IRADA Run 2/5
...
All IRADA runs done.

---

Option C: Run Analysis & Generate Plots

After running simulations, generate visualizations:

python Analysis.py

What Happens:

1. Automatically finds the latest simulation folders
2. Generates per-algorithm revenue plots
3. Creates consolidated comparison plots
4. Produces boxplots for statistical analysis
5. Saves outputs to Visualizations/

Expected Output:

INFO: Using max_rounds=50
RUN: Generating NonOverlap graphs
Saved plot: Visualizations/NonOverlap/plots/.../UAV0_meanstd.png
...
Saved NonOverlap-vs-IRADA final-total boxplot

---

Step 5: Verify Outputs

Results/
├── NonOverlap/
│   ├── revenue/2025-12-16/simulation_1/
│   │   ├── UAVs2_GRID5_ModeGG_Sequential.xlsx
│   │   └── UAVs2_GRID5_ModeGR_Sequential.xlsx
│   ├── sequences/2025-12-16/simulation_1/
│   │   └── UAVs2_GRID5_1800_20_ModeGG_Sequential_sequences.xlsx
│   └── waypoints/2025-12-16/simulation_1/
│       └── UAVs2_GRID5_waypoints.xlsx
├── Overlap/
│   └── (same structure)
└── BenchmarkingIRADA/
    └── (same structure)

Visualizations/
├── NonOverlap/plots/2025-12-07/simulation_1/
│   ├── analysis_plots/
│   │   ├── UAVs9_GRID13_ModeRR_Sequential/
│   │   │   ├── UAV0_mean_std.png
│   │   │   ├── UAV1_mean_std.png
│   │   │   ├── Total_mean_std.png
│   │   │   └── Consolidated_mean.png          ← Per-algorithm consolidated
│   │   └── UAVs9_GRID13_ModeGG_Sequential/
│   │       └── (same structure)
│   ├── combined_total_revenue_rate.png         ← Cross-algorithm comparison
│   └── boxplots_uav_contribution/
│       ├── uav_contribution_ModeGG_Sequential.png
│       └── uav_contribution_ModeRR_Sequential.png
│
├── Overlap/plots/2025-12-07/simulation_1/
│   ├── analysis_plots/
│   │   ├── UAVs9_GRID13_ModeRG_Sequential/
│   │   │   ├── UAV0_mean_std.png
│   │   │   ├── UAV1_mean_std.png
│   │   │   ├── Total_mean_std.png              ← Note: Total_mean_std.png (with underscores)
│   │   │   └── Consolidated_mean.png
│   │   └── (other algorithms)
│   ├── combined_total_revenue_rate.png
│   └── boxplots_uav_contribution/
│       ├── uav_contribution_ModeRG_Sequential.png
│       └── uav_contribution_ModeGR_Random.png
│
├── IRADA/plots/2025-12-07/simulation_1/
│   ├── analysis_plots/
│   │   └── IRADA/
│   │       ├── UAV0_mean_std.png
│   │       ├── UAV1_mean_std.png
│   │       ├── Total_mean_std.png
│   │       └── Consolidated_mean.png
│   ├── combined_total_revenue_rate.png
│   └── boxplots_uav_contribution/
│       └── uav_contribution_IRADA.png
│
└── Comparisons/2025-12-07/simulation_1/
    ├── final_total_nonoverlap_vs_irada.png
    ├── final_total_overlap_only.png
    └── flight_time_left_all_algorithms.png

---

Step 6: Inspect Key Outputs

Revenue Workbook (UAVs2_GRID5_ModeGG_Sequential.xlsx)

• Sheets: SimRun1, SimRun2, ..., SimRun5
• Columns: negotiation_round, UAV0, UAV1, ...
• Values: Revenue rate per UAV per negotiation round

Sequences Workbook (*_sequences.xlsx)

• Columns: negotiation_round, UAV0, m0, UAV1, m1, ...
• UAVk: Waypoint sequence (e.g., "3-7-12")
• mk: Travel time/cost (mⱼ) for that sequence

Waypoints Workbook (UAVs2_GRID5_waypoints.xlsx)

• Columns: Waypoint, Revenue, X, Y
• Rows: One per waypoint (grid positions and revenues)

Plots (in Visualizations/)

• Consolidated_mean.png: Shows all UAV revenue trends + system mean
• finaltotal_nonoverlapvsirada.png: Boxplot comparing final performance

---

Common Issues & Fixes

Issue 1: FileNotFoundError: settings.yaml

Fix: Ensure settings.yaml is in the same directory as the Python scripts.

Issue 2: ModuleNotFoundError: No module named 'yaml'

Fix: Install missing dependencies:

pip install pyyaml openpyxl

Issue 3: Preflight Check Fails

Symptom: ERROR: Preflight failed (tour exceeds max_flight_time) Fix: Increase maxflighttime or decrease grid.width/height in settings.yaml:

uav:
  max_flight_time: 3600  # Increase to 60 minutes

Issue 4: IRADA Can't Find Waypoints

Symptom: FileNotFoundError: Expected NonOverlap waypoint folder does NOT exist Fix: Run Games.py first to generate Non-Overlap waypoint files, then run IRADA.py.

Issue 5: No Plots Generated

Fix: Check Analysis.py:

  GraphGeneration: bool = True  # Must be true for Analysis.py
  GifGeneration: bool = False   # To visualize the tours 

---

Quick Test Run (30 seconds)

For a minimal test to verify everything works:

# In settings.yaml, set:
uav:
  num_uavs: 2
grid:
  width: 3
  height: 3
simulation:
  n_runs: 2
algorithms:
  sequentialGG: true
  # Set all others to false

Then run:

python Games.py && python Analysis.py

You should see:

• 2 runs completed in ~10-20 seconds
• Excel files in Results/
• Plots in Visualizations/
• However, 100 runs with real-world parameters (from the configuration table below) completed in ~12 hours for 3 UAVs

---

Next Steps

After verifying the basic setup:

1. Scale Up: Increase num_uavs to 3-5, grid.width/height to 5-10
2. Enable More Algorithms: Turn on Random strategies in settings.yaml
3. Run Batch Simulations: Use Simulate.sh (see next section)
4. Explore Parameter Sensitivity: Vary speed, max_flight_time, zero_prob

---

This section gives a complete walkthrough from installation to first successful run, with troubleshooting for common issues.

Batch Execution with simulate.sh

For running multiple parameter sweeps:

#!/bin/bash
# Example: Test different UAV counts and grid sizes

for uavs in 2 3 5; do
  for grid in 5 10 15; do
    python Games.py --num_uavs $uavs --grid_width $grid --grid_height $grid --n_runs 10
    python IRADA.py --num_uavs $uavs --grid_width $grid --grid_height $grid --n_runs 10
    python Analysis.py --num_uavs $uavs --grid_width $grid --grid_height $grid
  done
done

Usage:

chmod +x Simulate.sh
./Simulate.sh

---

2. Configuration (settings.yaml)

All parameters load from settings.yaml (or can be overridden via CLI flags in Simulate.sh):

Attribute	Type	Default	Description
grid_width	int	13	number of cells along each axis (grid is grid_width×grid_height)
grid_height	int	13	number of cells along each axis (grid is grid_width×grid_height)
grid_spacing	float	92.608	physical distance (m) between adjacent grid points
zero_prob	float [0–1]	0.2	probability of each waypoint's revenue being zero
random_revenue	bool	False	re-draw random revenue ∈[revenue_min,revenue_max] every run?
fixed_revenue	float	50	if random_revenue=False, all non-zero waypoints use this
revenue_min, _max	float	60, 600	when random_revenue=True, uniform draw bounds
num_uavs	int	5	number of UAV agents
speed	float	16	UAV speed (units consistent with spacing (m)/time (s))
max_flight_time	float	1920	2-opt solver's maximum allowable tour time
n_runs	int	10	number of independent experiments (only when run_experiments=True)
Per‐Mode toggles	bool	see below	eight toggles to pick exactly which modes run:
sequential_GG	bool	True	run ModeGG in sequential pass?
sequential_GR	bool	False	run ModeGR in sequential pass?
sequential_RG	bool	False	run ModeRG in sequential pass?
sequential_RR	bool	False	run ModeRR in sequential pass?
random_GG	bool	False	run ModeGG in random pass?
random_GR	bool	True	run ModeGR in random pass?
random_RG	bool	False	run ModeRG in random pass?
random_RR	bool	True	run ModeRR in random pass?
enable_logging	bool	True	whether to write negotiation logs to disk
results_dir	str	"output/"	base directory for all MPG log files, plots, excels, gifs
IRADA_benchmarking_dir	str	"output/"	base directory for all IRADA log files, plots, excels, gifs

Overrides can be passed via CLI:

--num_uavs 12 --grid_width 15 --max_flight_time 2000 --sequential_GG true --random_RR false

---

Algorithm Naming Convention

Each algorithm is identified by three components:

Component	Options	Meaning
Mode	GG, GR, RG, RR	Drop-Pick strategy
	GG = Greedy Drop, Greedy Pick	UAVs drop lowest-revenue waypoint, pick highest-revenue waypoint
	GR = Greedy Drop, Random Pick	UAVs drop lowest-revenue waypoint, pick random waypoint
	RG = Random Drop, Greedy Pick	UAVs drop random waypoint, pick highest-revenue waypoint
	RR = Random Drop, Random Pick	UAVs drop random waypoint, pick random waypoint
Order	Sequential, Random	Agent turn order
	Sequential	UAVs negotiate in fixed order (UAV0 → UAV1 → ...)
	Random	UAVs negotiate in shuffled order each round
Game	NonOverlap, Overlap	Waypoint ownership model
	NonOverlap	Each waypoint assigned to exactly one UAV
	Overlap	High-value waypoints can be "cloned" for multiple UAVs

Short Labels (used in plots):

• NSGG = NonOverlap, Sequential, Greedy-Greedy
• ORGR = Overlap, Random, Greedy-Random
• IRADA = IRADA benchmark (chronological event-driven)

---

---

Project Structure

├── Games.py            # Main simulation (Non-Overlap & Overlap games)
├── IRADA.py            # IRADA benchmark allocator
├── Analysis.py         # Post-processing and visualization
├── settings.yaml       # Configuration file
├── Simulate.sh         # Batch execution script
├── Results/            # Simulation outputs
│   ├── NonOverlap/
│   │   ├── revenue/
│   │   ├── sequences/
│   │   └── waypoints/
│   ├── Overlap/
│   └── (same structure)
└── BenchmarkingIRADA/  # IRADA outputs

---

📂 Code Structure

├─ Games.py   # Simulation runner with algorithms, Excel, log files
├─ IRADA.py   # IRADA with algorithms, Excel, log files
├─ Analysis.py        # Post‑processing: plots, boxplots, animations from Excel
├─ Results/

---

File 1: Games.py

Purpose

Runs the Non-Overlapping and Overlapping game simulations with negotiation-based task allocation.

Core Classes & Functions

1. Config Class

class Config:
    def __init__(self, data: dict)
    @classmethod
    def from_yaml(cls, path='settings.yaml')
    def override(self, overrides: dict)

• __init__: Loads simulation parameters from YAML (grid size, UAV count, speed, max flight time, revenue ranges, algorithm toggles). Stores as attributes: self.gridwidth, self.gridheight, self.numuavs, self.speed, self.max_flight_time, etc.
• from_yaml: Factory method to create Config from settings.yaml.
• override: Applies CLI overrides (e.g., --numuavs 5) by updating matching attributes.

---

2. Logger Class

class Logger:
    def __init__(self, outputdir, filename='negotiationlog.txt', enabled=True)
    def write(self, level, msg)
    def info(self, msg)
    def debug(self, msg)
    def error(self, msg)
    def log(self, msg)

• __init__: Creates a timestamped log file at outputdir/filename. If enabled=False, logging is disabled.
• write: Internal method that writes [TIMESTAMP] [LEVEL] message to log file.
• info: Writes INFO-level messages (e.g., round summaries).
• debug: Writes DEBUG-level messages (e.g., detailed UAV decisions).
• error: Writes ERROR-level messages (e.g., preflight failures).
• log: Alias for info.

---

3. WaypointManager Class

class WaypointManager:
    def __init__(self, config, log, presetwaypoints=None, presetvalues=None)
    def apply_zero_prob(self)
    def _draw_revenues(self) -> List[int]
    def redraw_revenues(self)
    def _generate_grid(self) -> List[Tuple[float, float]]
    def _init_clones_threshold_based(self)
    def ensure_clones_exist_and_wire(self, sequences)

• __init__: Initializes the waypoint grid (excluding depot at (0,0)) and revenues. If presetwaypoints/presetvalues are provided (for Overlap mode), uses them; otherwise generates fresh grid.
• apply_zero_prob: Sets revenue to 0 for a fraction of waypoints based on config.zeroprob (simulating low-value areas).
• _draw_revenues: Randomly assigns revenue values to each waypoint from [config.revenue_min, config.revenue_max].
• redraw_revenues: Re-generates revenues (calls draw_revenues + apply_zero_prob).
• _generate_grid: Creates a grid of waypoints at (x*spacing, y*spacing) for x in [0, W), y in [0, H), excluding depot (0,0).
• _init_clones_threshold_based: (Overlap mode) Creates clone waypoints for high-revenue POIs above config.clonethreshold. Clones have identical coordinates and revenues. Populates self.clonemap (dict mapping orig ↔ clone).
• ensure_clones_exist_and_wire: Ensures clones match their originals' revenues (called after revenue redraw).

---

4. PathOptimizer Class

class PathOptimizer:
    @staticmethod
    def euclidean(a, b) -> float
    def STSPSolver(self, depot, waypoints, speed, maxflighttime) -> (List[int], float)
    def simulate_mj(self, depot, waypoints, speed, maxflighttime) -> (float, float, float, float)

• euclidean: Computes Euclidean distance between two points a and b.
• STSPSolver: Uses 2-opt heuristic to optimize the Traveling Salesman Problem (TSP) tour starting/ending at depot. Returns (best_order, mⱼ) where best_order is the optimized waypoint sequence and mⱼ is the tour time/distance cost.
• simulate_mj: Simulates multi-loop (MJ) tours: calculates forward leg, return leg, and jump-back distances for a given sequence. Returns (mⱼ_manual, forward_dist, return_dist, total_time).

---

5. UAVAgent Class

class UAVAgent:
    def __init__(self, uid, manager, optimizer, config, logger)
    def remaining_capacity(self, t: float) -> float
    def current_POIs(self) -> List[int]
    def weighted_center(self, t: float) -> Tuple[float, float]
    def set_path(self, path: List[int])
    def revenue_rate(self, candidate_sequence=None) -> float
    def position(self, t: float) -> Tuple[float, float]
    def drop_waypoint(self, select_mode: str) -> (int, int, List[int], float)
    def pick_waypoint(self, pool, select_mode: str) -> (int, None, List[int], float)
    @staticmethod
    def exclude_repeated_locs(sequence, clonemap, waypoints) -> List[int]

• __init__: Initializes UAV with ID, waypoint manager, optimizer, config, and logger. Creates self.sequence (current waypoint list).
• remaining_capacity: Returns remaining flight time budget at time t.
• current_POIs: Returns the list of waypoints currently in the UAV's path.
• weighted_center: Computes the revenue-weighted centroid of owned waypoints (used for IRADA's η computation).
• set_path: Assigns a new path (waypoint sequence) to the UAV.
• revenue_rate: Computes average revenue per unit time for the tour: total_revenue / total_time. If candidate_sequence is provided, evaluates that instead of self.sequence.
• position: Returns UAV's current coordinates (last waypoint visited or depot).
• drop_waypoint: Drops a waypoint based on select_mode ('greedy' = lowest revenue, 'random' = random). Returns (dropped_wp, clone_wp, new_sequence, gain).
• pick_waypoint: Picks a waypoint from the pool based on select_mode. Returns (picked_wp, None, new_sequence, gain).
• exclude_repeated_locs: (Static method) Removes duplicate waypoints from a sequence, accounting for clones. If both a waypoint and its clone are present, keeps only one.

---

6. InitialAssigner Class

class InitialAssigner:
    def __init__(self, config, logger=None)
    def uniform(self, W) -> List[List[int]]

• __init__: Stores config and optional logger.
• uniform: Randomly distributes waypoints W (list of POI indices) uniformly among UAVs using round-robin shuffling. Returns List[List[int]] where each inner list is a UAV's initial sequence.

---

7. TaskAllocator (Base Class)

class TaskAllocator:
    def __init__(self, manager, config, logger, optimizer)
    def setup_agents(self, initial_sequences=None) -> List[UAVAgent]
    def allocate(self, initial_sequences) -> (List[List[float]], List[List[List[int]]])

• __init__: Base class for allocation strategies. Stores manager, config, logger, optimizer.
• setup_agents: Creates UAVAgent instances with initial sequences. If initial_sequences=None, uses InitialAssigner.uniform() to generate them. If overlap mode is enabled, calls ensure_clones_exist_and_wire().
• allocate: Abstract method – implemented by subclasses (e.g., NegotiationAllocator).

---

8. NegotiationAllocator (Subclass of TaskAllocator)

class NegotiationAllocator(TaskAllocator):
    def __init__(self, manager, config, log, drop_select, pick_select, maxrounds=100, patience=5)
    def allocate(self, initial_sequences=None) -> (List[List[float]], List[List[List[int]]])

• __init__: Defines drop strategy (drop_select: 'greedy'/'random') and pick strategy (pick_select: 'greedy'/'random'), plus maxrounds and patience for convergence.
• allocate: Core negotiation loop:
  1. Setup: Calls setup_agents() to initialize UAVs.
  2. Main Loop (up to maxrounds):
     • Drop Phase: Each UAV drops a waypoint based on drop_select.
     • Pick Phase: Each UAV picks a waypoint from the pool based on pick_select.
     • Pool Reassignment: Any waypoints left in the pool are optimally reinserted into their original owner's sequence.
     • MJ Calculation: Computes mⱼ (tour cost) for each UAV using STSP_Solver.
     • Revenue Rate: Computes revenue_rate() for each UAV.
     • Convergence Check: If total revenue doesn't improve for patience rounds, stops.
     • Rollback Detection: If revenue decreases, rolls back to previous state. If same rollback state repeats 5 times, breaks (stasis detected).
  3. Returns: (rates, history) where:
     • rates: List of lists [[UAV0_rate_r1, UAV1_rate_r1, ...], [UAV0_rate_r2, ...], ...]
     • history: List of lists of sequences [[[UAV0_seq_r1], [UAV1_seq_r1]], ...]

Key Features:

• Rollback detection: Detects cycles in state and breaks the loop.
• Convergence: Stops if revenue doesn't improve for self.patience rounds.
• Clone handling: Logs clone pair locations in overlap mode.

---

9. PreflightChecker Class

class PreflightChecker:
    def __init__(self, manager, config, log)
    def run(self) -> bool

• __init__: Initializes with waypoint manager, config, and logger.
• run: Checks if any UAV's initial tour exceeds maxflighttime. Uses STSP_Solver to compute optimal tour for initial assignment. Returns True if all tours are feasible, False otherwise. (Only runs for Non-Overlap mode.)

---

10. SimulationRunner Class

class SimulationRunner:
    def __init__(self, cfg, log)
    def _find_or_create_sim_folder(self) -> str
    def run(self)
    def _define_strategies(self) -> Dict
    def _prepare_initial_sequences(self) -> List[List[int]]
    def _compute_mj_matrix(self, history) -> (List[List[float]], List[List[List[int]]])
    def _make_outputs(self, rates, mjmatrix, history) -> (DataFrame, DataFrame, DataFrame)
    def _write_incremental(self, modekey, stratname, runidx, dfrev, dfseq, dfwp)
    def _append_sheet_to_excel(self, filepath, df, sheetname, index=False)

• __init__: Sets up manager, assigner, optimizer, and output folders. Sets self.datestr to current date.
• _find_or_create_sim_folder: Finds the next available simulation{N} folder under Results/{mode}/revenue/YYYY-MM-DD/. Creates folders if they don't exist.
• run: Main orchestrator:
  1. Creates fresh Non-Overlap grid for each run (n_runs times).
  2. For each run:
     • Runs Non-Overlap game (with preflight check).
     • Adds clones for Overlap game using the same base grid.
     • Executes all enabled strategies (ModeGG/GR/RG/RR × Sequential/Random).
     • Writes outputs incrementally.
• _define_strategies: Returns dictionary of strategy names → factory functions. Each factory sets config.randomize_sequence and returns a NegotiationAllocator instance.
• _prepare_initial_sequences: Filters zero-revenue waypoints (value > 0) and assigns them uniformly to UAVs using InitialAssigner.uniform(). Removes repeated locations (clones) using UAVAgent.exclude_repeated_locs().
• _compute_mj_matrix: For each round's sequences:
  1. Removes clones using exclude_repeated_locs().
  2. Optimizes tours using STSP_Solver (2-opt TSP).
  3. Computes mⱼ values.
  4. Returns (mj_matrix, optimized_history) where:
     • mjmatrix: List of lists [[UAV0_mj_r1, UAV1_mj_r1, ...], ...]
     • optimized_history: List of lists of optimized sequences (after 2-opt).
• make_outputs: Creates three DataFrames:
  • dfrev: Columns = ['negotiation_round', 'UAV0', 'UAV1', ...], values = revenue rates.
  • dfseq: Columns = ['negotiation_round', 'UAV0', 'm0', 'UAV1', 'm1', ...], values = sequences (as "1-3-5" strings) and mⱼ values (interleaved).
  • dfwp: Columns = ['Waypoint', 'Revenue', 'X', 'Y'], values = waypoint coordinates and revenues.
• _write_incremental: Appends a new sheet (SimRun{runidx}) to existing Excel files for revenue, sequences, and waypoints. Filenames: UAVs{N}_GRID{W}_{stratname}.xlsx.
• _append_sheet_to_excel: Helper function to append/replace sheet in Excel file using openpyxl engine.

---

Key Variable Names (from code)

Variable	Type	Purpose
self.grid_width	int	Grid width (number of columns)
self.grid_height	int	Grid height (number of rows)
self.grid_spacing	float	Physical distance (m) between waypoints
self.num_uavs	int	Number of UAVs
self.max_flight_time	float	Maximum flight time (seconds)
self.zero_prob	float	Probability of zero-revenue waypoints
self.clone_threshold	float	Revenue threshold for creating clones

File 2: IRADA.py

Purpose

Implements the IRADA (Iterative Resource Allocation with Dynamic Adjustment) benchmark allocator using chronological event-driven scheduling.

Core Functions

1. IRADAAllocator Class

class IRADAAllocator(TaskAllocator):
    def __init__(self, manager, config, log, max_rounds=1000)
    def allocate(self, initial_paths) -> (List[List[float]], List[List[List[int]]])

• __init__: Initializes with max rounds and κ (kappa) coefficient.
• allocate: Event-driven simulation:
  1. Initializes each UAV with an "ownership" set (initial waypoints).
  2. Computes first waypoint picks using restricted pool (ownership).
  3. Uses a priority queue (heap) to process events chronologically: (arrival_time, uav_id, waypoint).
  4. When a UAV arrives at a waypoint, it:
     • Records the trip segment.
     • Selects the next waypoint (or depot) using select_next_target_IRADA.
     • Schedules the next arrival event.
  5. When a UAV returns to depot, it closes a "round" (depot→trip→depot) and computes revenue rate.
  6. Stops when all UAVs complete max_rounds depot returns.
  7. Logs communication timestamps (last_comm) between UAVs.

---

2. IRADA Score Functions

def compute_phi(agent, poiidx, t, all_agents) -> float
def compute_epsilon(agent, poiidx, t) -> float
def compute_eta(agent, poi_idx, t, all_agents) -> float
def select_next_target_IRADA(agent, t, all_agents, include_depot=True, restrict_pool=None) -> int

• computephi(φ): Information value coefficient:

  • φᵢ(t) = Î(i,t) (estimated revenue/information at waypoint i at time t).

• computeepsilon(ε): Feasibility coefficient:

  • εᵢ,ᵥ(t) = exp(-γ · min(0, Rᵢ,ᵥ(t)))
  • Where Rᵢ,ᵥ(t) = C_remain(t) - dist(qᵥ, pᵢ) - dist(pᵢ, depot) - Cₘₐᵣgᵢₙ
  • Penalizes waypoints that violate flight time constraints.

• computeeta(η): Communication coefficient:

  • ηᵢ,ᵥ(t) = Π_{u≠v, i∈ownership_u} [1 - exp(-λ(t - t_comm(v,u)))] · exp(-||pᵢ - c_u(t)||² / ||c_u(t) - c_v(t)||²)
  • Encourages coordination: penalizes selecting waypoints owned by recently communicated UAVs and far from the agent's weighted center.

• selectnexttargetIRADA: Computes score = φ · ε · η for all waypoints (or depot) and selects the highest. If restrictpool is provided (first pick), only considers those waypoints.

---

3. ChronoSimulationRunner Class

class ChronoSimulationRunner:
    def __init__(self, cfg, log)
    def run(self)
    def prepare_output_dirs(self) -> (str, str)
    def dump_excel_data(self, rev_data, path_data, rev_dir, path_dir)

• __init__: Initializes IRADA-specific runner.
• run: Main IRADA execution:
  1. Loads Non-Overlap waypoint file (using findlatestwaypointsresultsroot) to ensure IRADA uses the same grid as Non-Overlap.
  2. Runs IRADAAllocator.allocate() for nruns times.
  3. Collects per-UAV revenue rates and trip sequences.
  4. Writes outputs to Benchmarking/revenue/ and BenchmarkingIRADA/sequences/.
• prepare_output_dirs: Creates dated simulation_N folders under Benchmarking/.

Let me complete the Analysis.py section of the README with detailed function documentation:

---

File 3: Analysis.py

Purpose

Post-processes simulation outputs to generate visualizations, statistical analyses, and comparative plots across all three game modes (Non-Overlap, Overlap, IRADA).

Core Functions

---

1. Configuration & Setup Functions

class Config:
    def __init__(self, data: dict)
    @classmethod
    def fromyaml(cls, path='settings.yaml')
    def override(self, overrides: dict)

• __init__: Loads analysis configuration including paths (results_dir, visualization_dir, irada_benchmarking_dir), simulation parameters, and master switches (GraphGeneration, GifGeneration).
• from_yaml: Factory method to create Config from settings.yaml.
• override: Applies CLI overrides for flexible parameter tuning.

def setplotstyle()

• Purpose: Configures global matplotlib styling (font family, sizes) for publication-ready plots.
• Sets: Font family (Times New Roman), title size (18), axis labels (24), tick labels (24), legend (24).

---

2. Path & File Management Functions

def find_latest_simulation(root: Path) -> Path

• Purpose: Finds the most recent simulation folder under a given root directory.
• Logic:
  1. Sorts date folders (YYYY-MM-DD) under root.
  2. Finds highest simulation_N folder under the latest date.
• Returns: Path to Results/{mode}/{type}/YYYY-MM-DD/simulation_N/.

def mode_from_path(p: Path) -> str

• Purpose: Extracts game mode from path components.
• Returns: "NonOverlap", "Overlap", "IRADA", or "Other".

def label_from_revenuefile(f: Path) -> str

• Purpose: Creates concise algorithm labels from revenue workbook filenames.
• Examples:
  • UAVs2_GRID5_ModeGG_Sequential.xlsx → "ModeGGSequential"
  • UAVs2_GRID5_IRADA.xlsx → "IRADA"

def short_algo_label(game_label: str, algo_label: str) -> str

• Purpose: Maps verbose labels to compact taxonomy codes for plots.
• Examples:
  • ("NonOverlap", "ModeGGSequential") → "NSGG"
  • ("Overlap", "ModeGRRandom") → "ORGR"
  • ("IRADA", "IRADA") → "IRADA"
• Format: {Game}{Order}{Mode} where:
  • Game: N (NonOverlap), O (Overlap), IRADA
  • Order: S (Sequential), R (Random)
  • Mode: GG, GR, RG, RR

def visplotsrootforsim(visroot: Path, mode: str, revsimpath: Path) -> Path
def visgifsrootforsim(visroot: Path, mode: str, seqsimpath: Path) -> Path
def viscomparisonsroot(visroot: Path, nonrevsim: Path) -> Path

• Purpose: Constructs output paths for visualizations.
• Returns:
  • Visualizations/{mode}/plots/YYYY-MM-DD/simulationN/
  • Visualizations/{mode}/gifs/YYYY-MM-DD/simulationN/
  • Visualizations/Comparisons/YYYY-MM-DD/simulationN/

---

3. Revenue Analysis Functions

def analyze_revenue_excels_graphs(excel_dir: str, out_root: str = None)

• Purpose: Primary revenue analysis function - generates three types of plots for each revenue workbook:

  Plot 1: Per-UAV Mean±Std Revenue Rate

  • One plot per UAV showing mean revenue rate ± standard deviation across runs.
  • X-axis: Negotiation round
  • Y-axis: Revenue rate
  • Shaded region: Standard deviation band
  • Output: {UAVk}_meanstd.png

  Plot 2: Total Revenue Rate Mean±Std

  • Aggregated total revenue rate across all UAVs.
  • Shows system-wide performance per round.
  • Output: Total_mean_std.png

  Plot 3: Consolidated Mean Plot

  • All UAV means + system mean on one plot.
  • Legend positioned outside (right) with dynamic figure width.
  • Output: Consolidated_mean.png

• Methodology:

  1. Reads all sheets (SimRun1, SimRun2, ...) from each .xlsx file.
  2. Extracts UAV columns and pads to max rounds using forward-fill.
  3. Stacks across runs: arr[run, round, uav].
  4. Computes mean(axis=0) and std(axis=0, ddof=1) across runs.

---

def plot_consolidated_total_revenue(exceldir: str, outputpath: str = None)

• Purpose: Cross-algorithm comparison - plots mean total revenue rate for all algorithms on a single figure.
• Features:
  • Dynamic figure width based on number of algorithms (base_w + extra_per_algo × (n_algos - 3)).
  • Uses short taxonomy labels (NSGG, ORGR, IRADA).
  • Legend outside plot area (right side).
• Output: combined_total_revenue_rate.png in Visualizations/Comparisons/.

---

4. Boxplot Functions

def boxplot_final_totals_with_irada(rev_dirs: List[str/Path], out_png: str = None)

• Purpose: Creates two separate boxplots of final total revenue per run:

  Boxplot 1: NonOverlap vs IRADA

  • Includes all NonOverlap strategies + IRADA.
  • Excludes Overlap data.
  • Sorts so IRADA appears last (visual separation).
  • Output: finaltotal_nonoverlap_vs_irada.png

  Boxplot 2: Overlap Only

  • Includes only Overlap strategies.
  • Separate comparison to isolate Overlap performance.
  • Output: final_total_overlap_only.png

• Methodology:

  1. Reads all revenue workbooks from provided directories.
  2. Extracts final row (last negotiation round) from each sheet.
  3. Sums UAV columns to get total revenue.
  4. Groups by algorithm label.
  5. Uses orange median lines, grid for readability.

---

def boxplot_uav_contribution_all(rev_dirs: str/Path, outpng: str = None)

• Purpose: Analyzes individual UAV contributions to total revenue.
• Generates: One boxplot per algorithm showing final revenue distribution across UAVs.
• Use Case: Identifies workload balance - are some UAVs consistently underperforming?
• Output: Saved to {revsim}/boxplots/uavcontribution/ with one plot per algorithm.

---

def boxplot_flight_time_left(seq_roots: List[str/Path], cfg: Config, out_png: str, nonoverlap_wp_sim: str/Path = None)

• Purpose: Computes remaining flight time for the final tour of each UAV in each run.
• Methodology:
  1. Parses UAV sequences from the last negotiation round.
  2. For IRADA: Computes single depot→tour→depot distance (requires NonOverlap waypoints file).
  3. For Non-Overlap/Overlap: Uses mⱼ values from sequences workbook.
  4. Calculates: remaining = maxflighttime - (distance / speed).
  5. Plots boxplot showing feasibility margin.
• Output: flighttimeleft_allalgorithms.png in Visualizations/Comparisons/.
• Insight: Negative values indicate infeasible tours (constraint violations).

---

5. Simulation Picking & Overrides

def pick_sim(rootseq: Path, rootrev: Path, manualdate: str = None, manualsim: str = None) -> (Path, Path)

• Purpose: Selects which simulation to analyze.
• Logic:
  • If manual_date and manual_sim are provided (e.g., from YAML overrides), uses those.
  • Otherwise, finds the latest simulation using find_latest_simulation().
• Returns: Tuple of (sequences_sim_path, revenue_sim_path).

---

6. Main Execution Block

if __name__ == "__main__":
    # 1. Load config from settings.yaml + CLI overrides
    # 2. Set plot style
    # 3. Pick simulations (NonOverlap, Overlap, IRADA)
    # 4. Generate per-algorithm graphs (if GraphGeneration enabled)
    # 5. Create consolidated comparisons
    # 6. Generate boxplots (final totals, UAV contributions, flight time)

Execution Flow:

1. Config Loading: Loads settings.yaml, applies CLI overrides (--numuavs, --gridwidth, etc.).
2. Simulation Selection:
   • NonOverlap: Uses manual overrides (NONDATE, NONSIM) or finds latest.
   • Overlap: Uses manual overrides (OVERDATE, OVERSIM) or finds latest.
   • IRADA: Uses manual overrides (IRADADATE, IRADASIM) or finds latest.
3. Graph Generation (if GraphGeneration=True):
   • Calls analyzerevenue_excelsgraphs() for each mode.
   • Generates per-UAV, total, and consolidated plots.
4. Consolidated Comparisons:
   • Calls plotconsolidatedtotalrevenue() for each mode.
   • Creates cross-algorithm comparison plots.
5. Boxplot Generation:
   • Final total revenue comparisons (NonOverlap vs IRADA, Overlap only).
   • UAV contribution analysis per mode.
   • Flight time left analysis across all modes.

---

7. Helper Functions

def algo_label_from_seq_file(seqfile: Path) -> str

• Purpose: Infers algorithm label from sequence filename.
• Examples:
  • UAVs2_GRID5_1003_ModeGG_Random_sequences.xlsx → "ModeGGRandom"
  • UAVs2_GRID5_IRADA_sequences.xlsx → "IRADA"

def get_max_rounds_from_algorithms(outputdir: str, datestr: str, simdir: str) -> int

• Purpose: Scans revenue and sequence workbooks to determine the maximum number of negotiation rounds across all runs/algorithms.
• Use Case: Ensures consistent x-axis limits when comparing algorithms with different convergence times.

def load_waypoint_revenues(pathoroutputdir, datestr=None, simdir=None, cfg=None, runidx=1) -> (List[int], List[Tuple])

• Purpose: Flexible waypoint loader for IRADA analysis.
• Two modes:
  • Case A (direct path): Load from exact path (e.g., UAVs2GRID5waypoints.xlsx).
  • Case B (legacy): Construct path from outputdir, datestr, simdir, cfg.
• Returns: (revenues, coords) for a specific run (sheet SimRun{runidx}).

---

Key Analysis Outputs

Output Type	Files Generated	Purpose
Per-Algorithm Revenue	{UAVk}_mean_std.png, Total_meanstd.png, Consolidated_mean.png	Tracks revenue convergence per UAV and system-wide
Cross-Algorithm Comparison	combined_total_revenue_rate.png	Compares all strategies (NSGG, ORGR, IRADA, etc.)
Final Total Boxplots	final_total_nonoverlapvsirada.png, finaltotal_overlaponly.png	Statistical comparison of final performance
UAV Contribution Boxplots	uav_contribution/*.png	Analyzes workload distribution across UAVs
Flight Time Left Boxplot	flight_time_left_all_algorithms.png	Validates constraint satisfaction

---

Usage Example

# Run analysis with default settings
python Analysis.py

# Override specific simulation
python Analysis.py --numuavs 3 --gridwidth 10 --nruns 50

# Use manual simulation selection (edit settings.yaml)
# NONDATE: "2025-12-15"
# NONSIM: "simulation3"
python Analysis.py

---

This completes the comprehensive function documentation for all three core files.

This is an excellent and comprehensive README! You've covered all the critical components. Here are a few minor suggestions to make it even more complete:

---

---

📂 Outputs

After each run:

Results/
  revenue/YYYY-MM-DD/simulation_X/
  sequences/YYYY-MM-DD/simulation_X/
  waypoints/YYYY-MM-DD/simulation_X/
Benchmarking/IRADA/
  revenue/YYYY-MM-DD/simulation_X/
  sequences/YYYY-MM-DD/simulation_X/
sim_logs/
  run_1_prep.txt
  run_1_main.txt
  run_1_analysis.txt

• Revenue Excel → per-algo totals (per round).
• Sequences Excel → UAV tours.
• Waypoints Excel → grid coords & revenues.
• Plots → consolidated revenue, IRADA boxplots, per UAV contribution to total revenue rate, flight-time left.

---

📈 Interpreting Results

• Revenue plots: compare convergence of total revenue across algorithms.
• Boxplots: distribution of results across runs (total revenue, UAV contributions, flight-time left).
• IRADA: always benchmarked side-by-side with other strategies.
• GIFs: optional animated UAV routes (if GifGeneration=True in Analysis.py).

---

---

🔧 Extending the Framework

• Add new allocators (e.g., CNP, CBBA, TS-DTA) by subclassing TaskAllocator.
• Toggle them in Config via sequential_X, random_X.
• New Excel outputs are auto-picked up by Analysis.py.

---

• Add new allocators: subclass TaskAllocator, implement allocate(pool) → (rates, history).
• Toggle in Config: add sequential_NewAlgo, random_NewAlgo, include in strategies dict.
• Analysis: new Excel files are auto‑picked up by Analysis.py functions.

---

Work in progress—future improvements: advanced multi‑objective metrics, dynamic deadlines, real‑world maps.

Performance Tuning Tips

For Large Grids (>10×10):

• Increase max_flight_time to avoid preflight failures
• Enable only 2-3 algorithms initially (disable Random modes)
• Reduce n_runs to 5 for faster iteration

For Many UAVs (>5):

• Expect longer negotiation times (10-50 rounds)
• Use enablelogging: false to speed up execution
• Monitor rollback_stasis in logs (indicates cycles)

For Statistical Significance:

• Use n_runs ≥ 30 for publication-ready results
• Set fixed seed for reproducibility across experiments
• Run IRADA with same maxrounds as longest MPG convergence

Memory Optimization:

• Disable GIF generation for large experiments
• Use Analysis.py with manual date/sim selection to avoid scanning all folders

---

---

Frequently Asked Questions (FAQ)

Q1: Why does Overlap sometimes perform worse than NonOverlap?
A: Clones add waypoints but don't increase total revenue. If clone_threshold is too low, UAVs waste time revisiting the same high-value locations instead of covering more area.

Q2: Can I run only IRADA without MPG?
A: No. IRADA requires a NonOverlap waypoint file to ensure fair comparison on the same grid. Run Overlap.py first, then IRADA.py.

Q3: What's the difference between sequences.xlsx and revenue.xlsx?
A:

• sequences.xlsx: Lists which waypoints each UAV visits per round
• revenue.xlsx: Shows the revenue rate (revenue/time) achieved per round

Q4: How do I reproduce thesis results exactly?
A: Use the same seed, grid parameters, and n_runs from the thesis config. Seed ensures identical random revenue/assignment.

Q5: Can I visualize UAV paths on a map?
A: Not built-in. Export waypoint coordinates from waypoints.xlsx and plot using matplotlib.pyplot.scatter() or GIS tools.

---

9. MIT License (open-source)

MIT License

Copyright (c) 2025 Intemnets-Lab

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

Troubleshooting Convergence Issues

Symptom 1: Negotiation doesn't converge (>100 rounds)

Causes:

• Grid too large relative to max_flight_time
• Too many zero-revenue waypoints (zero_prob too high)
• Rollback stasis (cyclic state repetition)

Fixes: simulation: patience: 10 # Reduce patience for faster termination rollback_limit: 3 # Lower rollback tolerance

Symptom 2: IRADA outperforms MPG significantly

Possible Reasons:

• MPG stuck in local Nash equilibrium
• Initial assignment biased (try AngleAssigner instead of uniform)
• IRADA benefits from continuous optimization vs. discrete negotiation

Analysis:

• Compare boxplots_uav_contribution to check workload balance
• Inspect negotiationlog.txt for repeated drop/pick patterns

---

---

Known Limitations

1. 2-opt TSP Heuristic: Not guaranteed to find global optimum (use for speed over exactness)
2. Static Revenue Model: Waypoint values don't decay over time (future work: temporal dynamics)
3. Homogeneous UAVs: All UAVs have identical speed and max_flight_time
4. Euclidean Distance: Assumes flat terrain (no elevation or no-fly zones)
5. Clone Threshold: Fixed per simulation (future: adaptive cloning based on demand)