最優良探索の並列化の研究

最佳搜索并行化研究

• 批准号: 20K11932
• 负责人: 福永 ALEX
• 金额: $ 2.75万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K11932/
• 关键词: 探索; 人工知能; 並列アルゴリズム; Heuristic Search

In 2022-2023, we developed improved algorithms for parallel search. While parallelization of the A* graph search algorithm is fairly well-understood,　parallelization of non-optimal best-first search algorithms such as Greedy Best-First Search (GBFS) has been much less understood. Recent work has proposed PUHF, a parallel GBFS which restricts search to exploration of the Bench Transition System (BTS), which is the set of states that can be expanded by GBFS under some tie-breaking policy.　However, PUHF causes threads to spend much of the time waiting so that only states which are guaranteed to be in the BTS are expanded.　We developed PUHF2, PUHF3, and PUHF4, three improvements to PUHF which maintain the constraint that only nodes in the BTS are epanded, but significantly reduce idle time and allow more rapid exploration of the BTS, resulting in better search performance compared to PUHF.

在2022-2023年，我们开发了用于并行搜索的改进算法。虽然A* 图搜索算法的并行化是相当好理解的，但非最优最佳优先搜索算法（如贪婪最佳优先搜索（GBFS））的并行化却很少被理解。最近的工作提出了PUHF，一个并行的GBFS，限制搜索的板凳过渡系统（BTS），这是一组状态，可以扩展的GBFS下一些平局打破政策的探索。然而，PUHF导致线程花费大量时间等待，因此只有保证在BTS中的状态才被扩展。我们开发了PUHF 2，PUHF 3和PUHF 4，这是对PUHF的三种改进，它们保持了仅BTS中的节点被epanded的约束，但显著减少了空闲时间，并允许更快速地探索BTS，从而与PUHF相比具有更好的搜索性能。

项目成果

Avoiding Pitfalls in Parallel Search

避免并行搜索中的陷阱

• 发表时间: 2021
• 作者: Hira Shoko;Endo Rei;Mochihara Kanta;Ohkoba Minoru;Ishikawa Tomoharu;Ayama Miyoshi;Ohtsuka Sakuichi;Fukunaga Alex
• 通讯作者: Fukunaga Alex

Analyzing and Avoiding Pathological Behavior in Parallel Best-First Search

分析和避免并行最佳优先搜索中的病态行为

• 发表时间: 2020
• 期刊: Proceedings of International Conference on Automated Planning and Scheduling
• 作者: Kuroiwa Ryo;Fukunaga Alex
• 通讯作者: Fukunaga Alex

Improved Exploration of the Bench Transition System in Parallel Greedy Best First Search

并行贪婪最佳优先搜索中替台转移系统的改进探索

• 发表时间: 2023
• 作者: Takumi Shimoda; Alex Fukunaga
• 通讯作者: Alex Fukunaga