Goal Staying Makes Sum-of-Costs Anonymous Multi-Agent Path Finding NP-Hard

Hang Ma

cs.MAAug 21, 2026

Goal Staying Makes Sum-of-Costs Anonymous Multi-Agent Path Finding NP-Hard

Authors: Hang Ma

Organizations: Simon Fraser University

Abstract

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.

Figures & tables

Problem	Graph	Objective / Question	Complexity	Reference / Note
Labeled MAPF	general	feasibility	P	pebble-motion [ 9 ] , [ 27 ]
Labeled MAPF	general	makespan	NP-hard	[ 20 ] , $(4/3-\epsilon)$ -inapprox. [ 11 ]
Labeled MAPF	general	SoC, total/max distance	NP-hard	[ 26 ]
Labeled MAPF	directed	feasibility	NP-complete	[ 14 ] , P for strongly connected directed [ 4 ]
Anonymous MAPF	general	makespan, total distance	P	[ 25 ]
Anonymous MAPF (disappear)	general	SoC	P	[ 3 ]

TABLE I: Representative complexity results for graph-based MAPF and its anonymous and colored variants.

Panel of Figure 2 — Fig. 1: A six-vertex AMAPF instance. Gray-filled vertices are starts, double-circled vertices are goals, and $g_{L},g_{R}$ are both starts and goals.

Panel of Figure 3 — Fig. 2: Example of the reduction for $\Phi=(X_{1}\vee\neg X_{2})\wedge(\neg X_{1}\vee X_{3})\wedge(\neg X_{2}\vee\neg X_{3})\wedge(X_{1}\vee X_{2}\vee\neg X_{3})$ . Here $m=4$ , so $K=5$ and $(\tau_{1},\tau_{2},\tau_{3},\tau_{4})=(1,2,3,4)$ . The clause starts $c_{j}$ , of potential $-\tau_{j}$ , are shown below the variable gadgets, whereas all clause goals $d_{j}$ have potential $2$ and are shown above them. A dotted connection labeled $5$ represents an internally disjoint selector path of exactly $K$ unit edges, and a dashed connection labeled $\tau_{j}$ represents an internally private clause path $Q_{j,\ell}$ of exactly $\tau_{j}$ unit edges. All other displayed connections are individual edges. The literal gates $g_{i}^{+}$ and $g_{i}^{-}$ are simultaneously starts and goals, and every path from either gate toward a positive-potential goal passes through the common bottleneck $v_{i}$ .

Explore similar work

Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms
Aug 25, 2026Andrea Di Nezza, Mihir Patel, Fabio Fagnani +1Multi-Agent Path Finding
Department of Mathematical Sciences, Politecnico di Torino, Turin, Italy · Department of Computer Science, University of Oxford, Oxford, United Kingdom
Hardness of Multi-Agent Path Finding on Trees: A Unified Approach
Jun 4, 2026Tzvika GeftMotion Planning Multi-Agent Path Finding
Rutgers University, NJ, USA · NJ, USA
AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding
Aug 8, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianRobust MAPF Conflict-Based Search
Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden.

Aug 25, 2026J/K move · Enter open · S save

Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms

Andrea Di Nezza, Mihir Patel, Fabio Fagnani, Sara Bernardini

Department of Mathematical Sciences, Politecnico di Torino, Turin, Italy · Department of Computer Science, University of Oxford, Oxford, United Kingdom

Multi-Agent Path Finding

Open paper AskPDF arXiv

Automated high-density storage systems (warehouses, robotic parking, plant logistics, etc.) require fleets of agents to move through scarce task-critical resources and then park without obstructing future operations. We introduce Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a MAPF variant in which a subset of tasked agents must each visit one of a set of interchangeable pivots (e.g., workstations) before the entire fleet terminates at anonymous stations, one agent per station. We characterize solvability completely: every instance on a 2-edge-connected graph is solvable, and, on arbitrary connected graphs, a structural effective-distance measure relative to the number of unoccupied vertices gives a necessary and sufficient condition. We prove that minimizing station-makespan or station-flowtime is NP-hard already with a single pivot. We present three algorithms, a complete baseline, a SAT-based optimal solver, and Pivot-Prioritized Planning (PPP), the last solving 74-89% of benchmark instances with makespan and flowtime orders of magnitude below the baseline.

Abstract

Explore similar work

Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms

Hardness of Multi-Agent Path Finding on Trees: A Unified Approach

AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding