PRA: Massively Parallel Heuristic Search

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 Machine's memory and processors. In addition, the algorithm is guaranteed to return an optimal path when an admissable heuristic is used. Results comparing PRA* to Korf's IDA* for the fifteen-puzzle show significantly fewer node expansions for PRA*. In addition, empirical results show significant parallel speedups, indicative of the algorithm's design for high processor utilization.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1991
Accession Number
ADA454848

Entities

People

  • Ambuj Mahanti
  • Dana S. Nau
  • James Hendler
  • Matthew Evett

Organizations

  • University of Maryland

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Classification
  • Contracts
  • Information Operations
  • Instructions
  • Maryland
  • Monitoring
  • Organizational Structure
  • Security
  • Standards
  • Universities

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Operations Research
  • Parallel and Distributed Computing.