Scalable, Parallel Best-First Search for Optimal Sequential Planning
Scalable, Parallel Best-First Search for Optimal Sequential Planning
复制标题
用于优化顺序规划的可扩展、并行最佳优先搜索
DOI：
10.1609/icaps.v19i1.13350
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Botea
中科院分区：
文献类型：
--
作者：
Akihiro Kishimoto;A. Fukunaga;A. Botea
由商用处理器组成的大规模并行集群越来越多，使得能够使用巨大的处理能力和分布式RAM来解决硬搜索问题。 我们研究并行算法的最佳顺序规划，重点是利用分布式内存计算集群。 特别是，我们专注于一种方法，该方法基于搜索状态的散列函数在处理器之间分配和调度工作。 我们使用这种方法来并行化的A* 算法的最佳顺序版本的快速向下规划。 该算法的缩放行为进行评估实验集群使用多达128个处理器，一个显着的增加相比，以前的工作在并行规划。 我们表明，这种方法的规模很好，使我们能够有效地利用大量的分布式内存，以最佳方式解决问题，需要数百GB的RAM来解决。我们还表明，这种方法可以很好地扩展为一个单一的，共享内存的多核机器。
Large-scale, parallel clusters composed of commodity processors are increasingly available, enabling the use of vast processing capabilities and distributed RAM to solve hard search problems. We investigate parallel algorithms for optimal sequential planning, with an emphasis on exploiting distributed memory computing clusters. In particular, we focus on an approach which distributes and schedules work among processors based on a hash function of the search state. We use this approach to parallelize the A* algorithm in the optimal sequential version of the Fast Downward planner. The scaling behavior of the algorithm is evaluated experimentally on clusters using up to 128 processors, a significant increase compared to previous work in parallelizing planners. We show that this approach scales well, allowing us to effectively utilize the large amount of distributed memory to optimally solve problems which require hundreds of gigabytes of RAM to solve. We also show that this approach scales well for a single, shared-memory multicore machine.