Jason Wolfe

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2011-138

December 15, 2011

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-138.pdf

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.

Advisors: Stuart J. Russell

---

BibTeX citation:

@phdthesis{Wolfe:EECS-2011-138,
    Author= {Wolfe, Jason},
    Title= {Hierarchical Methods for Optimal Long-Term Planning},
    School= {EECS Department, University of California, Berkeley},
    Year= {2011},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-138.html},
    Number= {UCB/EECS-2011-138},
    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.

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.},
}

EndNote citation:

%0 Thesis
%A Wolfe, Jason 
%T Hierarchical Methods for Optimal Long-Term Planning
%I EECS Department, University of California, Berkeley
%D 2011
%8 December 15
%@ UCB/EECS-2011-138
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-138.html
%F Wolfe:EECS-2011-138