Solving Multiagent Path Finding on Highly Centralized Networks

作     者：Fioravantes, Foivos Knop, Dušan Křišťan, Jan Matyáš Melissinos, Nikolaos Opler, Michal Vu, Tung Anh 

作者机构：Department of Theoretical Computer Science Faculty of Information Technology Czech Technical University in Prague Prague Czech Republic Computer Science Institute Faculty of Mathematics and Physics Charles University Prague Czech Republic 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Network topology 

摘      要：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. © 2024, CC BY.