MAPF-LNS2 + LaCAM (research fork)

A Multi-Agent Path Finding (MAPF) solver based on Large Neighborhood Search, extended with two experimental additions:

1. LaCAM as the initial solver for the cost-improvement phase (--initAlgo Lacam).
2. A LaCAM "time-window" perturbation that periodically jumps out of local minima during improvement (--timeWindow 1).

The goal of the fork is to drive the final sum-of-costs lower than stock LNS2 on dense instances. Everything else (the CBS/ECBS, PIBT/PPS, and prioritized-planning machinery) is inherited from the LNS framework.

---

How the solver runs

A run has two phases:

Phase	File	Purpose
Init	InitLNS.cpp	find a feasible (collision-free) solution — drives the number of colliding pairs to zero
Improve	LNS.cpp	anytime cost reduction on a collision-free solution — destroy a neighborhood, repair it, keep it if cheaper

Both additions in this fork live in the improve phase (LNS.cpp):

1. LaCAM initial solution (--initAlgo Lacam)

Instead of seeding the improvement phase with sequential Prioritized Planning, LaCAM jointly plans a collision-free solution for all agents at once. It is complete and fast, so it tends to produce a starting solution where PP would struggle on dense instances. If LaCAM times out, the solver falls back to the normal InitLNS feasibility search.

LaCAM is kept behind a thin adapter (inc/LacamSolver.h / src/LacamSolver.cpp) and the whole LaCAM source tree lives in its own namespace lacam, so it links cleanly alongside the existing PIBT code (both otherwise define global Graph and Node types).

2. Time-window perturbation (--timeWindow 1)

An iterated-local-search "kick", orthogonal to the destroy strategy:

• When a trigger condition fires (default: cost has not improved for 100 consecutive iterations), the solver chops every agent's path at a random time t*.
• The prefix [0, t*) of each path is frozen; each agent's position at t* becomes a fresh start, and LaCAM jointly replans the whole suffix to the goals.
• The new prefix+suffix solution is always accepted — it is usually worse, but it is a large jump that escapes local minima. Normal LNS steps then re-optimize from there.

Because all agents are replanned from t*, the frozen prefix (timesteps < t*) and the new suffix (timesteps ≥ t*) occupy disjoint time ranges and meet at the collision-free snapshot config(t*), so the concatenation is collision-free without any cross-constraint between prefix and suffix.

The trigger lives in LNS::shouldPerturbTimeWindow() and is the main knob to tune (e.g. a flat ~1% random sample instead of the stall counter).

---

Build

Dependencies:

• CMake ≥ 3.16, a C++14 compiler
• Boost (only program_options is used as a compiled library; the rest is header-only)
• Eigen3 (used by PIBT; no version is pinned)

cmake -B build -DCMAKE_BUILD_TYPE=RELEASE
cmake --build build -j
# produces ./build/lns

Notes:

• The Boost find is restricted to program_options (Boost ≥ 1.69 made system header-only, and newer Boost dropped its separate CMake component).
• Eigen is found with find_package(Eigen3 REQUIRED NO_MODULE) (no version pin), so a 3.x or 5.x install both work. If Eigen 5 requires C++17, bump CMAKE_CXX_STANDARD in CMakeLists.txt.

---

Usage

./build/lns -m <map> -a <scen> -k <#agents> -t <seconds> [options]

Example — stock LNS2 vs. this fork on the same instance:

# baseline: Adaptive destroy, PP init
./build/lns -m instances/random-64-64-20/random-64-64-20.map \
            -a instances/random-64-64-20/random-64-64-20-random-1.scen \
            -k 650 -t 60 --maxIterations 1000000 \
            --initAlgo PP --destoryStrategy Adaptive -o out_baseline

# this fork: LaCAM init + time-window perturbation
./build/lns -m instances/random-64-64-20/random-64-64-20.map \
            -a instances/random-64-64-20/random-64-64-20-random-1.scen \
            -k 650 -t 60 --maxIterations 1000000 \
            --initAlgo Lacam --destoryStrategy Adaptive --timeWindow 1 -o out_fork

Key options

Flag	Default	Meaning
-m, --map	—	map file (.map)
-a, --agents	—	scenario file (.scen)
-k, --agentNum	0	number of agents to load from the scenario
-t, --cutoffTime	7200	wall-clock budget in seconds
-o, --output	—	result CSV base (-LNS.csv is appended)
--seed	0	RNG seed (reproducibility)
--maxIterations	0	set this large (e.g. 1000000) to run the anytime loop until the cutoff — see caveat below
--initAlgo	PP	initial solver: PP, Lacam, EECBS, CBS, PIBT, PPS, winPIBT
--replanAlgo	PP	neighborhood repair: PP, EECBS, CBS
--destoryStrategy	Adaptive	base neighborhood: Adaptive, RandomWalk, Intersection, Random
--timeWindow	false	enable the LaCAM time-window perturbation on top of the destroy strategy
--neighborSize	8	neighborhood size for local search

--timeWindow is independent of --destoryStrategy: the base local search still follows the chosen destroy strategy, and the perturbation is layered on top, so it can be combined with any of them.

Caveat — --maxIterations: the improvement loop guard is iteration_stats.size() <= maxIterations, and the size is already 1 after the initial solution. With the default 0 (1 <= 0 is false) the improvement loop never runs and you only get the initial cost. Always pass a large value for a meaningful cost comparison.

---

Repository layout

inc/, src/              core LNS solver (LNS, InitLNS, single-agent A*, ...)
inc/CBS/, src/CBS/       CBS / ECBS / PBS
inc/PIBT/, src/PIBT/     PIBT / PPS / winPIBT
inc/lacam/, src/lacam/   LaCAM (wrapped in `namespace lacam`)
inc/LacamSolver.*        adapter exposing LaCAM via a plain vector interface
src/driver.cpp           CLI entry point
exp/                     experiment harness (Python)
instances/               MAPF benchmark maps + scenarios (not tracked)

---

Experiment harness (exp/)

Four scripts drive a batched comparison of vanilla (no perturbation) vs. timewindow (perturbation on) across maps, agent counts, and instances. Run them from inside exp/:

cd exp
python3 genCMD.py cmds.txt     # generate the command list
python3 runCMD.py cmds.txt 8   # run with 8 parallel workers
python3 merge.py results.csv   # merge per-run CSVs into one table

• config.py — all knobs in one place: maps (one per category: warehouse / random / room / game), agent range, instance counts, cutoff, init algorithm, and the two variants (vanilla / timewindow, differing only by --timeWindow).
• genCMD.py — expands the grid into one lns command per (variant × map × agent count × instance), encoding the metadata in the output filename.
• runCMD.py — bounded process pool. Optional Discord notifications via the DISCORD_WEBHOOK env var (off by default).
• merge.py — parses the metadata back out of each filename and prepends it as columns, producing a single analysis-ready CSV.

The merged CSV includes solution cost, initial solution cost, and area under curve, which are the metrics for the cost comparison.

---

Known limitations / TODO

• No best-solution tracking. The time-window perturbation is always accepted, so the reported solution cost is the current solution, not the best seen. If a run ends right after a perturbation it can report a spike. Proper iterated local search should keep a best-so-far snapshot and report that.
• Perturbation re-parses the map each call (LaCAM rebuilds its graph from the map file every time it runs). Fine for validation; cache the graph if it becomes a bottleneck.
• The perturbation trigger and the chop-time selection (t*, currently uniform random) are first cuts — both are intended tuning targets.

---

Acknowledgements

Built on the MAPF-LNS framework and the LaCAM multi-agent planner.