PARALLEL SEARCH USING TRANSFORMATION-ORDERING ITERATIVE-DEEPENING-A

Iterative-Deepening-A (IDA) is an optimal search technique which is u seful for large search spaces, because it requires no intermediate sta te storage. We show how Transformation-Ordering Iterative-Deepening-A (TOIDA) improves the performance of IDA* by dynamically modifying th e node expansion order based on results from previous cost limits. We then describe a window parallel implementation of TOIDA on a Hypercub e, and present empirical evidence that the parallel implementation dra matically reduces time spent in search. Finally, we analyze the best a nd worst case results of sequential and parallel TOIDA, and compare t he results with those of standard IDA search. Empirical and analytica l results show that TOIDA can provide significant improvements in sea rch speed over IDA with no penalty in storage requirements, and paral lel TOIDA offers substantial cost reduction over sequential TOIDA*, t hough at the cost of optimality. (C) 1993 John Wiley & Sons, Inc.