ArXiv

Many-to-Many Multi-Agent Pickup and Delivery

2026-05-08 · 15:03 UTC ·Ethan Schneider, Jingkai Chen, Tianyi Gu... ·1 min read

Authors: Ethan Schneider, Jingkai Chen, Tianyi Gu...
Categories: cs.RO, cs.MA
arXiv: https://arxiv.org/abs/2605.07835v1
PDF: https://arxiv.org/pdf/2605.07835v1

Brief

Many-to-Many Multi-Agent Pickup and Delivery (M2M) tackles warehouse many-to-many MAPD, where SKUs can be picked up from or delivered to multiple locations, yielding an NP-hard four-dimensional assignment. The authors propose two algorithmic variants (duration-minimizing M2M and SKU-aware M2M-wSKU) and report simulations over 8-hour operations showing up to 22,000 more tasks completed on average versus prior methods. Full text was not provided with the abstract.

Why it matters

The paper introduces M2M (Many-to-Many Multi-Agent Pickup and Delivery) with two variants—M2M (duration-minimizing) and M2M-wSKU (incorporates SKU distribution)—to solve the many-to-many MAPD problem formulated as an NP-hard four-dimensional assignment.

Key details

In simulation over 8-hour warehouse operations, M2M variants consistently match or outperform prior state of the art, with M2M completing up to 22,000 more tasks on average across different environments and inventory densities.

Source evidence

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 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.