Branch-and-Cut-and-Price for Multi-Agent Pathfinding
Branch-and-Cut-and-Price for Multi-Agent Pathfinding
复制标题
DOI：
10.24963/ijcai.2019/179
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Edward Lam;P. L. Bodic;Daniel Damir Harabor;Peter James Stuckey
中科院分区：
文献类型：
--
作者：
Edward Lam;P. L. Bodic;Daniel Damir Harabor;Peter James Stuckey
目前有两种广泛的策略用于最佳多代理探路（MAPF）：（1）基于搜索的方法，它们可以直接建模和求解MAPF，以及（2）基于汇编的求解器，将MAPF降低为众所周知的组合实例问题，因此可以从求解器技术的进步中受益。在这项工作中，我们提出了一种最佳算法BCP，该算法使用分支和定价（用于数学优化开发的分解框架）杂交这两种方法。我们将BCP形式化并与CBSH和CBSH-RM（两个领先的基于搜索的求解器）进行了正式比较。标准基准的结论性结果表明，其性能超过了最新的：在较小的网格上求解更多实例，并可靠地扩展到较大的游戏地图上的100个或更多代理。
There are currently two broad strategies for optimal Multi-agent Pathfinding (MAPF): (1) search-based methods, which model and solve MAPF directly, and (2) compilation-based solvers, which reduce MAPF to instances of well-known combinatorial problems, and thus, can benefit from advances in solver techniques. In this work, we present an optimal algorithm, BCP, that hybridizes both approaches using Branch-and-Cut-and-Price, a decomposition framework developed for mathematical optimization. We formalize BCP and compare it empirically against CBSH and CBSH-RM, two leading search-based solvers. Conclusive results on standard benchmarks indicate that its performance exceeds the state-of-the-art: solving more instances on smaller grids and scaling reliably to 100 or more agents on larger game maps.