基于互斥锁传播的多智能体路径规划算法  

Multi-Agent Pathfinding Algorithm Based on Mutex Propagation

作　　者：岳荣康 丁行 江海 龙吟 YUE Rongkang;DING Hang;JIANG Hai;LONG Yin(School of Computer Science and Technology,Southwest University of Science and Technology,Mianyang 621000,Sichuan,China;Sichuan Provincial Tobacco Companies Chengdu Company,Chengdu 610014,China)

机构地区：[1]西南科技大学计算机科学与技术学院,四川绵阳621000 [2]四川省烟草公司成都市公司,成都610014

出　　处：《计算机工程》2023年第12期103-110,120,共9页Computer Engineering

基　　金：国家自然科学基金(62101467)。

摘　　要：基于冲突的搜索(CBS)算法可以应用于连续时间假设下的多智能体路径规划问题,但是仍存在没有相应冲突识别方法与约束生成规则的问题,从而导致算法效率低下。为此,引入并改进人工智能规划领域中的互斥锁传播技术进行路径规划。首先通过多值决策图(MDD)中的终点可达信息判断冲突的基本类型,然后讨论不同MDD的深度,将冲突划分为基数冲突或非基数冲突,最后针对不同类型的冲突直接生成对应的约束集合,使得CBS下层算法根据约束集合一次性规划出最优路径。互斥锁传播技术提供了比特殊规则更加通用的方法,不仅可以识别出离散时间下的矩形冲突、廊道冲突等特殊基数冲突,还可以针对连续时间的情景,将识别出的基数冲突进行分类并自动生成不同冲突类别对应的约束集合。实验结果表明,使用互斥锁传播的CCBS算法相较于CBS框架下的前沿算法平均成功率提升了6.2%,平均运行时间缩短了38.6%,相较于非CBS框架下的前沿算法平均成功率提升了15.3%,平均运行时间缩短了56.8%。The Conflict-Based Search(CBS)algorithm can be applied to Multi-Agent Pathfinding(MAPF)problems under continuous-time assumptions.However,there is a lack of corresponding conflict recognition methods and constraint generation rules,resulting in low algorithm efficiency.To address this problem,this study introduces and improves the mutex propagation technology in the field of artificial-intelligence planning for pathfinding.First,the basic types of conflicts are determined based on the reachability information of endpoints in a Multi-valued Decision Diagram(MDD).Then,the depths of different MDDs are discussed,and conflicts are divided into cardinal conflicts or non-cardinal conflicts.Finally,corresponding constraint sets are directly generated for different types of conflicts,allowing the lower-level CBS algorithm to plan the optimal path at once based on the constraint sets.Mutex propagation technology provides a more general method than special rules,which can not only identify special cardinality conflicts,such as rectangular conflicts and corridor conflicts,in discrete time but also classify the identified cardinality conflicts for continuous-time scenarios and automatically generate constraint sets corresponding to different conflict categories.The experimental results show that the CCBS algorithm that uses mutex propagation has an average success rate improvement of 6.2%and average running time reduction of 38.6%compared with cutting-edge algorithms under the CBS framework.Compared with cutting-edge algorithms under non-CBS frameworks,the CCBS algorithm has an average success rate improvement of 15.3%and average running time reduction of 56.8%.

关 键 词：人工智能规划 互斥锁传播 连续时间 多智能体路径规划 多值决策图 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]