Learning-guided Prioritized Planning for Lifelong Multi-Agent Path Finding in Warehouse Automation

Han Zheng; Yining Ma; Brandon Araki; Jingkai Chen; Cathy Wu

cs.AIMar 25, 2026

Learning-guided Prioritized Planning for Lifelong Multi-Agent Path Finding in Warehouse Automation

Authors: Han Zheng, Yining Ma, Brandon Araki, Jingkai Chen, Cathy Wu

Organizations: Massachusetts Institute of Technology, Cambridge, MA, USA · Symbotic, Wilmington, MA, USA

Abstract

Lifelong Multi-Agent Path Finding (MAPF) is critical for modern warehouse automation, which requires multiple robots to continuously navigate conflict-free paths to optimize the overall system throughput. However, the complexity of warehouse environments and the long-term dynamics of lifelong MAPF often demand costly adaptations to classical search-based solvers. While machine learning methods have been explored, their superiority over search-based methods remains inconclusive. In this paper, we introduce Reinforcement Learning (RL) guided Rolling Horizon Prioritized Planning (RL-RH-PP), the first framework integrating RL with search-based planning for lifelong MAPF. Specifically, we leverage classical Prioritized Planning (PP) as a backbone for its simplicity and flexibility in integrating with a learning-based priority assignment policy. By formulating dynamic priority assignment as a Partially Observable Markov Decision Process (POMDP), RL-RH-PP exploits the sequential decision-making nature of lifelong planning while delegating complex spatial-temporal interactions among agents to reinforcement learning. An attention-based neural network autoregressively decodes priority orders on-the-fly, enabling efficient sequential single-agent planning by the PP planner. Evaluations in realistic warehouse simulations show that RL-RH-PP achieves the highest total throughput among baselines and generalizes effectively across agent densities, planning horizons, and warehouse layouts. Our interpretive analyses reveal that RL-RH-PP proactively prioritizes congested agents and strategically redirects agents from congestion, easing traffic flow and boosting throughput. These findings highlight the potential of learning-guided approaches to augment traditional heuristics in modern warehouse automation.

Figures & tables

