论文标题
学习通过基于冲突的搜索来解决多代理路径查找的冲突
Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search
论文作者
论文摘要
基于冲突的搜索（CBS）是用于多代理路径查找的最新算法。在高水平上，CBS反复发现冲突，并通过将当前问题分为两个子问题来解决其中之一。以前的工作选择冲突来解决，通过将冲突分为三个类，并始终从最高优先级级别中挑选冲突。在这项工作中，我们提出了一个用于冲突选择的甲骨文，该甲骨文的搜索树大小比以前的工作中使用的搜索树大小。但是，甲骨文的计算很慢。因此，我们提出了一个用于冲突选择的机器学习框架，该框架观察了甲骨文的决定，并学习了由线性排名函数表示的冲突选择策略，该策略可以准确，快速模仿甲骨文的决策。基准图上的实验表明，我们的方法显着提高了成功率，搜索树的大小和运行时间比当前最新的CBS求解器。
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.
