Multi-Agent Polygon Generator

A Python tool for procedural generation of 2D grid-map benchmark instances for multi-agent planning tasks (MAPF and MAPD).

Overview

This project generates reproducible 2D grid-map benchmark environments together with multi-agent scenarios, structural and graph metrics, visual previews, and a graph representation suitable for external planning modules.

A single run takes a YAML configuration file and a seed and produces:

• a grid map (binary occupancy: 0 free, 1 obstacle);
• a scenario with agents, starts, goals, and — for MAPD — pickup/dropoff tasks;
• a raw map.png and a preview.png showing agents and tasks;
• structural, scenario, and graph metrics;
• a graph representation (graph.json, graph_instance.json, nodes.csv, edges.csv) for use by external graph-based planners.

The tool is a benchmark generator, not a planner: it produces inputs for MAPF/MAPD solvers but does not solve the planning problems itself.

Project Goal

The goal is to provide configurable, seed-based, reproducible test environments for MAPF and MAPD research and coursework experiments. Maps and scenarios are fully described by a YAML config plus a seed, so any case can be regenerated bit-for-bit. Multiple structurally distinct map types are supported so algorithms can be compared on environments with different connectivity, density, and bottleneck characteristics.

The project is intentionally limited in scope: it does not include a solver, a physics simulation, or a robotics stack.

Supported Map Types

Four map generators are implemented in src/generators/:

Map type	Description
warehouse	Structured warehouse-style layout with regular aisles and shelf blocks. Used to model storage/dispatch scenarios common in MAPD literature.
bottleneck	A map with a single narrow passage separating two open areas. Designed to stress congestion and conflict resolution at narrow corridors.
maze	DFS-carved maze with long corridors, dead ends, and junctions. Stresses planners with few alternative routes and long path lengths.
thin_walls	Open map with randomly placed thin wall segments. Provides structurally varied open environments with controllable obstacle count and wall length.

For the maze type, the MAPF scenario generator uses dedicated logic (maze_mode=True in src/scenarios/mapf.py):

• spacing between chosen cells uses BFS distance on the corridor graph, not Manhattan distance, so two cells that are close along the corridor are never picked together even if they are far in straight-line distance;
• junction cells (degree ≥ 3) are preferred over dead ends and corridor cells, because junctions have alternative routes and are less likely to block other agents;
• the placement is then validated: if any agent's start lies on the BFS shortest path of another agent (i.e. it would block another agent's only route in a narrow corridor), the placement is rejected and re-sampled with a perturbed shuffle.

This avoids generating unsolvable maze scenarios where an agent sits on top of another agent's only path.

Supported Scenario Types

Three scenario generators are implemented in src/scenarios/:

Scenario type	Description
mapf	Multi-Agent Path Finding. Each agent has a start and a goal. No tasks.
mapd	Multi-Agent Pickup and Delivery. Agents have start positions; tasks are independent pickup/dropoff pairs assigned to the agent pool.
bottleneck_stress	Stress-test scenario that places agents so that they must traverse the bottleneck corridor, generating high contention at the narrow passage.

All scenario generators support minimum start/goal/wall spacing parameters (min_start_distance, min_goal_distance, min_wall_distance).

A single_nav.py file is present under src/scenarios/ but is empty and is not used by the current demo pipeline.

Project Structure

polygon_generator/
├── configs/
│   ├── warehouse_mapd.yaml
│   ├── bottleneck_stress.yaml
│   ├── maze_mapf.yaml
│   └── thin_walls_mapf.yaml
├── src/
│   ├── generators/
│   │   ├── warehouse.py
│   │   ├── bottleneck.py
│   │   ├── maze.py
│   │   └── thin_walls.py
│   ├── scenarios/
│   │   ├── mapf.py
│   │   ├── mapd.py
│   │   ├── bottleneck_stress.py
│   │   └── single_nav.py        # placeholder, currently empty
│   ├── validation/
│   │   ├── checks.py            # connectivity ratio
│   │   └── metrics.py           # grid + scenario metrics
│   └── export/
│       ├── files.py             # PNG / JSON / YAML writers
│       ├── visualize.py         # matplotlib preview
│       └── graph.py             # grid-to-graph export
├── outputs/                     # generated demo cases
├── generate_polygon.py          # single-case entry point
├── batch_generate.py            # runs all four demo cases
├── requirements.txt
└── README.md

Installation

Python 3.10+ is recommended.

python -m venv .venv
source .venv/bin/activate
pip install -r requirements.txt

On Windows, activate the virtual environment with:

.venv\Scripts\activate

Dependencies (requirements.txt): numpy, pillow, matplotlib, pyyaml.

Running the Generator

Generate a single case by passing a config, an output directory, and a seed:

python generate_polygon.py --config configs/warehouse_mapd.yaml --out outputs/case_001_warehouse_mapd --seed 42
python generate_polygon.py --config configs/bottleneck_stress.yaml --out outputs/case_002_bottleneck_stress --seed 42
python generate_polygon.py --config configs/maze_mapf.yaml         --out outputs/case_003_maze_mapf         --seed 42
python generate_polygon.py --config configs/thin_walls_mapf.yaml   --out outputs/case_004_thin_walls_mapf   --seed 42

Batch generation

batch_generate.py runs all four demo cases in sequence with seed=42 and writes their outputs under outputs/case_00X_*:

python batch_generate.py

It invokes generate_polygon.py as a subprocess for each case defined in its CASES list and aborts if any case fails.

Demo Cases

Case	Map type	Scenario type	Purpose
case_001_warehouse_mapd	warehouse	mapd	Structured storage environment with pickup/dropoff tasks.
case_002_bottleneck_stress	bottleneck	bottleneck_stress	Stress-test of conflict resolution at a single narrow passage.
case_003_maze_mapf	maze	mapf	Long-corridor MAPF with junction-aware, block-safe agent placement.
case_004_thin_walls_mapf	thin_walls	mapf	Open environment with random thin-wall obstacles.

