3.4.2 Facilitating Algorithmic Plan Construction

For many domains, simple domain-dependent approximation algorithms will provide good initial plans. For example, in the query planning domain, the system can easily generate initial query evaluation plans by randomly (or greedily) parsing the given query. In the Blocks World it is also straightforward to generate a solution in linear time using the naive algorithm: put all blocks on the table and build the desired towers from the bottom up. This algorithm produces plans of length no worse than twice the optimal, which makes it already a good approximation algorithm. However, the interest in the Blocks World has traditionally been on optimal solutions, which is an NP-hard problem [38].

Our system facilitates the creation of these initial plans by freeing
the user from specifying the detailed graph structure of a plan. The
user only needs to specify an algorithm that produces a sequence of
instantiated actions, that is, action names and the ground parameters
that each action takes.^{12}
For example, the (user-defined) naive algorithm for the Blocks World
domain described above applied to the problem in Figure 4
produces the sequence: `unstack(C A)`, `unstack(B D)`, `stack(C D Table)`, `stack(B C Table)`, and `stack(A B Table)`.
Then, the system automatically converts this sequence of actions into
a fully detailed partial-order plan using the operator specification
of the domain.
The resulting plan conforms to the internal data structures that PbR
uses. This process includes creating nodes that are fully detailed
operators with preconditions and effects, and adding edges that
represent all the necessary causal links and ordering constraints.
In our Blocks World example the resulting plan is that of
Figure 4.

The algorithm that transforms the user-defined sequence of actions into a partial-order plan is presented in Figure 17. The algorithm first constructs the causal structure of the plan (lines 2 to 6) and then adds the necessary ordering links to avoid threats (lines 7 to 10). The user only needs to specify action names and the corresponding instantiated action parameters. Our algorithm consults the operator specification to find the preconditions and effects, instantiate them, construct the causal links, and check for operator threats. Operator threats are always resolved in favor of the ordering given by the user in the input plan. The reason is that the input plan may be overconstrained by the total order, but it is assumed valid. Therefore, by processing each step last to first, only the orderings that indeed avoid threats are included in the partial-order plan.

Our algorithm is an extension of the greedy algorithm presented by
Veloso, Perez, & Carbonell [81]. Our algorithm
explores non-deterministically all the producers of a proposition
(line 3), as opposed to taking the latest producer in the sequence as
in their algorithm.^{13}
That is, if our algorithm is explored exhaustively, it produces all
partially-ordered causal structures consistent with the input
sequence. Our generalization stems from the criticism by
Bäckström [13] to the algorithm by
Veloso et al. [81] and our desire of being
able to produce alternative initial plans.

The problem of transforming a sequence of steps into a least constrained plan is analyzed by Bäckström [13] under several natural definitions of optimality. Under his definitions of least-constrained plan and shortest parallel execution the problem is NP-hard. Bäckström shows that Veloso's algorithm, although polynomial, does not conform to any of these natural definitions. Because our algorithm is not greedy, it does not suffer from the drawbacks pointed out by Bäckström. Moreover, for our purposes we do not need optimal initial plans. The space of partial orders will be explored during the rewriting process.

Regardless of the method for producing initial plans, generators that provide multiple plans are preferable. The different initial plans are used in conjunction with multiple restart search techniques in order to escape from low-quality local minima.