Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs. Surynek, P. In Proceedings of the 26th International Conference on Tools with Artificial Intelligence (ICTAI), pages 875–882, 2014. abstract bibtex This paper addresses makespan optimal solving of cooperative path-finding problem (CPF) by translating it to propositional satisfiability (SAT). The task is to relocate set of agents to given goal positions so that they do not collide with each other. A novel SAT encoding of CPF is suggested. The novel encoding uses the concept of matching in a bipartite graph to separate spatial constraint of CPF from consideration of individual agents. The separation allowed reducing the size of encoding significantly. The conducted experimental evaluation shown that novel encoding can be solved faster than existing encodings for CPF and also that the SAT based methods dominates over A* based methods in environment densely occupied by agents.
@INPROCEEDINGS{PSury14a,
AUTHOR= "P. Surynek",
TITLE= "Compact Representations of Cooperative Path-Finding as {SAT} Based on Matchings in Bipartite Graphs",
BOOKTITLE= "Proceedings of the 26th International Conference on Tools with Artificial Intelligence (ICTAI)",
PAGES= "875--882",
YEAR= "2014",
PDF= "http://surynek.com/publications/files/SurynekPavel_Matching-Code_ICTAI-2014.pdf",
FLAGS= ":2014:,:pavelsurynek:",
ABSTRACT=
"This paper addresses makespan optimal solving of cooperative path-finding
problem (CPF) by translating it to propositional satisfiability (SAT). The
task is to relocate set of agents to given goal positions so that they do not
collide with each other. A novel SAT encoding of CPF is suggested. The novel
encoding uses the concept of matching in a bipartite graph to separate spatial
constraint of CPF from consideration of individual agents. The separation
allowed reducing the size of encoding significantly. The conducted
experimental evaluation shown that novel encoding can be solved faster than
existing encodings for CPF and also that the SAT based methods dominates over
A* based methods in environment densely occupied by agents."
}
Downloads: 0
{"_id":"uqjDMghWWzhmPzC64","bibbaseid":"surynek-compactrepresentationsofcooperativepathfindingassatbasedonmatchingsinbipartitegraphs-2014","authorIDs":[],"author_short":["Surynek, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["P."],"propositions":[],"lastnames":["Surynek"],"suffixes":[]}],"title":"Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs","booktitle":"Proceedings of the 26th International Conference on Tools with Artificial Intelligence (ICTAI)","pages":"875–882","year":"2014","pdf":"http://surynek.com/publications/files/SurynekPavel_Matching-Code_ICTAI-2014.pdf","flags":":2014:,:pavelsurynek:","abstract":"This paper addresses makespan optimal solving of cooperative path-finding problem (CPF) by translating it to propositional satisfiability (SAT). The task is to relocate set of agents to given goal positions so that they do not collide with each other. A novel SAT encoding of CPF is suggested. The novel encoding uses the concept of matching in a bipartite graph to separate spatial constraint of CPF from consideration of individual agents. The separation allowed reducing the size of encoding significantly. The conducted experimental evaluation shown that novel encoding can be solved faster than existing encodings for CPF and also that the SAT based methods dominates over A* based methods in environment densely occupied by agents.","bibtex":"@INPROCEEDINGS{PSury14a, \n AUTHOR= \"P. Surynek\",\n TITLE= \"Compact Representations of Cooperative Path-Finding as {SAT} Based on Matchings in Bipartite Graphs\",\n BOOKTITLE= \"Proceedings of the 26th International Conference on Tools with Artificial Intelligence (ICTAI)\",\n PAGES= \"875--882\",\n YEAR= \"2014\",\n PDF= \"http://surynek.com/publications/files/SurynekPavel_Matching-Code_ICTAI-2014.pdf\",\n FLAGS= \":2014:,:pavelsurynek:\",\n ABSTRACT= \n\"This paper addresses makespan optimal solving of cooperative path-finding\nproblem (CPF) by translating it to propositional satisfiability (SAT). The\ntask is to relocate set of agents to given goal positions so that they do not\ncollide with each other. A novel SAT encoding of CPF is suggested. The novel\nencoding uses the concept of matching in a bipartite graph to separate spatial\nconstraint of CPF from consideration of individual agents. The separation\nallowed reducing the size of encoding significantly. The conducted\nexperimental evaluation shown that novel encoding can be solved faster than\nexisting encodings for CPF and also that the SAT based methods dominates over\nA* based methods in environment densely occupied by agents.\"\n}\n\n","author_short":["Surynek, P."],"key":"PSury14a","id":"PSury14a","bibbaseid":"surynek-compactrepresentationsofcooperativepathfindingassatbasedonmatchingsinbipartitegraphs-2014","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://mapf.info/bib/mapf.bib","creationDate":"2019-05-05T18:02:17.735Z","downloads":0,"keywords":[],"search_terms":["compact","representations","cooperative","path","finding","sat","based","matchings","bipartite","graphs","surynek"],"title":"Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs","year":2014,"dataSources":["oEkRzPPMbrG9LyYPh"]}