Output Files

Each case directory contains the following files (only files actually produced by the current code are listed):

File	Description
map.png	Raw grid visualization (black = obstacle, white = free), upscaled 10× for readability.
preview.png	Scenario preview with agents, goals, pickups, and dropoffs annotated on the map.
scenario.json	Scenario data: type, number of agents, and per-agent start/goal positions.
tasks.json	MAPD task list (pickup/dropoff pairs). Empty list ([]) for MAPF and bottleneck-stress scenarios.
metrics.json	Structural, scenario, and graph metrics for the generated case.
config_used.yaml	The exact configuration plus the resolved seed used for this run (reproducibility snapshot).
graph.json	Graph representation of the map: nodes, edges, adjacency.
graph_instance.json	Combined file: graph + scenario + tasks. Intended as the single input for external planning modules.
nodes.csv	Tabular node list (id, row, col, x, y).
edges.csv	Tabular edge list (from, to, cost).

Coordinates in scenario.json and tasks.json are stored as [x, y] (column first, row second). Graph node IDs use the inverse convention row_col (see below).

Graph Export

The graph export module (src/export/graph.py) converts each generated grid into an undirected graph for consumption by external graph-based planners:

• every free cell becomes a graph node;
• every valid 4-neighbour transition (up, down, left, right) between two free cells becomes an undirected edge;
• node IDs use the format row_col, e.g. 12_35 is the cell at row 12, column 35;
• every edge has cost = 1;
• diagonal movement is not included.

Four files describe the graph:

• graph.json — graph only: metadata (width, height, movement: "4-neighborhood", directed: false), a list of nodes (each with id, row, col, x, y), a list of edges (each with from, to, cost), and an adjacency map.
• graph_instance.json — combined {graph, scenario, tasks}. This is the primary file for external modules, because it contains both the topology and the planning instance in one place.
• nodes.csv, edges.csv — tabular form of the node and edge lists, convenient for quick inspection, NetworkX import, or spreadsheet tooling.

Metrics

Metrics are written to metrics.json and combine three groups:

Grid metrics (from src/validation/):

• width, height, total_cells, free_cells, obstacle_cells;
• obstacle_density — fraction of cells that are obstacles;
• connectivity_ratio — fraction of free cells reachable by 4-BFS from one starting free cell (1.0 means the free space is one connected component).

Scenario metrics:

• scenario_type, num_agents, num_tasks;
• agent_goal_min_distance, agent_goal_max_distance, agent_goal_avg_distance — Manhattan distances between start and goal across agents (MAPF only; null for MAPD where agents do not carry a fixed goal);
• task_min_distance, task_max_distance, task_avg_distance — Manhattan pickup→dropoff distances (MAPD only);
• complexity_score — heuristic indicator combining obstacle density, agent count, task count, and a connectivity penalty. It is not a formal solver-difficulty measure; treat it as a quick ranking signal between cases.

Graph metrics (from src/export/graph.py):

• graph_nodes, graph_edges;
• graph_avg_degree;
• graph_components — number of connected components in the free-space graph;
• graph_largest_component_ratio — size of the largest component divided by total node count.

Computer Vision Integration

The generator can be used together with a computer vision module that processes map images or occupancy-style representations. In this workflow, the generated map.png or preview.png files serve as visual inputs, while the underlying grid and graph files provide a structured reference representation for validation and comparison.

A practical pipeline looks like this: a CV component produces a binary occupancy mask from an image (real or simulated); that mask is then passed to the same graph export module (src/export/graph.py) used for procedurally generated maps, producing a node/edge graph with the same row_col ID convention and 4-neighbour edge model. This connects perception-derived maps with the tool's planning-oriented representation and makes the two interchangeable from the planner's point of view.

The opposite direction is also useful for benchmarking the CV side: a generated map.png (with the ground-truth grid available alongside it) can be fed to a CV module, and the recovered occupancy can be compared cell-by-cell against the ground truth.

This integration is a usage scenario, not a built-in pipeline. The repository does not ship a CV module and does not include a live connection to a perception system; it provides the structured benchmark side of the workflow.

Limitations

• The project does not include a MAPF/MAPD solver — only benchmark generation.
• Graph export uses 4-neighbour movement only; diagonals are not modelled.
• All graph edges have unit cost; weighted or terrain-dependent costs are not supported.
• Maps are 2D grids; there is no physics simulation, no continuous geometry, and no 3D modelling.
• Isaac Sim, ROS2, and Nav2 integration are outside the current implementation and discussed in the coursework report as directions for future work.
• Computer vision integration is limited to the map/occupancy representation workflow described above; the project is not a complete robotics or perception pipeline.
• src/scenarios/single_nav.py is present but empty and is not used by the current demo pipeline.

Reproducibility

Generation is fully seed-based. Given the same config file and the same --seed value, the generator produces identical maps, identical scenarios, identical metrics, and identical graph exports across runs and machines (subject to the same Python and NumPy versions).

Every output directory contains a config_used.yaml that records the exact configuration and the resolved seed, so any case can be regenerated from its own output folder.

Repository Notes

The .gitignore excludes local artefacts that should not be committed:

.venv/
__pycache__/
*.pyc
.DS_Store
outputs/
*.zip
*.docx
*.pdf
*.tmp

Note that outputs/ is ignored by default. The four demo case directories under outputs/ are committed in the current repository because they are part of the coursework demonstration; in normal development the outputs/ folder should remain untracked, and demo outputs should either be force-added explicitly (git add -f) or moved to a dedicated demo_outputs/ directory if they need to be versioned.