|Abstract or Summary
- Arti cial 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 decom- posing 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 knowl- edge 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-speci c knowl- edge becomes important. There exist two opportunities for learning in the context of hierarchical-decomposition planning. One is to learn how a planning task de- composes 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 speci cally, 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 provably correct algorithms for learning Horn clauses. Our algorithms are based on a generalize-and-test method, where inductive least-general gener- alization 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-tra c 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.