Proceedings:
Book One
Volume
Issue:
Proceedings of the AAAI Conference on Artificial Intelligence, 6
Track:
Automated Reasoning
Downloads:
Abstract:
This paper presents a parallel version of the Iterative-Deepening-A* (IDA*) algorithm. Iterative-Deepening-A* is an important admissible algorithm for state-space search which has been shown to be optimal both in time and space for a wide variety of state-space search problems. Our parallel version retatins all the nice properties of the sequential IDA* and yet does not appear to be limited in the amount of parallelism. To test its effectiveness, we have implemented this algorithm on Sequent Balance 21000 parallel processor to solve the 15-puzzle problem, and have been able to obtain almost linear speedups on the 30 processors that are available on the machine. On machines where larger number of processors are available, we expect that the speedup will still grow linearly. The parallel version seems suitable even for loosely coupled architectures such as the Hypercube.
AAAI
Proceedings of the AAAI Conference on Artificial Intelligence, 6