cs.CCDec 11, 2024

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

Authors: Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, Michal Opler

Organizations: Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic

Abstract

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 33 and the communication range is 11.

Figures & tables

Explore similar work

Nov 16, 2026

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

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.
Aug 21, 2026

Goal Staying Makes Sum-of-Costs Anonymous Multi-Agent Path Finding NP-Hard

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.
May 12, 2026

Distance-Constrained Unlabeled Multi-Agent Pathfinding

We study a graph pathfinding problem Distance-rr 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+1r+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.