AN ORDERING ON SUBGOALS FOR PLANNING

Subgoal ordering is a type of control information that has received mu ch attention in AI planning community. In this paper we formulate prec isely a subgoal ordering in the situation calculus. We show how inform ation about this subgoal ordering can be deduced from the background a ction theory. We also show for both linear and nonlinear planners how knowledge about this ordering can be used in a provably correct way to avoid unnecessary backtracking.