Goal Ordering in Partially Ordered Plans

Abstract

Partially ordered plans have not solved the goal ordering problem. Consider: a goal in a partially ordered plan is an operator precondition that is not yet achieved; operators, orderings and variable bindings are introduced to achieve such goals. While the planning community has known how to achieve individual goals for some time, there has been little work on the problem of which one of the many possible goals the planner should achieve next. This paper argues that partially ordered plans do not usefully address the goal-ordering problem and then presents a heuristic called temporal coherence which does. Temporal coherence is an admissible heuristic which provides goal-ordering guidance. Temporal coherence is admissible in the sense that if a solution exists in the planner's search space, then there will be a series of goal achievements permitted by the heuristic which can produce this solution. 1