Neural Neighborhood Search for Multi-agent Path Finding
Authors: Zhongxia Yan
Cathy Wu
Venue: ICLR 2024 poster (2024)
Keywords: Combinatorial Optimization
Neural Architecture
Multi-agent
Path Planning
Primary area: applications to robotics, autonomy, planning

Abstract: Multi-agent path finding (MAPF) is the combinatorial problem of planning optimal collision-avoiding paths for multiple agents, with application to robotics, logistics, and transportation. Though many recent learning-based works have focused on large-scale combinatorial problems by guiding their decomposition into sequences of smaller subproblems, the combined spatiotemporal and time-restricted nature of MAPF poses a particular challenge for learning-based guidance of iterative approaches like large neighborhood search (LNS), which is already a state-of-the-art approach for MAPF even without learning. We address this challenge of neural-guided LNS for MAPF by designing an architecture which interleaves convolution and attention to efficiently represent MAPF subproblems, enabling practical guidance of LNS in benchmark settings. We demonstrate the speedup of our method over existing state-of-the-art LNS-based methods for MAPF as well as the robustness of our method to unseen settings. Our proposed method expands the horizon of effective deep learning-guided LNS methods into multi-path planning problems, and our proposed representation may be more broadly applicable for representing path-wise interactions.

Published as a conference paper at ICLR 2024
NEURAL NEIGHBORHOOD SEARCH FOR MULTI-AGENT PATH FINDING
Zhongxia Yan, Cathy Wu MIT
(zxyan, cathywujemit.edd
ABSTRACT
Multi-agent path finding (MAPF) is the combinatorial problem of planning op- timal collision-avoiding paths for multiple agents, with application to robotics, logistics, and transportation. Though many recent learning-based works have focused on large-scale combinatorial problems by guiding their decomposition into sequences of smaller subproblems, the combined spatiotemporal and time- restricted nature of MAPF poses particular challenge for learning- based guid- ance of iterative approaches like large neighborhood search (LNS), which is al- ready ofate-of-the-art approach for MAPF even without learning. We address this challenge of neural-guided LNS for MAPF by designing an architecture which interleaves convolution and attention efficiently represent MAPF sub- problems, enabling practical guidance of LNS in benchmark settings. We demon- methods
strate the speedup of our method over existing state-of-the- for MAPF as well as the robustness of our method to unseen settings. Our pro- posed method expands the horizon of effective deep learning guidggdggdddddd LNS methods into multi-path planning problems, and our proposed representation may be more broadly applicable for representing path-wise interactions.
INTRODUCTION
Due to recent advances in robotics and artificial intelligence. logistics operations in warehouses have become increasingly automated. As example, hundreds to thousands of mobile robots work warehouses to transport items to their required locations. Limited warehouse space, hardware, and time to fulfill orders provide immense challenges and opportunities to coordinate the tasks and movements of these robots to maximize throughput and minimize congestion. Given the critical- ity and massive throughput of modern supply chains, even small improvements in solution quality would translate to billions of packages delivered faster annually. However, optimal coordination of such robots in real time on large scale, even in simplified discrete simulation, raises intractable discrete optimization problem: the NP-hard multi-agent path finding (MAPF) problem models the coordination of set of agents, each with start location and goal location, and requests collision- free plan to move all agents from their start locations to their goal locations which optimizes the aggregate delay of the agents. While MAPF naturally considers mobile agents like robots in ware- house or vehicles in a transportation system, other related multi-path planning problems may include routing of circuits (Cheng et al. 2022) or pipes.
Large-neighborhood search (LNS) is a general approach for decomposing large-scale optimization (Shaw) (1998) into a sequence of subproblems. LNS has been demonstrated obtain state-of-the- -htthartt solution qualities for MAPF (Li et al. [021a] (022). While studies have shown the effectiveness of deep learning for guiding LNS in other combinatorial problems like integer programming (IP) (Wu et al. 2021 Huang et al.) (023) and vehicle routing problems (VRP) (Li ct al. 2021b), such an approach has remained clusive for MAPF.
In this work, we identify the unique two-fold challenge of leveraging deep neural networks to guide LNS for MAPF. 1) Unlike many combinatorial problems like IP and VRP with graphical structure
among variables entities (Vinyals et al. 2015 Khalil al. 2017, Paulus et al. 2022 Labassil ct al. 2022 Scavuzzo et al., (022), agent-to-agent interactions in multi-path planning problems also correspond moments in simee-fime, where locality relationships must be aptly represented. 2) Due

---

Published as a conference paper at ICLR 2024
to the iterative nature of LNS and the short runtime of multi-path planners, each neural decision for guiding LNS must be made in very limited time (typically less than 0.05s). Essentially, challenge preseribes cumbersome convolutional architectures for representing MAPF subproblems. while challenge 2 demands very low inference time. For example, to sidestep these challenges, (uanln et al. (2022) applies linear model with hand-designed features while suggesting that a graph- convolution-base solution is impractical due to the inference time.
Addressing these challenges in our work, our main contributions are:
1. the first deep architecture designed to enhance LNS for MAPF by selecting agent subsets,
2. runtime speedup over state-of-the-art LNS baselines for obtaining given solution quality, empirical analyses of the generalization of our architectures to unseen settings.
3.
Full code, models, and instructions can be found on GitHub upon publication.
2 MULTI-AGENT PATH FINDING
A multi-agent path finding problem is denoted by P = SA, where agents A = {1..... ., |A] may move within a undirected graph G with vertices and edges (V, Each agent a A has start 8a E V and goal fa E V. Note that for conciseness, we use vectorized subscript 8,1 {8a a E A). An agent transition from vertex V E to e' E V is valid if (v, v') E E. For all v E V. staying is valid move, iee. (v, v) E E. The path Po. of agent is sequence of vertices with length T(p)) == [pal - such that all transitions (pa [t], Pt + 1I) with 0 S t S T(Pa) are valid and the path starts at Sa and end at Ja- The shortest distance d(u; v') between two vertices u, v' E V is the length of a shortest possible path p(u, o²) between v and v'. The cost of an agent's 's path pa is c(pa)= = Tpa)) - d(su. 90.) which is defined to be the delay that the agent suffers. A collision occurs two agents a and a' occupy the same vertex or edge at the same timestep, i.e. Pa[4] (p.[1) [t [t + 11) = 11, (1) and time IS max(r(Pa): (Pp )), which is the common, stay-at-goal formulation (Stern et al. 2019). A solution S = {Pula E A} is set of agent paths and is feasible if no conflicts exist. We consider a MAPF objective of total delay minimization: ming c(S) = Ep.es c(pa) such that S' is feasible.
Pa (4] or
3 RELATED WORK
Multi-agent Path Finding Nearly all methods for solving MAPF rely heavily running single- agent path planner such as A* search (Hart et al. 1968) or SIPP (Phillips and Likhachev 201T) multiple times, while holding paths of some set of other agents constraints. A simple MAPF al- gorithm is prioritized planning (PP) (Erdmann and Lozano-Perge 1987). also known as cooperative A* (Silver 2005), which plans one agent path time in random agent order while avoiding col- lisions with all previously planned agent paths and obstacles. Conflict-bass based Search (CBS) (Sharon et al.) 2015) is a seminal algorithm which relies backtracking tree-search to recursively resolve pairs of agent collisions. As part of our algorithm. we leverage a more scalable extension of CBS called Priority-based Search (PBS) Ma al. 2019), which heuristically reduces the number of pairwise conflicts to resolve but is suboptimal and incomplete.
Methods Learning- based methods for optimizing combinatorial problems typically can be classified constructive or iterative Kwon et al. 2020). Constructive methods such as Vinyals et al. (2013): et al. ( Kwon et (2020) are trained autoregressively generate one more feasible solutions. On the other hand, iterative methods, in- cluding LNS-based methods in integer programming, ILP, and VRPs (Wu et al.) 2021 Huang et al.) al., 2021b), start from an initial (often poor but feasible) solution and iteratively modify the solution to improve the solution quality. Constructive methods are often very fast in practice, but could yield lesser solution qualities than iterative methods.
Constructive vs Iterative Learning-baat
2023
Large Neighborhood Search for MAPF MAPF-LNS (Li et al., 2021a) starts from initially feasible solution then iteratively selects heuristically constructed subsets of agent paths to reoptimize while holding the rest constant. MAPF-MI-LLNS (Huang al. 2022) learns linear model rank
2

---

Published as a conference paper at ICLR 2024
Gurrent solution for lenation I
New s for ierentiion
+
Union
Unguided LNS
hon-subutt paths
Construct Subset
P(S),
-Ayy SAye
Neural LNS
Salve
New subset paths
Construct Subset
(s,)
NNN
(12334533 5 PoPPPP
Construct Subset
P .0))
NIN
:
Solre
Constrrct Sulhant
P(S.aa)
NW
New subsstution
Supproblem P
Construct Subset
Uniform: agants
Subprobiem P(S. n)
fo
Extimated imprrsmmnnt <(S.) c(5))
S
Solution
Agunttlocal: choces aagne,
2 Ieattty agarns
Subset
R
A = (4.5)
a (1223)
Internaction-loall caacso RePnaction then anctity agrens
Training only
Solve
Starts Sp, g02b de., wwb.uuuotttttooooocoooooooooo.. patho Sot,
P5
Figure 1: Our neural LNS framework for MAPF (counterclockwise from top left). Dotted (solid) arrows indicate that one (all) branch(es) must be taken. At each LNS iteration feasible solution St. In unguided LNS, a subset o is constructed with either Uniform, Agent-local, or Intersection-local heuristics. In neural LNS, J subsets constructed, their corresponding sub- problems are evaluated by the neural network, and the subproblem P(S", a)) with the best estimated improvement selected. In both cases, the subproblem P(S", a) is then solved obtain new sub-
have current
solution Sa. which forms part of the solution Si+1 at the next iteration + 1 if its solution quality improves upon S.,
the potential improvements of these subsets and prioritize which subset reoptimize. MAPF-LNS2 (Li et al. 2022) considers infeasible starting and intermediate solutions. These LNSS-based methods obtain state-of-the-a solution qualities for problems where a feasible solution can be found, while orthogonal recent work like LaCAM* (Okumura) 2023) instead focus on state-of-the-ar fcasibility in very-dense settings. Given the orthogonality of feasibility and solution quality, we choose to extend MAPF-LNS rather than MAPF-LNS2. Unlike MAPF-ML-LNS. we efficiently represent the spatiotemporal problem structure with deep neural network rather than handcrafting features.
Other learning-based Approaches for MAPF Huang al. 2021) leverages linear model with handcrafted features to guide CBS in problems with at most 200 agents. Damani et al. (202T) applies multi-agent reinforcement learning to decentrally coordinate agents based on local neighborhoods encoded by convolutional neural networks (CNNs), rewarding each agent when it reaches a goal. However, while this approach is scalable, its solution qualities are inferior to PBS and MAPF-LNS due to limitations of decentralization. |een et al. (2021) applies 2D CNN to classify the effectiveness of solvers in small MAPF problems with less than 100 agents.
4 NEURAL LARGE NEIGHBORHOOD SEARCH FOR MAPF
We illustrate our overall framework in Figure Given the MAPF problem P, let S be a feasible initial solution. For each improvement iteration 0- < 1, let St be the current (feasible) solution.
In unguided LNS, a subset of agents a C A of size is constructed with one of three subset- construction heuristics described in Li et al. 2021a):
1. Uniform: uniformly randomly sample k agents to construct C C.
2. Agent-local: sample one agent with nonzero delay which has not been recently sampled, then perform random walk to sample
nearby agents space and time.
3. Intersection-local:: sample any vertex of degree 2 3, then perform random walk sample k agents near the intersection.
Given St and agent subset a to reoptimize, we define the corresponding subproblem P(S a) = (G, Sa, Ga, 5t aaaa) to be constrained MAPF problem with k agents. The current paths St for the
3

