Accelerating Partial Order Planners by Emphasizing Deductive Choices

We describe some simple domain-independent improvements to plan-refinement strategies for well-founded partial order planning that promise to bring this style of planning closer to practicality. One suggestion concerns the strategy for selecting plans for refinement among the current (incomplete) candidate plans. We propose an A* heuristic that counts only steps and open conditions, while ignoring ‘unsafe conditions’ (threats). A second suggestion concerns the strategy for selecting open conditions (goals) to be established next in a selected incomplete plan. Here we propose giving top priority to unmatchable conditions (enabling the elimination the plan), and second-highest priority to goals that can only be achieved uniquely, through a new step or through the initial conditions. This a ‘zero-commitment’ strategy in the sense that the corresponding plan refinement is a matter of deductive certainty, involving no guesswork. In experiments based on modifications of UCPOP, we have obtained improvements by factors ranging from 5 to several hundred for a variety of problems that are nontrivial for the unmodified version, with the hardest problems giving the greatest improvement