acceptodds
Under review as a conference paper at ICLR 2027

Reinforcement Learning of Spatial Guidance for Large-Scale Lifelong Multi-Agent Path Finding

Abstract

Large-scale applications of lifelong multi-agent path finding (LMAPF) call for computationally inexpensive movement decisions under changing traffic conditions and across varied layouts. We propose a navigation policy in which a convolutional network computes a shared spatial field over the map once per timestep and a compact goal-conditioned operator derives agents' movement preferences. The complete policy is trained end-to-end using average-reward reinforcement learning with throughput as the reward, without planner demonstrations or a separate online path planner. For structured and unstructured layouts, we train one policy per class on mixtures of small maps and deploy each without retraining on larger, unseen layouts and agent populations. Across six layouts with 10000 agents, our policies achieve throughput comparable to or higher than the strongest evaluated baselines. The proposed method executes each step in less than 10 ms, more than an order of magnitude faster than several established planners.

Primary area:
reinforcement learning
Keywords:
Lifelong multi-agent path finding, reinforcment learning, spatial guidance, computational efficiency, policy transfer

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_UDx2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates the problem of large-scale lifelong multi-agent pathfinding, in which agents continuously receive new goals, and the system’s objective is to maximize long-term task throughput. A core contribution of this work is the implementation of map-level computation reuse across all agents; this allows policies trained on a scale of approximately one hundred agents to be deployed in much larger systems. The proposed method is evaluated across various environments—including warehouses, sorting centers, urban settings, and randomized grid layouts—with scenarios scaling up to 10,000–20,000 agents. The empirical validation includes comparisons against both learning-based and planning-based MAPF baselines, as well as comprehensive multi-dimensional ablation studies.

Critical strengths
  1. The paper employs shared CNN features for global map and traffic state computation, which are then combined with target-aware soft shortest-path references, finite-depth route reweighting, and global destination assignment to generate actions. This design effectively leverages the structural property of Multi-Agent Path Finding (MAPF)—where numerous agents share the same spatial topology—thereby avoiding a scenario where computational overhead scales linearly with the number of agents based on the full cost of network inference.

  2. Although the policy is primarily trained on scenarios involving several dozen to approximately 140 agents, it can be deployed in environments with up to 10,000 agents, achieving competitive throughput across various settings, including warehouses, sorting facilities, urban environments, and randomized maps.

Critical weaknesses

Focusing solely on optimizing and reporting aggregate throughput may effectively mask issues such as individual agent starvation or unfairness. For instance, the average number of completed tasks could remain high even if some agents complete tasks frequently while others remain stationary for extended periods. Consequently, it is currently unclear whether the proposed method improves overall traffic flow or if it achieves higher aggregate throughput at the expense of a subset of agents.

Questions for authors

see Weaknesses

1 comment

We sincerely thank the reviewer for the positive assessment of our work. We agree that aggregate throughput cannot show how the completed tasks are spread over the agents.

The submission reported throughput only. For the revision we recorded the completed tasks and the longest stop of every agent, with 240,000 agent records per layout (Table 10, Appendix E.2). We summarise the spread by the coefficient of variation (CV, the standard deviation divided by the mean), as Jiang & Lu (2019) do.

LayoutTasks per agent (mean ± SD)CVCV of the upper boundCompleted / upper bound (mean ± SD)Agents with no completed task
Warehouse13.5 ± 2.30.170.170.94 ± 0.050
Sortation14.1 ± 2.40.170.170.97 ± 0.040
Berlin8.2 ± 3.00.370.150.62 ± 0.210.63%
Paris8.2 ± 3.10.380.170.65 ± 0.210.34%
Random 10%13.5 ± 2.00.150.150.95 ± 0.040
Random 20%11.9 ± 1.90.160.150.85 ± 0.063 of 240,000

The goal sequence of each agent also contributes to this spread, since some sequences need longer paths than others. To isolate the effect of the policy, we computed for every agent an upper bound, the number of tasks it would complete on shortest paths with no other agent on the map. The table gives the CV of this bound and the ratio of the completed tasks to it. The bound is built like the delay of one-shot MAPF, the number of steps a path takes beyond the shortest path (Li et al., 2021), and Asano et al. (2023) measure fairness in multi-robot navigation by a similar delay.

