Before implementing this strategy, decisions had to be made as to which goal combinations to store. In previous work within state-space planning Veloso [40] has developed an approach to reducing the size of the library by first transforming a totally ordered plan into a partially ordered graph, separating out connected components of the graph, and storing these subplans individually. Goals which interact in that their respective plans must be interleaved in order to form a complete solution are stored together as a single case. When replay is based on a plan-space planner such as SNLP, a component subplan may be further subdivided, since the planner has the ability to first piece plans together, and later add step orderings to interleave these subplans [21,15]. Replay of these smaller cases will be sequenced as long as their individual subplans may be interleaved by the addition of step orderings to form a full solution. The plan-space planner therefore has a greater capability of reducing the size of the problems stored in the library, and, as a consequence, the number of cases stored.
DERSNLP+EBL's storage strategy makes use of the plan-space planners' ability
to piece small plans together, then add step orderings to interleave
these plans. As in earlier approaches, such as
PRIAR [22],
PRODIGY/ANALOGY [40] and
CAPLAN [32], the cases that are stored
cover smaller subsets of the original set of input goals achieved in the
successful problem-solving episode.
DERSNLP+EBL differs
from these earlier approaches
in that the division into goal subsets is not
based on the structure of the final plan alone,
but on the sequence of events
making up the problem-solving episode.
A new repairing case is stored if
the cases which were retrieved from the library
in solving the new problem fail to be extended into a new solution.
The storer constructs a new case based
on the failure explanation which was obtained through
the extension phase as well as the new successful plan derivation
obtained during recovery.
The failure explanation identifies the set of negatively interacting goals responsible for the failure. These goals form a subset of the input goals which are achieved in the new solution. Before the repairing case is stored, the new plan derivation is stripped of any decisions that are irrelevant to the achievement of these interacting goals. The new case then covers only the negatively interacting goals.
Note that we define negative interaction based on the failure of the skeletal plan. An interaction occurs when a set of input goals cannot be solved by refining the skeletal plan, causing the planner to have to backtrack over this plan. Moreover, we cannot determine whether two goals are negatively interacting merely by analyzing the final solution. It does not include information about the planning failures which were encountered in generating the solution. In particular, the final solution does not tell us whether an additional goal was achieved by extending the replayed path, or by backtracking over that path. Approaches to case storage which determine goal interaction from the final plan alone [40,32] therefore ignore the retrieval failures that have been encountered during the planning episode.
Retrieval failures provide important guidance as to how the library may be improved to avoid similar failures. For DERSNLP+EBL, they are used to dynamically improve the storage in the library through the addition of new goal combinations. Multi-goal problems are stored when retrieved cases corresponding to single-goal subproblems fail to be merged and extended into a new solution. Repairing cases are constructed which achieve the negatively interacting goals which are responsible and which are identified in the failure explanation.