Diane J. Cook
Search permeates all aspects of artificial intelligence including problem solving, robot motion planning, concept learning, theorem proving, and natural language understanding. Because search routines are frequently also a computational bottleneck, numerous methods have been explored to increase the efficiency of search by making use of background knowledge, search macro operators, and parallel hardware for search. We introduce an algorithm for massively-parallel heuristic search, named MIDA* (Massively-parallel Incremental-Deepening A* search). In this paper we demonstrate that MIDA* offers a significant improvement in efficiency of search over serial search algorithms and MIMD parallel algorithms that can only make use of a few processors. At the heart of the MIDA* approach lies a very fast information distribution algorithm that biases the search to the left side of the tree. Given information about favorable operator orderings, MIDA* can improve upon SIMD algorithms that rely on traditional information distribution techniques.