Dynamic Conflict-Prediction Based Algorithm for Multi-agent Path Finding

Multi-agent path finding(MAPF) is the problem of searching for collision-free paths for a group of agents.Currently,flexible explicit estimation conflict-based search algorithm(FEECBS) is deemed as one of the most effective bounded suboptimal algorithms to solve the MAPF problem,but it has several disadvantages concerning the frequent invocation of the low-level algorithm and slow reduction in the number of conflicts during iterations.To address such issues,This paper proposes a dynamic conflict-prediction based algorithm for multi-agent path finding(DCPB-MAPF).The DCPB-MAPF algorithm operates on a two-layer framework.On the low level,it investigates an optimized dynamic obstacle avoidance method based on critical intervals and a new iterative method based on path cost prediction for improving its efficiency.On the high level,it develops a conflict-prediction based search method together with the low-level algorithm.Firstly,the conflict selection technique is improved by quickly predicting the number of potential collisions.Further,a new method is proposed to accelerate reducing the number of conflicts by constructing a heuristic function.The extensively empirical experiment results demonstrate that DCPB-MAPF can effectively improve both efficiency and success rate on MAPF instances when compared to the existing algorithms.