---

Published as a conference paper at ICLR 2024
agents are discarded. The paths of the |A| k non-subset agents A \ are held constant as spatiotemporal obstacles, essentially changing the static graph G to be a varriig graph. The subproblem can be solved by a MAPF solver, e.g. Priority-based Search (PBS), to obtain new the
subsolution Saa = Solver( P(S*, a)). The solution at time + is then si+1 < S U S A/a
improvement O - ((S.) -c(S)) is positive, otherwise S c S
In neural LNS, we heuristically construct J agent subsets (a1....., 0..) corresponding to a set of subproblems P {P(S", ag)] ر i J/. Each subproblem P(S", a2) is evaluated with a trained neural network (P .g)) whose output is improvement ōgelver (P(S* az)). The top-scored subproblem P(S a) argmaxrep' fo(P) is selected, solved, and incorporated into the full solution. As discussed in Section neural LNS is similar in structure to MAPF-LNS and MAPF-MI-LNS.
approximating the quality of the true solver
4.1 CHALLENGES OF GUIDING LNS
The key challenge of designing a deep neural network fa for guiding LNS for MAPF is to design suitable representation for subproblem P(S a) (G, Sas Ia: S Saxa)) Previous -NN-bbdddeed MAPF works (Ren et al. 2021) use 2D CNN to encode 2D spatial tensors representing obstacles in G' and starts 8a and goals 9a of agents. However, due to the LNS context, we must also represent hundreds paths AA of non-subset agents A \\ as hard occupancy constraints to the subproblem.
To capture these dense spatiotemporal relationships, we utilize 3D convolutions in our architectures. In contrast, MAPF-MI-LNS (Huang et al.. 2022) designs linear summary features for 5% AA1o (see Appendix A.4): meanwhile, a sumilar work for VRP (Li et al. 2021b) does not need to capture the non-subsed agents A \\ a at all due to the lack of space-time interactions between a and A a.
4.2 NAIVE SUB-SU ARCHITECTURE
Carrent suboct parta
parto (ar Nen subeet patts She obstades
Current patio 5
pathip(rr)
[LA3)
features
(12)
Ave [3)
incresiry
Meighttd mwvrage paoting
Bepest with noreasing cherneh linght with
Flathen
Fally connected lepers
Predict Improvement
Learned
NPPS .e
"3p comalationn
connoutiion, poolingg
Per-Subset architecture consisting of featurized paths and obstacles, 3D convolutions, 2D convolutions, and finally fully connected network. The current paths S and shortest paths p(s,g) g) for all agents are illustrated for reference (top right).
Figure 2:
Intuitively, we propose to featurize S/y,0 as a 3D, one-hot encoded x W x T obstacle tensor, where T is a time cutoff chosen roughly as the average path length of the agents. Specifically, for each agent at time 0 t S min(T(pa), 1) and (y, = [t].], we set entry (y, x, t) in the tensor. Similarly. for every non-moving obstacle at position (y.z), we set entry (y, x. t) in the obstacle tensor for all 0 < t < T. To maximize spatiotemporal alignment with the obstacle tensor, we additionally one-hot encode the current subset paths St into 3D tensor, providing information to quantify 5(P(S*, a)) = c(St. Solver( P(S .)). Finally, we one-hot encode the shortest subset paths p( 9a) {p(s.. 9a la a into a third 3D tensor, providing information potential gains of running the solver. Despite these features, the truncation of long paths and the one-hot encoding of subset paths unavoidably lose some information.
We stack the three tensors into a 3 x W x H x T tensor as input into the neural network. Our con- applies sequence of 3D convolution blocks, aggregates
volutional architecture, shown in Figure along the temporal dimension, applics a sequence of 2D convolution blocks, flattens, then applies a fully connected network. We denote this architecture the Per-Subset architecture.
4

---

Published as a conference paper at ICLR 2024
4.3 MULTI-SUBSET ARCHITECTURE
Our core design principles for an effective architecture for guiding LNS are 1) to permit trajectory- level information flow between any two agents with intersecting or adjacent paths, and 2) amortize computation across multiple subproblems. While 3D convolution alone efficiently encodes spa- tiotemporal agent-agent and agent-obstacle interactions at any point along agent paths, convolution is inherently a local operation and cannot efficiently capture long-range trajectory-level interactions between the agents, motivating an attention iitentioo-bbsed mechanism. We illustrate our desired inter-agent and intra-agent interaction graph in the top left diagram in Figure 3 Additionally, as the Per-Subset architecture encodes single subproblem, requires additional batching across subproblems for neural LNS. We hypothesize that a new architecture representing trajectory-Ievel interactions be- tween all agents would permit significant shared computation among the subproblems P(S", aş), reducing the total computation for large J. As the representation can be disaggregated into indi- vidual agent trajectories, we can regroup individual agent representations efficiently into arbitrary number of subsets as required by LNS.
We propose an intra-path attention mechanism which, in alternation with 3D convolutions, achieves the desired agent interaction graph. Intra-path attention enables information flow along each agent's current path; 3D convolution provides for information flow between nearby space-time. Essentially, any two agents are two-hop neighbors in this representation if their paths both interact with some common agent at any point. For efficiency, we implement our intra intra-path through series of "gather" and "scatter" tensor operations surrounding a Transformer self ottf-attention (Vaswani et al.) 2017).
We denote this as the Multi-Subset architecture. The input is three H x W x T' tensors correspond- ing to all agents' paths 5¹ all agents' shortest paths p(SA.9A) and static obstacles. A series of convolution-atteniii
blocks is shared across all subsets. Given particular subset of agents aj. we extract the first temporal tensor for each agent from the last intra-path attention layer's 's output, then perform additional layers of Transformer self-attention to predict the score P(St,a;). Therefore, heavy 3D convolution and intra-path operations are amortized across subsets.
Desired agent
pla.s)
Obetade embedding
embedding
embbddinng
Interaction graph
(1221)
Osstacle
DKT features
Obstadle
3D convolution
Intraa patth atbention
Depeat incressing chammeds
Last laver
Fetroct subnetx
Subset transformer attortion
Fully connectedd layers
Predict Imprevements
Convelution-sttentoo
block
"Same" 3D convolusion
Intra-sath transfommer attuntion gaths y
Leamned output troen
Figure 3: Multi-Subset architecture is designed to encode both inter-agent interactions between agent paths and obstacles as well as intra-path interactions for obtaining trajectory-level information (top left). 3D convolutions encode local interactions in space-time, while intra-path attention gener- ates trajectory-level information across an agent's 's entire path. Convolution-atten across all subsets. The current paths S and shortest paths p(s. g) are the same those in Figure 2
blocks shared
4.4 PAIRWISE CLASSIFICATION Loss FUNCTION
Since the Multi-Subset architecture encodes J subsets corresponding to the same St at the same time, we design a pairwise classification loss: for every pair of subsets a, and ay,, let the difference in predicted scores be h " a.)) = (P a2)) fo(P .az)). A hinge loss encourages (S" az, a ) to be positive when (P az)) > 8solver (P(S', azy)) and negative vice versa; the loss is 0 when dsalver (P(S", ax))) òsuiver (P(S aayr)) In summary, this loss encourages the ordering of predicted scores to match the ordering of ground-truth improvements:
max (0, 1 he),
if 8 (P(S) ax))
(P(' az));
E(ha)
max (0, 1 ha),
if Ssutver (P(S) at)) < Ösotvrr (P(S ag)); if 8 (P(S), a.))) = PS (P(S)ay)) )).)
0,
5

