# CREST: Constraint-Release Execution for Multi-Robot Warehouse Shelf Rearrangement

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 28 references that are in the map.
- First posted on arXiv 27 Mar 2026.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [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)
- [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)
- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [Fabrica: Dual-Arm Assembly of General Multi-Part Objects via Integrated Planning and Learning](https://mlsanity.com/paper/2506.05168/) (2025)
- [A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph](https://mlsanity.com/paper/2010.05254/) (2020)
- [Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution](https://mlsanity.com/paper/2401.00315/) (2023)
- [Speedup Techniques for Switchable Temporal Plan Graph Optimization](https://mlsanity.com/paper/2412.15908/) (2024)
- [Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses](https://mlsanity.com/paper/2304.14309/) (2023)
- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [APEX-MR: Multi-Robot Asynchronous Planning and Execution for Cooperative Assembly](https://mlsanity.com/paper/2503.15836/) (2025)
- [MARPF: Multi-Agent and Multi-Rack Path Finding](https://mlsanity.com/paper/2403.12376/) (2024)

## Abstract (arXiv)

Double-Deck Multi-Agent Pickup and Delivery (DD-MAPD) models the multi-robot shelf rearrangement problem in automated warehouses. MAPF-DECOMP is a recent framework that first computes collision-free shelf trajectories with a MAPF solver and then assigns agents to execute them. While efficient, it enforces strict trajectory dependencies, often leading to poor execution quality due to idle agents and unnecessary shelf switching. We introduce CREST, a new execution framework that achieves more continuous shelf carrying by proactively releasing trajectory constraints during execution. Experiments on diverse warehouse layouts show that CREST consistently outperforms MAPF-DECOMP, reducing metrics related to agent travel, makespan, and shelf switching by up to 40.5%, 33.3%, and 44.4%, respectively, with even greater benefits under lift/place overhead. These results underscore the importance of execution-aware constraint release for scalable warehouse rearrangement. Code and data are available at https://github.com/ChristinaTan0704/CREST.