The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True

2022/10/10 by Bernhard Nebel, Nebel, Bernhard · 1 citation
Computer Science · Engineering · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #I.2.8 #Mobile Agent-Based Network Management #Modular Robots and Swarm Intelligence #Multiagent Systems (cs.MA) #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2210.04590

openalex publication_date 2022/10/10 · openalex created_date 2022/10/14 · openalex updated_date 2026/07/28

Abstract

The determination of the computational complexity of multi-agent pathfinding on directed graphs (diMAPF) has been an open research problem for many years. While diMAPF has been shown to be polynomial for some special cases, only recently, it has been established that the problem is NP-hard in general. Further, it has been proved that diMAPF will be in NP if the short solution hypothesis for strongly connected directed graphs is correct. In this paper, it is shown that this hypothesis is indeed true, even when one allows for synchronous rotations.

Cited by

• Solving Multi-Agent Multi-Goal Path Finding Problems in Polynomial Time

Related

• Multi-Agent Path Finding For Large Agents Is Intractable
• Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology
• Refined Hardness of Distance-Optimal Multi-Agent Path Finding
• Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids
• Dynamic Programming based Local Search approaches for Multi-Agent Path Finding problems on Directed Graphs