Many-to-Many Multi-Agent Pickup and Delivery
For warehouse logistics, this work addresses a more realistic many-to-many task assignment problem, offering significant throughput improvements over existing one-to-one approaches.
The paper tackles the many-to-many Multi-Agent Pickup and Delivery (MAPD) problem, where items can be picked up or delivered at multiple locations. The proposed M2M algorithm, with variants minimizing task durations or incorporating SKU distribution, consistently matches or outperforms prior state-of-the-art, completing up to 22,000 more tasks on average in simulated 8-hour warehouse operations.
Multi-robot systems in automated warehouses must manage continuous streams of pickup-and-delivery tasks while ensuring efficiency and safety. Prior work on Multi-Agent Pickup-and-Delivery (MAPD) has largely focused on the one-to-one variant, where each task has a fixed pickup and delivery location. In contrast, real warehouses often present many-to-many MAPD scenarios, where items, tracked by stock keeping unit (SKU) identifiers, can be retrieved from or stored at multiple locations, resulting in an NP-hard four-dimensional assignment problem. To solve the many-to-many MAPD problem, we contribute our algorithm: Many-to-Many Multi-Agent Pickup and Delivery (M2M). We experiment with two variants of our algorithm: one that minimizes estimated task durations (M2M), and one which incorporates SKU distribution into the objective function (M2M-wSKU). Simulation results over 8-hour warehouse operations show that our method consistently matches or outperforms prior state of the art, with M2M completing up to 22,000 more tasks on average across different environments and warehouse inventory densities.