Graduate Thesis Or Dissertation

 

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

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/cn69m903b

Descriptions

Attribute NameValues
Creator
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.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Keyword
Rights Statement
Language
Replaces
Additional Information
  • description.provenance : Submitted by Philip Vue (vuep@onid.orst.edu) on 2009-01-29T22:14:22Z No. of bitstreams: 1 Chandrasekhara_Reddy.pdf: 858199 bytes, checksum: 3786d294a149714a67b3d897b2b8d679 (MD5)
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2009-01-29T22:40:44Z (GMT) No. of bitstreams: 1 Chandrasekhara_Reddy.pdf: 858199 bytes, checksum: 3786d294a149714a67b3d897b2b8d679 (MD5)
  • description.provenance : Made available in DSpace on 2009-01-29T22:40:44Z (GMT). No. of bitstreams: 1 Chandrasekhara_Reddy.pdf: 858199 bytes, checksum: 3786d294a149714a67b3d897b2b8d679 (MD5)
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2009-01-29T22:38:47Z (GMT) No. of bitstreams: 1 Chandrasekhara_Reddy.pdf: 858199 bytes, checksum: 3786d294a149714a67b3d897b2b8d679 (MD5)

Relationships

Parents:

This work has no parents.

Items