Hierarchical Methods for Optimal Long-Term Planning. Wolfe, J. Ph.D. Thesis, EECS Department, University of California, Berkeley, 2011. Dissertation abstract bibtex This thesis addresses the problem of generating goal-directed plans involving very many elementary actions. For example, to achieve a real-world goal such as earning a Ph.D., an intelligent agent may carry out millions of actions at the level of reading a word or striking a key. Given computational constraints, it seems that such long-term planning must incorporate reasoning with high-level actions (such as delivering a conference talk or typing a paragraph of a research paper) that abstract over the precise details of their implementations, despite the fact that these details must eventually be determined for the actions to be executed. This multi-level decision-making process is the subject of hierarchical planning.
To most effectively plan with high-level actions, one would like to be able to correctly identify whether a high-level plan works, without first considering its low-level implementations. The first contribution of this thesis is an "angelic" semantics for high-level actions that enables such inferences. This semantics also provides bounds on the costs of high-level plans, enabling the identification of provably high-quality (or even optimal) high-level solutions.
Effective hierarchical planning also requires algorithms to efficiently search through the space of high-level plans for high-quality solutions. We demonstrate how angelic bounds can be used to speed up search, and introduce a novel decomposed planning framework that leverages task-specific state abstraction to eliminate many redundant computations. These techniques are instantiated in the Decomposed, Angelic, State-abstracted, Hierarchical A* (DASH-A*) algorithm, which can find hierarchically optimal solutions exponentially faster than previous algorithms.
@phdthesis{Wolfe2011Dissertation,
Author = {Jason Wolfe},
Title = {Hierarchical Methods for Optimal Long-Term Planning},
School = {EECS Department, University of California, Berkeley},
Year = {2011},
Abstract = {This thesis addresses the problem of generating goal-directed plans involving very many elementary actions. For example, to achieve a real-world goal such as earning a Ph.D., an intelligent agent may carry out millions of actions at the level of reading a word or striking a key. Given computational constraints, it seems that such long-term planning must incorporate reasoning with high-level actions (such as delivering a conference talk or typing a paragraph of a research paper) that abstract over the precise details of their implementations, despite the fact that these details must eventually be determined for the actions to be executed. This multi-level decision-making process is the subject of hierarchical planning.<br/><br/>
To most effectively plan with high-level actions, one would like to be able to correctly identify whether a high-level plan works, without first considering its low-level implementations. The first contribution of this thesis is an "angelic" semantics for high-level actions that enables such inferences. This semantics also provides bounds on the costs of high-level plans, enabling the identification of provably high-quality (or even optimal) high-level solutions.<br/>
Effective hierarchical planning also requires algorithms to efficiently search through the space of high-level plans for high-quality solutions. We demonstrate how angelic bounds can be used to speed up search, and introduce a novel decomposed planning framework that leverages task-specific state abstraction to eliminate many redundant computations. These techniques are instantiated in the Decomposed, Angelic, State-abstracted, Hierarchical A* (DASH-A*) algorithm, which can find hierarchically optimal solutions exponentially faster than previous algorithms.},
url_dissertation = {https://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-138.pdf}
}
Downloads: 0
{"_id":"giwqHKiC7wiGR65Ht","bibbaseid":"wolfe-hierarchicalmethodsforoptimallongtermplanning-2011","authorIDs":[],"author_short":["Wolfe, J."],"bibdata":{"bibtype":"phdthesis","type":"phdthesis","author":[{"firstnames":["Jason"],"propositions":[],"lastnames":["Wolfe"],"suffixes":[]}],"title":"Hierarchical Methods for Optimal Long-Term Planning","school":"EECS Department, University of California, Berkeley","year":"2011","abstract":"This thesis addresses the problem of generating goal-directed plans involving very many elementary actions. For example, to achieve a real-world goal such as earning a Ph.D., an intelligent agent may carry out millions of actions at the level of reading a word or striking a key. Given computational constraints, it seems that such long-term planning must incorporate reasoning with high-level actions (such as delivering a conference talk or typing a paragraph of a research paper) that abstract over the precise details of their implementations, despite the fact that these details must eventually be determined for the actions to be executed. This multi-level decision-making process is the subject of hierarchical planning.<br/><br/> To most effectively plan with high-level actions, one would like to be able to correctly identify whether a high-level plan works, without first considering its low-level implementations. The first contribution of this thesis is an \"angelic\" semantics for high-level actions that enables such inferences. This semantics also provides bounds on the costs of high-level plans, enabling the identification of provably high-quality (or even optimal) high-level solutions.<br/> Effective hierarchical planning also requires algorithms to efficiently search through the space of high-level plans for high-quality solutions. We demonstrate how angelic bounds can be used to speed up search, and introduce a novel decomposed planning framework that leverages task-specific state abstraction to eliminate many redundant computations. These techniques are instantiated in the Decomposed, Angelic, State-abstracted, Hierarchical A* (DASH-A*) algorithm, which can find hierarchically optimal solutions exponentially faster than previous algorithms.","url_dissertation":"https://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-138.pdf","bibtex":"@phdthesis{Wolfe2011Dissertation,\n Author = {Jason Wolfe},\n Title = {Hierarchical Methods for Optimal Long-Term Planning},\n School = {EECS Department, University of California, Berkeley},\n Year = {2011},\n Abstract = {This thesis addresses the problem of generating goal-directed plans involving very many elementary actions. For example, to achieve a real-world goal such as earning a Ph.D., an intelligent agent may carry out millions of actions at the level of reading a word or striking a key. Given computational constraints, it seems that such long-term planning must incorporate reasoning with high-level actions (such as delivering a conference talk or typing a paragraph of a research paper) that abstract over the precise details of their implementations, despite the fact that these details must eventually be determined for the actions to be executed. This multi-level decision-making process is the subject of hierarchical planning.<br/><br/>\n\n To most effectively plan with high-level actions, one would like to be able to correctly identify whether a high-level plan works, without first considering its low-level implementations. The first contribution of this thesis is an \"angelic\" semantics for high-level actions that enables such inferences. This semantics also provides bounds on the costs of high-level plans, enabling the identification of provably high-quality (or even optimal) high-level solutions.<br/>\n\n Effective hierarchical planning also requires algorithms to efficiently search through the space of high-level plans for high-quality solutions. We demonstrate how angelic bounds can be used to speed up search, and introduce a novel decomposed planning framework that leverages task-specific state abstraction to eliminate many redundant computations. These techniques are instantiated in the Decomposed, Angelic, State-abstracted, Hierarchical A* (DASH-A*) algorithm, which can find hierarchically optimal solutions exponentially faster than previous algorithms.},\n url_dissertation = {https://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-138.pdf}\n}\n\n\n","author_short":["Wolfe, J."],"key":"Wolfe2011Dissertation","id":"Wolfe2011Dissertation","bibbaseid":"wolfe-hierarchicalmethodsforoptimallongtermplanning-2011","role":"author","urls":{" dissertation":"https://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-138.pdf"},"metadata":{"authorlinks":{}}},"bibtype":"phdthesis","biburl":"hierarchical-task.net/bibtex/theses-in-hierarchical-planning.bib","creationDate":"2020-04-25T05:04:40.406Z","downloads":1,"keywords":[],"search_terms":["hierarchical","methods","optimal","long","term","planning","wolfe"],"title":"Hierarchical Methods for Optimal Long-Term Planning","year":2011,"dataSources":["YjidmhgCHYRtoZTo6","vY5emPje84NjvCwk9"]}