Multi-agent Path Finding Based on Improved CBS Algorithm
摘要
Conflict-Based Search (CBS) is one of the most common algorithms to solve Multi-Agent Path Finding (MAPF). Previous studies introduced heuristics to guide the high-level search of CBS. The high-level of heuristic CBS selects node according to a single objective, which often leads to many alternative nodes and the selection of the final node is random. To solve this problem, an improved CBS algorithm based on multi-objective (CBS-MO) is proposed. Based on the heuristic CBS, the high-level of CBS-MO selects the final node from the alternative nodes according to the number of conflicts, so that the constraint tree (CT) can be expanded to the target node more quickly. To further improve efficiency, we propose a bounded suboptimal algorithm (SCBS), the high-level of SCBS selects the final node with fewer conflicts from more alternative nodes by relaxing the first objective. The experimental results show that the solving efficiency of CBS-MO is higher than comparison algorithms and the solution is optimal. SCBS is more efficient than CBS-MO, but the solution is not optimal. In addition, the solution cost and efficiency of SCBS are related to the value of relaxation factor.