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

Limitations
Documentation / Home

Warehouse Multi-Agent System

Deterministic multi-agent coordination with formal verification, symmetry reduction, and constraint-based planning

CBS + A* 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 A* + CBS: Time-expanded pathfinding with conflict resolution
  • Symmetry Reduction: Orbit-based state space reduction for scalable verification
  • Bounded Verification: Formal safety checks on quotient models
  • 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 better performance on large grids, reduce the grid size or time steps 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 (Cooperative A* with CBS conflict resolution). Safety is checked via bounded verification on a symmetry-reduced quotient model.

Planning

Cooperative A* generates time-expanded paths. CBS resolves conflicts by adding constraints and replanning affected agents.

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 (CBS + Cooperative A*)

Each agent plans a time-expanded path using Cooperative A*. CBS resolves conflicts by adding constraints and replanning until paths are consistent. 

Cooperative A*:
- time-expanded grid
- reservation table
- avoid occupied cells

CBS:
- detect conflicts
- add constraints
- replan for agent

Interactive Demo: A* Pathfinding

A*: expanding frontier toward the goal

Symmetry Reduction

Agents are grouped into role orbits (idle vs carrying requested shelf). Canonicalization maps symmetric permutations to a single quotient state. 

Orbits:
- group agents by role
- canonicalize positions  
- shrink state space

Before vs After Symmetry Reduction

Role-orbit grouping collapses symmetric permutations. In this project, roles are derived from carrying status (idle, carrying requested, carrying non-requested).

Aspect
Full System
Symmetry-Reduced (Quotient)
Agents represented
All N agents explicitly modeled
k role orbits (k ≤ 3 in this project)
State size
O(N · d) full agent state
O(k · d) representative state
Verification cost
Cver(n) over full dimension n = N · d
Cver(m) with m ≪ n
Counterexamples
Full traces over all agents
Lifted from quotient representatives
Memory
O(n) full-state storage
O(m) reduced storage

Interactive Demo: Symmetry Reduction

Symmetry: grouping agents into orbits

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: 40
  use_cbs: true
  cbs_max_nodes: 200
  astar_max_nodes: 6000
  idle_limit: 6

Verification Configuration

verification:
  horizon: 30
  trials: 20
  min_separation: 1

Environment Configuration

environment:
  grid_width: 16
  grid_height: 16
  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

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.