Integrating Machine Learning in Parallel Heuristic Search

May 1998

Proceedings of the Eleventh International Florida Artificial Intelligence Research Society Conference (FLAIRS 1998)

Volume

Proceedings of the Eleventh International Florida Artificial Intelligence Research Society Conference (FLAIRS 1998)

All Papers

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.