@INPROCEEDINGS{ABote15a,
 AUTHOR= "A. Botea and P. Surynek",
 TITLE= "Multi-Agent Path Finding on Strongly Biconnected Digraphs",
 BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)",
 YEAR= "2015",
 PAGES= "2024--2030",
 PDF= "https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/download/9653/9499",
 FLAGS= ":2015;,:adibotea:,:pavelsurynek:",
 ABSTRACT= 
"Much of the literature on multi-agent path finding focuses on undirected
graphs, where motion is permitted in both directions along a graph
edge. Despite this, travelling on directed graphs is relevant in navigation
domains, such as pathfinding in games, and asymmetric communication
networks. We consider multi-agent path finding on strongly biconnected
directed graphs. We show that all instances with at least two unoccupied
positions can be solved or proven unsolvable. We present a polynomial-time
algorithm for this class of problems, and analyze its complexity. Our work may
be the first formal study of multi-agent path finding on directed graphs."
}

{"_id":"x5dPA5iyZaJMAKSiR","bibbaseid":"botea-surynek-multiagentpathfindingonstronglybiconnecteddigraphs-2015","authorIDs":[],"author_short":["Botea, A.","Surynek, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["A."],"propositions":[],"lastnames":["Botea"],"suffixes":[]},{"firstnames":["P."],"propositions":[],"lastnames":["Surynek"],"suffixes":[]}],"title":"Multi-Agent Path Finding on Strongly Biconnected Digraphs","booktitle":"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)","year":"2015","pages":"2024–2030","pdf":"https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/download/9653/9499","flags":":2015;,:adibotea:,:pavelsurynek:","abstract":"Much of the literature on multi-agent path finding focuses on undirected graphs, where motion is permitted in both directions along a graph edge. Despite this, travelling on directed graphs is relevant in navigation domains, such as pathfinding in games, and asymmetric communication networks. We consider multi-agent path finding on strongly biconnected directed graphs. We show that all instances with at least two unoccupied positions can be solved or proven unsolvable. We present a polynomial-time algorithm for this class of problems, and analyze its complexity. Our work may be the first formal study of multi-agent path finding on directed graphs.","bibtex":"@INPROCEEDINGS{ABote15a,\n AUTHOR= \"A. Botea and P. Surynek\",\n TITLE= \"Multi-Agent Path Finding on Strongly Biconnected Digraphs\",\n BOOKTITLE= \"Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)\",\n YEAR= \"2015\",\n PAGES= \"2024--2030\",\n PDF= \"https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/download/9653/9499\",\n FLAGS= \":2015;,:adibotea:,:pavelsurynek:\",\n ABSTRACT= \n\"Much of the literature on multi-agent path finding focuses on undirected\ngraphs, where motion is permitted in both directions along a graph\nedge. Despite this, travelling on directed graphs is relevant in navigation\ndomains, such as pathfinding in games, and asymmetric communication\nnetworks. We consider multi-agent path finding on strongly biconnected\ndirected graphs. We show that all instances with at least two unoccupied\npositions can be solved or proven unsolvable. We present a polynomial-time\nalgorithm for this class of problems, and analyze its complexity. Our work may\nbe the first formal study of multi-agent path finding on directed graphs.\"\n}\n\n","author_short":["Botea, A.","Surynek, P."],"key":"ABote15a","id":"ABote15a","bibbaseid":"botea-surynek-multiagentpathfindingonstronglybiconnecteddigraphs-2015","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://mapf.info/bib/mapf.bib","creationDate":"2019-05-05T18:02:17.739Z","downloads":0,"keywords":[],"search_terms":["multi","agent","path","finding","strongly","biconnected","digraphs","botea","surynek"],"title":"Multi-Agent Path Finding on Strongly Biconnected Digraphs","year":2015,"dataSources":["oEkRzPPMbrG9LyYPh"]}