Paper deep dive
Search-Aided Joint Agent-Environment Reinforcement Learning for Robust Lifelong Multi-Agent Path Finding with Rotations
He Jiang, Jingtian Yan, Yulun Zhang, Yimin Tang, Tanishq Duhan, Rishi Veerapaneni, Guillaume Sartoretti, Jiaoyang Li
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/8/2026, 3:25:54 AM
Summary
The paper introduces Search-Aided Joint Reinforcement Learning (SJRL) for Lifelong Multi-Agent Path Finding with Rotations (LMAPF-R2). LMAPF-R2 incorporates robust safety constraints and in-place rotation constraints to better model real-world automated warehouse systems. SJRL augments neural policies with Causal PIBT for collision resolution and introduces a unified RL formulation that jointly optimizes agent policies (for local coordination) and environment policies (for global guidance via edge cost optimization). Experiments show SJRL outperforms strong search-based planners like Causal-PIBT in high-density maps and mixed-reality environments.
Entities (7)
Relation Signals (7)
LMAPF-R2 → includes → in-place rotation constraints
confidence 95% · LMAPF-R2, which incorporates robust safety constraints and in-place rotation constraints.
LMAPF-R2 → includes → robust safety constraints
confidence 95% · LMAPF-R2, which incorporates robust safety constraints and in-place rotation constraints.
SJRL → solves → LMAPF-R2
confidence 95% · In this work, we study a more realistic LMAPF model... termed LMAPF-R2... To address these challenges, we propose Search-Aided Joint Reinforcement Learning (SJRL).
SJRL → uses → Causal PIBT
confidence 95% · We first augment neural policies with Causal PIBT... We then introduce a unified RL formulation that jointly optimizes agent and environment policies
SJRL → outperforms → Causal PIBT
confidence 90% · Experiments demonstrate that SJRL achieves significant improvements over the strong search-based planner, Causal-PIBT
LMAPF → underpins → automated warehouses
confidence 90% · LMAPF underpins many real-world multi-agent systems, including... automated warehouses
SJRL → buildsupon → SILLM
confidence 85% · Our design builds upon the neural architecture of the state-of-the-art planner SILLM
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2608.05588v1
- Canonical: https://arxiv.org/abs/2608.05588v1
Trouble viewing inline? Open PDF directly →
Full Text
59,975 characters extracted from source content.
Expand or collapse full text
Search-Aided Joint Agent-Environment Reinforcement Learning for Robust Lifelong Multi-Agent Path Finding with Rotations He Jiang 1 , Jingtian Yan 1 , Yulun Zhang 1 , Yimin Tang 2 , Tanishq Duhan 3 , Rishi Veerapaneni 1 , Guillaume Sartoretti 3 , Jiaoyang Li 1 1 Carnegie Mellon University 2 University of Southern California 3 National University of Singapore hej2,jingtiay,yulunz@andrew.cmu.edu, yimintan@usc.edu, e1280621@u.nus.edu, vrishi@cmu.edu, guillaume.sartoretti@nus.edu.sg, jiaoyangli@cmu.edu Abstract Lifelong Multi-Agent Path Finding (LMAPF) requires repeat- edly planning collision-free paths for agents that continu- ously receive new goals upon reaching their current ones. While many learning-based planners have been proposed for LMAPF, most rely on oversimplified kinematic assump- tions that may overlook motion constraints critical to real- world performance. In this work, we study a more realistic yet scalable 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 coordi- nation difficulty for learning-based planners, 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 poli- cies, where the environment policy learns graph edge costs to provide global movement guidance via backward Dijk- stra search. Experiments demonstrate that SJRL achieves sig- nificant improvements over the strong search-based planner, Causal-PIBT, across multiple high-density maps. We further validate SJRL in a challenging mixed-reality warehouse envi- ronment with 8 physical robots and 248 virtual robots. 1 Introduction Multi-Agent Path Finding (MAPF) (Stern et al. 2019) stud- ies the problem of planning collision-free paths for multiple agents from start vertices to goal vertices on a given graph. Lifelong MAPF (LMAPF) extends this setting by continu- ously assigning new goals to agents once they reach their current ones. The objective is to maximize system through- put, defined as the average number of goals reached by all agents per timestep. LMAPF underpins many real-world multi-agent systems, including smart manufacturing facilities, automated scien- tific laboratories, and virtual gaming environments. Auto- mated warehouses, as one of the key driving domains for LMAPF research, are now widely deployed worldwide by companies such as Amazon and Ocado. As demand for these systems continues to grow, increasingly complex and large- scale LMAPF deployments are expected in the near future. NORLSERL SARLSJRL 0 26 51 77 102 128 Figure 1: Heatmaps of average wait actions on a sortation map. Black cells denote obstacles; red intensity indicates wait frequency. NORL: no RL (Causal PIBT); SERL: en- vironment RL; SARL: agent RL; SJRL: joint RL. SARL alleviates congestion locally, SERL balances traffic globally, and SJRL combines both. See Section 5.1 for details. Accordingly, although many successful search-based plan- ners have been developed over the years (Li et al. 2021a; Okumura et al. 2022; Chen et al. 2024; Jiang et al. 2024), there is growing interest in learning-based approaches due to their potential for greater expressiveness and scalability. Unlike many other multi-robot domains, LMAPF typi- cally targets scenarios with high agent densities 1 , tightly constrained spaces, and long execution horizons, as ex- emplified by automated warehouses. Consequently, both re- search and industrial LMAPF systems often deliberately adopt grid graphs and relatively simple kinematic mod- els to ensure stable and scalable coordination. However, from the pioneering PRIMAL (Sartoretti et al. 2019) and PRIMAL 2 (Damani et al. 2021) to more recent state-of-the- art methods such as MAPF-GPT (Andreychuk et al. 2025b), SILLM (Jiang et al. 2025) and HMAGAT (Jain et al. 2026a), nearly all learning-based LMAPF planners 2 assume the oversimplified standard model (Stern et al. 2019), in which an agent moves directly to a neighboring vertex in a discrete timestep. Such oversimplification may fail to capture mo- 1 Agent density is defined as the ratio of the number of agents to the number of free locations. 2 Since planners for MAPF and LMAPF are largely adaptable, we do not explicitly distinguish between them unless necessary. arXiv:2608.05588v1 [cs.RO] 6 Aug 2026 tion constraints that are critical for high-quality execution in real-world robotic systems. In this work, we study a more realistic LMAPF model, mo- tivated by many real-world automated warehouse systems, termed LMAPF-R2. It incorporates (1) robust safety con- straints that enforce minimum safe distances between mov- ing agents, and (2) in-place rotation constraints that capture the non-holonomic nature of many robots used in practice, such as differential-drive robots. Both constraints have been previously studied for search-based planners. For example, prior work (Atzmon et al. 2020b) introduced robust MAPF and demonstrated its importance for reliable real-world ex- ecution, while studies such as (Varambally, Li, and Koenig 2022; Zhang et al. 2023; Yan et al. 2025) compared different modeling choices and highlighted the adverse consequences of neglecting rotation modeling during planning. Indeed, the modeling gap between planning and execution is equally critical for learning-based planners. However, to the best of our knowledge, it has received little attention in prior learning-based LMAPF studies. Thus, despite their re- markable progress under the standard model (Andreychuk et al. 2025a,b; Jiang et al. 2025), we argue that learning- based LMAPF research should also embrace more realis- tic yet scalable models, such as LMAPF-R2, to keep pace with advances in search-based planning. In fact, robust and rotational constraints substantially in- crease the coordination difficulty for learning-based plan- ners. The robust constraint requires agents to occupy ad- ditional vertices to ensure safe movement, while the rota- tional constraint forces agents to spend multiple timesteps to reach a neighboring vertex. As a result, the environment becomes more congested, and agents become more prone to deadlocks and livelocks. To address these challenges, we propose Search-Aided Joint Reinforcement Learning (SJRL), built upon two key design principles: (1) leveraging the strengths of both search and learning, and (2) optimizing coordination from both agent and environment perspectives. First, inspired by the success of Collision-Shield PIBT (CS-PIBT) (Veerapaneni et al. 2024; Jiang et al. 2025), which applies the single-step search algorithm PIBT (Oku- mura et al. 2022) to resolve potentially colliding decisions of neural policies, we conjecture that such collision shield- ing can also benefit learning in the LMAPF-R2 setting. Ac- cordingly, we integrate a variant of Causal PIBT (Okumura, Tamura, and Défago 2021), to accommodate the robust and rotational constraints and propagate agents’ intentions. Furthermore, motivated by the effectiveness of guidance graphs in coordinating agents through edge cost optimization in highly congested environments (Jiang et al. 2024; Zhang et al. 2024; Yukhnevich and Andreychuk 2025), we hypoth- esize that guidance graphs operate in a policy space com- plementary to the agent policy. Accordingly, we introduce a unified RL formulation that jointly optimizes the agent policy for local reactive coordination and the environment policy for global guidance generation. Experiments under diverse settings show that joint op- timization enables the two policies to reinforce each other, leading to consistent performance improvements. The heatmaps of wait actions on a sortation map in Figure 1 exemplify how joint learning improves traffic flow. Our main contributions can be summarized as follows: 1. We are the first to study LMAPF-R2, a more realistic yet scalable kinematic model, for learning-based plan- ners in scenarios with high agent densities and tightly constrained spaces, and advocate broader investigation into such models in learning-based planning. 2. To address the emerging coordination challenges, we pro- pose a search-aided joint RL framework that learns both agent and environment policies, with tailored adaptations to collision shielding, guidance graph optimization, and network architecture. 3. Through extensive experiments, we demonstrate the im- portance of appropriate modeling, the benefits of joint learning, and the critical role of Causal PIBT in facilitat- ing RL exploration by propagating agents’ intentions. 2 Problem Formulation LMAPF-R2 studied in this work is a variant of LMAPF defined on a 4-neighbor grid graphG = (V,E) withn agents A = a 1 ,a 2 ,...,a n . Vertices in V represent traversable grid cells, and directed edges in E connect adjacent vertices. Each agent is initialized at a unique start vertex v ∈ V with an orientation o∈East, South, West, North. Time is discretized into uniform timesteps. At each timestep, an agent may execute one of four actions: move forward to the adjacent vertex it faces, rotate 90 ◦ clockwise, rotate 90 ◦ counterclockwise, or wait. We prohibit both vertex collisions and following collisions. A vertex collision occurs when two agents occupy the same vertex at the same timestep. A following collision occurs when an agent moves into a ver- tex occupied by another agent in the previous timestep. Fol- lowing collisions also include edge collisions, which occur when two agents swap their locations in a single timestep. The first “R” in LMAPF-R2 denotes robust constraints, i.e., the prohibition of following collisions. 3 Unlike standard LMAPF, where an agent may immediately follow another, LMAPF-R2 guarantees a minimum safe distance between agents. Thus, if the leading agent is delayed at the current timestep, the following agent can still safely execute its cur- rent action and respond to the delay in the next timestep. The second “R” denotes rotational constraints. Due to orienta- tion, reaching an adjacent vertex may require one to three timesteps even in the absence of other agents. LMAPF-R2 operates in a lifelong setting where agents are continuously assigned new goal vertices by an external task allocator whenever they reach their current goals. The system runs for a fixed time horizon, and the objective is to maximize throughput, defined as the average number of goals reached per timestep across all agents. 3 Related Work Following the pioneering work PRIMAL (Sartoretti et al. 2019), numerous studies have explored learning-based plan- 3 In k-robust MAPF (Atzmon et al. 2020b), prohibiting following collisions is equivalent to 1-robust MAPF, which is sufficient for reactive neural policies. ners for (L)MAPF. Some approaches learn policies from scratch using reinforcement learning (RL) (Liu et al. 2020; Ma, Luo, and Pan 2021; Lin and Ma 2023), others leverage imitation learning (IL) from expert search algorithms (Li et al. 2021b; Andreychuk et al. 2025b; Veerapaneni et al. 2025a; Jiang et al. 2025), and some combine RL and IL (Damani et al. 2021; Wang et al. 2023). Despite extensive research on search-based planners that address robust constraints (Atzmon et al. 2020b,a; Chen et al. 2021), rotational constraints (Zhang et al. 2023; Jiang et al. 2024; Tao and Yu 2025; Yukhnevich and Andreychuk 2025), and more complex kinematic constraints (Wen, Liu, and Li 2022; Yan and Li 2025; Veerapaneni et al. 2025b) for real-world scenarios, few studies have investigated such constraints for learning-based (L)MAPF planners. One ex- ception is (Chan et al. 2022), which extends PRIMAL to handle rotations with an ad hoc deadlock-avoidance mecha- nism based on action counting during inference. This work explores orthogonal methods that seamlessly integrate search algorithms into both training and inference, enabling efficient coordination under both robust and rotational constraints. There has also been research on learning-based MAPF planners in continuous space for more complex kinodynamic settings, such as velocity and force control (Dergachev et al. 2025; Pshenitsyn, Panov, and Skrynnik 2026; Hu et al. 2025; Huo et al. 2026). However, as a tradeoff, these methods typ- ically focus on relatively open environments with at most a few tens of agents and a one-shot task formulation. By con- trast, we consider lifelong scenarios with high agent densities and long execution horizons. Our agent policy learning builds upon prior research addressing collision resolution for neural policy outputs. Early methods froze agents’ movements upon detecting colli- sions (Sartoretti et al. 2019), which proved highly inefficient. More recently, CS-PIBT (Veerapaneni et al. 2024) applied PIBT (Okumura et al. 2022), a lightweight search algorithm, to greedily resolve such collisions, and it has since become the de facto standard in state-of-the-art approaches (Jiang et al. 2025; Jain et al. 2026a,b). Inspired by CS-PIBT, we integrate a variant of Causal PIBT (Okumura, Tamura, and Défago 2021) into agent policy learning to efficiently han- dle robust and rotational constraints while resolving agents’ collisions and propagating their intentions. Our environment policy learning is adapted from guidance graph optimization (GGO) (Zhang et al. 2024), which pro- vides global guidance for agents’ movements. It formulates the guidance graph as edge costs on the map and applies CMA-ES (Hansen 2016), a derivative-free evolutionary al- gorithm, to optimize either the edge costs directly or the parameters of a small neural network that generates them. In contrast, our approach formulates GGO within an RL frame- work and jointly trains it with the agent policy. Joint optimization of agents and environments has rarely been explored for (L)MAPF. Prior work (Gao, Yang, and Prorok 2025; Li, Amir, and Prorok 2025) investigated the co-design of environment layouts and agent policies but was limited to small-scale scenarios involving at most 16 agents. In contrast, our work targets more practical settings by keep- ing the environment layout fixed and optimizing only the guidance graphs to coordinate hundreds of agents. 4 Method We first present the Markov Decision Process (MDP) formu- lation in Section 4.1, followed by agent policy learning with Causal PIBT in Section 4.2 and environment policy learning with GGO in Section 4.3. Finally, we describe the joint RL procedure in Section 4.4. Pseudocode and additional algo- rithmic details are provided in the appendix. 4.1 MDP Formulation Figure 2 illustrates the MDP formulation of SJRL from the perspective of the environment and the red agent. For joint optimization, at timestep 0, we first sample edge costs from the environment policy and then perform backward Dijkstra search to compute the minimum-cost distances between all pairs of states in the graph, where each state corresponds to a vertex–orientation pair. The resulting heuristic distances for states within an agent’s 11× 11 local view are then provided as input to the agent policy network to guide movement, as detailed in Section 4.2. Then, agents begin acting from timestep 1. For an agent, if it is free at a timestep—namely, it has not yet decided its next vertex—we sample a next vertex from the agent policy as its subgoal. Causal-PIBT is then applied as post-processing to resolve collisions among subgoals and propagate agents’ intentions, as detailed in Section 4.2. Once its subgoal is de- termined, the agent becomes busy and commits to reaching it using greedy actions. Due to the robust constraint, it may need to wait for other agents to move away before advancing to the next vertex. The agent receives a reward of−1 for each action taken to penalize timestep consumption. Upon reaching its subgoal, the agent becomes free again and selects a new subgoal. At this decision point, it also receives an additional reward of dist(s prev ,g)−dist(s curr ,g), wheres prev ands curr denote the agent’s state at the previous and current decision points, respectively. dist(s,g) is the minimum number of timesteps required to reach the goal vertex g from state s. It is worth noting that this distance is used for progress measurement, which is conceptually different from the previously computed heuristic distance used for movement guidance. This addi- tional reward measures the progress made toward the goal since the previous decision. To encourage coordination, each agent additionally receives a team reward at every timestep equal to the average reward of all agents within its 5×5 local view. The reward for the environment policy is defined as the sum of the rewards of all agents. 4.2 Agent Policy Learning For now, we assume that the environment policy is fixed and has already computed the heuristics used to guide movement. We now turn to the agent policy, illustrated in Figure 4. Our design builds upon the neural architecture of the state-of-the- art planner SILLM (Jiang et al. 2025). As in SILLM, the input to the neural network includes the locations of static obstacles within the agent’s local view, represented as a binary feature map. To facilitate collision Figure 2: Markov Decision Process (MDP) from the perspective of the environment and the red agent. Upper circles represent states, and yellow ones denote states where a neural policy needs to make decisions. The circle in a grid represents a robot, with a small bar indicating its orientation. The dashed square of the same color as the robot indicates its subgoal. In this MDP, the environment first generates edge costs at timestep 0, where darker arrows indicate lower costs and thus preferred movement directions. Agents begin to take actions at timestep 1. Suppose the red agent is free at timestep t and selects the vertex below it as its subgoal. It then becomes busy and moves greedily toward the subgoal unless its action is blocked by another agent (e.g., the green agent at timestep t + 1, whose subgoal is the vertex to its right). Once the subgoal is reached, the agent becomes free again and needs to select its next subgoal (e.g., the red agent at timestep t + 3). Additional details are described in Section 4.1. Figure 3: Illustration of the exploration challenge for nine agents in a long corridor under random exploration at the start of RL. Black and white cells denote obstacles and free space; red circles represent agents, and small black bars indicate their orientations. resolution, we maintain a priority for each agent following PIBT (Okumura et al. 2022). These priorities are encoded as a ternary feature map, where 1 indicates a higher-priority agent, −1 indicates a lower-priority agent, and 0 denotes other locations. We also include an additional channel to indicate whether an agent is currently busy or free. Un- like SILLM, our setting considers four possible orientations at each location in the local view. Accordingly, we have a four-channel heuristic feature map, with each channel corre- sponding to one orientation. In terms of architecture, we adopt the same convolutional neural network (CNN), communication module, and MLP as SILLM. In addition, we introduce two skip connections that directly inject heuristic information into the outputs of the CNN and the communication module. Specifically, these skip connections concatenate the learned feature vectors with the heuristic distances from the candidate next vertices to the goal. This design establishes a more direct dependency between the agent’s decisions and the heuristic guidance, thereby strengthening the influence of the environment policy and facilitating its optimization. As described in the MDP formulation, the neural policy predicts the intended next vertex as a subgoal rather than a primitive action. We find that directly predicting primitive actions makes exploration substantially more challenging in multi-agent RL settings. Consider a sequence of agents in a long corridor (Figure 3): meaningful progress requires them to align in a common direction and move forward at certain timesteps. If all agents explore randomly during the early stages of RL training, the probability of achieving such coor- dination decreases exponentially with the number of agents in the corridor, rendering exploration prohibitively difficult. In contrast, predicting the next vertex as a subgoal and ex- ecuting greedy actions toward it induces a simple policy hierarchy that enables higher-level coordination and more effective exploration. We further replace the CS-PIBT (Veerapaneni et al. 2024) used in SILLM with a synchronized variant of Causal PIBT (Okumura, Tamura, and Défago 2021) to safeguard agents’ intended next vertices. Unlike the original CS-PIBT, only agents that are free at the current timestep participate in joint decision-making, while the current and subgoal ver- tices of busy agents are treated as obstacles. In addition, we prohibit cyclic movements, as they would result in deadlocks during execution under the robust constraint. Aside from these modifications, our synchronized Causal PIBT follows the main logic of the CS-PIBT used in SILLM (Jiang et al. 2025). Specifically, agents make decisions in priority order, employing a priority inheritance mechanism when a higher- priority agent attempts to move to a vertex currently occu- pied by a lower-priority agent (Okumura et al. 2019; Oku- mura, Tamura, and Défago 2021). During decision-making, an agent first tries the highest-probability choice predicted by the neural policy, and then considers the remaining can- didates in ascending order of their heuristic distances. Notably, collision resolution for free agents considers only the robust constraints imposed by busy agents, but not those imposed by other free agents, since we allow a high-priority free agent to push away a low-priority free agent from its current vertex. Consequently, like other PIBT algorithms (Okumura et al. 2022; Okumura, Tamura, and Figure 4: Neural policies for the environment and two communicating agents. Orange blocks denote learning modules, blue denotes search modules, green represents features, yellow represents decisions produced by neural policies, and red represents decisions post-processed by search. The purple lines indicate skip connections and the associated feature concatenations. Défago 2021; Veerapaneni et al. 2024), through depth-first search with priority inheritance, Causal PIBT can identify chains of free agents a 1 ,a 2 ,...,a k , where agent a i moves to the current vertex of agent a i+1 for all i < k, and a k moves to an unoccupied vertex. From another perspective, this process can be viewed as the propagation of a 1 ’s inten- tion along the chain, as each a i pushes away a i+1 from its current vertex. If such a chain lies in the long corridor shown in Figure 3, intention propagation can rapidly couple the de- cisions of the agents in the corridor, increasing the likelihood that they move in a common direction. As a result, the agents are more likely to form a coordinated movement pattern, enabling more efficient exploration of joint decisions. After Causal PIBT is invoked, every agent is assigned a subgoal and becomes busy. Each agent then commits to reaching its subgoal by taking greedy actions: it first rotates until its orientation is correct, waits if the subgoal is occupied by another agent, and otherwise moves to the subgoal. If the subgoal coincides with its current vertex, the agent waits for one timestep before becoming free and making a new decision at the following timestep. The benefits of predicting the next vertex as a subgoal to induce a hierarchical policy and applying Causal PIBT for intention propagation are demonstrated experimentally in Section 5.3. It is worth noting that Causal PIBT is applied during both training and inference. During training, it is treated as part of the environment, allowing PPO (Schulman et al. 2017) to op- timize the policy directly without correcting policy gradients for the action modifications introduced by Causal PIBT. 4.3 Environment Policy Learning We now turn to the environment policy shown in Figure 4, which is implemented as a CNN consisting of five 3 × 3 convolutional layers with padding 1, ensuring that the final output has the same spatial dimensions as the input. The input to the CNN includes the binary obstacle fea- ture map and the simulation statistic feature maps proposed in (Zhang et al. 2024). Specifically, we run an existing plan- ner (in our case, the agent policy trained during the warm-up stage, described in Section 4.4) to simulate LMAPF multiple times, record the visitation frequency of each vertex and the traversal frequency of each edge, and normalize these statis- tics as input features. Notably, these features are precomputed and remain fixed throughout both training and inference. For each edge, the CNN outputs the mean and variance of a Gaussian distribution over its cost. Since each vertex has five outgoing edges (four directional moves and waiting), the CNN produces a total of 10 output channels. Invalid edges are masked according to the graph structure. During training, edge costs are sampled from the predicted Gaussian distributions, whereas during inference, the means are used. To bound edge costs within a predefined range, we apply an arctan transformation followed by a linear transformation, mapping each cost to the interval [1, 10]. By adjusting the bias term of the prediction layer, we can initialize the mean edge costs to any value within this interval. For example, a bias of 0 corresponds to an initial mean edge cost of 5.5 after the transformation. The effect of manually initializing edge costs is analyzed in the appendix. After the environment policy generates the edge costs, backward Dijkstra search is performed to compute the minimum-cost distances between all pairs of states in the graph. These distances are then provided as heuristic fea- tures to the agent policy, guiding the agents’ decisions. The environment policy can also be interpreted from an- other perspective: each edge is treated as a virtual agent that predicts its own cost. These virtual agents jointly shape the overall cost structure, which in turn determines the heuris- tic guidance for the movements of real agents. Accordingly, we adopt MAPPO (Yu et al. 2022) to train the environment policy, with all virtual agents sharing the same reward. 4.4 Joint Reinforcement Learning Since the agent and environment policies are formulated within a unified RL framework, they can be trained jointly using shared simulations. However, random exploration by the agent policy during the early stages of training would introduce high variance into the optimization of the environ- ment policy. To mitigate this issue, we first warm up the agent policy using uniform edge costs of 5.5, and then proceed to joint training. Additional training details are provided in the appendix. It is worth noting that, during inference, the edge costs and heuristic distances produced by the environment policy can be precomputed once for each map, requiring only the agent policy to be executed at each timestep. The edge costs can also be updated periodically to adapt to evolving traffic conditions, as in (Zang et al. 2025); we leave this extension for future work. 5 Experiments We conduct experiments on six maps with diverse obsta- cle structures (visualized in Figure 5) from the Moving-AI benchmark (Stern et al. 2019) and SILLM (Jiang et al. 2025). For each map, we train a policy with 256 agents and evaluate it with 32–320 agents in increments of 32. Each evaluation runs for 512 timesteps. In all cases, the inference time per timestep is below 0.05 seconds on an NVIDIA RTX 4090D GPU. Since maps are typically known in advance in real- world LMAPF applications, such as automated warehouses, we follow the state-of-the-art methods, SILLM (Jiang et al. 2025) and MAGAT+ (Jain et al. 2026b), and focus on gen- eralization across initial states, goal locations, and numbers of agents rather than across maps. Unless otherwise speci- fied, we report results with 256 agents, except for the main joint-learning experiment in Section 5.1. Additional results, including ablation on the network skip connections and val- idation with physical robots, are provided in the appendix. 5.1 The Benefits of Joint Learning We first compare our SJRL with the following: 1. NORL: No RL. Causal-PIBT (Okumura, Tamura, and Défago 2021), a strong search-based baseline that relies entirely on hand- crafted heuristics for planning. 2. SARL: Search-Aided Agent RL. Only the agent policy is trained, with uniform edge costs as the guidance graph. 3. SERL: Search-Aided Environment RL. Only the environment policy is trained to generate the guidance graph, with Causal-PIBT as the agent planner. 4. CMA-ES: the original GGO method (Zhang et al. 2024). The guidance graph is optimized using CMA-ES instead of RL, with Causal-PIBT as the agent planner. The results in Figure 5 show that SJRL significantly out- performs the strong search-based baseline, Causal-PIBT, par- ticularly as the number of agents increases. SJRL also consis- tently outperforms SARL and SERL, demonstrating the ben- efit of jointly optimizing the agent and environment policies and suggesting that these two policies contribute to LMAPF coordination in a complementary manner. NORL SARL SERL SJRL CMA-ES 326496 128160192224256288320 Number of Agents 1 2 3 Throughput (a) Warehouse (33× 57, 20%) 326496 128160192224256288320 Number of Agents 1 2 3 4 5 Throughput (b) Sortation (33× 57, 16%) 326496 128160192224256288320 Number of Agents 0.5 1.0 1.5 2.0 Throughput (c) Paris (64× 64, 9%) 326496 128160192224256288320 Number of Agents 2 4 6 Throughput (d) Empty (32× 32, 25%) 326496 128160192224256288320 Number of Agents 1 2 3 Throughput (e) Random-10 (32× 32, 28%) 326496 128160192224256288320 Number of Agents 1.0 1.5 2.0 Throughput (f) Random-20 (32× 32, 31%) Figure 5: Ablation study on joint policy learning (Sec- tion 5.1). Curves show the mean throughput, with shaded regions indicating the standard deviation. Dashed vertical lines indicate the number of agents used for training. Maps with 256 randomly placed agents are shown in the top-left corner of each subfigure (best viewed when zoomed in). Black and gray cells denote obstacles and free space, re- spectively; red circles represent agents, and small black bars indicate their orientations. The size and the agent density of each map are shown in the parentheses following its name. NORLSERLSARLSJRL WarehouseSortationParisEmptyRandom-10Random-20 0 20 40 MPD 20.2 20.5 30.1 14.4 14.1 15.3 26.2 27.3 36.5 19.3 18.8 18.7 22.3 25.1 34.0 17.6 16.1 17.0 28.3 29.2 38.9 20.9 19.8 19.5 Figure 6: Comparison of mean pairwise distance (MPD) between different policies (Section 5.1). SERL achieves performance comparable to CMA-ES overall, while performing slightly better on the Warehouse, Sortation, and Random-10 maps. These findings demonstrate the potential of optimizing the guidance graph through rein- forcement learning with more complex network structures. We also compare different methods in Figure 6 using the HMAGATMAGAT+SILLMSARLSJRL WarehouseSortationParisEmptyRandom-10Random-20 0 2 4 Throughput 2.29 2.88 1.92 3.43 3.03 2.07 2.26 2.88 2.01 3.58 3.02 2.18 2.30 2.96 2.04 3.65 3.11 2.25 2.64 3.73 1.91 4.66 3.50 2.18 3.24 4.18 2.43 5.04 3.54 2.38 Figure 7: Comparison between SARL, SJRL and other state- of-the-art methods (Section 5.2). mean pairwise distance (MPD), defined as MPD = X i,j p i p j dist ij , where p i is the empirical probability that vertex i is occupied by some agent, and dist ij is the shortest-path distance be- tween verticesi andj. Both the agent and environment policy learning increase the MPD, indicating that agents are more spatially dispersed and therefore experience less congestion. 5.2 Comparison with State-of-the-Art Methods We further compare SARL and SJRL with other state-of-the- art (SoTA) methods, including SILLM (Jiang et al. 2025), MAGAT+ (Jain et al. 2026b), and HMAGAT (Jain et al. 2026a), in Figure 7, using differential-drive robots as in (Yan et al. 2025) and the Action Dependency Graph (ADG) (Hönig et al. 2019) as the execution framework. The latter two SoTA methods are adapted to the LMAPF setting following the best practices in SILLM. SARL outperforms other SoTA meth- ods on four of the six maps and performs on par with them on the remaining two, while SJRL consistently outperforms all of them. A key reason is that SARL and SJRL adopt the LMAPF-R2 model, whereas the other methods use the stan- dard LMAPF model. The results suggest that, although ADG can accommodate diverse robot kinematics during execution, there is a need to study more realistic yet scalable LMAPF models, such as LMAPF-R2, for learning-based planners. In principle, the other three SoTA methods, which rely on IL, could also be adapted to the LMAPF-R2 model. However, our preliminary investigation suggests that such an adaptation would require non-trivial modifications to mul- tiple components, including the expert planner, collision- shielding mechanism, and training algorithm, and may lead to non-negligible performance degradation compared with the standard model. We therefore leave the adaptation of IL methods to the LMAPF-R2 model for future work. 5.3 Policy Hierarchy and Intention Propagation Finally, we compare our variant of Causal-PIBT with two alternative straightforward adaptations of CS-PIBT as collision-shielding mechanisms for agent RL: 1. Naive Action-Based Collision Shielding (NACS): the agent policy predicts primitive actions rather than next vertices, and a naive priority-based collision-shielding method is applied to resolve action conflicts. 2. Naive Vertex-Based Collision Shielding (NVCS): the agent policy predicts the next vertices, and a naive NACSNVCSCausal PIBT WarehouseSortationParisEmptyRandom-10Random-20 0 2 4 Throughput 0.25 1.44 0.55 2.82 0.12 0.02 0.73 2.68 0.21 4.63 0.84 0.06 1.95 3.94 1.49 5.34 2.63 1.32 Figure 8: Comparison between methods with different deci- sion spaces and collision-shielding strategies (Section 5.3). priority-based collision-shielding method is applied to resolve vertex conflicts. The naive priority-based collision shielding in the robust setting works as follows. Regardless of whether the agent policy predicts actions or next vertices, all free agents make decisions sequentially in their priority order: 1. If a vertex was occupied in the previous timestep, no agent can take this vertex for the next movement in the current timestep due to the robust constraint. 2. If a higher-priority agent has taken a vertex for the next movement, a lower-priority agent can no longer take this vertex for the next movement in the current timestep. Both NACS and NVCS ensure safe plans, but un- like Causal-PIBT, they cannot propagate agents’ intentions through depth-first search and priority inheritance. As shown in Figure 8, NACS underperforms NVCS in most cases, likely due to the lack of a policy hierarchy. More- over, both methods perform substantially worse than Causal- PIBT, with the largest performance gaps on the warehouse and random maps. We attribute this primarily to the explo- ration difficulty discussed in Section 4.2. Specifically, the warehouse map contains multiple aisle segments of length 3, while the random maps contain long, narrow corridors, both of which make coordinated exploration particularly challeng- ing. In contrast, our variant of Causal-PIBT benefits from the policy hierarchy and intention propagation, largely mitigat- ing this difficulty. These results further suggest that straight- forward adaptations to more complex robot kinematics may lead to poor performance, underscoring the importance of carefully designing and studying new LMAPF models for learning-based planners. 6 Conclusion Achieving strong performance in real-world robotic systems requires balancing abstraction and realism in problem model- ing. In this work, we study a more realistic yet scalable model for learning-based LMAPF planners, termed LMAPF-R2, which incorporates robust and rotational constraints. To address the coordination challenges introduced by LMAPF-R2, we propose SJRL, guided by two key princi- ples: (1) leveraging the complementary strengths of search and learning, and (2) optimizing coordination from both the agent and environment perspectives. We hope this work encourages future research on increas- ingly realistic yet scalable problem formulations for learning- based LMAPF, facilitating the deployment of learning-based planners in real-world applications. References Andreychuk, A.; Yakovlev, K.; Panov, A.; and Skrynnik, A. 2025a. Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning. In IEEE/RSJ Interna- tional Conference on Intelligent Robots and Systems (IROS), 10564–10571. IEEE. Andreychuk, A.; Yakovlev, K.; Panov, A.; and Skrynnik, A. 2025b. MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 39, 23126–23134. Atzmon, D.; Stern, R.; Felner, A.; Sturtevant, N. R.; and Koenig, S. 2020a. Probabilistic Robust Multi-Agent Path Finding. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), volume 30, 29–37. Atzmon, D.; Stern, R.; Felner, A.; Wagner, G.; Barták, R.; and Zhou, N.-F. 2020b. Robust Multi-Agent Path Finding and Executing. Journal of Artificial Intelligence Research, 67: 549–579. Chan, F. K. S.; Law, Y. N.; Lu, B.; Chick, T.; Lai, E. S. B.; and Ge, M. 2022. Multi-Agent Pathfinding for Deadlock Avoidance on Rotational Movements. In Proceedings of the International Conference on Control, Automation, Robotics and Vision (ICARCV), 765–770. Chen, Z.; Harabor, D.; Li, J.; and Stuckey, P. J. 2024. Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding. In Proceedings of the AAAI Conference on Artificial Intelli- gence (AAAI), volume 38, 20674–20682. Chen, Z.; Harabor, D. D.; Li, J.; and Stuckey, P. J. 2021. Symmetry Breaking for k-Robust Multi-Agent Path Finding. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 35, 12267–12274. Damani, M.; Luo, Z.; Wenzel, E.; and Sartoretti, G. 2021. PRIMAL 2 : Pathfinding via Reinforcement and Imitation Multi-Agent Learning-Lifelong. IEEE Robotics and Automa- tion Letters, 6(2): 2666–2673. Dergachev, S.; Pshenitsyn, A.; Panov, A.; Skrynnik, A.; and Yakovlev, K. 2025. CoRL-MPPI: Enhancing MPPI with Learnable Behaviours for Efficient and Provably- Safe Multi-Robot Collision Avoidance. arXiv preprint arXiv:2511.09331. Duhan, T.; He, C.; and Sartoretti, G. 2026. P3GASUS: Pre- Planned Path Execution Graphs for Multi-Agent Systems at Ultra-Large Scale. IEEE Robotics and Automation Letters, 11(2): 1274–1281. Gao, Z.; Yang, G.; and Prorok, A. 2025. Co-Optimizing Reconfigurable Environments and Policies for Decentral- ized Multiagent Navigation. IEEE Transactions on Robotics, 4741–4760. Hansen, N. 2016. The CMA Evolution Strategy: A Tutorial. arXiv preprint arXiv:1604.00772. Hönig, 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(2): 1125–1131. Hu, T.; Zhang, Z.; Zhu, C.; Xu, G.; Wu, Y.; Wu, H.; and Liu, Y. 2025. MARF: Cooperative Multi-Agent Path Finding with Reinforcement Learning and Frenet Lattice in Dynamic En- vironments. In IEEE International Conference on Robotics and Automation (ICRA), 12607–12613. Huo, L.; Mao, J.; San, H.; Li, R.; and Xuan, Z. 2026. Mean- Field Deep Reinforcement Learning for Multi-Agent Path Finding. IEEE Robotics and Automation Letters, 11(5): 5278–5285. Jain, R.; Okumura, K.; Amir, M.; Liò, P.; and Prorok, A. 2026a. Pairwise is Not Enough: Hypergraph Neural Net- works for Multi-Agent Pathfinding. In International Confer- ence on Learning Representations (ICLR). Jain, R.; Okumura, K.; Amir, M.; and Prorok, A. 2026b. Graph Attention-Guided Search for Dense Multi-Agent Pathfinding. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 40, 29504–29512. Jiang, H.; Wang, Y.; Veerapaneni, R.; Duhan, T.; Sartoretti, G.; and Li, J. 2025. Deploying Ten Thousand Robots: Scal- able Imitation Learning for Lifelong Multi-Agent Path Find- ing. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 1–7. Jiang, H.; Zhang, Y.; Veerapaneni, R.; and Li, J. 2024. Scal- ing Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities. In Pro- ceedings of the International Symposium on Combinatorial Search (SoCS), 234–242. Li, H. X.; Amir, M.; and Prorok, A. 2025. Scaling Multi- Agent Environment Co-Design with Diffusion Models. arXiv preprint arXiv:2511.03100. Li, J.; Tinka, A.; Kiesel, S.; Durham, J. W.; Kumar, T. S.; and Koenig, S. 2021a. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses. In Proceedings of the AAAI Con- ference on Artificial Intelligence (AAAI), volume 35, 11272– 11281. Li, Q.; Lin, W.; Liu, Z.; and Prorok, A. 2021b. Message- Aware Graph Attention Networks for Large-Scale Multi- Robot Path Planning. IEEE Robotics and Automation Letters, 6(3): 5533–5540. Lin, Q.; and Ma, H. 2023. SACHA: Soft Actor-Critic with Heuristic-Based Attention for Partially Observable Multi- Agent Path Finding. IEEE Robotics and Automation Letters, 8(8): 5100–5107. Liu, Z.; Chen, B.; Zhou, H.; Koushik, G.; Hebert, M.; and Zhao, D. 2020. MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments. In Proceedings of the IEEE/RSJ Interna- tional Conference on Intelligent Robots and Systems (IROS), 11748–11754. Ma, Z.; Luo, Y.; and Pan, J. 2021. Learning Selective Com- munication for Multi-Agent Path Finding. IEEE Robotics and Automation Letters, 7(2): 1455–1462. Okumura, K.; Machida, M.; Défago, X.; and Tamura, Y. 2022. Priority Inheritance with Backtracking for Itera- tive Multi-Agent Path Finding. Artificial Intelligence, 310: 103752. Okumura, K.; Machida, M.; Défago, 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. Okumura, K.; Tamura, Y.; and Défago, X. 2021. Time- Independent Planning for Multiple Moving Agents. In Pro- ceedings of the AAAI Conference on Artificial Intelligence (AAAI), 11299–11307. Pshenitsyn, A.; Panov, A.; and Skrynnik, A. 2026. CAMAR: Continuous Actions Multi-Agent Routing. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 29651–29659. Sartoretti, G.; Kerr, J.; Shi, Y.; Wagner, G.; Kumar, T. S.; Koenig, S.; and Choset, H. 2019. PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning. IEEE Robotics and Automation Letters, 4(3): 2378–2385. Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; and Klimov, O. 2017. Proximal Policy Optimization Algorithms. arXiv preprint arXiv:1707.06347. Stern, R.; Sturtevant, N.; Felner, A.; Koenig, S.; Ma, H.; Walker, T.; Li, J.; Atzmon, D.; Cohen, L.; Kumar, T.; et al. 2019. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. In Proceedings of the International Symposium on Combinatorial Search (SoCS), volume 10, 151–158. Tao, Z.; and Yu, C. 2025. Fast Multi-Agent Path Planning with Turn Actions: A Priority Inheritance Approach. In IEEE International Conference on Automation Science and Engineering (CASE), 2024–2029. Varambally, S.; Li, J.; and Koenig, S. 2022. Which MAPF Model Works Best for Automated Warehousing? In Pro- ceedings of the international symposium on combinatorial search, volume 15, 190–198. Veerapaneni, R.; Jakobsson, A.; Ren, K.; Kim, S.; Li, J.; and Likhachev, M. 2025a. Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large-Scale Imitation Learning for MAPF. In Proceedings of the IEEE In- ternational Conference on Robotics and Automation (ICRA), 10229–10236. Veerapaneni, R.; Tang, A.; He, H.; Zhao, S.; Shah, V.; Cen, Y.; Ji, Z.; Olin, G.; Arrizabalaga, J.; Shaoul, Y.; et al. 2025b. Conflict-Based Search as a Protocol: A Multi-Agent Motion Planning Protocol for Heterogeneous Agents, Solvers, and Independent Tasks. arXiv preprint arXiv:2510.00425. Veerapaneni, R.; Wang, Q.; Ren, K.; Jakobsson, A.; Li, J.; and Likhachev, M. 2024. Improving Learnt Local MAPF Policies with Heuristic Search. In Proceedings of the Inter- national Conference on Automated Planning and Scheduling (ICAPS), 597–606. Wang, Y.; Xiang, B.; Huang, S.; and Sartoretti, G. 2023. SCRIMP: Scalable Communication for Reinforcement- and Imitation-Learning-Based Multi-Agent Pathfinding. In Pro- ceedings of the IEEE/RSJ International Conference on Intel- ligent Robots and Systems (IROS), 9301–9308. Wen, L.; Liu, Y.; and Li, H. 2022. CL-MAPF: Multi-Agent Path Finding for Car-Like Robots with Kinematic and Spa- tiotemporal Constraints. Robotics and Autonomous Systems, 150: 103997. Yan, J.; and Li, J. 2025. Multi-Agent Motion Planning for Differential Drive Robots Through Stationary State Search. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 39, 23360–23368. Yan, J.; Li, Z.; Kang, W.; Zheng, K.; Zhang, Y.; Chen, Z.; Zhang, Y.; Harabor, D.; Smith, S. F.; and Li, J. 2025. Advancing MAPF Towards the Real World: A Scalable Multi-Agent Realistic Testbed (SMART). arXiv preprint arXiv:2503.04798. Yu, C.; Velu, A.; Vinitsky, E.; Gao, J.; Wang, Y.; Bayen, A.; and Wu, Y. 2022. The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games. In Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS). Yukhnevich, E.; and Andreychuk, A. 2025. Enhanc- ing PIBT via Multi-Action Operations. arXiv preprint arXiv:2511.09193. Zang, H.; Zhang, Y.; Jiang, H.; Chen, Z.; Harabor, D.; Stuckey, P. J.; and Li, J. 2025. Online Guidance Graph Op- timization for Lifelong Multi-Agent Path Finding. In Pro- ceedings of the AAAI Conference on Artificial Intelligence (AAAI), 14726–14735. Zhang, Y.; Harabor, D.; Le Bodic, P.; and Stuckey, P. J. 2023. Efficient Multi-Agent Path Finding with Turn Actions. In Proceedings of the International Symposium on Combinato- rial Search (SoCS), 119–127. Zhang, Y.; Jiang, H.; Bhatt, V.; Nikolaidis, S.; and Li, J. 2024. Guidance Graph Optimization for Lifelong Multi- Agent Path Finding. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 311–320. Algorithm 1: Synchronized Causal PIBT 1: // For simplicity, the following required data are global variables that can be accessed by PIBT. Require: Agent priority p i , goal g i , status s i Require: Agent vertex v i , orientation o i , subgoal sg i Require: Distance heuristics h Require: Subgoal vertex bv i predicted by the agent policy Ensure: Update sg i for IDLE agents Ensure: Select actions for all agents. 2: // O b : Vertices occupied by BUSY agents 3: // O c : Vertices occupied currently by IDLE agents 4: // O n : Vertices occupied next by IDLE agents 5: Initialize empty hash maps O b , O c , and O n , mapping each occupied vertex to its corresponding agent index. 6: for each agent i do 7: if s i = IDLE then 8:O c [v i ] = i 9:sg i = NULL 10: else 11:O b [v i ] = i 12:O b [sg i ] = i 13: for each IDLE agent i in priority order do 14: if sg i == NULL then 15:PIBT(i,i,v i ,O b ,O c ,O n ) 16: for each agent i do 17: Greedily select an action for agent i toward its sub- goal sg i , subject to the robust constraint. This appendix provides additional algorithm pseudocode, training details, experimental results, and physical-robot val- idation that were omitted from the main paper due to space limitations. A Algorithm Pseudocode We describe the pseudocode of our Causal PIBT variant in Algorithms 1 and 2. Since the algorithm closely follows the original PIBT (Okumura et al. 2019) and the pseudocode includes detailed comments, we do not explain it line by line. Instead, we highlight two key points of the algorithm, which are also the main differences from the original PIBT. 1. The PIBT procedure in our algorithm plans subgoals for IDLE agents rather than their primitive actions (Algo- rithm 2, Line 16 and 26). During planning, both the cur- rent and subgoal vertices of BUSY agents are treated as obstacles (Algorithm 2, Line 7). After PIBT reasoning, each agent greedily selects its primitive action toward its assigned subgoal (Algorithm 1, Line 17). 2. The PIBT procedure largely ignores the robust constraint to facilitate intention propagation among agents by con- sidering only edge collisions rather than following colli- sions (Algorithm 2, Line 11-13). The only exception is that cyclic movements are disallowed, as allowing them would cause deadlocks during execution (Algorithm 2, Line 5). The robust constraint is instead enforced primar- ily during the subsequent action selection stage (Algo- rithm 1, Line 17). Algorithm 2: PIBT Recursion Require: current agent index i Require: root agent index r Require: root agent vertex rv Require: Vertices occupied by BUSY agents O b Require: Vertices occupied currently by IDLE agents O c Require: Vertices occupied next by IDLE agents O n Ensure: Update sg i for agent i and return if PIBT succeeds 1: function PIBT(i,r,rv,O b ,O c ,O n ) 2: Sort candidate next vertices for agent i, by priori- tizing the vertex bv i predicted by the agent policy and then ranking the remaining vertices in ascending order of their heuristic distances to the goal according to h. 3: for nv in sorted candidate next vertices do 4:// cyclic movement 5:if i == r and nv == rv then continue 6:// collision with a BUSY agent 7:if nv ∈ O b then continue 8:// vertex collision with an IDLE agent 9:if nv ∈ O n then continue 10:// edge collision with an IDLE agent 11:if nv ∈ O c then 12:j = O c [nv] 13:if j ̸= i∧ sg j == v i then continue 14:// reserve the vertex nv as the subgoal for agent i 15:O n [nv] = i 16:sg i = nv 17:// priority inheritance 18:if nv ∈ O c then 19:j = O c [nv] 20:if j ̸= i∧ sg j == NULL then 21:succ =PIBT(j,r,rv,O b ,O c ,O n ) 22:if ¬succ then continue 23:return True 24: // take the wait action as the fallback 25: O n [v i ] = i 26: sg i = v i 27: return False The computational complexity of synchronized Causal PIBT is identical to that of PIBT up to constant-factor over- head introduced by checking the robust constraints and busy- agent obstacles. B Training Details The warm-up training stage of the agent policy consists of 16 iterations, each with 64 simulations. The subsequent joint training stage consists of 128 iterations, each with 128 sim- ulations. Due to GPU memory constraints, during warm-up, we update the agent policy every 32 timesteps, although each simulation lasts 512 timesteps. During joint training, the agent policy is updated after each simulation, but only 32 of the 512 timesteps are sampled for learning. The environ- ment policy does not face this limitation because it makes decisions only once at the beginning of each simulation. For the agent policy, the critic network uses the same SARL-no-skipSARLSJRL-no-skipSJRL WarehouseSortationParisEmptyRandom-10Random-20 0 2 4 6 Throughput 1.72 3.77 1.25 5.28 2.63 1.21 1.95 3.94 1.49 5.34 2.63 1.32 2.51 4.03 1.51 5.55 3.18 1.31 3.11 4.86 1.88 5.94 3.31 1.58 Figure 9: Throughput comparison between policies with and without skip connections (Section C.1). architecture as the policy network in Section 4.2. For the environment policy, no critic network is used, and we directly normalize returns with their means and standard deviations as advantages. Our policies are trained using the PPO variants described in Section 4. Table 1 lists the key training hyperparame- ters, while additional details can be found in the experiment configurations provided in the source code. These hyperpa- rameters were selected through a grid search around com- monly used best-practice values, subject to computational constraints. The policies are trained on servers with 64 vCPUs (Intel® Xeon® Platinum 8481C), 4 RTX 4090D GPUs (24 GB each), and 320 GB of memory. On average, for each map, the warm- up training stage takes approximately 3 hours, and the joint training stage takes approximately 6 hours. In all cases, the mean inference time per timestep is below 0.05 seconds. Table 1: Key training hyperparameters. HyperparameterAgent Environment Learning rate5× 10 −5 5× 10 −4 Entropy loss weight00 Clipping ratio0.20.1 GAE λ0.95– Discount factor γ0.99– Batch size512 steps 64 simulations Max gradient norm1.01.0 Max KL divergence0.020.02 C Experiments By default, all experiment settings in this paper are evaluated by 32 runs with different random seeds, and we report the mean and standard deviation. Goal vertices for the agents are generated independently and uniformly at random from the set of all vertices in the graph. C.1 Ablation on Skip Connections We compare the network architectures with and without skip connections in Figure 9. Our results show that the skip con- nections improve the performance of both SARL and SJRL, but are more critical for SJRL. These results support our design choice of introducing skip connections to establish stronger dependencies between agent decisions and heuristic guidance, thereby facilitating guidance graph optimization in joint reinforcement learning. Causal-PIBT Causal-PIBT-w-init SARL SARL-w-init SJRL SJRL-w-init 326496 128160192224256288320 Number of Agents 1 2 3 4 Throughput (a) Warehouse 326496 128160192224256288320 Number of Agents 2 4 6 Throughput (b) Sortation Figure 10: Throughput comparison between uniform edge- cost initialization (solid lines) and expert edge-cost initial- ization (dashed lines) on warehouse and sortation maps (Sec- tion C.2). Curves show mean throughput, and shaded regions indicate the standard deviation. C.2 The Effect of Guidance Graph Initialization For the warehouse and sortation maps with one-cell-wide aisles, human experts typically assign handcrafted edge costs within the aisles to encourage one-way traffic. Specifically, the preferred directions alternate between consecutive rows (or columns) of aisles. We investigate whether SJRL can benefit from such expert priors. For these experiments, we initialize the edge cost of moving in the preferred direction to 3, the edge cost of moving in the opposite direction to 7, and all remaining edge costs to 5.5, as in the default setting. The results in Figure 10 show that Causal-PIBT, SARL, and SJRL all benefit substantially from expert initialization, with weaker planners obtaining larger performance gains. However, SJRL trained from scratch still fails to match the performance of SJRL with expert initialization, suggesting that it may become trapped in a suboptimal local optimum during training, potentially due to the local optimization nature of PPO. This observation indicates that developing more effective optimization paradigms for joint learning is a promising direction for future work. C.3 Physical-Robot Validation Due to hardware and software limitations, we validate our algorithm using 8 physical robots and 248 virtual robots in a challenging mixed-reality warehouse environment with mul- tiple aisles. Specifically, we use the OptiTrack Motion Cap- ture System to localize the physical robots and the P3GASUS Framework (Duhan, He, and Sartoretti 2026) to handle errors arising from execution disturbances and control inaccuracies. The throughput of different methods is compared in Table 2. A video demo is provided in the supplementary material. C.4 Comparison with State-of-the-Art Methods In Section 5.2, we report only the mean throughput for the 256-agent setting. The complete results for different numbers of agents are provided in Figure 11, and the conclusions are consistent with those reported in the main paper. It is worth noting that, under the standard MAPF model, the state-of-the-art methods HMAGAT, MAGAT+, and Table 2: Comparison of throughput in a mixed-reality ware- house environment. Algorithm Mean Std NORL0.72 0.04 SERL0.84 0.07 SARL0.87 0.06 SJRL1.01 0.07 HMAGAT SARL MAGAT+ SJRL SILLM 326496 128160192224256288320 Number of Agents 1 2 3 Throughput (a) Warehouse (33× 57, 20%) 326496 128160192224256288320 Number of Agents 1 2 3 4 Throughput (b) Sortation (33× 57, 16%) 326496 128160192224256288320 Number of Agents 0.5 1.0 1.5 2.0 2.5 Throughput (c) Paris (64× 64, 9%) 326496 128160192224256288320 Number of Agents 1 2 3 4 5 Throughput (d) Empty (32× 32, 25%) 326496 128160192224256288320 Number of Agents 1 2 3 Throughput (e) Random-10 (32× 32, 28%) 326496 128160192224256288320 Number of Agents 0.5 1.0 1.5 2.0 2.5 Throughput (f) Random-20 (32× 32, 31%) Figure 11: Comparison between SARL, SJRL and other state- of-the-art methods (Section C.4). Curves show the mean throughput, with shaded regions indicating the standard de- viation. Dashed vertical lines indicate the number of agents used for training. Maps with 256 randomly placed agents are shown in the top-left corner of each subfigure (best viewed when zoomed in). Black and gray cells denote obstacles and free space, respectively; red circles represent agents, and small black bars indicate their orientations. The size and the agent density of each map are shown in the parentheses fol- lowing its name. SILLM achieve very similar performance in most cases. This suggests that recent advances in communication and repre- sentation learning have substantially narrowed the perfor- mance gap under the standard model. A possible explanation is that these methods share two key design principles: (1) communication mechanisms that effectively capture relative NORLSERL SARLSJRL 0 102 205 307 410 512 Figure 12: Heatmaps of average wait actions on the Ware- house map. Black cells denote obstacles; red intensity indi- cates wait frequency. NORLSERL SARLSJRL 0 102 205 307 410 512 Figure 13: Heatmaps of average wait actions on the Sortation map. Black cells denote obstacles; red intensity indicates wait frequency. spatial relationships among agents, and (2) deeper CNN- or GNN-based architectures that stack multiple layers to provide strong representation capacity for processing the communi- cated information. Since this work directly adopts SILLM’s communica- tion module, an important direction for future work is to investigate more effective communication mechanisms for LMAPF-R2 and more complex kinematics. C.5 Wait Action Heatmaps In Section 1, we present the wait-action heatmaps only for the Sortation map in Figure 1. Here, we provide the correspond- ing heatmaps for all maps in Figures 12 to 17. The same conclusions can be drawn from these visualizations: SARL alleviates congestion locally, SERL balances traffic globally, and SJRL combines the benefits of both. NORLSERL SARLSJRL 0 102 205 307 410 512 Figure 14: Heatmaps of average wait actions on the Paris map. Black cells denote obstacles; red intensity indicates wait frequency. NORLSERL SARLSJRL 0 102 205 307 410 512 Figure 15: Heatmaps of average wait actions on the Empty map. Black cells denote obstacles; red intensity indicates wait frequency. NORLSERL SARLSJRL 0 102 205 307 410 512 Figure 16: Heatmaps of average wait actions on the Random- 10 map. Black cells denote obstacles; red intensity indicates wait frequency. NORLSERL SARLSJRL 0 102 205 307 410 512 Figure 17: Heatmaps of average wait actions on the Random- 20 map. Black cells denote obstacles; red intensity indicates wait frequency.