Benchmarking Large Neighborhood Search for Multi-Agent Path Finding

Jiaqi Tan*¹ , Yudong Luo*², Jiaoyang Li³ , Hang Ma¹

¹ Simon Fraser University ² University of Waterloo ³ Carnegie Mellon University

This repository provides the official implementation of the paper Benchmarking Large Neighborhood Search for Multi-Agent Path Finding.

Table of Contents

• Introduction
• Installation
• Data preparation
• Methods
• Acknowledgements

Introduction

Multi-Agent Path Finding (MAPF) aims to arrange collision-free goal-reaching paths for a group of agents. Anytime MAPF solvers based on large neighborhood search (LNS) have gained prominence recently due to their flexibility and scalability. Neighborhood selection strategy is crucial to the success of MAPF-LNS and a flurry of methods have been proposed.

We conduct a fair comparison across prominent methods on the same benchmark and hyperparameter search settings and promote new challenges for existing learning based methods and present opportunities for future research when machine learning is integrated with MAPF-LNS.

Installation

Step 1 Clone the repository with all submodules.

# Clone the repo and submodules
git clone --recurse-submodules https://github.com/ChristinaTan0704/mapf-lns-benchmark.git
# For each submodue, checkout to the right branch
git submodule foreach 'git checkout $(git config -f $toplevel/.gitmodules submodule.$name.branch || echo master)'

Step 2 Install BOOST (https://www.boost.org/) and Eigen (https://eigen.tuxfamily.org/).

sudo apt update

• Install the Eigen library (used for linear algebra computing)

sudo apt install libeigen3-dev

• Install the boost library

sudo apt install libboost-all-dev

Step 3 Create conda environment and install Python dependencies.

# Create conda environment and activate
conda create --name mapf python=3.9.1
conda activate mapf
# Install pytorch
pip install torch==1.9.0+cu111 torchvision==0.10.0+cu111 torchaudio==0.9.0 -f https://download.pytorch.org/whl/torch_stable.html
# Install other requirements
pip install -r requirements.txt

Data preparation

Please check data preparation for how to download the data.

Methods

Rule-based

The executable for generating rule-based results can be found in the submodule under exe/lns-rule-based. Please check the instruction of submodule exe/lns-rule-based for how to implement the rule-based results.

Learning-based

• SVM

For instreuctions on how to train and infer SVM-LNS, please follow SVM-LNS implementation.

• Neural

For instreuctions on how to train and infer NNS-LNS, please follow NNS-LNS implementation.

• Bandit

The executable for generating bandit results can be found in the submodule under exe/bandit. For instructions on how to infer bandit, please follow bandit implementation.

Acknowledgements

Thanks to the open-source projects MAPF-LNS, MAPF-LNS2, lacam2, bandit, and the model reference from NNS that we were able to align many details for comparison between different methods, making our project possible.