Introduction

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

• A solution is represented as a path from the start state to a goal state.

• The search algorithm systematically tests alternate paths to the goal.

• Backtracking allows recovery from paths that fail to reach a goal.

• The open list (unexplored states) and closed list (visited states) keep track of the search's progress.

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

• The productions are rules of the form C → A, where the LHS is known as the condition and the RHS is known as the action. These rules are interpreted as follows: given condition, C, take action A. The action part can be any step in the problem solving process. The condition is the pattern that determines whether the rule applies or not.

• Working memory contains a description of the current state of the world in the problem-solving process. The description is matched against the conditions of the production rules. When a conditions matches, its action is performed. Actions are designed to alter the contents of working memory.

• The recognize-act cycle is the control structure. The patterns contained in working memory are matched agains the conditions of the production rules, which produces a subset of rules known as the conflict set, whose conditions match the contents of working memory. One (or more) of the rules in the conflict set is selected (conflict resolution) and fired, which means its action is performed. The process terminates when no rules match the contents of working memory.

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 memory	Conflict set	Rule fired
0	cbaca	1,2,3	1
1	cabca	2	2
2	acbca	3,2	2
3	acbac	1,3	1
4	acabc	2	2
5	aacbc	3	3
6	aabcc	-	Halt

Background

• Post (1943) proposed the production rule model as a formal theory of computation. It is equivalent in power to a Turing machine.

• Newell and Simon (1960s) General Problem Solver used production system as a model of human cognition. Production rules represent problem-solving skills stored in a person's long-term memory. The working memory represents the person's current focus of attention. Choosing rules to apply occurs through unconscious pattern matching.

• Production systems have been developed for a wide variety of problems, ranging from algebra word problems, mathematical and logical proofs, physics problems, and games.

• John Anderson (1983) proposed a production system known as ACT* as a model of human cognition and learning.

• Newell, Rosenbloom and Laird (1990) proposed a production system known as SOAR (Symbols, Operators AND Rules) as a model of human cognition and learning.

• The OPS (Official Production System) languages are based on the production system model.

• 1980s: Production systems were the basis of rule-based expert systems.

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  |
                                ----------------------

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

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 memory	Conflict set	Rule fired
0	goal	1	1
1	goal,p,q	1,2,3,4	2
2	goal,p,q,r,s	1,2,3,4,5	3
3	goal,p,q,r,s,w	1,2,3,4,5	4
4	goal,p,q,r,s,w,t,u	1,2,3,4,5	5
5	goal,p,q,r,s,w,t,u,v	1,2,3,4,5,6	6
6	goal,p,q,r,s,w,t,u,v,start	1,2,3,4,5,6	halt

In-class Exercise

Perform the search in a data-driven direction.

Search Control

• Data driven (C → A): If C matches, then perform A, changing WM.

• Goal driven (C → A): If A matches a goal in WM, then add C (subgoal) to WM.

• The order of the rules or clauses affects search control.

• Heuristic knowledge can be built into the rules.

• Conflict Resolution: refraction -- if rule C→A has fired, don't refire it until the conditions, C, have changed in WM. (prevents looping)

• Conflict Resolution: recency -- Fire rules whose conditions match the newer additions to WM. (Focused reasoning)

• Conflict Resolution: specificity -- Prefer rules that have more conditions and hence match with fewer WM patterns.

Important Characteristics of Production System Model

• Separation of Knowledge (the Rules) and Control (Recognize-Act Cycle)

• Natural Mapping onto State Space Search (Data or Goal Driven)

• Modularity of Production Rules (Rules represent chunks of knowledge)

• Pattern-Directed Control (More flexible than algorithmic control)

• Opportunities for Heuristic Control can be built into the rules

• Tracing and Explanation (Simple control, informative rules)

• Language Independence

• Model for Human Problem Solving (SOAR, ACT*)