Analyzing the Failure of Case Extension

 

In order for the skeletal plan to be successfully extended to achieve any conditions left open, the sequence of decisions that were adopted through the guidance of a previous trace must be concatenated with further choices to arrive at a solution. For this to occur, the replayed path must be decision-sequencable with respect to the new problem, which is defined as follows:

  

Figure 8: The specification of Barrett and Weld's Transformed D^m S¹Domain

Definition 1 (Decision-Sequencable Search Path)

A search path which contains a sequence of decisions D is decision-sequencable with respect to a new problem, $\langle I' , G' , {\cal A} \rangle$ , if and only if there exist two decision sequences E and E' such that $E \bullet D \bullet E'$ (where ``$\bullet$'' is the decision sequencing operator) will produce a plan which is correct for $\langle I' , G' , {\cal A} \rangle$.

One of the primary reasons a replayed path may not be decision sequencable is the goal interactions that occur between the input goals of the new problem. In particular, the extra goals not achieved by a case may interact with those that are covered, making the retrieved case inapplicable. It has long been recognized that the relative difficulty of problem-solving is linked to the level of interaction between the various input goals of the problem [27,18,2,41,23]. Goal interaction has been formalized by Korf [27] in terms of the problem search space. Barrett and Weld [2] extend Korf's analysis into plan space. For the plan-space planner, the order in which goals are achieved is not as crucial. Goals that are laboriously serializable for a state-space planner (in that there exist few goal orderings for which the goals may be solved in sequence) may be trivially serializable for a plan-space planner (meaning that the goals can be solved in any order).

However, goals are not always trivially serializable for the plan-space planner [41]. For example, consider the $\theta _2 D^m S^1$ domain [2] shown in Figure 8. Notice that if $g_\alpha$is one of a set of problem goals, and it is not true initially, then any other goal, g_i, that is present in the set must be achieved by the operator $A^\alpha_i$, and not by $A^\beta_i$. This means that any time a case is replayed that previously solved a goal, g_i, through an action $A^\beta_i$, and $g_\alpha$ is an extra goal not covered by the case, replay will fail.

In CBP, however, we are not so much concerned with the general properties of the domain, as we are with properties of the particular search paths which are stored in the case library. It is not required that the input goals of every problem be trivially serializable for CBP to be beneficial to planning performance. If it were, there would be very few domains in which CBP was effective. Trivial serializability is not a requirement since it is not necessary that every plan for every subset of the input goals be consistent with a solution to the full problem. It is only the particular plans that are retrieved from the library that we are concerned with.

Even if the goals of the problem are not trivially serializable, replay may be decision sequencable, depending on which cases are actually retrieved from the library. In the $\theta _2 D^m S^1$ domain, if the single-goal cases that are retrieved solve g_i through the action $A^\beta_i$, then these will not be decision-sequencable with any new multi-goal problem which contains the goal $g_\alpha$.However if the stored cases are solved through $A^\alpha_i$,then replay of these cases will be sequencable. In fact, the aim of the DERSNLP+EBL's learning component is to achieve an indexing within the case library such that all of the new problems encountered by the planner may be solved through sequenced replay of the cases retrieved from that library. The next section describes how DERSNLP+EBL is able to work towards this objective through its learning component which learns from replay failures.