To appear, AAAI-99 Using Planning Graphs for Solving HTN Planning Problems

In this paper we present the GraphHTN algorithm, a hybrid planning algorithm that does Hierarchical Task-Network (HTN) planning using a combination of HTNstyle problem reduction and Graphplan-style planninggraph generation. We also present experimental results comparing GraphHTN with ordinary HTN decomposition (as implemented in the UMCP planner) and ordinary Graphplan search (as implemented in the IPP planner). Our experimental results show that (1) the performance of HTN planning can be improved significantly by using planning graphs, and (2) that planning with planning graphs can be sped up by exploiting HTN control knowledge