Maximizing the Benefits of Parallel Search Using Machine Learning

Abstract

Many of the artificial intelligence techniques developed to date rely on heuristic search through large spaces. Unfortunately, the size of these spaces and corresponding computational effort reduce the applicability of otherwise novel and effective algorithms. A number of parallel and distributed approaches to search have considerably improved the performance of certain aspects of the search process. In this paper we describe the Eureka system, which combines the benefits of many different approaches to parallel heuristic search. Eureka uses a machine learning system to decide upon the optimal parallel search strategy for a given problem space. When a new search task is input to the system, Eureka gathers information about the search space and automatically selects the appropriate search strategy. Eureka includes diverse approaches to task distribution, load balancing, and tree ordering, and has been tested on a MIMD parallel processor, a distributed network of workstations, and a sin...