Efficient Declarative Solutions in Picat for Optimal Multi-Agent Pathfinding

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://drops.dagstuhl.de/opus/volltexte/2018/8459/pdf/OASIcs-ICLP-2017-11.pdf" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2018/8459/pdf/OASIcs-ICLP-2017-11.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/OASIcs.ICLP.2017.11" target="_blank" >10.4230/OASIcs.ICLP.2017.11</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Efficient Declarative Solutions in Picat for Optimal Multi-Agent Pathfinding

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. The majority of solutions for MAPF are algorithmic. Recently, declarative solutions that reduce MAPF to encodings for off-the-shelf solvers have achieved remarkable success. We present a constraint-based declarative model for MAPF, together with its implementation in Picat, which uses SAT and MIP. We consider both the makespan and the sum-of-costs objectives, and propose a preprocessing technique for improving the performance of the model. Experimental results show that the implementation using SAT is highly competitive. We also analyze the high performance of the SAT solution by relating it to the SAT encoding algorithms that are used in the Picat compiler.

Název v anglickém jazyce

Efficient Declarative Solutions in Picat for Optimal Multi-Agent Pathfinding

Popis výsledku anglicky

The multi-agent pathfinding (MAPF) problem has attracted considerable attention because of its relation to practical applications. The majority of solutions for MAPF are algorithmic. Recently, declarative solutions that reduce MAPF to encodings for off-the-shelf solvers have achieved remarkable success. We present a constraint-based declarative model for MAPF, together with its implementation in Picat, which uses SAT and MIP. We consider both the makespan and the sum-of-costs objectives, and propose a preprocessing technique for improving the performance of the model. Experimental results show that the implementation using SAT is highly competitive. We also analyze the high performance of the SAT solution by relating it to the SAT encoding algorithms that are used in the Picat compiler.

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/8G15027" target="_blank" >8G15027: INTEGRACE HEURISTICKÉHO PROHLEDÁVÁNÍ A KOMPILAČNÍCH TECHNIK PRO HLEDÁNÍ CEST S MNOHA AGENTY</a><br>

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

Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)

ISBN

978-3-95977-058-3

ISSN

2190-6807

e-ISSN

neuvedeno

Počet stran výsledku

2

Strana od-do

1-2

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Melbourne, Australia

Datum konání akce

28. 8. 2017

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

WRD - Celosvětová akce

Kód UT WoS článku

—