Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01H47zFmeyxcp4dX2PUu4ZPi |
||
|---|---|---|
| .github/workflows | ||
| exp/script | ||
| inc | ||
| src | ||
| .gitattributes | ||
| .gitignore | ||
| CMakeLists.txt | ||
| license.txt | ||
| README.md | ||
| TODO.md | ||
MAPF-LNS2 + LaCAM (research fork)
A Multi-Agent Path Finding (MAPF) solver based on Large Neighborhood Search, extended with several experimental additions:
- LaCAM as the initial solver for the cost-improvement phase
(
--initAlgo Lacam). - A LaCAM "time-window" perturbation that periodically jumps out of local
minima during improvement (
--timeWindow 1). - 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 att*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_optionsis 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
Boostfind is restricted toprogram_options(Boost ≥ 1.69 madesystemheader-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, bumpCMAKE_CXX_STANDARDinCMakeLists.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 isiteration_stats.size() <= maxIterations, and the size is already 1 after the initial solution. With the default0(1 <= 0is 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 theVARIANTSdict (name → extra CLI flags). EditVARIANTSto change which solver versions are compared.genCMD.py— expands the grid into onelnscommand 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 toerros.txt. Optional Discord notifications viaconfig.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/timeaverage over the co-solvable instances (those every variant finished) so the curves — starts included — are comparable. Under--segmentMakespan, the trace also carries per-windowSegWinrows: 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 costis 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.