Even Loose Proximity Constraints Make Makespan-optimal Unlabeled Multi-agent Pathfinding Hard
Authors: Takahiro Suzuki, Keisuke Okumura
Organizations: Graduate School of Information Sciences, Tohoku University, Japan · National Institute of Advanced Industrial Science and Technology (AIST), Japan
We study \textsc{r-Connected Unlabeled Multi-agent Pathfinding} (rCUMAPF), a variant of MAPF where interchangeable agents have a proximity range r∈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≤r is largely unknown. To narrow this gap, we show that finding a solution to rCUMAPF with makespan at most 2 is \NP-hard for 2≤r=O(∣V∣1−ε), where 0<ε≤1 is a fixed constant and ∣V∣ is the number of vertices. As a consequence, we show that the labeled analogue of rCUMAPF is also \NP-hard under the same condition.
Figures & tables
Figure 1: Complexity of makespan-optimal r CUMAPF by proximity range relative to D(G) .
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 .
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.