An Example of DERSNLP+EBL's Storage Strategy

As an example of how a multi-goal problem is stored, consider the problem contained in Figure 13 where three packages, OB1, OB2 and OB3, are to be transported to the same destination location, l_d. Initially the goal set contains the goal of transporting OB1 alone, represented as (AT-OB OB1 l_d), and the successful derivation is stored as Case A. The second goal is then added to the set. Since the problem just attempted achieves the first goal through a decision sequence which has to be backtracked over in order to solve the additional goal, a second derivation, Case B, is stored. This new derivation then solves the mutually interacting goals, (AT-OB OB1 l_d) and (AT-OB OB2 l_d). Problem-solving then continues with the addition of the third goal. This goal is solved through simple extension of the previous decision sequence. No case is stored which includes this goal. This means that we have two cases stored in the library: Case A corresponding to a single-goal problem and Case B corresponding to a multi-goal problem containing two negatively interacting goals. Multi-goal problems are stored only when the problem goals are mutually interacting, that is, only when their individual derivations cannot be sequenced and extended to solve the full problem.

With DERSNLP+EBL's storage strategy, the size of the library is limited by the amount of interaction in the domain. For example, if there is no negative interaction, then only single goal cases will be stored. In the logistics transportation domain, there is a potential for all problem goals to interact negatively. However, since there are also a significant percentage of non-interacting goals, this strategy reduces the size of the library in comparison to one in which all of the multi-goal problems which are successfully solved are stored. This storage strategy also represents a tradeoff since effort must be expended in merging the retrieved cases into a full solution (See Section 3.3).

  

Figure 14: A Library fragment indexing stored cases which solve a single input goal, (AT-OB OB1 l_d).