MAPF Project - Multi-Agent Pathfinding

Project Overview

This project implements and compares two Multi-Agent Pathfinding (MAPF) algorithms:

1. Conflict-Based Search (CBS) - Optimal but slower
2. Prioritized Planning - Fast but incomplete

Both algorithms use Space-Time A* as the low-level planner with Manhattan distance heuristic, and handle both vertex and edge conflicts.

Project Structure

final_proj/
├── cbs.py                      # Conflict-Based Search implementation
├── prioritized.py              # Prioritized Planning implementation
├── single_agent_planner.py     # Space-Time A* and helper functions
├── test_solvers.py             # Test suite with validation
├── simple_visualize.py         # Matplotlib visualization
├── planviz_export.py           # PlanViz format exporter
├── planviz_output/             # Generated visualizations and exports
└── MAPF/                       # Reference implementation (nicofretti/MAPF)

Key Features

Implemented Algorithms

Conflict-Based Search (CBS)

• ✅ Optimal (finds minimum sum-of-costs solution)
• ✅ Complete (finds solution if one exists)
• ✅ Handles vertex and edge conflicts
• ✅ Supports Weighted A* for faster but sub-optimal solutions
• ⚠️ Can be slow with many agents or conflicts

Prioritized Planning

• ✅ Very fast (microseconds for small problems)
• ✅ Simple and efficient
• ✅ Handles vertex and edge conflicts
• ✅ Supports Weighted A*
• ⚠️ Incomplete (may fail even when solutions exist)
• ⚠️ Solution quality depends on agent ordering

Space-Time A*

• Extends standard A* into space-time domain
• States: (row, col, time)
• Actions: Move (up/down/left/right) + Wait
• Constraint checking for vertex and edge conflicts
• Supports weighted heuristic (Weighted A*)

Running Tests

Basic Test Suite

Run all test cases with visualization:

python test_solvers.py

This will:

1. Run CBS and Prioritized Planning on multiple test scenarios
2. Validate solutions for conflicts
3. Generate visualizations in planviz_output/
4. Export results in JSON format

Viewing Visualizations

Generated PNG visualizations show:

• Black squares: Obstacles
• Colored circles: Agent start positions (with agent IDs)
• Colored diamonds: Agent goal positions
• Colored lines: Agent paths over time

Check the planviz_output/ folder for visualization files.

Test Results Summary

Test 1: Simple 5×5 Grid - Two Agents Swapping Corners

• Prioritized Planning: ✅ Success, 0.0002s, cost=10
• CBS: ✅ Success, 0.0005s, cost=10, 5 nodes expanded
• Both found optimal solutions

Test 2: Corridor - Three Agents in Tight Space

• Prioritized Planning: ❌ Failed (no solution for agent 2)
• CBS: ✅ Success, 0.10s, cost=21, 427 nodes expanded
• Demonstrates Prioritized Planning's incompleteness

Test 3: Open Space with Obstacles - Three Agents

• Prioritized Planning: ✅ Success, 0.0003s, cost=19
• CBS: ✅ Success, 0.0004s, cost=19, 2 nodes expanded
• Both found optimal solutions quickly

Key Findings

1. Prioritized Planning is much faster but can fail when agent ordering matters
2. CBS is guaranteed to find solutions but requires more computation
3. Both algorithms successfully handle:
   • Vertex conflicts (same location, same time)
   • Edge conflicts (agents swapping positions)
   • Wait actions (agents waiting in place)

Implementation Details

Constraint Format

Vertex Constraint:

{
    'agent': agent_id,
    'loc': [(row, col)],
    'timestep': time,
    'final': True/False  # If True, blocks all future times
}

Edge Constraint:

{
    'agent': agent_id,
    'loc': [(from_row, from_col), (to_row, to_col)],
    'timestep': time,
    'final': False
}

Path Format

Paths are lists of (row, col) tuples where index = timestep:

path = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
# Agent at (0,0) at t=0, (0,1) at t=1, etc.

Conflict Detection

The validator checks for:

• Vertex conflicts: Two agents at same (row, col) at same time
• Edge conflicts: Two agents swapping positions between timesteps

Next Steps

1. Experiments: Build pipeline to systematically compare algorithms across:

   • Different grid sizes (10×10, 20×20, 30×30)
   • Different obstacle densities (10%, 20%, 30%)
   • Different agent counts (2, 4, 8, 12)

2. Metrics Collection: Track and compare:

   • Success rate
   • Runtime
   • Sum of costs
   • Makespan
   • Node expansions

3. Visualization:

   • PlanViz integration (format compatibility needs work)
   • Animated matplotlib visualizations
   • Result plots and charts

4. Extensions (optional):

   • Weighted A* experiments
   • Different priority orderings for Prioritized Planning
   • Larger test scenarios

References

• nicofretti/MAPF: Reference implementation used as basis
• CBS Paper: Sharon et al., "Conflict-based search for optimal multi-agent pathfinding"
• Prioritized Planning: Silver, "Cooperative pathfinding"
• PlanViz: MAPF Competition visualization tool

Credits

• CBS implementation adapted from nicofretti/MAPF
• Space-Time A* implementation adapted from nicofretti/MAPF
• Prioritized Planning implemented following the same architecture
• Weighted A* support added to both algorithms