---

Published as a conference paper at ICLR 2024
5 EXPERIMENTAL SETUP
We briefly discuss experimental setup in the main text, deferring full details to Appendix A.I
Baselines. To analyze the performance of our proposed Aulti-Subset architecture, we implement the Unguided baseline similarly MAPF-LNS (Li et al. 2021a), the Linear baseline with features from MAPF-MI-LLNS (Huang et al. 2022). and the Per-Subset architecture haseline descrihed above.
Floor Maps. We demonstrate from the MAPF benchmark suite Stern et al. (2019). As illustrated in Figure 4 we use the five largest floor maps studied by [i et al. (2021a) la): empty-32-32, random-32-32-10 warehouse-10-20- 10-2-1, ost003d, and den520d. For readability, we annotate each floor map by their size: empty (32x32), random (32x32), warehouse (161x63), ost003d (194x and den520d (256x257). Starts and goals are each sampled uniformly without replacement from the set of non-obstacle vertices.
methods floor maps, which define the undirected graph G,
(a) empty (32x32)
(b) random (32x32)
(c) ost003d (194x194)
(d) warehouse (161x63)
(e) den520d (256x257)
Figure 4: Warehouse floor maps from MAPF benchmark suite (Stern et al. 2019
Initial Solution. The initialization algorithm does not typically affect the effectiveness of LNS- based approaches (Li al.] [202aa], as long a feasible solution can be reliably found. Prioritized planning (PP) (Erdmann and Lozano-Perez 1987) typically obtains better initial solution quality than Parallel Push and Swap (PPS) Sajid et al. (2012), but the latter more often finds feasible solutions (Li et al. 202 Thus, we use PP if it can reliably find feasible solution for particular setting, and otherwise use PPS.
Solver, Problem Size, Subset Construction, Subset Size. As there are many potential combina- tions of MAPF solvers (e.g. Priority-based Search (PBS) vs PP with a random agent order), subset construction heuristics (Uniform Agent-local vs Intersection-local), and subset size k. perform parameter sweeps detailed in Appendix A.2 to first identify the strongest possible configuration for the Unguided baseline. We find that PP typically has worse solution quality time tradeoff than the PBS. Considering the ranges of problem sizes |A] studied by MAPF-LNS (Li et al. 2021a), we find that PBS offers better quality time tradeoffss than PP in 2/5 of the settings for empty-32-32, 5/5 settings for random-32-33 32-32-10, and 4/5 settings for each of the other three floor maps. Our neural experiments focus on these settings where the PBS solver stronger, as the determinism (PP is stochastic) can be more consistently predicted and the slower runtime of PBS benefits more from neural guidance. For each floor map, we focus on the largest problem size |A] where PBS is the stronger solver; typically Agent-local subsets with k = 25 is the strongest. In very-dense cooblyyoonttrinedd settings, e.g. empty-32-32 with |A] 2 400 agents or den520d with |A] = 900, find that PP with very small à = 5 often is the best unguided LNS configuration. While method is likely applicable to these cases, we acknowledge that the overhead of the neural network may be significant if the runtime of PP k were very short. Unlike Huang et al. (2022)
PBS
do

---

