论文标题
LACAM：基于搜索的算法，用于快速多代理探路
LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding
论文作者
论文摘要
我们提出了一种用于多代理探路（MAPF）的新颖的完整算法，称为懒惰约束搜索MAPF（LACAM）。 MAPF是在图上找到多种代理的无碰撞路径的问题，并且是多机器人协调的基础。 Lacam使用两级搜索来快速找到解决方案，即使有数百个代理或更多代理。在低级时，它搜索了有关代理位置的约束。在高水平上，它按照低级指定的约束来搜索所有代理位置的序列。我们详尽的实验表明，与各种情况相比，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.
