Evaluation of a simple, scalable, parallel best-first search strategy

DOI10.1016/J.ARTINT.2012.10.007MaRDI QIDQ360118zbMATH OpenOpenAlexFDO

Authors Akihiro Kishimoto, Adi Botea, Alex Fukunaga

Publication date 26 August 2013

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.3204, http://www.sciencedirect.com/science/article/pii/S0004370212001294

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: 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 Hash-Distributed A* (HDA*), a simple approach to parallel best-first search that asynchronously 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 an optimal sequential version of the Fast Downward planner, as well as a 24-puzzle solver. The scaling behavior of HDA* is evaluated experimentally on a shared memory, multicore machine with 8 cores, a cluster of commodity machines using up to 64 cores, and large-scale high-performance clusters, using up to 2400 processors. We show that this approach scales well, allowing the effective utilization of large amounts of distributed memory to optimally solve problems which require terabytes of RAM. We also compare HDA* to Transposition-table Driven Scheduling (TDS), a hash-based parallelization of IDA*, and show that, in planning, HDA* significantly outperforms TDS. A simple hybrid which combines HDA* and TDS to exploit strengths of both algorithms is proposed and evaluated.

Recommendations

• An empirical investigation on parallelization strategies for scatter search
• Performances of parallel branch and bound algorithms with best-first search
• On the best search strategy in parallel branch-and-bound: Best-first search versus lazy depth-first search
• Best-first heuristic search for multicore machines
• The scalability analysis of a parallel tree search algorithm
• The scalability analysis of a parallel tree search algorithm
• A study of parallel branch-and-bound algorithms with best-bound-first search
• scientific article; zbMATH DE number 934538
• Parallel randomized best-first minimax search.
• On hash-based work distribution methods for parallel best-first search

Cited in

(7)

• Best-first heuristic search for multicore machines
• Accelerating backtrack search with a best-first-search strategy
• On hash-based work distribution methods for parallel best-first search
• Solving large problems with heuristic search: general-purpose parallel external-memory search
• scientific article; zbMATH DE number 4162301 (Why is no real title available?)
• Parallel multithreaded IDA\(*\) heuristic search: algorithm design and performance evaluation
• Evaluation of a Catalytic Search Algorithm

This page was built for publication: Evaluation of a simple, scalable, parallel best-first search strategy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q360118)