This is a code repository of the paper "Engineering LaCAM*: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding" (AAMAS-24).
LaCAM(*) is a search-based algorithm for MAPF that can address large instances, e.g., with more than 1k agents. If you are interested in academic background, check out this talk and slides. There is a toy Python implementation as well.
This is the third generation of LaCAM: [lacam; AAAI-23] [lacam2; IJCAI-23]. The evolution is depicted below. My prior studies such as [pibt2; AIJ-22] and [mapf-IR; IROS-21] (concurrent with LNS) also play important roles.
lacam2 (left) vs. lacam3 (right, this repo) ๐๐ช
random-32-32-20.map, 409 agents, 30sec timeout, on Mac Book Pro (M2 Max)
All you need is CMake (โฅv3.16). The code is written in C++(17).
First, clone this repo with submodules.
git clone --recursive https://github.com/Kei18/lacam3.git && cd lacam3
Then, build the project.
cmake -B build && make -C build
build/main -i assets/random-32-32-10-random-1.scen -m assets/random-32-32-10.map -N 300 -v 3
The result will be saved in build/result.txt
.
You can find details of all parameters with:
build/main --help
In fact, there are many hyperparameters (though I dislike). The default setting is usually an okay level to my knowledge.
This repository is compatible with kei18@mapf-visualizer.
The experimental script is written in Julia โฅ1.7. Setup may require around 10 minutes.
sh scripts/setup.sh
Edit the config file as you like.
Examples are in scripts/config
.
The evaluation starts by following commands.
julia --project=scripts/ --threads=auto
> include("scripts/eval.jl"); main("scripts/config/mapf-bench.yaml")
The results will be saved in ../data/
.
examples used in the paper
include("scripts/eval.jl"); target="scripts/config/exp_scatter"; foreach(x -> main("$(target)/common.yaml", x), filter(x -> !contains(x, "common"), glob("$(target)/*.yaml")))
include("scripts/eval.jl"); target="scripts/config/exp_mccg"; foreach(x -> main("$(target)/common.yaml", x), filter(x -> !contains(x, "common"), glob("$(target)/*.yaml")))
This software is released under the MIT License, see LICENSE.txt.
If possible, please consider contacting the author for commercial use. This is not a restriction, I just want to know about the use as an academic researcher.
pre-commit install
ctest --test-dir ./build
- The grid maps and scenarios files are (mostly) from MAPF benchmarks, with some original ones.
They are placed in
./scripts/map
and./scripts/scen
. - lacam4? I do not have such a plan currently...