基于冲突分类与消解的多智能体路径规划算法设计  

Design of a Multi-Agent Path Planning Algorithm Based on Conflict Classification and Resolution

作　　者：王东[1,2] 于连波 曹品钊 连捷 WANG Dong;YU Lian-bo;CAO Pin-zhao;LIAN Jie(Key Laboratory of Intelligent Control and Optimization for Industrial Equipment of Ministry of Education,Dalian University of Technology,Dalian 116024,China;School of Control Science and Engineering,Dalian University of Technology,Dalian 116024,China)

机构地区：[1]大连理工大学工业装备智能控制与优化教育部重点实验室,大连116024 [2]大连理工大学控制科学与工程学院,大连116024

出　　处：《导航定位与授时》2022年第5期56-66,共11页Navigation Positioning and Timing

基　　金：国家重点研发计划项目(2019YFE0197700);国家自然科学基金(61973050,62173061);辽宁省兴辽英才计划项目(XLYC2007010);中央高校基本科研业务费(DUT20GJ209,DUT20JC14)。

摘　　要：多智能体路径规划应用广泛但求解困难。为更好地处理多智能体路径规划中的路径冲突问题,提高求解效率,将冲突进一步分类为相向顶点冲突和交叉顶点冲突,并提出了对应的消解方式。相向顶点冲突的消解方法采用提前添加约束的方式,避免在消解其冲突的过程中产生另一个可预见的冲突;交叉顶点冲突的消解方法采用寻找最佳等待时间的方式,在消解其冲突的同时消解其他存在的冲突。两种冲突消解方法均可减小约束树的规模,在一定程度上减少算法的计算量。并提出了基于冲突搜索算法的高层节点冲突搜索算法。实验结果表明,所提出的冲突分类及消解方式有效地减小了算法高层中约束树的规模,降低了算法计算量,并在智能体密集的环境下表现出更大的优势。Multi-agent path planning is widely used, however, it is difficult to plan the paths of agents because of the existence of conflicts for these agents. In order to deal with the conflicts and improve the efficiency of the planning, the conflicts are further classified into the opposite vertex conflict and the intersect vertex conflict, and the corresponding resolution methods are proposed. The method of resolving the opposite vertex conflict adopts the method of adding constraints in advance to avoid another foreseeable conflict in the process of resolving its conflict. The method of resolving the intersect vertex conflict finds the best waiting time to resolve its conflict while resolving other existing conflicts. Both conflict resolution methods can reduce the size of the constraint tree and the computational complexity of the algorithm to a certain extent. An algorithm based on a conflict-based search algorithm to search for high-level node conflict is proposed. The experimental results show that the proposed conflict classification and resolution method can effectively reduce the size of the constraint tree in the high-level algorithm and the computational complexity of the algorithm, and shows advantages in the dense environment of agents.

关 键 词：多智能体路径规划 基于冲突搜索 路径冲突 冲突分类与消解 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置] V249[自动化与计算机技术—控制科学与工程]