Warehouse MAS

Getting Started

Overview Installation Quick Start

Core Concepts

Problem Scope Architecture Algorithms

Features

Path Planning Symmetry Reduction Verification Refinement

Usage

Commands Configuration Examples

Resources

Documentation Library Limitations
Documentation / Home

Warehouse Multi-Agent System

Deterministic multi-agent coordination with cooperative space-time planning, quotient verification, and iterative safety refinement

Cooperative Space-Time A* Hungarian Matching Symmetry Reduction Formal Verification Python 3.8+

Overview

A deterministic multi-agent warehouse coordination system that combines path planning, symmetry reduction, and formal verification to ensure collision-free operation.

Key Features

  • Cooperative Space-Time A*: Plans over (x, y, direction, time) with vertex and edge conflict checks
  • Global Task Matching: Hungarian minimum-cost assignment for robot-to-shelf and delivery-goal allocation
  • Rolling Reservations: Short reservation window with conservative unknown-agent occupancy blocking
  • Deadlock Recovery: Idle-aware escape actions to break long stalls safely
  • Symmetry Reduction: Orbit-based state space reduction for scalable verification
  • Bounded Verification: Formal safety checks on quotient models with delta-q tracking
  • Constraint Refinement: Iterative constraint extraction from counterexamples

Real-time visualization of multi-agent coordination

Problem Scope

Multi-agent warehouse coordination must satisfy throughput and safety constraints under dense traffic. This project models agents on a grid with pickup/drop tasks and enforces collision-free behavior through deterministic planning and bounded verification.

Safety Objectives

  • Maintain minimum inter-agent separation at all times
  • Prevent vertex and edge collisions across finite horizon
  • Complete shelf pickup and delivery tasks efficiently
  • Ensure deterministic and reproducible behavior

Installation

Prerequisites: Python 3.8 or higher, pip, virtual environment support

Step 1: Clone the Repository

git clone https://github.com/sunday-pichai/multi-agent-system.git
cd multi-agent-system

Step 2: Create Virtual Environment

python -m venv .venv
.venv\Scripts\activate  # Windows
source .venv/bin/activate  # Linux/Mac

Step 3: Install Dependencies

pip install -r requirements.txt

Quick Start

Get started with the interactive visualization in seconds:

python main.py --mode interactive --render
Tip: For faster runs on large layouts, reduce planning.horizon, planning.reservation_window, or agent/shelf counts in config.yaml.

Commands

Interactive Mode

Real-time visualization using pygame with agent trajectories, pickups, and collision avoidance:

python main.py --mode interactive --render

Simulation Mode

Run batch simulations for multiple episodes:

python main.py --mode simulate --episodes 8 --steps-per-episode 200

Evaluation Mode

Evaluate trained policies across test scenarios:

python main.py --mode eval --eval-episodes 3 --steps-per-episode 150

Testing

Run the full test suite:

python tests/run_tests.py

System Architecture

Agents operate on a discrete grid with pickup/drop objectives. Planning is deterministic and conflict-aware: global task matching, cooperative space-time A*, rolling reservations, and deadlock recovery. Safety is checked via bounded verification on a symmetry-reduced quotient model.

Planning

Agents plan sequentially in time-expanded space with vertex/edge reservations, conservative unknown-agent occupancy, and anti-stall escape actions.

Assignment

Hungarian minimum-cost matching assigns robots to requested shelves and allocates delivery goals to reduce congestion.

Symmetry

Agents are partitioned into role orbits. Canonicalization maps symmetric permutations to a single quotient state.

Verification

Bounded verification checks collisions and minimum separation on the quotient; unsafe traces generate counterexamples.

Refinement

Counterexamples are compiled into hard constraints, steering the planner away from unsafe transitions.

Algorithm Details

Path Planning (Cooperative Space-Time A*)

Each agent plans in a time-expanded grid while respecting reservations from already-planned agents. The planner also blocks likely occupied cells for not-yet-planned agents, uses rolling reservation windows, and applies idle-aware escape actions to prevent deadlock. 

Planner core:
- cooperative A* on (x, y, dir, t)
- vertex + edge reservations
- conservative unknown-agent occupancy
- rolling reservation window (WHCA*-style)
- idle-aware escape action

Interactive Demo: A* Pathfinding

A*: frontier expansion toward the goal with space-time constraints

Symmetry Reduction

Agents are grouped into role orbits (idle vs carrying requested shelf). Canonicalization maps symmetric permutations to a single quotient state, dramatically shrinking the state space for verification. 

Orbits:
- group agents by role (idle / carrying)
- encode each agent as tuple (x, y, dir, role)
- sort tuples within each orbit
- identical canonical key = same quotient state

Interactive Demo: Symmetry Reduction

Symmetry Reduction: step-by-step orbit detection and canonicalization

Bounded Verification

Bounded verification checks collisions and minimum separation over the quotient. If unsafe, it returns a counterexample trace. 

Verify:
- run trials on quotient
- track collisions
- compute safety margin (delta_q)

Interactive Demo: Verification Process

Verification: checking safety constraints

Constraint Refinement

Counterexamples are converted to hard constraints. The planner avoids these moves and verification repeats. 

Refine:
- extract conflict from trace
- add constraint to planner
- re-verify

Algorithm Flow Visualization

Plan -> Symmetry -> Verify -> Refine

Configuration Reference

Configure grid size, agent count, planning horizon, and verification budget in config.yaml.

Planning Configuration

planning:
  horizon: 30
  astar_max_nodes: 3500
  idle_limit: 4
  reservation_window: 8
  unplanned_hold_steps: 2
  escape_idle_steps: 6

Verification Configuration

verification:
  horizon: 30
  trials: 20
  min_separation: 1

Environment Configuration

grid:
  width: 16
  height: 16

agents:
  num_agents: 6
  num_shelves: 8

Usage Examples

Run Verification with Refinement

python main.py --verify-refine --verify-horizon 30 --verify-trials 20

Expected Output

Verification passed at iteration 2 (delta_q=0.50)
Average collision rate (per step): 0.0000
Final constraints: 3 positions, 1 edges

Interactive Mode with Custom Grid

Edit config.yaml to set custom grid parameters, then run:

python main.py --mode interactive --render

Documentation Library

Complete Markdown documentation set for this project:

Limitations

Current Limitations

  • Verification is bounded in time and trials
  • Refinement relies on extracted counterexamples
  • May require multiple iterations to converge for dense layouts
  • Performance degrades with very large grids (>20x20)

Recommended Usage

Use smaller grids or lower verification budgets for quick iteration, then increase budgets for stronger assurance on final configurations.