1 Search Results for "Bartak, Roman"


Document
Efficient Declarative Solutions in Picat for Optimal Multi-Agent Pathfinding

Authors: Neng-Fa Zhou and Roman Bartak

Published in: OASIcs, Volume 58, Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)


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.

Cite as

Neng-Fa Zhou and Roman Bartak. Efficient Declarative Solutions in Picat for Optimal Multi-Agent Pathfinding. In Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017). Open Access Series in Informatics (OASIcs), Volume 58, pp. 11:1-11:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{zhou_et_al:OASIcs.ICLP.2017.11,
  author =	{Zhou, Neng-Fa and Bartak, Roman},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-058-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{58},
  editor =	{Rocha, Ricardo and Son, Tran Cao and Mears, Christopher and Saeedloei, Neda},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2017.11},
  URN =		{urn:nbn:de:0030-drops-84595},
  doi =		{10.4230/OASIcs.ICLP.2017.11},
  annote =	{Keywords: Multi-agent Path Finding, SAT, MIP, Picat}
}
  • Refine by Author
  • 1 Bartak, Roman
  • 1 Zhou, Neng-Fa

  • Refine by Classification

  • Refine by Keyword
  • 1 MIP
  • 1 Multi-agent Path Finding
  • 1 Picat
  • 1 SAT

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail