核心发现
方法论
LaCAM采用双层搜索架构：高层搜索所有智能体的配置序列，低层搜索每个配置的约束条件。高层使用深度优先搜索，逐步扩展配置，低层利用宽度优先搜索生成最小约束集。通过惰性约束添加策略，有效减少搜索空间。算法结合PIBT等启发式配置生成方法，动态调整搜索顺序，确保完备性。实验中，LaCAM在多种复杂场景下表现优异，能在数秒内解决包含400个智能体的实例，且成功率高于或等于现有最优或次优算法。
关键结果
- 在MAPF基准测试中，LaCAM在解决含20%障碍的32×32网格上，成功解决所有400智能体实例，平均用时1秒，显著优于Silver、Standley等算法。其在大规模实例（如10000智能体）中表现出极佳的扩展性，平均解决时间不超过30秒。多场景下，LaCAM在成功率和时间效率方面优于EECBS、LNS2等主流方法，且解决方案的总成本（SOC）接近最优。
研究意义
该研究突破了大规模、多智能体路径规划的实时性瓶颈，为自动仓库、机器人集群调度等应用提供了强有力的技术支撑。通过引入惰性约束策略，显著降低了搜索复杂度，使得在数百甚至上千智能体的场景中实现高效规划成为可能。这不仅丰富了MAPF算法的理论体系，也推动了多机器人系统的实际部署，具有重要的学术价值和产业潜力。
技术贡献
LaCAM的核心创新在于其两层搜索框架结合惰性约束添加机制，保证了算法的完备性同时大幅提升搜索效率。算法利用深度优先搜索管理高层配置空间，宽度优先搜索在低层生成最小约束集，减少无效搜索路径。引入PIBT等启发式配置生成策略，动态调整搜索顺序，增强算法的适应性。理论上，LaCAM保证在可解实例中找到路径，且在复杂场景中表现出优异的扩展性，为MAPF提供了新的解决思路。
新颖性
LaCAM首次将惰性约束添加策略引入多智能体路径规划，结合双层搜索架构实现快速求解。其在保证完备性的基础上，通过惰性机制有效缩减搜索空间，突破了传统方法在大规模场景中的性能瓶颈。与CBS、EECBS等基于冲突检测的算法不同，LaCAM采用配置生成和惰性约束，有效提升了求解速度和规模适应性。
局限性
- 在狭窄通道或存在大量交换冲突的场景中，LaCAM的搜索效率明显下降，表现出对特定拓扑结构的敏感性。算法在极端密集或复杂障碍环境下，仍可能出现超时或次优解，特别是在高层搜索空间极大时。
- 惰性约束生成依赖启发式配置器，可能导致在某些实例中搜索路径偏离最优，影响解的质量。算法的随机性也可能引入结果不稳定性，需要进一步优化搜索策略。
- 在极大规模（如上万智能体）场景中，虽然表现出良好扩展性，但在硬件资源有限时仍存在性能瓶颈，未来需结合分布式或近似算法进行改进。
未来方向
未来将探索更智能的配置生成策略，结合学习方法优化启发式机制，提升在极端复杂环境中的表现。同时，考虑引入多目标优化，兼顾路径长度和能耗等指标。还计划将LaCAM扩展到动态环境和多目标场景，增强其实用性和鲁棒性。此外，结合分布式计算框架，实现大规模多机器人系统的实时调度，将是下一步的重要方向。
AI 总览摘要
多智能体路径规划（MAPF）是机器人、自动仓库等领域的核心问题，面对数百甚至上千智能体同时避障，传统算法在效率和规模上都面临巨大挑战。现有方法如CBS、EECBS等虽能保证最优或次优解，但在大规模场景中计算时间长、难以实时应用。为突破这一瓶颈，本文提出了LaCAM，一种基于搜索的快速多智能体路径规划算法。LaCAM采用双层搜索架构：高层探索所有智能体配置的序列，低层在每个配置中惰性生成约束，逐步逼近目标。该方法结合PIBT等启发式配置生成策略，有效减少搜索空间，保证算法完备性。实验结果显示，LaCAM在复杂场景中表现优异，能在几秒内解决含400个智能体的实例，成功率高于或等于现有最优算法，且具有极好的扩展性，能处理上万智能体。其创新点在于惰性约束策略与双层搜索的结合，为大规模、多智能体路径规划提供了新的解决思路。未来，研究将聚焦于优化配置生成、提升解的质量，以及在动态环境中的应用潜力。LaCAM的提出不仅丰富了MAPF理论体系，也为工业界实现高效、多机器人协作提供了技术基础。
深度解读
原文摘要
We propose a novel complete algorithm for multi-agent pathfinding (MAPF) called lazy constraints addition search for MAPF (LaCAM). MAPF is a problem of finding collision-free paths for multiple agents on graphs and is the foundation of multi-robot coordination. LaCAM uses a two-level search to find solutions quickly, even with hundreds of agents or more. At the low-level, it searches constraints about agents' locations. At the high-level, it searches a sequence of all agents' locations, following the constraints specified by the low-level. Our exhaustive experiments reveal that LaCAM is comparable to or outperforms state-of-the-art sub-optimal MAPF algorithms in a variety of scenarios, regarding success rate, planning time, and solution quality of sum-of-costs.