Published as a conference paper at ICLR 2024
not allow model to select subsets with different construction heuristics size since the runtime of the solver on those subsets could be substantially different. Future work could additionally pre- dict the runtime of the solver the subset in addition to the improvement, trading-off runtime and improvement in order to select the best subset.
Data Collection.
To collect training data from a random seed, we execute LNS for 25 to 100 improvement iterations: for each iteration i, we enumerate the solver on J = 100 agent subsets and record all triplets (S', (tj, ópbs (P(S", ag))) as training data. To proceed to iteration i we select the subset with the best improvements ópas. and move to iteration i + 1. We use up to 9000 different initial random seeds. Data collection takes around 10 to 50 hours on 48 Intel Xeon Platinum 8260 CPU cores, depending on floor map size.
Architectural Parameters. For the Per-Subset architecture, we use two 3D convolutional blocks with 32 and 64 channels, respectively, followed by two 2D convolutional blocks with 128 channels each. For the Multi-Subset architecture, we use eight convolution invoouutin-aattenioon blocks with 16 to 128 channels, shared across all subsets, followed by three Transformer multi-head attention blocks with 128 features for each subset. We provide additional architectural ablations in Appendix A.6 The Linear baseline utilizes handcrafted features described in HHang et al. (2022) and Appendix A.4
Training. Multi-Subset and Linear are trained with the pairwise classification loss in Section 4.4
while Per-Subset utilizes clipped regression loss described in Appendix [A.] Training takes less than 24 hours on a single NVIDIA V100 GPU. Hyperparameters of all models are manually tuned on one experimental setting, then replicated across all other experimental settings.
Validation and Test. We validate and test our trained models on different random seeds. The final test results are reported as 95% confidence intervals across roughly 200 previously unseen seed values where feasible initial solutions could be found. For all settings, we assume a planning time limit of Tiimit 60s unless otherwise stated. For absolute comparisons, Appendix [A.7 and A.8 respectively compares sums of delays c(S) with respect to runtime and improvement iterations.
Model Overhead Reduction. As MAPF solvers are fast and any model inference time adds the overall stepwise runtime, we devise techniques to further reduce inference overhead. If necessary, we pre-apply 2D spatial pooling along both W and H for all agent locations and obstacles to reduce the floor map size. We similarly pre-apply temporal pooling if necessary to minimize redundant information. All guided methods utilize a single NVIDIA V100 GPU with FP16 precision for acceleration. Interestingly, we find that the CPU overhead of Linear is significant, so we instead compute features for Linear on the GPU to reduce overhead.
Metrics. For a given seed, denote the solution cost achieved by running Unguided for 600 seconds
as Cmin- We define the gap as gSS) <(S) Gomn 100%, which better gauges the suboptimality of solution. Given a solution quality g. we define the speedup of method X over method Y as the time for method Y to attain divided by the time of method X to attain g. Following Li et al. (2021a), we define the area under curve (AUC) of method as AUC = S Tlimi g(S(()) dt. which takes into account not only the final solution cost but also the rate of decrease, However, we instead report the more interpretable AUC/ iimi:: the average gap. We define the Win Loss metric as the number of seeds where method's 's average gap is lower / higher than that of Unguided on the same seed.
) Cass
6 EXPERIMENTAL RESULTS
6.1 PERFORMANCES ON ALL SETTINGS
In Table I we compare the performance and overheads of all methods under all floor maps. Multi- Subset strongly outperforms all other methods in empty (32x32), warehouse (161x63), and ost003d (194x194), and weakly outperforms Linear in random (32x32) and den520d (256x257). Multi- Subset's overhead is 2x less than Per-Subset for the empty and random settings, which do not pre- apply pooling. Surprisingly, we see that pre-applying 2x temporal, 4x spatiotemporal, and 4x spa- tiotemporal pooling for warehouse, ost003d, and den520d still allows Multi- Suulti-Subett to maintain best predictivity while keeping the model overhead low. On the other hand, when pre-apple pre-applynng similar amount of pooling for the Per-Subset architecture for ost003d and den520d, the model overhead even exceeds the solver runtime.
7

---

Published as a conference paper at ICLR 2024
Table Performance and overhead of all methods. We report the the average solver time per step for the Unguided overhead. All other overheads are additionally incurred by model inference. Gaps and Win Loss account for the model overhead already. Lower gap is better; higher Win is better.
Setting
Metric
Unguided
Linear
Per-Subset
Multi-Subset
Average Gap
42 +
46
31
empty (32x32)
Win / Loss
0/0
136 50
57 129
178 / 8
|A| = 350
Final Gap (%)
19
1
22
1 0.7 +0.013
Uniform k 50
Overhead (s)
0.1
+0.002
+0.03
Average Gap (%)
5.3 0.2
0.3
6.2
5 0.2
random (32x32)
Win Loss
0/0
100
36/ 162
116 / 82
|A| = 250
Final Gap (%)
0.51 0.03
0.05
0.72
0.69 + 0.04
Agent-local k 25
Overhead (s)
0.079
+0.0018
+0.03
+0.012
Average Gap (%)
0.6
0.7
2.
12 0.6
warehouse (161x63)
Win / Loss
0/0
82/103
679
155 30
|A|= = =30 Agent-local k 25
Final Gap (%)
1.7
0.3
2.5
1.6 + 0.2
Overhead (s)
0.21
+0.0025
+0.05
+0.025
Average Gap (%)
43
36 #
35 0.9
22 #
ost003d (194x194)
Win Loss
0/0
180
188 / 12
200 0
|A| 400
Final Gap (%)
24
15
16 0.8
6,5 + 0.7
Agent-local = 10
Overhead (8)
0.063
+0.002
+0.09
+0.013
Average Gap (%)
45 + 0.7
0.7
0.7
& 0.7 200 0
den520d (256x257)
Win Loss
0//
200
45/
|4|= 800
Final Gap (%)
22 0.7
8.8
2.6
8.2 + 0.5
Agent-local 25
Overhead (8)
0.15
+0.006
+0.19
+0.025
6.2 TIME vs SOLUTION QUALITY FOR EMPTY (32x32) AND DEN520D (256x257)
methods on the smallest and largest floor maps. Similar plots for the remaining floor maps are found in Appendix A.3 We observe here that Multi-Sbbee can offer 1.5-4x speedup compared to Unguided, though Linear also offers substantial speedup den520d (256x257) in particular. The model overhead is negligible for Linear, still noticeable for Multi-Subset, but large for Per-Subset. Optionally excluding the overhead allows independently judge the predictivity of the model's representation.
In Figure we illustrate representative time vs gap tradeoff
6.3 GENERALIZATION TO UNSEEN SETTINGS
In Table 2 we test the robustness each method to unseen settings during training by examining the zero-shot transfer performance of two models from Table the model trained on empty (32x32)
with |A| 350 Uniform & = 50 subsets and the model trained on random (32x32) with |A| = 250 Agent-local
subsets. The target settings are empty (32x32) settings with different numbers of agents subset construction heuristics as determined by the parameter sweep in Appendix A.2 We find that the multi-subset architecture transfers particularly well, even better than Linear, the unseen settings. This is particularly surprising for transferring from the random (32x32) source task, where the performance gap between the Linear and Multi-Subset models is small. Unfortunately, could not transfer from empty (32x32) random (32x32) because the obstacle embedding is untrained in the former setting due to lack obstacles. Similarly, we could not transfer between floor maps of different size due differing spatial and temporal embeddings.
7 CONCLUSIONS
In this work, design neural architecture with potential for effectively guiding LNS for MAPF, efficiently representing complex spatiotemporal and agent-to-agent interactions without hand-designed features. While acknowledge that fair computational resource comparisons
8

---

Published as a conference paper at ICLR 2024
100
Unguided Uiner
Linear Multi-Subset
Speadup over Ungulded
Mult-Subset
Cap (50
60
20
10a
10a
100
90
80
70
60
50
40
30
(a) empty (32x32)
100
Unguided
Linear
Linear
Speedup Unguided
2.5
Sur-St
80
PerSubset
Mulli-Subeat
Mult-Subzet
2.0
Cap
60
1.5
40
20
70
20
Time 1st
Gap (%)
(b) den520d (256x257)
Figure 5: Runtime vs solution quality including (solid) and excluding (dashed) model overhead in the runtime, (left) Lower gap is better. (right) Higher speedup over Unguided is better.
Table 2: Zero-shot generalization performance. As an example, "empty. 350, A25" denotes the empty (32x32) setting with A 350 and Agent-local k subsets. Average gap (%) are re- ported for all settings. As the solver runtime is significantly faster for casier target settings, affecting the relative model overhead, we exclude the model overhead here to study the transferability of model predictivity. denotes two easier settings where all methods obtain near-zero average gaps over Tima 60s, so we instead run all methods for a shorter Timm- 10s.
Target
Source
Unguided
Linear
Per-Subset
Multi-Subset
empty, 350, U50
39 + 1
43 +
30 +
empty, 350, US0
42 + I
random, 250, A25
40
41 #
37 #
empty, 350, U50
38
28 + 0.8
empty, 350, A25
42 1
random, 250, A25
39 + 1
40
37 +
empty. 350, U50
36 + 2
36 2
24
empty, 300, A25*
28 +
random, 250, A25
29 +
27
22 # 0.9
empty, 350, U50 random, 250, A25
14 + 1
14 1
9,4 + 0.7
empty, 250, A25*
10 0.5
11 0.7
9.8 +
0.6
8.0 0.4
difficult Unguided does not require GPU, believe that research into deep learning-basee celeration in problems like MAPF is worthwhile due to the rapid advances in GPU technology (our own NVIDIA V100 is generations old). To our knowledge, despite copious research in MAPF, there exists no other work leveraging deep learning for enhancing state-of thehe----- MAPF algorithms our scale. addition, our work demonstrates the potential graphical problems and encompasses problems with complex spatiotemporal constraints, where it may serve as a blueprint for future learning- iterative methods. Our convolution-aatentio blocks may be more broadly applicable for representing pathwise interactions beyond LNS settings. Some immediate extensions of our work include guiding stochastic solvers like prioritized plan- ning. Furthermore, the Multi-Subser architecture may allow direct construction of subsets for LNS rather than evaluating surrisically-constuuce subsets. Finally, future work may investigate the effectiveness of unguided and guided LNS techniques in real-world robotic warehouses.
learning-guiiie LNS beyond

---

Published as a conference paper at ICLR 2024
8 ACKNOWLEDGMENT
The authors acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center for providing HPC resources that have contributed to the research results reported within this paper. This work was supported by the MIT Amazon Science Hub as well as a gift from Amazon.
REFERENCES
Ruoyu Cheng, Xianglong Lyu, Yang Li, Junjie Ye, Jianye Hao, and Junchi Yan. The policy-gradient placement and generative routing neural networks for chip design. Advances in Neural Informa- fion Processing Systems, 35:26350-26362, 2022.
Paul Shaw. Using constraint programming and local search methods to solve vehicle routing prob- lems. In International Conference on Principles and Practice of Constraint Programming, pages 417-431 Springer, 1998.
Jiaoyang Li, Zhe Chen, Daniel Harabor, P Stuckey, and Sven Koenig. Anytime multi-agent path finding via large neighborhood search. In International Joint Conference on Artificial Intelligence (IJCAI), 2a
Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter Stuckey, and Sven Koenig. Mapf-Ins2: fast pairing for multi-agent path finding via large neighborhood search. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 00256-10265, 2022.
Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning large neighborhood search policy for integer programming. Advances in Neural Information Processing Systems, 34:30075-30087, 2021.
Taoan Huang, Aaron M Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning. In International Conference on Machine Learning. pages 13869- 13890. PMLR, 2023.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Ad- vances in Neural Information Processing Systems, 34:26198 11-26198-2221,, 1, 2021b.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural informa-
tion processing systems, 28, 2015.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference on machine learning, pages 17584-17600. PMLR, 2022.
Abdel Ghani Labassi, Didier Chételat, and Andrea Lodi. Learning compare nodes in branch and bound with graph neural networks. Advances in neural information processing systems, 2022.
Lara Scavuzzo, Feng Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning branch with mdps. Advances in Neural Information Processing Systems, 35:18514-18857 2022.
Taoan Huang, Jiaoyang Li, Sven Koenig, and Bistra Dilkina. Anytime multi-agent path finding via machine learning-guided large neighborhood search. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages
2022.
Roni Stern, Nathan R Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, TK Satish Kumar, et al. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Twelfth Anmual Symposium Combinatorial Search, 2019.
Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 1(2):100-107, 1968.
10

---

Published as a conference paper at ICLR 2024
Mike Phillips and Maxim Likhachev. Sipp: Safe interval path planning for dynamic environments. In 2011 IEEE International Conference on Robotics and Automation, pages 6628-5635. IEEE, 2011.
Michael Erdmann and Tomas Lozano-Perez. On multiple moving objects. Algorithmica, 2:477-521, 1987.
David Silver. Cooperative pathfinding. In Proceedings of the AAAI Conference on Artificial Intelli- gence and Interactive Digital Entertainment, volume 1, pages 1 117-122, 2005.
Guni Sharon, Roni Stern, Ariel Felner, and Nathan R Sturtevant. Conflict- search for optimal multi-agent pathfinding. Artificial Intelligence, 219:40-60 2015.
Hang Ma, Daniel Harabor, Peter J Stuckey, Jiaoyang Li, and Sven Koenig. Searching with consistent prioritization for multi-agent path finding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 7643-7650, 2019.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:2118 188-21198. 2020.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! Inter- national Conference Learning Representations, 2019.
Keisuke Okumura. Improving lacam for scalable eventually optimal multi-agent pathfinding. Inter- national Joint Conference on Arlificial Intelligence (IJCAI), 2023.
Taoan Huang, Sven Koenig, and Bistra Dilkina. Learning to resolve conflicts for multi-agent path finding with conffict-based search. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 35, pages 1126-112253 2021.
Mehul Damani, Zhiyao Luo, Emerson Wenzel, and Guillaume Sartoretti. Primal 2: Pathfinding via reinforcement and imitation multi-agent Saaming-lifelong IEEE Robotics and Automation Letters, 200:2666-2673. 2021.
Jingyao Ren, Vikraman Sathiyanarayanan, Eric Ewing, Baskin Senbaslar, and Nora Ayanian. Map- fast: A deep algorithm selector for multi agent path finding using shortest path embeddings. arXiv preprint arXiv:2 102. 12461, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Qandeel Sajid, Ryan Luna, and Kostas Bekris. Multi-agent pathfinding with simultaneous execution of single-agent primitives. In Proceedings of the International Symposium Combinatorial Search, volume 3, pages 88-96, 2012.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830. 2011.
Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. Liblinear: A library for large linear classification. the Journal of machine Learning research, 9:1871-1874, 2008.
Jiaoyang Li, Wheeler Ruml, and Sven Koenig. Eecbs: A bounded-suboptimall search for multi-agent path finding. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 12353-12361 2021c
11

---

Published as a conference paper at ICLR 2024
A
APPENDIX
CONTENTS
A.1
Setup
A.2
Parameter Sweep for Solver, Subset Construction Heuristics, and Subset Size k
A.3
Runtime vs Solution Quality for All Settings
Handcrafted Features for Linear Baseline
A.5
Software Framework and Code
A.6
Architectural Ablations)
7
Direct Comparisons with MAPI-LNS and MAPI-ML-LNS
10
A.8
Performance by Iteration
11
A.1
SETUP
We discuss the full experimental setup here for all experiments performed in our paper, unless al- ready discussed in Section
Warehouses The MAPF benchmark suite Stern et al. (2019) is a set of empty, random, maze-like, game-like, and city-like floor maps. Here describe the floor maps presented in Figure 4
1. empty-32-32: a size 32 x 32 map with no static obstacles.
2. mandom-32-32-10- a size 32 map with randomly sampled static obstacles covering 10% of the vertices.
warehouse- 10-10000--------10 obstacles covering 44% of the vertices.
size 161 63 procedurally generated warehouse with static
4. ost003d: a size 194 x 194 map taken from the game Dragon Age Origin, with obstacles covering 65% of the vertices.
5. den520d: a size 256 x 257 map taken from the game Dragon Age Origin, with obstacles covering 57% of the vertices.
The starts and goals are each selected uniformly at random without replacement from the set of non-obstacle vertices. All floor maps are undirected graphs
Architecture Parameters For the Per-Subset architecture, we use two 3D convolutional blocks (convolution, batch normalization, ReLU, max pooling) with 32 and 64 channels, respectively, fol- lowed by two 2D convolutional blocks with 128 channels each. For the Multi-Subset architecture, we use eight wewvolution-attentin blocks with (C' =) 16, 16, 32, 32, 64, 64, 128, and 128 channels, respectively, shared across all subsets, followed by three Transformer multi with 128 features for each subset. time cutoff of 48 used for both architectures in empty (32x32) and random (32x32), T = 96 for warehouse (161x63), T = 192 for ost003d (194x19)) and 7 216 for den520d (256x257). Pre-applied temporal pooling with factors 3, 6, and are used for Per-Subset for warchouse, ost003d, and den520d, respectively; pre-applied temporal poooling with factors 2, 4, 4 are used for Hulti-Subset, respectively, Pre-applied spatial pooling with factors 2, 4, and 4 are used for Per-Subset, respectively. Pre-applied spatial pooling with factors 4 are used for Multi-Subset for ost003d and den520d.
attention blocks
Loss Function for Per-Subset Architecture Unlike architecture cannot efficiently encode large multiples of J subproblems simultaneously. There- fore, rather than pairwise classification loss, utilize clipped mean squared error loss. Denoting fe = fo(P az)) to be the neural network's output score for subproblem and 8solver = 6 (S
and Linear, the Per-Subset
(St,a,) a.4)) to be the ground-trutt improvement, this loss function
{(fo 88
ag) (8,0g))
(Jo min(stop grad(fo). 0) max (SSolver, 0))

