提出高效算法解决高度中心化网络中的多智能体路径规划问题
Solving Multiagent Path Finding on Highly Centralized Networks
- 基于网络中心化程度设计可扩展的精确算法
- 在11叶树和星型拓扑下证明问题为NP难
- 适用于有核心枢纽的现实网络场景
多智能体路径规划（MAPF）问题旨在为一组智能体在给定网络中规划无碰撞路径，使其以最短时间到达目标。本文从参数复杂度视角系统研究该问题。首先，证明当网络具有星型拓扑（顶点覆盖数有界）或为11叶树时，MAPF问题是NP难的，填补了近期[Fiorevantes et al., AAAI'24]工作的空白。主要贡献是提出一个在高度中心化网络（距离团有界）上表现良好的固定参数可解（FPT）精确算法。该参数能有效刻画真实世界网络中由少数核心枢纽连接少量外围节点的结构特征。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。