Efficient SAT Approach to Multi-Agent Path Finding under the Sum of Costs Objective

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10333014" target="_blank" >RIV/00216208:11320/16:10333014 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Efficient SAT Approach to Multi-Agent Path Finding under the Sum of Costs Objective
Original language description
In the multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. In this paper we present the first SAT-solver for the sum-of-costs variant of MAPF which was previously only solved by search-based methods. Using both a lower bound on the sum-of-costs and an upper bound on the makespan, we are able to have a reasonable number of variables in our SAT encoding. We then further improve the encoding by borrowing ideas from ICTS, a search-based solver. Experimental evaluation on several domains showed that there are many scenarios where the new SAT-based method outperforms the best variants of previous sum-of-costs search solvers - the ICTS and ICBS algorithms.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 22nd European Conference on Artificial Intelligence
ISBN
978-1-61499-672-9
ISSN
—
e-ISSN
—
Number of pages
9
Pages from-to
810-818
Publisher name
IOS Press
Place of publication
Amsterdam
Event location
Hague
Event date
Aug 29, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)