Parallel search using transformation‐ordering Lterative‐Deepening‐A*

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.