A simulator and visualizer of Multi-Agent Path Finding (MAPF), used in a paper "Iterative Refinement for Real-Time Multi-Robot Path Planning" (to appear at IROS-21). 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.

The implementations include: HCA* and WHCA* [1], PIBT [2], CBS [3], ICBS [4], ECBS [5], Revisit Prioritized Planning [6], Push and Swap [7], winPIBT [8], PIBT+, and IR (Iterative Refinement).

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

You can see the performance of each solver from auto_record repo. The records were created by Github Actions.

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

@inproceedings{okumura2021iterative,
  author={Okumura, Keisuke and Tamura, Yasumasa and Défago, Xavier},
  booktitle={2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
  title={Iterative Refinement for Real-Time Multi-Robot Path Planning},
  year={2021},
  pages={9690-9697},
  doi={10.1109/IROS51168.2021.9636071}
}

100 agents in arena, planned by PIBT in 67ms 5ms.

1000 agents in brc202d, planned by PIBT in 84sec 1348ms. The gif shows a part of an MAPF plan.

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

cmake -DCPU=M1 ..

PIBT

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

IR (the result will be saved in result.txt)

./app -i ../instances/random-32-32-20_70agents_1.txt -s IR_HYBRID -n 300 -t 100 -v

You can find details and explanations for all parameters with:

./app --help

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

This is an example output of ../instances/sample.txt. Note that (x, y) denotes location. (0, 0) is the left-top point. (x, 0) is the location at x-th column and 1st row.

instance= ../instances/sample.txt
agents=100
map_file=arena.map
solver=PIBT
solved=1
soc=3403
makespan=68
comp_time=58
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), [...]
[...]

A new visualizer Kei18@mapf-visualizer is available. I recommend using the new one instead of this repo.

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

cd build
../visualize.sh result.txt

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

Generated by Github Actions. See also auto_record repo.

Scripts for the experiments are in exp_scripts/. Several solvers are coded in different names. See the following.

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

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. Okumura, K., Machida, M., Défago, X., & Tamura, Y. (2019). Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding. Proc. Intel. Joint Conf. on Artificial Intelligence (IJCAI)
3. Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015). Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence
4. Boyarski, E., Felner, A., Stern, R., Sharon, G., Tolpin, D., Betzalel, O., & Shimony, E. (2015). ICBS: improved conflict-based search algorithm for multi-agent pathfinding. Proc. Intel. Joint Conf. on Artificial Intelligence (IJCAI)
5. Barer, M., Sharon, G., Stern, R., & Felner, A. (2014). Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem. Annual Symposium on Combinatorial Search (SoCS)
6. Čáp, M., Novák, P., Kleiner, A., & Selecký, M. (2015). Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Trans. on automation science and engineering
7. Luna, R., & Bekris, K. E. (2011). Push and swap: Fast cooperative path-finding with completeness guarantees. Proc. Intel. Joint Conf. on Artificial Intelligence (IJCAI)
8. Okumura, K., Tamura, Y. & Défago, X. (2020). winPIBT: Extended Prioritized Algorithm for Iterative Multi-agent Path Finding. IJCAI Workshop on Multi-Agent Path Finidng (WoMAPF)