Problem Compilation for Multi-Agent Path Finding: a Survey

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>

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.

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

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

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ů

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

—