{"_id":"SrHQesdMEHREiiBhj","bibbaseid":"cohen-koenig-kumar-wagner-choset-chan-sturtevant-rapidrandomizedrestartsformultiagentpathfindingpreliminaryresults-2018","authorIDs":[],"author_short":["Cohen, L.","Koenig, S.","Kumar, S.","Wagner, G.","Choset, H.","Chan, D.","Sturtevant, N."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["L."],"propositions":[],"lastnames":["Cohen"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Koenig"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Kumar"],"suffixes":[]},{"firstnames":["G."],"propositions":[],"lastnames":["Wagner"],"suffixes":[]},{"firstnames":["H."],"propositions":[],"lastnames":["Choset"],"suffixes":[]},{"firstnames":["D."],"propositions":[],"lastnames":["Chan"],"suffixes":[]},{"firstnames":["N."],"propositions":[],"lastnames":["Sturtevant"],"suffixes":[]}],"title":"Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results","booktitle":"Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)","year":"2018","pages":"1909–1911","pdf":"http://idm-lab.org/bib/abstracts/papers/aamas18a.pdf","flags":":2018:,:svenkoenig:,:lironcohen:,:satishkumar:,:howiechoset:,:glennwagner:","abstract":"Multi-Agent Path Finding (MAPF) is an NP-hard problem with many real-world applications. However, existing MAPF solvers are deterministic and perform poorly on MAPF instances where many agents interfere with each other in a small region of space. In this paper, we enhance MAPF solvers with randomization and observe that their runtimes can exhibit heavy-tailed distributions. This insight leads us to develop simple Rapid Randomized Restart (RRR) strategies with the intuition that multiple short runs will have a better chance of solving such MAPF instances than one long run with the same runtime limit. Our contribution is to show experimentally that the same RRR strategy indeed boosts the performance of two state-of-the-art MAPF solvers, namely M* and ECBS.","bibtex":"@INPROCEEDINGS{SKoen18k, \n AUTHOR= \"L. Cohen and S. Koenig and S. Kumar and G. Wagner and H. Choset and D. Chan and N. Sturtevant\",\n TITLE= \"Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results\",\n BOOKTITLE= \"Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)\",\n YEAR= \"2018\",\n PAGES= \"1909--1911\",\n PDF= \"http://idm-lab.org/bib/abstracts/papers/aamas18a.pdf\",\n FLAGS= \":2018:,:svenkoenig:,:lironcohen:,:satishkumar:,:howiechoset:,:glennwagner:\",\n ABSTRACT=\n\"Multi-Agent Path Finding (MAPF) is an NP-hard problem with many real-world\napplications. However, existing MAPF solvers are deterministic and perform\npoorly on MAPF instances where many agents interfere with each other in a\nsmall region of space. In this paper, we enhance MAPF solvers with\nrandomization and observe that their runtimes can exhibit heavy-tailed\ndistributions. This insight leads us to develop simple Rapid Randomized\nRestart (RRR) strategies with the intuition that multiple short runs will have\na better chance of solving such MAPF instances than one long run with the same\nruntime limit. Our contribution is to show experimentally that the same RRR\nstrategy indeed boosts the performance of two state-of-the-art MAPF solvers,\nnamely M* and ECBS.\"\n}\n\n","author_short":["Cohen, L.","Koenig, S.","Kumar, S.","Wagner, G.","Choset, H.","Chan, D.","Sturtevant, N."],"key":"SKoen18k","id":"SKoen18k","bibbaseid":"cohen-koenig-kumar-wagner-choset-chan-sturtevant-rapidrandomizedrestartsformultiagentpathfindingpreliminaryresults-2018","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://mapf.info/bib/mapf.bib","creationDate":"2019-05-05T18:02:17.681Z","downloads":0,"keywords":[],"search_terms":["rapid","randomized","restarts","multi","agent","path","finding","preliminary","results","cohen","koenig","kumar","wagner","choset","chan","sturtevant"],"title":"Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results","year":2018,"dataSources":["oEkRzPPMbrG9LyYPh"]}