On warehouse, sortation and the two random layouts, whose structure is homogeneous, the CV is close to that of the upper bound and the ratio to the upper bound is nearly the same for all agents, so the spread comes mainly from the goal sequences. On Berlin and Paris, whose structure differs from region to region, the CV is more than twice that of the upper bound, the ratio varies widely between agents, and 0.6% and 0.3% of the agents complete no task within 2,500 steps. Figure 9 maps the delay of the tasks by goal location, and the delay is concentrated in some regions of each map. Agents that stand still for long are blocked by other agents in a local deadlock, and this occurs almost only on the two city layouts. We therefore hypothesise that the spread on the two city layouts comes from congestion at particular places, which the policy does not resolve, rather than from the objective as such. With the same objective, the spread on the other four layouts stays close to that of the upper bound.

Our policy gives no guarantee that every agent reaches its goal, such as the one PIBT has on graphs in which every pair of adjacent nodes lies on a simple cycle (Okumura et al., 2022). The revised conclusion states that we do not address fairness across agents and leaves a fairness-aware extension to future work (Jiang & Lu, 2019; Zimmer et al., 2021; Asano et al., 2023).

References

Hikaru Asano, Ryo Yonetani, Mai Nishimura, and Tadashi Kozuno. Counterfactual fairness filter for fair-delay multi-robot navigation. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 887–895, 2023.

Jiechuan Jiang and Zongqing Lu. Learning fairness in multi-agent systems. In Advances in Neural Information Processing Systems, volume 32, pp. 13854–13865, 2019.

Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J. Stuckey, and Sven Koenig. Anytime multi-agent path finding via large neighborhood search. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), pp. 4127–4135, 2021.

Keisuke Okumura, Manao Machida, Xavier Défago, and Yasumasa Tamura. Priority inheritance with backtracking for iterative multi-agent path finding. Artificial Intelligence, 310:103752, 2022.

Matthieu Zimmer, Claire Glanois, Umer Siddique, and Paul Weng. Learning fair policies in decentralized cooperative multi-agent reinforcement learning. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12967–12978, 2021.

Reviewer_jdkaOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents a reinforcement-learning approach for large-scale lifelong multi-agent path finding (LMAPF). Instead of running a separate neural network for each agent, the authors use a shared spatial field to guide the movement of all agents. The method has three main parts. A CNN first processes the map and current traffic conditions to generate movement scores. These scores are then combined with a soft shortest-path reference to determine each agent's preferred direction over a short planning horizon. Finally, a Sinkhorn-based allocation step adjusts the movement probabilities when multiple agents try to move to the same cell. The policy is trained using average-reward reinforcement learning, where the reward is based on the number of completed tasks. It does not require demonstrations from existing planners or additional reward shaping. The authors train separate policies for structured and unstructured environments using small maps with no more than 160 agents. The experiments evaluate these policies on six larger maps with 10,000 agents, without any retraining. The proposed method achieves similar or better throughput than the strongest evaluated baselines, while taking around 6–9 ms per step. The authors also test how well the method generalizes to unseen layouts and larger agent populations, including up to 20,000 agents. Additional experiments examine the effects of planning depth, destination allocation, and computational cost.

Critical strengths
  1. The policy is trained on small maps with at most 160 agents but transfers to environments with 10,000 agents without retraining. It outperforms the strongest baselines on Berlin (32.99 vs. 30.02) and Random 20% (47.52 vs. 45.90), while remaining competitive on Warehouse (42.31 vs. 42.79) and Sortation (44.20 vs. 44.25).
  2. Additional experiments on unseen layouts provide further evidence of generalization. I consider this a significant strength because the method scales well beyond its training conditions without requiring planner demonstrations or reward shaping.
  3. The method combines shared spatial guidance, a goal-conditioned route operator, and Sinkhorn-based allocation to coordinate a large number of agents. The ablations show that destination allocation is particularly important in congested environments. Removing it reduces throughput on Berlin from 32.99 to 18.76.
  4. The continuation-depth experiments show that longer route continuations can reduce opposing corridor traffic and improve throughput, particularly in warehouse environments.
