SHAPES - A NOVEL-APPROACH FOR LEARNING SEARCH HEURISTICS IN UNDER-CONSTRAINED OPTIMIZATION PROBLEMS

Although much research in machine learning has been carried out on acq uiring knowledge for problem-solving in many problem domains, little e ffort has been focused on learning search-control knowledge for solvin g optimization problems. This paper reports on the development of SHAP ES, a system that learns heuristic search guidance for solving optimiz ation problems in intractable, under-constrained domains based on the Explanation-Based Learning (EEL) framework. The system embodies two ne w and novel approaches to machine learning. First, it makes use of exp lanations of varying levels of approximation as a mean for verifying h euristic-based decisions, allowing heuristic estimates to be revised a nd corrected during problem-solving. The provision of such a revision mechanism is particularly important when working in intractable and un der-constrained domains, where heuristics tend to be highly over-gener alized, and hence at times will give rise to incorrect results. Second , ii employs a new linear and quadratic programming-based weight-assig nment algorithm formulated to direct search toward optimal solutions u nder best-first search. The algorithm offers a direct method for assig ning rule strengths and, in so doing, avoids the need to address the c redit-assignment problem faced by other iterative weight-adjustment me thods.