ML Anthology

A Parallel Implementation of Iterative-Deepening-A*

V. Nageshwara Rao, Vipin Kumar, K. Ramesh
AAAI 1987 pp. 178-182
/aaai/1987/rao1987aaai-parallel/

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.

PDF AAAI Semantic Scholar

Cite

Text

Rao et al. "A Parallel Implementation of Iterative-Deepening-A*." AAAI Conference on Artificial Intelligence, 1987.

Markdown

[Rao et al. "A Parallel Implementation of Iterative-Deepening-A*." AAAI Conference on Artificial Intelligence, 1987.](https://mlanthology.org/aaai/1987/rao1987aaai-parallel/)

BibTeX

@inproceedings{rao1987aaai-parallel,
  title     = {{A Parallel Implementation of Iterative-Deepening-A*}},
  author    = {Rao, V. Nageshwara and Kumar, Vipin and Ramesh, K.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {1987},
  pages     = {178-182},
  url       = {https://mlanthology.org/aaai/1987/rao1987aaai-parallel/}
}