# Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses

Source: [Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses](<https://www.sota2.com/research/paper/68fa6f261e209131cea44133>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-26T01:14:37.532Z

Authors: Baiyu Li, Hang Ma

Published: 2023-04-27T16:26:05.000Z

## Abstract

We introduce a new problem formulation, Double-Deck Multi-Agent Pickup and Delivery (DD-MAPD), which models the multi-robot shelf rearrangement problem in automated warehouses. DD-MAPD extends both Multi-Agent Pickup and Delivery (MAPD) and Multi-Agent Path Finding (MAPF) by allowing agents to move beneath shelves or lift and deliver a shelf to an arbitrary location, thereby changing the warehouse layout. We show that solving DD-MAPD is NP-hard. To tackle DD-MAPD, we propose MAPF-DECOMP, an algorithmic framework that decomposes a DD-MAPD instance into a MAPF instance for coordinating shelf trajectories and a subsequent MAPD instance with task dependencies for computing paths for agents. We also present an optimization technique to improve the performance of MAPF-DECOMP and demonstrate how to make MAPF-DECOMP complete for well-formed DD-MAPD instances, a realistic subclass of DD-MAPD instances. Our experimental results demonstrate the efficiency and effectiveness of MAPF-DECOMP, with the ability to compute high-quality solutions for large-scale instances with over one thousand shelves and hundreds of agents in just minutes of runtime.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Multi-Agent Pickup and Delivery (MAPD) on R2R Warehouse Layout N=32](<https://www.sota2.com/research/sota/multi-agent-pickup-and-delivery-mapd-on-r2r-warehouse-layout-n-32.md>): Multi-Agent Pickup and Delivery (MAPD); R2R Warehouse Layout N=32; Normalized Cost: 7575.4.

- [Multi-Agent Pickup and Delivery (MAPD) on R2R Warehouse Layout (N=100)](<https://www.sota2.com/research/sota/multi-agent-pickup-and-delivery-mapd-on-r2r-warehouse-layout-n-100.md>): Multi-Agent Pickup and Delivery (MAPD); R2R Warehouse Layout (N=100); Normalized Cost: 72018.48.

- [Multi-Agent Pickup and Delivery (MAPD) on S2W Warehouse Layout N=32](<https://www.sota2.com/research/sota/multi-agent-pickup-and-delivery-mapd-on-s2w-warehouse-layout-n-32.md>): Multi-Agent Pickup and Delivery (MAPD); S2W Warehouse Layout N=32; Normalized Cost: 17662.92.

- [Multi-Agent Pickup and Delivery (MAPD) on S2W Warehouse Layout N=100](<https://www.sota2.com/research/sota/multi-agent-pickup-and-delivery-mapd-on-s2w-warehouse-layout-n-100.md>): Multi-Agent Pickup and Delivery (MAPD); S2W Warehouse Layout N=100; Normalized Cost: 461249.72.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2304.14309>)

[PDF](<https://arxiv.org/pdf/2304.14309.pdf>)
