A minimal python implementation of Priority Inheritance with Backtracking (PIBT) for Multi-Agent Path Finding (MAPF). If you are just interested in moving hundreds of agents or more in a short period of time, PIBT may work as a powerful tool.
- Okumura, K., Machida, M., Défago, X., & Tamura, Y. Priority inheritance with backtracking for iterative multi-agent path finding. AIJ. 2022. [project-page]
To be honest, as the developer of PIBT, I only developed it to keep multiple agents running smoothly, not to solve MAPF or MAPD. But it turned out to be much more powerful than I expected. A successful example is LaCAM*. It achieves remarkable performance, to say the least. I also noticed that PIBT has been extended and used by other researchers. These experiences were enough to motivate me to create a minimal implementation example to help other studies, including my future research projects.
As you know, many researchers like Python because it is friendly and has a nice ecosystem. In contrast, most MAPF algorithms, such as the original PIBT, are coded in C++ for performance reasons. So here is the Python implementation. I hope the repo is helpful to understand the algorithm; the main part is only a hundred and a few lines. You can also use and extend this repo, for example, applying to new problems, enhancing with machine learning, etc.
This repository is easily setup with Poetry. After cloning this repo, run the following to complete the setup.
poetry installpoetry run python app.py -m assets/random-32-32-10.map -i assets/random-32-32-10-random-1.scen -N 200The result will be saved in output.txt
The grid maps and scenarios in assets/ are from MAPF benchmarks.
You can visualize the planning result with @kei18/mapf-visualizer.
mapf-visualizer ./assets/random-32-32-10.map ./output.txt
Jupyter Lab is also available. Use the following command:
poetry run jupyter labYou can see an example in notebooks/demo.ipynb.
This software is released under the MIT License, see LICENSE.txt.