Critical weaknesses
  1. Similar ideas on spatial guidance have been explored in GGO, OnlineGGO, and RAILGUN. The paper does not clearly establish how the proposed approach differs from these methods.
  2. The ablations show that route depth and Sinkhorn allocation are important, but they do not fully isolate the contribution of the learned field. Removing some learned components produces similar or slightly better results on certain layouts.
  3. A baseline using the same shortest-path reference and Sinkhorn allocation without learned guidance would help establish the contribution of learning.
  4. The reported speedups also need some qualification, as the methods use different hardware and the execution times exclude map preprocessing, which requires substantial memory and computation.
  5. Performance drops at higher agent densities. At 20,000 agents, the method achieves around 42 goals per step compared with 47.8 for SILLM-DG, despite using substantially more Sinkhorn iterations.
  6. Training uses 48 Sinkhorn iterations per pass, while some evaluation settings require up to 4,608 accelerated iterations. This raises questions about generalization to traffic conditions outside the training range.
  7. The longer evaluations show variation across cases and seeds, particularly on Paris, where the 10,000-step evaluation reports 23.4 ± 7.5 goals per step at 144 iterations.
  8. The evaluation focuses on overall throughput. Per-agent waiting times and task-completion statistics would help determine whether some agents experience starvation despite good overall performance.
Questions for authors
  1. Can the authors compare against (a) shortest-path guidance with Sinkhorn allocation but no learned field, and (b) a direct-output CNN without the route operator, to isolate the contributions of learning and route reweighting?
  2. What is the main methodological novelty over RAILGUN, GGO, and OnlineGGO? Could RAILGUN be compared on a common benchmark?
  3. At higher agent densities, is the performance degradation mainly due to allocation convergence or congestion patterns not seen during training?
  4. What explains the lower-performing Berlin cases and the large Paris seed variance in the long-horizon evaluations?
6 comments

We sincerely appreciate the reviewer's thorough examination of our work, and in particular the request for a clearer comparison with related methods. Below we clarify our methodological contribution relative to existing approaches, present the missing ablations, and address the remaining concerns and questions. Section, table, figure and equation numbers refer to the revised PDF, in which changes are marked in colour.

  1. The paper does not clearly establish how the proposed approach differs from GGO, OnlineGGO and RAILGUN (Q2).

    The primary differences from GGO and OnlineGGO are how the guidance is trained and how it is consumed. Both learn edge costs (a guidance graph) for a separate planner through which the agents act. GGO fixes this graph before execution, and OnlineGGO updates it during execution from recent traffic. Both optimise the costs, or a small network that produces them, with CMA-ES, an evolution strategy that scores each candidate by simulating the planner. In contrast, our field is not a cost for a planner but a latent representation of a differentiable policy, read by the route operator and the allocation and trained by RL from throughput. This also affects execution. Every guidance update in OnlineGGO requires the planner's heuristic table to be recomputed (its Section 3.1), whereas our route operator uses references that are precomputed once per map, so reacting to traffic needs no online path search.

    RAILGUN has a closer policy architecture, a single CNN that processes the whole map, but there are two distinctions beyond the route operator and the Sinkhorn allocation. First, its observation encodes agents by their integer index and goals by the raw shortest-path cost, both of which grow without bound in large-scale deployment, whereas we use normalised features. Second, it learns from planner demonstrations for one-shot MAPF, while we learn from the policy's own experience with lifelong throughput as the reward. We omitted RAILGUN from the tables because its released model fails on our 10,000-agent benchmarks. It completes at most 0.01 tasks per step on all six layouts, although we closely reproduce the results of its public release on its own benchmark. In its own range, on the 128 small random maps of Table 11 with 8 agents, it completes 0.52 tasks per step against 0.61 for our policy (Appendix E.6). Rescaling the index and distance channels to the training range raises throughput to 1.2–5.6 tasks per step, still far below every method in Table 2.

    Our main novelty is therefore a policy in which the shared spatial field, a goal-conditioned route operator and a joint allocation are trained end-to-end by RL for lifelong throughput, with no planner in training or execution. Section 6 now states these differences.

