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

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