[ CogSci
Summaries home | UP
|
email
]
http://www.jimdavies.org/summaries/
K. Hammond (1989), Case-Based
Planning: Viewing Planning as a Memory Task, chapters 1, Academic Press.
Chapter 1: Planning and Memory
Author of the summary: Patrawadee Prasangsit, 1999, pp@cc.gatech.edu
Cite this paper for:
-
Case-based planning is planning as remembering -- remembering successes,
failures, and repairs, so that they can be reused, avoided, and reapplied,
respectively.
-
A case-based planner's components: RETRIEVER, MODIFIER, STORER, REPAIRER,
ASSIGNER, and ANTICIPATOR.
-
The complete picture is figure 1.6 (page 26). A concise description
is in 1.5.8 (page 28-29).
-
A basic case-based planner must incorporate a RETRIEVER, a MODIFIER, and
a STORER.
Summary:
Case-based planning is planning as remembering -- remembering successes,
failures, and repairs, so that they can be reused, avoided, and reapplied,
respectively.
A case-based planner uses its knowledge of the world and the effects
of its actions in the world to build a plan. The plan becomes a test
of that knowledge. The feedback from the interaction between the
plan and the world is used to modify existing plans and add new plans to
memory, as well as verify the planner's knowledge of the world. Learning
is central to case-based planners.
A new theory of planning
Case-based planning differs from other approaches to planning and problem
solving in three areas:
-
Building an initial plan: it anticipates problems so that planner
can find plans that avoid them. This anticipate and avoid
contrasts
strongly with the create and debug paradigm that has been the thrust
of machine planning in the past.
-
Debugging failed plans: it responds to planning failures by fixing
both the faulty plan (by the alteration of a plan) and its own faulty knowledge
base that allowed it to build the plan incorrectly (by the alteration of
the planner and its understanding of the world).
-
Storing plans for later use: it stores new plans indexed not only
by the goals they satisfy but also by the problems they avoid. This
allows a planner to find plans that achieve the goals while avoiding the
problems it predicts will arise.
Learning from planning
A case-based planner must also be a learning system because it must reuse
its own experiences. This learning breaks down into three types:
-
Plan learning: create new plans it has never encountered before
and store them by positive goals as well as negative effects. Ex:
A plan for going outside in the rain with an umbrella to get a paper would
be indexed by the fact that it is a plan to retrieve a paper and by the
fact that it allows the planner to avoid getting wet.
-
Expectation learning: learn the features that predict the problems.
Ex: The fact that it is raining and the planner has a goal to pick up his
paper would be marked as predictive of the problem of getting wet
-- because these features would be included in any explanation of why the
plan that lacked an umbrella failed.
-
Critic learning: learn the repairs that have to be made if those
problems arise again in different circumstances. Ex: Predicting that
the rain would get someone wet in any case of going outside and that applying
the repair of using an umbrella to a plan for going outside would fix the
problem.
The structure of case-based planning
The planner has remindings that are similar to those people have, but only
has them because they are required to solve particular planning problems.
It is reminded of past episodes for the same reason that people are reminded
of past episodes: these episodes contain information that can help in planning
for new problems.
Why case-based?
The need to learn from experience. It is always useful to make use
of past information. Advantages are, for instance, stored plans include
information about how to avoid problems that the planner tends to encounter,
and for a complex plan that consists of a huge number of steps, it is more
economical to save the entire plan and recall it for reuse than to rebuild
one all over again.
It also seems like a natural way of human to do planning. Ex:
when we dine in a restaurant, we don't attempt to derive the principle
by which a restaurant operates, we merely recall the actions that need
to be taken on our part when the time comes -- be seated, order, eat, pay,
leave.
Plan retrieval
The best match for a set of goals is a plan that maximizes its utility.
Given a set of goals, in order for a RETRIEVER to find a best match, it
needs
-
a memory of plans indexed by the goals they satisfy. In addition,
a planner must also know the states that are currently true so that plans
that are designed for particular situations, not just particular goals,
can be found and used;
-
a similarity metric for judging the similarity of goals that a planner
can use to determine partial matches;
-
a value hierarchy, which tells how much each goal is worth, for
judging the relative utility of plans with respect to a set of goals.
Plan modification
A MODIFIER takes a plan suggested by the RETRIEVER and modifies it to satisfy
goals not already satisfied by the plan. In order to do so, it needs
-
a set of modification rules that are designed for plans and classes
of goals. These rules will be sets of steps that can be added to
particular plans to achieve particular goals. Access to these rules
will allow a MODIFIER to add new steps to a plan in a way that is sensitive
to the type of plan being modified and the particular goal that is being
satisfied. Ex: "If a goal is to have more windows in a building,
then the action is to add a window";
-
a set of critics with knowledge of goal specific requirements which
will enable the planner to tailor the general modifications of a plan to
the specific needs of the items required to achieve particular goals.
Ex: "Use window type A for an office, B for a house, and C for a plant";
-
general plan specifications, so that it does not violate the goals
of the overall plan when it modifies it to satisfy a specific goal.
The RETRIEVER and MODIFIER are the core of a case-based planner.
For a given set of goals, the former finds a past plan that best matches
them, and the latter modifies the plan to satisfy all of the goals.
Plan storage
A STORER stores in the memory new plans indexed by the same features that
the RETRIEVER uses to find them: the goals that they satisfy and the situations
in which they are appropriate. (An example showing the need of the
latter is, "An umbrella prevents one from getting wet when used in the
rain, but not in a flooded basement".) The features used for indexing
are only those relating to satisfying the goals, as opposed to the entire
set of states that are true as a result of running the plan. For
example, a particular circuit will have both "relevant" characteristics,
such as, I/O, implementation costs, size, and so forth, and "irrelevant"
ones, such as, its color, and its overall aesthetic character.
A basic case-based planner must incorporate a RETRIEVER, a MODIFIER,
and a STORER.
Plan repair
The input to the REPAIRER is a faulty plan and some description of the
fault itself (such as the desired state it has failed to achieve or the
undesired state that is has caused to come about). Such description
will be more useful if it also contains an explanation of why a
failure has occurred (Ex: "The engine failed to start because there was
no gas" is far more useful than "The engine did not start"). In order
to repair a plan, the REPAIRER needs
-
description of the planning failures, described through a set of
vocabulary;
-
a set of repair methods indexed by that vocabulary. Note the
relationship between problem and repair is analogous to the relationship
between goals and plans in that plans are indexed by the goals they satisfy
and repair methods are indexed by the types of problems they resolve.
The REPAIRER fixes the faulty plan by addressing the failures. The
new plan, along with the description of the problems that have just been
fixed, is passed on to the STORER. With the addition of the REPAIRER,
the STORER can now index plans by the problems that they avoid as well
as the goals that they satisfy.
Learning from failure
The fact that a plan solves a particular problem is not useful unless the
planner can anticipate that problem in the appropriate circumstances and
use that prediction to find the plan in memory. The ability to do
such prediction rests on the ability to figure out why it happened in the
past. To do that, the planner needs the ASSIGNER, whose function
is to identify which features of a failed plan caused the failure.
The output of the ASSIGNER is not a plan, but instead a knowledge base
of possible problems that can arise and the circumstances that predict
them. As suggested by its name, the ASSIGNER does blame assignment.
Problem anticipation
The job of an ANTICIPATOR is to look at the planner's goals and the situation
that surrounds them and decide if there is anything in the situation that
is predictive of a problem before any other planning is done.
Since plans are indexed by goals they satisfy and problems they avoid,
given a set of goals alone, we cannot make use of the plan library to its
full capability. It therefore makes sense to first call the ANTICIPATOR
to predict potential problems. The anticipated problems, along with
the given set of goals, are then used by the RETRIEVER to retrieve plans.
The final package
In summary, a case-based planner does two things as it builds a plan.
It is trying to satisfy a set of goals using its model of what plans are
appropriate for different situations. But it is also testing that
model of the appropriateness of those plans against the real world so that
later planning will be easier and more reliable. To serve its first
function, the planner has to react to failures by repairing the present
plan. To serve its second function, it has to alter its view of the
world by adding new plans indexed by the problems they solve and by altering
its predictions so that it can anticipate those problems and find the plans
that avoid them.
Back
to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:
JimDavies ( jim@jimdavies.org
)
Last modified: June 14, 1999