The code repository of the paper "Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding" (AIJ-22; the journal version).

Updated

• 2023-10-02: The visualizer for Ubuntu is available here.
• 2023-07-26: A minimal Python implementation is now available.

Description

• There is an old implementation for the conference paper (IJCAI-19); this repo is much faster and cleaner.
• The implementation includes both Multi-Agent Path Finding (MAPF) and Multi-Agent Pickup and Delivery (MAPD).
• It is written in C++(17) with CMake (≥v3.16) build.
• The repository uses Google Test and the original library for 2D pathfinding as git submodules.
• The visualizer uses openFrameworks and works only on macOS (as git submodule).
• The accompanied solvers are HCA* [1], Push and Swap [2], TP [3], and PIBT(+).

platform	status (public)	status (dev)
macos-10.15
ubuntu-latest

Please cite the following paper if you use the code in your published research:

# AIJ-22

@article{okumura2022priority,
  title = {Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding},
  journal = {Artificial Intelligence},
  pages = {103752},
  year = {2022},
  issn = {0004-3702},
  doi = {https://doi.org/10.1016/j.artint.2022.103752},
  author = {Keisuke Okumura and Manao Machida and Xavier Défago and Yasumasa Tamura},
}

# IJCAI-19

@inproceedings{okumura2019priority,
  title={Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding},
  author={Okumura, Keisuke and Machida, Manao and D{\'e}fago, Xavier and Tamura, Yasumasa},
  booktitle={Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, {IJCAI-19}},
  publisher={International Joint Conferences on Artificial Intelligence Organization},
  pages={535--542},
  year={2019},
  month={7},
  doi={10.24963/ijcai.2019/76},
  url={https://doi.org/10.24963/ijcai.2019/76}
}

git clone --recursive https://github.com/Kei18/pibt2.git
cd pibt2
mkdir build && cd build
cmake ..
make

You can also use the docker environment instead of the native one, based on Ubuntu18.04.

docker compose up -d
docker compose exec dev bash

PIBT

./mapf -i ../instances/mapf/sample.txt -s PIBT -o result.txt -v

You can find details and explanations for all parameters with:

./mapf --help

Please see instances/mapf/sample.txt for parameters of instances, e.g., filed, number of agents, time limit, etc.

instance=../instances/mapf/sample.txt
agents=100
map_file=arena.map
solver=PIBT
solved=1
soc=3738
lb_soc=3243
makespan=68
lb_makespan=68
comp_time=11
starts=(32,21),(40,4),(20,22),(26,18), [...]
goals=(10,16),(30,21),(11,42),(44,6), [...]
solution=
0:(32,21),(40,4),(20,22),(26,18), [...]
1:(31,21),(40,5),(20,23),(27,18), [...]
[...]

PIBT

./mapd -i ../instances/mapd/sample.txt -s PIBT -o result.txt -v

You can find details and explanations for all parameters with:

./mapd --help

Please see instances/mapd/sample.txt for parameters of instances.

When you specify pickup and delivery locations (and non-task endpoints), put a special file in map/. An example is map/warehouse.map.pd. The rule is the following:

• [@T]: obstacles
• [psa]: pickup locations
• [dsa] delivery locations
• [ea] endpoints

instance=../instances/mapd/sample.txt
agents=50
map_file=warehouse.map
solver=PIBT
solved=1
service_time=25.33
makespan=535
comp_time=437
preprocessing_comp_time0
starts=(33,17),(32,19), [...]
task=
0:129->113,appear=0,finished=23
4:342->256,appear=4,finished=24
[...]
solution=
0:(33,17)->(24,3):-1,(32,19)->(24,3):-1, [...]
1:(32,17)->(29,2):-1,(31,19)->(29,2):-1, [...]
[...]

It takes around 10 minutes.

bash ./visualizer/scripts/build_macos.sh

Note: The script of openFrameworks seems to contain bugs. Check this issue. I fixed this in my script :D

git submodule update --remote
bash ./third_party/openFrameworks/scripts/osx/download_libs.sh
cd visualizer
make build
cd ..
chmod +x ./visualize.sh

cd build
../visualize.sh result.txt

You can manipulate it via your keyboard. See printed info.

The experimental scripts are written in Python3.7.

Exp	used version	scripts
MAPF		exp_scripts/mapf.py
MAPD		exp_scripts/mapd.py

• Maps in maps/ are from MAPF benchmarks. When you add a new map, please place it in the maps/ directory.
• The font in visualizer/bin/data is from Google Fonts.
• Other baseline solvers are obtained from: CBS, EECBS, and BCP

This software is released under the MIT License, see LICENSE.txt.

Keisuke Okumura is a Ph.D. student at the Tokyo Institute of Technology, interested in controlling multiple moving agents.

1. Silver, D. (2005). Cooperative pathfinding. Proc. AAAI Conf. on Artificial Intelligence and Interactive Digital Entertainment (AIIDE-05)
2. Luna, R., & Bekris, K. E. (2011). Push and swap: Fast cooperative path-finding with completeness guarantees. Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI)
3. Ma, H., Li, J., Kumar, T. K., & Koenig, S. (2017). Lifelong multi-agent path finding for online pickup and delivery tasks. Proc. Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS)