ICBS: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding

ICBS: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding. Boyarski, E., Felner, A., Stern, R., Sharon, G., Betzalel, O., Tolpin, D., & Shimony, E. In Proceedings of the Symposium on Combinatorial Search (SoCS), pages 223–225, 2015.
abstract bibtex

Conflict-Based Search (CBS) and its enhancements, Meta-Agent CBS and bypassing conflicts are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces two new improvements to CBS and incorporates them into a coherent, improved version of CBS, namely ICBS. Experimental results show that each of these improvements further reduces the runtime over the existing CBS-based approaches. When all improvements are combined, an even larger improvement is achieved, producing state-of-the art results for a number of domains.

@INPROCEEDINGS{AFeln15c, 
 AUTHOR= "E. Boyarski and A. Felner and R. Stern and G. Sharon and O. Betzalel and D. Tolpin and E. Shimony",
 TITLE= "{ICBS}: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding",
 BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)",
 PAGES= "223--225",
 YEAR= "2015",
 PDF= "https://docs.wixstatic.com/ugd/749b4b_0b1d4e2537f24f44b5b3e210b10dccbc.pdf",
 FLAGS= ":eliboyarski:,:arielfelner:,:ronistern:,:gunisharon:",
 ABSTRACT= 
"Conflict-Based Search (CBS) and its enhancements, Meta-Agent CBS and bypassing
conflicts are amongst the strongest newly introduced algorithms for
Multi-Agent Path Finding. This paper introduces two new improvements to CBS
and incorporates them into a coherent, improved version of CBS, namely
ICBS. Experimental results show that each of these improvements further
reduces the runtime over the existing CBS-based approaches. When all
improvements are combined, an even larger improvement is achieved, producing
state-of-the art results for a number of domains."
}

Downloads: 0

{"_id":"7xtZyufKYHF29gDjv","bibbaseid":"boyarski-felner-stern-sharon-betzalel-tolpin-shimony-icbstheimprovedconflictbasedsearchalgorithmformultiagentpathfinding-2015","authorIDs":[],"author_short":["Boyarski, E.","Felner, A.","Stern, R.","Sharon, G.","Betzalel, O.","Tolpin, D.","Shimony, E."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["E."],"propositions":[],"lastnames":["Boyarski"],"suffixes":[]},{"firstnames":["A."],"propositions":[],"lastnames":["Felner"],"suffixes":[]},{"firstnames":["R."],"propositions":[],"lastnames":["Stern"],"suffixes":[]},{"firstnames":["G."],"propositions":[],"lastnames":["Sharon"],"suffixes":[]},{"firstnames":["O."],"propositions":[],"lastnames":["Betzalel"],"suffixes":[]},{"firstnames":["D."],"propositions":[],"lastnames":["Tolpin"],"suffixes":[]},{"firstnames":["E."],"propositions":[],"lastnames":["Shimony"],"suffixes":[]}],"title":"ICBS: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding","booktitle":"Proceedings of the Symposium on Combinatorial Search (SoCS)","pages":"223–225","year":"2015","pdf":"https://docs.wixstatic.com/ugd/749b4b_0b1d4e2537f24f44b5b3e210b10dccbc.pdf","flags":":eliboyarski:,:arielfelner:,:ronistern:,:gunisharon:","abstract":"Conflict-Based Search (CBS) and its enhancements, Meta-Agent CBS and bypassing conflicts are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces two new improvements to CBS and incorporates them into a coherent, improved version of CBS, namely ICBS. Experimental results show that each of these improvements further reduces the runtime over the existing CBS-based approaches. When all improvements are combined, an even larger improvement is achieved, producing state-of-the art results for a number of domains.","bibtex":"@INPROCEEDINGS{AFeln15c, \n AUTHOR= \"E. Boyarski and A. Felner and R. Stern and G. Sharon and O. Betzalel and D. Tolpin and E. Shimony\",\n TITLE= \"{ICBS}: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding\",\n BOOKTITLE= \"Proceedings of the Symposium on Combinatorial Search (SoCS)\",\n PAGES= \"223--225\",\n YEAR= \"2015\",\n PDF= \"https://docs.wixstatic.com/ugd/749b4b_0b1d4e2537f24f44b5b3e210b10dccbc.pdf\",\n FLAGS= \":eliboyarski:,:arielfelner:,:ronistern:,:gunisharon:\",\n ABSTRACT= \n\"Conflict-Based Search (CBS) and its enhancements, Meta-Agent CBS and bypassing\nconflicts are amongst the strongest newly introduced algorithms for\nMulti-Agent Path Finding. This paper introduces two new improvements to CBS\nand incorporates them into a coherent, improved version of CBS, namely\nICBS. Experimental results show that each of these improvements further\nreduces the runtime over the existing CBS-based approaches. When all\nimprovements are combined, an even larger improvement is achieved, producing\nstate-of-the art results for a number of domains.\"\n}\n\n","author_short":["Boyarski, E.","Felner, A.","Stern, R.","Sharon, G.","Betzalel, O.","Tolpin, D.","Shimony, E."],"key":"AFeln15c","id":"AFeln15c","bibbaseid":"boyarski-felner-stern-sharon-betzalel-tolpin-shimony-icbstheimprovedconflictbasedsearchalgorithmformultiagentpathfinding-2015","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://mapf.info/bib/mapf.bib","creationDate":"2019-05-05T18:02:17.699Z","downloads":0,"keywords":[],"search_terms":["icbs","improved","conflict","based","search","algorithm","multi","agent","pathfinding","boyarski","felner","stern","sharon","betzalel","tolpin","shimony"],"title":"ICBS: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding","year":2015,"dataSources":["oEkRzPPMbrG9LyYPh"]}