The GoDeL planning system: a more perfect union of domain-independent and hierarchical planning

Abstract

One drawback of Hierarchical Task Network (HTN) planning is the difficulty of providing com-plete domain knowledge, i.e., a complete and cor-rect set of HTN methods for every task. To pro-vide a principled way to overcome this difficulty, we define a simple formalism that extends classical planning to include problem decomposition using methods, and a planning algorithm based on this formalism. In our formalism, the methods specify ways to achieve goals (rather than tasks as in conven-tional HTN planning), and goals may be achieved even when no methods are available. Our plan-ning algorithm, GoDeL (Goal Decomposition with Landmarks), is sound and complete irrespective of whether the domain knowledge (i.e., the set of methods given to the planner) is complete. By comparing GoDeL’s performance with vary-ing amounts of domain knowledge across three benchmark planning domains, we show experimen-tally that (1) GoDeL works correctly with partial planning knowledge, (2) GoDeL’s performance im-proves as more planning knowledge is given, and (3) when given full domain knowledge, GoDeL matches the performance of a state-of-the-art hier-archical planner. 1