A FRAMEWORK FOR LEARNING IN SEARCH-BASED SYSTEMS

In this paper, we provide an overall framework for learning in search- based systems that are used to find optimum solutions to problems. Thi s framework assumes that prior knowledge is available in the form of o ne or more heuristic functions (or features) of the problem domain. An appropriate clustering strategy is used to partition the state space into a number of classes based on the available features. The number o f classes formed will depend on the resource constraints of the system . In the training phase, example problems are run using a standard adm issible search algorithm. In this phase, heuristic information corresp onding to each class is learned. This new information can be used in t he problem-solving phase by appropriate search algorithms so that subs equent problem instances can be solved more efficiently. In this frame work, we also show that heuristic information of forms other than the conventional single-valued underestimate value can be used, since we m aintain the heuristic of each class explicitly. We show some novel sea rch algorithms that can work with some such forms. Experimental result s have been provided for some domains.