Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00374774" target="_blank" >RIV/68407700:21240/24:00374774 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1609/aaai.v38i16.29686" target="_blank" >https://doi.org/10.1609/aaai.v38i16.29686</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1609/aaai.v38i16.29686" target="_blank" >10.1609/aaai.v38i16.29686</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology

Popis výsledku v původním jazyce

In the Multiagent Path Finding (MAPF for short) problem, we focus on efficiently finding non-colliding paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target. An important measure of the quality of the solution is the length of the proposed schedule l, that is, the length of a longest path (including the waiting time). In this work, we propose a systematic study under the parameterized complexity framework. The hardness results we provide align with many heuristics used for this problem, whose running time could potentially be improved based on our Fixed-Parameter Tractability (FPT) results. We show that MAPF is W[1]-hard with respect to k (even if k is combined with the maximum degree of the input graph). The problem remains NP-hard in planar graphs even if the maximum degree and the makespan l are fixed constants. On the positive side, we show an FPT algorithm for k+l. As we continue, the structure of G comes into play. We give an FPT algorithm for parameter k plus the diameter of the graph G. The MAPF problem is W[1]-hard for cliquewidth of G plus l while it is FPT for treewidth of G plus l.

Název v anglickém jazyce

Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology

Popis výsledku anglicky

In the Multiagent Path Finding (MAPF for short) problem, we focus on efficiently finding non-colliding paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target. An important measure of the quality of the solution is the length of the proposed schedule l, that is, the length of a longest path (including the waiting time). In this work, we propose a systematic study under the parameterized complexity framework. The hardness results we provide align with many heuristics used for this problem, whose running time could potentially be improved based on our Fixed-Parameter Tractability (FPT) results. We show that MAPF is W[1]-hard with respect to k (even if k is combined with the maximum degree of the input graph). The problem remains NP-hard in planar graphs even if the maximum degree and the makespan l are fixed constants. On the positive side, we show an FPT algorithm for k+l. As we continue, the structure of G comes into play. We give an FPT algorithm for parameter k plus the diameter of the graph G. The MAPF problem is W[1]-hard for cliquewidth of G plus l while it is FPT for treewidth of G plus l.

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í

2024

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

Proceedings of the 38th AAAI Conference on Artificial Intelligence

ISBN

—

ISSN

2159-5399

e-ISSN

2374-3468

Počet stran výsledku

9

Strana od-do

17380-17388

Název nakladatele

AAAI Press

Místo vydání

Menlo Park

Místo konání akce

Vancouver

Datum konání akce

20. 2. 2024

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

WRD - Celosvětová akce

Kód UT WoS článku

001239323500011