文献类型：会议论文

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

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

机构：[1] Beijing Key Laboratory of Information Service Engineering, Beijing Union University, Beijing, 100101, China; [2] College of Smart City, Beijing Union University, Beijing, 100101, China; [3] College of Robotics, Beijing Union University, Beijing, 100101, China

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

通讯机构：[2]College of Smart City, Beijing Union University, Beijing, 100101, China|[11417]北京联合大学;

会议论文集：Proceedings of 2023 11th China Conference on Command and Control

会议日期：October 24, 2023 - October 25, 2023

会议地点：Beijing, China

语种：英文

外文关键词：Electric circuit breakers - Graph theory - Many valued logics

摘要：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. ? Chinese Institute of Command and Control 2024.