Cost-Optimal Algorithms for Planning with Procedural Control Knowledge
  There is an impressive body of work on developing heuristics and other
reasoning algorithms to guide search in optimal and anytime planning algorithms
for classical planning. However, very little effort has been directed towards
developing analogous techniques to guide search towards high-quality solutions
in hierarchical planning formalisms like HTN planning, which allows using
additional domain-specific procedural control knowledge. In lieu of such
techniques, this control knowledge often needs to provide the necessary search
guidance to the planning algorithm, which imposes a substantial burden on the
domain author and can yield brittle or error-prone domain models. We address
this gap by extending recent work on a new hierarchical goal-based planning
formalism called Hierarchical Goal Network (HGN) Planning to develop the
Hierarchically-Optimal Goal Decomposition Planner (HOpGDP), an HGN planning
algorithm that computes hierarchically-optimal plans. HOpGDP is guided by
$h_{HL}$, a new HGN planning heuristic that extends existing admissible
landmark-based heuristics from classical planning to compute admissible cost
estimates for HGN planning problems. Our experimental evaluation across three
benchmark planning domains shows that HOpGDP compares favorably to both optimal
classical planners due to its ability to use domain-specific procedural
knowledge, and a blind-search version of HOpGDP due to the search guidance
provided by $h_{HL}$.