---

Published as a conference paper at ICLR 2024
with gradient
de(fo 15),az) d/o
-- (fo cainssto-ggra((nne 0) max((Ssaterr) 0))
ósotver
fo.
if fe and ò > 0,
- -fo.
if fa > and d S 0,
= 2
Ósotvers
if fa S 0 and ò > 0,
0,
if fe 0 and å S O,
which only encourages fo be non-positive rather than forcing fo approach ō when dsalver < O; this allows extra network capacity to be dedicated to fitting positive improvements well, rather than unnecessarily fitting negative improvements.
Additional clipping similar to that in Equation is also performed for the loss in Section 4.4
Training We train all neural models with the Adam optimizer Kingma and Ba (0014), decaying learning rate (0.01 for Per-Subset and 0.0001 for Multi-Subset) with cosine annealing across 100000
training steps. Per-Subset architecture sees a minibatch of 512 subsets per gradient step, and Multi- Subset architecture sees minibatch of 16J 1600 subsets per step. Training takes roughly 24 hours on a single NVIDIA V100 GPU. For the Linear baseline, we found the Scikit-learn Pedregosal et al. (2011) implementation of linear support vector machine (SVM) Fan et al. (2008) with full- batch gradient descent to outperform our minibatched gradient descent-based training loop; we sub- sample the subsets required stay within the batch size limits of linear SVM (note that the total batch size scales with J²). Training for the Linear baseline takes around 10 minutes to hour on single 48-CPU Intel Xeon Platinum 8260 processor. Hyperparameters of all models manually tuned on one experimental setting, then replicated across all other experimental settings.
Validation During training, we periodically validate our learned model's predictivity on a vali- dation set with held-out seeds. Predictivity is measured by collection of proxy metrics, such as correlation between predicted scores and ground-truth improvements, rather than directly running guided LNS with the current model checkpoint, which would take more time. The checkpoint with the best validation performance (typically the one at the end of training) is selected, and further val- idation may be performed for additional hyperparameter selection by guiding LNS with the selected checkpoint.
Test The final selected model from validation tested on 200 additional held-out random seeds by guiding LNS. All reported results are performances on the test set.
For each given seed, all methods (unguided or guided) share the same initialization solution. The planning time limit of Timit 60s is used by previous LNS-based MAPF work (Li et al. 2021a Huang et al. 2022) and is motivated by the short-horizon nature of MAPF and path planning in general. We observe that learned models may often repeatedly select similar subsets across consecutive LNS iterations, resulting in low or no improvement. As such, we design strati- fied sampling procedure where we filter away any subset more similar to previously selected subsets than randomly sampled threshold, and permit the learned model to select among the rest of the subsets. We observe that this procedure is effective in alleviating the similarity issue.
Guiding LNS
Fitting Proxy for Solver Runtime As the solver's runtime is noisy to measure and heavily depends on the current computation load of the machine, we instead collect datasets of number of low-level search iterations by the solver as features and ideal solver runtimes as labels. For every setting (floor map. |A], construction heuristic, k), features and ideal solver runtimes are obtained by running unguided LNS with no other processes the machine. We obtain fitted linear models with 0.95-0.99 coefficient of determination across five folds of cross-validation.
Aggregating Metrics Across Seeds We always report the 95% confidence interval of the mean across the 200 test seeds, though any seed without feasible initialization excluded. e.g. compute the 95% confidence interval of the average gap at a given runtime, we perform bootstrap sampling to obtain 1000 resampled means of 200 gaps, then take the 2.5th percentile and 97.5th percentile
2

---

Published as a conference paper at ICLR 2024
of those means the 95% confidence interval. To compute the mean and confidence interval of speedups corresponding to different seeds at a given gap, we take the geometric mean rather than the arithmetic mean, each speedup is ratio. When plotting speedup vs gap. some seeds may not reach a given gap within 10s of runtime; therefore, we only consider the range of gaps reached by all seeds when plotting, rather than [0, 100).

---

Published as a conference paper at ICLR 2024
A.2 PARAMETER SWEEP FOR SOLVER, SUBSET CONSTRUCTION HEURISTICS, AND SUBSET SIZE k
We perform sweeps to identify the strongest settings for Unguided LNS for the different warehouse maps and use these settings for guided LNS. As seen in Figure 6 PBS fairly dominant for most empty (32x32) settings with | 400. On the other hand, PP with k becomes dominant for |A] 2 400. In our work, we experiment with settings where PBS is dominant, since a determin- istic solver could be easier to predict for learning-basd -aaedd methods. As seen Figure 7 PBS the dominant solver across wide range of problem settings anyways.
Following Li al, (2021a), we additionally sweep over i with Adaptive LNS (ALNS). We do not see benefits of ALNS over the best fixed subset construction in random, empty, warehouse, and den520d. Only ost003d benefits slightly from ALNS. This is fairly consistent with the findings of Li ct al. (202 Table 2. Thus, we choose to study the more controlled setting of best fixed subset construction rather than adaptive subset construction.
Unlike Huang et al. (022). we do not select between subsets of different sizes k. Intuitively, sub- problems with different sizes could require significantly different amount time to solve by the solver. Neither
work nor MAPF-MI-LNS devises method to account for the runtime of solv- ing subproblems: purely selecting the subset offering the most improvement may be highly subop- timal if the subproblem takes relatively longer to solve than other candidates. Thus, choose to use a fixed subset size k, assuming that subsets of the same size likely take similar amount of time solve. This assumption confirmed by our iteration-basee results Appendix [A.8] Our method is likely compatible with future LNS methods designed to account for both predicted improvement and predicted runtime of subsets.
4

---

Published as a conference paper at ICLR 2024
Compoucta bm
Conttracien: Uettr Agreniica
6468
Sun ChEEE
7359
5406
(a) empty (32x32) |4| = 250
(b) empty (32x32) |^| = 300
2006
Ededractoon mieection bodl GeatttcclerApprt.. Apeieezzi
258
Sarie FB5
Salver whree
2006
30000
2500
3256
Time
(c) empty (32x32) |A| = 350
(d) empty (32x32) |A] -400
Figure 6: Effect of solver, subset construction heuristics, and agent subset size k in unguided LNS for empty (32x32). Colors distinguish subset sizes k line styles distinguish construction heuristics, and line widths distinguish solvers. The Adaptive construction heuristics adaptively chooses between Uniform, Intersection-local, and Agent-local heuristics following Li et al. a202
5

