CPSC 352 -- Artificial Intelligence
Notes: Production Systems

Introduction

In general state-space search is characterized by the following points:

Recursive Search

If a recursive search algorithm is used, we can dispense with the open list. The internal mechanism of recursion keeps track of unexplored children instead of the open list.

function depthsearch(current_state) {        %% closed_list is global
   if current_state is a goal state
       return (success);                         %% Base case: success
   add current_state to closed_list;
   while (current_state has unexamined children) {
       child = next unexamined child;
       if child not member of closed_list
           if depthsearch(child) = success       %% Recursive case
               return (success);
   }
   return (fail);                                %% Base case: failure ==> Backtrack

Basic idea: To find a path from the current state to a goal state, move to a child state and recur. If the child state fails to lead to a goal, try its siblings.

Pattern-Directed Search (PROLOG)

Pattern directed search uses unification to determine when two expressions match, and it uses modus ponens to generate the children states.

function pattern_search(current_goal) {          %% closed_list is global
   if current_state is a member of closed_list   %% Loop test
       return (fail);
   else add current_goal to closed_list;
   while there remain in database unifying facts or rules do {
       case: current_goal unifies with a fact:
           return (success);                     %% Base case: success
       case: current_goal is a conjunction (p ^ ...)
           for each conjunct do
                pattern_search(conjunct);        %% Recursive case
           if pattern_search succeeds for each conjunct
                return (success);                %% Base case: success
           else
                return (fail);                   %% Base case: fail
       case: current_goal unifies with a rule conclusion (p in p :- q)
                  apply goal unifying substitutions to premise (q);
           pattern_search(premise);              %% Recursive case
           if pattern_search succeeds
                return (success);                %% Base case: success
           else
                return (fail);                   %% Base case: fail
   }
   return (fail);                                %% Base case: failure ==> Backtrack

Production Systems

A production system is a model of computation that provides pattern-directed search control using a set of production rules, a working memory, and a recognize-act cycle.

Example: String Rewriting

Production rules can take a wide variety of forms. In this problem we are doing string rewriting of the sort that might be done in certain forms of proof system or in a Lindenmayer system (L-system). Suppose we have the following set of productions:

    1. ba → ab
    2. ca → ac
    3. cb → bc

A production matches if its LHS matches any portion of the string in working memory. The conflict resolution rule in this example is to choose the lowest numbered rule.

Iteration #Working memoryConflict setRule fired
0cbaca1,2,31
1cabca22
2acbca3,22
3acbac1,31
4acabc22
5aacbc33
6aabcc-Halt

Background

Example: Knight's Tour

Problem: Solve the 3 x 3 knight's tour using the production system model. Each legal move is represented as a production rule of the form:

   current_state → new_state

Working memory contains both the current board state and the goal state. Conflict resolution would fire the first rule that avoids creating a loop. The control regime should also allow backtracking. Find a path from square 1 to square 2.

        Production rules
       -----------------
   1. 1 → 8    9.  6 → 1       ----------------------
   2. 1 → 6    10. 6 → 7       |      |      |      |
   3. 2 → 9    11. 7 → 2       |   1  |   2  |   3  |
   4. 2 → 7    12. 7 → 6       ----------------------
   5. 3 → 4    13. 8 → 3       |      |      |      |
   6. 3 → 8    14. 8 → 1       |   4  |   5  |   6  |
   7. 4 → 9    15. 9 → 2       ----------------------
   8. 4 → 3    16. 9 → 4       |      |      |      |
                               |   7  |   8  |   9  |
                                ----------------------
Iteration #Working memoryConflict setRule fired
Current SquareGoal Square
0121,21
18213,1413
2325,65
3427,87
49215,1615
522-Halt

Example: Propositional Calculus

Problem: Given the set of propositional calculus productions, perform goal driven search using the production system approach.

        Production rules
       -----------------
   1.  p ^ q → goal
   2.  r ^ s → p
   3.  w ^ r → p
   4.  t ^ u → q
   5.  v     → s
   6.  start → v ^ r ^ q

Propositional Graph

The following table provides a trace of a goal-driven search. The conflict resolution rule is to use the least recently used rule.
Iteration #Working memoryConflict setRule fired
0goal11
1goal,p,q1,2,3,42
2goal,p,q,r,s1,2,3,4,53
3goal,p,q,r,s,w1,2,3,4,54
4goal,p,q,r,s,w,t,u1,2,3,4,55
5goal,p,q,r,s,w,t,u,v1,2,3,4,5,66
6goal,p,q,r,s,w,t,u,v,start1,2,3,4,5,6halt

In-class Exercise

Perform the search in a data-driven direction.

Search Control

Important Characteristics of Production System Model