next up previous
Next: Task Distribution Up: No Title Previous: Introduction

Parallel Search Approaches

A number of researchers have explored methods for improving the efficiency of search using parallel hardware. We will focus in this paper on parallel search techniques that can be applied to IDA* search. IDA* performs a series of incrementally-deepening depth-first searches through the search space. In each iteration through the space, the depth of the search is controlled by an A* cost threshold. If a goal node is not found during a given iteration, search begins at the root node with a cost threshold set to the minimum f(n) value in the search space that exceeded the previous threshold. IDA* is an admissible search algorithm which requires an amount of memory linear in the depth of the solution.

In this section we will review existing methods for parallelizing IDA* search. In particular, we will consider alternative techniques for task distribution, for dynamically balancing work between processors, and for changing the left-to-right order of the search tree.