Keywords
MAPF, CBS, PrioritizedPlanning, MicroTimeStep

Technologies
Python

Multi-Agent Pathfinding (MAPF) is the problem of planning collision-free paths for multiple agents simultaneously, with applications in automated warehouses, airport vehicle coordination, and service robotics. Classical MAPF assumes all agents are identical (same size, same speed) which limits its applicability to real-world scenarios.

This project extends two well-known MAPF algorithms, Prioritized Planning and Conflict-Based Search, to support agents with heterogeneous speeds. The extensions handle constant and variable speeds, acceleration and deceleration dynamics, and an additional collision type called the following conflict. Time is discretized into micro time-steps, allowing faster agents to traverse cells at different speeds while preserving MAPF's synchronized discrete time structure. Experimental results show that variable-speed extensions incur moderately higher run-times and expanded search spaces compared with their fixed-speed counterparts, while producing solutions of comparable quality.