Accession Number:

ADA454848

Title:

PRA: Massively Parallel Heuristic Search

Descriptive Note:

Research rept.

Corporate Author:

MARYLAND UNIV COLLEGE PARK SYSTEMS RESEARCH CENTER

Report Date:

1991-01-01

Pagination or Media Count:

26.0

Abstract:

This paper describes a variant of A search designed to run on the massively parallel SIMD Connection Machine. The algorithm is designed to run in a limited memory by use of a retraction technique which allows nodes with poor heuristic values to be removed from the open list until such time as they may need reexpansion more promising paths having failed. Our algorithm, called PRA for Parallel Retraction A, is designed to maximize use of the Connection Machines memory and processors. In addition, the algorithm is guaranteed to return an optimal path when an admissable heuristic is used. Results comparing PRA to Korfs IDA for the fifteen-puzzle show significantly fewer node expansions for PRA. In addition, empirical results show significant parallel speedups, indicative of the algorithms design for high processor utilization.

Subject Categories:

  • Operations Research
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE