Anytime Multi-Agent Path Finding via Large Neighborhood Search
MAPF-LNS is an effifent anytime algorithm for solving Multi-Agent Path Finding (MAPF). More details can be found in our paper at IJCAI 2021 [1].
Note: The code used in the IJCAI paper had a typo for the agent-based neighborhood selection method. After fixing this typo (commit 3e03f6e), the method performs better than what was reported in the paper.
A stronger version MAPF-LNS2 can be found here: https://github.com/Jiaoyang-Li/MAPF-LNS2
The code requires the external libraries BOOST (https://www.boost.org/) and Eigen (https://eigen.tuxfamily.org/). An easy way to install the required libraries on Ubuntu:
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
After you installed both libraries and downloaded the source code, go into the directory of the source code and compile it with CMake:
cmake -DCMAKE_BUILD_TYPE=RELEASE .
make
You also need to download the MAPF instances from the MAPF benchmark (https://movingai.com/benchmarks/mapf/index.html). In particular, the format of the scen files is explained here: https://movingai.com/benchmarks/formats.html. For a given number of agents k, the first k rows of the scen file are used to generate the k pairs of start and target locations.
Then, you are able to run the code:
./lns -m random-32-32-20.map -a random-32-32-20-random-1.scen -o test.csv -k 50 -t 60
- m: the map file from the MAPF benchmark
- a: the scenario file from the MAPF benchmark
- o: the output file
- k: the number of agents
- t: the runtime limit
You can find more details and explanations for all parameters with:
./lns --help
The software was developed by Jiaoyang Li and Zhe Chen.
The rule-based MAPF solvers (i.e., PPS, PIBT, and winPIBT) inside the software were borrowed from https://github.com/Kei18/pibt/tree/v1.3
MAPF-LNS is released under USC – Research License. See license.txt for further details.
[1] Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J. Stuckey, Sven Koenig. Anytime Multi-Agent Path Finding via Large Neighborhood Search. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 4127-4135, 2021.