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:
- When $r=1$ (agents must be adjacent), the problem is NP-hard.
- 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.
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.
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:
- Closing the complexity gap for $r = \omega(D(G)/\log D(G))$.
- Developing approximation algorithms for the NP-hard regimes.
- Investigating if subexponential-time algorithms exist for specific values of $\epsilon$.
Summary updated