ADAPTIVE PARALLEL ITERATIVE DEEPENING SEARCH

Many of the artificial intelligence techniques developed to date rely on heuristic search through large spaces. Unfortunately, the size of t hese spaces and the corresponding computational effort reduce the appl icability of otherwise novel and effective algorithms. A number of par allel and distributed approaches to search have considerably improved the performance of the search process. Our goal is to develop an archi tecture that automatically selects parallel search strategies for opti mal performance on a variety of search problems. In this paper we desc ribe one such architecture realized in the EUREKA system, which combin es the benefits of many different approaches to parallel heuristic sea rch. Through empirical and theoretical analyses we observe that featur es of the problem space directly affect the choice of optimal parallel search strategy. We than employ machine learning techniques to select the optimal parallel search strategy for a given problem space. When a new search task is input to the system, EUREKA uses features describ ing the search space and the chosen architecture to automatically sele ct the appropriate search strategy. EUREKA has been tested on a MIMD p arallel processor, a distributed network of workstations, and a single workstation using multireading. Results generated from fifteen puzzle problems, robot arm motion problems, artificial search spaces, and pl anning problems indicate that EUREKA outperforms any of the tested str ategies used exclusively for all problem instances and is able to grea tly reduce the search time for these applications.