Problem Compilation for Multi-Agent Path Finding: a Survey

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

Problem Compilation for Multi-Agent Path Finding: a Survey

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA22-31346S" target="_blank" >GA22-31346S: logicMOVE: Logic Reasoning in Motion Planning for Multiple Robotic Agents</a><br>

Continuities

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

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence

ISBN

978-1-956792-00-3

ISSN

1045-0823

e-ISSN

—

Number of pages

8

Pages from-to

5615-5622

Publisher name

International Joint Conferences on Artificial Intelligence Organization

Place of publication

—

Event location

Vienna

Event date

Jul 23, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—