HTN-MAKER: Learning HTNs with Minimal Additional Knowledge Engineering Required

Abstract

We describe HTN-MAKER, an algorithm for learning hier-archical planning knowledge in the form of decomposition methods for Hierarchical Task Networks (HTNs). HTN-MAKER takes as input the initial states from a set of clas-sical planning problems in a planning domain and solutions to those problems, as well as a set of semantically-annotated tasks to be accomplished. The algorithm analyzes this se-mantic information in order to determine which portions of the input plans accomplish a particular task and constructs HTN methods based on those analyses. Our theoretical results show that HTN-MAKER is sound and complete. We also present a formalism for a class of plan-ning problems that are more expressive than classical plan-ning. These planning problems can be represented as HTN planning problems. We show that the methods learned by HTN-MAKER enable an HTN planner to solve those prob-lems. Our experiments confirm the theoretical results and demonstrate convergence in three well-known planning do-mains toward a set of HTN methods that can be used to solve nearly any problem expressible as a classical planning prob-lem in that domain, relative to a set of goals.