jiaoyang-li / mapf-lns

Anytime Multi-Agent Path Finding via Large-Neighborhood Search

MAPF-LNS

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

Credits

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.

References

[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.

mapf-lns's Issues

Code questions

Firstly, thank you very much for your code, which is very helpful for me to learn MAPF.

But I'm not sure whether this line of code should be a=n, to select an agent in neighbors_set randomly. Otherwise, this is just a random selection [0, neighbors_set.size ()] agent, maybe randomly to other agents with no clear relationship with the max_delay agent.

Thanks a lot!