Title :
PRA*: a memory-limited heuristic search procedure for the Connection Machine
Author :
Evet, Matthew ; Hendler, James ; Mahanti, Ambujashka ; Nau, Dana
Author_Institution :
Inst. of Adv. Comput. Studies Maryland Univ., College Park, MD, USA
Abstract :
A variant of A* search designed to run on the massively parallel SIMD (single-instruction-stream, multiple-data-steam) Connection Machine is described. The algorithm is designed to run in a limited memory; a retraction technique allows nodes with poor heuristic values to be removed from the open list until such time as they may need reexpansion if more promising paths fail. The algorithm, called PRA* (for parallel retraction A*), takes maximum advantage of the SIMD design of the Connection Machine and is guaranteed to return an optimal path when an admissible heuristic is used. Results comparing PRA* to R. Korf´s IDA* (see Artif. Intell. J., vol.27, 1985) for the 15 puzzle show significantly fewer node expansions for PRA*
Keywords :
heuristic programming; parallel algorithms; search problems; 15 puzzle; Connection Machine; PRA*; SIMD; memory-limited heuristic search procedure; parallel retraction A*; retraction technique; Algorithm design and analysis; Computational efficiency; Concurrent computing; Heuristic algorithms; Iterative algorithms; Parallel machines; Size measurement; Tree graphs;
Conference_Titel :
Frontiers of Massively Parallel Computation, 1990. Proceedings., 3rd Symposium on the
Conference_Location :
College Park, MD
Print_ISBN :
0-8186-2053-6
DOI :
10.1109/FMPC.1990.89450
