next up previous
Next: An Empirical Test of Up: Improving Case Storage and Previous: A Detailed Example of

Multi-case Merging


We say that two plans are mergeable with respect to a problem, $\langle I' , G' , {\cal A} \rangle$, if there exists a solution to the problem which contains all of their combined constraints.

Definition 2 (Mergeability)

A plan P1 for achieving goal g1 is mergeable with a plan P2 for the goal g2 with respect to a problem, $\langle I' , G' , {\cal A} \rangle$, if there is a plan P' which is correct for $\langle I' , G' , {\cal A} \rangle$ and the candidate set of P' is a subset of the intersection of the candidate sets of P1 and P2. (Thus syntactically, P' contains all the constraints of P1 and P2).

Figure 16: New linking opportunities indicated by an increase in the number of siblings of the step addition decision.

Multi-case replay accomplishes plan merging, but may result in lower quality plans if care is not taken to avoid redundant step additions [17,33]. These occur when goals covered by separate cases positively interact in that they may be solved through common steps. Replaying each case in sequence then results in unneeded steps in the plan[*].

In multi-case replay, if an open condition is the only justification for adding a new step, some steps may be added which already exist in the plan due to the earlier replay of another case. When the first retrieved derivation is replayed, none of its replayed step additions will result in redundancy. However, when subsequent goals are solved through replay of additional cases, some step additions may be unnecessary in that there are opportunities for linking the open conditions they achieve to earlier established steps. The planner has no way of determining a priori that these steps may be represented by a single step in the plan[*].

DERSNLP+EBL's replay framework handles redundant step additions by skipping over step addition establishments whenever the open condition may be achieved by a new link. It thus strengthens or increases the justification for replaying step addition decisions in that the open condition is no longer the only basis for validating the decision. The justification for replay is strengthened to add the condition that no new linking opportunities are present. These may be detected as an increase in the number of siblings of the prescribed step addition choice (See Figure 16). The siblings of the stored step addition decision are recorded as annotations on the derivation trace. When new links are available which are not contained within these siblings, the step addition decision is skipped. After replay, the alternative new links are explored through the normal course of plan refinement. This means that the same step may eventually be added if the new links fail.

Increasing the justification for the step addition decisions improves the quality of plans in terms of the number of steps they contain. For example, Case B and B' would normally produce subplans which are shown in Figure 15. When these cases are replayed in sequence in solving a single problem, their plans are merged so that the plane moves to each city only once. Plan merging through increasing the justification for replay accomplishes the retracting out of redundant action sequences, which may cause a planning failure. It thus deals with the action-merging interactions defined in [44]. In the next section we describe an empirical study testing the effectiveness of this merging strategy.

Table 3: Percentage problems solved, total CPU time in seconds on all 30 problems for problems in the Logistics Transportation Domain. Average solution length is shown in parentheses next to %Solved.
  replay scratch replay scratch
%Solved 87%(6) 67%(5) 87%(7) 67% (5)
time(sec) 2465 5796 2198 5810

next up previous
Next: An Empirical Test of Up: Improving Case Storage and Previous: A Detailed Example of