Integrating Machine Learning in Parallel Heuristic Search

R. Craig Varnell, Stephen F. Austin State University; and Diane J. Cook, University of Texas at Arlington

Abstract Many artificial intelligence applications rely on searc-ing through large, complex spaces. Iterative Deepening-A* (IDA') is a procedure capable of finding a least cost path to a goal; however, the execution time on a single processor is often too long for most applications. Parallel processing can be used to reduce the complexity and run time of a search problem by dividing the work load over multiple processors. A number of techniques have been introduced that improve the performance of heuristic search. Each approach has a number of parameters that are often selected by the user before the problem is executed. It is common to find that the selection of parameters for one approach will conflict with parameters for another approach and poor performance will result. This research uses a knowledge base constructed by the C4.5 machine learning system to continuously select approaches and the associated parameters throughout the execution of a problem. Therefore, as the search moves deeper into the tree structure, the approach will be modified to adapt to the tree structure. A series of experiments has been performed with the fifteen puzzle problem domain. A significant improvement in performance has resulted from using machine learning to select an appropriate approach for a problem.


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.