PaperlayerView exact revision on arXiv

Source-linked AI summary

Divide and Collapse: MAPF-Collapse via Exact Decomposition into Independent Sub-Instances

Oren Salzman

arXiv:2609.39559v1cs.AIcs.RO

TL;DR

MAPF-COLLAPSE removes avoidable moves from feasible MAPF plans while preserving feasibility, but solving it jointly is NP-hard. Divide-and-Collapse identifies which agents need coordination, solves isolated agents separately, and uses a regime-aware joint planner; over tested benchmarks, it achieves a 10.5× median per-instance speedup over Judgelight.

  • Problem

    MAPF-COLLAPSE asks how to remove avoidable moves from a feasible joint MAPF plan without violating feasibility, a task made relevant by redundant moves in modern solver plans.

    Source: §1 · p. 1

  • Method

    Divide-and-Collapse partitions agents by possible interactions, solves isolated agents optimally in linear time, and dispatches coupled components to a joint solver.

    Source: §1 · p. 1

  • Results

    10.5× median per-instance speedup over Judgelight; the hybrid matches mean saving (0.360 vs. 0.359), ties on 2,697 instances, improves on 599, and loses on none.

    Source: §8.5 · p. 12

  • Takeaways & Limitations

    A regime-aware planner uses C-CBS for small-to-medium components and Judgelight for the largest cores, while the framework remains exact on components C-CBS solves.

    Source: §1 · p. 2

    The formulation assumes all input plan rows share a common makespan.

    Source: §3 · p. 3

Abstract

from arXiv · show

In this work we study the problem of MAPFC, a post-optimization step for Multi-Agent Path Finding (MAPF) plans where we are given a feasible plan produced by a modern MAPF solver and are tasked with removing avoidable moves while preserving feasibility. This NP-hard problem naturally arises when using learning-based state-of-the-art (SOTA) solvers which construct plans that contain redundant moves that can be removed. Recently, Tang et al. presented Judgelight, which uses Integer Linear Programming (ILP) to solve MAPFC. Importantly, the ILP is constructed over all agents jointly, so its cost is governed by the full instance rather than by the small coupled residue that actually requires joint reasoning. Our key insight, motivating this work, is that MAPFC instances naturally decompose into independent sub-problems, most of which involve a single agent and can be solved without any inter-agent reasoning. To this end, we first identify which agents need to coordinate their motion and partition the instance into sub-problems accordingly. For the cases where no coordination is required, we introduce an extremely lightweight solver that is $\approx\!1{,}900\times$ faster than Judgelight. For cases where coordination is required, Judgelight can be used but we introduce an alternative CBS-like solver which is more efficient on easier problems. The resulting framework is exact, uses no commercial ILP solver, and matches Judgelight's quality while running substantially faster on the coordination-light majority of instances; on the coordination-heavy instances we propose a regime-aware hybrid planner that falls back to Judgelight. Over all benchmarks tested, this planner achieves a median $10.5\times$ per-instance speedup over Judgelight.

1 Introduction

MAPF-COLLAPSE removes avoidable moves from feasible plans while preserving feasibility, but its joint optimization is NP-hard. Divide-and-Collapse isolates agents that need no coordination and applies a joint solver only to coupled groups.

1 Introduction

  • MAPF solvers produce feasible plans with moves that can be replaced by waits without violating feasibility, wasting energy without throughput benefit.MAPF-COLLAPSE formalizes removing such moves by collapsing closed subwalks into waits at their endpoint.Source: §1 · p. 1
  • Divide-and-Collapse partitions agents by whether they could occupy the same position at the same time under any sequence of collapses.Isolated agents are solved optimally in linear time; only the residue requiring coordination needs a joint solver.Source: §1 · p. 1
  • Collapse-CBS uses a CBS-like joint solver for coupled agents, exploiting that MAPF-COLLAPSE requires reasoning about vertex collisions rather than edge collisions.Judgelight is another available joint solver.Source: §1 · p. 1
  • 10.5× median per-instance speedup over Judgelight; the regime-aware planner matches its quality and is near-instant on coordination-light instances.It uses C-CBS on small-to-medium components and falls back to Judgelight on the largest cores.Source: §1 · p. 2

