Rapid Randomized Restarts for Multi-Agent Path Finding Solvers

Rapid Randomized Restarts for Multi-Agent Path Finding Solvers. Cohen, L., Wagner, G., Chan, D., Choset, H., Sturtevant, N., Koenig, S., & Kumar, S. In Proceedings of the Symposium on Combinatorial Search (SoCS), pages 148–152, 2018.
abstract bibtex

Multi-Agent Path Finding (MAPF) is an NP-hard problem that has been well studied in artificial intelligence and robotics. Recently, randomized MAPF solvers have been shown to exhibit heavy-tailed distributions of runtimes, which can be exploited to boost their success rates for given runtime limits. In this paper, we discuss different ways of randomizing MAPF solvers and evaluate simple rapid randomized restart strategies for state-of-the-art MAPF solvers such as iECBS, M* and CBS-CL.Comment: We did not get the polished version of the paper (shown here) submitted in time and thus they published an intermediate version with the same experimental results but less polished text.

@INPROCEEDINGS{SKoen18w,
 AUTHOR= "L. Cohen and G. Wagner and D. Chan and H. Choset and N. Sturtevant and S. Koenig and S. Kumar",
 TITLE= "Rapid Randomized Restarts for Multi-Agent Path Finding Solvers",
 BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)",
 YEAR= "2018",
 PAGES= "148--152",
 PDF= "http://idm-lab.org/bib/abstracts/papers/socs18c-good.pdf",
 XLAGS= ":2018:,:lironcohen:,:satishkumar:,:howiechoset:,:glennwagner:",
 ABSTRACT=
"Multi-Agent Path Finding (MAPF) is an NP-hard problem that has been well
studied in artificial intelligence and robotics. Recently, randomized MAPF
solvers have been shown to exhibit heavy-tailed distributions of runtimes,
which can be exploited to boost their success rates for given runtime
limits. In this paper, we discuss different ways of randomizing MAPF solvers
and evaluate simple rapid randomized restart strategies for state-of-the-art
MAPF solvers such as iECBS, M* and CBS-CL.<b>Comment:</b> We did not get the
polished version of the paper (shown here) submitted in time and thus they
published an intermediate version with the same experimental results but
less polished text."
}

Downloads: 0

{"_id":"MnJse9eWMX4KAi8yg","bibbaseid":"cohen-wagner-chan-choset-sturtevant-koenig-kumar-rapidrandomizedrestartsformultiagentpathfindingsolvers-2018","authorIDs":[],"author_short":["Cohen, L.","Wagner, G.","Chan, D.","Choset, H.","Sturtevant, N.","Koenig, S.","Kumar, S."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["L."],"propositions":[],"lastnames":["Cohen"],"suffixes":[]},{"firstnames":["G."],"propositions":[],"lastnames":["Wagner"],"suffixes":[]},{"firstnames":["D."],"propositions":[],"lastnames":["Chan"],"suffixes":[]},{"firstnames":["H."],"propositions":[],"lastnames":["Choset"],"suffixes":[]},{"firstnames":["N."],"propositions":[],"lastnames":["Sturtevant"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Koenig"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Kumar"],"suffixes":[]}],"title":"Rapid Randomized Restarts for Multi-Agent Path Finding Solvers","booktitle":"Proceedings of the Symposium on Combinatorial Search (SoCS)","year":"2018","pages":"148–152","pdf":"http://idm-lab.org/bib/abstracts/papers/socs18c-good.pdf","xlags":":2018:,:lironcohen:,:satishkumar:,:howiechoset:,:glennwagner:","abstract":"Multi-Agent Path Finding (MAPF) is an NP-hard problem that has been well studied in artificial intelligence and robotics. Recently, randomized MAPF solvers have been shown to exhibit heavy-tailed distributions of runtimes, which can be exploited to boost their success rates for given runtime limits. In this paper, we discuss different ways of randomizing MAPF solvers and evaluate simple rapid randomized restart strategies for state-of-the-art MAPF solvers such as iECBS, M* and CBS-CL.<b>Comment:</b> We did not get the polished version of the paper (shown here) submitted in time and thus they published an intermediate version with the same experimental results but less polished text.","bibtex":"@INPROCEEDINGS{SKoen18w,\n AUTHOR= \"L. Cohen and G. Wagner and D. Chan and H. Choset and N. Sturtevant and S. Koenig and S. Kumar\",\n TITLE= \"Rapid Randomized Restarts for Multi-Agent Path Finding Solvers\",\n BOOKTITLE= \"Proceedings of the Symposium on Combinatorial Search (SoCS)\",\n YEAR= \"2018\",\n PAGES= \"148--152\",\n PDF= \"http://idm-lab.org/bib/abstracts/papers/socs18c-good.pdf\",\n XLAGS= \":2018:,:lironcohen:,:satishkumar:,:howiechoset:,:glennwagner:\",\n ABSTRACT=\n\"Multi-Agent Path Finding (MAPF) is an NP-hard problem that has been well\nstudied in artificial intelligence and robotics. Recently, randomized MAPF\nsolvers have been shown to exhibit heavy-tailed distributions of runtimes,\nwhich can be exploited to boost their success rates for given runtime\nlimits. In this paper, we discuss different ways of randomizing MAPF solvers\nand evaluate simple rapid randomized restart strategies for state-of-the-art\nMAPF solvers such as iECBS, M* and CBS-CL.<b>Comment:</b> We did not get the\npolished version of the paper (shown here) submitted in time and thus they\npublished an intermediate version with the same experimental results but\nless polished text.\"\n}\n\n","author_short":["Cohen, L.","Wagner, G.","Chan, D.","Choset, H.","Sturtevant, N.","Koenig, S.","Kumar, S."],"key":"SKoen18w","id":"SKoen18w","bibbaseid":"cohen-wagner-chan-choset-sturtevant-koenig-kumar-rapidrandomizedrestartsformultiagentpathfindingsolvers-2018","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://mapf.info/bib/mapf.bib","creationDate":"2019-05-05T18:02:17.680Z","downloads":0,"keywords":[],"search_terms":["rapid","randomized","restarts","multi","agent","path","finding","solvers","cohen","wagner","chan","choset","sturtevant","koenig","kumar"],"title":"Rapid Randomized Restarts for Multi-Agent Path Finding Solvers","year":2018,"dataSources":["oEkRzPPMbrG9LyYPh"]}