Modeling and Solving the Multi-agent Pathfinding Problem in Picat
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Modeling and Solving the Multi-agent Pathfinding Problem in Picat
Original language description
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.
Czech name
—
Czech description
—
Classification
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)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 2017 International Conference on Tools with Artificial Intelligence (ICTAI)
ISBN
978-1-5386-3876-7
ISSN
1082-3409
e-ISSN
neuvedeno
Number of pages
8
Pages from-to
959-966
Publisher name
IEEE
Place of publication
USA
Event location
Boston, USA
Event date
Nov 6, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000435294700136