Don't Split, Try To Work It Out: Bypassing Conflicts in Multi-Agent Pathfinding. Boyarski, E., Felner, A., Sharon, G., & Stern, R. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pages 47–51, 2015.
abstract   bibtex   
Conflict-Based Search (CBS) is a recently introduced algorithm for Multi-Agent Path Finding (MAPF) whose runtime is exponential in the number of conflicts found between the agents’ paths. We present an improved version of CBS that bypasses conflicts thereby reducing the CBS search tree. Experimental results show that this improvement reduces the runtime by an order of magnitude in many cases.
@INPROCEEDINGS{AFeln15b, 
 AUTHOR= "E. Boyarski and A. Felner and G. Sharon and R. Stern",
 TITLE= "Don't Split, Try To Work It Out: Bypassing Conflicts in Multi-Agent Pathfinding",
 BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
 PAGES= "47--51",
 YEAR= "2015",
 PDF= "https://docs.wixstatic.com/ugd/749b4b_6c85984d14ff4379b3a4400aab955b7b.pdf",
 FLAGS= ":2015:,:eliboyarski:,:arielfelner:,:gunisharon:,:ronistern:",
 ABSTRACT= 
"Conflict-Based Search (CBS) is a recently introduced algorithm for
Multi-Agent Path Finding (MAPF) whose runtime is exponential in the number of
conflicts found between the agents’ paths. We present an improved version of
CBS that bypasses conflicts thereby reducing the CBS search tree. Experimental
results show that this improvement reduces the runtime by an order of
magnitude in many cases."
}

Downloads: 0