cs.MANov 16, 2026

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

Abstract

We study \textsc{rr-Connected Unlabeled Multi-agent Pathfinding} (rrCUMAPF), a variant of MAPF where interchangeable agents have a proximity range r∈Nr\in \mathbb{N}, and agents must form a single group in a given graph GG 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=1r=1 and polynomial-time solvability when rr is sufficiently large; the complexity for the intermediate case 2≤r2\le r is largely unknown. To narrow this gap, we show that finding a solution to rrCUMAPF with makespan at most 22 is \NP-hard for 2≤r=O(∣V∣1−ε)2\le r= O(|V|^{1-\varepsilon}), where 0<ε≤10<\varepsilon\le 1 is a fixed constant and ∣V∣|V| is the number of vertices. As a consequence, we show that the labeled analogue of rrCUMAPF is also \NP-hard under the same condition.

Figures & tables

Explore similar work

CardsList
  1. Distance-Constrained Unlabeled Multi-Agent Pathfinding

    May 12, 2026Takahiro Suzuki, Yuma Tamura, Keisuke OkumuraConstrained Motion PlanningMulti-Agent Coordination

  2. Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures

    Dec 11, 2024Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +2Multi-Agent Path Finding