The organization of a memory should reflect its function. The content of the objects stored in memory, the vocabulary used to index those objects and the features used to search for them should rise out of the needs of the process that ultimately uses them.
A case-based planner's memory has four separate organizations, serving different processes and functions. These are:
Plan library
The first component of a case-based planner's memory of plans is the plans themselves. These plans are represented as a fully ordered set of steps at the level of the planner's primitive actions.
Each plan is also defined as being a particular type of plan, a plan for a certain type of object. This information does not limit the types of steps that can be included in the plan, it only defines the class of results, the class of goals that the plan is expected to satisfy.
As for the CHEF system, the definition of a plan basically includes its ingredients, its steps, and the type of plan it is (Ex: figure 3.1 page 73).
Every plan in memory has a set of goals associated with it that is generated from both the specific ingredients in the current plan and general role information on the plan type. The latter kind of goals are inferred from the knowledge about the requirements of the general dish type of the plan. Ex: CHEF's knowledge about stir-fry plans, for example, includes the fact that all vegetables should end up crisp, each piece should be no larger than a certain size and that the dish in general should take on the taste of the major spices. This default information allows the planner to infer the presence of goals that may not have been specified in the original request.
Plans also have links to any failures that occurred while they were being built. These links are attached to plans that have failed and have been repaired to now avoid those failures. Every plan has knowledge of the goals it satisfies and the problems it avoids.
A set of plans is useless if they are not organized so that they can be accessed at the appropriate times. So, in addition to plans themselves, we need a memory organization. Given that the primary task of building plans is to achieve their goals, it seems straightforward to index plans in memory by goals they satisfy. In general, there should be a link between the planner's different goals and the plans that satisfy them (figure 3.2 page 76).
However, it is often the case that a planner has to plan for many goals at once and has to find a single plan that satisfies a set of goals rather than just one. The memory of a case-based planner has to be designed so that multiple keys can be used in combination to find plans in memory. One way to implement a memory that uses a set of features to index to the objects it stores is through a discrimination net (figure 3.3 page 77). CHEF's plan memory is implemented as a discrimination net of plans in which the discriminators are the goals that each plan satisfies.
Similarity metric
If a plan to satisfy a particular goal cannot be found, CHEF searches for one that satisfies a similar goal.
To make similarity judgments between goals, a case-based planner tries to find goals of the same type that have similar features. In matching goals, it first looks at those features which it has experienced as being problematic. Ex: Given the goal "stir-fried shrimp", it chooses "stir-fried fish" and "stir-fried beef" over "steamed shrimp" because they have the same type "stir-fry". It then compares fish and beef against shrimp considering features, such as, TASTE, TEXTURE, SIZE, and COLOR. These features are presorted based on the planner's experience about which should be discriminated off of first.
Value metric
To decide between two plans that satisfy the same number of different
goals, a case-based planner needs some way to determine the relative utility
of the goals it fully satisfies. This value metric is based on how
much more work the planner needs to incorporate into an existing plan so
that it satisfies all the goals. Given a set of goal, it first tries
to satisfy them in the order of their difficulty of being satisfied, and
works its way to easier ones. Ex: Given the goal "stir-fried beef
and broccoli" and that two candidate plans are "stir-fried broccoli with
tofu" and "stir-fried beef with green beans". Since the meat in a
stir-fry dish usually determines the seasoning, the latter is the
right choice in this situation because it is easier to substitute green
beans with broccoli than to substitute tofu with beef and change seasonings.
A case-based planner's plan memory organizes plans by the goals they satisfy and the problems they avoid. It searches through this memory using its current goals and predictions of problems. It uses a notion of similarity between goals and the idea of their relative values to find a "best match" even in those situations where a plan that satisfies all of its goals cannot be found.
Given a set of goals, a case-based planner's approach "anticipate and
avoid" enables it to predict that its normal indexing methods and its normal
modification procedures will result in a failed plan. If there is
a predicted problem, it will search for a plan that avoids that problem
while also satisfying or partially satisfying its current goals.
In other words, a goal, namely the goal to avoid that problem, is added
to the current set of goals. This kind of goals have higher priority
in search than goals to include particular items and tastes but lower than
the goals to make the plan a certain type of dish. Ex: Given three
initial goals "make stir-fry dish", "include chicken", and " include snow
peas", the planner predicts a problem and adds another goal "avoid soggy
vegetables". The goal "avoid soggy vegetables" has higher priority
than "include chicken" and " include snow peas" do but lower than "make
stir-fry dish" does.
A memory of failures predicts failures on the basis of the similarity between past and current situations. An occurrence of failures is predicted using goal features that might cause them. The reoccurrence of features that participated in past failures brings the memory of the failures to mind.
A case-based planner's memory of failures includes the failure state itself, the plan in which the failure occurred, the causal situation that led to the failure, and the features which are predictive of the failure. Of these, the last is the most important.
A memory of failures can be thought of as a simple network of nodes, in which particular failures are connected to the goal features that predict them (see figure 3.8 page 92). This allows the presence of those features to activate the memory of the failure at a later time.
A case-based planner links not only features that were predictive of a failure, but also its actual causes. Ex: The failure of the soufflé to rise was a result of too much liquid as opposed to just the result of adding fruit. In such case, links are made from both the features that predict the failure (such as "include high-moisture fruit") and the actual cause ("too much liquid"). These links enable a planner to predict failures solely from goal features, even in the situation where current goals are different from those that first caused them.
A case-based planner uses the features of its current goals to activate
the memories of any failures. If a failure is recalled, a goal to
avoid it is added to the current set of goals.
A case-based planner's memory of modifiers has to be sensitive to both the goal being added and the plan being altered. Ex: Given only the goal "add a window to a building", the planner cannot make a sufficiently informed decision about what kind of windows to be added, unless the kind of building is known (house, office, factory, etc.).
It combines two storage systems. The first is a static table of standard modifications, indexed by the plan being altered and the goal being added. The second is a dynamic set of ingredient critics that are stored under particular ingredients, indexed by the failures they repair.
CHEF stores rules for modifying plans in a table of steps that is indexed by the goals to be added (e.g., "include meat", "make dish taste hot") and the plan type (e.g., STIR-FRY, SOUFFLÉ, PASTA). A typical one is shown in figure 3.9 (page 98).
Critics are rules that add steps which compensate for the idiosyncrasies
of particular ingredients. They are stored under the ingredient that
they handle. Each of them has a test that it applies to the current
plan, and a modification it makes if test is true. They deal with
the specific problems not covered by the more general modification rules.
An example of a critic is "chicken must be boned"; when substitute chicken
for beef in BEEF-AND-BROCCOLI, the critic step must be added to the plan
in addition to those already in the BEEF-AND-BROCCOLI plan. New critics
can be learned by a planner repairing faulty plans. They are stored
under the item they relate to and indexed by the problems they solve.
All three kinds of memories we have discussed so far are dynamic organizations that are altered in response to failures on the part of the planner. When a case-based planner learns from a failure, it learns
Note that modification rules are different from repair strategies in that the former are designed to add a new goal to existing plans, the latter to alter a plan to achieve the goals that it was supposed to achieve but did not, because of an unforeseen feature of some ingredient or an interaction between many ingredients.
Repair strategies are specific, in that they suggest repairs for particular classes of problems, but they are not domain specific. Examples of repair strategies are SPLIT-AND-REFORM (breaking the parallel plans into serial steps), ALTER-PLAN:SIDE-EFFECT (using a different plan for the initial step that caused the side-effect), and ADJUNCT-PLAN (making use of an adjunct plan that would disable the side-effect).
Repair strategies are stored under planning TOPs (Thematic Organization Packets, see Chapter 2). Each TOP, which corresponds to a planning problem, stores all strategies designed to fix that problem. It is indexed in memory by a causal description of the type of problem it corresponds to. So the strategies stored under each TOP are only recalled when the problems that they fix arise.
When a case-based planner is confronted with a failure it builds up a causal explanation of why that failure has occurred. The explanation describes the steps and states that have caused the failure and the goals that were being served by each of those steps and states. This explanation of the causes of the failure indexes to a TOP and the strategies that will repair the failure. Each repair strategy suggests a repair that breaks a link in the causal chain that leads to the failure.
A case-based planner's memory of plan repairs is indexed by a description of the problems it deals with.