On Hash-Based Work Distribution Methods for Parallel Best-First Search

DOI10.1613/JAIR.5225zbMATH Open1419.68094arXiv1706.03254OpenAlexW2963090680WikidataQ129489037 ScholiaQ129489037MaRDI QIDQ4591193

Yuu Jinnai, Alex Fukunaga

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

Mathematics Subject Classification ID

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