2-3. The ablations do not fully isolate the contribution of the learned field (Q1).

We agree that Table 18 alone does not isolate these contributions and thank the reviewer for pointing this out. We have added three controls (Table 19, Appendix F.1), namely (a) the reference with Sinkhorn and no learned field, evaluated without retraining, (b) a learned field that feeds Sinkhorn directly, without the reference or the route operator, and (c) a learned field that reweights the reference for the next move only, without multi-step continuation, gains or the vector branch.

Throughput (tasks per step)WarehouseSortationBerlinParisRandom 10%Random 20%
(a) Reference + Sinkhorn, no learned field0.28 ± 0.002.88 ± 0.050.80 ± 0.010.96 ± 0.014.50 ± 0.310.39 ± 0.02
(b) Learned field + Sinkhorn, direct output39.07 ± 0.5942.82 ± 0.1527.46 ± 0.5628.71 ± 0.6251.73 ± 0.1343.56 ± 0.12
(c) One-step reweighting + Sinkhorn37.05 ± 3.4543.82 ± 0.0228.94 ± 7.1932.92 ± 1.9053.64 ± 0.0445.82 ± 0.10
Full method42.31 ± 0.0644.20 ± 0.0232.99 ± 0.8333.17 ± 1.9054.19 ± 0.0347.52 ± 0.04

Together with Table 18, these results show the clear contribution of the learned field and the complementary role of the Sinkhorn allocation, while the vector branch and the route gains are layout-dependent refinements. Without the learned field, throughput falls to 0.3–4.5 tasks per step. The direct output (b) stays 1.4–5.5 below the full method on every layout. One-step reweighting (c) recovers most of this gap on Sortation, Paris and the random layouts, but remains 5.3 and 4.1 below on Warehouse and Berlin, where it also varies across training seeds. Our interpretation is that the core of the approach is the end-to-end learning of the guidance field together with the allocation, and that the additional components improve performance on the harder layouts with minimal cost elsewhere.

  1. The methods use different hardware, and the execution times exclude map preprocessing.

    We agree that speed has to be compared on common hardware. We have re-timed our policy and every learned baseline over all timesteps on one dedicated machine (Ryzen 7 7800X3D, RTX 5090, no other job running), and Table 2 and the text now use these values. As before, the step time is the wall time of a whole step after map preparation, covering policy inference or planning and the simulator.

Step time (ms)WarehouseSortationBerlinParisRandom 10%Random 20%
Ours8.47.78.78.75.87.2
SILLM-SG13.013.013.113.113.013.1
SILLM-BD13.213.113.213.212.913.1
SILLM-DG281390303318454377

SILLM-SG and SILLM-BD (Jiang et al., 2025) take 1.5 to 2.2 times our step time, and SILLM-DG 34 to 78 times. Follower and OnlineGGO take 2.5–3.9 s and 2.4–3.7 s per step on the same machine. The non-learned baselines of Table 2 were re-timed there as well and their entries are updated, and so were most step times at the other scales (Figure 1, Table 14, Appendix D). At 20,000 agents, SILLM-DG was timed on a second machine (EPYC 7B12, RTX 5090), on which our policy takes 325 ms per step against its 924 ms (Appendix D).

