Abstract:
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.
