acceptodds
Under review as a conference paper at ICLR 2027

Learning Repairable Initializations for Multi-Agent Path Finding via Discrete Diffusion

Abstract

Multi-Agent Path Finding (MAPF) is a coordination problem that requires computing globally consistent, collision-free trajectories for multiple agents from their start positions to assigned goals in a shared environment. In dense settings, sequential prioritized planning can concentrate repeated conflicts on a small subset of agents, hindering local repair. Despite its importance for downstream repair, the initialization stage of repair-based MAPF solvers has received relatively limited research attention. We propose DiffLNS, a hybrid framework that integrates a discrete denoising diffusion probabilistic model (D3PM) with LNS2 to improve initialization for repair. Trained on expert demonstrations, the D3PM initializer uses diffusion-aware sparse social attention to learn a spatiotemporal prior and samples diverse plans directly in the categorical action space. These plans serve as warm starts for LNS2, which completes unfinished trajectories and resolves conflicts under hard MAPF constraints. Controlled comparisons show that diffusion-generated initializations exhibit more balanced conflict loads across agents and achieve higher repair success under the same repair procedure and budget, despite starting with more colliding pairs. Although trained with at most 96 agents, the initializer generalizes to tested scenarios with up to 312 agents. Across 20 complex and congested settings, DiffLNS achieves an average success rate of 95.8%, exceeding the strongest tested baseline by 9.65 percentage points and matching or exceeding all baselines in every setting. To the best of our knowledge, this is the first work to use discrete diffusion to warm-start an LNS-based MAPF solver.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Discrete diffusion, multi-agent path finding, LNS2

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_J4j6OpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents a diffusion based approach to generating initial paths in a MAPF problem. The paths are not a correct solution, but large neighbourhood search is used to generate a solution from them. The interesting finding is that the initial paths, even though they have more conflicts than using priorities planning, generate better solutions after repair. But its not clear the method is scalable to problems of interest, and the authors use non-standard benchmarks while there is a wealth of standard benchmarks in this space. There seems little reason to do this, except to make it harder to compare with other existing methods.

Critical strengths

Clearly the diffusion is learning something meaningful, since the repaired plans are better than those created by prioritised planning.

Critical weaknesses

Not applied to large maps. The actual use of MAPF in warehouse logistics is on very large maps with very large numbers of agents. No arguments that this approach scales to this map size.

Not applied to standard maps. There are plenty of small maps and agent start-goal pairs benchmarks available but the authors choose to use their own, for no reason discernible.

Questions for authors

How do you compare with using PIBT/LACAM to generate initial paths and then repairing with LNS. These simple symbolic approaches have very high success rate, leaving LNS2 to mainly reduce the cost of the resulting solution rather than fix conflicts. These are commonly used in modern MAPF solutions e.g. Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI-24).

Sometimes an agent may reach its goal state and have to move off the goal, to let another agent through. Is this something the diffusion patterns can learn. It seems you disallow such paths in the preprocessing step before they are passed to LNS2

How does the method scale with map size. The joint discrete action tensor is going to be very large for 1000 agents on a large map, e.g. requiring over 1000 time steps to complete.

Can you redo the experiments on standard maps, with standard start-goal agent pairs.

Given you are comparing on dense maps with many agents, shouldnt you compare against modern MAPF methods that take into account traffic in their planning, e.g. Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding (AAAI-25) even if they are designed for Lifelong MAPF.

2 comments
Reviewer_J4j6OpenReview ↗

After rebuttal

The authors did a good job at answering my questions. Its a pity they did not illustrate the methods on more standard MAPF benchmarks which are widely available. Without this its not clear if this approach actually moves the state-of-the-art for MAPF forward.

The method clearly suffers on large maps, at least how I read the table for Q3 is that on the map of interest (warehouse) LNS2 is faster and has better solutions. The maze and room maps are quite artificial and hard for reasons that dont tend to occur on other map types.

There is some interesting ideas here, but at least for me not quite enough evidence that it really moves the state-of-the-art. I will raise my score to weak acceptance.

We appreciate the reviewer's careful assessment and constructive feedback. We agree that broader evaluation on standard MAPF benchmarks and improved scalability are important for establishing the approach's value across different MAPF settings.

In future work, we will investigate how to improve efficiency and solution quality on larger maps with more agents, and conduct more extensive testing on standard MAPF benchmarks across diverse map types. The reviewer's comments have helped us clarify these priorities for our future research.

Reviewer_PbZ6OpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces DiffLNS, a learnt initialiser D3PM for LNS2 refinement for MAPF. D3PM uses discrete diffusion denoising to generate joint action drafts ignoring the feasibility constraints, while LNS2 enforces the MAPF constraints. This provides a complementary direction to repair improvements for enhanced LNS-based solvers.

Critical strengths
  1. The idea and problem is well motivated. It also provides a complementary direction to repair improvements and shows a valid research direction.
  2. The paper shows good empirical performance.
