[ CogSci Summaries home | UP | email ]

K. Hammond (1989), Case-Based Planning: Viewing Planning as a Memory Task, chapters 3, Academic Press.

Chapter 3: Planning from Memory

Author of the summary: Patrawadee Prasangsit, 1999, pp@cc.gatech.edu

Cite this paper for:


Memory is defined by not only the objects it stores, but also a description of how they are going to be indexed and searched for.  A memory with no notion of how to find the objects stored there is as useless as a library without a card catalogue.

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:

The first three of these memories are dynamic, meaning that they change in response to the planner's experiences.  They respond to its failures, storing the information as to why and when it failed and how it recovered, and avoid the problems it has already encountered.

Memory of plans

A memory of plans provides initial plans for a set of goals to be satisfied and problems to be avoided.  Without a memory of past successes, a case-based planner's is nothing.  The objects stored in the memory are specific plans.  The vocabulary used to index them is a vocabulary of the goals they satisfy and the problems they avoid.

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.

Memory of failures

A failure is a particular state in the world that has come about or failed to come about as a result of the running of the current plan.

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.

Memory of modifiers

A memory of modifiers provides the alterations that have to be made to an old plan to account for new 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

Memory of repairs

A memory of repairs contain strategies that will be useful in repairing particular plan failures.  It is completely static, meaning that it does not add new strategies nor alters their organization.

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.

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:
JimDavies ( jim@jimdavies.org )

Last modified: June 14, 1999