Problem Compilation for Multi-Agent Path Finding: a Survey
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00360903" target="_blank" >RIV/68407700:21240/22:00360903 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.24963/ijcai.2022/783" target="_blank" >https://doi.org/10.24963/ijcai.2022/783</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.24963/ijcai.2022/783" target="_blank" >10.24963/ijcai.2022/783</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Problem Compilation for Multi-Agent Path Finding: a Survey
Popis výsledku v původním jazyce
Multi-agent path finding (MAPF) attracts considerable attention in artificial intelligence community. The task in the standard MAPF is to find discrete paths through which agents can navigate from their starting positions to individual goal positions. The combination of two additional requirements makes the problem computationally challenging: agents must not collide with each other and the paths must be optimal with respect to some objective. Two major approaches to optimal MAPF solving include dedicated search-based methods, and compilation-based methods that reduce a MAPF instance to an instance in a different formalism, for which an efficient solver exists. In this survey, we summarize major compilation-based solvers for MAPF using CSP, SAT, and MILP formalisms. We explain the core ideas of the solvers in a simplified and unified way while preserving the merit making them more accessible for a wider audience.
Název v anglickém jazyce
Problem Compilation for Multi-Agent Path Finding: a Survey
Popis výsledku anglicky
Multi-agent path finding (MAPF) attracts considerable attention in artificial intelligence community. The task in the standard MAPF is to find discrete paths through which agents can navigate from their starting positions to individual goal positions. The combination of two additional requirements makes the problem computationally challenging: agents must not collide with each other and the paths must be optimal with respect to some objective. Two major approaches to optimal MAPF solving include dedicated search-based methods, and compilation-based methods that reduce a MAPF instance to an instance in a different formalism, for which an efficient solver exists. In this survey, we summarize major compilation-based solvers for MAPF using CSP, SAT, and MILP formalisms. We explain the core ideas of the solvers in a simplified and unified way while preserving the merit making them more accessible for a wider audience.
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/GA22-31346S" target="_blank" >GA22-31346S: logicMOVE: Logické uvažování v plánování pohybu pro mnoho robotických agentů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2022
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
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
ISBN
978-1-956792-00-3
ISSN
1045-0823
e-ISSN
—
Počet stran výsledku
8
Strana od-do
5615-5622
Název nakladatele
International Joint Conferences on Artificial Intelligence Organization
Místo vydání
—
Místo konání akce
Vienna
Datum konání akce
23. 7. 2022
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—