Map preparation is excluded from the step time and reported separately. The reference tables are built once per map and reused for all agents and all successive tasks. They take 17.5–29.1 s to build and occupy 5.5–12.7 GiB (Table 7), and Table 8 now separates preparation memory from execution memory, with the tables included. On Random 20% our policy peaks at 12.1 GiB of host memory and 10.3 GiB of GPU memory, against 20.0 and 10.7 GiB for SILLM-SG. Separating preparation from execution follows the convention of this benchmark, in which the competition setting used by WPPL allows 30 minutes of preprocessing per map (Jiang et al., 2024, Section 2) and SILLM reports the average single-step planning time (Jiang et al., 2025, Table III). The cost is nevertheless real, since the tables grow with the square of the number of free cells, which limits the map size that fits on one GPU.

  1. Performance drops at higher agent densities (Q3).

    This is a limitation of our method, and the revised paper states it more clearly in Section 4.2 and in the conclusion. We think that both causes contribute at 20,000 agents and that they are connected. The congestion pattern not seen in training is the size of the groups of agents that compete for the same cells. Agents that demand the same cell are linked through its destination potential (Eq. 8). The largest linked group averages about four agents in training, where the small maps bound it, and 33 at 16,000 agents, but 3,641 at 20,000 (Table 15). Allocation convergence is its first consequence. The allocation needs more iterations to converge across such a group, and raising the budget from 288 to 4,608 iterations, where it has converged by our criterion (Eq. 28), raises throughput from 32.6 to 42.0. This is the smaller part. With the converged allocation the agents still select their moves independently, and within a large group many of these moves are cancelled.

    We therefore devised an iterative action selection (Appendix E.4), inspired by the PIBT-based collision shield, that lets the agents whose moves were cancelled choose again among the free cells, using the already computed allocation probabilities. Applied to the same policy, it raises throughput from 42.0 to 54.1 at 4,608 iterations, and 864 iterations already reach 48.0 at 61 ms per step, which matches SILLM-DG's 47.8 (Table 14).

  2. Training uses 48 Sinkhorn iterations per pass, while some evaluation settings require up to 4,608.

    We agree that the gap between the two budgets raises this question. Training uses fewer iterations to keep training fast, and in our few trials a larger training budget did not improve the policy, although we have not studied this systematically. The results of Table 2 do not depend on a large budget. They use 144 or 288 iterations, to which the 6–9 ms step times refer, and on Random 20% throughput is 47.5 at 96, 144 and 288 iterations alike (Appendix E.4). Larger budgets matter only at the highest densities. As discussed in point 5, we believe the core limitation there is the size of the groups of competing agents rather than the small number of training iterations.

Reviewer_SmA8OpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a novel method to solve lifelong multi-agent path finding problems. Their method uses a convolutional neural network to compute a spatial field shared across all agents, that is then used as the input for a chain of fixed, non-trained operations to determine each agents action. The post-processing steps include a route reweighting for each agent based on computed field scroes and a cell allocation to resolve final conflicts and collisions. The method is trained using reinforcement learning The authors put an emphasis on the computational efficiency of their method, comparing favorably to many other methods while achieving competitive goal throughput rates.

Critical strengths

A critical strength of the paper is the conscious use of a hybrid policy to achieve efficient multi-agent planning. The authors introduce conscious problem-oriented modeling to reduce trainable parameters and thus decrease time per step.

Critical weaknesses

The most critical weakness of the paper is a lack of intuitive explanation of the core idea. Section 3 is difficult to parse and lacks overall motivation and communication of the intuition. For instance, it is unclear and not formulated what the "shared field" predicts exactly and what the intuition behind using a CNN to predict it is. Many terms and phrases are introduced but not explained (see questions below). Also the intuition behind why this method scales to larger maps, and why it needs a specific training mixture is not explained. The evaluation and ablation sections lack thoroughness (details formulated as questions below).

Questions for authors

3.1

  • What is departure depth?
  • What is the motivation behind the CNN and predicting a spatial field? Which CNN architecture is being used?

3.2

  • What is a goal phase?
  • What does it mean to "consume one departure"?
  • What do you mean with "two contrasts formed after centring the reference probabilities"?
  • How is bhb_h derived?
  • How are the gains γh(x)\gamma_h(x) determined?

3.4

  • Why is this particular RL paradigm being selected?
  • Terminology "mixture" is unclear and unusual
  • What is the intuition behind separating training on structured and unstructured maps?

Table 1:

  • What is a "headline" learned-policy comparison?
  • Different train/test splits seem to prohibit an apples-to-apples comparison. What is the reason to not compare all methods a) when trained on the same map, and b), when transfering to a new map?

