PRA - MASSIVELY-PARALLEL HEURISTIC-SEARCH

In this paper we describe a variant of A search designed to run on th e massively parallel, SIMD Connection Machine (CM-2). The algorithm is designed to run in a limited memory by the use of a retraction techni que which allows nodes with poor heuristic values to be removed from t he open list until such time as they may need reexpansion, more promis ing paths having failed. Our algorithm, called PRA (for Parallel Retr action A), is designed to maximize use of the Connection Machine's me mory and processors. In addition, the algorithm is guaranteed to retur n an optimal path when an admissible heuristic is used. Results compar ing PRA to Korf's IDA* for the fifteen puzzle show significantly fewe r node expansions for PRA. In addition, empirical results show signif icant parallel speedups, indicative of the algorithm's design for high processor utilization. (C) 1995 Academic Press, Inc.