Figure 1. Robot fleet routing in a Symbotic warehouse (source: https://www.symbotic.com ).

Figure 2. The framework of our proposed RL-RH-PP. At each planning step, the RL policy encodes shortest path of each agents into agent embeddings and autoregressively decodes a total of $K$ priority orders. These orders are passed to the RH-PP planner to compute the conflict -free path, which is then executed in the warehouse simulation. Feedback rewards are used to update the policy. This closed-loop interaction enables the RL policy to learn to generate effective priority orders during training.

Figure 3. Our proposed encoding process for RL-RH-PP. Raw path inputs are indexed using position embeddings to construct a learnable representation for agent paths. Temporal and spatial attention mechanisms are applied in turn, along with normalization and residual modules, to extract and refine agent embeddings.

Figure 4. Our proposed decoding process for RL-RH-PP. Agent embeddings from the encoder are fed into a self-attention mechanism to generate a sampling distribution. To construct each priority order, agents are sampled and added one by one in an autoregressive manner until all $N$ agents are assigned. This process can be executed in parallel to generate a set of $K$ promising orders efficiently.

(18)

\theta_{z+1}=\arg\max_{\theta}\frac{1}{|\mathcal{D}|{T}}\sum_{{\tau}\in\mathcal{D}}\sum_{t=0}^{{T}}\left[\min\left(\frac{\pi_{\theta}(a_{t}|\boldsymbol{o}_{t})}{\pi_{\theta_{z}}(a_{t}|\boldsymbol{o}_{t})}\hat{A}(\boldsymbol{o}_{t},a_{t}),\,g(\epsilon,\hat{A}(\boldsymbol{o}_{t},a_{t}))\right)+\eta\mathcal{H}(\pi_{\theta}(\cdot|\boldsymbol{o}_{t}))\right]

Algorithm 1 Training for RL-RH-PP

Figure 5. Amazon fulfillment center dense map (obstacle density = 15.3 $\%$ ), modified from ( Li et al., 2021b ) .

Figure 6. Symbotic warehouse map (obstacle density = 56.6 $\%$ ).

Method		$N\!=\!80$		$N\!=\!100$		$N\!=\!120$
Method		TPA $\uparrow$	Time(s) $\downarrow$	TPA $\uparrow$	Time(s) $\downarrow$	TPA $\uparrow$	Time(s) $\downarrow$
Ama.	RH-PP ( $K=1$ )	28.77 $\pm$ 0.91	0.13	22.49 $\pm$ 1.29	0.19	16.34 $\pm$ 1.22	0.25
Ama.	RL-RH-PP ( $K=1$ )	30.55 $\pm$ 0.56	0.13	25.59 $\pm$ 1.01	0.20	22.69 $\pm$ 1.07	0.26
Sym.	RH-PP ( $K=1$ )	15.86 $\pm$ 0.69	0.11	10.85 $\pm$ 4.69	0.16	5.97 $\pm$ 0.95	0.21
Sym.	RL-RH-PP ( $K=1$ )	17.73 $\pm$ 0.22	0.12	13.29 $\pm$ 3.44	0.17	10.74 $\pm$ 3.21	0.22

Table 1. Evaluation comparison of RH-PP and RL-RH-PP with

K=1

, RL-RH-PP policy trained from scratch with

w=20

for each setting, TPA = throughput per agent, ‘Ama.’ for Amazon and ‘Sym.’ for Symbotic.

Figure 7. Ave. total throughput on held-out evaluation environments during training with

N=120

Method		$N\!=\!80$		$N\!=\!100$		$N\!=\!120$
Method		TPA $\uparrow$	Time(s) $\downarrow$	TPA $\uparrow$	Time(s) $\downarrow$	TPA $\uparrow$	Time(s) $\downarrow$
Ama.	RH-PP ( $K=5$ )	30.85 $\pm$ 0.52	0.65	25.92 $\pm$ 1.32	0.78	21.74 $\pm$ 2.25	0.95
Ama.	RL-RH-PP ( $K=5$ )	31.80 $\pm$ 0.46	0.65	28.84 $\pm$ 0.35	0.79	25.56 $\pm$ 0.55	0.96
Sym.	RH-PP ( $K=5$ )	16.51 $\pm$ 0.35	0.68	11.39 $\pm$ 4.22	0.80	8.21 $\pm$ 2.24	0.96
Sym.	RL-RH-PP ( $K=5$ )	18.38 $\pm$ 0.50	0.68	15.38 $\pm$ 1.85	0.82	11.31 $\pm$ 2.21	0.99

Table 2. Evaluation comparison of RH-PP and RL-RH-PP with

K=5

, RL-RH-PP policy trained from scratch with

w=20

for each setting, TPA = throughput per agent, ‘Ama.’ for Amazon and ‘Sym.’ for Symbotic.

Method		$N\!=\!80$		$N\!=\!100$		$N\!=\!120$
Method		TPA $\uparrow$	Time(s) $\downarrow$	TPA $\uparrow$	Time(s) $\downarrow$	TPA $\uparrow$	Time(s) $\downarrow$
Amazon	RH-CBS	4.94 $\pm$ 0.83	1.00	3.58 $\pm 0.52$	1.00	2.84 $\pm$ 0.29	1.00
	RH-PBS	22.13 $\pm$ 7.58	1.00	4.92 $\pm$ 0.65	1.00	3.37 $\pm$ 0.26	1.00
	PIBT	21.19 $\pm$ 0.58	0.16	18.62 $\pm$ 0.35	0.20	16.09 $\pm$ 0.48	0.27
	WPPL	29.70 $\pm$ 0.51	1.00	26.60 $\pm$ 0.48	1.00	23.59 $\pm$ 0.26	1.00
	RL-RH-PP (ours)	31.80 $\pm$ 0.46	0.65	28.84 $\pm$ 0.35	0.79	25.56 $\pm$ 0.55	0.96

Table 3. Evaluation comparison of RL-RH-PP to various baselines, RL-RH-PP policy trained from scratch with

w=20

for each setting. TPA = throughput per agent. Best is bolded ; second best is underlined .

Figure 8. Total throughput versus agent number

N

in zero-shot transfer evaluation at

w=20

. The base model (yellow star) is trained at

N=120

and

w=20

, and evaluated zero-shot at other

N

Figure 9. Total throughput versus planning horizon

w

in zero-shot transfer evaluation at

N=120

. The base model (yellow star) is trained at

N=120

and

w=20

, and evaluated zero-shot at other

w

Method		Total TP $\uparrow$	Optimal $(N,w)$
Amazon	RH-CBS	512 $\pm$ 83	(40,10)
	RH-PBS	2343 $\pm$ 30	(60,20)
	PIBT	1939 $\pm$ 53	(140,1)
	WPPL	3132 $\pm$ 68	(120,30)
	RH-PP	3170 $\pm$ 60	(120,30)
	RL-RH-PP	3364 $\pm$ 67	(120,30)

Table 4. Highest total throughput of each methods under the corresponding configurations

(N,w)

(TP = throughput).

Figure 10. Symbotic-style layout family: Original (training layout), Shorter Aisle (uniformly shortened aisles), Longer Aisle (uniformly lengthened aisles), In/Out Switch (inbound and outbound docks swapped), and In/Out Alternate (inbound/outbound docks interleaved along the perimeter). All share the same map size $(W,H)$ .

Figure 11. Total throughput versus different Symbotic maps in zero-shot transfer evaluation at

N=120

and

w=20

. The base model is trained at

N=120

and

w=20

on the Original map.

Figure 12. Throughput per agent (TPA) at evaluation vs

K

, evaluated with

N=100

Figure 13. Total throughput vs runtime budget of all methods, evaluated with

N=100

and

w=20

Component	Time (ms)
Priority order generation (network forward pass)	32
Priority order evaluation (run prioritized planning)	46

Table 5. Per priority order runtime breakdown, evaluated at Symbotic map with

N=100

Figure 14. Throughput per agent (TPA) at evaluation vs

\beta

, evaluated with

N=100

Method		$N\!=\!80$	$N\!=\!100$	$N\!=\!120$
Ama.	RH-PP ( $K=5$ )	8.1% $\pm$ 2.1%	39% $\pm$ 5.1%	88% $\pm$ 4.3%
Ama.	RL-RH-PP ( $K=5$ )	7.8% $\pm$ 1.9%	28% $\pm$ 5.0%	60% $\pm$ 6.2%
Sym.	RH-PP ( $K=5$ )	83% $\pm$ 3.9%	97% $\pm$ 1.1%	99% $\pm$ 0.1%
Sym.	RL-RH-PP ( $K=5$ )	34% $\pm$ 4.8%	84% $\pm$ 3.5%	97% $\pm$ 0.3%

Table 6. Percentage of steps where the selected order yields an infeasible initial plan (lower is better), tracked from same experiments in Table 2 , ‘Ama.’ for Amazon and ‘Sym.’ for Symbotic.

Figure 15. Total throughput during training under different congestion (

\kappa

) and infeasibility (

\sigma

) weights in reward function Eq. 2 , evaluated on-the-fly with

N=120

Figure 16. Total throughput during training for encoder ablation study, evaluated on-the-fly with

N=120

Method		$N\!=\!80$		$N\!=\!100$		$N\!=\!120$
Method		TPA $\uparrow$	Time(s) $\downarrow$	TPA $\uparrow$	Time(s) $\downarrow$	TPA $\uparrow$	Time(s) $\downarrow$
Ama.	DQ-RH-PP	27.23 $\pm$ 0.77	0.17	20.89 $\pm$ 1.64	0.25	17.66 $\pm$ 0.56	0.48
Ama.	RL-RH-PP ( $K=5$ )	31.80 $\pm$ 0.46	0.65	28.84 $\pm$ 0.35	0.79	25.76 $\pm$ 0.55	0.96
Sym.	DQ-RH-PP	17.33 $\pm$ 0.56	0.15	14.01 $\pm$ 2.31	0.22	9.88 $\pm$ 0.74	0.43
Sym.	RL-RH-PP ( $K=5$ )	18.38 $\pm$ 0.50	0.68	15.38 $\pm$ 1.85	0.82	11.31 $\pm$ 2.21	0.99

Table 7. Compare with other priority order assignment heuristics (

w=20

). ‘Ama.’ for Amazon and ‘Sym.’ for Symbotic.

Figure 17. Total throughput during training for contextual bandit ablation study, evaluated on-the-fly with

N=80

Figure 18. Number of tasks completed during simulation (Symbotic map,

N=100

). We measure how many tasks are completed between consecutive planning steps. The green dashed vertical lines highlight the key planning steps 0, 30, and 100 shown in Figure 19 . In the RH-PP

\rightarrow

RL-RH-PP curve, we first use RH-PP for planning and switch to RL-RH-PP at planning step 30.

Figure 19. Priority heatmaps for three planning methods (rows) at different steps (columns): 0, 30, and 100, as shown in Figure 18 . Agents are shown in dots. The top row shows RH-PP, which assigns uniformly random priorities and experiences severe congestion by step 100. The middle row shows RL-RH-PP, which adaptively assigns higher priorities for agents in congested regions, sustaining high throughput. The bottom row shows switching from RH-PP (planning steps 0–29) to RL-RH-PP at step 30, effectively resolving inherited congestion by step 100. Lighter colors indicate higher priority assignments.

Figure 20. Next movement directions along shortest path and the actual planned path of RH-PP $\rightarrow$ RL-RH-PP curve at planning step = 45 in Figure 18 . The blue bounding boxes highlight the agents located near the boundary of the congested region. Different ordinal directions are shown in different colors, the cross symbol indicates wait action.

Figure 21. Illustrative grid world example of RL-RH-PP congestion recovery. It shows a deck and a narrow aisle with agents labeled “1” (lower priority) and “2” (higher priority), and their goals. As a result, agent 1 backtracks to clear the path, enabling agent 2 to move forward. This temporary detour mitigates congestion and prevents deadlocks, thereby improving throughput.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 22. Total throughput versus agent number

N

in zero-shot transfer evaluation. The base model is trained at

N=120

and

w=20

, and evaluated zero-shot at other

N

with

w=15

Figure 23. Total throughput versus agent number

N

in zero-shot transfer evaluation. The base model is trained at

N=120

and

w=20

, and evaluated zero-shot at other

N

with

w=10

Figure 24. Total throughput versus different Symbotic maps in zero-shot transfer evaluation. The base model is trained at

N=120

and

w=20

on the Original map, and evaluated zero-shot at other map layouts with

w=20

Figure 25. Throughput per agent (TPA) at evaluation vs

\beta

, evaluated with

N=80

Figure 26. Throughput per agent (TPA) at evaluation vs

K

, evaluated with

N=80

Notation	Description
General MAPF and Agent Parameters
$N$	Number of agents.
$V,E$	Vertices and edges defining the MAPF graph $G=(V,E)$ .
$W,H$	Width and height of the warehouse map.
$g_{i}$	Goal location of agent $i$ .
$o_{i}$	Indicator if agent $i$ is forced to use its shortest path (when no feasible single-agent path is found).

Appendix

Table 35

Parameter	Value
Training epochs	4000
Rollout reuse per epoch ( $f$ )	3
Entropy loss weight ( $\eta$ )	0.01
PPO clipping parameter ( $\epsilon$ )	0.2
Initial learning rate ( $\lambda$ )	0.001
Learning rate decay ( $\omega$ )	0.999

Appendix

Table 9. Hyperparameter Settings for RL-RH-PP

Warehouse Automation

See all 14 papers

Search-Aided Joint Agent-Environment Reinforcement Learning for Robust Lifelong Multi-Agent Path Finding with Rotations
Aug 6, 2026He Jiang, Jingtian Yan, Yulun Zhang +5Constrained Motion Planning Robust MAPF
1Carnegie Mellon University · University of Southern California · 3National University of Singapore
From Gridworlds to Warehouses: Adapting Lightweight One-shot Multi-Agent Pathfinding for AGVs
May 15, 2026Hiroki Nagai, Keisuke OkumuraMulti-Robot Motion Planning Constrained Motion Planning
National Institute of Advanced Industrial Science and Technology (AIST), Japan
TRACS: A Geometry-Aware Framework for Scalable Multi-Agent Path Finding in Warehouses
Sep 19, 2026Siddhant Erande, Anuj TiwariMulti-Agent Path Finding Motion Planning
Department of Engineering Design, Indian Institute of Technology Madras, Chennai 600036, India · Department of Mechanical Engineering at Indian Institute of Technology Madras, Chennai 600036, India

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

Search-Aided Joint Agent-Environment Reinforcement Learning for Robust Lifelong Multi-Agent Path Finding with Rotations

He Jiang, Jingtian Yan, Yulun Zhang, Yimin Tang+4

1Carnegie Mellon University · University of Southern California · 3National University of Singapore

Constrained Motion Planning Robust MAPF Multi-Agent Path Finding Cooperative MARL

Open paper AskPDF arXiv

Lifelong Multi-Agent Path Finding (LMAPF) requires repeatedly planning collision-free paths for agents that continuously receive new goals upon reaching their current ones. While many learning-based planners have been proposed for LMAPF, most rely on oversimplified kinematic assumptions that may overlook motion constraints critical to real-world performance. In this work, we study a more realistic LMAPF model derived from many real-world automated warehouse systems, termed LMAPF-R2, which incorporates robust safety constraints and in-place rotation constraints. These constraints substantially increase coordination difficulty, particularly in highly constrained spaces. To address these challenges, we propose Search-Aided Joint Reinforcement Learning (SJRL). We first augment neural policies with Causal PIBT, a single-step search-based planner that resolves agents' collisions and propagates their intentions. We then introduce a unified RL formulation that jointly optimizes agent and environment policies, where the environment policy learns graph edge costs to provide global movement guidance via backward Dijkstra search. Experiments demonstrate that SJRL achieves significant improvements over the strong search-based planner, Causal-PIBT, across multiple high-density maps. We further validate SJRL in a challenging mixed-reality warehouse environment with 8 physical robots and 248 virtual robots.

Abstract

Warehouse Automation

Explore similar work

Search-Aided Joint Agent-Environment Reinforcement Learning for Robust Lifelong Multi-Agent Path Finding with Rotations

From Gridworlds to Warehouses: Adapting Lightweight One-shot Multi-Agent Pathfinding for AGVs

TRACS: A Geometry-Aware Framework for Scalable Multi-Agent Path Finding in Warehouses