Source-linked AI summary
Goal Staying Makes Sum-of-Costs Anonymous Multi-Agent Path Finding NP-Hard
Hang Ma
TL;DR
AMAPF is polynomial-time solvable for several objectives when agents disappear at goals, but standard goal-staying SoC has a different complexity. The paper adds goal-settlement constraints to the time-expanded flow model, finds a non-integral LP relaxation, and proves goal-staying SoC minimization NP-hard via a 3-SAT reduction.
Problem
Although disappearing AMAPF admits polynomial-time SoC optimization, it was unknown whether standard goal-staying AMAPF-SoC is polynomial-time solvable.
Method
The paper augments the time-expanded flow formulation with goal-settlement variables and uses permanent goal occupancy in a reduction from 3-SAT.
Results
The natural LP relaxation is non-integral, and minimizing SoC in standard goal-staying AMAPF is NP-hard.
Takeaways & Limitations
The complexity of anonymous SoC optimization is sharply determined by whether completed agents disappear or remain at their goals.
Abstract
from arXiv · showhide
Anonymous Multi-Agent Path Finding (AMAPF) admits polynomial-time network-flow algorithms for several objectives, including makespan, total distance, and sum-of-costs (SoC) when agents disappear upon reaching goals. We show that standard goal-staying AMAPF is fundamentally different. We first formulate SoC minimization by augmenting the standard time-expanded flow model with goal-settlement constraints and show that the resulting linear programming relaxation is non-integral. We then prove that minimizing SoC in goal-staying AMAPF is NP-hard via a reduction from 3-SAT. Together with the polynomial-time result for the disappearing variant, this establishes a sharp complexity boundary determined by whether completed agents remain at their goals.
I. INTRODUCTION
AMAPF is tractable for several objectives under interchangeability, but standard goal-staying SoC has remained unresolved. The paper identifies permanent goal occupancy, formulates it explicitly, and proves that the resulting optimization problem is NP-hard.
- Complexity gap: AMAPF makespan, total distance, and disappearing-agent SoC can be optimized in polynomial time with network-flow methods.SoC counts moves and waits until completion, while disappearing agents leave the time-expanded network at their goals.
- Complexity gap: Standard AMAPF uses goal-staying semantics, where completed agents continue occupying goals and participating in collisions.This differs from disappearing AMAPF, in which agents cease to occupy the graph after reaching goals.
- Key distinction: The paper identifies permanent goal occupancy as the constraint coupling one agent’s completion with all agents’ future motion.A completed agent permanently reserves its goal vertex, unlike a flow unit that simply exits the network.
- Approach: The authors augment the time-expanded flow model with goal-settlement variables, whose natural LP relaxation is non-integral.The settlement constraints explicitly represent permanent occupancy and explain why the usual flow-integrality argument fails.
- Main result: The paper proves that minimizing SoC for standard goal-staying AMAPF is NP-hard.Its construction uses permanent goal occupancy to encode mutually exclusive choices and enforce Boolean consistency.
II. RELATED WORK: COMPLEXITY OF MAPF VARIANTS
Prior work establishes several complexity boundaries for labeled, anonymous, and partially interchangeable MAPF. This paper focuses on a distinct boundary within fully anonymous MAPF: disappearing-agent SoC is polynomial, whereas goal-staying SoC is NP-hard.
- Variants: MAPF variants differ by agent interchangeability, with AMAPF representing one interchangeable team and colored MAPF representing multiple teams.One agent per team corresponds to standard labeled MAPF.
- Known complexity results: AMAPF makespan and total distance are polynomial-time solvable, while labeled MAPF optimization is NP-hard for common objectives.The cited results distinguish feasibility from optimization and labeled from fully interchangeable settings.
- SoC boundary: For SoC, disappearing AMAPF is polynomially solvable by minimum-cost maximum flow, but standard goal-staying AMAPF has exponential worst-case optimal algorithms.The paper closes this gap by proving goal-staying optimal AMAPF-SoC NP-hard.
- Partial interchangeability: With two interchangeable teams, MAPF is already NP-hard for makespan and SoC on general graphs.For makespan, prior work established (4/3 −ϵ) and later (3/2−ϵ) inapproximability under stronger restrictions.
- Restricted graphs: Hardness also persists across restricted graph classes, including planar graphs and 2D grid graphs with holes.The cited results cover several labeled objectives and some two-team settings.
- Position of this work: The paper’s complexity boundary is different from the one-team-versus-two-team boundary: it arises from whether anonymous agents remain at goals.Table I summarizes the representative comparisons relevant to these boundaries.
III. PROBLEM FORMULATION
An AMAPF instance consists of an undirected graph, distinct start vertices, and distinct goal vertices occupied by interchangeable agents. A solution assigns agents bijectively to goals and requires collision-free trajectories that eventually remain at those goals.
- Instance: An AMAPF instance is I = (G, S, D), with an undirected graph and N distinct start and goal vertices.Initially, one agent occupies every vertex in S.
- Motion: Agents follow trajectories that wait or move along graph edges while avoiding vertex collisions and opposite-direction edge traversals.These are the collision constraints for a set of trajectories.
- Solutions: A solution bijectively assigns agents to goals and requires each assigned agent eventually to remain at its goal forever.An agent initially at a goal may leave it before settling at another goal.
- Objective: The objective is to minimize the sum of agents’ completion times, called the sum-of-costs.Completion time is the first time after which an agent stays at its assigned goal permanently.
IV. FLOW FORMULATION AND LOSS OF INTEGRALITY
The paper extends the anonymous time-expanded flow model with variables that encode when goals become permanently occupied. This yields an exact integer formulation for SoC, but adding settlement constraints destroys LP integrality.
- Horizon: A polynomially bounded horizon H can contain an optimal minimum-SoC solution, enabling a finite time-expanded formulation.A polynomial-makespan AMAPF solution provides a polynomial upper bound on SoC and the relevant makespan.
- Flow model: The formulation uses binary flow variables on directed movement and waiting arcs without agent indices because agents are anonymous.The flow represents anonymous motion through the time-expanded network.
- Flow constraints: Standard flow constraints enforce the initial configuration, conservation, vertex capacity, edge-conflict exclusion, and final goal occupancy.Together these constraints describe anonymous collision-free flow from starts to goals.
- Settlement: Goal arrival is insufficient for SoC because an agent may enter a goal, leave it, and settle permanently only later.The model therefore distinguishes first occupation from completion.
- Settlement: Binary goal-settlement variables indicate whether a goal’s final occupant remains there from a given time onward.The variables encode permanent occupancy through the remaining horizon.
- Objective encoding: Each goal’s settlement time is the first time from which its final occupant remains there, and these times form the multiset of agent completion times.Summing settlement times therefore gives SoC.
- Exactness: For a sufficiently long horizon, an optimal integer solution of the formulation corresponds to a minimum-SoC AMAPF solution with the same SoC.The proof extends the horizon solution by waiting forever after H.
- Loss of integrality: Unlike disappearing AMAPF, goal staying reserves a goal vertex after completion, and the natural LP relaxation can fractionally settle goals.This persistent reservation is the source of the lost integrality property.
A. Integrality Gap of the LP Relaxation
The LP relaxation attains SoC 6 on the six-vertex instance, while every integral solution requires SoC 7, yielding an integrality gap of 7/6. The gap arises because fractional flow can partially settle at goals while continuing through the graph.
- Integer optimum: The integer solution has completion times 2, 2, 2, and 1, for total SoC 7.The lower bound follows from TgL + TgR ≥3 and Tc + Th ≥4.
- LP optimum: The LP reaches value 6 by splitting each initial unit of flow symmetrically across waiting and movement choices.At time 1, fractional occupancy is permitted at a and b while gL, c, and gR each carry one unit.
- Integrality gap: 7/6 is the integrality gap: OPTLP = 6 while OPTIP = 7.The instance is the six-vertex tree shown in Figure 1.
- Source of non-integrality: Fractional flow can permanently settle partly at gL and gR while the remainder continues, unlike an integral agent.This split is what creates a combinatorial distinction from ordinary single-commodity flow.
V. NP-HARDNESS OF OPTIMAL AMAPF-SOC
The paper establishes that finding a minimum-SoC solution for goal-staying AMAPF is NP-hard. The proof begins by reducing from 3-SAT formulas with clauses containing at most three literals.
- Hardness result: Computing a minimum-SoC solution for AMAPF is NP-hard.This is the paper’s main hardness theorem for standard goal-staying AMAPF.
A. Potential Lower Bound
A potential function gives a lower bound on every feasible AMAPF solution. Equality is highly restrictive: every pre-completion move must increase the potential by exactly one.
- Potential lower bound: The reduction uses a potential function to characterize solutions attaining a tight SoC lower bound.The bound compares goal potentials with start potentials.
- Equality condition: Equality requires every agent to move before completion along an edge increasing λ by exactly one at every timestep.This condition follows because equality must hold in each individual agent inequality.
B. Reduction
The reduction builds variable and clause gadgets whose potential-increasing paths encode Boolean choices and clause satisfaction. Shared bottlenecks prevent both literal choices for one variable from being used simultaneously, while private clause paths connect occurrences to literal gates.
- Construction size: The construction sets τj = j and K = m + 1, giving distinct clause-path lengths and a polynomial-size instance with 3n + m agents.The example uses K = 5 and τ1, τ2, τ3, τ4 = 1, 2, 3, 4.
- Variable gadget: Each variable gadget has two literal gates, a shared bottleneck vi, and an auxiliary goal hi.Both literal gates are simultaneously starts and goals, and the gadget includes edges through vi to hi.
- Variable gadget: Both literal-gate paths have length K, and the potential increases by one along every edge.The two paths are internally disjoint before converging through the shared bottleneck.
- Variable gadget: A solution attaining the potential lower bound cannot let both literal-gate agents leave, because both must enter the shared bottleneck vi at time 1.This enforces a mutually exclusive choice between the two literal gates.
- Clause gadget: Each clause gadget introduces a clause start cj and goal dj, with a private path of length τj from cj to every literal gate appearing in the clause.The polarity of each occurrence is encoded by the literal gate through which the clause agent enters.
C. SoC Threshold
The construction establishes that the 3-CNF formula Φ is satisfiable exactly when the constructed AMAPF instance admits a solution with SoC B.
- Φ is satisfiable if and only if the constructed AMAPF instance has a solution of SoC B.
D. Correctness
The correctness proof uses permanent literal-gate occupancy and timed selector and clause paths to encode Boolean assignments and show that SoC at most B is equivalent to satisfiability.
- Soundness: A satisfiable formula yields a collision-free AMAPF solution with SoC B.
- SoC accounting: The construction’s total SoC is determined by variable completion times 0, 2, and K and clause completion times τj + 2.
- Assignment encoding: The shared bottleneck prevents both literal-gate agents from leaving, while the selector prevents both from staying, forcing exactly one gate to vacate.
- Assignment encoding: The selector must complete at the vacated gate because the opposite gate remains permanently occupied and alternative agents cannot validly occupy it.
- Clause satisfaction: Each clause agent must reach a gate corresponding to one of its literals, and an occupied false-literal gate makes that literal unavailable.
- Hardness conclusion: The reduction has polynomial size, and any AMAPF solution with SoC at most B yields a satisfying assignment, proving NP-hardness.
VI. DISCUSSION AND CONCLUSION
The paper identifies permanent goal occupancy as the source of goal-staying AMAPF-SoC hardness and contrasts it with the polynomial-time disappearing variant. The reduction also supports extensions using bounded-occurrence or planar SAT variants.
- Permanent goal occupancy adds settlement constraints that destroy integrality in the time-expanded flow formulation.
- Together with polynomial-time disappearing-agent SoC, the result establishes a complexity boundary based on whether completed agents remain at their goals.
- The reduction uses a tight potential bound, a shared bottleneck, and permanently occupied literal goals to communicate binary choices to clause agents.
- Under bounded occurrence, constant time offsets can replace τj and K, potentially yielding constant-length paths and bounded-degree reductions.