Controlling the Parameters of Parallel Search Using Uncertainty Reasoning
Diane J. Cook, Piotr J. Gmytrasiewicz · 1999
Many artificial intelligence techniques rely on heuris-tic search through large spaces. Because the compu-tational effort required to search through these spaces reduces the applicability of the techniques, a number of parallel and distributed approaches to search have been introduced to improve the performance of certain aspects of the search process. However, theoretical and experimental results have shown that the effec-tiveness of parallel search algorithms can vary greatly from one search problem to another. In this paper we investigate the use of uncertainty rea-soning to choose the parallel search techniques that maximize the speedup obtained by parallel search. The approach described here is implemented in the EUREKA system, an architecture that includes diverse approaches parallel search. When a new search task is input to the system, EUREKA gathers information about the search space and automatically selects the appropriate search strategy. Because the gathered in-formation is uncertain and incomplete, we use a belief network to model the influence of problem features on speedup and select strategies that will yield the best performance. We present preliminary results on search problems drawn from the Fifteen Puzzle domain.