Dynamic Shelf Arrangement and Task Assignment with Stable Matching for Multi-Agent Pickup and Delivery with Multi-Item Packing Problem

Abstract

The multi-agent pickup and delivery (MAPD) problem requires not only planning collision-free paths for carrier agents to carry items while avoiding obstacles but also optimizing task allocation among agents, and it has become a key problem in automated warehouse environments. Most existing studies rely on simplified models that fail to capture the constraints of real-world warehousing. We investigate a more realistic online variant, MAPD with multi-item packing problem (MAPD-MP), where agents process picking lists of multiple tasks, each requiring an agent to carry a shelf containing items to a picking station and return it to the original location. We incorporate the fact that each shelf has a distinct probability of being requested. To solve this problem, we integrated conventional planning methods with three components: shelf arrangement optimization, which optimizes shelf arrangement based on probabilistic demand; task assignment using the Gale–Shapley algorithm, which uses stable matching for task allocation; and holding-node integration, in which shelves are temporarily placed at holding nodes for subsequent tasks. Our experiments demonstrate that our method improves cooperative efficiency in large-scale agent teams and increases the picking-list processing throughput.