Because of the dependence AI techniques demonstrate upon heuristic search algorithms, researchers continually seek more efficient methods of searching through the large spaces created by these algorithms. Advances in parallel and distributed computing offer potentially large increases in performance to such compute-intensive tasks. In response, a number of parallel approaches have been developed to improve various search algorithms including depth-first search [19], branch-and-bound search [1], A* [13,22], IDA* [21,24,25], and game tree search [14], as well as to improve the run time of specific applications such as the fifteen puzzle problem [19] and robot arm path planning [6]. In addition to MIMD distributed-memory algorithms, parallel search algorithms have been developed for MIMD shared-memory systems [17,19] and SIMD architectures [11,13,18,21,24]. While existing approaches to parallel search have many contributions to offer, comparing these approaches and determining the best use of each contribution is difficult because of the diverse search algorithms, implementation platforms, and applications reported in the literature.
In response to this problem, we have developed the EUREKA parallel search engine that combines many of these approaches to parallel heuristic search. EUREKA [8] is a parallel IDA* search architecture that merges multiple approaches to task distribution, load balancing, and tree ordering, and can be run on a MIMD shared memory or distributed memory parallel processor, a distributed network of workstations, or a single machine with multithreading. Using our collection of search algorithms, we perform theoretical and empirical comparisons and observe that performance trends do exist as search space features are varied. To capitalize on these trends, EUREKA uses a machine learning system to predict the optimal set of parallel search strategies for a given problem, which are then used to complete the search task.