Indexing on the Basis of Replay Failure

  Multi-goal cases are stored in the library so as to censor the retrieval of their corresponding single-goal subproblems. This library organization differs from earlier work which stores all cases in a common fashion on a single level, first indexing each case by all of the goals, then by all of the success conditions relevant to these goals [40,32]. In contrast, DERSNLP+EBL indexes its cases through a discrimination net similar to the one depicted in Figure 14. This figure shows one fragment of the case library which includes all of the cases which solve a single input goal. Individual planning episodes which achieve this goal are represented one level lower in the net. Each is labeled by its relevant initial state conditions, otherwise known as the footprinted initial state [40]. Together, the goal and initial state conditions make up the static success conditions on which cases are first retrieved. When one of these cases is retrieved for replay and replay fails, the derivation corresponding to the extra interacting goals is added to the library and indexed directly under the failing case. On future retrievals of the case, the failure conditions are checked to see whether the extra goals responsible for the failure are present under the same conditions. If so, the retrieval process returns the repairing case which achieves these conflicting goals. The case failure reason is thus used to direct retrieval away from the case which will repeat a known failure, and towards the case that avoids it.

One might question this hierarchical organization in instances where failures are due to interacting goals alone. Why not just store all cases on a single level first indexing each case by all of its goals, then by the conditions relevant to all of these goals? The answer lies in the need to censor cases when failure conditions are satisfied. This type of error will be found when retrieving multiple cases. As an example, consider that our new problem contains three goals, g₁, g₂ and g₃. Suppose further that the goal g₂ negatively interacts with both g₁ and g₃. If a case is retrieved from the library which achieves both g₁ and g₂, then one goal, g₃, is left open. However, if a case is then retrieved which solves g₃ alone, it will fail because of the presence of g₂. This type of retrieval error is handled by prioritizing cases. A repairing case is stored as a subclass of the case that failed. Failing cases are annotated with the failure reason which directs the retriever to the case that avoids the failure.

Prioritizing cases on the basis of negatively interacting goals alone is not sufficient to capture all of the retrieval failures that may be encountered. If cases are retrieved on the basis of a partial match of the relevant initial state conditions, then retrieval errors may occur because of unmatched conditions [40]. For example, just as a failure might occur in our logistics transportation example if there is an extra package off the plane's route, a similar failure will occur if a package is moved off the plane's route. The strategy that is adopted to deal with both types of failure information is to annotate the case with the failure reason (whether it is an extra goal or an unmatched initial state condition) and use the failure reasons to prioritize cases. The EBL techniques that we have employed in the construction of failure explanations may be used for both types of failures.

DERSNLP+EBL's method of storing multi-goal cases only when goals are negatively interacting limits the size of the case library. Other aspects of DERSNLP+EBL's storage strategy also serve to lower library size. The planner always uses its current library in solving new problems. New derivations are stored only when there is no applicable case, or when the retrieved cases fail. This strategy avoids the storage of duplicate cases, but may not be entirely effective since the soundness of failure explanations is not guaranteed. If failure explanations are not sound, pointers to repairing cases may eventually lead to a duplicate case, causing the library to continue to grow indefinitely. However, this is easily checked by putting a depth limit on the number of repairing cases in the discrimination net. Also, failures which are due to interacting goals will not result in unchecked growth of the library since the number of interacting goals is limited by the maximum problem size.