Adaptive K-Parallel Best-First Search: A Simple but Efficient Algorithm for Multi-Core Domain-Independent Planning
Adaptive K-Parallel Best-First Search: A Simple but Efficient Algorithm for Multi-Core Domain-Independent Planning
复制标题
自适应 K 并行最佳优先搜索：一种简单但高效的多核域独立规划算法
DOI：
10.1609/socs.v1i1.18165
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Y. Hamadi
中科院分区：
文献类型：
--
作者：
V. Vidal;L. Bordeaux;Y. Hamadi
受最近硬件向多核机器发展的启发，我们研究了共享内存环境中的并行规划技术。更具体地说，我们考虑运行K个线程的最佳优先搜索算法的并行版本，每个线程从开放列表中扩展下一个最佳节点。我们证明了所提出的技术有许多优点。首先，它（相当）简单：我们展示了如何主要通过添加并行注释从顺序版本获得算法。其次，我们进行了广泛的实证研究，表明这种方法是相当有效的。它也是动态的，因为在搜索过程中可以调整并行扩展的节点数量。总的来说，我们表明该方法对于并行领域无关的次优规划是有希望的。
Motivated by the recent hardware evolution towards multi-core machines, we investigate parallel planning techniques in a shared-memory environment. We consider, more specifically, parallel versions of a best-first search algorithm that run K threads, each expanding the next best node from the open list. We show that the proposed technique has a number of advantages. First, it is (reasonably) simple: we show how the algorithm can be obtained from a sequential version mostly by adding parallel annotations. Second, we conduct an extensive empirical study that shows that this approach is quite effective. It is also dynamic in the sense that the number of nodes expanded in parallel is adapted during the search. Overall we show that the approach is promising for parallel domain-independent, suboptimal planning.