Conflict-Based Search (CBS) is a state-of-the-art algorithm for multi-agent path finding. At the high level, CBS repeatedly detects conflicts and resolves one of them by splitting the current problem into two subproblems. Previous work chooses the conflict to resolve by categorizing the conflict into three classes and always picking a conflict from the highest-priority class. In this work, we propose an oracle for conflict selection that results in smaller search tree sizes than the one used in previous work. However, the computation of the oracle is slow. Thus, we propose a machine-learning framework for conflict selection that observes the decisions made by the oracle and learns a conflict-selection strategy represented by a linear ranking function that imitates the oracle's decisions accurately and quickly. Experiments on benchmark maps indicate that our method significantly improves the success rates, the search tree sizes and runtimes over the current state-of-the-art CBS solver.
翻译:基于冲突的搜索(CBS) 是用于多试剂路径发现的最先进的算法。 在高级一级, CBS 反复检测冲突,并通过将当前问题分为两个子问题来解决其中之一。 先前的工作选择冲突, 将冲突分为三个类别, 并总是从最优先的类别中选择冲突。 在此工作中, 我们为冲突选择建议了一个标志, 导致搜索树小于先前工作所使用的。 然而, 甲骨文的计算很慢。 因此, 我们提出一个冲突选择的机器学习框架, 以观察甲骨文做出的决定, 并学习以直线排序函数代表的冲突选择战略, 准确和迅速地模仿甲骨文做出的决定。 对基准地图的实验表明, 我们的方法极大地提高了成功率、 搜索树大小和 运行时间, 超过当前最先进的 CBS 解答器 。