Learning a Priority Ordering for Prioritized Planning in Multi-Agent Path Finding
Learning a Priority Ordering for Prioritized Planning in Multi-Agent Path Finding
复制标题
学习多智能体寻路中优先规划的优先顺序
DOI：
10.1609/socs.v15i1.21769
复制
发表时间：
2022
期刊：
影响因子：
13.5
通讯作者：
B. Dilkina
中科院分区：
文献类型：
--
作者：
Shuyang Zhang;Jiaoyang Li;Taoan Huang;Sven Koenig;B. Dilkina
优先级规划（PP）是求解多Agent路径问题的一种快速而流行的框架，但其解的质量很大程度上取决于Agent的预定优先级排序。目前的PP算法使用贪婪的政策或随机分配，以确定总的优先级排序，但没有一个占主导地位的成功率和解决方案的质量（衡量的总和成本）。我们提出了一个机器学习（ML）框架来学习PP的良好优先级排序。我们开发了两种模型，即ML-T，它是在总优先级排序上训练的，ML-P，它是在部分优先级排序上训练的。我们建议通过进一步应用随机排序和随机重启来提高PP的有效性。结果表明，我们的ML引导的PP算法优于现有的PP算法在成功率，运行时间和解决方案的质量在小地图上，在大多数情况下，尽管在这些地图上收集训练数据的困难与他们在大地图上的竞争力。
Prioritized Planning (PP) is a fast and popular framework for solving Multi-Agent Path Finding, but its solution quality depends heavily on the predetermined priority ordering of the agents. Current PP algorithms use either greedy policies or random assignments to determine a total priority ordering, but none of them dominates the others in terms of the success rate and solution quality (measured by the sum-of-costs). We propose a machine-learning (ML) framework to learn a good priority ordering for PP. We develop two models, namely ML-T, which is trained on a total priority ordering, and ML-P, which is trained on a partial priority ordering. We propose to boost the effectiveness of PP by further applying stochastic ranking and random restarts. The results show that our ML-guided PP algorithms outperform the existing PP algorithms in success rate, runtime, and solution quality on small maps in most cases and are competitive with them on large maps despite the difficulty of collecting training data on these maps.
学习通过基于冲突的搜索解决多代理路径查找的冲突
DOI：
--
发表时间：
2021
期刊：
AAAI Conference on Artificial Intelligence (AAAI
影响因子：
--
作者：
Huang, T.;Koenig, S.;Dilkina, B.
通讯作者：
Dilkina, B.
多智能体路径查找中的介数中心性
DOI：
--
发表时间：
2022
期刊：
International Conference on Autonomous Agents and Multiagent Systems
影响因子：
--
作者：
Eric Ewing;Jingyao Ren;Dhvani Kansara;Vikraman Sathiyanarayanan;Nora Ayanian
通讯作者：
Nora Ayanian
MAPFAST：使用最短路径嵌入进行多智能体路径查找的深度算法选择器
DOI：
--
发表时间：
2021
期刊：
Autonomous agents and multiagent systems
影响因子：
--
作者：
Ren, Jingyao;Sathiyanarayanan, Vikraman;Ewing, Eric;Senbaslar, Baskin;Ayanian, Nora
通讯作者：
Ayanian, Nora