License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ICLP.2017.11
URN: urn:nbn:de:0030-drops-84595
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8459/
Go to the corresponding OASIcs Volume Portal

Zhou, Neng-Fa ; Bartak, Roman

Efficient Declarative Solutions in Picat for Optimal Multi-Agent Pathfinding

pdf-format:
OASIcs-ICLP-2017-11.pdf (0.2 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{zhou_et_al:OASIcs:2018:8459,
  author =	{Neng-Fa Zhou and Roman Bartak},
  title =	{{Efficient Declarative Solutions in Picat for Optimal Multi-Agent Pathfinding}},
  booktitle =	{Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)},
  pages =	{11:1--11:2},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-058-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{58},
  editor =	{Ricardo Rocha and Tran Cao Son and Christopher Mears and Neda Saeedloei},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8459},
  URN =		{urn:nbn:de:0030-drops-84595},
  doi =		{10.4230/OASIcs.ICLP.2017.11},
  annote =	{Keywords: Multi-agent Path Finding, SAT, MIP, Picat}
}

Keywords: Multi-agent Path Finding, SAT, MIP, Picat
Collection: Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)
Issue Date: 2018
Date of publication: 14.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI