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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Multi-agent Path Finding Based on Improved CBS Algorithm

  • Yuhui Sun,
  • Shaoyun Xu,
  • Yang Wang,
  • Shu Zhang,
  • Yuexing Hao

摘要

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.