Learning search control knowledge for planning with conjunctive goals.
Kwang Ryel Ryu · Deep Blue (University of Michigan) · 1992
Significant results of research are available in the area of learning search control knowledge for problem solving. However, previous systems that derive goal ordering rules exhibit some weaknesses. These systems fail to effectively reduce search because their rules are either over-specific or over-general. Moreover, they require a priori domain-specific knowledge to derive effective rules. This thesis presents a methodology which enables the derivation of goal ordering rules from the analysis of problem failures without relying on any a priori knowledge. We examine all the planning actions which unavoidably lead to failures. If there are restrictions imposed by a problem state on possible actions to be taken, the restrictions manifest themselves in the form of a restricted set of possible operator bindings. Our method makes use of this observation to derive general goal ordering rules which are guaranteed to be correct. We formally investigate the scope of applicability of our methodology for learning correct rules. The overhead involved in learning is very low because this methodology needs only a small amount of data to learn from, namely, the goal stacks from the leaf nodes of a failure search tree, rather than the whole search tree. Empirical tests show that the rules derived by our system PAL, after sufficient learning, performs as well as, and in some cases better than, those derived by other systems such as PRODIGY/EBL and STATIC.