2 Related Work

Related work covers fast MAPF planning, post-processing plans, and heuristic search methods that reason about agent interactions. This work differs from prior decomposition methods by computing an exact interaction split up front for MAPF-COLLAPSE.

2.1 Learning-Based and Lifelong MAPF

  • Learning-based policies scale to large fleets and horizons and produce feasible schedules quickly, but their plans can contain redundant oscillations and cost gaps relative to search-based baselines.In lifelong settings, per-plan waste compounds across replanning.Source: §2.1 · p. 2

2.2 Post-Optimization of MAPF Schedules

  • MAPF-COLLAPSE shortens the movement layer while preserving the timeline, unlike execution-layer methods that re-time plans for feasibility, robustness, or slack.Other post-processing methods destroy and repair trajectories or add waits to address execution-time failures.Source: §2.2 · p. 2

2.3 Heuristic Search for MAPF

  • CBS resolves vertex conflicts by branching on per-agent constraints, while prior decomposition methods typically discover coupling lazily during search.These approaches include independence detection, M*, and meta-agent CBS.Source: §2.3 · p. 2

2 Related Work

  • Unlike those methods, this work reasons about interactions up front and uses MAPF-COLLAPSE reach sets to make the split exact.The related-work discussion places this approach at the intersection of learning-based and lifelong MAPF, schedule post-optimization, and heuristic search.Source: §2 · p. 2, §2.3 · p. 3

3 Preliminaries and Problem Formulation

The paper defines plans as vertex sequences with waits or edge moves, and joint plans as collision-free combinations of agent plans. MAPF-COLLAPSE seeks the lowest-cost feasible plan obtainable by collapsing closed subwalks of a given joint plan.

3 Preliminaries and Problem Formulation

  • A plan’s cost is its number of moves, and a collapse replaces a closed subwalk with waits at its repeated endpoint without increasing cost.The operation preserves plan length; the example reduces a single-agent plan’s cost from 4 to 2.Source: §3 · p. 3
  • Joint plans extend each agent’s position by endpoint waits and are feasible only when no pair has a vertex or edge collision over the joint horizon.A vertex collision is a shared position at the same time; an edge collision is a simultaneous swap.Source: §3 · p. 3
  • MAPF-COLLAPSE minimizes total moves over collision-free joint plans derived from the input by finite sequences of collapses.The input rows are assumed to share a common makespan, so agents wait at their goals until the last agent arrives.Source: §3 · p. 3
  • The example’s single-agent optima are not necessarily jointly feasible: agent 1’s wait at b overlaps agent 2’s visit there at t = 2.That conflict is the coupling that distinguishes the joint problem from solving each agent independently.Source: §3 · p. 3

4 Algorithmic Background: Judgelight

Judgelight formulates MAPF-COLLAPSE as an ILP over candidate collapses, maximizing their move savings subject to feasibility and dependency constraints. Preprocessing reduces candidates, but the model can still grow quartically with plan length.

4 Algorithmic Background: Judgelight

  • Judgelight assigns a binary variable to each candidate collapse and maximizes saved moves subject to per-agent exclusion, vertex-collision exclusion, and dependency constraints.Dependency constraints couple agents when one selected collapse keeps an agent at a cell another agent originally occupies.Source: §4 · p. 3
  • Safe-oscillation removal greedily eliminates independently undoable oscillations, while maximal-loop reduction losslessly prunes redundant collapse candidates.The greedy reduction can preclude a larger joint saving.Source: §4 · p. 3
  • An alternating segment of length n can still yield O(n^2) variables and O(n^4) dependency constraints, making ILP construction worst-case quartic in plan length.This remains true after the maximal-loop reduction.Source: §4 · p. 3

5 Decomposing MAPF-COLLAPSE by Interaction Components

The paper uses reach sets to identify which agents could conflict under any collapse, then solves each interaction-graph component independently. This decomposition is exact: singleton agents use a per-agent solver, while non-trivial components go to a joint solver.

