Technical Report No. 89, April 1997 - Abstract

Nebel, Bernhard; Dimopoulos, Yannis; Koehler, Jana:
Irrelevant Facts and Operators in Plan Generation

It is traditional wisdom that one should start from the goals when generating a plan in order to focus the plan generation process on potentially relevant actions. The Graphplan system, however, which is the most efficient planning system nowadays, builds a ``planning graph'' in a forward-chaining manner. Although this strategy seems to work well, it may possibly lead to problems if the planning task description contains irrelevant information. Although some irrelevant information can be filtered out by Graphplan, most cases of irrelevance are not noticed.

In this paper, we analyze the effects arising from ``irrelevant'' information to planning task descriptions for different types of planners. Based on that, we propose a family of heuristics that select relevant information by minimizing the number of initial facts that are used when approximating a plan by backchaining from the goals ignoring any conflicts. These heuristics, although not solution-preserving, turn out to be very useful for guiding the planning process, as shown by applying the heuristics to a large number of examples from the literature.