%----------------------------------------------------------------------------%

KNOWLEDGE-BASED PROBLEM SOLVING - II: 
CASE-BASED REASONING

%----------------------------------------------------------------------------%

>From Case-Based Planning, Hammond, 1989

Case-Based Planning is the idea of planning as reminding.
(integrates problem solving and memory)

The justification for case-based planning is the need to
learn from experience.
(integrates problem solving and learning)

%----------------------------------------------------------------------------%

CASE RETRIEVAL

                      Plan
                      Memory
                      ^
                      |   |
                      |   |
                          V
Planner's Goels --->  RETRIEVER  ---> ``Best'' Plan
                        /   \
                      /      \
                    /         \
                   Goal          Goal
                   Value         Similarity
                   Hierarchy     Metric



To get a best match, the RETRIEVER needs a plan memory,
a goal similarity metric (in the form of an abstraction hierarchy),
and a goal value hierarchy.

%----------------------------------------------------------------------------%

CASE MODIFICATION

            Modification    Critics
            Rules            /
               \            /
                \          /
  RETRIEVER --->  MODIFIER ---> Modified Plan


To alter old plans to meet new goals, the MODIFIER needs a set of modification
rules, and critics.

The retriever and the modifier are the core of the case-based planner.


%----------------------------------------------------------------------------%

CASE STORAGE


                Plan Memory
                /          \
               /            \
             /               \
  RETRIEVER ---> MODIFIER ---> STORER ---

To place new plans in memory, the STORER needs to index them under the same
features that the RETRIEVER uses to find them: the goals they satisfy and
the situations in which they are appropriate.

%----------------------------------------------------------------------------%

Plan Repair



   RETRIEVER ---> MODIFIER ---> STORER
                                  ^
                                  |
                                  |
Failed  --- REPAIRER  ---> Repaired Plan
Plan           ^       ---> Explanation of Failure
               |
               |
             Repair
             Strategies


To repair failed plans, the REPAIRER requires a vocabulary of
plan failures and repair stratergies that are indexed by that
vocabulary.


With the addition of the REPAIRER, the STORER can index tha plans
by the problems they avoid as well as the goals they satisfy.


%----------------------------------------------------------------------------%

Blame Assignment


Failed Plan --->  REPAIRER ---> Explanation of Failure
                                          |
                                          |
                                          V
                                     ASSIGNER ---> Plan Failure Predictors

To decide which features in a situation are to blame for a failure,
the ASSIGNER needs to be able to describe the causes for the failure.

%----------------------------------------------------------------------------%
                                        
Problem Anticipation


Planner's Goals  ---> ANTICIPATOR ---> Goals and Predictions ---> RETRIEVER
                          ^
                          |
                          |
     ASSIGNER ---> Plan Failure Predictors

To anticipate problems, the ANTICIPATOR needs the information built
by the ASSIGNER.

With the addition of the ANTICIPATOR, the RETRIEVER can serach for plans
on the basis of teh problems they avoid as well as the goals they satisfy.


%----------------------------------------------------------------------------%

CASE REPRESENTATION

A Case is typically represented as a schema.

Example from Hammond's CHEF:

(broccoli-and-tofu
 (ingredients
   ingr1 (tofu lb .5)
   ingr2 (soy-sauce tablespoon 2)
   ingr3 (rice-wine spoon 1)
   ingr4 (corn-starch tablespoon .5)
   ingr5 (sugar spoon 1)
   ingr6 (broccoli lb 1)
   ingr7 (red-pepper piece 6))
 (actions
   act1 (chop object (ingr1) size chunk)
   act2 (marinade object (result act1) 
          in (& ingr2 ingr3 ingr4 ingr5)) time (20)
   act3 (chop object (ingr6) size chunk))
   act4 (stir-fry object (& (result act2) (ingr7) time (1))
   act5 (add object (result act3) to (result act4))
   act6 (stir-fry object (result act5) time (2))
 (style stir-fry))

%----------------------------------------------------------------------------%

CASE INDEXING 

An index is a label. 

In case retrieval, the index to a case can be examined to decide on the
similarity of the case to the new problem. 

%----------------------------------------------------------------------------%

Memory Organization

Cases in memory can be organized in a hierarchy. 

%----------------------------------------------------------------------------%

Object Representation

The relations between objects are represented in the form of
concept hierarchies.


           vegetables
         /        \
    IS-A           IS-A
   /                    \
broccoli              green-pepper

%----------------------------------------------------------------------------%

Copyright (c) Ashok Goel, 1993-97
Associate Professor, College of Computing 
Georgia Institute of Technology, Atlanta, Georgia 30332
Email: <goel@cc.gatech.edu>

%----------------------------------------------------------------------------%