Multi-agent Path Finding with Map Preprocessing

When the Conflict-Based Search (CBS) algorithm is applied to solve the Multi-Agent Path Finding (MAPF) problem, the low-level search of the CBS framework can reduce the number of nodes explored in the path search by calling space-time A*, but the time costs for each agent to dynamically perceive the map increase fast with the number of agents. To solve this problem, we preprocess the map to obtain the shortest path costs from any vertex to other vertices in the map; when solving the MAPF problem, the calculated shortest path costs are loaded and acts as the heuristic of space-time A*; by taking advantage of the incremental value of the shortest path costs, Multi-Valued Decision Diagram (MDD) can be constructed conveniently to optimize the classification of the conflicts. Experiments on the MAPF benchmark maps show that CBS with map preprocessing outperforms the current state-of-the-art solver CBSH2-RTC algorithm with respect to runtime.