Hammond 1989: Case-Based Planning: Viewing Planning as a Memory Task, chapters 2 (Learning from Planning)

[ CogSci Summaries home | UP | email ]
http://www.jimdavies.org/summaries/

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

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

Cite this paper for:

CHEF: a case-based planner which can output new recipes given particular ingredients and tastes.
Thematic Organization Packets (TOPs). The idea behind TOPs is that, there are problems that are caused by interactions between plans and goals. These pieces of information cannot be tied to any individual goal. TOPs provide a means to store such information and strategies to deal with it.

Summary:

A case-based planner learns by correctly indexing its planning experiences in memory. The main task of the learner is to figure out which features a piece of information should be indexed under. A case-based planner learns 1) new plans; 2) the features that predict failures; 3) past repairs to faulty plans that it can reuse. This learning is accomplished by saving the different results of the planner's own experiences.

CHEF

CHEF is a case-based planner. Its domain is Szechwan cooking. It task is to create new recipes given particular ingredients and tastes. The particular problem to be solved is to produce a stir-fried dish with beef and broccoli. Given three goals: the goal to have a stir-fried dish, to include beef and to include broccoli, CHEF does its planning as follows.

It starts by searching for a best-matched plan, which results in a recipe BEEF-WITH-GREEN-BEANS. Goals are partially satisfied.
The fact that there is a partial match between the target goal "to include broccoli", and an object in the existing recipe, "green beans", tells the planner that it can replace the broccoli for the green beans directly.
Object critics allow it to correctly adjust the cooking time appropriate for broccoli and also suggest that broccoli has to be chopped before being stir-fried.
All of the modifications are incorporated to produce a new recipe, BEEF-AND-BROCCOLI.
In addition to the given set of goals, it derives more goals from its knowledge of stir-frying and its understanding of what items are important in this recipe. So it has the understanding that running this plan should result in other six goals, in addition.

CHEF runs the plan in a simulation and checks the goal. One of the goals, in particular "The broccoli is now crisp", cannot be satisfied.

The broccoli is instead soggy.
Not all goals are satisfied. Changing name of this bad recipe to BAD-BEEF-AND-BROCCOLI..

It explains the failure using a set of inference rules that tell it about the effects of each step in its domain on each object in its domain. These rules are used to chain through the steps and states of the plan to answer a set of questions that will form the explanation of why the failure has occurred.

It finds out that "The broccoli is soggy" is caused by thin liquid in the pan, which is a side effect of stir-frying all the ingredients together.

The explanation of the failure is used to find a structure in memory that organizes a set of strategies for solving the problem described by the explanation. These structures are called Thematic Organization Packets (TOPs). The idea behind TOPs is that, there are problems that are caused by interactions between plans and goals. These pieces of information cannot be tied to any individual goal. TOPs provide a means to store such information and strategies to deal with it.

All the TOPs are associated with causal configurations that lead to failures and strategies for fixing them.
In this case, the causal description is: The side effect of liquid coming from "the stir-frying of the beef" disables a precondition of "the stir-frying of the broccoli" that the pan being used is dry. This is used to access the TOP SIDE-EFFECT:DISABLED-CONDITION:CONCURRENT out of the twenty TOPs known to the program.
The mentioned TOP, which relates to the interaction between concurrent plans in which a side effect of one violates a precondition of the other, has three strategies associated with it: SPLIT-AND-REFORM, ALTER-PLAN:SIDE-EFFECT, and ADJUNCT-PLAN.
CHEF can only find one possible instantiation, a specialization of the strategy SPLIT-AND-REFORM (which suggests breaking the parallel plans into serial steps), so it is applied directly to the problem.
The new plan is then: Stir-fry the broccoli, remove it from the plan, stir-fry everything else, add the broccoli, and stir-fry briefly.

Using the explanation of why a failure has occurred, CHEF builds links that will allow it to predict the failure later in similar situations.

Using the beef-and-broccolli-recipe failure, it learns "Meat sweats when it is stir-fried" and "Stir-frying in too much liquid makes vegetables soggy".

It uses its understanding of past failures to anticipate problems that will arise in new situations, as well as to find a plan that avoids it.

While planning for a stir-fried dish with chicken and snow peas, it predicts the possibility of the snow peas getting soggy. It adds a goal to explicitly avoid the problem. The initial set of goals thus are: 1) include chicken in the dish; 2) include snow pea in the dish; 3) make a stir-fry dish; 4) avoid failure of type SIDE-EFFECT:DISABLED-CONDITION:CONCURRENT exemplified by the failure "The broccoli is now soggy" in recipe BEEF-AND-BROCCOLI.

Learning plans

A case-based planner stores the plan itself in a plan memory. It learns in a sense that it figures out the features that should be used to index the plan and then store the plan in memory using them.

In storing a plan, it does not generalize the plan itself. It instead generalizes the features that are used to index the plan in memory. The general indices make it applicable in many situations and the specificity of the plan makes it a powerful tool in those situations in which the match between the desired goals and those satisfied by the plan is a good one.

CHEF stores new plans indexed by the goals they satisfy and the problems they avoid. This is usually the case for other case-based planners as well. It also has to be indexed by the features of a situation that are independent of the goals but do direct the planner to one plan or another. Ex: A plan to call the hotel front desk for a wake-up call is only a good plan for getting up in the morning only if one is spending the night in a hotel, not at home.

Learning to predict failures

The problem of learning to predict a failure is thus that of figuring out which features of an existing situation have caused the failure. When a failure occurs, the planner records a link between features of goals and the failure that they have caused. These memories of failures can be used when the goals arise again. They give the planner the warning that it should find a plan that avoids the problem.

A case-based planner uses the explanation of a failure to identify the features that will predict it. It generalizes these features to the highest level of description allowed by the rules in the explanation. Ex: Generalize from "beef" to "meat", "broccoli" to "vegetables".

When multiple features are required to predict a failure, all of them are linked to the memory of the failure. This memory is not activated unless all of the linked features are present.

In tracing back through the explanation of a failure to the initial causes, a planner passes through states that those original causes have created. Though these states are the ones that are the more proximate causes of the problems but not the first causes, they can also be used to predict the problems in the future.

Learning critics

Aside from storing plans and failures, a case-based planner also stores some of the repairs in the form of critics, indexed by the problems that they solve. These repairs are used when a planner predicts a problem, but cannot find a plan of the proper type to deal with that problem. When this occurs, it has to use a plan that it knows to be faulty and then change it with the same patch it used to repair another faulty plan in the past.

Not all the repairs can be saved. Some failures are the product of multiple ingredients interacting so no one ingredient alone can be blamed and no one ingredient be given a critic that will repair. Some repairs are too complex to transfer to a new problem and therefore are hardly worth storing.

The critic is the actual repair that was built by the strategy to patch the plan. The explanation that is used to repair the plan in the first place identifies where the critics should be stored.

How learning from planning is different

Learning for a case-based planner is a by-product of planning. Planning is a test of the planner's knowledge. When that knowledge fails, the planner can see through its own experience that it needs to learn some new way to discriminate between the situation it thought it was in and the one it is actually in. In the case-based planning sense, learning means storing the different results of the planner's activity indexed by the features that determine their usefulness.

How learning from planning is better

Learning from planning is an improvement over other types of learning in that it uses the knowledge of the planner to determine what to learn, how to index it, and when to learn it at all. All of the improvements come from the basic idea that learning is not separate from planning. Learning is the management of the planner's memory of its own experience so that it can plan more effectively and avoid the problems that it has encountered before.

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:

JimDavies ( jim@jimdavies.org )

Last modified: June 14, 1999