---

Published as a conference paper at ICLR 2024
2006
4003
Composeaa hm
3033
riased
Oratracder: Hanueiiniaal
156
Conmrseao Aoptve
Crntrrcter: Sgaribea
1298
Schar
Se FRS
Sum Collerre
300
1ime
(a) random (32x32) |A 250
(b) warehouse (161x63) |4| = 300
22
20000
Consructox miseette
1600
Esiitration fmm
Conttrsdeen Hingtonn
Eieddrattoon Nagtar
Sever
5006
50000
4000
Time
(c) ost003d (194x194) [A| = 400
(d) den520d (256x257) [A] 800
Figure 7: Effect solver, subset construction heuristics, and agent subset size k in unguided LNS. Colors distinguish subset sizes k, line styles distinguish construction heuristics, and line widths distinguish solvers. The Adaptive construction heuristics adaptively chooses between Uni- form, Intersection-locce and Agent-local heuristics following Li et al. (2021a).

---

Published as a conference paper at ICLR 2024
A.3
RUNTIME VS SOLUTION QUALITY FOR ALL SETTINGS
Here, we report the full results corresponding to Figure 5
in the main text.
100
Unear Ungaiced
Spooddus avd Ungaased
Per Subset
Linar
Mult: Subset
(3)
60
20
empty (32x32)
80
Unguided ded Linsar
Speedtur tven Erqultedd
62
Muili Subuct
Sur-ttbstt
CAB (50
2.0
Linor
Per-Susset
Mulli Subuc:
20"
15a
Time 6)
Cup 754
(b) random (32x32)
Ligg loed UJeer
Speedkss ovee Ennouneed
2.5
Inner Sueeet
Multi Subst
RenGubeet
2.0
2.5
2.0-
0.5
124
10
20
50
20
Cap 1%1
(c) warchouse (16lx63)
Ungulced Unear Per Surbuttet
Lincar
Subsot
Subset
Mult-SSuee abeet
60
60
15a
10
50
6:
60
40
Time
Gop (%)
(d) ost003d (194x 194)
Uiquitted Uneer
Linear
Spoedder King Stedd
Sen-Sutseet
RenGubtet
Huith Suboer
MulliSulee Substt
60
16a
10
90
30
60
50
40
30
Cap 1961
(e) den520d (256x257)
Figure 8: Runtime solution quality for all considered floor maps including (solid) and exclud- ing (dashed) model overhead in the runtime. (left) Lower gap is better. (right) Higher speedup over Unguided is better.
7

---

Published as a conference paper at ICLR 2024
A.4 HANDCRAFTED FEATURES FOR LINEAR BASELINE
The features from our Linear baseline are hand-designed by Huang et al. (2022) and reiterated here. Given current solution S*, to featurize subproblem P(S", a). features calculated for every agent E then combined into aggregate features for the subset a and the non-subset a, which are then concatenated.
Table lists the 16 features (Huang et al. (2022) states 17, but only lists 16) for each agent a, consisting of static features which only depend on the problem = (G, SA,9A) and 10 dynamic features which depend on the current solution St. The heat of vertex E V is defined to be the total number of times the vertex is occupied by an agent. The degree of vertex v E is defined to be the total number of edges to from v, excluding the self-edge (v, v). The per-agent features are then aggregated with minimum, maximum, sum, and average across and \ a, resulting in 4 2 16 128 total features for the subset a.
We vectorize the computation these features to allow faster feature-computation on GPU, as the CPU-only feature computation tends to be several times slower.
Table 3: Linear features from Huang et al. (2022) for each agent These features then aggregated by subset a and non-subset a.
Description
Count
Static features
Distance between start and goal: d(sa, 9a)
Row and column numbers 8a and Ja in graph Degree of the goal fa
Dynamic features
10
Delay of c(S.)
Ratio between delay and shortest distance: )(S.:9.)
cS.)
Minimum, maximum, sum, and average of heat values along path Pa
Number of timesteps that path Pa passes a vertex with degree 1 S j S 4 before reaching the goal
A.5 SOFTWARE FRAMEWORK AND CODE
A key challenge of studying learning-basee based approaches for MAPF, especially LNS-based, is the low-level nature of MAPF, where the solvers must be implemented in low-level language like C++. Performing (especially learning-based) experiments within such context is tedious and error- prone for the researcher. We design software framework which abstracts away low-level MAPF operations into a C++ library, exposing a high-level interfaces which can be controlled through Python via convenient pybind11 I interface while maintaining execution speed. We hope that such framework could prove useful for MAPF researchers in general, greatly reducing the need to interact with low-level C++.
8

---

Published as a conference paper at ICLR 2024
Table 4:
Architectural ablations in random (32x32) |A|
250. Gaps and Win / Loss do not
include model overhead. Lower gap is better; higher Win is better.
Metric
Unguided
Linear
Per-Subset
Multi-Subset (Convolution Only)
(Full)
(Attention Only)
Average Gap (%)
5.3 0.2
5.4 + 0.3
5.0 + 0.2
4.6 + 0.2
6.6 + 0.3
5.2 0.2
Win / Loss
0/0
106 / /92
128 / 70
151 / 47
27 / 171
112 / 86
A.6 ARCHITECTURAL ABLATIONS
To assess the importance of our proposed intra-path attention mechanism as part convolution-atiention block in the Multi-Subset network, conduct an ablation study to under- stand the individual contributions intra--arii patta-ppthhha attention and 3D convolution in our architecture. For Multi-Subset (3D Convolution Only), remove the intra-path attention mechanism and double the number of 3D convolutions to keep model capacity similar. For Multi-Subset (Intra-path Attention Only), remove the 3D convolution and double the number of intra-path attention layers; however this requires us to use (C =) 128 channels at every layer (increasing the model capacity) as the intra- path attention itself cannot change the number of channels from layer to layer. Due to the changes in architecture, we compare performances without model overhead to focus on the predictivity of the different architectures.
In Figure 9 we see that our intra-path attention is critical to Multi-Subsee performance, while 3D convolution also contributes moderately. Corresponding metries are reported in Table
80
Unguided
Linear
Per-Subset
60
Multi-Subset
Gap (%)
Multi-Subset (3D Convolution Only)
40
Multi-Subset (Intra-path Attention Only)
20
0
100
101
Time (s)
Figure 9: Runtime vs gap for architectural ablation in random (32x32) |A] model overhead in the runtime. Lower gap is better.
250, excluding

