@INPROCEEDINGS{ABote09,
 AUTHOR= "C. Wang and A. Botea",
 TITLE= "Tractable Multi-Agent Path Planning on Grid Maps",
 BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
 YEAR= "2009",
 PAGES= "1870--1875",
 PDF= "http://users.rsise.anu.edu.au/~cwang/ijcai09-paper.pdf",
 FLAGS= ":2009:,:adibotea:,:cindywang:",
 ABSTRACT= 
"Multi-agent path planning on grid maps is a challenging problem and has
numerous real-life applications. Running a centralized, systematic search such
as A* is complete and cost-optimal but scales up poorly in practice, since
both the search space and the branching factor grow exponentially in the
number of mobile units. Decentralized approaches, which decompose a problem
into several subproblems, can be faster and can work for larger problems.
However, existing decentralized methods offer no guarantees with respect to
completeness, running time, and solution quality. To address such limitations,
we introduce MAPP, a tractable algorithm for multi-agent path planning on grid
maps. We show that MAPP has low-polynomial worst-case upper bounds for the
running time, the memory requirements, and the length of solutions. As it runs
in low-polynomial time, MAPP is incomplete in the general case. We identify a
class of problems for which our algorithm is complete. We believe that this is
the first study that formalises restrictions to obtain a tractable class of
multi-agent path planning problems."
}

{"_id":"hGAZiopPZ3oTsbNQH","bibbaseid":"wang-botea-tractablemultiagentpathplanningongridmaps-2009","authorIDs":[],"author_short":["Wang, C.","Botea, A."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["C."],"propositions":[],"lastnames":["Wang"],"suffixes":[]},{"firstnames":["A."],"propositions":[],"lastnames":["Botea"],"suffixes":[]}],"title":"Tractable Multi-Agent Path Planning on Grid Maps","booktitle":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)","year":"2009","pages":"1870–1875","pdf":"http://users.rsise.anu.edu.au/~cwang/ijcai09-paper.pdf","flags":":2009:,:adibotea:,:cindywang:","abstract":"Multi-agent path planning on grid maps is a challenging problem and has numerous real-life applications. Running a centralized, systematic search such as A* is complete and cost-optimal but scales up poorly in practice, since both the search space and the branching factor grow exponentially in the number of mobile units. Decentralized approaches, which decompose a problem into several subproblems, can be faster and can work for larger problems. However, existing decentralized methods offer no guarantees with respect to completeness, running time, and solution quality. To address such limitations, we introduce MAPP, a tractable algorithm for multi-agent path planning on grid maps. We show that MAPP has low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. As it runs in low-polynomial time, MAPP is incomplete in the general case. We identify a class of problems for which our algorithm is complete. We believe that this is the first study that formalises restrictions to obtain a tractable class of multi-agent path planning problems.","bibtex":"@INPROCEEDINGS{ABote09,\n AUTHOR= \"C. Wang and A. Botea\",\n TITLE= \"Tractable Multi-Agent Path Planning on Grid Maps\",\n BOOKTITLE= \"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)\",\n YEAR= \"2009\",\n PAGES= \"1870--1875\",\n PDF= \"http://users.rsise.anu.edu.au/~cwang/ijcai09-paper.pdf\",\n FLAGS= \":2009:,:adibotea:,:cindywang:\",\n ABSTRACT= \n\"Multi-agent path planning on grid maps is a challenging problem and has\nnumerous real-life applications. Running a centralized, systematic search such\nas A* is complete and cost-optimal but scales up poorly in practice, since\nboth the search space and the branching factor grow exponentially in the\nnumber of mobile units. Decentralized approaches, which decompose a problem\ninto several subproblems, can be faster and can work for larger problems.\nHowever, existing decentralized methods offer no guarantees with respect to\ncompleteness, running time, and solution quality. To address such limitations,\nwe introduce MAPP, a tractable algorithm for multi-agent path planning on grid\nmaps. We show that MAPP has low-polynomial worst-case upper bounds for the\nrunning time, the memory requirements, and the length of solutions. As it runs\nin low-polynomial time, MAPP is incomplete in the general case. We identify a\nclass of problems for which our algorithm is complete. We believe that this is\nthe first study that formalises restrictions to obtain a tractable class of\nmulti-agent path planning problems.\"\n}\n\n","author_short":["Wang, C.","Botea, A."],"key":"ABote09","id":"ABote09","bibbaseid":"wang-botea-tractablemultiagentpathplanningongridmaps-2009","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://mapf.info/bib/mapf.bib","creationDate":"2019-05-05T18:02:17.741Z","downloads":0,"keywords":[],"search_terms":["tractable","multi","agent","path","planning","grid","maps","wang","botea"],"title":"Tractable Multi-Agent Path Planning on Grid Maps","year":2009,"dataSources":["oEkRzPPMbrG9LyYPh"]}