next up previous
Next: 4 Empirical Results Up: 3.4 Initial Plan Generation Previous: 3.4.1 Biased Generative Planners


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.

Figure 17: Algorithm for Converting Total-order to Partial-order Plans
\begin{figure}\hrule\begin{tabbing}
{\bf procedure} TO2PO \\
{\em Input}: a val...
...
11. {\bf return} (($a_1$, ..., $a_n$), $\prec$)
\end{tabbing}\hrule\end{figure}

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.


next up previous
Next: 4 Empirical Results Up: 3.4 Initial Plan Generation Previous: 3.4.1 Biased Generative Planners
Jose-Luis Ambite 2001-08-09