Production Rule Assignment

 Starting State

 A Goal State

Problem 1:
The figure to the left represents a blocks problem.

  • Write a set of production rules that will solve this problem.
  • Hand-simulate the solution.
  • Determine from this simulation the memory bound required by your production rules to solve this problem.
  • Could you compose a set of production rules that would require less memory.

In the worked problems below:

  • the Starting State description provides the language used to describe this domain;
  • the Goal State description provides the interpretation of the goal implied by the picture associated with a problem;
  • the Production Rules provide the rules where:
    • the right hand side (RHS) and the left hand side (LHS) are separated by the symbol " ->";
    • expressions on the RHS receive a conjunctive interpretation;
    • variables are implicitly given an existential interpretation;
    • small letters denote variables, and capital letters denote constants;
    • the relation named "ne" stands for 'not-equal' and is a way of making explicit the constraint that the values ('bindings') of variables must be different;
    • the * notation is used to indicate that the expression must be marked in this fashion....functionally this prevents this expression from being used to match a rule that includes that expression.....if the contents of WM could be deleted then one wouldn't need this operation
    • the expressions on the LHS are interpreted as a set of actions which operate on the WM
    • the bindings of the variables that appear on the RHS of a rule are passed to (available to) the LHS;
    • the order of the production rules is significant here and is used for Conflict Resolution
  • in the trace of the solution the rows shown in yellow depict the successive contents of WM (working memory) where the items in bold italics indicate items which have been added or marked with the * as a result of the application of a production rule to the prior WM. The gray rows indicate which production rule is applied. The bindings for the application of the production rule are shown next to the name of the production rule that was applied.

Problem 1 Answer

 Starting State
 So: on(A,B), on(B,C), on(C,D), on(D,T) clear(A)

Goal State
 Sg: on(A,T)

Production Rules

Put X on Table
 P1: goal(on(x,T)), on(x,y), ne(x,y), ne(y,T), clear(x) ->
                                      on(x,T), clear(y), *goal(on(x,T))


Trace of Solution to Problem 1

WM0
 goal(on(A,T)), on(A,B), on(B,C), on(C,D), on(D,T), clear(A)
P1: with x/A; T/T; y/B

 WM1
 on(A,T), clear(B), *goal(on(A,T)), on(B,C), on(C,D), on(D,T), clear(A)

 Starting State

 A Goal State

Problem 2:
The figure to the left represents a blocks problem.

  • Write a set of production rules that will solve this problem.
  • Hand-simulate the solution.
  • Determine from this simulation the memory bound required by your production rules to solve this problem.
  • Could you compose a set of production rules that would require less memory.
  • If the problem had involved a goal state where D is above C rather than C above D, then could your rule system solve this problem as well?

Problem 2 Answer

 Starting State
 So: on(A,B), on(B,C), on(C,D), on(D,T) clear(A), on(E,G), on(G,T), clear(E)

Goal State
 Sg: on(A,B), on(B,T)

Production Rules

Decompose Conjunctive Goal
 P1: goal(on(x,y) AND on(y,T)), ne(x,y), ne(y,T) ->
                goal(on(x,y)), goal(on(y,T)), *goal(on(x,y) AND on(y,T))

 Introduce SubGoal
 P2: goal(on(x,T)), on(y,x) ne(x,y), ne(y,T) ->
                                                    goal(clear(x))

Clear X
 P3: goal(clear(x)), on(y,x), ne(x,y), clear(y) ->
                              clear(x), on(y,T), *on(y,x), *goal(clear(x))

Put X on Table
 P4: goal(on(x,T)), ne(x,T), on(x,y), clear(x) ->
                               on(x,T), clear(y), *on(x,y), *goal(on(x,T))

Stack X from Table to top of Y
 P5: goal(on(x,y)), on(x,T), clear(x), clear(y), ne(x,y) ->
                         on(x,y), *on(x,T), *clear(y), *goal(on(x,y))


Trace of Solution to Problem 2

WM0
 goal(on(A,B) AND on(B,T)), on(A,B), on(B,C), on(C,D), on(D,T) clear(A), on(E,G), on(G,T), clear(E)
P1: with x/A; y/B; T/T;

 WM1
 goal(on(A,B)), goal(on(B,T)), *goal(on(A,B) AND on(B,T)), on(A,B), on(B,C), on(C,D), on(D,T) clear(A), on(E,G), on(G,T), clear(E)
P2: with x/B; y/A; T/T;

WM2
 goal(clear(B), goal(on(A,B)), goal(on(B,T)), *goal(on(A,B) AND on(B,T)), on(A,B), on(B,C), on(C,D), on(D,T) clear(A), on(E,G), on(G,T), clear(E)
P3: with x/B; y/A; T/T;

WM3
 clear(B), on(A,T), *goal(clear(B), goal(on(A,B)), goal(on(B,T)), *goal(on(A,B) AND on(B,T)), *on(A,B), on(B,C), on(C,D), on(D,T) clear(A), on(E,G), on(G,T), clear(E)
P4: with x/B; T/T; y/C;

WM4
 on(B,T), clear(C), clear(B), on(A,T), *goal(clear(B), goal(on(A,B)), *goal(on(B,T)), *goal(on(A,B) AND on(B,T)), *on(A,B), *on(B,C), on(C,D), on(D,T) clear(A), on(E,G), on(G,T), clear(E)
P5: with x/A; y/B; T/T;

WM5
 on(A,B), on(B,T), clear(C), *clear(B), *on(A,T), *goal(clear(B), *goal(on(A,B)), *goal(on(B,T)), *goal(on(A,B) AND on(B,T)), *on(A,B), *on(B,C), on(C,D), on(D,T) clear(A), on(E,G), on(G,T), clear(E)

Human Cognition - Table of Contents
 © Charles F. Schmidt