Cost-Optimal Algorithms for Planning with Procedural Control Knowledge
This work addresses the problem of improving planning efficiency and robustness for domain authors in hierarchical planning, though it is incremental as it extends existing formalisms and heuristics.
The paper tackles the lack of search guidance techniques in hierarchical planning formalisms like HTN planning, which burdens domain authors and leads to brittle models, by developing HOpGDP, a Hierarchically-Optimal Goal Decomposition Planner that uses a new admissible heuristic $h_{HL}$; experimental results show it compares favorably to optimal classical planners and a blind-search version in three benchmark domains.
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}$.