A minimal Python implementation of LaCAM* (lazy constraints addition search) for Multi-Agent Path Finding (MAPF).
LaCAM* is a graph pathfinding algorithm to solve MAPF. With the effective use of other MAPF algorithms, such as PIBT, LaCAM can achieve remarkable scalability (e.g., for 10k agents), while maintaining nice theoretical guarantees.
The original references use PIBT as a submodule, which makes the implementation a bit complicated. Here, I provide a much simpler implementation by replacing PIBT with random action selection. While this is not at all effective from a performance perspective, it can highlight the simple (and beautiful imo) structure of the algorithm and also can help understand the underlying concept.
Feel free to use/extend this repo!
This repository is based on Poetry. After cloning this repo, run the following to complete the setup.
poetry config virtualenvs.in-project true && poetry install
poetry run python app.py -m assets/tunnel.map -i assets/tunnel.scen -N 4 --time_limit_ms 5000 --verbose 2
The result will be saved in output.txt
.
The grid maps and scenarios follow the format of MAPF benchmarks.
You can visualize the planning result with @Kei18/mapf-visualizer.
mapf-visualizer ./assets/tunnel.map ./output.txt
When you need just a suboptimal solution, try:
poetry run python app.py -m assets/tunnel.map -i assets/tunnel.scen -N 2 --no-flg_star
Jupyter Lab is also available. Use the following command:
poetry run jupyter lab
You can see an example in notebooks/demo.ipynb
.
This software is released under the MIT License, see LICENSE.txt.