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

arXiv: https://arxiv.org/abs/2304.14309 · HTML: https://mlsanity.com/paper/2304.14309/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 27 Apr 2023.

## Builds on (most cited first, 9 of 9)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search](https://mlsanity.com/paper/2103.07116/) (2021)
- [Multi-Agent Path Finding with Delay Probabilities](https://mlsanity.com/paper/1612.05309/) (2016)
- [Intractability of Optimal Multi-Robot Path Planning on Planar Graphs](https://mlsanity.com/paper/1504.02072/) (2015)
- [Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning](https://mlsanity.com/paper/2006.08845/) (2020)
- [Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering](https://mlsanity.com/paper/2009.05161/) (2020)

## Built on by (most cited first, 5 of 5)

- [Constrained Environment Optimization for Prioritized Multi-Agent Navigation](https://mlsanity.com/paper/2305.11260/) (2023)
- [Foundation Models to the Rescue: Deadlock Resolution in Connected Multi-Robot Systems](https://mlsanity.com/paper/2404.06413/) (2024)
- [Using Protected Attributes to Consider Fairness in Multi-Agent Systems](https://mlsanity.com/paper/2410.12889/) (2024)
- [CREST: Constraint-Release Execution for Multi-Robot Warehouse Shelf Rearrangement](https://mlsanity.com/paper/2603.28803/) (2026)
- [Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity](https://mlsanity.com/paper/2608.07734/) (2026)

## Abstract (arXiv)

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.