# Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 7 Aug 2026.

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

- [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)
- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [Refined Hardness of Distance-Optimal Multi-Agent Path Finding](https://mlsanity.com/paper/2203.07416/) (2022)
- [Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses](https://mlsanity.com/paper/2304.14309/) (2023)
- [Reinforcement learning for multi-item retrieval in the puzzle-based storage system](https://mlsanity.com/paper/2202.03424/) (2022)
- [MARPF: Multi-Agent and Multi-Rack Path Finding](https://mlsanity.com/paper/2403.12376/) (2024)
- [Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Unassigned Agents](https://mlsanity.com/paper/2509.01022/) (2025)
- [Robust Out-of-Order Retrieval for Grid-Based Storage at Maximum Capacity](https://mlsanity.com/paper/2601.19144/) (2026)
- [Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids](https://mlsanity.com/paper/2305.16303/) (2023)
- [Fully Packed and Ready to Go: High-Density, Rearrangement-Free, Grid-Based Storage and Retrieval](https://mlsanity.com/paper/2505.22497/) (2025)

## Abstract (arXiv)

Automated warehouses face a fundamental trade-off between maximizing storage density and achieving high retrieval throughput. While puzzle-based storage (PBS) architectures increase capacity by eliminating aisles, coordinating multiple robots in these high-density spaces is computationally challenging. This paper formalizes the challenge through a novel multi-robot problem formulation for ordered storage and retrieval: We consider rectangular 2D grids, where uniform-sized loads are first stored, up to full capacity, and subsequently retrieved according to prescribed arrival and departure sequences. The main contribution of this work is an online prioritized multi-agent path planning algorithm for this problem. The algorithm builds on prior work that constructs arrangements supporting sequential storage and retrieval, i.e., of one load at a time, without relocating loads. By exploiting the structural invariants of such arrangements, we achieve the scalability of decoupled planning while guaranteeing complete, deadlock-free parallel execution even at full storage density. Experiments demonstrate that the algorithm achieves near-linear improvement in makespan with respect to the number of robots, up to C robots, where C is the width of the grid's open side. Furthermore, the algorithm supports robust storage arrangements that accommodate bounded uncertainty in the departure sequence, with negligible impact on execution makespan.