Many-To-Many Multi-Agent Pickup and Delivery
Ethan Schneider, Jingkai Chen, Tianyi Gu, Kunlei Lian, Seth Hutchinson, Sonia Chernova
AI summary
Problem
Existing multi-agent pickup-and-delivery methods assume fixed pickup and delivery locations, failing to account for real-world warehouse inventory where items can be retrieved from or stored at multiple locations, which leads to inefficient allocations and lower system performance.
Approach
The authors introduce M2M, an algorithm that decomposes the many-to-many task allocation into a computationally efficient four-dimensional assignment problem, iteratively optimizes it using Large Neighborhood Search, and generates collision-free paths with PBS, alongside a variant that optimizes for future SKU distribution.
Key results
- Introduces M2M algorithm for many-to-many MAPD task allocation
- Develops M2M-wSKU variant incorporating SKU distribution into cost function
- Achieves up to 38.8% higher task throughput than state-of-the-art LNS-PBS baseline
- Completes up to 22,000 additional tasks over 8-hour warehouse simulations
Why it matters
Provides a scalable, high-throughput task allocation framework for automated warehouses that explicitly handles multi-location inventory, directly benefiting logistics and robotics researchers and practitioners.
Abstract
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 prob- lem, 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.