** Next:** 3.4.1 Biased Generative Planners
** Up:** 3 Planning by Rewriting as Local Search
** Previous:** 3.3 Plan Quality

##

3.4 Initial Plan Generation

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.

**Subsections**

** Next:** 3.4.1 Biased Generative Planners
** Up:** 3 Planning by Rewriting as Local Search
** Previous:** 3.3 Plan Quality
Jose-Luis Ambite
2001-08-09