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.
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
TPA ↑
Time(s) ↓
TPA ↑
Time(s) ↓
TPA ↑
Time(s) ↓
Ama.
RH-PP ( K=5 )
30.85 ± 0.52
0.65
25.92 ± 1.32
0.78
21.74 ± 2.25
0.95
RL-RH-PP ( K=5 )
31.80 ± 0.46
0.65
28.84 ± 0.35
0.79
25.56 ± 0.55
0.96
Sym.
RH-PP ( K=5 )
16.51 ± 0.35
0.68
11.39 ± 4.22
0.80
8.21 ± 2.24
0.96
RL-RH-PP ( K=5 )
18.38 ± 0.50
0.68
15.38 ± 1.85
0.82
11.31 ± 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
TPA ↑
Time(s) ↓
TPA ↑
Time(s) ↓
TPA ↑
Time(s) ↓
Amazon
RH-CBS
4.94 ± 0.83
1.00
3.58 ±0.52
1.00
2.84 ± 0.29
1.00
RH-PBS
22.13 ± 7.58
1.00
4.92 ± 0.65
1.00
3.37 ± 0.26
1.00
PIBT
21.19 ± 0.58
0.16
18.62 ± 0.35
0.20
16.09 ± 0.48
0.27
WPPL
29.70 ± 0.51
1.00
26.60 ± 0.48
1.00
23.59 ± 0.26
1.00
RL-RH-PP (ours)
31.80 ± 0.46
0.65
28.84 ± 0.35
0.79
25.56 ± 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 ↑
Optimal (N,w)
Amazon
RH-CBS
512 ± 83
(40,10)
RH-PBS
2343 ± 30
(60,20)
PIBT
1939 ± 53
(140,1)
WPPL
3132 ± 68
(120,30)
RH-PP
3170 ± 60
(120,30)
RL-RH-PP
3364 ± 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 β , evaluated with N=100
Method
N=80
N=100
N=120
Ama.
RH-PP ( K=5 )
8.1% ± 2.1%
39% ± 5.1%
88% ± 4.3%
RL-RH-PP ( K=5 )
7.8% ± 1.9%
28% ± 5.0%
60% ± 6.2%
Sym.
RH-PP ( K=5 )
83% ± 3.9%
97% ± 1.1%
99% ± 0.1%
RL-RH-PP ( K=5 )
34% ± 4.8%
84% ± 3.5%
97% ± 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 ( κ ) and infeasibility ( σ ) 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
TPA ↑
Time(s) ↓
TPA ↑
Time(s) ↓
TPA ↑
Time(s) ↓
Ama.
DQ-RH-PP
27.23 ± 0.77
0.17
20.89 ± 1.64
0.25
17.66 ± 0.56
0.48
RL-RH-PP ( K=5 )
31.80 ± 0.46
0.65
28.84 ± 0.35
0.79
25.76 ± 0.55
0.96
Sym.
DQ-RH-PP
17.33 ± 0.56
0.15
14.01 ± 2.31
0.22
9.88 ± 0.74
0.43
RL-RH-PP ( K=5 )
18.38 ± 0.50
0.68
15.38 ± 1.85
0.82
11.31 ± 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 → 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 → 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 β , 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.
gi
Goal location of agent i .
oi
Indicator if agent i is forced to use its shortest path (when no feasible single-agent path is found).
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.
He Jiang, Jingtian Yan, Yulun Zhang +5
1Carnegie Mellon University · University of Southern California · 3National University of Singapore
Multi-agent pathfinding (MAPF) under one-shot planning is a core component of warehouse automation, yet classical formulations typically assume four-connected 2D grids with unit-time moves in four directions. To fill reality gaps while still being trackable with discrete combinatorial search, this work proposes a more practical counterpart tailored to differential-drive AGVs. We term this multi-agent warehouse pathfinding (MAWPF), featured with four constraints: (i) agent actions are restricted to straight motion and in-place rotation; (ii) rotations require multi-step costs; (iii) acceleration and deceleration are considered, and; (iv) follower collisions are prohibited to prevent rear-end crashes. To solve MAWPF efficiently, we adapt representative suboptimal MAPF algorithms-PP, LNS2, PIBT, and LaCAM-and conduct comprehensive benchmarking. Our experiments reveal that PP and LNS2 struggle to solve instances with many agents, while PIBT-based approaches achieve preferable scalability with increased solution cost. We believe that these constitute an important step toward adapting classical gridworld MAPF to operational warehouse setups.
Hiroki Nagai, Keisuke Okumura
National Institute of Advanced Industrial Science and Technology (AIST), Japan
Large scale warehouse automation relies on efficient multi agent path finding (MAPF) to coordinate thousands of robots in structured environments. Existing MAPF algorithms primarily improve conflict resolution while representing warehouses as generic navigation graphs, overlooking their inherent geometric structure and traffic patterns. This paper presents TRACS (Traffic aware Routing and Aisle Coordination System), a geometry aware planning framework that exploits warehouse layout to simplify planning rather than introducing another conflict-resolution algorithm. TRACS constructs a directed routing graph with alternating one way aisles that eliminates head on and edge swap conflicts by design, decoupling spatial routing from temporal traffic coordination. Independent hybrid graph grid routing is combined with lightweight edge based scheduling to avoid joint space time search while ensuring collision free execution. Experimental evaluation on warehouse benchmarks against representative priority based, iterative repair, and search based MAPF planners shows that TRACS consistently achieves a 100% empirical success rate while substantially improving planning scalability. On fixed scene benchmarks with up to 1000 robots, TRACS reduces planning time by up to 14.7X while maintaining competitive makespan, lower flowtime, and near optimal path quality. Under a fixed 10 minute planning budget, TRACS routes up to 5120 robots, roughly twice the largest fleet reached by the strongest baselines, while sustaining a 100% success rate, demonstrating the effectiveness of exploiting warehouse geometry for scalable robotic warehouse systems.
Siddhant Erande, Anuj Tiwari
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