Neural Neighborhood Search for Multi-agent Path Finding

We thank the reviewer for the feedback and suggestions and encourage the reviewer to view our general response to all reviewers, which contain significant improvements to our paper. Here are our specific responses to each concern:

Weaknesses

1. We would like to clarify that the Average Gap (%), Win / Loss, and Final Gap (%) in Table 1 already include the stated model overhead in the 60s runtime (they are exactly the solid curves in Figure 5). Thus, our Multi-subset architecture outperforms Linear in all settings (especially in empty, random, warehouse, and ost003d), even with higher overhead. We believe that this fairly demonstrates the benefits of our method.
2. Linear, Per-subset, and Multi-subset all use a single NVIDIA V100 GPU (released in 2017, Volta architecture) rather than more recent top-end GPUs. Our understanding is that recent affordable commodity GPUs such as NVIDIA RTX 3060 (released in 2021, Ampere architecture) perform similarly to the NVIDIA V100.

Questions

As mentioned above, we do include inference overhead for both our method and the Linear baseline. We agree that our method would be slower than Linear if executed on a CPU. We agree that standard model compression techniques may reduce our model overhead significantly to be more runnable on a CPU, but this is orthogonal to our proposed method and can be further investigated by practitioners. For example, we could imagine that our Multi-subset model could serve as a teacher model for a Linear student model during model distillation.

We thank the reviewer for their time. We hope that the reviewer could update our score if we have further strengthened our paper through our additional rebuttal efforts.

We are very grateful for the reviewer’s suggestions to improve the rigor and soundness of our experiments by providing additional perspectives of performance. We encourage the reviewer to first examine our general response to all reviewers, where we summarize major rebuttal updates. Here we focus on each comment in more detail:

Novelty: We discuss the novelty of our proposed intra-path attention in the general response and its aptness for multi-agent path planning. We encourage the reviewer to view updated architectural figure (Figure 3) as well as additional ablation (Appendix A.6).

Soundness: Regarding the reviewer’s comments about sources of increase in runtime:

1. Model overhead: the neural network overhead is indeed larger than Linear. However, what’s important is the relative overhead; that is, the model overhead is insignificant when it is small compared to the repair heuristic. In Table 1, we observe this phenomenon in many cases for the Multi-Subset network, especially in large settings like den520d (256x257). In real-world deployment settings, the repair heuristic used could incorporate continuous robot dynamics and thus take even longer than the repair heuristics used in our discrete setting; this would further reduce the relative model overhead.
2. Both MAPF-ML-LNS and our work requires multiple calls to the destroy heuristic. However, the destroy heuristic takes 3-4 orders of magnitude less time than the repair heuristic, and thus is insignificant in the overall runtime.
3. PBS is indeed slower than PP, but offers significantly stronger improvements per call, especially as we show in parameter sweeps in Appendix A.2. The slower runtime of PBS is actually synergistic with our neural network approach (see Bullet 1).

Regarding the reviewer’s concerns about generalization, our generalization experiments are grounded in multi-robot warehousing applications, where it would be uncommon (and expensive!) to have large deviations in floor maps (especially size) or warehouse operating conditions (e.g. 5x fewer robots). Under such circumstances, we presume it would be common practice to train separate models rather than rely on generalization. On the other hand, obstacle locations, number of agents, and subset construction could change on a minute-by-minute or week-by-week basis, and thus we felt that this warranted an investigation into generalization. The results of our generalization analysis is summarized in Table 2 and are favorable: we found that models trained on both the random and empty floor maps could generalize better than Linear to different number of agents and/or different subset construction heuristics/sizes in the empty floor map.

Questions

We study PBS as a repair heuristics because it is one of the state-of-the-practice solvers which is more scalable than CBS and offers much better solution qualities than PP. We are unclear on why MAPF-LNS and MAPF-ML-LNS do not study PBS, even though it is used in other papers by the same authors [2]. Thus, as MAPF-LNS only sweeps for PP from $k = 2$ to $k = 16$ and differs in compute resources from us, we must sweep hyperparameters ourselves with both PBS and PP. Indeed, our hyperparameter search finds that larger neighborhood sizes (e.g. $k = 25$) tend to be the best for PBS.

[2] Li, Jiaoyang, et al. "Lifelong multi-agent path finding in large-scale warehouses." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 13. 2021.

In general, it also could make sense to use deep learning as the destroy heuristic for LNS and this could be explored by future work in the MAPF domain. [3, 4, 5] use deep learning as the destroy heuristics. On the other hand, [MAPF-ML-LNS, 6] are similar to ours and perform subset selection. In general, we find that deep learning works in (mixed) integer (linear) programming like [3, 4] tend to learn the destroy heuristic.

[3] Y. Wu et al., "Learning Large Neighborhood Search Policy for Integer Programming", NeurIPS 2021

[4] Huang, Taoan, et al. "Searching large neighborhoods for integer linear programs with contrastive learning." International Conference on Machine Learning. PMLR, 2023.

[5] Zong, Zefang, et al. "Rbg: Hierarchically solving large-scale routing problems in logistic systems via reinforcement learning." Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.

