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

Jiaqi Tan; Yudong Luo; Sophia Huang; Yifan Yang; Hang Ma

cs.ROMar 27, 2026

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

Authors: Jiaqi Tan, Yudong Luo, Sophia Huang, Yifan Yang, Hang Ma

Organizations: School of Computing Science, Simon Fraser University, Burnaby, BC V5A 1S6, Canada · HEC Montréal, Montréal, QC H3T 2A7, Canada · Purdue University, West Lafayette, IN 47907 USA

Abstract

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.

Figures & tables

Fig. 1: Illustration of warehouse robots rearranging shelves [ 5 ] .

Fig. 2: CREST running example with two agents (

a_{1}

a_{2}

) and four shelves (

s_{1}

–

s_{4}

) . (a) shows the initial

\mathcal{T}

and

D

t=0

. Each shelf trajectory in

\mathcal{T}

is an ordered waypoint sequence, and

D

is a precedence graph defined over these waypoints; solid arrows denote Type-1 arcs and dashed arrows denote Type-2 arcs. (b) shows the simplified

\mathcal{T}

and

D

t=0

, obtained by merging consecutive waypoints for each shelf. (c) shows the final execution produced by CREST from

t=0

t=7

Fig. 3: STR example with one agent (

a_{1}

) and three shelves (

s_{1}

s_{2}

s_{3}

). With

a_{1}

assigned to

s_{3}

, the baseline detours to avoid

s_{1}

and

s_{2}

(left). STR replans the remaining path of

s_{3}

to shorten the unexecuted segment and avoid being blocked at

(3,1)

(right).

Fig. 4: DS and GTR example with one agent (

a_{1}

) and two shelves (

s_{1}

and

s_{2}

). Agent

a_{1}

carries

s_{2}

first. When

s_{2}

is constrained by

s_{1}

at location

(2,3)

, DS reverses the corresponding Type-2 dependencies to allow

s_{2}

to proceed first, whereas GTR replans the unexecuted portion of

s_{1}

’s path to free the route for

s_{2}

Fig. 5: Distributions of shelf pickup (top) and delivery (bottom) cells (brown) and agent initial cells (blue) across three layouts.

Map	Size	# Shelves ( $\frac{\text{\# Shelves}}{\text{\# Cells}}$ )	# Rearranged Shelves ( $\frac{\text{\# Rearranged Shelves}}{\text{\# Cells}}$ )
R2R -M	48 $\times$ 48	460 (20.0%)	230 (10.0%)
S2W -M	64 $\times$ 33	384 (18.2%)	384 (18.2%)
DnE -M	47 $\times$ 45	672 (31.7%)	403 (19.0%)
R2R -L	96 $\times$ 96	1,843 (20.0%)	921 (10.0%)
S2W -L	128 $\times$ 111	2,816 (19.8%)	2,816 (19.8%)
DnE -L	128 $\times$ 111	2,816 (19.8%)	2,816 (19.8%)

TABLE I: Layout Specifications.

Map	Method	Norm. Cost	Norm. Mksp	# Switch/Shelf	Time (s)
R2R -M $N$ =32	Baseline	7,575.40	316.75	1.48	9.47
R2R -M $N$ =32	CREST	5,863.36 (-22.6%)	287.51 (-9.2%)	1.27 (-14.2%)	6.88
S2W -M $N$ =32	Baseline	17,662.92	648.46	5.37	21.74
S2W -M $N$ =32	CREST	13,920.84 (-21.2%)	515.11 (-20.6%)	5.00 (-6.8%)	15.75
DnE -M $N$ =32	Baseline	14,504.16	547.56	3.13	24.64
DnE -M $N$ =32	CREST	11,820.40 (-18.5%)	465.76 (-14.9%)	2.84 (-9.1%)	22.32

TABLE II: Results for the MAPF-DECOMP baseline and CREST without overhead. Percentages indicate reductions relative to the baseline. ‘

N

’ denotes the number of agents.

Fig. 6: Percentage reduction over baseline achieved by CREST and its variants on three layouts, measured by normalized sum of costs, normalized makespan, and number of lift/place transitions per shelf.