Critical weaknesses
  1. Unfair Comparison: LaCAM3 is not given the same fixed per-setting budget used by the other baselines. HMAGAT is given a 512-step limit. The results might thus be misleading. The paper highlights that DiffLNS is trained with up to 96 agents and scales to 312 agents, but ignores that HMAGAT is trained with up to 32 agents. It is unclear if the benefits are simply from the increased number of agents in training.
  2. Further Experiments: The paper presents DiffLNS as a complementary direction to repair improvements, like LNS2+RL, but never shows how the combination would perform. The necessity of an expensive diffusion model has also not been established.
  3. Related Works Discussion: The paper notes in the related works section that various learning-based MAPF solvers struggle with satisfying hard MAPF constraints in dense environments. However, a common strategy to combat this is to use collision shielding [1] and various methods do in fact use them and guarantee satisfaction of the MAPF constraints.

[1] Veerapaneni, R., Jakobsson, A., Ren, K., Kim, S., Li, J., & Likhachev, M. (2025, May). Work smarter not harder: Simple imitation learning with cs-pibt outperforms large-scale imitation learning for mapf. In 2025 IEEE International Conference on Robotics and Automation (ICRA) (pp. 10229-10236). IEEE.

Questions for authors
  1. Can you please update the results (Figure 3 and appendix) with fair baselines, i.e. LaCAM3 given the same fixed per-setting time budget as the other baselines and HMAGAT not constrained to a 512-step limit (by either removing the step limit or setting the limit to a much larger value, so that the success is not inhibited by this, but rather by hitting the time limit)?
  2. Can you please provide comparisons with other methods for the initialisation generation? This could be via training of new models or the use of the HMAGAT model without collision shielding to provide different initialisations.
  3. Can you please provide the results of running D3PM with LNS2+RL repair?

I would be inclined to increase my score if the authors are able to answer these questions satisfactorily. For Q1, it is fine if the results are unfavourable to DiffLNS, as it is still valuable to question how we can improve initialisation for LNS2. However, it is important to show the complete picture and the current results seem misleading.

Reviewer_14K7OpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper focuses on a clear idea: classical priority planning is suboptimal as a starting point for path repairs and learning can give better priors to start the repair process. The paper also uses a timely and appropriate method of discrete diffusion to tackle this issue, as (existing) autoregressive methods might be difficult to train for longer horizons. The results are clear and convincing.

Critical strengths

The paper is well written and easy to understand. It appropriately focuses on both the “what” and “how” of the proposed solution. The proposed method is novel and has the potential to motivate further research in the field. The results are convincing, and the appendix is thorough.

Critical weaknesses

My only critique of the paper is that it doesn’t focus enough on “why” the method works. IL for diffusion means that diffusion tries to replicate what an expert would, given the same MAPF instance. However, the paper states that there are significantly more collisions in the initial plan compared to SIPPS, so it does not perfectly replicate LACAM3. So, I am unsure “why” the trained diffusion model performs so well, because:

  1. It doesn’t appropriately imitate the expert (seen from the initial collisions).
  2. It uses IL, not RL where it might learn to make use of the subsequent path repair.

While the last paragraph in Appendix B.2 touches briefly on this point, I would have liked to see a better reasoning on why the method works. In its current state, I am not fully convinced that the results are reproducible.

Questions for authors

My main question is: upon retraining on the same dataset, do the results remain similar, or was this a one-off and the diffusion model stumbled on a network that accidently works well with LNS2?

If the answer is that the results remain similar, then the paper should look into “why” this might be happening. As in how the initial paths differ from SIPPS, and why the repair works better. The paper can then use these observations to make an even stronger claim on how the method beats SIPPS in low to medium density maps, and why this doesn’t work in high density maps. These observations could help researchers push future work in this domain.

For example, it seems that while the proposed diffusion is not good at planning collision free paths, but it might be really good at agents’ homotopic routing. So, the main advantage of the method might come from that fact that while SIPPS forces certain agents to choose alternate, worse plans to get the least number of collisions, diffusion might be better at routing and LNS2 can easily solve the inter-agent collisions in these routes. If this is true, then this might be a more fundamental contribution to the field of MAPF, that future works can try and improve upon, rather than just showing that discrete diffusion works with LNS2.

This was just an example, but the inclusion of such an analysis in the paper would change my rating to a clear accept. If retraining does not work as reliably (or not every time), then this should also be discussed in more details, as the "success rate" of training this framework also seems very important for the community.

3 comments
AuthorsOpenReview ↗

Mechanism Disscusion

We sincerely thank the reviewer for the encouraging assessment and the insight that understanding the learned routing structure could lead to a more general MAPF algorithm.

Reproducibility. We retrained D3PM twice with different random seeds, using the same dataset, hyperparameters, and evaluation protocol. We evaluated the most congested setting of each family, since original SRs on the other 15 settings were already 92–100% (Table 8). The table shows similar end-to-end DiffLNS SRs (%) across the three training runs on the same 300 test instances. We will report per-seed success rates in the camera-ready.

