Integration of Independence Detection into SAT-Based Optimal Multi-Agent Path Finding - A Novel SAT-based Optimal MAPF Solver. Surynek, P., Svancara, J., Felner, A., & Boyarski, E. In Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART), pages 85–95, 2017. abstract bibtex The problem of optimal multi-agent path finding (MAPF) is addressed in this paper. The task is to find optimal paths for mobile agents where each of them need to reach a unique goal position from the given start with respect to the given cost function. Agents must not collide with each other which is a source of combinatorial difficulty of the problem. An abstraction of the problem where discrete agents move in an undirected graph is usually adopted in the literature. Specifically, it is shown in this paper how to integrate independence detection (ID) technique developed for search based MAPF solving into a compilation-based technique that translates the instance of the MAPF problem into propositional satisfiability formalism (SAT). The independence detection technique allows decomposition of the instance consisting of a given number of agents into instances consisting of small groups of agents with no interaction across groups. These small instances can be solved independently and the solution of the original instance is combined from small solutions eventually. The reduction of the size of instances translated to the target SAT formalism has a significant impact on performance as shown in the presented experimental evaluation. The new solver integrating SAT translation and the independence detection is shown to be state-of-the-art in its class for optimal MAPF solving.
@INPROCEEDINGS{AFeln17a,
AUTHOR= "P. Surynek and J. Svancara and A. Felner and E. Boyarski",
TITLE= "Integration of Independence Detection into {SAT}-Based Optimal Multi-Agent Path Finding - A Novel {SAT}-based Optimal {MAPF} Solver",
BOOKTITLE= "Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)",
PAGES= "85--95",
YEAR= "2017",
PDF= "https://docs.wixstatic.com/ugd/749b4b_8045b531d493420e9bcf415b8e9d7037.pdf",
FLAGS= ":2017:,:arielfelner:,:eliboyarski:,:pavelsurynek:",
ABSTRACT=
"The problem of optimal multi-agent path finding (MAPF) is addressed in this
paper. The task is to find optimal paths for mobile agents where each of them
need to reach a unique goal position from the given start with respect to the
given cost function. Agents must not collide with each other which is a source
of combinatorial difficulty of the problem. An abstraction of the problem
where discrete agents move in an undirected graph is usually adopted in the
literature. Specifically, it is shown in this paper how to integrate
independence detection (ID) technique developed for search based MAPF solving
into a compilation-based technique that translates the instance of the MAPF
problem into propositional satisfiability formalism (SAT). The independence
detection technique allows decomposition of the instance consisting of a given
number of agents into instances consisting of small groups of agents with no
interaction across groups. These small instances can be solved independently
and the solution of the original instance is combined from small solutions
eventually. The reduction of the size of instances translated to the target
SAT formalism has a significant impact on performance as shown in the
presented experimental evaluation. The new solver integrating SAT translation
and the independence detection is shown to be state-of-the-art in its class
for optimal MAPF solving."
}
Downloads: 0
{"_id":"Pw4beG3tt6jpKNgCY","bibbaseid":"surynek-svancara-felner-boyarski-integrationofindependencedetectionintosatbasedoptimalmultiagentpathfindinganovelsatbasedoptimalmapfsolver-2017","authorIDs":[],"author_short":["Surynek, P.","Svancara, J.","Felner, A.","Boyarski, E."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["P."],"propositions":[],"lastnames":["Surynek"],"suffixes":[]},{"firstnames":["J."],"propositions":[],"lastnames":["Svancara"],"suffixes":[]},{"firstnames":["A."],"propositions":[],"lastnames":["Felner"],"suffixes":[]},{"firstnames":["E."],"propositions":[],"lastnames":["Boyarski"],"suffixes":[]}],"title":"Integration of Independence Detection into SAT-Based Optimal Multi-Agent Path Finding - A Novel SAT-based Optimal MAPF Solver","booktitle":"Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)","pages":"85–95","year":"2017","pdf":"https://docs.wixstatic.com/ugd/749b4b_8045b531d493420e9bcf415b8e9d7037.pdf","flags":":2017:,:arielfelner:,:eliboyarski:,:pavelsurynek:","abstract":"The problem of optimal multi-agent path finding (MAPF) is addressed in this paper. The task is to find optimal paths for mobile agents where each of them need to reach a unique goal position from the given start with respect to the given cost function. Agents must not collide with each other which is a source of combinatorial difficulty of the problem. An abstraction of the problem where discrete agents move in an undirected graph is usually adopted in the literature. Specifically, it is shown in this paper how to integrate independence detection (ID) technique developed for search based MAPF solving into a compilation-based technique that translates the instance of the MAPF problem into propositional satisfiability formalism (SAT). The independence detection technique allows decomposition of the instance consisting of a given number of agents into instances consisting of small groups of agents with no interaction across groups. These small instances can be solved independently and the solution of the original instance is combined from small solutions eventually. The reduction of the size of instances translated to the target SAT formalism has a significant impact on performance as shown in the presented experimental evaluation. The new solver integrating SAT translation and the independence detection is shown to be state-of-the-art in its class for optimal MAPF solving.","bibtex":"@INPROCEEDINGS{AFeln17a, \n AUTHOR= \"P. Surynek and J. Svancara and A. Felner and E. Boyarski\",\n TITLE= \"Integration of Independence Detection into {SAT}-Based Optimal Multi-Agent Path Finding - A Novel {SAT}-based Optimal {MAPF} Solver\",\n BOOKTITLE= \"Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)\",\n PAGES= \"85--95\",\n YEAR= \"2017\",\n PDF= \"https://docs.wixstatic.com/ugd/749b4b_8045b531d493420e9bcf415b8e9d7037.pdf\",\n FLAGS= \":2017:,:arielfelner:,:eliboyarski:,:pavelsurynek:\",\n ABSTRACT= \n\"The problem of optimal multi-agent path finding (MAPF) is addressed in this\npaper. The task is to find optimal paths for mobile agents where each of them\nneed to reach a unique goal position from the given start with respect to the\ngiven cost function. Agents must not collide with each other which is a source\nof combinatorial difficulty of the problem. An abstraction of the problem\nwhere discrete agents move in an undirected graph is usually adopted in the\nliterature. Specifically, it is shown in this paper how to integrate\nindependence detection (ID) technique developed for search based MAPF solving\ninto a compilation-based technique that translates the instance of the MAPF\nproblem into propositional satisfiability formalism (SAT). The independence\ndetection technique allows decomposition of the instance consisting of a given\nnumber of agents into instances consisting of small groups of agents with no\ninteraction across groups. These small instances can be solved independently\nand the solution of the original instance is combined from small solutions\neventually. The reduction of the size of instances translated to the target\nSAT formalism has a significant impact on performance as shown in the\npresented experimental evaluation. The new solver integrating SAT translation\nand the independence detection is shown to be state-of-the-art in its class\nfor optimal MAPF solving.\"\n}\n\n","author_short":["Surynek, P.","Svancara, J.","Felner, A.","Boyarski, E."],"key":"AFeln17a","id":"AFeln17a","bibbaseid":"surynek-svancara-felner-boyarski-integrationofindependencedetectionintosatbasedoptimalmultiagentpathfindinganovelsatbasedoptimalmapfsolver-2017","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://mapf.info/bib/mapf.bib","creationDate":"2019-05-05T18:02:17.695Z","downloads":0,"keywords":[],"search_terms":["integration","independence","detection","sat","based","optimal","multi","agent","path","finding","novel","sat","based","optimal","mapf","solver","surynek","svancara","felner","boyarski"],"title":"Integration of Independence Detection into SAT-Based Optimal Multi-Agent Path Finding - A Novel SAT-based Optimal MAPF Solver","year":2017,"dataSources":["oEkRzPPMbrG9LyYPh"]}