An Example of a Negative Interaction

Figure 11

  

Figure 11: An Example of a case failure reason

provides an example of an explanation for failure encountered when solving a problem from Barrett and Weld's $\theta _2 D^m S^1$ domain shown in figure 8. The problem contains three goals, $g_\alpha$, g₆ and g₈, and has been attempted through replay of a case which solves two of these goals, $g_\alpha$ and g₆, and a second case, which achieves only g₈. In the latter, the goal was achieved through the action $A^\beta_8$ which represents an incorrect operator choice when the input goals of the problem include the goal $g_\alpha$.

The failure explanation shown in Figure 11 identifies a subset of interacting goals, made up of g₈ and $g_\alpha$.Note that this interaction is not evident in the final plan shown in Figure 12. In this plan, the three input goals of the problem are achieved through the same connected component. If we base storage solely on the plan graph represented by the successful plan, then all three input goals will be stored in a single case. Moreover, each new problem representing a novel combination of goals will be stored in the library, causing the library size to increase exponentially with problem size. For example, suppose the domain includes the goals, $\{g_i \vert 1 < i < n \}$ and $g_\alpha$.Then the number of problems of size three will be the number of 3-goal subsets of these n + 1 goals. DERSNLP+EBL's strategy of storing cases based on explanations of retrieval failure will result in a maximum of 2n + 1 cases stored. Each goal $\{g_i \vert 1 < i < n \}$ appears in only two cases, one representing the single-goal problem and one representing a two goal problem which also achieves $g_\alpha$.

Storing only negatively interacting goals as multi-goal problems may therefore result in a substantial reduction in the size of the case library. It also represents a tradeoff, as the replayed cases must be extended by from-scratch planning to solve conflicts between the individual plans recommended by separate cases. Moreover, in more complex domains, there may be goals which interact positively in that they may be solved through common steps [17,33]. If these goals are stored as separate cases, then replay may result in unnecessary redundancy in the plan. In DERSNLP+EBL, these positive interactions are handled through the replay process itself, which merges the subplans provided by multiple cases. In Section 3.3 we describe how this merging is accomplished. The next section provides more detail as to the case storage strategy which has been implemented for our empirical study.

  

Figure 12: A Solution to the example problem.