Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies multiagent path finding with a communication constraint (agents must stay d-connected) under parameterized complexity, giving W[1]-hardness for number of agents and FPT algorithms for tree-like structures.
Problem
Makespan-optimal multiagent path finding where, at every time step, agents' positions must form a connected backbone in the communication graph (distance at most d in the network); the complexity is open under structural and combined parameterizations.
Approach
Introduces the MAPFCC problem and gives parameterized results: W[1]-hardness by number of agents even for makespan 3 and range 1; FPT by agents plus max degree plus range via configuration graph; FPT on trees by pruning high-degree vertices to degree 3k; FPT by treewidth plus makespan plus range via MSO2 encoding on a time-expanded augmented graph with Courcelle's theorem.
Key results
- MAPFCC is W[1]-hard parameterized by the number of agents even when makespan is 3 and communication range is 1.
- MAPFCC is FPT parameterized by number of agents, maximum degree and communication range, and on trees parameterized by number of agents plus communication range.
- MAPFCC is FPT parameterized by treewidth plus makespan plus communication range, and by agents plus makespan plus range on bounded local treewidth graphs including planar graphs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Bound the input graph's maximum degree and parameterize by k, Δ, and d | MAPFCC configuration-network algorithm · MAPFCC | parameterized complexity | Helped |
| Restrict the input graph to a tree and parameterize by k and d | MAPFCC tree-pruning algorithm · MAPFCC on trees | parameterized complexity | Helped |
| Use bounded treewidth and parameterize by w, ℓ, and d | MAPFCC MSO algorithm · MAPFCC on bounded-treewidth graphs | parameterized complexity | Helped |
| Restrict the graph class to one with bounded local treewidth and parameterize by k, ℓ, and d | MAPFCC local-treewidth algorithm · MAPFCC on bounded-local-treewidth graphs | parameterized complexity | Helped |
| Restrict the graph class to planar graphs and parameterize by k, ℓ, and d | MAPFCC local-treewidth algorithm · MAPFCC on planar graphs | parameterized complexity | Helped |
| Parameterize only by the number of agents k, even with makespan ℓ=3 and communication range d=1 | MAPFCC · MAPFCC | parameterized complexity: ℓ=3; d=1 | Hurt |
Surprising findings
- Parameterizing by the number of agents alone is W[1]-hard even for makespan 3 and communication range 1, ruling out FPT for single parameters k, makespan, or d.
Limitations
- Purely theoretical; no implementation or experimental evaluation of the algorithms.
- Hardness result rules out FPT for agents alone, so practical scalability depends on bounded structural parameters.
Experimental setup
Metrics: parameterized complexity classification
Builds on: Courcelle theorem multicolored clique reduction
Closest papers by meaning
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.92)
- Solving Multiagent Path Finding on Highly Centralized Networks (AAAI 2025 · similarity 0.92)
- Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size (AAAI 2025 · similarity 0.87)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.86)
- Improved Anonymous Multi-Agent Path Finding Algorithm (AAAI 2024 · similarity 0.86)
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.