New Advances in GraphHTN: Identifying Independent Subproblems in Large HTN Domains

摘要

We describe in this paper a new method for extracting knowledge on Hierarchical Task-Network (HTN) planning problems for speeding up the search. This knowledge is gathered by propagating properties through an AND/OR tree that represents disjunctively all possible decompositions of an HTN planning problem. We show how to use this knowledge during the search process of our GraphHTN planner, to split the current refined planning problem into independent subproblems. We also present new experimental results comparing GraphHTN with ordinary HTN decomposition (as implemented in the UMCP planner). The comparison is performed on a set of problems from the UM Translog domain - a large HTN transportation domain that is considerably more complicated than the well known "logistics" domain. Finally, so that we could compare GraphHTN with action-based planners such as IPP and Blackbox, we translated the UM Translog domain into a STRIPS-style representation. We found that GraphHTN performed considerably better on UM Translog than IPP and Blackbox.