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 ..
makecmake -DCPU=M1 ..PIBT
./app -i ../instances/sample.txt -s PIBT -o result.txt -vIR (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 -vYou can find details and explanations for all parameters with:
./app --helpPlease 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.shNote: The script of openFrameworks seems to contain bugs. Check this issue. I fixed this in my script :D
cd build
../visualize.sh result.txtYou 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.
| paper | code |
|---|---|
| RPP | RevisitPP |
| PIBT+ | PIBT_COMPLETE |
| IR: random | IR |
| IR: single-agent | IR_SINGLE_AGENTS |
| IR: focusing-at-goals | IR_FOCUS_GOALS |
| IR: local-repair-around-goals | IR_FIX_AT_GOALS |
| IR: using-MDD | IR_MDD |
| IR: using-bottleneck-agent | IR_BOTTLENECK |
| IR: composition | IR_HYBRID |
- Maps in
maps/are from MAPF benchmarks. When you add a new map, please place it in themaps/directory. - The font in
visualizer/bin/datais 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.
- Silver, D. (2005). Cooperative pathfinding. Proc. AAAI Conf. on Artificial Intelligence and Interactive Digital Entertainment (AIIDE-05)
- 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)
- Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015). Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence
- 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)
- 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)
- Čá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
- Luna, R., & Bekris, K. E. (2011). Push and swap: Fast cooperative path-finding with completeness guarantees. Proc. Intel. Joint Conf. on Artificial Intelligence (IJCAI)
- 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)
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent