On Hash-Based Work Distribution Methods for Parallel Best-First Search
From MaRDI portal
Publication:4591193
DOI10.1613/JAIR.5225zbMATH Open1419.68094arXiv1706.03254OpenAlexW2963090680WikidataQ129489037 ScholiaQ129489037MaRDI QIDQ4591193FDOQ4591193
Publication date: 13 November 2017
Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1706.03254
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Parallel algorithms in computer science (68W10)
Cited In (1)
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)