5.1 Reach Sets and the Interaction Graph

  • The interaction graph connects agents whose reach sets intersect, and its connected components define the independent sub-instances.Singletons go to 1-MAPFC; non-trivial components are passed to a joint solver.Source: §5 · pp. 3–4, §5.1 · p. 4

5 Decomposing MAPF-COLLAPSE by Interaction Components

  • Collapses cannot introduce edge collisions, so the framework needs to enforce only vertex-collision avoidance.Collapse operations only turn moves into waits, leaving each derived plan’s move-transition set within that of its input plan.Source: §5 · p. 4

5.1 Reach Sets and the Interaction Graph

  • A reach set contains exactly the vertex-time cells an agent can occupy under some plan derived from its input plan by collapses.It combines the original trajectory cells with anchor cells; an anchor is a vertex visited more than once.Source: §5.1 · p. 4

5.2 Exact Decomposition and the Pipeline

  • Combining optimal plans for interaction-graph components yields a globally optimal plan because collisions can occur only within a component.The proof establishes that cross-component pairs are collision-free under every choice of plans and that cost decomposes additively.Source: §5.2 · p. 5
  • The pipeline computes reach sets, groups agents by shared cells, solves components independently, and stitches their plans together.The singleton-exact part runs before the joint-solver call; the input joint plan supplies a global upper bound, while the sum of single-agent optima supplies a lower bound.Source: §5.2 · pp. 5–6

6 Per-Agent Solver for Singleton Components

The 1-MAPFC primitive finds an optimal collapse-derived plan by reducing the problem to a shortest path in a Collapse DAG. A structured sweep avoids constructing the potentially quadratic set of collapse arcs, giving linear time and space.

6 Per-Agent Solver for Singleton Components

  • The Collapse DAG represents trace steps as costed arcs and collapse operations as zero-cost arcs, with paths corresponding to collapse-derived plans.A path’s cost equals the resulting plan’s cost.Source: §6 · p. 6
  • The sweep avoids materializing the potentially quadratic collapse-arc set by tracking each vertex’s cheapest earlier occurrence.At each node it compares the trace-arc cost with the best collapse-arc candidate retrieved from a per-vertex hash.Source: §6 · pp. 6–7
  • 1-MAPFC computes a minimum-cost plan obtainable by collapses in O(|π|) time.Its sweep computes a minimum-cost path in the Collapse DAG using O(|π|) time and space.Source: §6 · pp. 6–7

7 A Joint Solver for Non-Trivial Components

The section develops an exact joint solver for non-trivial components, built on a constrained single-agent planner and a CBS-style search. Its low-level planner computes optimal plans under reach constraints, while C-CBS resolves conflicts and supports CBS-derived efficiency optimizations.

7 A Joint Solver for Non-Trivial Components

  • The framework applies a joint solver only to non-trivial components, using C-CBS or Judgelight per sub-instance.C-CBS is the section’s exact CBS-style alternative, tailored to those components and built on a constrained single-agent primitive.Source: §7 · p. 7

7.1 The Constrained Single-Agent DAG

  • The constrained Collapse DAG retains paths corresponding exactly to plans satisfying an agent’s negative reach constraints, with equal cost.The constrained sweep finds a minimum-cost path or reports infeasibility in O(ki + |Ci|) time and space.Source: §7.1 · pp. 7–8

7.2 Conflict-Based Joint Solver: C-CBS

  • C-CBS terminates with a feasible, optimal joint plan on every MAPF-COLLAPSE instance.It searches constraint sets in increasing lower-bound order, branching on conflicts; the lower bound sums each agent’s constrained optimum.Source: §7.2 · pp. 8–9

7.3 CBS-Style Optimizations

  • Cardinal-conflict prioritization, disjoint splitting, and conflict bypass adapt CBS optimizations to improve C-CBS efficiency.Conflict bypass returns a child immediately when its joint plan is conflict-free and matches the parent’s lower bound.Source: §7.3 · p. 9

8 Experimental Evaluation

The evaluation tests Divide-and-Collapse on the POGEMA suite, examining its singleton solver, the interaction-graph structure, component solvers, and full-framework performance. It finds that most components are singletons or small, while a regime-aware hybrid matches Judgelight’s mean saving and solves all instances at a median 10.5× per-instance speedup.

