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

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

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

Key words:  Multi-agent path planning  Conflict-based search  Path conflict  Conflict classification and resolution

摘要:

多智能体路径规划应用广泛但求解困难。为更好地处理多智能体路径规划中的路径冲突问题，提高求解效率，将冲突进一步分类为相向顶点冲突和交叉顶点冲突，并提出了对应的消解方式。相向顶点冲突的消解方法采用提前添加约束的方式，避免在消解其冲突的过程中产生另一个可预见的冲突；交叉顶点冲突的消解方法采用寻找最佳等待时间的方式，在消解其冲突的同时消解其他存在的冲突。两种冲突消解方法均可减小约束树的规模，在一定程度上减少算法的计算量。并提出了基于冲突搜索算法的高层节点冲突搜索算法。实验结果表明，所提出的冲突分类及消解方式有效地减小了算法高层中约束树的规模，降低了算法计算量，并在智能体密集的环境下表现出更大的优势。

Abstract:

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.