---

Published as a conference paper at ICLR 2024
Table Absolute "sum of delays" comparisons with MAPF-LNS (Li et al. 2021a) and MAPF- ML-LNS (Huang et al., 2022). LNS, LNS (ML-LNS), and Unguided denotes the best unguided
LNS as respectively reported by Li al. 2021a), Huunn et al. (2022). and our work. ML-LNS and
Linear denotes the best linear-guided LNS as respectively reported by Huang et al. (0022) and our work.
Setting
LNS
LNS (ML-LLNS)
Unguided
MI.LNNS
Linear
Multi-Subset
empty |A| 350
743
N/A
1302
N/A
1263
1043
random |A| 250
3388
806
516
843
532
515
warehouse |A| = 300
1400
4719
670
3547
686
658
ost003d |A| 400
2427
6907
2736
6584
2119
1760
den520d A| = 800
7408
> 12558
4637
> 11535
2397
2229
A.7 DIRECT COMPARISONS WITH MAPF-LNS AND MAPF-ML-LNS
While computation resources may differ from previous related works (Li et al. 2021a Huang jet al. 2022). we attempt to provide absolute comparisons of sums of delays attained by all methods 5 The sum of delays is a measure of final solution quality: the final cost attained minus the shortest individual cost for each agent. The sums of delays of all methods here are attained with 60s of solution time including the model overhead. Like previous work, here we use the 25 seeded scenarios provided by the MAPF benchmark suite Stern et al. (2019). For our Unguided, Linear, and Multi-Subset, we use the same hyperparameters as in Table [ which represent the best fixed subset construction heuristic and subset size k. We take the best MAPF-LNS (Li eL 2021a) sums of delays as the minimum of their Table 4, Table 2, and Table We take MAPF-ML-LAE (Hang et al. 2022) sums of delays from their Table 3.
We make several observations. Our numerical sums of delays here are fairly consistent with our hy- perparameter sweeps in Appendix A.2 which uses different set of seeds. Comparing the baselines, MAPF-LNS's 's own reported sums of delays (denoted as LNS in Table 5 are usually significantly lower than MAPF-LNS sums of delays reported by the MAPF-ML-LNN (ML-LNS)) Table 5). as seen in warehouse, ost003d, and den520d. Our Unguided sums of delays often significantly lower (random, warehouse, den520d) than those of MAPF-LNS, illustrating the advantage of using PBS rather than PP as the subproblem solver, which has not been studied by previous works; indeed, the runs with PP as the subproblem solver in our hyperparameter sweeps in Figure 7 more closely resemble the best reported MAPF-LNS performance. Our Linear baseline significantly outperforms MAPF-ML-LNS in all settings. Multi-Subset improves the sums of delays over Unguided, especially in empty, ost003d, and den520d.
paper (denoted as LNS
We point out two cases where our sums of delays are worse than MAPF-LNS. For empty |A| 350, MAPF-INS moderately outperforms Unguided and Multi-Subset. We hypothesize that this is because Li et al. (2021a) uses EECBS (Li et al.) 2021c) as the initialization for this particular setting while use PP. which is casier implement in our codebase than EECBS (which contains many hyperparameters itself). For ost003d |A| 400, MAPF-LNS slightly outperforms Unguided (but not Multi-Subset). We observe in Figure that adaptive LNS slightly improves the performance of Unguided this setting. Nevertheless, the difference between MAPF-LNS and Unguided is dwarved by the difference between Unguided and Multi-Subset.
Overall, we find that our methods compare reasonably with prior work. We additionally illustrate corresponding time delay in Figure
10

---

