A minimal Python implementation of the TSWAP algorithm for unlabeled multi-agent pathfinding (aka. anonymous MAPF; AMAPF).
- Okumura, K. & Défago, X. Solving simultaneous target assignment and path planning efficiently with time-independent execution. AIJ. 2023. [project-page] (best student paper award at ICAPS-22 🏆)
TSWAP is a polynomial time, suboptimal, complete algorithm for solving unlabeled MAPF efficiently. Just as pypibt for PIBT, pylacam for LaCAM, I here provide a distilled implementation. In particular, the implementation is based on Algorithm 1 from the AIJ paper (not optimised one), and the scipy linear-sum optimal target assignment is adopted, although this is a bit slow for cost table preparation). Please note that this remains a toy implementation designed to help you understand the algorithm. I do not think it is a good idea to use this implementation for benchmarking.
This repository is setup with uv. After cloning this repo, run the following to complete the setup.
uv syncuv run python app.py -m assets/empty_48_128.map -i assets/empty_48_128.scen -N 100The 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/empty_48_128.map ./output.txt
Jupyter Lab is also available. Use the following command:
uv run jupyter labYou can see an example in notebooks/demo.ipynb.
This software is released under the MIT License, see LICENSE.txt.