Characterizing Subgoal Interactions for Planning

Abstract

Korf's taxonomy of subgoal interactions [5] fails to differentiate between classes that have vastly different computational properties; in particular, some sets of serializable goals are easy to solve while others are difficult . We present a predictive theory of planner performance based on the number of feasible serialization orderings. The central notions are the classes of TRIVIALLY SERIALIZABLE and LABORIOUSLY SERIALIZABLE subgoals which are tractable and difficult respectively. To illustrate our theory, we compare the interaction structure of three planners. We demonstrate a domain whose structure is trivially serializable for a partial order planner, laboriously serializable for a total order planner, and nonserializable for a world-state, regression planner. As predicted, only the partial order algorithm could plan for this domain . We conclude that our theory is partially confirmed.