Published as a conference paper at ICLR 2024
12300
bed
13303
2000
1090
2303
1000
101
334
18
(a) empty (32x32)
(b) random (32x32)
(c) warchouse (161x63)
8900
Linerr
Her buboct
15300
Hatti Subest
6000
6000
Ungulded
10300
Utear
Per Sutset
5200
2000
MJB: Subuet
Time 50
(d) ost003d (194x194)
(e) den520d (256x257)
Figure 10: Runtime vs sum of delays for all considered floor maps including model overhead in the runtime. Lower sum of delays is better.
A.8 PERFORMANCE BY ITERATION
For the same runs studied in Appendix A.7 we demonstrate the sum of delays with respect to number of LNS iterations in Figure II We similar behavior as in Figure [00 that the Multi- Subset architecture significantly improves the decision quality and reduces the number of iterations needed to attain given cost. The similarities in the plots also confirm our assumption that subsets of the same construction heuristic and size & take roughly similar time to solve.
Note that because we each method for 60s, the number of iterations may differ between problem instances. As we must compute the mean and confidence interval of the performance across all seeds for each method, we truncate all runs at the minimum number iterations across all seeds for each method when calculating the mean and confidence interval. This choice does not have a significantly visible effect due the log-scale of LNS iteration in Figure 11
670
11m Aidd
8109
Ford Jtar
1000
105
14
1P
12
104
(a) empty (32x32)
(b) random (32x32)
(c) warehouse (161x63)
0020
Per Subeet
Liver
7050
Hu butct
0000
5050
Ung-ittd
4000
Utear
3050
MJB: Sumoet
Pe: Suiset
2000
(d) ost003d (194x194)
(e) den520d (256x257)
Figure 11: LNS iteration vs sum of delays for all considered floor maps. Lower sum of delays is better.
11


Reviews:
[{"review_id": "7QOOIJoOqZ", "reviewer": "Reviewer_CV86", "summary": "1The paper proposes to use a deep learning-based framework to select agent subsets to destroy in LNS for the problem of multi-agent path finding (MAPF). Two architectures are proposed: per-subset and multi-subset methods. In experiment, two architectures are tested on five maps of different sizes. In particular, multi-subset performs a lot better than the other approaches.", "questions": "You mentioned two challenges in the intro with the second one being the overhead of machine learning inference time. Can you elaborate more on how you address this issue with your model?\nThere is a short paragraph in section 5 that describes some of the engineering details. Do you use other techniques behind the scenes?\n\n\nYou use c_min to compute the gap, which is the solution found by the baseline within 10 minutes. Could this lead to a negative gap when your method finds better solutions within just 1 minute? (though it is unlikely to happen)", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The deep neural network architecture that incorporates spatiotemporal information seems to be a good contribution to the MAPF community. \n\n2. Empirical results demonstrate the usefulness of the multi-subset architecture.", "weaknesses": "1. The description of the runtime overhead is a bit unclear. I just want to confirm since this is important: when you run your method for 60 seconds, this includes the machine learning inference overhead, right? Though, from the plot it is clear your approach is still the best when the overhead is included. \n\n2. Have you tried generalizing your model to other agent sizes on the same map as training (similar to what Huang et al show in their paper)?\n\n3. It seems unfair to restrict the unguided approach to use only one destroy heuristic, this restriction is made mainly for the benefit of the ML-guided approaches. In the MAPF-LNS paper, it has been shown that the adaptive destroy heuristic is much better for the unguided approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZSJyz8xiDR", "reviewer": "Reviewer_TxMF", "summary": "This paper is a study that utilizes a neural network structure based on 3D convolution to perform multi-agent path finding from a spatial-temporal perspective. Unlike previous research that used linear feature-based machine learning structures, this paper eliminates the feature dependency through 3D convolution-based architecture.\n\nBy selecting a subset of k diverse combinations of agents from the entire agent set and comparing the changes in cost, it distinguishes between the multi-subset approach, which aims to find the optimal subset structure, and the per-subset approach, which uses only a single subset. Through testing, it confirms that the multi-subset approach performs better. Furthermore, it also demonstrates performance improvements when comparing with the Unguided method, which extracts subsets using predefined rules, and the traditional Linear method.", "questions": "Overall, the representation through diagrams is lacking. First, this paper places significant importance on the Time dimension. However, it merely mentions the T dimension without providing any illustrative examples of path changes in this time domain direction, which made it challenging to comprehend. It would have been easier to understand if a few examples of images with different appearances in the T dimension were shown.\n\nAdditionally, it would have been helpful for understanding if the paper had diagrammatically represented the network in Figures 2 and 3. The section regarding the network is written with text such as \"3D CNN\" and \"2D CNN,\" making it difficult to intuitively grasp. Visualizing the network, as done in other papers that use convolution layers, would have aided in conveying the content.\n\nFurthermore, in Section 4.3, two types of transformers are utilized: Light-weight and Heavy-weight. It would be beneficial if the differences between these two structures were more explicitly mentioned.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "By utilizing 3D convolution to consider spatial and temporal information simultaneously, the authors have proposed a method for enabling appropriate path finding for multi-agents without collision in situations involving a large number of agents at higher speed. Furthermore, through the Multi-subset structure, they solve multiple subproblems in a \"batch\" format, which has the advantage of quickly verifying better paths using this batch structure.", "weaknesses": "The key point of this paper is the rapid resolution of Guiding LNS using 3D convolution without the need for separate feature design in the network structure. However, the author has only applied 3D convolution without providing further theoretical proof or proposing new methods. Therefore, while it is acknowledged that there is an improvement in performance through the application of deep learning structures, the paper has limitations in terms of its overall value.\n\nAdditionally, the MAPF the author aimed to address only holds significance when applied to real robots. However, the author tested the proposed method in a simplified simulation environment for performance verification. This aspect restricts the paper's value to the theoretical domain. To give this research more meaning, it would have been beneficial to include tests involving the use of robots in real-world environments, such as logistics robots.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wfACgcrAXf", "reviewer": "Reviewer_TyGL", "summary": "The paper addresses Large Neighborhood Search (LNS) for Multi-Agent Pathfinding (MAPF) using deep learning. Starting with a feasible (but suboptimal) solution, LNS can solve MAPF in an anytime manner by iteratively destroying and repairing parts, i.e., the neighborhood, of the incumbent solution to improve the solution quality over time. The neighborhoods are determined by using some heuristics from the literature. Given a set of neighborhood candidates, the paper proposes to use deep learning to select a suitable neighborhood via score prediction. The deep learning approach exploits the spatio-temporal structure of the MAPF problem by encoding the paths and obstacles in separate tensors, which are processed by a series of 3D and 2D convolutional layers as well as an attention mechanism. The approach performs well compared to state-of-the-art approaches in selected problems and displays some generalization capabilities for maps of the same size.", "questions": "- *“we perform parameter sweeps detailed in Appendix A.2 to first identify the strongest possible configuration for the Unguided baseline”* - The original MAPF-LNS paper already reported extensive hyperparameter experiments to determine good hyperparameters. Why was it necessary to tune them again?\n- I wonder why deep learning was only used for neighborhood selection via scoring, while the neighborhood generation is still based on the handcrafted destroy heuristics. Wouldn't it make sense to address the generation via deep learning as well to make the approach more end-to-end [6]?\n\n[6] Y. Wu et al., \"Learning Large Neighborhood Search Policy for Integer Programming\", NeurIPS 2021", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper addresses an interesting application area that is well-known in the AI community.\n\nThe paper is well-written and easy to understand.", "weaknesses": "**Novelty**\n\nThe main contribution of the paper is the application of standard deep learning techniques to 2D grid world MAPF. Since tensor encoding of grid worlds is common practice [1,2,3], I do not consider the approach as particularly novel. The architecture is common practice as well (standard convolutional layers and attention), where the application to a new domain seems to be the main contribution to me.\n\n[1] D. Silver et al., \"Mastering the Game of Go with Deep Neural Networks and Tree Search\", Nature 2016\n\n[2] J. Leibo et al., \"Multi-Agent Reinforcement Learning in Sequential Social Dilemmas\", AAMAS 2017\n\n[3] M. Dennis et al., \"Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design\", NeurIPS 2020\n\n**Soundness**\n\nAs noted in the paper, MAPF-LNS relies on fast operations (like prioritized planning/PP for repairing and linear models for neighborhood scoring) to ensure its success as an anytime algorithm. However, the paper proposes several modifications to the standard/default setting of the MAPF-LNS or MAPF-ML-LNS paper, which actually increase runtime:\n- A relatively large model for score prediction compared to simple linear models\n- Generation of several neighborhoods at each iteration (which requires the invocation of the destroy heuristics several times)\n- Priority-based planning (PBS) for repairing, which is slower than the default PP due to backtracking in the tree search\n\nMAPF-LNS and MAPF-ML-LNS rely on a large number of iterations to achieve a good solution quality. Therefore, I am not sure if the addition of several more expensive operations actually pays off since it should significantly limit the number of possible iterations.\n\nThe generalization depends on the map size. A model trained on $32 \\times 32$ maps cannot be straightforwardly used on, e.g., $24 \\times 64$ maps and is therefore limited.\n\n**Significance**\n\nThe paper evaluates with different hyperparameters than suggested in the original literature [4,5]. Thus, I am\n1. uncertain about the fairness of the evaluation and\n2. skeptical about the effectiveness, since some changes increase runtime that would limit the number of iterations for sufficient search (see above).\n\nI am also not sure if the modifications used in the deep learning variant are also applied to the linear version. If so, the comparison might be unfair since MAPF-ML-LNS uses some mechanisms, e.g., random neighborhood sizes, that are seemingly important for its success. \n\nThe experiments only report relative numbers, which makes it difficult to relate to the performance reported in prior work, e.g., do the baselines still perform similarly? In that case, fairness could be confirmed, at least.\n\nThe evaluation only considers maps with a fixed number of agents; therefore, I have no intuition on how the average/final gap would scale, e.g., with an increasing number of agents.\n\n[4] J. Li et al., \"Anytime Multi-Agent Path Finding via Large Neighborhood Search\", IJCAI 2021\n\n[5] T. Huang et al., \"Anytime Multi-Agent Path Finding via Machine Learning-Guided Large Neighborhood Search\", AAAI 2022\n\n**Evaluation**\n\nTo decide whether I raise my score or not, I first need to check the following:\n- Since MAPF algorithms are generally very implementation-dependent (as stated in the appendix), I need to confirm the validity of the proposed mechanisms by viewing and running the code myself (with a provided trained model).\n- I need to see plots or tables with the absolute performance, i.e., the sum of delays, for different numbers of agents per map. The evaluation can be easily done by running the experiments with the neural LNS on the exact same setting as [5] and comparing it with the performance of MAPF-LNS and MAPF-ML-LNS reported in that paper.\n- I need to see plots or tables with the number of iterations and success rate per iteration for different time budgets. If the approach was valid, we should see a lower iteration count than the state-of-the-art but a higher success rate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KcBNU53zrZ", "reviewer": "Reviewer_pDBe", "summary": "This paper presents a novel approach for leveraging machine learning in multi-agent path planning (MAPF) based on large neighbor search (LNS). Given an initial solution for a MAPF problem instance, LNS selects a subset of agents and optimizes their solution paths, treating the paths of other agents as spatiotemporal obstacles. \n\nTraditionally, subset selection has relied on heuristic rules or linear models with hand-crafted features. However, the method proposed here integrates a deep neural network into the agent subset selection process. This network predicts the performance gain achievable by selecting a particular subset, using a tensor that encapsulates the agents' current paths, potential shortest paths, and the layout of other obstacles. To manage the computational expense of applying this procedure to various subsets, the proposed method initially extracts features from all agents' paths and predicts the final gain from the feature map slices corresponding to the subset, facilitated by the deep network.\n\nThe method's effectiveness has been validated on MAPF problems involving hundreds of agents.", "questions": "While the paper is well-written and the proposed method is clearly explained, there are some uncertainties regarding the evaluation experiments.\n\nSpecifically, how can we demonstrate the effectiveness of the proposed method over the Linear baseline? While the solution quality obtained by the proposed method is better, the Linear baseline can run faster instead. Moreover, I wonder if the proposed method may require much more GPU resources than other methods and could be much slower when performed on CPUs.\n\nFor example, is it possible to reduce the model capacity for the proposed method so that it can run as approximately fast as the Linear baseline, and compare the solution quality under such conditions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Clarity**: The paper is very well-written overall, and it accurately positions the proposed method against various related studies.\n\n**Novelty**: The structure of the network used to estimate performance gain for agent subset selection and the method of constructing input tensors are new and intriguing.\n\n**Quality**: Overall, the work is of high quality. The proposed method appears solid and technically sound. The authors have implemented numerous techniques to reduce computational costs, a critical factor in MAPF where execution time is crucial.\n\n**Significance**: The method's significance has been evaluated across multiple MAPF problems, and it has been tested on scenarios involving hundreds of agents. It is commendable that the proposed method can handle hundreds of agents, though I still have some concerns about experimental results, as shown below.", "weaknesses": "Despite the paper's strengths, it could benefit from a more persuasive quantitative evaluation, which would likely enhance its impact.\n\nIn Table 1, the difference between the Linear baseline and the proposed method appears relatively marginal. While the proposed method outperforms the Linear baseline in terms of average gap and final gap scores, the Linear baseline requires less runtime overhead. Given this trade-off between computation time and solution quality, how can the benefits of the proposed method be demonstrated?\n\nAdditionally, it is unclear what computational resources the proposed method and baseline methods require. The paper suggests that both the proposed method and Linear baseline were tested on a GPU, but it doesn't specify the details of GPU specs required. In practical scenarios, not all environments have access to high-end GPUs, and being able to execute path planning on affordable entry-level GPUs or standard CPUs could be a significant advantage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)