Parallel search using transformation-ordering Lterative-Deepening-A*
Diane J. Cook, Lawrence Hall, Willard Thomas · International Journal of Intelligent Systems · 1993
Iterative-Deepening-A (IDA*) is an optimal search technique which is useful for large search spaces, because it requires no intermediate state storage. We show how Transformation-Ordering Iterative-Deepening-A* (TOIDA*) improves the performance of IDA* by dynamically modifying the node expansion order based on results from previous cost limits. We then describe a window parallel implementation of TOIDA* on a Hypercube, and present empirical evidence that the parallel implementation dramatically reduces time spent in search. Finally, we analyze the best and worst case results of sequential and parallel TOIDA*, and compare the results with those of standard IDA* search. Empirical and analytical results show that TOIDA* can provide significant improvements in search speed over IDA* with no penalty in storage requirements, and parallel TOIDA* offers substantial cost reduction over sequential TOIDA*, though at the cost of optimality. © 1993 John Wiley & Sons, Inc.