1 March 1992 SIMD approach to IDA* search
Author Affiliations +
Abstract
Heuristic search is a fundamental component of artificial intelligence applications. Because search routines are frequently a computational bottleneck, numerous methods have been explored to increase the efficiency of search. While sequential search methods use exponential amounts of storage and yield exponential run times, parallel algorithms designed for MIMD machines significantly reduce the time spent in search. In this paper, we present a massively- parallel SIMD approach to search named MIDA* search. The components of MIDA* include a very fast distribution algorithm which biases the search to one side of the tree, and an incrementally-deepening depth-first search of all the processors in parallel. We show the results of applying MIDA* to instances of the fifteen puzzle problem. Results reveal an efficiency of 76% and a speedup of 8553% and 492% over serial and 16- processor MIMD algorithms, respectively.
© (1992) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Gary Lyons, Gary Lyons, Dianne J. Cook, Dianne J. Cook, "SIMD approach to IDA* search", Proc. SPIE 1707, Applications of Artificial Intelligence X: Knowledge-Based Systems, (1 March 1992); doi: 10.1117/12.56879; https://doi.org/10.1117/12.56879
PROCEEDINGS
11 PAGES


SHARE
RELATED CONTENT

Propagation of variances in belief networks
Proceedings of SPIE (February 28 1991)
Case-based reasoning approach for heuristic search
Proceedings of SPIE (February 28 1991)
Inconsistency checking: an approach based on satisfiability
Proceedings of SPIE (February 29 1992)
Parallelism In Rule-Based Systems
Proceedings of SPIE (March 28 1988)
Selection Of Subdomains In Hierarchic Path Generation
Proceedings of SPIE (March 20 1989)
Learning Significant Class Descriptions
Proceedings of SPIE (May 10 1987)

Back to Top