No description
Find a file
Andy Li 7c1e382ca6
Some checks failed
test_macos / build (push) Has been cancelled
test_ubuntu / build (push) Has been cancelled
plotCompare: round-4 comparisons (w10/w25 widths, wrand10-150, v2 w50-s4 in overall)
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01H47zFmeyxcp4dX2PUu4ZPi
2026-11-05 07:36:56 +00:00
.github/workflows Create test_macos.yml 2023-01-30 11:48:52 -05:00
exp/script plotCompare: round-4 comparisons (w10/w25 widths, wrand10-150, v2 w50-s4 in overall) 2026-11-05 07:36:56 +00:00
inc segment v2/v3: --segmentWindowMin; exp: round 4 (v2 w10 / w25 / wrand10-150 sweep, v2 w50-s4); plotCompare 2x2 + delta metric 2026-11-04 10:37:22 +00:00
src segment v2/v3: --segmentWindowMin; exp: round 4 (v2 w10 / w25 / wrand10-150 sweep, v2 w50-s4); plotCompare 2x2 + delta metric 2026-11-04 10:37:22 +00:00
.gitattributes Initial commit 2020-09-11 17:02:21 +10:00
.gitignore V3 no-memleak 2026-10-02 12:13:01 +10:00
CMakeLists.txt V3 no-memleak 2026-10-02 12:13:01 +10:00
license.txt Create license.txt 2021-02-04 16:08:38 -08:00
README.md tidy up code 2026-07-16 09:20:54 +10:00
TODO.md make lacam to be lacam2 2026-07-13 12:19:23 +10:00

MAPF-LNS2 + LaCAM (research fork)

A Multi-Agent Path Finding (MAPF) solver based on Large Neighborhood Search, extended with several 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).
  3. A segmented-makespan solver (--segmentMakespan) — a 3-stage shifting-window scheme that, once the sum-of-costs LNS plateaus, runs a makespan-objective LNS on individual time-windows of the solution and stitches them back together.

The whole solution is always optimized for sum-of-costs. Makespan optimization is used only per-segment, inside the segmented solver — it is not exposed as a standalone whole-solution mode. The motivation is that shrinking an early segment's makespan — while many agents are still moving — shifts everyone earlier and so saves a lot of sum-of-costs. 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.

The bundled solver is LaCAM2 (the scalable successor to the original LaCAM); it finds a valid joint plan for ~1000 agents in a fraction of a second on the benchmark maps (e.g. ~0.24 s on den520d k1000), which the original LaCAM could not. It is kept behind a thin adapter (inc/LacamSolver.h / src/LacamSolver.cpp, exposing the plain-vector lacam_solve()) and the whole LaCAM2 source tree lives under inc/lacam/ + src/lacam/ wrapped in its own namespace lacam, so it links cleanly alongside the existing PIBT code and the project's own Instance (all of which otherwise define global Graph / Node / Instance / Time names).

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

3. Segmented makespan (--segmentMakespan)

A 3-stage shifting-window scheme that applies a makespan-objective LNS to time-windows of the solution rather than the whole horizon. It is a fallback: the ordinary sum-of-costs LNS runs first, and the segmented process is triggered once the sum-of-costs has not improved for 20 s. The whole solution is always optimized for sum-of-costs; the makespan objective below is applied only within a window, never to the whole solution.

The per-window makespan objective. Inside an optimized window, the sub-solver minimizes the window's makespan (max path length) with a lexicographic accept test: a repaired neighborhood is kept iff it lowers the window makespan, or ties it and does not worsen the window sum-of-costs. The sum-of-costs tiebreak keeps the search productive — the makespan landscape is flat (most local moves don't touch the max), so a pure-makespan accept would stall immediately.

  • The window makespan is read straight off PathTable::makespan (maintained incrementally on every insert/delete), so the accept test is O(1).
  • In makespan mode the random-walk neighborhood is seeded from the longest-path agent (the one that determines the makespan) instead of the most sum-of-cost-delayed one, so the search works on the actual bottleneck.
  • The sub-solvers use --replanAlgo PP (CBS/EECBS optimize their own sum-of-costs internally, so the makespan criterion cannot be threaded through them).

This variant is governed entirely by its own convergence conditions — it ignores both -t and --maxIterations. The vanilla phase runs until the 20 s cost plateau, and each window solver runs until 6 s of no makespan improvement. Termination is still guaranteed: the sum-of-costs is a bounded-below integer that only ever decreases, so vanilla always plateaus, and each window's makespan likewise bottoms out. (The other modes still respect -t and --maxIterations as usual.)

Each stage then cuts the current makespan M into four consecutive windows, optimizes a subset of them, and stitches everything back:

Stage Cut (fractions of M) Optimized windows Frozen "seam"
1 28 / 28 / 28 / 16 first three last 16%
2 16 / 28 / 28 / 28 last three first 16%
3 28 / 28 / 28 / 16 first three last 16%

For each optimized window, agent i is given a fresh MAPF sub-instance from its position at the window start to its position at the window end (both read from the current solution). That sub-instance is solved by a makespan-LNS sub-solver, warm-started from the window's own slice (so it improves monotonically from a known-good baseline) and run until there is no makespan improvement for 6 s. Windows not in the optimized subset are kept verbatim.

