Solving Multiagent Path Finding on Highly Centralized Networks

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/68407700:21240/25:00378600

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Solving Multiagent Path Finding on Highly Centralized Networks

Popis výsledku v původním jazyce

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&apos;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.

Název v anglickém jazyce

Solving Multiagent Path Finding on Highly Centralized Networks

Popis výsledku anglicky

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&apos;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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

THIRTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, AAAI-25

ISBN

978-1-57735-897-8

ISSN

2159-5399

e-ISSN

2374-3468

Počet stran výsledku

8

Strana od-do

23186-23193

Název nakladatele

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE

Místo vydání

PALO ALTO

Místo konání akce

Philadelphia

Datum konání akce

25. 2. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001477505600008