CSE 473 Autumn 1998, Copyright, S. Tanimoto, Univ. of Washington 
Introduction to Artificial Intelligence (Oct 9, 1998)

"Production Systems"

• Analogy to a set of neurons
• Unordered and ordered production systems
• Implementations with COND, IF
• Implementation with APPLY
• Discrimination nets

Analogy to a set of neurons

A neuron can be viewed as a sensor/actor combination.

The synapses on the input side collect stimulation.

The component inputs are essentially combined by the neuron, and if the result is sufficiently strong (i.e., a condition is satisfied), then the neuron "fires".

When the neuron fires, it causes changes that affect other neurons.
 
 

Unordered and Ordered Production Systems

When a rule's condition is satisfied, then the rule may "fire" and its action performed.

A set of rules forms an unordered production system, provided no special preference is given to any rule on the basis of its position in an enumeration of the set.

An unordered production system may have several rules whose conditions are satisfied simultaneously.  Their corresponding actions may be conflicting.  For example, one rule may have the action of setting a variable X to 0 while another rule has the action of setting it to 1.

A conflict resolution scheme is needed.

An ordered production system considers the set of rules to be strictly ordered.  Whenever we consider the rules for possible action, the first rule on the list whose condition is satisfied fires.  Then we go back to the head of the list of rules for the next iteration.
 
 
 

Implementations with COND, IF

(cond ((condition1)  (action1))
          ((condition2)  (action2))
          ...
          ((conditionk)  (actionk))  )

Using IF:

(if (condition1)  (action1)
    (if  (condition2)  (action2)
        ...
             (if (conditionk) (actionk)
                  nil
                 ) ... ) )
 
 

Implementations with APPLY or FUNCALL

(defparameter *rules*
  (list (cons #'cond1   #'action1)
           (cons #'cond2  #'action2)
           ...
           (cons #'condk  #'actionk) ) )

(defun apply-rules ()
  (dolist (rule *rules* nil)
     (if (apply (car rule) nil) (progn (apply (cdr rule) nil)
                                                              (return-from 'apply-rules nil) )
       ) ) )
 
 
 
 
 
 

Discrimination Nets

A discrimination net is an implementation of a production system in which common conditions and/or subconditions have been arranged so as to form a tree of tests.  This permits finding the applicable rule more efficiently than the linear searching method.

Discrimination nets have some disadvantages, however.
1. The rules are no longer so easy to read.
2. Changes are more difficult to make to the set of rules because there are dependencies among the various tests that must be taken into consideration.

One possible solution:  Use a "compiler" that accepts an ordered production system as a list of rules and automatically generates the more efficient (discrimination net) from it.
 
 

Last modified: October 8, 1998