py-lacam

A minimal Python implementation of LaCAM* (lazy constraints addition search) for Multi-Agent Path Finding (MAPF).

Description

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.

• Okumura, K. LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding. AAAI. 2023. [project-page]
• Okumura, K. Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding. IJCAI. 2023. [project-page]
• Okumura, K. Engineering LaCAM*: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding. AAMAS. 2024. [project-page]

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!

News

• 13 Jan. 2024: A simple implementation of LaCAM with PIBT is now available. It is scalable. Check this branch.

Setup

This repository uses uv for fast Python package management. After cloning this repo, run the following to complete the setup.

uv sync --all-extras

Demo

uv 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.

Visualization

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

mapf-visualizer ./assets/tunnel.map ./output.txt

without refienment

When you need just a suboptimal solution, try:

uv run python app.py -m assets/tunnel.map -i assets/tunnel.scen -N 2 --no-flg_star

Jupyter Lab

Jupyter Lab is also available. Use the following command:

uv run jupyter lab

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

Licence

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

Notes

• There is a minimal Python implementation for PIBT as well.