Maximizing the Benefits of Parallel Search Using Machine Learning

Diane J. Cook, R. Craig Varnell

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.