8.1 Setup

  • The benchmark covers 3,296 POGEMA-derived scenarios across five families, and reports saving ratio, wall-clock time, singleton fraction, and success rate under a 30-second instance limit.Each instance/configuration pair is run five times; reported runtime is the median over runs.Source: §8.1 · p. 10

8.2 Q1: The Per-Agent Primitive Is Near-Instant

  • The 1-MAPFC singleton primitive has a 10 µs median solve time, with no solve exceeding 150 µs across approximately 1.5 million schedule prefixes.The evaluation runs schedules with lengths from 8 to 128 moves.Source: §8.2 · p. 10

8.4 Q3: C-CBS Dominates the Small-to-Medium Residue

  • Under a 5-second per-component budget, C-CBS solves 99.7% of components with at most 50 agents, versus all for Judgelight; above 50, C-CBS solves 38.2%.Among components larger than 50 agents where both succeed, C-CBS is cheaper on 325 of 370, by up to 7.6%.Source: §8.4 · p. 11, Table 2 · p. 11

8.3 Q2: The Interaction Graph Is Mostly Singletons and Small Components

  • 88% of components are singletons; the 8,291 non-trivial components have a median size of three agents, but components over 50 agents contain roughly half of all agents.The large-component agent share is 65% in 03-warehouse and 55% in 04-movingai.Source: §8.3 · p. 11, Figure 6 · p. 11

8.5 Q4: The Hybrid Matches Judgelight at a Fraction of the Runtime

  • The hybrid routes components over 40 agents to Judgelight and tries C-CBS for smaller ones before falling back after 1.5 seconds; unlike C-CBS alone, it reaches 100% success.C-CBS alone plateaus at 85.4%, with unresolved instances containing components whose search trees grow prohibitively large.Source: §8.5 · p. 12
  • 10.5× median per-instance speedup over Judgelight; the hybrid solves all 3,296 instances and matches its mean saving (0.360 vs. 0.359).It ties on 2,697 instances, improves on 599, and loses on none.Source: §8.5 · p. 12, Table 3 · p. 12

9 Discussion and Future Work

The discussion frames Divide-and-Collapse as exact decomposition into linear-time singleton solves and a joint residue, while noting that C-CBS struggles on large components. It outlines MAPF-optimization adaptations and online or lifelong variants as future directions.

9 Discussion and Future Work

  • C-CBS is exact on the joint residue, but its search tree grows prohibitively on large components.The authors identify adapting more MAPF machinery and reusing information across replanning episodes as future directions.Source: §9 · p. 12
  • Adapting interval constraints and mutex propagation is non-trivial because both interact with the constrained Collapse DAG in non-standard ways.Interval constraints could sparsify conflicts on shared cells; mutex structure depends on collapse availability, itself a search variable.Source: §9 · pp. 12–13
  • In lifelong and online settings, repeated replanning could compound MAPF-COLLAPSE’s value, with information reuse a key question for hard instances.The paper studies MAPF-COLLAPSE as a one-shot offline post-processing step and raises reuse of prior search information as a future direction.Source: §9 · p. 13

A MAPF-Based Optimizations for C-CBS

  • The appendix adapts cardinal-conflict prioritization, disjoint splitting, and conflict bypass from CBS to Collapse-derived plans, then measures each in an ablation.These optimizations are described as supporting C-CBS; their behavior is evaluated in App. B.1.Source: A MAPF-Based Optimizations for C-CBS · p. 14

A.1 Cardinal-Conflict Prioritization

C-CBS’s conflict-selection and branching optimizations aim to improve search while preserving optimality. The appendix also describes disjoint splitting and a restricted conflict-bypass rule tailored to Collapse-derived plans.

A.1 Cardinal-Conflict Prioritization

  • Cardinal-first selection prioritizes conflicts that increase both children’s lower bounds, avoiding non-progressing branches when possible.A forbidden cell can split a vertex’s available window and destroy collapse arcs, making such conflicts common in MAPF-COLLAPSE.Source: Definitions and structural observation · p. 14, §A.1 · p. 14
  • SelectConflict scans conflicts in time order, choosing the first cardinal conflict, then falling back to semi-cardinal or non-cardinal conflicts.The rule preserves C-CBS’s soundness and completeness guarantees; best-first expansion still returns an optimum.Source: Algorithm and analysis · pp. 14–15

