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.