LLM2D
分层LA-MAPF:一种大型Agent多智能体路径规划问题实例的分解方法,用于加速求解且不影响可解性
Layered LA-MAPF: a decomposition of large agent MAPF instance to accelerate solving without compromising solvability
作者: Zhuo Yao
发布日期: 10/23/2024
arXiv ID: oai:arXiv.org:2410.17160v1

摘要

近年来,多智能体路径规划 (MAPF) 问题得到了广泛的研究。然而,大多数现有的 MAPF 算法假设智能体仅占据网格地图中的单个网格。这一假设限制了它们在许多现实世界领域的应用,因为在这些领域中,智能体具有几何形状,而不是点状的。这种可以同时占据多个单元格的智能体被称为“大型”智能体。当在 MAPF 中考虑智能体的形状和大小时,随着智能体数量的增加,计算复杂度会显著增加,这主要是由于几何智能体之间冲突检测的开销增加。在本文中,我们针对大型智能体多智能体路径规划 (LA-MAPF) 问题提出了两种子问题:\textbf{集群}(对解的顺序没有约束)和\textbf{层次}(对解的顺序施加约束)。我们介绍了\textbf{分层 LA-MAPF} 方法,该方法将涉及几何智能体的 MAPF 实例分解为集群,然后将每个集群进一步分解为层次。这种方法旨在降低求解 LA-MAPF 问题的时间复杂度。我们的结果证明了该方法在不同地图上随着智能体数量增加时的性能,以及它如何加速 LA-MAPF 方法,例如 LA-CBS 和 LA-LaCAM。实验表明,我们的具有实例分解的 LA-MAPF 方法\textbf{将求解时间成本降低了一半(从平均 40 秒减少到 20 秒),并将成功率提高了两倍(从平均 0.27 提高到 0.80)},在 60 秒内找到解。为了促进进一步的研究,我们已将分层 LA-MAPF 的源代码公开发布在 \url{https://github.com/JoeYao-bit/LayeredMAPF/algorithm/LA-MAPF}。