On hash-based work distribution methods for parallel best-first search

DOI10.1613/JAIR.5225MaRDI QIDQ4591193zbMATH OpenOpenAlexWikidataFDO

Authors Yuu Jinnai, Alex Fukunaga

Publication date 13 November 2017

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.03254

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Parallel algorithms in computer science (68W10)

Abstract: Parallel best-first search algorithms such as Hash Distributed A* (HDA*) distribute work among the processes using a global hash function. We analyze the search and communication overheads of state-of-the-art hash-based parallel best-first search algorithms, and show that although Zobrist hashing, the standard hash function used by HDA*, achieves good load balance for many domains, it incurs significant communication overhead since almost all generated nodes are transferred to a different processor than their parents. We propose Abstract Zobrist hashing, a new work distribution method for parallel search which, instead of computing a hash value based on the raw features of a state, uses a feature projection function to generate a set of abstract features which results in a higher locality, resulting in reduced communications overhead. We show that Abstract Zobrist hashing outperforms previous methods on search domains using hand-coded, domain specific feature projection functions. We then propose GRAZHDA*, a graph-partitioning based approach to automatically generating feature projection functions. GRAZHDA* seeks to approximate the partitioning of the actual search space graph by partitioning the domain transition graph, an abstraction of the state space graph. We show that GRAZHDA* outperforms previous methods on domain-independent planning.

Recommendations

• Evaluation of a simple, scalable, parallel best-first search strategy
• Best-first heuristic search for multicore machines
• Publication:3489493
• scientific article; zbMATH DE number 934534
• A study of parallel branch-and-bound algorithms with best-bound-first search

Cited in

(2)

• Evaluation of a simple, scalable, parallel best-first search strategy
• Best-first heuristic search for multicore machines

This page was built for publication: On hash-based work distribution methods for parallel best-first search

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