Efficient Multi Agent Path Finding with Turn Actions

Current approaches for real-world Multi-Agent Path Finding (MAPF) usually start with a simplified MAPF model and modify the resulting plans so they are kinematically feasible. We investigate one such problem, called MAPF with turn actions MAPF_T, and show that ignoring the kinematic constraints significantly increases solution cost. A first modification of the popular Conflict-Based Search algorithm to MAPF_T yields significantly better plans but comes at the cost of substantial decreases in scalability. We then introduce several techniques that can improve the performance of CBS for MAPF_T, including stronger and generalised versions of existing symmetry-breaking constraints and a novel pruning technique that eliminates redundant branches in the CBS constraint tree. Experimental results on six popular MAPF domains show convincing improvements for CBS success rate and substantial reductions in node expansions and runtime.

Authors

• Yue Zhang 0048
• Daniel Harabor
• Pierre Le Bodic
• Peter J. Stuckey

Keywords

• Bounding And Pruning Techniques
• Constraint Search
• Symmetry Handling
• Search In Robotics