A.2 Disjoint Splitting

  • Disjoint splitting branches on one agent’s negative or positive occupancy at a conflict cell and propagates matching negative constraints to other colliding agents.The positive constraint is represented through negative constraints over other vertices the agent could reach at that time.Source: §A.2 · p. 15
  • The disjoint split’s children cover all Collapse-derived plans, and their lower bounds preserve optimality under best-first expansion.The positive child can be solved using the constrained Collapse DAG, with feasibility decided in time O(k_i + |C_i|).Source: §A.2 · p. 15

A.3 Conflict Bypass

  • Conflict bypass returns a collision-free child plan immediately when its cost matches the parent lower bound, which makes that plan optimal.In the experiments, bypass frequently trims per-node reconstruction work rather than reducing tree size.Source: §A.3 · p. 15

B Additional Experiments

The appendix reports supporting experiments on C-CBS optimizations and an end-to-end per-family comparison. Figure 8 presents the optimization ablation’s search effort and success-rate measures.

B Additional Experiments

  • The appendix covers an ablation of C-CBS’s MAPF-based optimizations and a per-family end-to-end breakdown.Both use the platform, baselines, and protocol from Sec. 8.1.Source: B Additional Experiments · p. 15
  • Figure 8 compares median high-level expansions by component size and success rate within a 5-second per-component budget.The figure captions identify the left panel as expansion counts on a log scale and the right panel as success rate.Source: Figure 8 · p. 16

B.1 Ablation of C-CBS’s MAPF-Based Optimizations

The ablation finds cardinal-conflict prioritization to be the decisive ingredient for C-CBS’s component coverage, with disjoint splitting adding coverage and bypass reducing per-node work. The appendix also reports that the regime-aware hybrid leads Judgelight on every benchmark family.

B.1 Ablation of C-CBS’s MAPF-Based Optimizations

  • The ablation ladder varies conflict prioritization, disjoint splitting, and conflict bypass over 7,322 components of size at most 50.Median high-level expansions proxy search effort; success is the fraction solved within the 5-second per-component budget.Source: §B.1 · p. 16
  • 99.7% of components are solved after cardinal-conflict prioritization and disjoint splitting, versus 94.9% for vanilla C-CBS.Cardinal prioritization lifts success to 99.3%; disjoint splitting contributes the remaining coverage, while bypass leaves the search tree essentially unchanged at this scale.Source: §B.1 · p. 16
  • The regime-aware hybrid leads Judgelight on every family, while the regime-agnostic hybrid is 3.2× slower on 04-movingai.Table 4 reports mean saving ratio and median wall-clock over the 3,296-instance suite.Source: Table 4 · p. 16

B.2 Per-Family End-to-End Breakdown

Table 4 shows DnC+C-CBS→JL outperforming Judgelight across all five POGEMA families, with the largest median-runtime gains on singleton-dominated families. Regime-aware routing preserves its advantage on the largest-core families and stabilizes returned costs.

B.2 Per-Family End-to-End Breakdown

  • ≈1,200× on 05-puzzles, 21× on 01-random, and 11× on 02-mazes; DnC+C-CBS→JL also leads by 1.5× on 03-warehouse and 1.1× on 04-movingai.These are median-runtime advantages over Judgelight in the Q4 comparison.Source: §B.2 · p. 16
  • On 04-movingai, regime-aware routing delivers a 1.1× advantage, while the regime-agnostic variant is ≈3.2× slower than Judgelight after C-CBS exhausts its 1.5-second budget on the largest cores.Regime-aware routing sends work to Judgelight rather than spending that budget on the largest cores.Source: §B.2 · p. 16
  • Regime-aware routing leaves no instance whose reported cost flips across timing repeats, versus twenty under regime-agnostic routing; saving agrees within 5 · 10−4 across families and variants.The regime-aware and regime-agnostic variants have essentially unchanged saving across all families.Source: §B.2 · p. 16
Loading 2609.39559v1…