Paper deep dive
Lifelong Scalable Multi-Agent Realistic Testbed and A Comprehensive Study on Design Choices in Lifelong AGV Fleet Management Systems
Jingtian Yan, Yulun Zhang, Zhenting Liu, Han Zhang, He Jiang, Jingkai Chen, Stephen F. Smith, Jiaoyang Li
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/21/2026, 2:55:52 AM
Summary
The paper introduces LSMART, an open-source simulator for evaluating Multi-Agent Path Finding (MAPF) algorithms in Lifelong MAPF (LMAPF) settings within Automated Guided Vehicle (AGV) Fleet Management Systems (FMS). It addresses limitations of prior tools like SMART, which did not support lifelong planning or realistic execution constraints. LSMART incorporates kinodynamic models, communication delays, and execution uncertainties. The authors analyze key design choices: planner invocation policies (periodic vs. event-based), instance generation strategies for duplicate goals, and fail policies for handling planning failures. The study provides empirical comparisons of state-of-the-art methods to guide the design of centralized lifelong AGV systems.
Entities (10)
Relation Signals (7)
LSMART → developedby → Carnegie Mellon University
confidence 95% · Jingtian Yan... Robotics Institute, Carnegie Mellon University
LSMART → handles → AGV
confidence 95% · evaluate any Multi-Agent Path Finding (MAPF) algorithm in a Fleet Management System (FMS) with Automated Guided Vehicles (AGVs)
LSMART → supports → LMAPF
confidence 95% · LSMART, an open-source simulator to evaluate any Multi-Agent Path Finding (MAPF) algorithm in a Fleet Management System (FMS)... Lifelong MAPF (LMAPF) is a variant of MAPF
LSMART → extends → SMART
confidence 90% · Generalizing SMART to an FMS requires many more design choices... In this paper, we first present LSMART... that incorporate all these considerations
LSMART → replaces → Pebble Motion Model
confidence 90% · LSMART... considering agent kinodynamics... most works predominantly assume the pebble motion model
LSMART → incorporates → ADG
confidence 85% · LSMART uses ADG... The paths are then converted and added to the ADG
LSMART → supports → PIBT
confidence 80% · LSMART supports (1) replanning from scratch using PIBT
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2602.15721v1
- Canonical: https://arxiv.org/abs/2602.15721v1
Trouble viewing inline? Open PDF directly →
Full Text
55,015 characters extracted from source content.
Expand or collapse full text
Lifelong Scalable Multi-Agent Realistic Testbed and A Comprehensive Study on Design Choices in Lifelong AGV Fleet Management Systems Jingtian Yan 1 * , Yulun Zhang 1 * , Zhenting Liu 1 , Han Zhang 2 , He Jiang 1 , Jingkai Chen 2 , Stephen F. Smith 1 , Jiaoyang Li 1 1 Robotics Institute, Carnegie Mellon University 2 Symbotic jingtianyan,yulunzhang@cmu.edu Abstract 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 Man- agement System (FMS) with Automated Guided Vehicles (AGVs). MAPF aims to move a group of agents from their corresponding starting locations to their goals. Life- long MAPF (LMAPF) is a variant of MAPF that continu- ously assigns new goals for agents to reach. LMAPF ap- plications, 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 execu- tion and communication for AGVs. Prior work has presented SMART, a software capable of evaluating any MAPF algo- rithms while considering agent kinodynamics, communica- tion 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 optimal- ity and differing agent-model assumptions, one must decide how to plan. Third, when the planner fails to return valid so- lutions, the system must determine how to recover. In this pa- per, we first present LSMART, an open-source simulator that incorporate 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, of- fering guidance on how to effectively design centralized life- long AGV Fleet Management Systems. LSMART is available at https://smart-mapf.github.io/lifelong-smart. 1 Introduction We present LSMART, the first open-source software capa- ble of evaluating any Multi-Agent Path Finding (MAPF) al- gorithm in a centralized, lifelong Fleet Management Sys- tem (FMS) with Automated Guided Vehicles (AGVs). MAPF (Stern et al. 2019) aims to move agents from their starts to goals without collisions, and lifelong MAPF (LMAPF) is a variant of MAPF that continuously assigns new goals to agents. LMAPF has extensive applications, * These authors contributed equally and are listed alphabetically. Copyright © 2026, Association for the Advancement of Artificial Intelligence (w.aaai.org). All rights reserved. such as autonomous fulfillment warehouses (Li et al. 2021b) and robotic sorting systems (Zhang et al. 2025a), where a centralized, lifelong system is required to coordinate the movement of a fleet of AGVs. Many prior works have stud- ied LMAPF by planning paths (Li et al. 2021b), optimiz- ing task assignments (Kou et al. 2020), optimizing physical layouts (Zhang et al. 2023a), or optimizing traffic (Zhang et al. 2024b). Although MAPF and LMAPF research is of- ten motivated by real-world applications, very few works are evaluated in a realistic setting that considers kinodynamic constraints, communication delays, and execution uncertain- ties. In fact, most works predominantly assume the peb- ble motion model for AGVs’ movement, where they move in a discretized space (typically a 4-connected grid) and at discretized timesteps. While a prior work has proposed SMART (Yan et al. 2025a), an open-source software tool to evaluate any MAPF algorithm while respecting these fac- tors, SMART is designed for MAPF, instead of LMAPF. Generalizing SMART to an FMS in LMAPF settings re- quires non-trivial design choices. First, we need to decide when to plan. In LMAPF, agents are continuously assigned new goals, which requires invoking the planner to plan new paths. We also need to resynchronize agents’ plans through replanning based on execution feedback to maintain effi- ciency. Therefore, an invocation policy is needed to decide when to invoke the planner. Second, we must decide how to plan. Prior work has proposed MAPF algorithms with different optimality and agent models. Using an algorithm with better optimality and a more accurate agent model im- proves solution quality, but also increases runtime (Yan et al. 2025b). In LMAPF, the MAPF planner often has a time limit. Thus, it is critical to determine how to plan. For exam- ple, is an optimal planner with a simplified agent model bet- ter than a suboptimal planner with an accurate agent model? Moreover, MAPF planners often assume that agents remain at their goals upon arrival and therefore require distinct goals, whereas in LMAPF it is reasonable to assume that the same goal can be assigned to multiple agents. Therefore, an instance generator is needed to generate and refine MAPF problem instances that satisfy such assumptions. Third, we must decide how to recover from failure. In practice, MAPF planners may fail to return a solution, either due to algorith- mic incompleteness (Ma et al. 2019) or time limits despite theoretical completeness (Sharon et al. 2015). Thus, a fail arXiv:2602.15721v1 [cs.RO] 17 Feb 2026 policy is required to recover from planning failures (Morag, Stern, and Felner 2023). In this paper, we present LSMART, the first open-source simulation software that allow MAPF researchers to evalu- ate any MAPF algorithm in an FMS. LSMART encapsu- lates all the design choices mentioned above in separate modules. These include (1) a MAPF planner, (2) a MAPF problem instance generator, (3) an invocation policy, and (4) a fail policy. We provide documentation so that users can customize each module to conduct empirical experiments relevant to their research. We also implement state-of-the- art solutions in each module. Although some of these so- lutions have been studied in prior LMAPF work, they are almost all evaluated under highly simplified assumptions, most commonly the pebble motion model with perfect ex- ecution and communication. Thus, such evaluations could systematically overestimate performance or even lead to qualitatively different conclusions when applied to realistic settings. LSMART enables these design choices to be evalu- ated under realistic execution conditions at scale, supporting experiments with thousands of AGVs in physics-based sim- ulation. Our empirical study shows that system-level design choices may behave differently when evaluated in realistic FMS settings compared to idealized MAPF models, under- scoring the need for execution-aware evaluation tools. 2 Background LMAPF is often solved by decomposing the problem into a sequence of MAPF problems and exploiting an existing MAPF algorithm to solve them. However, deploying MAPF algorithms in an FMS requires more than a sequential de- composition. In this section, we first formally define the standard MAPF and LMAPF, along with the pebble motion agent, the agent model predominantly used in prior MAPF and LMAPF works. We then define the AGV and the FMS that are simulated in LSMART. Finally, we discuss related work on LMAPF and FMS. 2.1 Lifelong MAPF and Its Design Choices Definition 1 (Pebble Motion Agent) Given a 2D grid graph G(V,E), a pebble motion agent must be placed at a vertex. It can move to an adjacent vertex or wait at its current vertex in each discretized timestep. Two pebble motion agents collide if they reach the same vertex or swap vertices at the same timestep. Definition 2 (Standard MAPF) Given a 2D grid graph G(V,E) and k pebble motion agents, each with a start and a goal, the standard MAPF aims to search for collision-free paths from the starts to the corresponding goals. Standard MAPF minimizes the sum-of-costs, defined as the sum of the path lengths of all agents, where a path length equals the number of timesteps it takes for an agent to arrive at its goal. Definition 3 (Standard Lifelong MAPF) Standardlife- long MAPF (LMAPF) is a variant of standard MAPF where agents are assigned new goals upon reaching their current goals. Standard LMAPF aims to maximize throughput, defined as the number of goals reached per timestep. Definition 4 (Automated Guided Vehicles (AGV)) Given a 2D workspace, an AGV is modeled as a differential drive robot that can move forward or rotate in place in continuous time. Each AGV has an onboard controller that executes motions subject to speed and acceleration limits. The state of an AGV is determined by (x,y,θ,t), where x,y ∈R determines its planar location, θ ∈ [0, 2π) determines the orientation, and t∈R ≥0 determines the time. Definition 5 (AGV Fleet Management System (FMS)) An FMS is a centralized lifelong system in which a fleet of AGVs is coordinated to solve a lifelong MAPF problem in a 2D rectangular workspace. The space is evenly divided into a grid consisting of M × N cells, some of which are non-traversable obstacles. Each AGV can occupy at most one cell. It can either wait or rotate in a cell, or move to a neighboring cell. Two AGVs are considered to collide if they occupy the same cell or swap cells during overlapping time intervals. During execution, AGVs are subject to kinody- namic constraints and receive their planned paths through network communication. Each AGV uses an onboard controller to track its assigned path. The system considers: (1) communication delays among the AGVs, (2) execution uncertainties in action completion times, (3) concurrent planning and execution, and (4) planning failure recovery. Agent Models in Planning Prior works in MAPF pre- dominantly follow the standard MAPF definition, where pebble motion agents are assumed in planning (Stern et al. 2019; Sharon et al. 2015; Ma et al. 2018; Okumura et al. 2019). However, the pebble motion model fails to account for communication delays, execution uncertainties, and the kinodynamics of AGVs. Therefore, to tackle execution un- certainties, Atzmon et al. (2020) proposes the k-robust de- lay model, where the MAPF solution is guaranteed to be collision-free when each agent is delayed for at most k timesteps. To account for kinodynamics, some works in- corporate more realistic robot models, such as rotation and kinematic limits (Cohen et al. 2019; Zhang et al. 2023b; Yan and Li 2025). However, these works always assume that the agent models in planning are always exactly the same as the agent models in execution, resulting in inaccurate experi- mental evaluations. Execution Policy Although it is possible to consider some real-world factors during planning, it is impractical to build perfect agent models for planning that account for all of such factors. Therefore, another line of research attempts to de- velop execution policies capable of executing plans found using simplified agent models. A pioneering work proposes the Action Dependency Graph (ADG) (H ̈ onig et al. 2019), where AGVs are modeled as pebble motion agents during planning. The path of each agent is converted into a se- quence of actions. If two agents visit the same location, ADG constructs a dependency between the corresponding actions of the agents. During execution, the AGVs can then robustly execute their paths following the action dependen- cies according to the ADG. More recent works (Su, Veerapa- neni, and Li 2024; Feng et al. 2024; Jiang, Lin, and Li 2025) seek to optimize ADG by switching inter-agent dependen- cies. However, they are developed on the basis of the pebble motion model and are non-trivial to extend to FMS. Another work (Zhang et al. 2025b) proposed different execution poli- cies for pebble motion agents based on PIBT (Okumura et al. 2019), a one-step rule-based algorithm. At each timestep, each agent attempts to move to a location closer to its goal. If agents collide, a simple rule based on priority inheritance and backtracking is applied to resolve the collision. Since PIBT is designed for pebble motion agents, it is non-trivial to extend them to FMS. Planner Invocation Policy Previous LMAPF algorithms employ primarily a periodic invocation policy, in which MAPF planners are invoked periodically after a few timesteps (Li et al. 2021b; Liu et al. 2019) or once per timestep (Okumura et al. 2019). Meanwhile, works studying ADG-based execution policies (H ̈ onig et al. 2019; Varam- bally, Li, and Koenig 2022) use an event-based invocation policy in which the planner is only invoked when one of the AGVs is expected to finish executing all its actions in the ADG before the planner returns a new batch of paths. To the best of the authors’ knowledge, no prior work has system- atically studied invocation policy or compared the proposed invocation policies. Duplicate Goals Resolution in Instance Generator In FMS, it is common for two agents to have duplicate goals. However, duplicate goals may cause standard MAPF solvers to fail, since they assume agents remain at their goals indef- initely. To resolve duplicate goals, one can assign a tempo- rary goal to an agent and allow it to return to its original goal after the other agent releases that goal, namely the distinct- one-goal instance generator. However, this could result in unnecessary detours for AGVs because traveling to tempo- rary goals does not contribute to throughput. Liu et al. (2019) assigns a distinct home location for each agent and appends them as the last goals to avoid duplicate goals. The paths to the home locations are never executed. This method avoids taking detours in temporary goals, but requires additional planning efforts. Li et al. (2021b) leverages a windowed- multi-goals instance generator that assigns multiple goals to each agent and plans collision-free paths within a pre- defined time window, but it requires a windowed MAPF al- gorithm. Morag et al. (2025) reformulates the MAPF prob- lem as MAPF for Lifelong (MAPF4L), which allows agents to move freely after reaching their goals. MAPF4L planners can solve standard MAPF problems regardless of duplicate goals. Notably, all of these works evaluate their methods us- ing the unrealistic pebble motion model, and none of the previous works have compared these different methods on resolving duplicate goals. Fail Policy In case the MAPF planner fails to return collision-free paths, an FMS must adapt to the failure. One approach is to replan using a separate, fast, but suboptimal planner, such as PIBT (Okumura et al. 2019), the runtime of which can be neglected. If the MAPF planner returns colliding paths, which can be intermediate solutions found by the planner when the timeout is reached, it can be help- ful to exploit such results rather than abolish them. Morag, Stern, and Felner (2023) propose a simple rule-based fail policy that (1) allows agents whose paths have no collisions to move and (2) instructs agents that are conflicting with oth- ers to wait at their start locations. If a waiting agent collides with a moving agent, the waiting agent can make a single move to avoid the collision if possible. Otherwise, the mov- ing agent must stop. However, this strategy might instruct too many agents to wait. The open-source code repository of Li et al. (2021b) implements Local Repair Guided Waits (LRGW), which guides agents along colliding paths and in- serts as few wait actions as possible to generate collision- free paths. Zhang et al. (2024a) proposes a similar fail pol- icy based on a generalized ADG which inserts wait actions to avoid collisions and preserve passing orders of the agents in each location. Both generalized ADG and LRGW resolve collisions only by adding wait actions, which could cause too many agents to wait indefinitely. A more recent work has proposed Guided PIBT. which instructs agents to fol- low a pre-defined set of paths, known as guide paths, while resolving collisions (Chen et al. 2024) using PIBT. Guided PIBT was originally proposed as an LMAPF algorithm, but it can also be an effective fail policy. All the aforementioned fail policies are studied while assuming the pebble motion model. In this work, we select representative policies and conduct a systematic comparison among them. 2.2 FMS Software Table 1 summarizes the existing FMS software. Works 1 and 2 use differential drive robots with speed and acceleration limits during execution, but none of them are open-source. Work 5 considers the rotation motion model, where agents can move forward or rotate in discretized time and space. All other works use the pebble motion model. For the execution policy, works 1, 2, and 6 consider ADG (H ̈ onig et al. 2019). Since the PIBT-based execution policy cannot be trivially extended to FMS, LSMART uses ADG. For instance genera- tors, all previous works support only one method, while LS- MART supports multiple. For planner invocation policies, previous work supports either periodic or event-based pol- icy, while LSMART supports both. For fail policies, work 3 supports LRGW, work 4 supports a generalized ADG, and work 7 supports several rule-based fail policies. All avoid collisions by adding wait actions to the colliding paths re- turned by the planner. LSMART supports a wider variety, including fail policies that depend on colliding paths and those that do not. 3 LSMART Fig. 1 shows the architecture of LSMART. It consists of 7 modules: (1) a planner invocation policy, (2) an instance generator, (3) a MAPF planner, (4) a fail policy, (5) an ADG, (6) a fleet of AGVs, and (7) a physics-based simulator. When generalizing SMART to LSMART, we use the same simula- tor, ADG, and AGV fleet, while adding or updating other modules. In this section, we first provide an overview of LS- MART and discuss each added or updated module in detail. System Overview A simulation starts by using the planner invocation policy to determine whether the MAPF planner should be invoked. If so, LSMART first uses the instance Agent Model (Planning)Agent Model (Execution)Execution PolicyPlanner Invocation PolicyInstance GeneratorFail PolicyOpen-source 1H ̈ onig et al. (2019)Pebble MotionDifferential DriveADGEvent-basedDistinct-One-GoalN/A✗ 2 Varambally, Li, and Koenig (2022)Pebble MotionDifferential DriveADGEvent-basedWindowed-Multi-GoalsN/A✗ 3Li et al. (2021b)Pebble MotionPebble MotionN/APeriodicWindowed-Multi-GoalsLRGW✓ 4Zhang et al. (2024a)Pebble MotionPebble MotionN/APeriodicWindowed-Multi-GoalsGeneralized ADG✓ 5 Chan et al. (2024)Rotation MotionRotation MotionN/APeriodicWindowed-Multi-GoalsN/A✓ 6Zhang et al. (2025b)Pebble MotionPebble MotionADG, PIBT-BasedPeriodicWindowed-Multi-GoalsN/A✓ 7 Morag et al. (2025)Pebble MotionPebble MotionN/APeriodicOne-Goal + MAPF4LRule-based✓ 8LSMART (ours)AnyDifferential DriveADGMultipleMultipleMultiple✓ Table 1: Overview of previous FMS software tools. Action Dependency Graph ... MAPF Problem Instance Simulator MAPF Planner Planner Invocation Policy AGVs PID Controller ... Action Queue ... Action Queue ... Action Queue ... PID ControllerPID Controller Fail Policy Colliding PathsCollision-free Paths Instance Generator Failure Recover Flow Required Flow Successful Plan Flow Find Start StatesAssign GoalsRefine Goals 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. generator to generate the next MAPF problem instance by computing a commit cut in the ADG to find the start states, assigning goals to AGVs, and refining the goals if necessary. At the start of the simulation, the start locations of the AGVs are randomly generated with all agents facing north. The in- stance is passed to the MAPF planner. If the planner solves it successfully, the collision-free paths are returned directly to the ADG. If it fails, the fail policy replans or resolves the collisions. Depending on the fail policy, the MAPF planner may not be required to send colliding paths to the fail policy. The paths are then converted and added to the ADG, which records a sequence of actions for each AGV with their pass- ing orders in each location. The AGVs and the simulator run in parallel with the planner. Each AGV is equipped with a PID controller and an action queue. Each agent periodically obtains actions from the ADG following the action depen- dencies, stores them in the action queue, and executes them in the simulator. If no actions are left, it waits in place. The simulation stops after a pre-defined amount of time. Planner Invocation Policy SMART is designed for stan- dard MAPF, and therefore does not need an invocation policy. LSMART supports two planner invocation policies, namely the periodic policy, where the planner is invoked periodically every P seconds, and the event-based policy, where the planner is invoked when at least one AGV is ex- pected to complete all its assigned actions in the ADG before the planner can return the next plan. To determine whether an AGV is finishing its actions, we pre-define a time limit of T seconds for the planner and compute the minimal amount of time for an AGV to finish one action as ε seconds based on the kinodynamic model of the AGV. If an AGV has fewer than T ε actions left in the ADG, which is the maximum num- ber of actions the AGV can finish in T seconds, the event- based policy invokes the planner. If the planner is to be in- voked, the invocation policy awakens the instance generator to generate the next MAPF problem instance. Instance Generator The instance generator is responsi- ble for generating the next MAPF problem instance by (1) computing a commit cut on the ADG to determine the start states of the AGVs, (2) assigning goals to the AGVs, and (3) refining the goals to satisfy planner-specific assumptions if necessary. To compute the commit cut, we use the same algorithm from H ̈ onig et al. (2019), which looks into the future for T ε actions for each AGV. Since LSMART focuses on evaluating MAPF algorithms, we use a random goal as- signer. Depending on the MAPF planner, LSMART pro- vides three types of instance generator: (1) distinct-one-goal, (2) one-goal, and (3) windowed-multi-goals. The distinct- one-goal instance generator first assigns one goal to each AGV. If duplicate goals are detected, a temporary goal clos- est to the original goal to which no other agents are going is generated and assigned. The distinct-one-goal instance generator is compatible with all standard MAPF algorithms, which expect distinct goals. The one-goal instance gener- ator simply assigns one goal to each AGV and does not perform any refinements. Therefore, it is only compatible with MAPF algorithms that can handle duplicate goals. In this paper, we present experiment results with the MAPF4L model (Morag et al. 2025) for its state-of-the-art perfor- mance in this category. The windowed-multi-goals instance generator assigns at least one goal to each AGV, given a win- dow size, and expects a windowed MAPF planner to plan collision-free paths within the window. It also does not per- form refinements. It guarantees that no AGVs can finish their goals within the pre-defined window. Notably, while these three instance generators have been studied in various prior LMAPF works, we are the first to present a comprehensive comparative study of them in an FMS. Fail Policy LSMART supports four fail policies. Since the MAPF planner may not return colliding paths, LSMART supports (1) replanning from scratch using PIBT (Okumura et al. 2019) and (2) asking all AGVs to wait in place (Morag, Stern, and Felner 2023). If the MAPF planner is capable of returning colliding paths in the case of failure and we want to exploit such paths, LSMART supports (1) Guided PIBT (Chen et al. 2024) and (2) LRGW (Li et al. 2021b). MAPF Planner The MAPF planner takes in a MAPF problem instance with a time limit and returns collision-free paths within that time limit. In SMART, the MAPF planner is only invoked once and does not need to return colliding paths in case of failure. However, in LSMART, the MAPF planner should return colliding paths in case of failure if the fail policy expects them. LSMART supports MAPF plan- ners of different AGV models, including the pebble motion model, the rotation model, the differential drive model, and the k-robust model (Atzmon et al. 2020). LSMART also supports planners that plan in continuous time. 4 Experimental Evaluation In this section, we conduct empirical evaluations of key de- sign choices in LSMART. We focus on user-customizable modules, including (1) instance generators, (2) planner in- vocation policies, (3) failure policies, and (4) agent models and theoretical optimality in the MAPF planner. 4.1 General Experiment Setup Table 2 summarizes all LSMART setups used in all experi- ments and Table 3 summarizes all experiments. Map We conduct all experiments on six maps, including warehouse-33-36, warehouse-10-20-10-2-1, maze-32-32-4, empty-32-32, random-64-64-10, and room-64-64-16, shown in the corners of Fig. 2. Due to constraints in space, we show part of the results in Appendix B. The warehouse-33-36 is used extensively in previous lifelong MAPF works (Li et al. 2021b; Zhang et al. 2023a), and the other five maps are selected from the MAPF benchmark (Stern et al. 2019). On the two warehouse maps, agents move indefinitely between randomly selected workstations (pink) and endpoints (blue). In other maps, agents move between randomly selected empty spaces (white). In all maps, black represents obstacles. During execution, each map is converted to continuous grids, where each grid has a size of 1 × 1 m. AGV Model in Execution During execution, we use dif- ferential drive robots with maximum speed of 2m/s, accel- eration 2m/s 2 and angular speed of 45 ◦ /s. Metrics For all experiments, we show two metrics: (1) throughput and (2) the ratio of fail policy calls, computed as the ratio between the number of fail policy calls to the number of planner invocations. In each map, we run simu- lations with various numbers of agents. For each number of agents, we run 10 simulations, each lasting for 600 simula- tion seconds. We plot the average as solid lines and the 95% confidence intervals as shaded areas in the figures. Compute Resource We conduct all experiments on an HPC with numerous 64-core AMD EPYC 7742 CPUs, each with 256 GB of RAM (Brown et al. 2021). 4.2 Instance Generator Experiment Setup We perform experiment 1 as described in Table 3. We compare three instance generators (IG) each paired with a corresponding MAPF planner. For a fair com- parison, we use variants of PBS (Ma et al. 2019) as the MAPF planners, resulting in three setups of IGs and plan- ners: (1) standard: distinct-one-goal IG with standard PBS, (2) transient: one-goal IG with MAPF4L PBS (Morag et al. 2025), and (3) windowed: windowed-multi-goals IG with windowed PBS (Li et al. 2021b). Experiment Result Fig. 2 presents the results of ex- periment 1. The windowed setup consistently achieves equal or highest throughput. This is because the win- dowed planning mechanism reduces planning effort, al- lowing the planner to fail less and reducing the ratio of fail policy calls. The comparison between standard and transient setups is in accordance with Morag et al. (2025). When there are a limited number of possible goals, such as in warehouse-10-20-10-2-1, the tran- sient setup outperforms the standard setup. Otherwise, ei- ther the two setups are similar (room-64-64-16) or the standard setup slightly outperforms the transient setup (random-64-64-10). Additional results are shown in Fig. 9 of Appendix B.1. 4.3 Planner Invocation Policy Experiment Setup We perform experiments 2, 3, and 4 in Table 3. For experiment 2, we compare periodic and event- based invocation policies using the windowed PBS planner with W = 1 seconds and W = 10 seconds. In Experiment 3, we compare different configurations with P = W , pair- ing the periodic invocation policy with planning windows of the same size. Although Varambally, Li, and Koenig (2022) conducted a similar study with the event-based policy, their experiments were conducted in a single setup with low agent density and a small map (50 robots in a 60 × 20 map), whereas our experiments scale to as many as 2000 robots on maps as large as 61× 159. In experiment 4, we isolate the impact of W and P , performing an ablation on different val- ues of P with a standard MAPF solver. Intuitively, more fre- quent replanning can improve the system’s ability to adapt SetupAgent Model (Planning)PlannerW (s)P (s)T (s)Planner Invocation PolicyInstance GeneratorFail Policy 1Pebble MotionStandard PBS∞11PeriodicDistinct-One-GoalPIBT 2Pebble MotionStandard PBS∞N/A1Event-basedDistinct-One-GoalPIBT 3Pebble MotionWindowed PBS111PeriodicWindowed-Multi-GoalsPIBT 4Pebble MotionWindowed PBS1N/A1Event-basedWindowed-Multi-GoalsPIBT 5Pebble MotionMAPF4L PBS∞11PeriodicOne-GoalPIBT 6 Pebble MotionMAPF4L PBS∞N/A1Event-basedOne-GoalPIBT 7Pebble MotionWindowed PBS101010PeriodicWindowed-Multi-GoalsPIBT 8Pebble MotionWindowed PBS10N/A10Event-basedWindowed-Multi-GoalsPIBT 9Pebble MotionWindowed PBS222PeriodicWindowed-Multi-GoalsPIBT 10Pebble MotionWindowed PBS555PeriodicWindowed-Multi-GoalsPIBT 11 Pebble MotionMAPF-LNS2∞0.1, 0.5, 1, 2,..., 20PeriodicDistinct-One-GoalAll Wait 12Pebble MotionWindowed PBS111PeriodicWindowed-Multi-GoalsLRGW 13Pebble MotionWindowed PBS111PeriodicWindowed-Multi-GoalsGuided PIBT 14Pebble MotionWindowed PBS101010PeriodicWindowed-Multi-GoalsLRGW 15 Pebble MotionWindowed PBS101010PeriodicWindowed-Multi-GoalsGuided PIBT 16Pebble MotionStandard CBS∞2020PeriodicDistinct-One-GoalAll Wait 17Rotation MotionStandard CBS∞2020PeriodicDistinct-One-GoalAll Wait 18Pebble MotionStandard P∞2020PeriodicDistinct-One-GoalAll Wait 19 Rotation MotionStandard P∞2020PeriodicDistinct-One-GoalAll Wait 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. Invoke=Periodic, IG=distinct-one-goal + Standard PBS Invoke=Event-based, IG=distinct-one-goal + Standard PBS Invoke=Periodic, IG=windowed-multi-goals + Windowed PBS Invoke=Event-based, IG=windowed-multi-goals + Windowed PBS Invoke=Periodic, IG=one-goal + MAPF4L PBS Invoke=Event-based, IG=one-goal + MAPF4L PBS 200400600800 Number of Agents 0 2.5 5 Throughput 200400600800 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (a) random-64-64-10 200400600800 Number of Agents 0 0.5 1 Throughput 200400600800 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (b) room-64-64-16 5001000 Number of Agents 0 1.5 3 Throughput 5001000 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (c) warehouse-10-20-10-2-1 Figure 2: Experiment results of instance generators (Experiment 1 in Table 3). SectionExperimentSetups Section 4.211, 2, 3, 4, 5, 6 Section 4.3 23, 4, 7, 8 33, 7, 9, 10 411 Section 4.453, 7, 12, 13, 14, 15 Section 4.5616, 17, 18, 19 Table 3: Summary of experiments and the setups being used. to delays during execution. To study this effect without con- founding it with fail policy, we use MAPF-LNS2 (Li et al. 2022), a scalable MAPF solver that consistently produces solutions across all tested settings. We adopt the standard MAPF model with the distinct-one-goal instance generator. Experiment Result Fig. 3 shows the results of ex- periment 2 in Table 3. In room-64-64-16 and warehouse-10-20-10-2-1, both policies have similar performance with the same values of W , potentially due to the topology of the maps. room-64-64-16 contains large open areas connected by narrow entry points or corridors. In contrast, warehouse-10-20-10-2-1is sufficiently spacious that congestion rarely occurs, allowing agents to follow their shortest paths regardless of the invocation pol- icy, which results in little performance difference among the policies. In random-64-64-10, interestingly, the advan- tage varies among different values of W . When W = 1 second, the planner makes myopic decisions 1 second in the future, so planning more frequently with the periodic policy results in slightly better throughput. However, when W = 10, the planner makes long-term decisions, making re- planning frequently less desirable. Therefore, sticking to the planned paths with the event-based policy results in better throughput than the periodic policy. Fig. 10 in Appendix B.2 shows additional results. Fig. 4 shows the result of experiment 3. Across all maps, invoking the planner more frequently and planning for shorter horizons results in better throughput with a smaller number of agents. This conforms with the results obtained by Varambally, Li, and Koenig (2022). However, with a larger number of agents, invoking the planner less frequently while planning for longer horizons is more beneficial. This Windowed PBS (W=1s) + Invoke=Periodic Windowed PBS (W=1s) + Invoke=Event-based Windowed PBS (W=10s) + Invoke=Periodic Windowed PBS (W=10s) + Invoke=Event-based 200400600800 Number of Agents 0 2.5 5 Throughput 200400600800 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (a) random-64-64-10 200400600800 Number of Agents 0 0.5 1 Throughput 200400600800 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (b) room-64-64-16 5001000 Number of Agents 0 1.5 3 Throughput 5001000 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (c) warehouse-10-20-10-2-1 Figure 3: Experiment results of planner invocation policies (Experiment 2 in Table 3). Windowed PBS (P=W=1s)Windowed PBS (P=W=2s)Windowed PBS (P=W=5s)Windowed PBS (P=W=10s) 200400600800 Number of Agents 0 2.5 5 Throughput 200400600800 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (a) random-64-64-10 200400600800 Number of Agents 0 0.5 1 Throughput 200400600800 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (b) room-64-64-16 5001000 Number of Agents 0 1.5 3 Throughput 5001000 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (c) warehouse-10-20-10-2-1 Figure 4: Experiment results of P and W (Experiment 3 in Table 3). Number of Agents:3060100 (a) random-64-64-10(b) room-64-64-16(c) warehouse-10-20-10-2-1 Figure 5: Experiment results of different P with standard MAPF (Experiment 4 in Table 3). serves as an updated result of Varambally, Li, and Koenig (2022). Fig. 11 in Appendix B.2 shows additional results. Fig. 5 shows the result of experiment 4. Decreas- ing P improves throughput on random-64-64-10 and warehouse-10-20-10-2-1at high agent densities. However, the advantage of a higher replanning frequency does not hold consistently in room-64-64-16 or at lower densities. This behavior stems from the execution–planning mismatch inherent in FMS. Before each replanning step, the system computes a commit cut to determine the expected start states, and the planner assumes synchronous planning from these states. In practice, however, the committed cuts estimated from the ADG are never perfectly aligned with the agents’ actual progress. As a result, more frequent re- planning does not necessarily resynchronize the system and may even accumulate timing inconsistencies over time. This highlights a key challenge in deploying MAPF within FMS: accurately estimating the commit cut to ensure proper resyn- chronization at each replanning step. Additional results are provided in Fig. 12 in Appendix B.2. 4.4 Fail Policy Experiment Setup We perform experiment 5 in Table 3 to compare the following fail policies: PIBT, Guided PIBT, and LRGW. We do not include the all wait fail policy because experiments in Morag, Stern, and Felner (2023) have proven its bad performance. Experiment Result Fig. 6 shows the results of experi- ment 5 in Table 3. LRGW and PIBT achieve the best perfor- mance on different maps and at different values of W . Com- pared to PIBT, LRGW is advantageous when the conflicting paths returned by windowed PBS are valuable. For exam- ple, in random-64-64-10, for both values of W , LRGW Windowed PBS (w=10s) + FP=GuidedPIBT Windowed PBS (w=10s) + FP=LRGW Windowed PBS (w=10s) + FP=PIBT Windowed PBS (w=1s) + FP=GuidedPIBT Windowed PBS (w=1s) + FP=LRGW Windowed PBS (w=1s) + FP=PIBT 200400600800 Number of Agents 0 2.5 5 Throughput 200400600800 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (a) random-64-64-10 200400600800 Number of Agents 0 0.7 1.4 Throughput 200400600800 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (b) room-64-64-16 5001000 Number of Agents 0 1.5 3 Throughput 5001000 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (c) warehouse-10-20-10-2-1 Figure 6: Experiment results of fail policies (Experiment 5 in Table 3). CBSCBS_rotationPPPP_rotation (a) random-64-64-10(b) room-64-64-16(c) warehouse-10-20-10-2-1 Figure 7: Experiment results of agent model accuracy and planner optimality (Experiment 6 in Table 3). achieves higher throughput than the other two fail policies when they are invoked with a large number of agents. This is because using LRGW to instruct agents to follow such paths is better than replanning from scratch using PIBT, which is known to be a suboptimal and myopic one-step plan- ner. However, when the conflicting paths returned by win- dowed PBS are of low quality, replanning from scratch us- ing PIBT works better. In room-64-64-16, for example, we conjecture that the special topology of the map (chunks of empty spaces connected by narrow entry points) results in the conflicting solution of windowed PBS having too many wait actions. Since LRGW potentially adds more wait ac- tions to avoid collisions, using it results in traffic conges- tion. PIBT, on the other hand, tends to move agents instead of having them wait in place, alleviating more congestion than LRGW. Surprisingly, Guided PIBT fails to be the best fail policy in all setups, meaning that the conflicting paths returned by windowed PBS are low-quality guide paths for it. Fig. 13 in Appendix B.3 shows additional results. 4.5 Optimality and Robot Model Accuracy Experiment Setup Planning with more accurate agent models and more optimal solvers leads to better solution quality, but both lead to a longer planning runtime (Yan et al. 2025b). Therefore, we conduct experiment 6 in Table 3 to study the trade-off between optimality and model accuracy. We pair the pebble motion and rotation motion models with CBS (Li et al. 2020; Zhang et al. 2023b), a slow optimal solver, and P (Erdmann and Lozano-Perez 1987), a fast suboptimal solver, to set up the experiment. Experiment Result As shown in Fig. 7, if all planners never invoke the fail policy, the planners with more accurate models always achieve better throughput. However, when we compare optimal and suboptimal planners, their solution quality is close when the instances can be solved by both, as prominent in random-64-64-10. However, both more accurate models and stronger optimality guarantees degrade the planners’ scalability. The results in room-64-64-16 and warehouse-10-20-10-2-1 evidently demonstrate such tradeoffs between planners’ solution quality and scala- bility. Fig. 7 in Appendix B.4 shows additional results. Ad- ditional comparisons of planner optimality under the same agent model are provided in Appendix C. 5 Conclusion We present LSMART, the first open-source simulator capa- ble of evaluating any MAPF algorithms in FMS that con- sider kinodynamics constraints, communication delays, and execution uncertainties. LSMART also considers a number of design choices, including (1) MAPF planners, (2) in- stance generators, (3) planner invocation policies, and (4) fail policies. LSMART synthesizes these design choices as customizable modules, allowing users to conduct experi- ments to evaluate novel MAPF algorithms in FMS. We con- duct empirical comparisons of state-of-the-art solutions in the above design choices, each has been studied in the prior MAPF literature but has not been evaluated under settings as realistic as LSMART. Future work includes adding support for graphs beyond the 4-connected grid in the simulator and for robots with more complex kinodynamics than AGVs. Acknowledgments This work is in part supported by the National Science Foun- dation (NSF) under grant numbers #2328671 and #2441629, as well as a gift from Amazon. This work used Bridge-2 at Pittsburgh Supercomputing Center (PSC) through allocation CIS220115 from the Advanced Cyberinfrastructure Coordi- nation Ecosystem: Services & Support (ACCESS) program, which is supported by NSF under grant numbers #2138259, #2138286, #2138307, #2137603, and #2138296. References Atzmon, D.; Stern, R.; Felner, A.; Wagner, G.; and Zhou, n.- f. 2020. Robust Multi-Agent Path Finding and Executing. Journal of Artificial Intelligence Research, 67: 549–579. Brown, S. T.; Buitrago, P.; Hanna, E.; Sanielevici, S.; Scibek, R.; and Nystrom, N. A. 2021. Bridges-2: A Platform for Rapidly-Evolving and Data Intensive Research. In Pro- ceedings of the Practice and Experience in Advanced Re- search Computing (PEARC): Evolution Across All Dimen- sions, PEARC ’21. Chan, S.-H.; Chen, Z.; Guo, T.; Zhang, H.; Zhang, Y.; Hara- bor, D.; Koenig, S.; Wu, C.; and Yu, J. 2024. The League of Robot Runners Competition: Goals, Designs, and Imple- mentation. In ICAPS 2024 System’s Demonstration track. Chen, Z.; Harabor, D.; Li, J.; and Stuckey, P. 2024. Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding. In Proceedings of the AAAI Conference on Artificial Intelli- gence (AAAI), 20674–20682. Cohen, L.; Uras, T.; Kumar, T. K. S.; and Koenig, S. 2019. Optimal and Bounded-Suboptimal Multi-Agent Mo- tion Planning. In Proceedings of the Symposium on Combi- natorial Search (SoCS), volume 10, 44–51. Erdmann, M.; and Lozano-Perez, T. 1987. On Multiple Moving Objects. Algorithmica, 2: 477–521. Feng, Y.; Paul, A.; Chen, Z.; and Li, J. 2024. A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 201–209. H ̈ onig, W.; Kiesel, S.; Tinka, A.; Durham, J. W.; and Aya- nian, N. 2019. Persistent and Robust Execution of MAPF Schedules in Warehouses. IEEE Robotics and Automation Letters, 4: 1125–1131. Jiang, H.; Lin, M.; and Li, J. 2025. Speedup Techniques for Switchable Temporal Plan Graph Optimization. In Pro- ceedings of the AAAI Conference on Artificial Intelligence (AAAI), 23212–23221. Kou, N. M.; Peng, C.; Ma, H.; Kumar, T. K. S.; and Koenig, S. 2020. Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 9925– 9932. Li, J.; Chen, Z.; Harabor, D.; Stuckey, P. J.; and Koenig, S. 2021a. Anytime multi-agent path finding via large neighbor- hood search. In International Joint Conference on Artificial Intelligence 2021, 4127–4135. Association for the Advance- ment of Artificial Intelligence (AAAI). Li, J.; Chen, Z.; Harabor, D.; Stuckey, P. J.; and Koenig, S. 2022. MAPF-LNS2: Fast repairing for multi-agent path finding via large neighborhood search. In AAAI Conference on Artificial Intelligence, volume 36, 10256–10265. Li, J.; Gange, G.; Harabor, D.; Stuckey, P. J.; Ma, H.; and Koenig, S. 2020. New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 193–201. Li, J.; Tinka, A.; Kiesel, S.; Durham, J. W.; Kumar, T. K. S.; and Koenig, S. 2021b. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses. In Proceedings of the AAAI Con- ference on Artificial Intelligence (AAAI), 11272–11281. Liu, M.; Ma, H.; Li, J.; and Koenig, S. 2019. Task and Path Planning for Multi-Agent Pickup and Delivery. In Proceed- ings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 1152–1160. Ma, H.; Harabor, D.; Stuckey, P. J.; Li, J.; and Koenig, S. 2019. Searching with Consistent Prioritization for Multi- Agent Path Finding. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 7643–7650. Ma, H.; Harabor, D. D.; Stuckey, P. J.; Li, J.; and Koenig, S. 2018. Searching with Consistent Prioritization for Multi- Agent Path Finding. ArXiv, abs/1812.06356. Morag, J.; Gabay, N.; Koyfman, D.; and Stern, R. 2025. Should Multi-Agent Path Finding Algorithms Coordinate Target Arrival Times? In Proceedings of the International Symposium on Combinatorial Search, 231–235. Morag, J.; Stern, R.; and Felner, A. 2023. Adapting to Plan- ning Failures in Lifelong Multi-Agent Path Finding. In Pro- ceedings of the International Symposium on Combinatorial Search (SoCS), 47–55. Okumura, K.; Machida, M.; D ́ efago, X.; and Tamura, Y. 2019. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding. In Proceedings of the Interna- tional Joint Conference on Artificial Intelligence (IJCAI), 535–542. Sharon, G.; Stern, R.; Felner, A.; and Sturtevant, N. R. 2015. Conflict-Based Search for Optimal Multi-Agent Pathfind- ing. Artificial Intelligence, 219: 40–66. Stern, R.; Sturtevant, N. R.; Felner, A.; Koenig, S.; Ma, H.; Walker, T. T.; Li, J.; Atzmon, D.; Cohen, L.; Kumar, T. K. S.; Bart ́ ak, R.; and Boyarski, E. 2019. Multi-Agent Pathfind- ing: Definitions, Variants, and Benchmarks. In Proceedings of the International Symposium on Combinatorial Search (SoCS), 151–159. Su, Y.; Veerapaneni, R.; and Li, J. 2024. Bidirectional Tem- poral Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution. In Proceedings of the AAAI Conference on Artificial Intel- ligence (AAAI), 17559–17566. Varambally, S.; Li, J.; and Koenig, S. 2022.Which MAPF Model Works Best for Automated Warehousing? In Proceedings of the Symposium on Combinatorial Search (SoCS), 190–198. Yan, J.; and Li, J. 2025.Multi-agent Motion Planning for Differential Drive Robots Through Stationary State Search.In AAAI Conference on Artificial Intelligence, 23360–23368. Yan, J.; Li, Z.; Kang, W.; Zheng, K.; Zhang, Y.; Chen, Z.; Zhang, Y.; Harabor, D.; Smith, S. F.; and Li, J. 2025a. Ad- vancing MAPF towards the Real World: A Scalable Multi- Agent Realistic Testbed (SMART). ArXiv, abs/2503.04798. Yan, J.; Zhou, S.; Smith, S. F.; and Li, J. 2025b. Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines. arXiv preprint arXiv:2511.21886. Zhang, Y.; Barbosa, A. O. G.; Pecora, F.; and Li, J. 2025a. Destination-to-Chutes Task Mapping Optimization for Multi-Robot Coordination in Robotic Sorting Systems. In Proceedings of the IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS). Zhang, Y.; Chen, Z.; Harabor, D.; Bodic, P. L.; and Stuckey, P. J. 2024a.Planning and Execution in Multi-Agent Path Finding: Models and Algorithms. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 707–715. Zhang, Y.; Chen, Z.; Harabor, D.; Bodic, P. L.; and Stuckey, P. J. 2025b. Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities. In AAAI Conference on Artificial Intelligence. Zhang, Y.; Fontaine, M. C.; Bhatt, V.; Nikolaidis, S.; and Li, J. 2023a. Multi-Robot Coordination and Layout Design for Automated Warehousing. In Proceedings of the Inter- national Joint Conference on Artificial Intelligence (IJCAI), 5503–5511. Zhang, Y.; Harabor, D.; Le Bodic, P.; and Stuckey, P. J. 2023b. Efficient Multi Agent Path Finding with Turn Ac- tions. In International Symposium on Combinatorial Search, volume 16, 119–127. Zhang, Y.; Jiang, H.; Bhatt, V.; Nikolaidis, S.; and Li, J. 2024b. Guidance Graph Optimization for Lifelong Multi- Agent Path Finding. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 311– 320. Figure 8: Logo of LSMART. A Logo Fig. 8 shows the logo of LSMART 1 . The logo visualizes the complex nature of a realistic LMAPF system. The central figure—a stylized infinity loop constructed of engineered tracks—represents the Lifelong nature of the system, where agents are continuously assigned new goals. The track fea- tures mechanical gear teeth and circuit-like resistance lines, symbolizing the realistic kinodynamic constraints, commu- nication delays, and execution uncertainties that LSMART accounts for. The orange agents navigating this rigorous course highlight the core challenge: scalable Multi-Agent coordination within a physically constrained environment. B Additional Results In this section, we present additional experiment re- sults to augment Section 4. For experiments out- lined in Table 3, we show results in additional maps, including warehouse-33-36, maze-32-32-4, and empty-32-32. B.1 Instance Generator Fig. 9 shows the additional experimental results of experi- ment 1 in Table 3, comparing different instance generators. B.2 Planner Invocation Policies Fig. 10 shows additional experimental results of experiment 2 in Table 3, comparing different invocation policies. Fig. 11 shows additional experimental results of experiment 3 in Ta- ble 3, comparing different planning windows W and invoca- tion policy frequencies P for the periodic invocation policy. Fig. 12 shows additional experimental results of experiment 4 in Table 3, comparing periodic policy of different P values with standard MAPF planners. B.3 Fail policy Fig. 13 shows additional experimental results of experiment 5 in Table 3, comparing different fail policies. B.4 Optimality and Robot Model Accuracy Fig. 14 shows additional experimental results of experiment 6 in Table 3, comparing planners of different optimalities and agent model accuracies. 1 Generated by Google Gemini 3. C Planner Optimality In this section, we carry out an additional experiment to compare MAPF planners of different optimality. Experiment Setup In this section, given the trade-off be- tween plan optimality and runtime of MAPF algorithms, we evaluate the impact of different planner optimality on throughput. We plan paths of different optimality using MAPF-LNS (Li et al. 2021a), an anytime MAPF algorithm that progressively improves solution quality given a runtime limit seconds. By increasing the runtime limit T , MAPF- LNS returns better solutions. We use the standard MAPF model with the distinct-one-goal refiner and periodic invo- cation policy with P = T , comparing the runtime limits of T ∈0.1, 0.5, 1, 2, 3,..., 20 seconds. Experiment Result As shown in Fig. 15, the throughput curves remain relatively flat across environments and robot densities, indicating that more frequent replanning does not necessarily yield better execution performance. This result arises from two competing effects: Higher replanning fre- quency should help mitigate execution asynchrony caused by delays and controller variability. However, because we use an anytime planner (MAPF-LNS2), a longer replanning period enables more computation, producing higher-quality plans with fewer collisions and thus higher throughput. As these effects counteract each other, the net influence of re- planning frequency becomes small. Invoke=Periodic, IG=distinct-one-goal + Standard PBS Invoke=Event-based, IG=distinct-one-goal + Standard PBS Invoke=Periodic, IG=windowed-multi-goals + Windowed PBS Invoke=Event-based, IG=windowed-multi-goals + Windowed PBS Invoke=Periodic, IG=one-goal + MAPF4L PBS Invoke=Event-based, IG=one-goal + MAPF4L PBS 100200300 Number of Agents 0 1 2 Throughput 100200300 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (a) warehouse-33-36 100200300 Number of Agents 0 0.4 0.8 Throughput 100200300 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (b) maze-32-32-4 100200300400 Number of Agents 0 2 4 Throughput 100200300400 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (c) empty-32-32 Figure 9: Additional experiment results of instance generators (Experiment 1 in Table 3). Windowed PBS (W=1s) + Invoke=Periodic Windowed PBS (W=1s) + Invoke=Event-based Windowed PBS (W=10s) + Invoke=Periodic Windowed PBS (W=10s) + Invoke=Event-based 100200300 Number of Agents 0 1 2 Throughput 100200300 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (a) warehouse-33-36 100200300 Number of Agents 0 0.4 0.8 Throughput 100200300 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (b) maze-32-32-4 100200300400 Number of Agents 0 2 4 Throughput 100200300400 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (c) empty-32-32 Figure 10: Experiment results of planner invocation policies (Experiment 2 in Table 3). Windowed PBS (P=W=1s)Windowed PBS (P=W=2s)Windowed PBS (P=W=5s)Windowed PBS (P=W=10s) 100200300 Number of Agents 0 1 2 Throughput 100200300 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (a) warehouse-33-36 100200300 Number of Agents 0 0.4 0.8 Throughput 100200300 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (b) maze-32-32-4 100200300400 Number of Agents 0 2 4 Throughput 100200300400 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (c) empty-32-32 Figure 11: Additional Experiment results of P and W (Experiment 3 in Table 3). Number of Agents:3060100 01020 Invocation Period P (s) 0.00 0.25 0.50 0.75 1.00 1.25 Throughput 01020 Invocation Period P (s) 0.0 0.2 0.4 0.6 0.8 1.0 Ratio of Fail Policy Calls (a) empty-32-32 01020 Invocation Period P (s) 0.00 0.05 0.10 0.15 0.20 0.25 Throughput 01020 Invocation Period P (s) 0.0 0.2 0.4 0.6 0.8 1.0 Ratio of Fail Policy Calls (b) maze-32-32-4(c) warehouse-10-20-10-2-1 Figure 12: Additional experiment results of different invocation frequencies (Experiment 4 in Table 3). Windowed PBS (w=10s) + FP=GuidedPIBT Windowed PBS (w=10s) + FP=LRGW Windowed PBS (w=10s) + FP=PIBT Windowed PBS (w=1s) + FP=GuidedPIBT Windowed PBS (w=1s) + FP=LRGW Windowed PBS (w=1s) + FP=PIBT 100200300 Number of Agents 0 1 2 Throughput 100200300 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (a) warehouse-33-36 100200300 Number of Agents 0 0.4 0.8 Throughput 100200300 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (b) maze-32-32-4 100200300400 Number of Agents 0 2 4 Throughput 100200300400 Number of Agents 0 0.5 1 Ratio of Fail Policy Calls (c) empty-32-32 Figure 13: Additional experiment results of fail policies (Experiment 5 in Table 3). CBSCBS_rotationPPPP_rotation (a) warehouse-33-36(b) empty-32-32(c) maze-32-32-4 Figure 14: Additional experiment results of MAPF model accuracy and planner optimality (Experiment 6 in Table 3). (a) den312d(b) empty-32-32(c) maze-32-32-4 (d) random-64-64-10(e) room-64-64-16(f) warehouse-10-20-10-2-1 Figure 15: Experiment results of MAPF planner optimality.