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.
multi-agent path findingheuristic guided conflict-based searchheuristic searchPareto set
万方数据
维普
