The failure explanation shown in Figure 11 identifies a subset of interacting goals, made up of g8 and .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, and .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 appears in only two cases, one representing the single-goal problem and one representing a two goal problem which also achieves .
Storing only negatively interacting goals as multi-goal problems
may therefore result in a substantial reduction in the size of the
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,
complex domains, there may be goals which
interact positively in that they may be solved through common
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
In Section 3.3 we describe how this merging is
The next section provides more detail as to the case storage
strategy which has been implemented for our empirical study.