Neural Neighborhood Search for Multi-agent Path Finding
Authors: Zhongxia Yan, Cathy Wu
ICLR 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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. |
| Researcher Affiliation | Academia | Zhongxia Yan, Cathy Wu MIT {zxyan,cathywu}@mit.edu |
| Pseudocode | No | No pseudocode or algorithm blocks are explicitly presented. The methods are described in text and illustrated with diagrams (Figure 1, 2, 3). |
| Open Source Code | No | Full code, models, and instructions can be found on Git Hub upon publication. |
| Open Datasets | Yes | Floor Maps. We demonstrate our methods on floor maps, which define the undirected graph G, from the MAPF benchmark suite Stern et al. (2019). |
| Dataset Splits | Yes | 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 (Si, αj, δPBS(P(Si, αj))) as training data. ... 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. ... During training, we periodically validate our learned model s predictivity on a validation set with held-out seeds. |
| Hardware Specification | Yes | Training takes less than 24 hours on a single NVIDIA V100 GPU. ... Training for the Linear baseline takes around 10 minutes to 1 hour on a single 48-CPU Intel Xeon Platinum 8260 processor. |
| Software Dependencies | No | The paper mentions software like "Adam optimizer Kingma and Ba (2014)", "Scikit-learn Pedregosa et al. (2011)", and "linear support vector machine (SVM) Fan et al. (2008)" but does not provide specific version numbers for these software components. |
| Experiment Setup | Yes | 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-attention blocks with 16 to 128 channels, shared across all subsets, followed by three Transformer multi-head attention blocks with 128 features for each subset. A time cutoff of T = 48 is used for both architectures in empty (32x32) and random (32x32), T = 96 for warehouse (161x63), T = 192 for ost003d (194x194), and T = 216 for den520d (256x257). ... We train all neural models with the Adam optimizer Kingma and Ba (2014), 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 a minibatch of 16J = 1600 subsets per step. |