I. PROBLEM SOLVING WITH PRODUCTION SYSTEMS

A. `STATE SPACE' Description of Problems

1. Specify the Initial State of the system.
2. Specify the Generators (or Rules) of the system
3. Specify possible Goal States
4. Specify every possible rule sequence.

This implies a `search tree': The `root' is an initial state and possible rule sequences are applied to generate either (a) all possible subsequent states, or (b) a selected subset of states, until a goal state is found. The goal state is any state at which the system should stop.

B. SEARCH METHODS

Some simple methods of searching the state space for a problem are:

• 1. Random search. `generate and test' Randomly apply a rule and see if it is a goal state, then try another and test again. Not practical for large spaces (though it would certainly work for the water jug problem.)
• 2. Systematic, `blind' search. Apply the generators in a fixed order and check each output. Depth-first (follow each path downward far into the tree), Breadth-first (follow each path only one or a few steps, then move on to next path at the same level.)
• 3. Heuristic search. Evaluate partial solutions for how much they help reach goal. Depends on the possibility of evaluating how good the current position is. If such evaluation is possible, then follow the paths that lead closer to the goal. Branch and bound. Forward-chaining or backward-chaining.

C. PRODUCTION SYSTEMS

Systems that search the problem state space for a goal state with IF-THEN rules. Controlled by pattern matching and actions. They have:

1. A set of Rules or Operators . Each consists of a Lefthand Side, LHS, (a pattern) which, when matched in working memory, allows the Righthand Side, RHS, (an action) to be executed (and to change the state of working memory).

Example: `IF (goal eat) & (exists now food) THEN(seek future food)',
`IF (goal eat) & (eat past food) THEN (goal nap)'

2. One or more Databases or Working Memory containing information appropriate for a particular task. Some parts may be permanent and some parts are specialized for the particular problem (eg, one memory for active goals and another for the problem status).

3. An Interpreter or Control Strategy for choosing the order in which rules will be applied to the working memory, and a way of resolving conflict when there are multiple matches of the Lefthand Side of rules. Eg, `if two LHSs match, choose the more specific LHS' or `choose the rule with the lower number.'

EXAMPLE 1: Water Jug Problem. Both a 3-gal and are 4-gal container are supplied, plus unlimited water, unlimited discard possibility and a set of 10 rules representing operations of filling, emptying, and pouring from one to another. Goal: get 2 gals in the 4-gal container. How could one of the correct sequences of rule applications be found? By searching, somehow, for rules which match the `working memory'.

EXAMPLE 2: Phrase Structure Grammar. A Chomsky-style phrase structure is a production system (though the term is not known in linguistics). Eg,

Rule Set:

1) S -> NP VP

2) NP -> Art N

3) VP -> V NP

4) N -> `children', etc

5) V -> `like', etc.

6) Art -> `the', etc.

Then the working memory begins with initial state S, which matches the LHS of rules 1 and 2. The rules replace S with NP VP and then eventually with, eg, `The children like children'.

EXAMPLE 3. Animal Identification Production System. The camel problem.

Advantages: 1) Production systems can model the data-driven property of intelligence. As new information is added to working memory, behavior can change.
2) New rules can be added easily.

Disadvantages.

The consequences of a simple change in the program can be very hard to anticipate when the system gets complex.

Example 3: Travelling Salesman Problem: Find shortest tour returning to start, visiting all cities once. (NB: This is not a task that human's find easy to solve either.)

1. exhaustive search
ntours=T = (n-1)!/2
For n=6, T=60; for n=25, T=3 X 10^23
Classic combinatorial explosion!

2. nearest neighbor heuristic (From current position, pick the city that is closest.)

3. branch and bound search - keep shortest tour found so far, abandon any tours that are longer than it.