通过分层分解大模型机器人路径规划问题，提速降耗且不丢解。
Layered LA-MAPF: a decomposition of large agent MAPF instance to accelerate solving without compromising solvability
- 将大尺寸机器人路径问题拆分为簇和层级，降低冲突检测开销。
- 在60秒内求解成功率从27%提升至80%，平均耗时由40秒降至20秒。
- 适合需高效处理多大尺寸机器人协同路径的智能系统研究者。
多智能体路径规划（MAPF）近年受到广泛关注，但多数算法假设智能体仅占据单个网格，难以应对具有几何形状的真实场景。此类占据多个单元的智能体称为‘大智能体’，其存在显著增加冲突检测复杂度，尤其当智能体数量增多时。本文提出两类子问题：无顺序约束的‘簇’与有顺序要求的‘层级’，并引入分层大智能体路径规划（Layered LA-MAPF）方法，将大规模实例先分解为簇，再对每簇进一步分层。该策略有效降低求解时间复杂度。实验表明，在多种地图下随智能体数增长，本方法显著加速了LA-CBS与LA-LaCAM等算法。在60秒时限内，求解成功率从平均0.27提升至0.80，平均耗时由40秒减少至20秒。源码已开源，便于后续研究。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) has been widely studied in recent years. However, most existing MAPF algorithms assume that an agent occupies only a single grid in a grid-based map. This assumption limits their applicability in many real-world domains where agents have geometric shapes, rather than being point-like. Such agents, which can occupy multiple cells simultaneously, are referred to as ``large'' agents. When considering the shape and size of agents in MAPF, the computational complexity increases significantly as the number of agents grows, primarily due to the increased overhead in conflict detection between geometric agents. In this paper, we propose two types of subproblems for the LA-MAPF (Large-Agent MAPF) problem: \textbf{cluster} (which has no constraints on the order of solution) and \textbf{level} (which imposes constraints on the solution order). We introduce \textbf{Layered LA-MAPF}, a method that decomposes a MAPF instance involving geometric agents into clusters, and then further decomposes each cluster into levels. This approach aims to reduce time complexity when solving LA-MAPF problems. Our results demonstrate the performance of our method as the number of agents increases across various maps, and how it accelerates LA-MAPF methods, such as LA-CBS and LA-LaCAM. Experiments show that our LA-MAPF method with instance decomposition \textbf{halves the time cost (reducing from an average of 40s to 20s) and triples the success rate (from an average of 0.27 to 0.80)} in finding a solution within 60 seconds. To facilitate further research, we have made the source code for Layered LA-MAPF publicly available at \url{https://github.com/JoeYao-bit/LayeredMAPF/algorithm/LA-MAPF}.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。