Fast initial plan generation is domain-specific in nature. It requires the user to specify an efficient mechanism to compute the initial solution plan. In general, generating an initial plan may be as hard as generating the optimal plan. However, the crucial intuition behind planning algorithms is that most practical problems are quasi-decomposable [77], that is, that the interactions among parts of the problems are limited. If interactions in a problem are pervasive, such as in the 8-puzzle, the operator-based representation and the algorithms of classical planning are of little use. They would behave as any other search based problem solver. Fortunately, many practical problems are indeed quasi-decomposable. This same intuition also suggests that finding initial plan generators for planning problems may not be as hard as it appears, because the system can solve the subproblems independently, and then combine them in the simplest way, for example, concatenating the solutions sequentially. Moreover, in many circumstances the problems may be easily transformed into a state that minimizes the interactions and solving the problem from this state is much easier. For example, in the Blocks World the state in which all blocks are on the table minimizes the interactions. It is simple to design an algorithm that solves any Blocks World problem passing through such intermediate state. Using these methods an initial plan generator may produce suboptimal initial plans but at a reasonable planning cost.
These ideas for constructing initial plan generators can be embodied in two general ways, which are both implemented in our system. The first one is to bootstrap on the results of a general purpose planning algorithm with a strong search control bias. The second one is to provide the user convenient high-level facilities in which to describe plan construction algorithms programmatically.