Adversarial Multi-Agent Path Finding is Intractable
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F21%3A00356868" target="_blank" >RIV/68407700:21240/21:00356868 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1109/ICTAI52525.2021.00078" target="_blank" >https://doi.org/10.1109/ICTAI52525.2021.00078</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/ICTAI52525.2021.00078" target="_blank" >10.1109/ICTAI52525.2021.00078</a>
Alternativní jazyky
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.
Klasifikace
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)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA19-17966S" target="_blank" >GA19-17966S: intALG-MAPFg: Inteligentní algoritmy pro zobecněné varianty multi-agetního hledání cest</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
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ů
Údaje specifické pro druh výsledku
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