[6] Li, Sirui, Zhongxia Yan, and Cathy Wu. "Learning to delegate for large-scale vehicle routing." Advances in Neural Information Processing Systems 34 (2021): 26198-26211.

We again thank the reviewer for taking the time to help us strengthen our work, and we truly believe that the reviewer’s suggestions has led to a more grounded perspective of our work. We hope that the reviewer will consider increasing our score accordingly if we have appropriately alleviated the reviewer's concerns.

Significance/Evaluation: We acknowledge that our original submission lacks direct comparisons that invites concerns regarding fairness/significance, especially the relative metrics that we used and the lack of per-iteration performance comparisons. We thus provide additional results which addresses these concerns and allow direct comparisons with MAPF-LNS and MAPF-ML-LNS.

Our Linear baseline also uses the best fixed neighborhood size and destroy heuristic. As we explain in detail in updated Appendix A.2, neither our work nor MAPF-ML-LNS is designed to choose between subsets with different sizes in a principled manner. E.g. a subset of size 50 would take significantly longer time to repair than a subset of size 5, but neither our work nor MAPF-ML-LNS considers the runtime of repairing the subsets. Thus, to keep the experimental setting controlled, we do not consider subsets with different size. We note that any future linear-model work proposing a principled way to consider subsets of different size is also applicable to our neural method. Moreover, when comparing absolute performance below, MAPF-ML-LNS does not outperform our Linear (and we could not find their code for comparison). Thus, we believe that our implementation of linear guided LNS is fair to previous work.

Regarding absolute performance, this is a great point which we aim to convincingly address here. We compile the best “sums of delays” for each of our studied settings from MAPF-LNS and MAPF-ML-LNS into Appendix A.7. We show that except for the empty (32x32) setting studied by MAPF-LNS, our sums of delays are significantly lower than both previous works. Unclear to us, MAPF-ML-LNS often reports significantly higher sums of delays than the original MAPF-LNS. While compute resources may be different, we believe that our sums of delays are reasonable or better compared to MAPF-LNS and MAPF-ML-LNS. The better solution qualities that we see may be explained by the difference between using PBS vs PP as the subproblem solver, as illustrated in Appendix A.2. Unfortunately, we could not compare AUC directly with either work, as they do not report absolute AUCs. We believe that our sums of delays are worse in the empty (32x32) setting than MAPF-LNS because this is the only setting where MAPF-LNS finds it advantageous to use EECBS [1] as the initialization algorithm (see MAPF-LNS Table 2), while we only use PP and PPS as the initialization algorithms.

[1] Li, Jiaoyang, Wheeler Ruml, and Sven Koenig. "Eecbs: A bounded-suboptimal search for multi-agent path finding." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 14. 2021.

Regarding generalization performance to different number of agents, in Table 2 we show that our models are reasonably generalizable, as demonstrated between different number of training ($|A| = 350$ or $|A| = 250$) and testing agents ($|A| \in \\{250, 300, 350\\}$).

Regarding reporting performance vs number of iterations, we indeed show that our method uses significantly fewer LNS iterations than baselines to attain a given sum of delays. In new Appendix A.8, we graph the sum of delays vs iteration for all settings. We find that the conclusions here are similar to Appendix A.7, and that our method reduces both the number of LNS steps and the runtime needed to attain a given solution quality.

Regarding the reviewer’s request for code, we hope that the concern for reproducibility is alleviated by our additional analysis: 1) the absolute sums of delays comparisons with MAPF-LNS and MAPF-ML-LNS and 2) the per-iteration comparisons of learned vs unguided selection. We are committed to releasing full code and trained models for reproducibility upon publication. We are averse to releasing code before then, especially because the public nature of ICLR review process leaves some room for abuse of released material if our paper were not accepted. Please let us know if the reviewer has further concerns regarding this point, and we will be happy to see how we can address the concerns.

Thank you for the rebuttal (and apologies for the time it took me to read through it). Most concerns are addressed, and I will slightly raise my score.

However, I do not acknowledge the lack of code. Since reproducibility and implementation details (especially regarding MAPF/search algorithms) are important in our community, the concerns regarding abuse should be outweighed by an adequate review since any code may have flaws. Thus, allowing independent checks can improve the overall quality of the work.

We very much thank the reviewer for alerting us to the deficiencies of our current architectural Figures 2 and 3, which we have completely revamped during the rebuttal. We would appreciate the reviewer taking some time to examine our new Figures 2 and 3, which can be viewed by re-downloading the paper from OpenReview. Furthermore, we encourage the reviewer to view our general response to all reviewers, where we also discuss other major rebuttal additions. Here we address some of the reviewer’s comments.

Weaknesses

1. We acknowledge that our work does not aim for theoretical impact; however, we believe that our work provides a new and valuable empirical method. The integration of intra-path attention with 3D convolution is the core aspect of our neural method, and is broadly applicable to general multi-path problems, which occur in multi-agent or combinatorial problems that consider spatiotemporal interactions. Though we focus on LNS, we envision that the same architecture may improve the performance on classification, regression, generative, and decision tasks in these domains.
2. While we do not consider real-world robot experiments in this work, it is a great direction for future work (we have added it to the conclusions). Even without such experiments, our work informs practitioners (e.g., logistics companies) of the potential and limitations of deep neural approaches for LNS-based methods.