4

  • Why are PRIMAL1 and PRIMAL2 not considered, as mentioned in 6?
  • What is the value for H in section 4?
  • How is the step time determined, as this is hardware dependent, among many other aspects?

5

  • Why have only H=1,2,4 been tried, if performance seems to trend upwards?
  • What is the significance of Figure 4b? The authors should emphasize notable parts of the image to highlight to the readers.
  • Did you ablate on different training sets, e.g. testing policies trained on structured maps on unstructured maps, or training a policy on all maps?

6

  • Why is related work placed at the back of the paper?
3 comments

We thank the reviewer for the careful reading and the specific questions. We first give the motivation behind the method, and then answer each question in the reviewer's order. Section, table, figure and equation numbers refer to the revised PDF.

  1. The motivation and intuition of the core idea

    A spatial field computed by a CNN is an established way to guide agents in MAPF (OnlineGGO, SJRL and RAILGUN, Section 6). The direct benefit of such a field is its cost. The network runs once per timestep for all agents, its computation grows with the area of the map and not with the number of agents, and it can be applied to a map of any size.

    The central difference from these works is what reads the field. In OnlineGGO (Zang et al., 2025) and SJRL (Jiang et al., 2026) the field assigns a cost to each move between neighbouring cells and these are optimised for the performance of a downstream method that is built on a planner such as PIBT. RAILGUN (Tang et al., 2025) uses the field directly as the action probabilities of each agent. In contrast, in our approach the field is an intermediate output of the policy. Its scores serve as the utilities of each agent's route choice (Fosgerau et al., 2013; Section 3.2), and the allocation then adjusts the resulting probabilities for agents that want the same cell. The field does not predict a quantity that is defined in advance, and no planner takes part.

    The primary motivation for this form is dynamic guidance at a low cost per step. Static guidance has so far been designed by hand (SILLM-SG) or optimised for each map (SJRL; GGO, Zhang et al., 2024). Existing dynamic guidance changes the edge costs or guide paths that a PIBT-based planner follows, so the planner's distance tables or guide paths are recomputed during execution, which brings the cost to about 200 ms per step or more at 10,000 agents (SILLM-DG, TrafficFlow and OnlineGGO, Table 2). Our policy needs only shortest-path distances that are computed once per map. In other words, we wanted to replace the downstream planner while keeping the cheap spatial field of a CNN. In this light, we designed the route operator and the Sinkhorn allocation as soft counterparts of a planner's goal-conditioned routing and conflict resolution, respectively. The revised Section 3 now states that one network evaluation serves all agents (Section 3.1), that the scores act as utilities of each agent's route choice, and that the distances used by the route operator are computed once per map (Section 3.2). Section 6 has a new paragraph on the models of route choice that the route operator follows.

  2. Why the method scales to larger maps

    This work was inspired by the success at large scale of methods that decide each step from an agent's surroundings and precomputed distances (PIBT and SILLM). We built a setup in which RL learns such local coordination on pools of small maps, and the resulting policy can be applied to other map sizes and numbers of agents without retraining. That its throughput carries over is an empirical result. It holds on the six layouts of Table 2 and the three additional layouts of Table 16, and it ends in extremely dense settings (Section 4.2).

  3. Section 3.1

  • What is departure depth?

    We thank the reviewer for pointing this out. The revised Section 3 defines the term at its start. A departure is one step of an agent's route, a move or a wait. The route operator considers routes of H steps, and the departure depth h = 0, …, H−1 is the index of a step, with h = 0 the next action.

  • What is the motivation behind the CNN and the spatial field, and which architecture is used?

    The motivation is given above. The main branch of the network has two 3×3 convolutional layers of width 48, followed by a local output head and a multi-scale head with dilations 2, 4 and 8. A small second branch outputs a two-dimensional vector at each cell (Section 3.1, Appendix A.2).

  1. Section 3.2
  • What is a goal phase?

    Each agent knows its current goal and the one after it. A route that reaches the current goal continues toward the next one, and the goal phase records which of the two is active.

  • What does it mean to "consume one departure"?

    The phrase meant that each move or wait uses one of the H steps of a continuation. In the revised Section 3, we deleted the phrase and included this fact in the definition of a departure instead.

  • What are the "two contrasts formed after centring the reference probabilities"?

    In short, ψ(z,a)=(D(z,a),B(z,a))\psi(z, a)=(D(z, a),B(z, a)) consists of two relative preferences of the action aa, where B(z,a)B(z,a) is how much the axis of aa is preferred (so it measures horizontal vs. vertical, and e.g., B(z,E)=B(z,W)B(z, E)=B(z,W) by definition), and D(z,a)D(z,a) is how much the direction of aa is preferred within its axis (so it measures, e.g., eastward vs. westward). See Appendix A.3 for details. The revised text describes them in these terms.

  • How is bhb_h derived?

    It is computed from two outputs of the network at cell xx. The first, Fhcont(x)∈R5F^{\mathrm{cont}}_h(x)\in\mathbb{R}^5, holds one number for each of the five actions at depth hh. The second, G(x)∈R2G(x)\in\mathbb{R}^2, is a 2-D vector. Each move also receives the component of G(x)G(x) along its direction, so a move and its opposite receive opposite amounts. Together, bh(x,a)=Fa+⟨ea,G(x)⟩b_h(x,a)=F_a+\langle e_a, G(x) \rangle with F=Fhcont(x)F=F^{\mathrm{cont}}_h(x), where eae_a is the unit vector in the direction of move aa and zero for waiting (Eq. 16). In other words, it is the per-action field plus the projection of the 2-D vector field on the direction of the move.

  • How are the gains γh(x)\gamma_h(x) determined?

    They are computed from the output FF and a learned global coefficient matrix K∈R2×2K\in\mathbb{R}^{2\times2}. Intuitively, the gains γh(x)\gamma_h(x) work as multipliers for the two preferences DD and BB described above, and they reinforce or weaken how strongly an agent follows its goal direction at each cell xx and depth hh. KK is trained by RL like any other parameter. See Eq. (16) for details.

  1. Section 3.4
  • Why is this RL paradigm selected?

    Maximising throughput in lifelong MAPF is well aligned with the objective of average-reward reinforcement learning. With the number of goals completed at each step as the reward, the throughput is the long-run average reward (Eq. 1), and this simplicity is why we chose the paradigm.

  • The term "mixture" is unclear.

    We agree that the term was unusual. The revised text no longer uses it. It says training pool, a fixed set of 128 small maps of several types that are all used in every update (Appendix B, Figure 5).

  • Why are structured and unstructured maps trained separately, and why a training mixture?

    Having two classes is an empirical choice. We observed during development that small warehouses in the pool were important for competitive performance on large warehouses. We therefore made the structured maps a specialised class of their own, separate from the more general unstructured ones. Table 17, added in the revision, agrees. The final policy trained on the unstructured pool is 8% lower on the warehouse, and our answer on Section 5 below reports a single policy trained on both pools.

    We train on a pool because we regard the training as a form of multi-task RL (Hessel et al., 2018), in which each type of small map is a task with its own traffic pattern.

  1. Table 1
  • What is a "headline" comparison?

    It meant the main comparison of the paper, Table 2. The revised text refers to Table 2 directly.

  • Why not compare all methods (a) trained on the same map and (b) transferred to a new map?

    • (a) The difference in Table 1 gives SILLM and OnlineGGO the more favourable setting. Both are evaluated on the layout for which they were trained, which is setting (a), while our policies and Follower are not trained on the test layouts, which is setting (b). Training for the target layout is part of each of the two methods. SILLM learns by imitation on a downscaled copy of the target layout, and OnlineGGO optimises its policy on a smaller map of the same layout. We therefore use the released checkpoints of SILLM and the released recipe of OnlineGGO (Section 4), since replacing their training maps with our pools would not reproduce either method.
    • (b) The paper makes this comparison on three layouts on which no learned method was trained (Table 16; Table 15 in the submission). The revision fills the entries that were missing in that table. Our policy is comparable to the best baseline on one of them and higher on the other two, for example 22.1 against 14.5 tasks per step on a random map with 40% obstacles.
  1. Section 4
  • Why are PRIMAL and PRIMAL2 not considered?

    PRIMAL addresses one-shot MAPF. PRIMAL2 is lifelong. We did not include it because Follower, a later learned method, is reported to reach about twice its throughput on maze maps with 256 agents, and SILLM is in turn reported to almost double the score of Follower at 10,000 agents. Follower and SILLM are both in Table 2. For this response we compared with PRIMAL2 on the benchmark of its own paper, the Moving AI maze and warehouse maps with its largest teams of 1,024 to 2,048 agents. Its paper reports 1.05 and 3.36 tasks per step there. On the same maps and team sizes our policies complete 4.60 and 9.48 without retraining, on cases that we generated because its instances are not published. We also ran its released model in our simulator on five of these settings (one case each). It reaches 0.84 and 1.01 tasks per step on the maze map and stays below the published values on the warehouse maps, so we compare with the published values.

  • What is the value of H in Section 4?

    H = 4 in all experiments of Section 4. The submission stated this in Section 3.4, and the revised text also states it at the start of Section 3, where H is introduced.

  • How is the step time determined?

    It is the average wall-clock time of one simulated step, including inference or planning and the simulator, and excluding setup. All step times in the revision are measured on one dedicated machine (AMD Ryzen 7 7800X3D, RTX 5090), one job at a time (Appendix D). Our policy, SILLM and Follower use the GPU, and PIBT, WPPL, TrafficFlow, LLLG and OnlineGGO run on the CPU as released, with the thread counts in Appendix D.

  1. Section 5
  • Why only H = 1, 2 and 4?

    We first trained H = 1, 2 and 4, and the throughput did not increase with H on every layout. On Berlin H = 2 is below H = 1 (26.7 against 30.2 tasks per step), and on Paris H = 1 matches H = 4 (33.3 against 33.2, Table 18). We therefore stopped at H = 4. For this response we also trained H = 6 on the structured pool, with three seeds and the same budget. On the 10,000-agent warehouse the throughput is 40.06, 41.64, 42.31 and 42.62 tasks per step for H = 1, 2, 4 and 6, and on sortation H = 6 gives 44.23 against 44.20 for H = 4. H = 6 takes almost the same time per step as H = 4.

  • What is the significance of Figure 4b?

    It shows the traffic in one narrow passage over time. With H = 1, a one-way convention is only weakly established. Agents enter the passage from both ends, and those that meet opposing traffic turn back. With H = 4, the traffic runs almost entirely in one direction. The opposing demand, which measures how often neighbouring agents request moves towards each other, shows the same difference over all 172 passages of the map (4.34% with H = 4 against 7.16% with H = 1). Our assessment is that longer continuations improve the warehouse throughput by helping such a convention to form in the passages. The revised figure marks the agents that turn back.

  • Did you ablate on different training sets?

    We thank the reviewer for this question. We ran the two ablations that the reviewer suggested (Table 17). A policy trained on the structured pool fails on Berlin and Paris (7.2 and 10.7 tasks per step, against 33.0 for the policy trained on the unstructured pool). The structured policy is at most 3% lower on the two random layouts, and the unstructured policy is 2% and 8% lower on sortation and the warehouse.

    We also trained a single policy on both pools. It comes close to the class-specific policies on four layouts and remains 1.2 and 3.8 tasks per step lower on Berlin and Paris (one training seed).

    Each pool combines several types of small maps (Appendix B, Figure 5), and Table 17 compares whole pools. Which map types within a pool are needed is a question that we did not study, and a formal description of local traffic patterns that answers it is future work.

  1. Section 6
  • Why is related work at the back?

    The comparison with the closest methods refers to the components defined in Section 3, so we placed it after the method and the experiments. The introduction positions the work against the main lines of prior work.

Reference

Hessel, Soyer, Espeholt, Czarnecki, Schmitt and van Hasselt. Multi-task deep reinforcement learning with PopArt. arXiv:1809.04474, 2018.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.