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, , 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, , if there is a plan P' which is correct for 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).

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.

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.

 DERSNLP+EBL DERSNLP+EBL-IJ replay scratch replay scratch %Solved 87%(6) 67%(5) 87%(7) 67% (5) time(sec) 2465 5796 2198 5810

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

11/5/1997