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 解答器 。

0
下载
关闭预览

相关内容

甲骨文公司,全称甲骨文股份有限公司(甲骨文软件系统有限公司),是全球最大的企业级软件公司,总部位于美国加利福尼亚州的红木滩。1989年正式进入中国市场。2013年,甲骨文已超越 IBM ,成为继 Microsoft 后全球第二大软件公司。
专知会员服务
16+阅读 · 2020年12月4日
可解释强化学习,Explainable Reinforcement Learning: A Survey
专知会员服务
129+阅读 · 2020年5月14日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习扫盲贴:从Q-learning到DQN
夕小瑶的卖萌屋
52+阅读 · 2019年10月13日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
7+阅读 · 2018年10月12日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
5+阅读 · 2018年6月12日
Arxiv
6+阅读 · 2018年4月24日
VIP会员
相关资讯
强化学习扫盲贴:从Q-learning到DQN
夕小瑶的卖萌屋
52+阅读 · 2019年10月13日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
7+阅读 · 2018年10月12日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员