基于动态冲突预测的多智体寻路算法  

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

作　　者：张萌希 韩建军[1] 肖彦 ZHANG Mengxi;HAN Jianjun and XIAO Yan(College of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China)

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机科学》2025年第4期21-32,共12页Computer Science

摘　　要：多智体寻路(MAPF)是为多个智能体寻找无冲突路径的问题,灵活显式估计的基于冲突搜索算法是目前解决MAPF问题最有效的有界次优算法之一,但该算法仍存在调用底层算法次数多、迭代中冲突数量减少速度慢等问题。为此,提出基于动态冲突预测的多智体寻路算法(DCPB-MAPF)。该算法分为两层,在底层提出基于关键区间的动态避障方法与基于路径成本预测的迭代方法,用以提升底层算法的运算效率;以此为基础,在顶层提出基于冲突预测的搜索算法,通过快速预测冲突数量以优化冲突选择技术,进一步提出冲突数量优先的启发式函数以加速减少冲突数量。实验结果表明,相比现有算法,所提算法能显著提升多智体寻路问题的运算效率及成功率。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.

关 键 词：多智体路径寻找 有界次优算法 启发式搜索 路径成本预测 冲突预测 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]