Fig. 7: Cost breakdown for three methods on medium layouts.

Map	W/O Overhead			W/ Overhead ( $\Delta$ = 1)
Map	/Shelf	/Shelf Step	/Agent Step	/Shelf	/Shelf Step	/Agent Step
R2R -M	0.0299	0.0009	0.0005	0.0307	0.0009	0.0004
S2W -M	0.0410	0.0011	0.0006	0.0398	0.0011	0.0005
DnE -M	0.0554	0.0015	0.0008	0.0556	0.0015	0.0007
R2R -L	0.3777	0.0055	0.0030	0.3538	0.0052	0.0024
S2W -L	2.9661	0.0294	0.0132	3.2029	0.0317	0.0124

TABLE III: Runtime (s) per shelf, shelf step, and agent step.

Multi-Robot Systems

Multi-robot systems coordinate teams of robots to plan, perceive, communicate, and act together in shared tasks and environments.

See all 205 papers

Dynamic Haven Selection for Multi-Agent Pickup and Delivery in Constrained Warehouses
Aug 27, 2026Taisei Hirayama, Kohei Yoshida, Hiroki Sakaji +1Multi-Agent Planning Multi-Agent Path Finding
Hokkaido University, Sapporo 060-0808, Japan · Toyota Industries Corporation, Aichi 474-8601, Japan
Many-to-Many Multi-Agent Pickup and Delivery
May 8, 2026Ethan Schneider, Jingkai Chen, Tianyi Gu +3Multi-Agent System Optimization Multi-Robot Task Allocation
Institute of Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA · Symbotic Inc., Wilmington, MA 01887, USA · Northeastern University, Boston, MA 02115, USA
Dynamic Multi-Agent Pickup and Delivery in Robotic Cellular Warehousing Systems
Jun 4, 2026Cheng Ren, Ming Li, Xinping Guan +1Multi-Agent Coordination Robotics
Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hong Kong, China · School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, Shanghai, China

Aug 27, 2026J/K move · Enter open · S save

Dynamic Haven Selection for Multi-Agent Pickup and Delivery in Constrained Warehouses

Taisei Hirayama, Kohei Yoshida, Hiroki Sakaji, Itsuki Noda

Hokkaido University, Sapporo 060-0808, Japan · Toyota Industries Corporation, Aichi 474-8601, Japan

Multi-Agent Planning Multi-Agent Path Finding Constrained Motion Planning Multi-Robot Task Allocation

Open paper AskPDF arXiv

Space-efficient warehouse layouts often contain single-agent-width aisles and dead-end workstations where robots have few places to wait without blocking others. In Multi-Agent Pickup and Delivery (MAPD) on such constrained layouts, robots must accept online pickup-delivery tasks while preserving protected waiting locations called Havens. The Safe HAven Retreat Planner (SHARP) introduced a mechanism that extends each committed task path with a validated retreat to the agent's dedicated initial Haven, but fixed-Haven commitments can send agents toward distant Havens after deliveries. We present A-sharp (Adaptive SHARP), which changes an agent's retreat target at task assignment time. A naive switch can cause two agents to rely on the same waiting location or let another committed path pass through a location that is still occupied or reserved. A-sharp prevents these failures with an availability test for candidate Havens and a pending-release rule that keeps the previous Haven protected until the agent departs. Under explicit Haven-structure and Safe Interval Path Planning (SIPP) assumptions, we prove invariant preservation and finite-release completeness: every task in any finite release sequence is delivered in finite time. Across 72,000 runs on 14,400 paired map-agent-count-rate-seed cases over four maps, both SHARP and A-sharp complete their respective 14,400 runs. For makespan (final delivery time), a prespecified paired comparison with Holm correction over all 138 configurations with more Havens than agents finds A-sharp significantly better in 107 configurations and never significantly worse than SHARP; on the tested tree map, the median reduction is 16.7%.

Abstract

Multi-Robot Systems

Explore similar work

Dynamic Haven Selection for Multi-Agent Pickup and Delivery in Constrained Warehouses

Many-to-Many Multi-Agent Pickup and Delivery

Dynamic Multi-Agent Pickup and Delivery in Robotic Cellular Warehousing Systems