Iterative Refinement for Real-Time Multi-Robot Path Planning (IROS-21)
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.
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/
are from MAPF benchmarks.
When you add a new map, please place it in the maps/
directory.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.