Maximizing the Benefits of Parallel Search Using Machine Learning

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 EUREKAsystem, 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, EUREKAgathers 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 single workstation using multithreading. Results in the fifteen puzzle domain, robot arm path planning domain, and an artificial domain indicate that EUREKAoutperforms any existing strategy used exclusively for all problem instances.

Authors

• Diane J. Cook

Keywords

No keywords are indexed for this paper.