Chapter 3 : GPS and Problem Reduction

1. finding possible paths (operators)
2. traversing the path (control)

Search causes floundering -- not goal driven

In the following we will address 2 goal driven methods

1. Problem Reduction: reduce to subgoals
   have a pattern...method to achieve goal
   e.g. AND-OR trees (goal-acquire tv: subs- steal or earn&buy) MOVER
   AND/OR trees enable question answering
   how did you ... identify goal and report immediate sub
   why did you ... identify goal and report supergoal
   
2. Means-Ends - GPS: understand why (what needs to be done) and try to get there

• in these, path flow is part of the problem (not dynamic determination of states)
• not all processes are good for goal driven (missionary/cannibal - not sharp goal/subgoal division)
• different ways to solve different problems study form of knowledge then which is the best method

Problem Reduction (Goal-reduction)

ANALOGY

Problem: select an answer figure, X, such that A is to B as C is to X gives the best fit

Each of these subgoals, in turn, can be divided still more finely into lower-level subgoals

Procedure (the Analogy problem reduction (do goal tree)):

1. Describe the rule that transforms the figure A into the B figure and the rules that transform the C figure into the various answer figures, the X's (above, left-of, inside)
2. Match the A-to-B rule to each of the C-to-X rules and describe the differences
3. Select the C-to-X that is most like the A-to-B rule. Announce the corresponding X as the correct answer. Rule descriptions have three parts. Two describe relations between subfigures and one describes how subfigures change
   • describe the source figure in terms of the subfigures in it
   • describe the destination figure
   • describe how figures in source are altered to become dest.
   Relations between subfigures:
   
   size - enlarge (scale)
   orientation - rotation, reflection
   location - left-of, inside, above
   remove
   
   Only one subfigure:
   changes - rotation, size
   

   Similarity = (intersections and set differences, size is # of elements ) a X Size(SAB AND SCX) - ß X Size(SAB - SCX) -c X Size(SCX - SAB)

   Be skeptical about such formulas - A procedure that depends on a lot of weights is "suspicious" ... weights are not explicit and expose little constraint (Winston)

   Means-ends:
   Process driven by means to accomplish goals (ends)
   

   GPS: General Problem Solver
   historically important - Newell & Simon 1963
   * "mini-mind" ... general (used means-ends)

   search strategies - forward and backward a mixture makes it possible to solve major parts of a problem then go back and solve small problems in "glueing" big pieces together

   E.g. Robot (Robbie and book)
   GPS coursenotes

   ... protocols and surface phenomenolism ... logic expressions & student ... monkey/banana in back

   Monkey and Banana: Slagle

   HOW?

   Necessary for Means - Ends

   1. state description - structured
      • several aspects
      • several values
   2. operators and preconditions
   3. difference ordering (compare and order)
   4. table of connections
      what operators useful to reduce what differences
   Goal - subgoal --> look at pre-conditions to see what to try next try most important (difference)
   (do most difficult first, else waste effort & time)
   
   Goals: Three kinds of goals handled by GPS (page 285 paper)
   1. transform object A into object B (select subgoal)
   2. reduce difference D on object A (select method)
   3. apply operator Q to object A (apply method)
   GPS is not "modern" control
   
   • normally forward (except differences makes start at back)
   • depth-first it does
     
   • means-ends analysis
   • problem reduction
   • search (depth-first with backtrack)
   • can use planning (if test before action)
     it has
     
   • no parallellism
   • no communication among procedures
   • no new procedures (fixed)

   SOAR CMU ... goal structures

   Closeness and Reformulation

4. Good examples of the importance of proper representation and structure
   
   • closeness - structural simularity what is useful to represent in the structure
   • dynamic representations of structure (pg 8) allow structure to change during problem solving

   Kanal and Chandrasekaran - pattern recognition
   "despite the enormous intrinsic interest in the mathematical problem of designing and improving classification algorithms, the real power often comes from the careful choice of the variables themselves, based on a good knowledge of the domain." (1969)

5. some examples of useful general heuristics for pruning search (control)
   • symbolic closeness
   • reformulation
   Line of reasoning
   what is the problem (is it a general problem type?)
   what representation
   what control
   

   water-jug: what does it mean to be close to 2 (dump, add)

   Blocks-world: gravity ... on(table, x) is significant knowledge

   reformulation: approach from both ends, changes "goal"