文献类型：会议论文

英文题名：Multi-agent Path Finding with Map Preprocessing

作者：Chen, Ming[1];He, Ning[2];Hong, Chen[1,3];Wang, Qi[1];Xiao, Ming-Ming

通讯作者：He, N[1]

机构：[1]Beijing Union Univ, Beijing Key Lab Informat Serv Engn, Beijing 100101, Peoples R China;[2]Beijing Union Univ, Coll Smart City, Beijing 100101, Peoples R China;[3]Beijing Union Univ, Coll Robot, Beijing 100101, Peoples R China

第一机构：北京联合大学北京市信息服务工程重点实验室

通讯机构：[1]corresponding author), Beijing Union Univ, Coll Smart City, Beijing 100101, Peoples R China.|[11417]北京联合大学;

会议论文集：11th China Conference on Command and Control-C2 CHINA

会议日期：OCT 24-25, 2023

会议地点：Beijing, PEOPLES R CHINA

语种：英文

外文关键词：Multi-agent path finding; Map preprocessing; Conflict-based search

摘要：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.