LEARNING FOR EFFICIENT SEARCH

Learning for problem solving involves acquisition and storage of relev ant knowledge from past problem solving instances in a domain in such a form that the information can be used to effectively solve subsequen t problems in the same domain. Our interest is in the role of learning in problem solving systems that solve problems optimally. Such proble ms can be solved by an informed search algorithm like A. Learning a s tronger heuristic function leads to more effective problem solving. A set of arbitrary features of the domain induce a clustering of the sta te space. The heuristic information associated with each cluster may b e learned. We discuss the use of a new form of information in the form of h set (the set of optimum cost values of all nodes of the cluster ) and present an algorithm for using the information that is more effe ctive than A. A possibilistic (fuzzy set theoretic) extension of this algorithm is also presented. This version can handle incomplete infor mation and is expected to find solutions faster in the average case wi th controlled relaxation in the optimality guarantee. We also discuss how to make the best use of the features, when the system has memory r estrictions that limit the number of classes that can be stored.