The windows are concatenated with a sync barrier at each boundary: every agent waits at its window goal until that window's optimized makespan, so consecutive windows meet at the exact collision-free snapshot configuration and the stitch stays collision-free. The final window ends at config(M) = the real goals, so the result is always a valid full solution, and each window's makespan is ≤ its original width, so a stage never worsens the makespan.

The 16% seam alternates end → start → end across the three stages, so any window boundary that is frozen in one stage lands inside an optimized window in the next — letting the search heal the seams the barrier cannot cross within a single stage.

"Never raise cost" guard. The makespan can never increase (a stage's makespan is the sum of its window makespans, each ≤ its original width), but the sync barrier can raise the sum-of-costs even when the makespan is flat. To prevent that, each stage is snapshotted and reverted if it raised the sum-of-costs — so segmentation only ever commits cost-non-increasing changes (even a makespan-reducing stage is dropped if it costs SoC). This keeps segmentMakespan no worse than the vanilla result in cost.

--dynamicCap 1 propagates into each window's sub-solver (it early-terminates doomed PP repair iterations). The stage/window layout and the 6 s stall live in LNS::runSegmentedMakespan() / LNS::runMakespanStage() and are the tuning targets (hardwired for now, intended to be auto-adjusted).

Structural note. With fixed window waypoints and a sync barrier, the segmented makespan equals the sum of the window makespans, which is ≥ the global makespan — so it cannot beat a hypothetical whole-solution makespan optimizer on small instances. The segmented scheme is aimed at large instances (where a whole-solution makespan-LNS barely moves the needle) and at exploiting the early-segment → sum-of-costs leverage.


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
--segmentMakespan false 3-stage shifting-window solver: after the sum-of-costs LNS plateaus, run a per-window makespan-LNS and concatenate (requires --replanAlgo PP)
--dynamicCap false early-terminate doomed PP repair iterations; propagates into each window's solver under --segmentMakespan
--neighborSize 8 neighborhood size for local search

--segmentMakespan writes a makespan column into the result / iteration CSVs alongside solution cost.

--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/)

runAll.py drives a batched comparison across maps, agent counts, and instances, end to end (generate → run → merge → plot). The current sweep compares three variants — vanilla, segmentMakespan, and segmentMakespan-dyncap (--segmentMakespan with/without --dynamicCap). Run it from exp/script/:

cd exp/script
python3 runAll.py --procs 8            # full sweep; failures are recorded in erros.txt
python3 runAll.py --rerun-errors --procs 4   # re-run just the failed commands, re-merge + re-plot

Everything a batch produces lands under exp/<DD-Mon>/ (per-run summary CSVs, iter/ anytime traces, figures/, the merged <DD-Mon>.csv, and cmds.txt).

  • config.py — all knobs in one place: ACTIVE_MAPS, agent range, instance count, cutoff, init/replan/destroy algorithms, and the VARIANTS dict (name → extra CLI flags). Edit VARIANTS to change which solver versions are compared.
  • genCMD.py — expands the grid into one lns command per (variant × map × agent count × instance), encoding the metadata in the output filename (variant__map__k…__type-idx__seed…).
  • runCMD.py — bounded process pool; writes any non-zero-exit commands to erros.txt. Optional Discord notifications via config.DISCORD_WEBHOOK.
  • merge.py — parses the metadata back out of each filename and prepends it as columns, producing a single analysis-ready CSV.
  • plotResult.py — renders the figures: --kind iter (cost vs iteration index), --kind time (cost vs runtime — the anytime curve; the right lens for --segmentMakespan, whose segment stage is invisible on the iteration axis), and --kind final (final cost/lower-bound per instance). iter/time average over the co-solvable instances (those every variant finished) so the curves — starts included — are comparable. Under --segmentMakespan, the trace also carries per-window SegWin rows: the true projected sum-of-costs if the windows optimized so far were committed and the rest left as-is, so each segment's makespan gain is reflected in the global cost at its real wall-clock time.

The merged CSV includes solution cost, makespan, initial solution cost, lower bound, and area under curve. Under the makespan variants the makespan column is the metric of interest (and note solution cost can be below the sum-of-costs lower bound only if a run is infeasible — a useful sanity check).

Single-agent search timing. Every run also records how long the per-agent low-level search (findPath) takes, split by stage: {vanilla,segment} search {count,time,avg}. The vanilla columns are the full start→goal searches during the sum-of-costs phase; the segment columns are the shorter window searches summed over the per-window sub-solvers under --segmentMakespan (empty for non-segment variants). avg = time / count. Window searches are typically ~10× faster than full-path ones (they cover only ~28% of the horizon), which is the cost side of the segmentation trade-off.


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.
  • Segmented makespan is a first cut. The window layout (28/28/28/16), the 3-stage count, the alternating-seam offset, the per-window 6 s stall, and the even time budget are all hardwired and intended to be auto-tuned. The fixed snapshot waypoints + sync barrier make the segmented makespan ≥ the global makespan, so it is expected to pay off on large instances / via the early-segment leverage rather than on small ones.
  • Per-segment sub-solvers rebuild heuristics. Each optimized window spins up a fresh sub-LNS, so every agent's single-source heuristic is recomputed for that window's goal configuration — real overhead at high agent counts.

Acknowledgements

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