Deriving subgoal ordering constraints prior to problem solving and planning.
Jie Cheng · Deep Blue (University of Michigan) · 1991
Subgoal ordering is an important search control strategy in planning and problem solving. Failure to properly order problem subgoals may result in less optimal problem solutions, may cause otherwise avoidable backtracking in search, and may even preclude a solution to a problem at all in problem solving. In this thesis, a methodology to subgoal ordering is presented. The thrust of this methodology is the development of a set of relational formulations that lend themselves to the characterization of various types of subgoal ordering constraints, based solely on basic problem model parameters. Using these formulations, we are able to identify a unique set of subgoal ordering constraints that exist independent of initial states and independent of specific ways problems are solved. In addition, we are able to investigate the properties of such constraints independent of any specific implementation. By taking advantage of these properties, procedures are then developed which can guarantee to derive the subgoal ordering constraints prior to planning or problem solving. To increase the utility of this subgoal ordering approach, an extension has been made to generalize ordering constraints derived for any problem so that it can be applied to many other problem instances. This generalization includes variablizing subgoal conditions that are constrained in the order of their achievements, and then, finding a sufficient condition for the ordering constraint to be applicable. Since the objective of ordering subgoals is to reduce search in planning or problem solving, it is investigated in this thesis how to effectively incorporate derived subgoal ordering constraints with heuristic problem solvers and planners. Several domain-independent problem solvers and planners are analyzed. For each of them, its weakness in handling subgoal ordering constraints is identified and then a strategy is devised. Empirical results are given to show the performance improvements of these systems after subgoal ordering constraints are incorporated.