Setting (agents)InstancesOriginalRetraining 1Retraining 2
Small Random (60)100817882
Medium Maze (190)509896100
Medium Room (192)50647062
Medium Warehouse (252)5010098100
Large Maze (312)50929892

What may make the learned plans repairable. D3PM is trained to model a conditional distribution of expert plans through denoising and posterior matching (Eqs. 7–8). Low average denoising error does not guarantee collision-free joint plans: small action or timing errors can propagate across trajectories and create many conflicts. Our hypothesis is that D3PM learns useful coarse spatiotemporal structure from expert plans, guiding agents to appropriate regions at appropriate times. This hypothesis is related to the reviewer's homotopic routing conjecture, as both emphasize the role of global route structure in supporting LNS2 repair. Such structure may give LNS2 a better starting point for conflict repair, even though D3PM is not trained on repair outcomes. The paper's observations of less concentrated conflicts and more balanced conflict loads across agents also suggest that initialization heuristics should consider conflict structure and repairability alongside conflict count (Section 4.2; Appendix B.2).

To probe this explanation within the rebuttal period, we conducted a small perturbation experiment on 150 saved D3PM drafts before LNS2 repair: 50 each from Medium Maze (190 agents), Medium Room (192), and Medium Warehouse (236). We fixed each agent's position at every fifth timestep in the generated prefix, then randomly resampled the intervening moves to reach the same next waypoint at the same time. Replacements allowed waiting and respected obstacles and map boundaries, but did not enforce inter-agent collision avoidance; segments without alternatives were retained. We repeated path resampling with three seeds and applied the same LNS2 repair procedure. The rows separate the 114 originally successful cases from the 36 originally unsuccessful cases; the two resampling columns report mean success and failure counts across the three trials.

Original repair outcomeSuccess after resamplingFailure after resamplingCases
Successful99.015.0114
Unsuccessful11.324.736

After the moves between waypoints are resampled, 86.8% of originally successful cases still succeed and 68.5% of originally unsuccessful cases still fail on average. Overall, 82.4% of cases retain their original repair outcome. This small experiment offers partial support for our interpretation that D3PM learns useful coarse spatiotemporal structure. At a minimum, it suggests that coarse planning structure may be important for LNS2 repair. We are currently trying to distill the underlying mechanism and use it to develop a better MAPF solver. Combining global search with relaxed collision constraints and LNS2 repair could be a promising way to achieve this.

I thank the authors for their experiments and analysis on why the algorithm works. I am convinced by the additional results, and as promised, I’ll update my rating to a clear accept. Although I agree with some of the points raised by my fellow reviewers, I believe this paper is a step in the right direction. Like most novel work, it can be improved further, but in its current state it deserves publication. Some remaining out-of-scope changes are best left for future work.

We are grateful for the reviewer's thoughtful assessment, constructive guidance, and support for our work. The reviewer's questions about what D3PM learns and why its plans remain repairable have helped us sharpen our analysis and identify promising directions for future solver design. This encouragement gives us greater confidence to continue investigating these mechanisms and developing stronger MAPF solvers.

We have also incorporated the two independent retraining experiments into Appendix C.4 (Table 11) of the revised manuscript. The table reports success rates for the original model and both retrained models on the same 300 test instances.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal

Dear Area Chair and Reviewers,

We are grateful for the constructive feedback and discussion. Reviewers recognized the novelty and research potential of the approach (14K7), its complementarity to repair improvements (PbZ6), and the value of the learned initializations for downstream repair (J4j6).

Below, we summarize the main updates.

  • Reproducibility and mechanism (14K7). We added two independent retraining runs with similar results (App. C.4, Table 11), and provided further mechanism analysis and a preliminary perturbation study in the discussion.
  • Baseline fairness and transparency (PbZ6). Following the reviewer's suggestions, we revised the main-experiment evaluation protocols and updated both the main and supplementary results. We now use shared per-setting time budgets, report LaCAM3's full-budget SOC, and evaluate HMAGAT with PIBT shielding and a 4096-step limit. We also added DiffLNS+RL to the main comparison, combining D3PM initialization with LNS2+RL repair to demonstrate their complementarity (Fig. 3, Table 10).
  • Initializer comparisons (PbZ6, J4j6). We added comparisons with HMAGAT, LaCAM, and PIBT to evaluate whether D3PM provides more effective starting points for subsequent LNS2 repair and optimization than alternative learned and search-based initializers (App. B.4).
  • Standard benchmarks and scalability (J4j6). We expanded the MovingAI experiments to include multiple baselines and solution quality alongside success rates, and added 1,000-agent tests on larger maps using official scenarios (App. B.3, Tables 1–2).

Following the discussion, all three reviewers increased their ratings by one point, from 3/2/2 to 4/3/3. We thank the reviewers for helping us strengthen the evidence, improve the manuscript, and identify promising directions for future work.

Best regards,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.