Even Loose Proximity Constraints Make Makespan-optimal Unlabeled Multi-agent Pathfinding Hard

Takahiro Suzuki, Keisuke OkumuraarXiv 2026 · arXiv

TL;DR

This paper proves that finding a makespan-optimal solution for $r$-Connected Unlabeled Multi-Agent Pathfinding ($r$CUMAPF) is NP-hard for any proximity range $2 \le r = O(|V|^{1-\epsilon})$. This result bridges a significant gap in computational complexity theory, showing that even loose connectivity constraints make the otherwise tractable unlabeled pathfinding problem computationally difficult.

What Problem Does This Paper Address?

Multi-Agent Pathfinding (MAPF) is the task of moving a group of agents from their starting positions to targets without collisions. In the unlabeled version, agents are interchangeable—any agent can go to any target. Standard unlabeled MAPF is solvable in polynomial time.

However, real-world applications like robot platooning or autonomous exploration often require agents to maintain a communication network. This leads to $r$-Connected MAPF, where agents must form a connected graph at every time step, with edges existing between any two agents within a proximity range $r$.

Prior research showed that:

  1. When $r=1$ (agents must be adjacent), the problem is NP-hard.
  2. When $r$ is very large (specifically $r \ge D(G)$, the diameter of the graph), the connectivity constraint becomes trivial, and the problem is solvable in polynomial time.

The complexity for the intermediate range ($r \ge 2$) remained a mystery until now. This paper investigates whether "loose" proximity constraints (where agents can be relatively far apart but still need to stay connected) still result in NP-hardness.

Methods

The authors prove NP-hardness by reducing the Boolean Satisfiability Problem (SAT) to a decision version of $r$CUMAPF: "Does a plan exist with a makespan of at most 2?"

They construct a complex graph $G$ consisting of four types of gadgets:

  • Variable Gadgets: Represent the TRUE/FALSE state of variables.
  • Clause Gadgets: Represent the logical clauses that must be satisfied.
  • Connection Gadgets: Ensure the entire group of agents remains connected to a "base" group.
  • Occurrence Gadgets: Link variables to the clauses where they appear.
Figure 2: Illustrations of the construction when r = 2 and ϕ = (x1 ∨x2 ∨x3) ∧(¬x1 ∨¬x2 ∨x4) ∧(¬x2 ∨x3 ∨¬x4). (a): variable gadgets, (b): clause gadgets, (c): the connection gadget, and (d): occurrence gadgets. (e): The entire graph G and two configurations S, T. Filled vertices indicate S, with colors identifying their gadgets, and blue circles indicate T. Solid lines represent single edges, whereas dotted lines represent paths of length r −1.

The reduction is designed so that a valid 2-step plan exists if and only if the original SAT formula is satisfiable. The connectivity constraint ($r$) is baked into the lengths of the paths connecting these gadgets.

Datasets

As a theoretical complexity paper, no empirical datasets were used. The "data" consists of the mathematical structures and graph constructions used in the proof.

Key Insights and Ideas

  • Connectivity Negates Interchangeability: In standard unlabeled MAPF, the fact that agents are interchangeable makes the problem easy (reducible to flow problems). This paper shows that the global constraint of connectivity forces specific agents to occupy specific regions to "bridge" the network, effectively re-introducing the difficulty found in labeled MAPF.
  • Makespan 2 is Sufficient for Hardness: The proof shows that even the simplest non-trivial plans (taking only two time steps) are hard to find. This establishes a "sharp" complexity boundary, as plans of makespan 1 are easily checkable.
  • The Proximity Range Gap: The authors identify a specific threshold for $r$ relative to the number of vertices $|V|$. As long as $r$ grows slower than the total size of the graph (specifically $O(|V|^{1-\epsilon})$), the problem remains hard.
Figure 1: Complexity of makespan-optimal rCUMAPF by proximity range relative to D(G).

Key Results

  • Theorem 1: For any fixed $0 < \epsilon \le 1$ and integer $r \ge 2$ where $r = O(|V|^{1-\epsilon})$, finding a makespan-optimal plan for $r$CUMAPF is NP-hard, even on graphs with a maximum degree of 3.
  • Hardness of Approximation: The authors derive that there is no polynomial-time algorithm to approximate the optimal makespan within a factor of $\rho < 3/2$ unless P = NP.
  • Labeled Hardness: As a corollary, the labeled version of the problem ($r$CMAPF) is also confirmed to be NP-hard under the same conditions.
  • Exponential Time Hypothesis (ETH): The reduction implies that no subexponential-time algorithm exists for this problem unless the ETH is false.

Limitations and Future Work

The paper leaves a small "open" window in the complexity landscape. While they proved hardness for $r$ up to $O(D(G)/\log D(G))$, there is still a gap between that and the known tractable case of $r \ge D(G)$.

Future research directions include:

  1. Closing the complexity gap for $r = \omega(D(G)/\log D(G))$.
  2. Developing approximation algorithms for the NP-hard regimes.
  3. Investigating if subexponential-time algorithms exist for specific values of $\epsilon$.
Figure 3: The plan ⟨S, Q1, T⟩, where ϕ = (x1 ∨x2 ∨x3) ∧(¬x1 ∨¬x2 ∨x4) ∧(¬x2 ∨x3 ∨¬x4), and x = (TRUE, FALSE, FALSE, TRUE). Fill colors identify the agents’ gadgets, and blue circles indicate T. Solid lines represent single edges, whereas dotted lines represent paths of length r −1. The green markings certify the r-connectivity of the three configurations.

Summary updated

Abstract

We study $r$-Connected Unlabeled Multi-agent Pathfinding ($r$CUMAPF), a variant of MAPF where interchangeable agents have a proximity range $r\in \mathbb{N}$, and agents must form a single group in a given graph $G$ through limited-range communication at all times. The problem arises in fundamental applications such as self-reconfiguration and platooning, while standard MAPF does not capture proximity constraints. For the problem of finding a makespan-optimal solution, prior work shows NP-hardness for $r=1$ and polynomial-time solvability when $r$ is sufficiently large; the complexity for the intermediate case $2\le r$ is largely unknown. To narrow this gap, we show that finding a solution to $r$CUMAPF with makespan at most $2$ is NP-hard for $2\le r= O(|V|^{1-\varepsilon})$, where $0<\varepsilon\le 1$ is a fixed constant and $|V|$ is the number of vertices. As a consequence, we show that the labeled analogue of $r$CUMAPF is also NP-hard under the same condition.
BibTeX
@misc{suzuki2026even,
  author = {Takahiro Suzuki and Keisuke Okumura},
  title = {{Even Loose Proximity Constraints Make Makespan-optimal Unlabeled Multi-agent Pathfinding Hard}},
  year = {2026},
  eprint = {2611.21277},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21277},
}
Figure