Multi-agent path finding(MAPF)is a core challenge in multi-agent systems research,aiming to assign indepen-dent paths to each agent to avoid collisions during movement.As an NP-hard problem,it is highly sought after to develop efficient algorithms.This paper proposes an innovative multi-agent path planning algorithm called heuristic guided conflict-based search(HG-CBS),designed to address complex MAPF scenarios such as heterogeneous agent speeds and varying edge lengths.To optimize HG-CBS,the paper develops three unique heuristic computation methods:(1)weighted sum method,using the weighted sum of all heuristics as the final heuristic;(2)Pareto set method,constructing a Pareto set and select-ing nodes from it;(3)alternating method,alternating between various heuristics during search iterations.Experimental re-sults demonstrate that HG-CBS with heuristics outperforms conventional methods in terms of success rate,runtime,and number of expanded nodes.For instance,in a complex scenario with 16 agents,HG-CBS-h3(alternating method)reduces the runtime by 89%and the number of expanded nodes by 95%.Moreover,the performance advantage of HG-CBS-h3 becomes even more prominent as the complexity of the scenario increases.These findings validate the effec-tiveness and efficiency of the HG-CBS algorithm,highlighting its significant theoretical and practical implications for multi-agent trajectory planning.
关键词
多智能体路径规划/启发式导向冲突搜索/启发式搜索/帕累托集
Key words
multi-agent path finding/heuristic guided conflict-based search/heuristic search/Pareto set
维普
万方数据