/pypibt

Minimal Python implementation of PIBT for MAPF

Primary LanguagePythonMIT LicenseMIT

pypibt

MIT License CI

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]

background

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.

setup

This repository is easily setup with Poetry. After cloning this repo, run the following to complete the setup.

poetry install

demo

poetry run python app.py -m assets/random-32-32-10.map -i assets/random-32-32-10-random-1.scen -N 200

The result will be saved in output.txt The grid maps and scenarios in assets/ are from MAPF benchmarks.

visualization

You can visualize the planning result with @kei18/mapf-visualizer.

mapf-visualizer ./assets/random-32-32-10.map ./output.txt

jupyter lab

Jupyter Lab is also available. Use the following command:

poetry run jupyter lab

You can see an example in notebooks/demo.ipynb.

Licence

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