Solving Multiagent Path Finding on Highly Centralized Networks
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10510244" target="_blank" >RIV/00216208:11320/25:10510244 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21240/25:00378600
Result on the web
<a href="https://doi.org/10.1609/aaai.v39i22.34484" target="_blank" >https://doi.org/10.1609/aaai.v39i22.34484</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1609/aaai.v39i22.34484" target="_blank" >10.1609/aaai.v39i22.34484</a>
Alternative languages
Result language
angličtina
Original language name
Solving Multiagent Path Finding on Highly Centralized Networks
Original language description
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, presented in 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
THIRTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, AAAI-25
ISBN
978-1-57735-897-8
ISSN
2159-5399
e-ISSN
2374-3468
Number of pages
8
Pages from-to
23186-23193
Publisher name
ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE
Place of publication
PALO ALTO
Event location
Philadelphia
Event date
Feb 25, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001477505600008