Adversarial Multi-Agent Path Finding is Intractable

Kód výsledku v IS VaVaI

RIV/68407700:21240/21:00356868 - isvavai.cz

Výsledek na webu

https://doi.org/10.1109/ICTAI52525.2021.00078

DOI - Digital Object Identifier

10.1109/ICTAI52525.2021.00078

Jazyk výsledku

angličtina

Název v původním jazyce

Adversarial Multi-Agent Path Finding is Intractable

Popis výsledku v původním jazyce

Adversarial Multi-Agent Path Finding (AMAPF) extends the standard discrete Multi-Agent Path Finding with an adversarial element. Agents of two competing teams are deployed in a shared environment represented by an undirected graph. The first team aims to navigate all its agents from their initial locations to given goal locations, while the second team aims to prevent agents of the first team from fulfilling their goal. We prove that the problem of finding a winning strategy is EXPTIME-complete.

Název v anglickém jazyce

Adversarial Multi-Agent Path Finding is Intractable

Popis výsledku anglicky

Adversarial Multi-Agent Path Finding (AMAPF) extends the standard discrete Multi-Agent Path Finding with an adversarial element. Agents of two competing teams are deployed in a shared environment represented by an undirected graph. The first team aims to navigate all its agents from their initial locations to given goal locations, while the second team aims to prevent agents of the first team from fulfilling their goal. We prove that the problem of finding a winning strategy is EXPTIME-complete.

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

GA19-17966S: intALG-MAPFg: Inteligentní algoritmy pro zobecněné varianty multi-agetního hledání cest

Návaznosti

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

Rok uplatnění

2021

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

2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI)

ISBN

978-1-6654-0898-1

ISSN

1082-3409

e-ISSN

2375-0197

Počet stran výsledku

6

Strana od-do

481-486

Název nakladatele

IEEE Computer Society

Místo vydání

Los Alamitos

Místo konání akce

Washington

Datum konání akce

1. 11. 2021

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

WRD - Celosvětová akce

Kód UT WoS článku

000747482300070