Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Inapproximability of Optimal Multi-Agent Pathfinding Problems
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.
Proves NP-completeness and several inapproximability bounds for optimal MAPF and diMAPF variants (makespan-bounded and max-agents-reaching-goal) via L-reductions from 3DM and MAXE3SAT.
Problem
The computational approximability of optimal multi-agent pathfinding problems, minimizing makespan or maximizing the number of agents reaching goals, on undirected and directed graphs.
Approach
Uses L-reductions from MAX3DM and MAXE3SAT to build MAPF/diMAPF instances with bounded makespan (3 or 2) or maximized arrivals, yielding the first inapproximability bounds for these MAPF optimization variants.
Key results
- MAPF and diMAPF with makespan 3 are NP-complete; no polytime approximation within factor 4/3 for minimizing makespan (Corollary 6), and 3/2 for two-type agents (Corollary 8).
- MAX-diMAPF with makespan bound 3 admits no approximation better than 662/665 ≈ 0.995 unless P=NP (Theorem 9).
- MAX-diMAPF admits no polytime approximation better than 57/64 ≈ 0.891 unless P=NP (Corollary 11, refined from 113/120 ≈ 0.942).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Bound the makespan by 3 steps | diMAPF · diMAPF⟨ms,B≤3⟩ | complexity | Hurt |
| Bound the makespan by 3 steps | MAPF · MAPF⟨ms,B≤3⟩ | complexity | Hurt |
| Require a makespan approximation for general diMAPF | diMAPF makespan minimization · diMAPF makespan minimization | approximation ratio: α < 4/3 | Hurt |
| Require a makespan approximation for general MAPF | MAPF makespan minimization · MAPF makespan minimization | approximation ratio: α < 4/3 | Hurt |
| Restrict agents and goals to two types | MAPF · Typed MAPF⟨ms,B≤2⟩ | complexity | Hurt |
| Restrict agents and goals to two types | diMAPF · Typed diMAPF⟨ms,B≤2⟩ | approximation ratio: α < 3/2 | Hurt |
| Maximize arrivals with makespan bounded by 3 | MAXMAPF⟨ms,B≤3⟩ · MAXMAPF⟨ms,B≤3⟩ | approximation ratio: 662/665 ≈ 0.995 | Hurt |
| Maximize arrivals with makespan bounded by 3 | MAX-diMAPF⟨ms,B≤3⟩ · MAX-diMAPF⟨ms,B≤3⟩ | approximation ratio: 662/665 ≈ 0.995 | Hurt |
| Use the MAXE3SAT reduction to bound approximability | MAX-diMAPF · MAX-diMAPF | approximation ratio: 113/120 ≈ 0.942 | Hurt |
| Reduce the number of dark agents to ⌈m/8⌉ + 1 | MAX-diMAPF · MAX-diMAPF | approximation ratio: 57/64 ≈ 0.891 | Hurt |
Limitations
- Results are worst-case hardness bounds and do not address average-case or practical instances.
- Tightness of the bounds is not established; authors aim to tighten them in future work.
- Results are not extended to restricted graph classes such as grids, planar graphs, or trees.
Experimental setup
Metrics: approximation ratio NP-completeness
Builds on: L-reduction (Papadimitriou and Yannakakis) diMAPF definitions (Nebel) MAX3DM approximation (Cygan) MAXE3SAT inapproximability (Hastad)
Closest papers by meaning
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.90)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.89)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.89)
- Windowed MAPF with Completeness Guarantees (AAAI 2025 · similarity 0.89)
- Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding (AAAI 2025 · similarity 0.88)
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.88)
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.