启发式搜索的多智能体异速轨迹规划

Multi-agent path finding (MAPF) is a core challenge in multi-agent systems research, aiming to assign independent 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 selecting nodes from it; (3) alternating method, alternating between various heuristics during search iterations. Experimental results 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 effectiveness and efficiency of the HG-CBS algorithm, highlighting its significant theoretical and practical implications for multi-agent trajectory planning.