Questions

1. We have significantly updated our Figures 2 and 3 to better illustrate the time dimensions. We would appreciate any additional feedback on the new figures!
2. Similarly, please let us know if the updated Figures 2 and 3 allow readers to better visualize the convolutional structures.
3. In our updated Figure 3, we have better illustrated “light-weight” vs “heavy-weight”. The “heavy-weight” transformer attention operations attends across each agent’s entire path (and is thus proportional to the number of agents and T); these operations are contained within the “Convolution-attention block” and are shared across all subsets. The “light-weight” attention operation only operates on the first tensor along each subset agent’s path rather than the entire path, and thus does not depend on T. Thus, both “heavy-weight” and “light-weight” attention utilize the standard transformer architecture, but differ in the size of the inputs, and thus their computational cost.

By following the reviewer's suggestions, we believe we have significantly strengthened our submission. If we have addressed the reviewer's concerns, we hope that the reviewer will consider increasing their score accordingly.

We thank the reviewer for the feedback and suggestions. Here are our responses to each concern:

Weaknesses

1. Yes, the Average Gap (%), Win / Loss, and Final Gap (%) in Table 1 already include the stated model overhead in the 60s runtime (they are exactly the solid curves in Figure 5).
2. Yes, in Table 2, we did indeed find that our method generalizes better than Linear to different warehouse obstacle layouts (random (32x32) during training and empty (32x32) during testing), different destroy heuristics (agent-local $k=25$ during training and uniform $k=50$ during testing), and different number of agents ($|A| = 250$ or $|A| = 350$ during training and $|A| \in \\{250, 300, 350\\}$ during testing). Regarding how we chose these generalization configurations: our generalization experiments are grounded in multi-robot warehousing applications, where it would be uncommon (and expensive!) to have large deviations in floor maps (especially size) or warehouse operating conditions (e.g. 5x fewer robots). Under such circumstances, we presume it would be common practice to train separate models rather than rely on generalization. On the other hand, obstacle locations, number of agents, and subset construction could change on a minute-by-minute or week-by-week basis, and thus we felt that this warranted an investigation into generalization.
3. Adaptive LNS (ALNS), which is used by MAPF-LNS and MAPF-ML-LNS to adaptively adjust subset construction method (destroy heuristic), does not offer significant difference in performance compared to the best fixed subset construction method used in our paper. Indeed, examining Table 2 in the original MAPF-LNS paper, ALNS is often worse than the best fixed destroy heuristic. We also demonstrate this in our sweep experiments in Appendix A.2, Table 7 and Table 6. Therefore, we believe that it is fair to restrict our focus to the best fixed destroy heuristics.

Questions

1. As suggested by reviewers, we revamped illustrations of our architectures in updated Figures 2 and 3 in the paper (please see the updated pdf on OpenReview). Comparing Figure 2 and Figure 3, the Multi-subset architecture shares much of the computation across all $J$ subsets, and the computation specific to each subset is relatively minimal and requires no 3D convolution or attention across space and time. As discussed in Section 5, we may use spatiotemporal pooling for all agent locations and obstacles for both Multi-subset and Per-subset. We also use fp16 precision instead of fp32 precision. Other than these techniques already stated in our paper, we have not used additional techniques behind the scene, though we believe that the model overhead can be further improved if needed with traditional model compression techniques like distillation, pruning, and/or quantization.
2. Indeed, this could lead to the gap turning negative, but that would require a more than 10x speedup over the Unguided LNS baseline.

We hope that we have addressed the reviewer’s concerns here, and we encourage the reviewer to additionally take into account new results presented in our general rebuttal to all reviewers. We hope that the reviewer will consider increasing our score if they agree that we have strengthened the work.

Hi Yudong,

Thanks for your interest!

1. 25 to 100 was somewhat arbitrarily chosen, since data collection is the most computationally expensive and we did not experiment extensively with the amount of data collected. Essentially we ran enumeration until the solution cost nearly plateaus. We will release all experimental parameters soon, and you will find the individual settings there. Yes, J is the number of proposed subsets at each iteration. The heuristic and subset sizes were chosen in the sweeps in Appendix A.2, and listed in Table 1 (i.e. "Agent-local k = 25" corresponds to the agent-local heuristics described in MAPF-LNS [Li 2021].
2. Yes, this is correct except for in Table 2, where we tried to transfer between maps.
3. Yes, evaluation still proposes 100 subsets/iteration, though we did not experiment with this parameter much. As mentioned to Reviewer TyGL earlier, we did not really consider the subset proposal time as 1) all methods except Unguided use the same subset proposal heuristics, 2) the destroy heuristics take 3-4 orders of magnitude less time than the subset solving times.

We've already pushed the code online, but are still working on pushing run configs and model checkpoints!