Modeling and Solving the Multi-agent Pathfinding Problem in Picat

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10371747" target="_blank" >RIV/00216208:11320/17:10371747 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.picat-lang.org/papers/ictai17.pdf" target="_blank" >http://www.picat-lang.org/papers/ictai17.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/ICTAI.2017.00147" target="_blank" >10.1109/ICTAI.2017.00147</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Modeling and Solving the Multi-agent Pathfinding Problem in Picat

Popis výsledku v původním jazyce

The multi-agent pathfinding (MAPF) problem has attracted considerable attention because of its relation to practical applications. In this paper, we present a constraint-based declarative model for MAPF, together with its implementation in Picat, a logic-based programming language. We show experimentally that our Picat-based implementation is highly competitive and sometimes outperforms previous approaches. Importantly, the proposed Picat implementation is very versatile. We demonstrate this by showing how it can be easily adapted to optimize different MAPF objectives, such as minimizing makespan or minimizing the sum of costs, and for a range of MAPF variants. Moreover, a Picat-based model can be automatically compiled to several general-purpose solvers such as SAT solvers and Mixed Integer Programming solvers (MIP). This is particularly important for MAPF because some MAPF variants are solved more efficiently when compiled to SAT while other variants are solved more efficiently when compiled to MIP. We analyze these differences and the impact of different declarative models and encodings on empirical performance.

Název v anglickém jazyce

Modeling and Solving the Multi-agent Pathfinding Problem in Picat

Popis výsledku anglicky

The multi-agent pathfinding (MAPF) problem has attracted considerable attention because of its relation to practical applications. In this paper, we present a constraint-based declarative model for MAPF, together with its implementation in Picat, a logic-based programming language. We show experimentally that our Picat-based implementation is highly competitive and sometimes outperforms previous approaches. Importantly, the proposed Picat implementation is very versatile. We demonstrate this by showing how it can be easily adapted to optimize different MAPF objectives, such as minimizing makespan or minimizing the sum of costs, and for a range of MAPF variants. Moreover, a Picat-based model can be automatically compiled to several general-purpose solvers such as SAT solvers and Mixed Integer Programming solvers (MIP). This is particularly important for MAPF because some MAPF variants are solved more efficiently when compiled to SAT while other variants are solved more efficiently when compiled to MIP. We analyze these differences and the impact of different declarative models and encodings on empirical performance.

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

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2017

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 2017 International Conference on Tools with Artificial Intelligence (ICTAI)

ISBN

978-1-5386-3876-7

ISSN

1082-3409

e-ISSN

neuvedeno

Počet stran výsledku

8

Strana od-do

959-966

Název nakladatele

IEEE

Místo vydání

USA

Místo konání akce

Boston, USA

Datum konání akce

6. 11. 2017

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

WRD - Celosvětová akce

Kód UT WoS článku

000435294700136