Ph.D. Thesis, Lehigh University, 2011.
![Learning Hierarchical Task Networks From Traces and Semantically Annotated Tasks [link]](https://bibbase.org/img/filetypes/link.svg "link")
Dissertation abstract bibtex
Dissertation abstract bibtex Hierarchical Task Network planning is a fast and highly expressive formalism for problem solving, but systems based on this formalism depend on the existence of domain-specific knowledge constructs (methods) describing how and in what circumstances complex tasks may be reduced into simpler tasks in order to solve problems. Writing and debugging a set of methods for a new domain has in the past been a difficult and error-prone manual process. This dissertation presents and evaluates a framework in which HTN methods can be automatically learned from a classical planning domain description, a set of example pairs of planning states from that domain with plans applicable in those states, and a set of annotated tasks for that domain. Annotated task are task symbols with associated preconditions and postconditions describing what it means to accomplish those tasks.
The primary algorithm based on this framework is HTN-Maker, which works by searching the input plans for subplans over which an annotated task has been accomplished and using goal regression to build a recursive series of explanations of how the task was accomplished. Each of these explanations becomes a method stating that the task may be reduced into its subtasks and giving conditions under which this will be valid. These methods that have been learned can then be used by an HTN planner to solve HTN planning problems.
The implementation of the HTN-Maker algorithm has a number of configurable options and design decisions relating to such questions as how subtasks should be grouped together, how constants should be generalized into variables, and whether or not effort should be expended in discovering and pruning unnecessary methods. Theoretical results show that if the system is configured properly, the methods learned by HTN-Maker will accurately model the annotated tasks from which they were learned. They also show that, from a finite number of examples, HTN-Maker is capable of learning a set of methods for a domain that can be used to solve all solvable problems in that domain that can be expressed using the provided annotated tasks. There are HTN planning problems that cannot be expressed using annotated tasks, and thus cannot be solved using methods learned by HTN-Maker, but there are also non-classical problems that can be solved using the methods learned by HTN-Maker.
HTN-MakerND is an extension of HTN-Maker that learns methods that will be effective in domains in which actions do not have deterministic effects. It does so by learning methods with a carefully chosen structure that maximizes flexibility when using those methods. Q-Maker is an extension of HTN-Maker that learns both methods and estimated values of those methods intended to guide a planner toward a near-optimal plan quickly. A further algorithm, Q-Reinforce, uses reinforcement learning to refine these method values through planning experience, and Q-Shop uses the methods and values to solve planning problems, preferring to use methods with higher values when given a choice.
Experimental results in several benchmark planning domains explore the consequences of several of the options and design decisions in HTN-Maker on the amount of useful knowledge it is able to extract from examples and on the speed of planning with the methods that it learns. The evaluation demonstrates that both HTN-Maker and HTN-MakerND are able to learn knowledge that generalizes well to new problems. In four of five deterministic domains and both nondeterministic domains, planning with the learned methods is much faster than non-HTN planning. Q-Shop using methods learned by Q-Maker and refined by Q-Reinforce produces plans that are of higher quality than those produced by traditional satisficing planners while still running much more quickly than an optimal planner in both domains in which it was tested.
The primary algorithm based on this framework is HTN-Maker, which works by searching the input plans for subplans over which an annotated task has been accomplished and using goal regression to build a recursive series of explanations of how the task was accomplished. Each of these explanations becomes a method stating that the task may be reduced into its subtasks and giving conditions under which this will be valid. These methods that have been learned can then be used by an HTN planner to solve HTN planning problems.
The implementation of the HTN-Maker algorithm has a number of configurable options and design decisions relating to such questions as how subtasks should be grouped together, how constants should be generalized into variables, and whether or not effort should be expended in discovering and pruning unnecessary methods. Theoretical results show that if the system is configured properly, the methods learned by HTN-Maker will accurately model the annotated tasks from which they were learned. They also show that, from a finite number of examples, HTN-Maker is capable of learning a set of methods for a domain that can be used to solve all solvable problems in that domain that can be expressed using the provided annotated tasks. There are HTN planning problems that cannot be expressed using annotated tasks, and thus cannot be solved using methods learned by HTN-Maker, but there are also non-classical problems that can be solved using the methods learned by HTN-Maker.
HTN-MakerND is an extension of HTN-Maker that learns methods that will be effective in domains in which actions do not have deterministic effects. It does so by learning methods with a carefully chosen structure that maximizes flexibility when using those methods. Q-Maker is an extension of HTN-Maker that learns both methods and estimated values of those methods intended to guide a planner toward a near-optimal plan quickly. A further algorithm, Q-Reinforce, uses reinforcement learning to refine these method values through planning experience, and Q-Shop uses the methods and values to solve planning problems, preferring to use methods with higher values when given a choice.
Experimental results in several benchmark planning domains explore the consequences of several of the options and design decisions in HTN-Maker on the amount of useful knowledge it is able to extract from examples and on the speed of planning with the methods that it learns. The evaluation demonstrates that both HTN-Maker and HTN-MakerND are able to learn knowledge that generalizes well to new problems. In four of five deterministic domains and both nondeterministic domains, planning with the learned methods is much faster than non-HTN planning. Q-Shop using methods learned by Q-Maker and refined by Q-Reinforce produces plans that are of higher quality than those produced by traditional satisficing planners while still running much more quickly than an optimal planner in both domains in which it was tested.
@PhdThesis{Hogg2011PhDThesis,
author = {Chad Michael Hogg},
title = {Learning Hierarchical Task Networks From Traces and Semantically Annotated Tasks},
school = {Lehigh University},
year = {2011},
abstract = {Hierarchical Task Network planning is a fast and highly expressive formalism for problem solving, but systems based on this formalism depend on the existence of domain-specific knowledge constructs (methods) describing how and in what circumstances complex tasks may be reduced into simpler tasks in order to solve problems. Writing and debugging a set of methods for a new domain has in the past been a difficult and error-prone manual process. This dissertation presents and evaluates a framework in which HTN methods can be automatically learned from a classical planning domain description, a set of example pairs of planning states from that domain with plans applicable in those states, and a set of annotated tasks for that domain. Annotated task are task symbols with associated preconditions and postconditions describing what it means to accomplish those tasks.<br/><br/>
The primary algorithm based on this framework is HTN-Maker, which works by searching the input plans for subplans over which an annotated task has been accomplished and using goal regression to build a recursive series of explanations of how the task was accomplished. Each of these explanations becomes a method stating that the task may be reduced into its subtasks and giving conditions under which this will be valid. These methods that have been learned can then be used by an HTN planner to solve HTN planning problems.<br/><br/>
The implementation of the HTN-Maker algorithm has a number of configurable options and design decisions relating to such questions as how subtasks should be grouped together, how constants should be generalized into variables, and whether or not effort should be expended in discovering and pruning unnecessary methods. Theoretical results show that if the system is configured properly, the methods learned by HTN-Maker will accurately model the annotated tasks from which they were learned. They also show that, from a finite number of examples, HTN-Maker is capable of learning a set of methods for a domain that can be used to solve all solvable problems in that domain that can be expressed using the provided annotated tasks. There are HTN planning problems that cannot be expressed using annotated tasks, and thus cannot be solved using methods learned by HTN-Maker, but there are also non-classical problems that can be solved using the methods learned by HTN-Maker.<br/><br/>
HTN-MakerND is an extension of HTN-Maker that learns methods that will be effective in domains in which actions do not have deterministic effects. It does so by learning methods with a carefully chosen structure that maximizes flexibility when using those methods. Q-Maker is an extension of HTN-Maker that learns both methods and estimated values of those methods intended to guide a planner toward a near-optimal plan quickly. A further algorithm, Q-Reinforce, uses reinforcement learning to refine these method values through planning experience, and Q-Shop uses the methods and values to solve planning problems, preferring to use methods with higher values when given a choice.<br/><br/>
Experimental results in several benchmark planning domains explore the consequences of several of the options and design decisions in HTN-Maker on the amount of useful knowledge it is able to extract from examples and on the speed of planning with the methods that it learns. The evaluation demonstrates that both HTN-Maker and HTN-MakerND are able to learn knowledge that generalizes well to new problems. In four of five deterministic domains and both nondeterministic domains, planning with the learned methods is much faster than non-HTN planning. Q-Shop using methods learned by Q-Maker and refined by Q-Reinforce produces plans that are of higher quality than those produced by traditional satisficing planners while still running much more quickly than an optimal planner in both domains in which it was tested.},
url_Dissertation = {https://preserve.lehigh.edu/cgi/viewcontent.cgi?article=2235&context=etd}
}Downloads: 0