Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search
Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search
复制标题
基于冲突搜索的多代理路径查找的不相交分裂
DOI：
10.1609/icaps.v29i1.3487
复制
发表时间：
2019
影响因子：
5.2
通讯作者：
Sven Koenig
中科院分区：
文献类型：
--
作者：
Jiaoyang Li;Daniel Damir Harabor;Peter James Stuckey;Hang Ma;Sven Koenig
多代理路径查找（MAPF）是为代理团队寻找无碰撞路径的计划问题。我们专注于基于冲突的搜索（CBS），这是一种两级树搜索最新的MAPF算法。 CBS使用的标准分裂策略不是不相交的，即，当问题将问题分成两个子问题时，两种解决方案都会由两个子问题共享，这可以创建搜索工作的重复。在本文中，我们演示了如何通过分裂的分裂来改善CBS以及如何修改CBS的低级搜索以获得最大优势。实验表明，分裂的分裂可将CBS及其变体的成功率和速度提高2个数量级。
Multi-Agent Path Finding (MAPF) is the planning problem of finding collision-free paths for a team of agents. We focus on Conflict-Based Search (CBS), a two-level tree-search state-of-the-art MAPF algorithm. The standard splitting strategy used by CBS is not disjoint, i.e., when it splits a problem into two subproblems, some solutions are shared by both subproblems, which can create duplication of search effort. In this paper, we demonstrate how to improve CBS with disjoint splitting and how to modify the low-level search of CBS to take maximal advantage of it. Experiments show that disjoint splitting increases the success rates and speeds of CBS and its variants by up to 2 orders of magnitude.