Learning hierarchical decomposition rules for planning: An inductive logic programming approach

Artificial Intelligence (AI) planning techniques have been central to automating a gamut of tasks from the mundane route planning and beer production to the ethereal image processing of space-ship images. Of all the planning techniques, hierarchical-decomposition planning has been the technique most employed in industrial-strength planners. Hierarchical-decomposition planning is performed by recursively decomposing a planning task into its subtasks, until the decomposition results in primitive tasks which can be directly achieved by executing the primitive actions.;Hierarchical-decomposition planning is knowledge intensive; it exploits knowledge of the structure and the constraints of a planning domain, to decompose a task into subtasks. Because dependence on human experts for this knowledge leads to knowledge-acquisition bottleneck, machine learning of this domain-specific knowledge becomes important. There exist two opportunities for learning in the context of hierarchical-decomposition planning. One is to learn how a planning task decomposes into subtasks. The other is to learn control knowledge to choose among various decompositions for a task depending upon situations. In this dissertation, the focus is on the former; more specifically, we focus on learning rules for task or goal decompositions.;Goal-decomposition rules (d-rules) decompose goals into a sequence of subgoals under certain conditions. These are a special case of hierarchical task networks (HTNs). The methodology we used for learning d-rules is to map d-rules to Horn clauses, and, thus, transform the problem of learning d-rules to learning Horn clauses. We developed probably correct algorithms for learning Horn clauses. Our algorithms are based on a "generalize-and-test" method, where inductive least-general generalization of positive examples is followed by pruning of irrelevant literals by asking queries or performing self-testing. We implemented systems that are founded in the theoretical algorithms, and tested the applicability of the systems in two planning domains--a robot navigation domain and an air-traffic control domain. One of these systems, ExEL, learned from solved problems and expert-answered queries. The other, LeXer, learned from unsolved but ordered problems, or exercises, and self-testing. The applicability of the theoretical algorithms developed for learning Horn clauses, however, transcends the learning of d-rules and even the learning of the more general HTNs.