next up previous
Next: An Example of a Up: Storing and Indexing Plan Previous: Experimental Results

Improving Case Storage and Adaptation

  The aim of case-based planning is to efficiently solve large problems in complex domains. A complex domain means a great variety in the problems encountered. When problem size (measured in terms of the number of goals, n) is large, it is unlikely that the same n-goal problem will have been seen before. It is therefore an advantage to be able to store cases covering smaller subsets of goals, and to retrieve and adapt multiple cases in solving a single large problem.

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.



 
next up previous
Next: An Example of a Up: Storing and Indexing Plan Previous: Experimental Results

11/5/1997