基于冲突搜索的多智能体路径规划研究进展  

Research Progress of Multi-agent Path Finding Based on Conflict-based Search Algorithms

作　　者：王子晗 童向荣 WANG Zihan;TONG Xiangrong(School of Computer and Control Engineering,Yantai University,Yantai,Shandong 264005,China)

机构地区：[1]烟台大学计算机与控制工程学院,山东烟台264005

出　　处：《计算机科学》2023年第6期358-368,共11页Computer Science

基　　金：国家自然科学基金(62072392,61972360);山东省重大科技创新工程项目(2019522Y020131);烟台市重点实验室:高端海洋工程装备智能技术。

摘　　要：多智能体路径规划是人工智能领域一个经典的搜索问题,基于冲突的搜索算法是当前解决该问题的最优算法之一。文中讨论了多智能体路径规划的基础研究,对国内外近年来基于冲突搜索算法及其变体的研究成果进行了分类,根据改进方式将其变体分为4类,包括分割策略的改进、启发式算法、对典型冲突的处理和次优算法。同时介绍了基于冲突的搜索算法在多智能体路径规划的扩展问题中的应用。最后根据当前算法的优缺点,指出了目前面临的挑战,并针对这些挑战给出了未来可能的研究方向。Multi-agent path finding is a classic search problem in the field of artificial intelligence.Conflict-based search algorithm is one of the best algorithms to solve this problem.This paper discusses the basic research of multi-agent path finding,and classifies the research results based on conflict search algorithms and their variants in recent years.According to the improved ways,the variants are divided into four categories,including segmentation strategy improvement,heuristic algorithm,bounded suboptimal algorithm and typical conflict processing.It also introduces the application of the conflict-based search algorithm to the extended problem of multi-agent path finding.Finally,according to the advantages and disadvantages of the current algorithm,the existing challenges are pointed out.In view of these challenges,the possible research directions in the future are given.

关 键 词：人工智能 多智能体路径规划 基于冲突的搜索算法 启发式搜索算法 A*算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]