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.
We study a graph pathfinding problem Distance-r Independent Unlabeled Multi-Agent Pathfinding, finding a set of collision-free paths between two sets where agents must stay at pairwise distance at least r+1 at all times. This additional constraint, generalizing collision modeling for classical MAPF, targets aspects of real-world multi-agent coordination. This additional distance constraint makes feasibility (i.e., whether a solution exists) PSPACE-complete, in contrast to standard (unlabeled) MAPF, where it can be decided in polynomial time. We address the challenge via two complementary approaches: (i) reduction-based optimal algorithms with a feasibility-preserving compression procedure, and (ii) a configuration generator-based search. Despite the hardness, empirical results show that our algorithm can handle hundreds of agents in a practical timeframe.
Takahiro Suzuki, Yuma Tamura, Keisuke Okumura
Tohoku University · National Institute of Advanced Industrial Science and Technology (AIST)
Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean as fast as possible, which is evaluated by a measure known as the makespan of the proposed solution. This is the setting studied in the Multiagent Path Finding problem. In this work, we additionally provide the agents with a way to communicate with each other. Due to size constraints, it is reasonable to assume that the range of communication of each agent will be limited. What should be the trajectories of the agents to, additionally, maintain a backbone of communication? In this work, we study the Multiagent Path Finding with Communication Constraint problem under the parameterized complexity framework. Our main contribution is three exact algorithms that are efficient when considering particular structures for the input network. We provide such algorithms for the case when the communication range and the number of agents (the makespan resp.) are provided in the input and the network has a tree topology, or bounded maximum degree (has a tree-like topology, i.e., bounded treewidth resp.). We complement these results by showing that it is highly unlikely to construct efficient algorithms when considering the number of agents as part of the input, even if the makespan is 3 and the communication range is 1.
Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan +2
Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic
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.