@INPROCEEDINGS{dmap2016surynek,
author = {Pavel Surynek and Ariel Felner and Roni Stern and Eli Boyarski},
title = {Efficient {SAT} Approach to Multi-Agent Path Finding under the Sum of Costs Objective},
abstract = {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 sumof-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 shown 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.},
url = {https://icaps16.icaps-conference.org/proceedings/dmap16.pdf#page=69}
}

{"_id":"v4LGPyfWKerwp36XC","bibbaseid":"surynek-felner-stern-boyarski-efficientsatapproachtomultiagentpathfindingunderthesumofcostsobjective","downloads":0,"creationDate":"2016-05-19T13:26:44.118Z","title":"Efficient SAT Approach to Multi-Agent Path Finding under the Sum of Costs Objective","author_short":["Surynek, P.","Felner, A.","Stern, R.","Boyarski, E."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/dmap16.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Pavel"],"propositions":[],"lastnames":["Surynek"],"suffixes":[]},{"firstnames":["Ariel"],"propositions":[],"lastnames":["Felner"],"suffixes":[]},{"firstnames":["Roni"],"propositions":[],"lastnames":["Stern"],"suffixes":[]},{"firstnames":["Eli"],"propositions":[],"lastnames":["Boyarski"],"suffixes":[]}],"title":"Efficient SAT Approach to Multi-Agent Path Finding under the Sum of Costs Objective","abstract":"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 sumof-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 shown 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.","url":"https://icaps16.icaps-conference.org/proceedings/dmap16.pdf#page=69","bibtex":"@INPROCEEDINGS{dmap2016surynek,\nauthor = {Pavel Surynek and Ariel Felner and Roni Stern and Eli Boyarski},\ntitle = {Efficient {SAT} Approach to Multi-Agent Path Finding under the Sum of Costs Objective},\nabstract = {In the multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. In\nthis paper we present the first SAT-solver for the sumof-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 shown 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.},\nurl = {https://icaps16.icaps-conference.org/proceedings/dmap16.pdf#page=69}\n}\n\n","author_short":["Surynek, P.","Felner, A.","Stern, R.","Boyarski, E."],"key":"dmap2016surynek","id":"dmap2016surynek","bibbaseid":"surynek-felner-stern-boyarski-efficientsatapproachtomultiagentpathfindingunderthesumofcostsobjective","role":"author","urls":{"Paper":"https://icaps16.icaps-conference.org/proceedings/dmap16.pdf#page=69"},"metadata":{"authorlinks":{}},"downloads":0,"html":""},"search_terms":["efficient","sat","approach","multi","agent","path","finding","under","sum","costs","objective","surynek","felner","stern","boyarski"],"keywords":[],"authorIDs":[],"dataSources":["YTEH97APBj4BGmm5u","oF6o5YwZvH6DhpPhw"]}