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

来源：计算机工程与应用杂志2025年第2期北京时间：

作者：鲁宇, 匡金骏, 肖峣, 龚建伟

单位：1.重庆长安望江工业集团有限公司，重庆 401120；2.北京理工大学 机械与车辆学院，北京 100081

摘要：在多智能体系统研究中，多智能体路径规划（multi-agent path finding，MAPF）是一个核心难题，其目标是为各个智能体规定独立路径，确保智能体在移动过程中不发生碰撞。这是一个NP难题，亟须高效解决算法。创新性地提出了一种多智能体路径规划算法——启发式导向冲突搜索（heuristic guided conflict-based search，HG-CBS），以解决复杂的MAPF场景，如智能体移动速度不同或各条边的道路长度不同。为优化HG-CBS算法，构建了三种独特的启发式计算方法：（1）加权求和法，以所有启发式的加权总和作为最终启发式；（2）帕累托集合法，构建一个帕累托集并从中选择节点；（3）交替法，在搜索迭代过程中交替使用各种启发式。实验结果显示，相比于传统方法，带有启发值的HG-CBS在成功率、运行时间及扩展节点数量等关键性能指标上均表现更优。例如，在包含16个智能体的复杂场景下，HG-CBS-h3（交替法）将运行时间缩短了89%，将拓展节点的数目减少了95%。此外，随着场景复杂度的提升，HG-CBS-h3的性能优势更加明显。这些结果证明了HG-CBS算法的有效性和高效性，对多智能体轨迹规划问题具有显著的理论和应用价值。

关键词：多智能体路径规划,启发式导向冲突搜索,启发式搜索,帕累托集