2024/12/12 by Foivos Fioravantes, Dušan Knop, Fioravantes, Foivos +9 · 2 citations
Computer Science · #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Mobile Agent-Based Network Management #Multi-Agent Systems and Negotiation #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2412.09433
openalex publication_date 2024/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destinations as soon as possible, but without colliding with each other. We aim to minimize the maximum time any agent takes to reach their goal, ensuring optimal path length. In this work, we complement a recent thread of results that aim to systematically study the algorithmic behavior of this problem, through the parameterized complexity point of view. First, we show that MAPF is NP-hard when the given network has a star-like topology (bounded vertex cover number) or is a tree with 11 leaves. Both of these results fill important gaps in our understanding of the tractability of this problem that were left untreated in the recent work of [Fioravantes et al. Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology. AAAI'24]. Nevertheless, our main contribution is an exact algorithm that scales well as the input grows (FPT) when the topology of the given network is highly centralized (bounded distance to clique). This parameter is significant as it mirrors real-world networks. In such environments, a bunch of central hubs (e.g., processing areas) are connected to only few peripheral nodes.