We present Lifelong Scalable Multi-Agent Realistic Testbed (LSMART), an open-source simulator to evaluate any Multi-Agent Path Finding (MAPF) algorithm in a Fleet Management System (FMS) with Automated Guided Vehicles (AGVs). MAPF aims to move a group of agents from their corresponding starting locations to their goals. Lifelong MAPF (LMAPF) is a variant of MAPF that continuously assigns new goals for agents to reach. LMAPF applications, such as autonomous warehouses, often require a centralized, lifelong system to coordinate the movement of a fleet of robots, typically AGVs. However, existing works on MAPF and LMAPF often assume simplified kinodynamic models, such as pebble motion, as well as perfect execution and communication for AGVs. Prior work has presented SMART, a software capable of evaluating any MAPF algorithms while considering agent kinodynamics, communication delays, and execution uncertainties. However, SMART is designed for MAPF, not LMAPF. Generalizing SMART to an FMS requires many more design choices. First, an FMS parallelizes planning and execution, raising the question of when to plan. Second, given planners with varying optimality and differing agent-model assumptions, one must decide how to plan. Third, when the planner fails to return valid solutions, the system must determine how to recover. In this paper, we first present LSMART, an open-source simulator that incorporates all these considerations to evaluate any MAPF algorithms in an FMS. We then provide experiment results based on state-of-the-art methods for each design choice, offering guidance on how to effectively design centralized lifelong AGV Fleet Management Systems. LSMART is available at https://smart-mapf.github.io/lifelong-smart.
Figures & tables
Agent Model (Planning)
Agent Model (Execution)
Execution Policy
Planner Invocation Policy
Instance Generator
Fail Policy
Open-source
1
Hönig et al. (2019)
Pebble Motion
Differential Drive
ADG
Event-based
Distinct-One-Goal
N/A
✗
2
Varambally et al. (2022)
Pebble Motion
Differential Drive
ADG
Event-based
Windowed-Multi-Goals
N/A
✗
3
Li et al. (2021b)
Pebble Motion
Pebble Motion
N/A
Periodic
Windowed-Multi-Goals
LRGW
✓
4
Zhang et al. (2024a)
Pebble Motion
Pebble Motion
N/A
Periodic
Windowed-Multi-Goals
Generalized ADG
✓
5
Chan et al. (2024)
Rotation Motion
Rotation Motion
N/A
Periodic
Windowed-Multi-Goals
N/A
✓
6
Zhang et al. (2025a)
Pebble Motion
Pebble Motion
ADG, PIBT-Based
Periodic
Windowed-Multi-Goals
N/A
✓
Table 1: Overview of previous FMS software tools.
Figure 1: Detailed architecture of LSMART. Red boxes are user customizable modules, gray boxes are non-customizable modules, and yellow boxes are data structures used for communicating between modules. Black arrows indicates required flow, red arrows indicate flow when the MAPF planner successfully finds collision-free paths, and yellow arrows indicate flow when the planner fails and the system need to recover from failure.
Setup
Agent Model (Planning)
Planner
W (s)
P (s)
T (s)
Planner Invocation Policy
Instance Generator
Fail Policy
1
Pebble Motion
Standard PBS
∞
1
1
Periodic
Distinct-One-Goal
PIBT
2
Pebble Motion
Standard PBS
∞
N/A
1
Event-based
Distinct-One-Goal
PIBT
3
Pebble Motion
Windowed PBS
1
1
1
Periodic
Windowed-Multi-Goals
PIBT
4
Pebble Motion
Windowed PBS
1
N/A
1
Event-based
Windowed-Multi-Goals
PIBT
5
Pebble Motion
MAPF4L PBS
∞
1
1
Periodic
One-Goal
PIBT
6
Pebble Motion
MAPF4L PBS
∞
N/A
1
Event-based
One-Goal
PIBT
Table 2: Summary of LSMART setups used in the experiments. W is the planning window for windowed MAPF solvers, P is the period to invoke the planner for periodic invocation policy, and T is the runtime limit for one invocation of the MAPF planner, all given in seconds. The ∞ sign indicates that the planner plans collision-free paths to all the given goals.
Section
Experiment
Setups
Section 4.2
1
1, 2, 3, 4, 5, 6
Section 4.3
2
3, 4, 7, 8
3
3, 7, 9, 10
4
11
Section 4.4
5
3, 7, 12, 13, 14, 15
Section 4.5
6
16, 17, 18, 19
Table 3: Summary of experiments and the setups being used.
Figure 2: Experiment results of instance generators (Experiment 1 in Table 3 ).
Figure 3: Experiment results of planner invocation policies (Experiment 2 in Table 3 ).
Figure 4: Experiment results of P and W (Experiment 3 in Table 3 ).
Figure 5: Experiment results of different P with standard MAPF (Experiment 4 in Table 3 ).
Figure 6: Experiment results of fail policies (Experiment 5 in Table 3 ).
Figure 7: Experiment results of agent model accuracy and planner optimality (Experiment 6 in Table 3 ).
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 8: Logo of LSMART.
Figure 9: Additional experiment results of instance generators (Experiment 1 in Table 3 ).
Figure 10: Experiment results of planner invocation policies (Experiment 2 in Table 3 ).
Figure 11: Additional Experiment results of P and W (Experiment 3 in Table 3 ).
Figure 12: Additional experiment results of different invocation frequencies (Experiment 4 in Table 3 ).
Figure 13: Additional experiment results of fail policies (Experiment 5 in Table 3 ).
Figure 14: Additional experiment results of MAPF model accuracy and planner optimality (Experiment 6 in Table 3 ).
Figure 15: Experiment results of MAPF planner optimality.
Local guidance has recently proven to be a powerful driver of empirical performance in real-time, suboptimal multi-agent pathfinding (MAPF), improving the scalable configuration-based solver LaCAM. By injecting informative spatiotemporal cues around each agent, local guidance mitigates congestion, reduces waiting, and remains scalable enough even with tight time budgets, yielding state-of-the-art performance for one-shot MAPF. This study asks whether the same benefits can be lifted to the lifelong setting (LMAPF), where tasks arrive continuously and improvements in per-step plans can increase task completion throughput over long horizons. We propose LLLG, a Lifelong version of LaCAM enhanced with Local Guidance, which employs a receding-horizon windowed planning framework and warm-starts guidance from the previous solution at each timestep. Our method scales effectively, maintains high throughput even in compact, dense environments, and surpasses existing planners, thereby pushing the frontier of real-time, lifelong MAPF.
Tomoki Arita, Keisuke Okumura
Keio University, Japan · National Institute of Advanced Industrial Science and Technology (AIST), Japan
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
Lifelong Multi-Agent Path Finding (LMAPF) requires generating collision-free paths for large agent fleets under strict real-time constraints. Reactive frameworks such as PIBT and Enhanced PIBT (EPIBT) scale effortlessly to thousands of agents through rule-based, step-by-step coordination but suffer from severe temporal myopia, making them ineffective in scenarios where long-horizon reasoning is essential. RHCR plans windowed paths over multi-step horizons but incurs substantial planning overheads that hinder scalability. TP tackles both challenges by planning only subsets of agents at each timestep, yet its applicability is restricted to highly structured maps. To achieve long-horizon planning at scale across general maps, we propose Path Updates over Staggered Horizons (PUSH), a LMAPF planner capable of coordinating thousands of agents in under a second while planning over multi-step horizons. PUSH combines the key advantages of PIBT, RHCR, and TP. Like TP, PUSH reduces computational complexity by planning only a subset of agents at each timestep using staggered planning windows. Unlike TP, however, PUSH plans RHCR-style windowed paths in general maps without relying on restrictive map assumptions. To maintain high throughput in congested environments, PUSH further integrates EPIBT-inspired priority inheritance, backtracking, and anytime improvements into its windowed planning. Empirical evaluations across two realistic MAPF scenarios requiring long-horizon reasoning show that PUSH scales to the same massive agent loads as EPIBT (e.g., 10k agents) while achieving significantly higher system throughput than all baselines.