Building the Case Library

  The following deliberative strategy was adopted for building the case library. When a new problem contains n goals, the first goal is attempted, and, if solved, the case covering this goal alone is stored in the library. Problem-solving continues by increasing the problem size by one goal at a time. For example, if the problem just attempted contained the goal set, $G = \langle g_1, g_2, ..., g_i \rangle$ and was solved through a decision sequence D_i then a second decision sequence, D_i+1, is stored whenever D_i cannot be replayed and extended to achieve the next goal g_i+1. Whenever the replayed derivation path fails, and the recovery phase is successful in producing a new solution, the explanation for the case retrieval failure is used to identify a subset of negatively interacting input goals, $N = \langle g_j ... g_{j+m} \rangle$,that are responsible for the failure. If the replayed path fails to be extended, and is backtracked over to reach a solution to the new problem, then the new successful derivation is passed to the storer along with the failure explanation. The explanation is used to delete from the derivation any decisions which are not relevant to the set of negatively interacting goals, N. This reduced derivation is then stored in the library as the repairing case. Alternatively, whenever the next goal in the set is solved through simple extension of the previous decision sequence, no case is stored which includes that goal.

This storage strategy entails two important properties. (1) Each new case corresponds to either a new single-goal problem or to a multi-goal problem containing negatively interacting goals. (2) All of the plan derivations arising from a single problem-solving episode are different in that no decision sequence stored in the library is a prefix of another stored case. This is because no case is added to the library when a new problem is solved by extending a retrieved case. New cases are stored only when some of the previous decisions need to be backtracked over in the search for a new solution.

DERSNLP+EBL's strategy of restricting multi-goal cases to those with goals which are negatively interacting serves to ameliorate the mis-retrieval problem. The more experience that the planner has in problem-solving, the more of these interactions are discovered, and the less likely it is that the planner has to backtrack over its replayed paths. The aim is to eventually have in the library a minimal number of cases such that all of the problems encountered may be achieved by successfully merging multiple instances of stored cases. The approach is therefore to retain cases based on their competence as well as their performance [37].

  

Figure 13: A logistics transportation example illustrating multi-case storage. The figure shows two plans produced by two stored derivations. Case A achieves the goal of having a single packages, OB1, transported to the destination airport, l_d. Case B achieves the goal of having OB1 and OB2 located at the same airport.